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/resolutionset.go b/tools/compliance/resolutionset.go
index 29f3212..893ef26 100644
--- a/tools/compliance/resolutionset.go
+++ b/tools/compliance/resolutionset.go
@@ -19,34 +19,6 @@
 	"strings"
 )
 
-// JoinResolutionSets returns a new ResolutionSet combining the resolutions from
-// multiple resolution sets. All sets must be derived from the same license
-// graph.
-//
-// e.g. combine "restricted", "reciprocal", and "proprietary" resolutions.
-func JoinResolutionSets(resolutions ...*ResolutionSet) *ResolutionSet {
-	if len(resolutions) < 1 {
-		panic(fmt.Errorf("attempt to join 0 resolution sets"))
-	}
-	rmap := make(map[*TargetNode]actionSet)
-	for _, r := range resolutions {
-		if len(r.resolutions) < 1 {
-			continue
-		}
-		for attachesTo, as := range r.resolutions {
-			if as.isEmpty() {
-				continue
-			}
-			if _, ok := rmap[attachesTo]; !ok {
-				rmap[attachesTo] = as.copy()
-				continue
-			}
-			rmap[attachesTo].addSet(as)
-		}
-	}
-	return &ResolutionSet{rmap}
-}
-
 // ResolutionSet describes an immutable set of targets and the license
 // conditions each target must satisfy or "resolve" in a specific context.
 //
@@ -68,8 +40,8 @@
 //
 // An "unencumbered" condition would originate from the binary, and a "notice"
 // condition would originate from the .a library. A ResolutionSet for the
-// context of the Notice policy might apply both conditions to the binary while
-// preserving the origin of each condition. By applying the notice condition to
+// context of the Notice policy might attach both conditions to the binary to
+// act on the origin of each condition. By attaching the notice condition to
 // the binary, the ResolutionSet stipulates the policy that the release of the
 // unencumbered binary must provide suitable notice for the .a library.
 //
@@ -77,228 +49,71 @@
 // validating that a suitable notice has been built into the distribution, or
 // for reporting what notices need to be given.
 //
