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