Performance and scale.
Defer edge creation.
Don't create edges until the count is known to avoid repeated allocate+
copy operatios.
Limit resolutions.
Allow only a single resolution condition set per target, and overwrite
intermediate results. Reduces memory and obviates allocations.
Propagate fewer conditions.
Instead of propagating notice conditions to parents in graph during
initial resolve, leave them on leaf node, and attach to ancestors in
the final walk. Reduces copies.
Parallelize resolutions.
Use goroutines, mutexes, and waitgroups to resolve branches of the
graph in parallel. Makes better use of available cores.
Don't accumulate resolutions inside non-containers.
During the final resolution walk, only attach actions to ancestors from
the root down until the 1st non-aggregate. Prevents an explosion of
copies in the lower levels of the graph.
Drop origin for scale.
Tracking the origin of every potential origin for every restricted
condition does not scale. By dropping origin, propagating from top
to bottom can prune many redundant paths avoiding an exponential
explosion.
Conditions as bitmask.
Use bit masks for license conditions and condition sets. Reduces maps
and allocations.
Bug: 68860345
Bug: 151177513
Bug: 151953481
Test: m all
Test: m systemlicense
Test: m listshare; out/soong/host/linux-x86/bin/listshare ...
Test: m checkshare; out/soong/host/linux-x86/bin/checkshare ...
Test: m dumpgraph; out/soong/host/linux-x86/dumpgraph ...
Test: m dumpresolutions; out/soong/host/linux-x86/dumpresolutions ...
where ... is the path to the .meta_lic file for the system image. In my
case if
$ export PRODUCT=$(realpath $ANDROID_PRODUCT_OUT --relative-to=$PWD)
... can be expressed as:
${PRODUCT}/gen/META/lic_intermediates/${PRODUCT}/system.img.meta_lic
Change-Id: Ia2ec1b818de6122c239fbd0824754f1d65daffd3
diff --git a/tools/compliance/policy/walk.go b/tools/compliance/policy/walk.go
index 8b6737d..3e73088 100644
--- a/tools/compliance/policy/walk.go
+++ b/tools/compliance/policy/walk.go
@@ -14,27 +14,60 @@
package compliance
+// EdgeContextProvider is an interface for injecting edge-specific context
+// into walk paths.
+type EdgeContextProvider interface {
+ // Context returns the context for `edge` when added to `path`.
+ Context(lg *LicenseGraph, path TargetEdgePath, edge *TargetEdge) interface{}
+}
+
+// NoEdgeContext implements EdgeContextProvider for walks that use no context.
+type NoEdgeContext struct{}
+
+// Context returns nil.
+func (ctx NoEdgeContext) Context(lg *LicenseGraph, path TargetEdgePath, edge *TargetEdge) interface{} {
+ return nil
+}
+
+// ApplicableConditionsContext provides the subset of conditions in `universe`
+// that apply to each edge in a path.
+type ApplicableConditionsContext struct {
+ universe LicenseConditionSet
+}
+
+// Context returns the LicenseConditionSet applicable to the edge.
+func (ctx ApplicableConditionsContext) Context(lg *LicenseGraph, path TargetEdgePath, edge *TargetEdge) interface{} {
+ universe := ctx.universe
+ if len(path) > 0 {
+ universe = path[len(path)-1].ctx.(LicenseConditionSet)
+ }
+ return conditionsAttachingAcrossEdge(lg, edge, universe)
+}
+
// VisitNode is called for each root and for each walked dependency node by
// WalkTopDown. When VisitNode returns true, WalkTopDown will proceed to walk
// down the dependences of the node
-type VisitNode func(*LicenseGraph, *TargetNode, TargetEdgePath) bool
+type VisitNode func(lg *LicenseGraph, target *TargetNode, path TargetEdgePath) bool
// WalkTopDown does a top-down walk of `lg` calling `visit` and descending
// into depenencies when `visit` returns true.
-func WalkTopDown(lg *LicenseGraph, visit VisitNode) {
+func WalkTopDown(ctx EdgeContextProvider, lg *LicenseGraph, visit VisitNode) {
path := NewTargetEdgePath(32)
- // must be indexed for fast lookup
- lg.indexForward()
-
- var walk func(f string)
- walk = func(f string) {
- visitChildren := visit(lg, lg.targets[f], *path)
+ var walk func(fnode *TargetNode)
+ walk = func(fnode *TargetNode) {
+ visitChildren := visit(lg, fnode, *path)
if !visitChildren {
return
}
- for _, edge := range lg.index[f] {
- path.Push(TargetEdge{lg, edge})
+ for _, edge := range fnode.edges {
+ var edgeContext interface{}
+ if ctx == nil {
+ edgeContext = nil
+ } else {
+ edgeContext = ctx.Context(lg, *path, edge)
+ }
+ path.Push(edge, edgeContext)
walk(edge.dependency)
path.Pop()
}
@@ -42,35 +75,164 @@
for _, r := range lg.rootFiles {
path.Clear()
- walk(r)
+ walk(lg.targets[r])
}
}
+// resolutionKey identifies results from walking a specific target for a
+// specific set of conditions.
+type resolutionKey struct {
+ target *TargetNode
+ cs LicenseConditionSet
+}
+
// WalkResolutionsForCondition performs a top-down walk of the LicenseGraph
-// resolving all distributed works for condition `names`.
-func WalkResolutionsForCondition(lg *LicenseGraph, rs *ResolutionSet, names ConditionNames) *ResolutionSet {
+// resolving all distributed works for `conditions`.
+func WalkResolutionsForCondition(lg *LicenseGraph, conditions LicenseConditionSet) ResolutionSet {
shipped := ShippedNodes(lg)
// rmap maps 'attachesTo' targets to the `actsOn` targets and applicable conditions
- //
- // rmap is the resulting ResolutionSet
- rmap := make(map[*TargetNode]actionSet)
+ rmap := make(map[resolutionKey]ActionSet)
- WalkTopDown(lg, func(lg *LicenseGraph, tn *TargetNode, _ TargetEdgePath) bool {
- if _, ok := rmap[tn]; ok {
+ // cmap identifies previously walked target/condition pairs.
+ cmap := make(map[resolutionKey]struct{})
+
+ // result accumulates the resolutions to return.
+ result := make(ResolutionSet)
+ WalkTopDown(ApplicableConditionsContext{conditions}, lg, func(lg *LicenseGraph, tn *TargetNode, path TargetEdgePath) bool {
+ universe := conditions
+ if len(path) > 0 {
+ universe = path[len(path)-1].ctx.(LicenseConditionSet)
+ }
+
+ if universe.IsEmpty() {
+ return false
+ }
+ key := resolutionKey{tn, universe}
+
+ if _, alreadyWalked := cmap[key]; alreadyWalked {
+ pure := true
+ for _, p := range path {
+ target := p.Target()
+ tkey := resolutionKey{target, universe}
+ if _, ok := rmap[tkey]; !ok {
+ rmap[tkey] = make(ActionSet)
+ }
+ // attach prior walk outcome to ancestor
+ for actsOn, cs := range rmap[key] {
+ rmap[tkey][actsOn] = cs
+ }
+ // if prior walk produced results, copy results
+ // to ancestor.
+ if _, ok := result[tn]; ok && pure {
+ if _, ok := result[target]; !ok {
+ result[target] = make(ActionSet)
+ }
+ for actsOn, cs := range result[tn] {
+ result[target][actsOn] = cs
+ }
+ pure = target.IsContainer()
+ }
+ }
+ // if all ancestors are pure aggregates, attach
+ // matching prior walk conditions to self. Prior walk
+ // will not have done so if any ancestor was not an
+ // aggregate.
+ if pure {
+ match := rmap[key][tn].Intersection(universe)
+ if !match.IsEmpty() {
+ if _, ok := result[tn]; !ok {
+ result[tn] = make(ActionSet)
+ }
+ result[tn][tn] = match
+ }
+ }
+ return false
+ }
+ // no need to walk node or dependencies if not shipped
+ if !shipped.Contains(tn) {
+ return false
+ }
+ if _, ok := rmap[key]; !ok {
+ rmap[key] = make(ActionSet)
+ }
+ // add self to walk outcome
+ rmap[key][tn] = tn.resolution
+ cmap[key] = struct{}{}
+ cs := tn.resolution
+ if !cs.IsEmpty() {
+ cs = cs.Intersection(universe)
+ pure := true
+ for _, p := range path {
+ target := p.Target()
+ tkey := resolutionKey{target, universe}
+ if _, ok := rmap[tkey]; !ok {
+ rmap[tkey] = make(ActionSet)
+ }
+ // copy current node's action into ancestor
+ rmap[tkey][tn] = tn.resolution
+ // conditionally put matching conditions into
+ // result
+ if pure && !cs.IsEmpty() {
+ if _, ok := result[target]; !ok {
+ result[target] = make(ActionSet)
+ }
+ result[target][tn] = cs
+ pure = target.IsContainer()
+ }
+ }
+ // if all ancestors are pure aggregates, attach
+ // matching conditions to self.
+ if pure && !cs.IsEmpty() {
+ if _, ok := result[tn]; !ok {
+ result[tn] = make(ActionSet)
+ }
+ result[tn][tn] = cs
+ }
+ }
+ return true
+ })
+
+ return result
+}
+
+// WalkActionsForCondition performs a top-down walk of the LicenseGraph
+// resolving all distributed works for `conditions`.
+func WalkActionsForCondition(lg *LicenseGraph, conditions LicenseConditionSet) ActionSet {
+ shipped := ShippedNodes(lg)
+
+ // cmap identifies previously walked target/condition pairs.
+ cmap := make(map[resolutionKey]struct{})
+
+ // amap maps 'actsOn' targets to the applicable conditions
+ //
+ // amap is the resulting ActionSet
+ amap := make(ActionSet)
+ WalkTopDown(ApplicableConditionsContext{conditions}, lg, func(lg *LicenseGraph, tn *TargetNode, path TargetEdgePath) bool {
+ universe := conditions
+ if len(path) > 0 {
+ universe = path[len(path)-1].ctx.(LicenseConditionSet)
+ }
+ if universe.IsEmpty() {
+ return false
+ }
+ key := resolutionKey{tn, universe}
+ if _, ok := cmap[key]; ok {
return false
}
if !shipped.Contains(tn) {
return false
}
- if as, ok := rs.resolutions[tn]; ok {
- fas := as.byActsOn(shipped).byName(names)
- if !fas.isEmpty() {
- rmap[tn] = fas
+ cs := universe.Intersection(tn.resolution)
+ if !cs.IsEmpty() {
+ if _, ok := amap[tn]; ok {
+ amap[tn] = cs
+ } else {
+ amap[tn] = amap[tn].Union(cs)
}
}
- return tn.IsContainer() // descend into containers
+ return true
})
- return &ResolutionSet{rmap}
+ return amap
}