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/cmd/dumpresolutions.go b/tools/compliance/cmd/dumpresolutions.go
index 36fbb7d..318cd91 100644
--- a/tools/compliance/cmd/dumpresolutions.go
+++ b/tools/compliance/cmd/dumpresolutions.go
@@ -36,7 +36,7 @@
)
type context struct {
- conditions []string
+ conditions []compliance.LicenseCondition
graphViz bool
labelConditions bool
stripPrefix string
@@ -50,9 +50,9 @@
resolution in the graph. When -dot flag given, outputs nodes and edges
in graphviz directed graph format.
-If one or more '-c condition' conditions are given, outputs the joined
-set of resolutions for all of the conditions. Otherwise, outputs the
-result of the bottom-up and top-down resolve only.
+If one or more '-c condition' conditions are given, outputs the
+resolution for the union of the conditions. Otherwise, outputs the
+resolution for all conditions.
In plain text mode, when '-label_conditions' is requested, the Target
and Origin have colon-separated license conditions appended:
@@ -86,13 +86,17 @@
os.Exit(2)
}
+ lcs := make([]compliance.LicenseCondition, 0, len(*conditions))
+ for _, name := range *conditions {
+ lcs = append(lcs, compliance.RecognizedConditionNames[name])
+ }
ctx := &context{
- conditions: append([]string{}, *conditions...),
+ conditions: lcs,
graphViz: *graphViz,
labelConditions: *labelConditions,
stripPrefix: *stripPrefix,
}
- err := dumpResolutions(ctx, os.Stdout, os.Stderr, flag.Args()...)
+ _, err := dumpResolutions(ctx, os.Stdout, os.Stderr, flag.Args()...)
if err != nil {
if err == failNoneRequested {
flag.Usage()
@@ -104,36 +108,31 @@
}
// dumpResolutions implements the dumpresolutions utility.
-func dumpResolutions(ctx *context, stdout, stderr io.Writer, files ...string) error {
+func dumpResolutions(ctx *context, stdout, stderr io.Writer, files ...string) (*compliance.LicenseGraph, error) {
if len(files) < 1 {
- return failNoneRequested
+ return nil, failNoneRequested
}
// Read the license graph from the license metadata files (*.meta_lic).
licenseGraph, err := compliance.ReadLicenseGraph(os.DirFS("."), stderr, files)
if err != nil {
- return fmt.Errorf("Unable to read license metadata file(s) %q: %v\n", files, err)
+ return nil, fmt.Errorf("Unable to read license metadata file(s) %q: %v\n", files, err)
}
if licenseGraph == nil {
- return failNoLicenses
+ return nil, failNoLicenses
}
- // resolutions will contain the requested set of resolutions.
- var resolutions *compliance.ResolutionSet
-
- resolutions = compliance.ResolveTopDownConditions(licenseGraph)
+ compliance.ResolveTopDownConditions(licenseGraph)
+ cs := compliance.AllLicenseConditions
if len(ctx.conditions) > 0 {
- rlist := make([]*compliance.ResolutionSet, 0, len(ctx.conditions))
+ cs = compliance.NewLicenseConditionSet()
for _, c := range ctx.conditions {
- rlist = append(rlist, compliance.WalkResolutionsForCondition(licenseGraph, resolutions, compliance.ConditionNames{c}))
- }
- if len(rlist) == 1 {
- resolutions = rlist[0]
- } else {
- resolutions = compliance.JoinResolutionSets(rlist...)
+ cs = cs.Plus(c)
}
}
+ resolutions := compliance.WalkResolutionsForCondition(licenseGraph, cs)
+
// nodes maps license metadata file names to graphViz node names when graphViz requested.
nodes := make(map[string]string)
n := 0
@@ -142,11 +141,7 @@
targetOut := func(target *compliance.TargetNode, sep string) string {
tOut := strings.TrimPrefix(target.Name(), ctx.stripPrefix)
if ctx.labelConditions {
- conditions := make([]string, 0, target.LicenseConditions().Count())
- for _, lc := range target.LicenseConditions().AsList() {
- conditions = append(conditions, lc.Name())
- }
- sort.Strings(conditions)
+ conditions := target.LicenseConditions().Names()
if len(conditions) > 0 {
tOut += sep + strings.Join(conditions, sep)
}
@@ -168,26 +163,16 @@
// outputResolution prints a resolution in the requested format to `stdout`, where one can read
// a resolution as `tname` resolves `oname`'s conditions named in `cnames`.
// `tname` is the name of the target the resolution applies to.
- // `oname` is the name of the target where the conditions originate.
// `cnames` is the list of conditions to resolve.
- outputResolution := func(tname, aname, oname string, cnames []string) {
+ outputResolution := func(tname, aname string, cnames []string) {
if ctx.graphViz {
// ... one edge per line labelled with \\n-separated annotations.
tNode := nodes[tname]
aNode := nodes[aname]
- oNode := nodes[oname]
- fmt.Fprintf(stdout, "\t%s -> %s; %s -> %s [label=\"%s\"];\n", tNode, aNode, aNode, oNode, strings.Join(cnames, "\\n"))
+ fmt.Fprintf(stdout, "\t%s -> %s [label=\"%s\"];\n", tNode, aNode, strings.Join(cnames, "\\n"))
} else {
// ... one edge per line with names in a colon-separated tuple.
- fmt.Fprintf(stdout, "%s %s %s %s\n", tname, aname, oname, strings.Join(cnames, ":"))
- }
- }
-
- // outputSingleton prints `tname` to plain text in the unexpected event that `tname` is the name of
- // a target in `resolutions.AppliesTo()` but has no conditions to resolve.
- outputSingleton := func(tname, aname string) {
- if !ctx.graphViz {
- fmt.Fprintf(stdout, "%s %s\n", tname, aname)
+ fmt.Fprintf(stdout, "%s %s %s\n", tname, aname, strings.Join(cnames, ":"))
}
}
@@ -200,16 +185,11 @@
fmt.Fprintf(stdout, "strict digraph {\n\trankdir=LR;\n")
for _, target := range targets {
makeNode(target)
- rl := compliance.ResolutionList(resolutions.Resolutions(target))
+ rl := resolutions.Resolutions(target)
sort.Sort(rl)
for _, r := range rl {
makeNode(r.ActsOn())
}
- conditions := rl.AllConditions().AsList()
- sort.Sort(conditions)
- for _, lc := range conditions {
- makeNode(lc.Origin())
- }
}
}
@@ -222,7 +202,7 @@
tname = targetOut(target, ":")
}
- rl := compliance.ResolutionList(resolutions.Resolutions(target))
+ rl := resolutions.Resolutions(target)
sort.Sort(rl)
for _, r := range rl {
var aname string
@@ -232,38 +212,11 @@
aname = targetOut(r.ActsOn(), ":")
}
- conditions := r.Resolves().AsList()
- sort.Sort(conditions)
-
- // poname is the previous origin name or "" if no previous
- poname := ""
-
// cnames accumulates the list of condition names originating at a single origin that apply to `target`.
- cnames := make([]string, 0, len(conditions))
+ cnames := r.Resolves().Names()
- // Output 1 line for each attachesTo+actsOn+origin combination.
- for _, condition := range conditions {
- var oname string
- if ctx.graphViz {
- oname = condition.Origin().Name()
- } else {
- oname = targetOut(condition.Origin(), ":")
- }
-
- // Detect when origin changes and output prior origin's conditions.
- if poname != oname && poname != "" {
- outputResolution(tname, aname, poname, cnames)
- cnames = cnames[:0]
- }
- poname = oname
- cnames = append(cnames, condition.Name())
- }
- // Output last origin's conditions or a singleton if no origins.
- if poname == "" {
- outputSingleton(tname, aname)
- } else {
- outputResolution(tname, aname, poname, cnames)
- }
+ // Output 1 line for each attachesTo+actsOn combination.
+ outputResolution(tname, aname, cnames)
}
}
// If graphViz output, rank the root nodes together, and complete the directed graph.
@@ -280,5 +233,5 @@
}
fmt.Fprintf(stdout, "}\n}\n")
}
- return nil
+ return licenseGraph, nil
}