1// Copyright 2021 Google LLC 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package compliance 16 17var ( 18 // AllResolutions is a TraceConditions function that resolves all 19 // unfiltered license conditions. 20 AllResolutions = TraceConditions(func(tn *TargetNode) LicenseConditionSet { return tn.licenseConditions }) 21) 22 23// TraceConditions is a function that returns the conditions to trace for each 24// target node `tn`. 25type TraceConditions func(tn *TargetNode) LicenseConditionSet 26 27// ResolveBottomUpConditions performs a bottom-up walk of the LicenseGraph 28// propagating conditions up the graph as necessary according to the properties 29// of each edge and according to each license condition in question. 30// 31// e.g. if a "restricted" condition applies to a binary, it also applies to all 32// of the statically-linked libraries and the transitive closure of their static 33// dependencies; even if neither they nor the transitive closure of their 34// dependencies originate any "restricted" conditions. The bottom-up walk will 35// not resolve the library and its transitive closure, but the later top-down 36// walk will. 37func ResolveBottomUpConditions(lg *LicenseGraph) { 38 TraceBottomUpConditions(lg, AllResolutions) 39} 40 41// TraceBottomUpConditions performs a bottom-up walk of the LicenseGraph 42// propagating trace conditions from `conditionsFn` up the graph as necessary 43// according to the properties of each edge and according to each license 44// condition in question. 45func TraceBottomUpConditions(lg *LicenseGraph, conditionsFn TraceConditions) { 46 47 // short-cut if already walked and cached 48 lg.onceBottomUp.Do(func() { 49 // amap identifes targets previously walked. (guarded by mu) 50 amap := make(map[*TargetNode]struct{}) 51 52 var walk func(target *TargetNode, treatAsAggregate bool) LicenseConditionSet 53 54 walk = func(target *TargetNode, treatAsAggregate bool) LicenseConditionSet { 55 priorWalkResults := func() (LicenseConditionSet, bool) { 56 if _, alreadyWalked := amap[target]; alreadyWalked { 57 if treatAsAggregate { 58 return target.resolution, true 59 } 60 if !target.pure { 61 return target.resolution, true 62 } 63 // previously walked in a pure aggregate context, 64 // needs to walk again in non-aggregate context 65 } else { 66 target.resolution |= conditionsFn(target) 67 amap[target] = struct{}{} 68 } 69 target.pure = treatAsAggregate 70 return target.resolution, false 71 } 72 cs, alreadyWalked := priorWalkResults() 73 if alreadyWalked { 74 return cs 75 } 76 77 // add all the conditions from all the dependencies 78 for _, edge := range target.edges { 79 // walk dependency to get its conditions 80 dcs := walk(edge.dependency, treatAsAggregate && edge.dependency.IsContainer()) 81 82 // turn those into the conditions that apply to the target 83 dcs = depConditionsPropagatingToTarget(lg, edge, dcs, treatAsAggregate) 84 cs |= dcs 85 } 86 target.resolution |= cs 87 cs = target.resolution 88 89 // return conditions up the tree 90 return cs 91 } 92 93 // walk each of the roots 94 for _, rname := range lg.rootFiles { 95 rnode := lg.targets[rname] 96 _ = walk(rnode, rnode.IsContainer()) 97 } 98 }) 99} 100 101// ResolveTopDownCondtions performs a top-down walk of the LicenseGraph 102// propagating conditions from target to dependency. 103// 104// e.g. For current policy, none of the conditions propagate from target to 105// dependency except restricted. For restricted, the policy is to share the 106// source of any libraries linked to restricted code and to provide notice. 107func ResolveTopDownConditions(lg *LicenseGraph) { 108 TraceTopDownConditions(lg, AllResolutions) 109} 110 111// TraceTopDownCondtions performs a top-down walk of the LicenseGraph 112// propagating trace conditions returned by `conditionsFn` from target to 113// dependency. 114func TraceTopDownConditions(lg *LicenseGraph, conditionsFn TraceConditions) { 115 116 // short-cut if already walked and cached 117 lg.onceTopDown.Do(func() { 118 // start with the conditions propagated up the graph 119 TraceBottomUpConditions(lg, conditionsFn) 120 121 // amap contains the set of targets already walked. (guarded by mu) 122 amap := make(map[*TargetNode]struct{}) 123 124 var walk func(fnode *TargetNode, cs LicenseConditionSet, treatAsAggregate bool) 125 126 walk = func(fnode *TargetNode, cs LicenseConditionSet, treatAsAggregate bool) { 127 continueWalk := func() bool { 128 if _, alreadyWalked := amap[fnode]; alreadyWalked { 129 if cs.IsEmpty() { 130 return false 131 } 132 if cs.Difference(fnode.resolution).IsEmpty() { 133 // no new conditions 134 135 // pure aggregates never need walking a 2nd time with same conditions 136 if treatAsAggregate { 137 return false 138 } 139 // non-aggregates don't need walking as non-aggregate a 2nd time 140 if !fnode.pure { 141 return false 142 } 143 // previously walked as pure aggregate; need to re-walk as non-aggregate 144 } 145 } else { 146 fnode.resolution |= conditionsFn(fnode) 147 } 148 fnode.resolution |= cs 149 fnode.pure = treatAsAggregate 150 amap[fnode] = struct{}{} 151 cs = fnode.resolution 152 return true 153 }() 154 if !continueWalk { 155 return 156 } 157 // for each dependency 158 for _, edge := range fnode.edges { 159 // dcs holds the dpendency conditions inherited from the target 160 dcs := targetConditionsPropagatingToDep(lg, edge, cs, treatAsAggregate, conditionsFn) 161 dnode := edge.dependency 162 // add the conditions to the dependency 163 walk(dnode, dcs, treatAsAggregate && dnode.IsContainer()) 164 } 165 } 166 167 // walk each of the roots 168 for _, rname := range lg.rootFiles { 169 rnode := lg.targets[rname] 170 // add the conditions to the root and its transitive closure 171 walk(rnode, NewLicenseConditionSet(), rnode.IsContainer()) 172 } 173 }) 174} 175