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/test_util.go b/tools/compliance/test_util.go
index a183b90..8f4088a 100644
--- a/tools/compliance/test_util.go
+++ b/tools/compliance/test_util.go
@@ -86,7 +86,6 @@
license_kinds: "legacy_by_exception_only"
license_conditions: "by_exception_only"
`
-
)
var (
@@ -111,23 +110,39 @@
}
)
-// toConditionList converts a test data map of condition name to origin names into a ConditionList.
-func toConditionList(lg *LicenseGraph, conditions map[string][]string) ConditionList {
- cl := make(ConditionList, 0)
- for name, origins := range conditions {
- for _, origin := range origins {
- cl = append(cl, LicenseCondition{name, newTestNode(lg, origin)})
- }
- }
- return cl
-}
-
// newTestNode constructs a test node in the license graph.
func newTestNode(lg *LicenseGraph, targetName string) *TargetNode {
- if _, ok := lg.targets[targetName]; !ok {
- lg.targets[targetName] = &TargetNode{name: targetName}
+ if tn, alreadyExists := lg.targets[targetName]; alreadyExists {
+ return tn
}
- return lg.targets[targetName]
+ tn := &TargetNode{name: targetName}
+ lg.targets[targetName] = tn
+ return tn
+}
+
+// newTestCondition constructs a test license condition in the license graph.
+func newTestCondition(lg *LicenseGraph, targetName string, conditionName string) LicenseCondition {
+ tn := newTestNode(lg, targetName)
+ cl := LicenseConditionSetFromNames(tn, conditionName).AsList()
+ if len(cl) == 0 {
+ panic(fmt.Errorf("attempt to create unrecognized condition: %q", conditionName))
+ } else if len(cl) != 1 {
+ panic(fmt.Errorf("unexpected multiple conditions from condition name: %q: got %d, want 1", conditionName, len(cl)))
+ }
+ lc := cl[0]
+ tn.licenseConditions = tn.licenseConditions.Plus(lc)
+ return lc
+}
+
+// newTestConditionSet constructs a test license condition set in the license graph.
+func newTestConditionSet(lg *LicenseGraph, targetName string, conditionName []string) LicenseConditionSet {
+ tn := newTestNode(lg, targetName)
+ cs := LicenseConditionSetFromNames(tn, conditionName...)
+ if cs.IsEmpty() {
+ panic(fmt.Errorf("attempt to create unrecognized condition: %q", conditionName))
+ }
+ tn.licenseConditions = tn.licenseConditions.Union(cs)
+ return cs
}
// testFS implements a test file system (fs.FS) simulated by a map from filename to []byte content.
@@ -270,6 +285,21 @@
return ReadLicenseGraph(&fs, stderr, roots)
}
+// logGraph outputs a representation of the graph to a test log.
+func logGraph(lg *LicenseGraph, t *testing.T) {
+ t.Logf("license graph:")
+ t.Logf(" targets:")
+ for _, target := range lg.Targets() {
+ t.Logf(" %s%s in package %q", target.Name(), target.LicenseConditions().String(), target.PackageName())
+ }
+ t.Logf(" /targets")
+ t.Logf(" edges:")
+ for _, edge := range lg.Edges() {
+ t.Logf(" %s", edge.String())
+ }
+ t.Logf(" /edges")
+ t.Logf("/license graph")
+}
// byAnnotatedEdge orders edges by target then dep name then annotations.
type byAnnotatedEdge []annotated
@@ -296,33 +326,137 @@
return l[i].target < l[j].target
}
+// act describes test data resolution actions to define test action sets.
+type act struct {
+ actsOn, origin, condition string
+}
+
+// String returns a human-readable string representing the test action.
+func (a act) String() string {
+ return fmt.Sprintf("%s{%s:%s}", a.actsOn, a.origin, a.condition)
+}
+
+// toActionSet converts a list of act test data into a test action set.
+func toActionSet(lg *LicenseGraph, data []act) ActionSet {
+ as := make(ActionSet)
+ for _, a := range data {
+ actsOn := newTestNode(lg, a.actsOn)
+ cs := newTestConditionSet(lg, a.origin, strings.Split(a.condition, "|"))
+ as[actsOn] = cs
+ }
+ return as
+}
+
// res describes test data resolutions to define test resolution sets.
type res struct {
attachesTo, actsOn, origin, condition string
}
// toResolutionSet converts a list of res test data into a test resolution set.
-func toResolutionSet(lg *LicenseGraph, data []res) *ResolutionSet {
- rmap := make(map[*TargetNode]actionSet)
+func toResolutionSet(lg *LicenseGraph, data []res) ResolutionSet {
+ rmap := make(ResolutionSet)
for _, r := range data {
attachesTo := newTestNode(lg, r.attachesTo)
actsOn := newTestNode(lg, r.actsOn)
- origin := newTestNode(lg, r.origin)
if _, ok := rmap[attachesTo]; !ok {
- rmap[attachesTo] = make(actionSet)
+ rmap[attachesTo] = make(ActionSet)
}
- if _, ok := rmap[attachesTo][actsOn]; !ok {
- rmap[attachesTo][actsOn] = newLicenseConditionSet()
- }
- rmap[attachesTo][actsOn].add(origin, r.condition)
+ cs := newTestConditionSet(lg, r.origin, strings.Split(r.condition, ":"))
+ rmap[attachesTo][actsOn] |= cs
}
- return &ResolutionSet{rmap}
+ return rmap
}
+// tcond associates a target name with '|' separated string conditions.
+type tcond struct {
+ target, conditions string
+}
+
+// action represents a single element of an ActionSet for testing.
+type action struct {
+ target *TargetNode
+ cs LicenseConditionSet
+}
+
+// String returns a human-readable string representation of the action.
+func (a action) String() string {
+ return fmt.Sprintf("%s%s", a.target.Name(), a.cs.String())
+}
+
+// actionList represents an array of actions and a total order defined by
+// target name followed by license condition set.
+type actionList []action
+
+// String returns a human-readable string representation of the list.
+func (l actionList) String() string {
+ var sb strings.Builder
+ fmt.Fprintf(&sb, "[")
+ sep := ""
+ for _, a := range l {
+ fmt.Fprintf(&sb, "%s%s", sep, a.String())
+ sep = ", "
+ }
+ fmt.Fprintf(&sb, "]")
+ return sb.String()
+}
+
+// Len returns the count of elements in the slice.
+func (l actionList) Len() int { return len(l) }
+
+// Swap rearranges 2 elements of the slice so that each occupies the other's
+// former position.
+func (l actionList) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
+
+// Less returns true when the `i`th element is lexicographically less than
+// the `j`th element.
+func (l actionList) Less(i, j int) bool {
+ if l[i].target == l[j].target {
+ return l[i].cs < l[j].cs
+ }
+ return l[i].target.Name() < l[j].target.Name()
+}
+
+// asActionList represents the resolved license conditions in a license graph
+// as an actionList for comparison in a test.
+func asActionList(lg *LicenseGraph) actionList {
+ result := make(actionList, 0, len(lg.targets))
+ for _, target := range lg.targets {
+ cs := target.resolution
+ if cs.IsEmpty() {
+ continue
+ }
+ result = append(result, action{target, cs})
+ }
+ return result
+}
+
+// toActionList converts an array of tcond into an actionList for comparison
+// in a test.
+func toActionList(lg *LicenseGraph, actions []tcond) actionList {
+ result := make(actionList, 0, len(actions))
+ for _, actn := range actions {
+ target := newTestNode(lg, actn.target)
+ cs := NewLicenseConditionSet()
+ for _, name := range strings.Split(actn.conditions, "|") {
+ lc, ok := RecognizedConditionNames[name]
+ if !ok {
+ panic(fmt.Errorf("Unrecognized test condition name: %q", name))
+ }
+ cs = cs.Plus(lc)
+ }
+ result = append(result, action{target, cs})
+ }
+ return result
+}
+
+// confl defines test data for a SourceSharePrivacyConflict as a target name,
+// source condition name, privacy condition name triple.
type confl struct {
sourceNode, share, privacy string
}
+// toConflictList converts confl test data into an array of
+// SourceSharePrivacyConflict for comparison in a test.
func toConflictList(lg *LicenseGraph, data []confl) []SourceSharePrivacyConflict {
result := make([]SourceSharePrivacyConflict, 0, len(data))
for _, c := range data {
@@ -334,30 +468,40 @@
cprivacy := fields[1]
result = append(result, SourceSharePrivacyConflict{
newTestNode(lg, c.sourceNode),
- LicenseCondition{cshare, newTestNode(lg, oshare)},
- LicenseCondition{cprivacy, newTestNode(lg, oprivacy)},
+ newTestCondition(lg, oshare, cshare),
+ newTestCondition(lg, oprivacy, cprivacy),
})
}
return result
}
// checkSameActions compares an actual action set to an expected action set for a test.
-func checkSameActions(lg *LicenseGraph, asActual, asExpected actionSet, t *testing.T) {
- rsActual := ResolutionSet{make(map[*TargetNode]actionSet)}
- rsExpected := ResolutionSet{make(map[*TargetNode]actionSet)}
+func checkSameActions(lg *LicenseGraph, asActual, asExpected ActionSet, t *testing.T) {
+ rsActual := make(ResolutionSet)
+ rsExpected := make(ResolutionSet)
testNode := newTestNode(lg, "test")
- rsActual.resolutions[testNode] = asActual
- rsExpected.resolutions[testNode] = asExpected
- checkSame(&rsActual, &rsExpected, t)
+ rsActual[testNode] = asActual
+ rsExpected[testNode] = asExpected
+ checkSame(rsActual, rsExpected, t)
}
// checkSame compares an actual resolution set to an expected resolution set for a test.
-func checkSame(rsActual, rsExpected *ResolutionSet, t *testing.T) {
+func checkSame(rsActual, rsExpected ResolutionSet, t *testing.T) {
+ t.Logf("actual resolution set: %s", rsActual.String())
+ t.Logf("expected resolution set: %s", rsExpected.String())
+
+ actualTargets := rsActual.AttachesTo()
+ sort.Sort(actualTargets)
+
expectedTargets := rsExpected.AttachesTo()
sort.Sort(expectedTargets)
+
+ t.Logf("actual targets: %s", actualTargets.String())
+ t.Logf("expected targets: %s", expectedTargets.String())
+
for _, target := range expectedTargets {
if !rsActual.AttachesToTarget(target) {
- t.Errorf("unexpected missing target: got AttachesToTarget(%q) is false in %s, want true in %s", target.name, rsActual, rsExpected)
+ t.Errorf("unexpected missing target: got AttachesToTarget(%q) is false, want true", target.name)
continue
}
expectedRl := rsExpected.Resolutions(target)
@@ -365,8 +509,8 @@
actualRl := rsActual.Resolutions(target)
sort.Sort(actualRl)
if len(expectedRl) != len(actualRl) {
- t.Errorf("unexpected number of resolutions attach to %q: got %s with %d elements, want %s with %d elements",
- target.name, actualRl, len(actualRl), expectedRl, len(expectedRl))
+ t.Errorf("unexpected number of resolutions attach to %q: %d elements, %d elements",
+ target.name, len(actualRl), len(expectedRl))
continue
}
for i := 0; i < len(expectedRl); i++ {
@@ -375,34 +519,86 @@
target.name, i, actualRl[i].asString(), expectedRl[i].asString())
continue
}
- expectedConditions := expectedRl[i].Resolves().AsList()
- actualConditions := actualRl[i].Resolves().AsList()
- sort.Sort(expectedConditions)
- sort.Sort(actualConditions)
- if len(expectedConditions) != len(actualConditions) {
- t.Errorf("unexpected number of conditions apply to %q acting on %q: got %s with %d elements, want %s with %d elements",
+ expectedConditions := expectedRl[i].Resolves()
+ actualConditions := actualRl[i].Resolves()
+ if expectedConditions != actualConditions {
+ t.Errorf("unexpected conditions apply to %q acting on %q: got %04x with names %s, want %04x with names %s",
target.name, expectedRl[i].actsOn.name,
- actualConditions, len(actualConditions),
- expectedConditions, len(expectedConditions))
+ actualConditions, actualConditions.Names(),
+ expectedConditions, expectedConditions.Names())
continue
}
- for j := 0; j < len(expectedConditions); j++ {
- if expectedConditions[j] != actualConditions[j] {
- t.Errorf("unexpected condition attached to %q acting on %q at index %d: got %s at index %d in %s, want %s in %s",
- target.name, expectedRl[i].actsOn.name, i,
- actualConditions[j].asString(":"), j, actualConditions,
- expectedConditions[j].asString(":"), expectedConditions)
- }
- }
}
}
+ for _, target := range actualTargets {
+ if !rsExpected.AttachesToTarget(target) {
+ t.Errorf("unexpected extra target: got expected.AttachesTo(%q) is false, want true", target.name)
+ }
+ }
+}
+
+// checkResolvesActions compares an actual action set to an expected action set for a test verifying the actual set
+// resolves all of the expected conditions.
+func checkResolvesActions(lg *LicenseGraph, asActual, asExpected ActionSet, t *testing.T) {
+ rsActual := make(ResolutionSet)
+ rsExpected := make(ResolutionSet)
+ testNode := newTestNode(lg, "test")
+ rsActual[testNode] = asActual
+ rsExpected[testNode] = asExpected
+ checkResolves(rsActual, rsExpected, t)
+}
+
+// checkResolves compares an actual resolution set to an expected resolution set for a test verifying the actual set
+// resolves all of the expected conditions.
+func checkResolves(rsActual, rsExpected ResolutionSet, t *testing.T) {
+ t.Logf("actual resolution set: %s", rsActual.String())
+ t.Logf("expected resolution set: %s", rsExpected.String())
+
actualTargets := rsActual.AttachesTo()
sort.Sort(actualTargets)
- for i, target := range actualTargets {
+
+ expectedTargets := rsExpected.AttachesTo()
+ sort.Sort(expectedTargets)
+
+ t.Logf("actual targets: %s", actualTargets.String())
+ t.Logf("expected targets: %s", expectedTargets.String())
+
+ for _, target := range expectedTargets {
+ if !rsActual.AttachesToTarget(target) {
+ t.Errorf("unexpected missing target: got AttachesToTarget(%q) is false, want true", target.name)
+ continue
+ }
+ expectedRl := rsExpected.Resolutions(target)
+ sort.Sort(expectedRl)
+ actualRl := rsActual.Resolutions(target)
+ sort.Sort(actualRl)
+ if len(expectedRl) != len(actualRl) {
+ t.Errorf("unexpected number of resolutions attach to %q: %d elements, %d elements",
+ target.name, len(actualRl), len(expectedRl))
+ continue
+ }
+ for i := 0; i < len(expectedRl); i++ {
+ if expectedRl[i].attachesTo.name != actualRl[i].attachesTo.name || expectedRl[i].actsOn.name != actualRl[i].actsOn.name {
+ t.Errorf("unexpected resolution attaches to %q at index %d: got %s, want %s",
+ target.name, i, actualRl[i].asString(), expectedRl[i].asString())
+ continue
+ }
+ expectedConditions := expectedRl[i].Resolves()
+ actualConditions := actualRl[i].Resolves()
+ if expectedConditions != (expectedConditions & actualConditions) {
+ t.Errorf("expected conditions missing from %q acting on %q: got %04x with names %s, want %04x with names %s",
+ target.name, expectedRl[i].actsOn.name,
+ actualConditions, actualConditions.Names(),
+ expectedConditions, expectedConditions.Names())
+ continue
+ }
+ }
+
+ }
+ for _, target := range actualTargets {
if !rsExpected.AttachesToTarget(target) {
- t.Errorf("unexpected target: got %q element %d in AttachesTo() %s with %d elements in %s, want %s with %d elements in %s",
- target.name, i, actualTargets, len(actualTargets), rsActual, expectedTargets, len(expectedTargets), rsExpected)
+ t.Errorf("unexpected extra target: got expected.AttachesTo(%q) is false, want true", target.name)
}
}
}