-// Resolutions for different contexts may be combined in a new ResolutionSet
-// using JoinResolutions(...).
-//
-// See: resolve.go for:
-//  * ResolveBottomUpConditions(...)
-//  * ResolveTopDownForCondition(...)
-// See also: policy.go for:
-//  * ResolveSourceSharing(...)
-//  * ResolveSourcePrivacy(...)
-type ResolutionSet struct {
-	// resolutions maps names of target with applicable conditions to the set of conditions that apply.
-	resolutions map[*TargetNode]actionSet
+// The action is defined by the context. In the above example, the action is
+// providing notice for the module acted on. In another context, the action
+// might be sharing the source-code or preserving the privacy of the module
+// acted on.
+type ResolutionSet map[*TargetNode]ActionSet
+
+// AttachesTo identifies the list of targets triggering action to resolve
+// conditions. (unordered)
+func (rs ResolutionSet) AttachesTo() TargetNodeList {
+	result := make(TargetNodeList, 0, len(rs))
+	for attachesTo := range rs {
+		result = append(result, attachesTo)
+	}
+	return result
 }
 
-// String returns a string representation of the set.
-func (rs *ResolutionSet) String() string {
+
+// AttachesToTarget returns true if the set contains conditions that
+// are `attachedTo`.
+func (rs ResolutionSet) AttachesToTarget(target *TargetNode) bool {
+	_, isPresent := rs[target]
+	return isPresent
+}
+
+
+// Resolutions returns the list of resolutions that `attachedTo`
+// target must resolve. Returns empty list if no conditions apply.
+func (rs ResolutionSet) Resolutions(attachesTo *TargetNode) ResolutionList {
+	as, ok := rs[attachesTo]
+	if !ok {
+		return nil
+	}
+	result := make(ResolutionList, 0, len(as))
+	for actsOn, cs := range as {
+		result = append(result, Resolution{attachesTo, actsOn, cs})
+	}
+	return result
+}
+
+// String returns a human-readable string representation of the set.
+func (rs ResolutionSet) String() string {
 	var sb strings.Builder
 	fmt.Fprintf(&sb, "{")
 	sep := ""
-	for attachesTo, as := range rs.resolutions {
-		fmt.Fprintf(&sb, "%s%s -> %s", sep, attachesTo.name, as.String())
+	for attachesTo, as := range rs {
+		fmt.Fprintf(&sb, "%s%s -> %s", sep, attachesTo.Name(), as.String())
 		sep = ", "
 	}
 	fmt.Fprintf(&sb, "}")
 	return sb.String()
 }
 
-// AttachesTo identifies the list of targets triggering action to resolve
-// conditions. (unordered)
-func (rs *ResolutionSet) AttachesTo() TargetNodeList {
-	targets := make(TargetNodeList, 0, len(rs.resolutions))
-	for attachesTo := range rs.resolutions {
-		targets = append(targets, attachesTo)
-	}
-	return targets
-}
+// ActionSet identifies a set of targets to act on and the license conditions
+// the action will resolve.
+type ActionSet map[*TargetNode]LicenseConditionSet
 
-// ActsOn identifies the list of targets to act on (share, give notice etc.)
-// to resolve conditions. (unordered)
-func (rs *ResolutionSet) ActsOn() TargetNodeList {
-	tset := make(map[*TargetNode]struct{})
-	for _, as := range rs.resolutions {
-		for actsOn := range as {
-			tset[actsOn] = struct{}{}
-		}
-	}
-	targets := make(TargetNodeList, 0, len(tset))
-	for target := range tset {
-		targets = append(targets, target)
-	}
-	return targets
-}
-
-// Origins identifies the list of targets originating conditions to resolve.
-// (unordered)
-func (rs *ResolutionSet) Origins() TargetNodeList {
-	tset := make(map[*TargetNode]struct{})
-	for _, as := range rs.resolutions {
-		for _, cs := range as {
-			for _, origins := range cs.conditions {
-				for origin := range origins {
-					tset[origin] = struct{}{}
-				}
-			}
-		}
-	}
-	targets := make(TargetNodeList, 0, len(tset))
-	for target := range tset {
-		targets = append(targets, target)
-	}
-	return targets
-}
-
-// Resolutions returns the list of resolutions that `attachedTo`
-// target must resolve. Returns empty list if no conditions apply.
-//
-// Panics if `attachedTo` does not appear in the set.
-func (rs *ResolutionSet) Resolutions(attachedTo *TargetNode) ResolutionList {
-	as, ok := rs.resolutions[attachedTo]
-	if !ok {
-		return ResolutionList{}
-	}
-	result := make(ResolutionList, 0, len(as))
+// String returns a human-readable string representation of the set.
+func (as ActionSet) String() string {
+	var sb strings.Builder
+	fmt.Fprintf(&sb, "{")
+	sep := ""
 	for actsOn, cs := range as {
-		result = append(result, Resolution{attachedTo, actsOn, cs.Copy()})
+		fmt.Fprintf(&sb, "%s%s%s", sep, actsOn.Name(), cs.String())
+		sep = ", "
 	}
-	return result
-}
-
-// ResolutionsByActsOn returns the list of resolutions that must `actOn` to
-// resolvee. Returns empty list if no conditions apply.
-//
-// Panics if `actOn` does not appear in the set.
-func (rs *ResolutionSet) ResolutionsByActsOn(actOn *TargetNode) ResolutionList {
-	c := 0
-	for _, as := range rs.resolutions {
-		if _, ok := as[actOn]; ok {
-			c++
-		}
-	}
-	result := make(ResolutionList, 0, c)
-	for attachedTo, as := range rs.resolutions {
-		if cs, ok := as[actOn]; ok {
-			result = append(result, Resolution{attachedTo, actOn, cs.Copy()})
-		}
-	}
-	return result
-}
-
-// AttachesToByOrigin identifies the list of targets requiring action to
-// resolve conditions originating at `origin`. (unordered)
-func (rs *ResolutionSet) AttachesToByOrigin(origin *TargetNode) TargetNodeList {
-	tset := make(map[*TargetNode]struct{})
-	for attachesTo, as := range rs.resolutions {
-		for _, cs := range as {
-			if cs.HasAnyByOrigin(origin) {
-				tset[attachesTo] = struct{}{}
-				break
-			}
-		}
-	}
-	targets := make(TargetNodeList, 0, len(tset))
-	for target := range tset {
-		targets = append(targets, target)
-	}
-	return targets
-}
-
-// AttachesToTarget returns true if the set contains conditions that
-// are `attachedTo`.
-func (rs *ResolutionSet) AttachesToTarget(attachedTo *TargetNode) bool {
-	_, isPresent := rs.resolutions[attachedTo]
-	return isPresent
-}
-
-// AnyByNameAttachToTarget returns true if the set contains conditions matching
-// `names` that attach to `attachedTo`.
-func (rs *ResolutionSet) AnyByNameAttachToTarget(attachedTo *TargetNode, names ...ConditionNames) bool {
-	as, isPresent := rs.resolutions[attachedTo]
-	if !isPresent {
-		return false
-	}
-	for _, cs := range as {
-		for _, cn := range names {
-			for _, name := range cn {
-				_, isPresent = cs.conditions[name]
-				if isPresent {
-					return true
-				}
-			}
-		}
-	}
-	return false
-}
-
-// AllByNameAttachTo returns true if the set contains at least one condition
-// matching each element of `names` for `attachedTo`.
-func (rs *ResolutionSet) AllByNameAttachToTarget(attachedTo *TargetNode, names ...ConditionNames) bool {
-	as, isPresent := rs.resolutions[attachedTo]
-	if !isPresent {
-		return false
-	}
-	for _, cn := range names {
-		found := false
-	asloop:
-		for _, cs := range as {
-			for _, name := range cn {
-				_, isPresent = cs.conditions[name]
-				if isPresent {
-					found = true
-					break asloop
-				}
-			}
-		}
-		if !found {
-			return false
-		}
-	}
-	return true
-}
-
-// IsEmpty returns true if the set contains no conditions to resolve.
-func (rs *ResolutionSet) IsEmpty() bool {
-	for _, as := range rs.resolutions {
-		if !as.isEmpty() {
-			return false
-		}
-	}
-	return true
-}
-
-// compliance-only ResolutionSet methods
-
-// newResolutionSet constructs a new, empty instance of resolutionSetImp for graph `lg`.
-func newResolutionSet() *ResolutionSet {
-	return &ResolutionSet{make(map[*TargetNode]actionSet)}
-}
-
-// addConditions attaches all of the license conditions in `as` to `attachTo` to act on the originating node if not already applied.
-func (rs *ResolutionSet) addConditions(attachTo *TargetNode, as actionSet) {
-	_, ok := rs.resolutions[attachTo]
-	if !ok {
-		rs.resolutions[attachTo] = as.copy()
-		return
-	}
-	rs.resolutions[attachTo].addSet(as)
-}
-
-// add attaches all of the license conditions in `as` to `attachTo` to act on `attachTo` if not already applied.
-func (rs *ResolutionSet) addSelf(attachTo *TargetNode, as actionSet) {
-	for _, cs := range as {
-		if cs.IsEmpty() {
-			return
-		}
-		_, ok := rs.resolutions[attachTo]
-		if !ok {
-			rs.resolutions[attachTo] = make(actionSet)
-		}
-		_, ok = rs.resolutions[attachTo][attachTo]
-		if !ok {
-			rs.resolutions[attachTo][attachTo] = newLicenseConditionSet()
-		}
-		rs.resolutions[attachTo][attachTo].AddSet(cs)
-	}
+	fmt.Fprintf(&sb, "}")
+	return sb.String()
 }