diff --git a/tools/compliance/Android.bp b/tools/compliance/Android.bp
new file mode 100644
index 0000000..648bc9a
--- /dev/null
+++ b/tools/compliance/Android.bp
@@ -0,0 +1,44 @@
+//
+// Copyright (C) 2021 The Android Open Source Project
+//
+// 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 {
+    default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+bootstrap_go_package {
+    name: "compliance-module",
+    srcs: [
+        "actionset.go",
+        "condition.go",
+        "conditionset.go",
+        "graph.go",
+        "readgraph.go",
+        "resolution.go",
+        "resolutionset.go",
+    ],
+    testSrcs: [
+        "condition_test.go",
+        "conditionset_test.go",
+        "readgraph_test.go",
+        "resolutionset_test.go",
+        "test_util.go",
+    ],
+    deps: [
+        "golang-protobuf-proto",
+        "golang-protobuf-encoding-prototext",
+        "license_metadata_proto",
+    ],
+    pkgPath: "compliance",
+}
diff --git a/tools/compliance/actionset.go b/tools/compliance/actionset.go
new file mode 100644
index 0000000..d575321
--- /dev/null
+++ b/tools/compliance/actionset.go
@@ -0,0 +1,110 @@
+// 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
+
+import (
+	"fmt"
+	"sort"
+	"strings"
+)
+
+// actionSet maps `actOn` target nodes to the license conditions the actions resolve.
+type actionSet map[*TargetNode]*LicenseConditionSet
+
+// String returns a string representation of the set.
+func (as actionSet) String() string {
+	var sb strings.Builder
+	fmt.Fprintf(&sb, "{")
+	osep := ""
+	for actsOn, cs := range as {
+		cl := cs.AsList()
+		sort.Sort(cl)
+		fmt.Fprintf(&sb, "%s%s -> %s", osep, actsOn.name, cl.String())
+		osep = ", "
+	}
+	fmt.Fprintf(&sb, "}")
+	return sb.String()
+}
+
+// byName returns the subset of `as` actions where the condition name is in `names`.
+func (as actionSet) byName(names ConditionNames) actionSet {
+	result := make(actionSet)
+	for actsOn, cs := range as {
+		bn := cs.ByName(names)
+		if bn.IsEmpty() {
+			continue
+		}
+		result[actsOn] = bn
+	}
+	return result
+}
+
+// byActsOn returns the subset of `as` where `actsOn` is in the `reachable` target node set.
+func (as actionSet) byActsOn(reachable *TargetNodeSet) actionSet {
+	result := make(actionSet)
+	for actsOn, cs := range as {
+		if !reachable.Contains(actsOn) || cs.IsEmpty() {
+			continue
+		}
+		result[actsOn] = cs.Copy()
+	}
+	return result
+}
+
+// copy returns another actionSet with the same value as `as`
+func (as actionSet) copy() actionSet {
+	result := make(actionSet)
+	for actsOn, cs := range as {
+		if cs.IsEmpty() {
+			continue
+		}
+		result[actsOn] = cs.Copy()
+	}
+	return result
+}
+
+// addSet adds all of the actions of `other` if not already present.
+func (as actionSet) addSet(other actionSet) {
+	for actsOn, cs := range other {
+		as.add(actsOn, cs)
+	}
+}
+
+// add makes the action on `actsOn` to resolve the conditions in `cs` a member of the set.
+func (as actionSet) add(actsOn *TargetNode, cs *LicenseConditionSet) {
+	if acs, ok := as[actsOn]; ok {
+		acs.AddSet(cs)
+	} else {
+		as[actsOn] = cs.Copy()
+	}
+}
+
+// addCondition makes the action on `actsOn` to resolve `lc` a member of the set.
+func (as actionSet) addCondition(actsOn *TargetNode, lc LicenseCondition) {
+	if _, ok := as[actsOn]; !ok {
+		as[actsOn] = newLicenseConditionSet()
+	}
+	as[actsOn].Add(lc)
+}
+
+// isEmpty returns true if no action to resolve a condition exists.
+func (as actionSet) isEmpty() bool {
+	for _, cs := range as {
+		if !cs.IsEmpty() {
+			return false
+		}
+	}
+	return true
+}
diff --git a/tools/compliance/condition.go b/tools/compliance/condition.go
new file mode 100644
index 0000000..e6d23ef
--- /dev/null
+++ b/tools/compliance/condition.go
@@ -0,0 +1,156 @@
+// 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
+
+import (
+	"fmt"
+	"strings"
+)
+
+// LicenseCondition describes an individual license condition or requirement
+// originating at a specific target node. (immutable)
+//
+// e.g. A module licensed under GPL terms would originate a `restricted` condition.
+type LicenseCondition struct {
+	name   string
+	origin *TargetNode
+}
+
+// Name returns the name of the condition. e.g. "restricted" or "notice"
+func (lc LicenseCondition) Name() string {
+	return lc.name
+}
+
+// Origin identifies the TargetNode where the condition originates.
+func (lc LicenseCondition) Origin() *TargetNode {
+	return lc.origin
+}
+
+// asString returns a string representation of a license condition:
+// origin+separator+condition.
+func (lc LicenseCondition) asString(separator string) string {
+	return lc.origin.name + separator + lc.name
+}
+
+// ConditionList implements introspection methods to arrays of LicenseCondition.
+type ConditionList []LicenseCondition
+
+
+// ConditionList orders arrays of LicenseCondition by Origin and Name.
+
+// Len returns the length of the list.
+func (l ConditionList) Len() int      { return len(l) }
+
+// Swap rearranges 2 elements in the list so each occupies the other's former position.
+func (l ConditionList) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
+
+// Less returns true when the `i`th element is lexicographically less than tht `j`th element.
+func (l ConditionList) Less(i, j int) bool {
+	if l[i].origin.name == l[j].origin.name {
+		return l[i].name < l[j].name
+	}
+	return l[i].origin.name < l[j].origin.name
+}
+
+// String returns a string representation of the set.
+func (cl ConditionList) String() string {
+	var sb strings.Builder
+	fmt.Fprintf(&sb, "[")
+	sep := ""
+	for _, lc := range cl {
+		fmt.Fprintf(&sb, "%s%s:%s", sep, lc.origin.name, lc.name)
+		sep = ", "
+	}
+	fmt.Fprintf(&sb, "]")
+	return sb.String()
+}
+
+// HasByName returns true if the list contains any condition matching `name`.
+func (cl ConditionList) HasByName(name ConditionNames) bool {
+	for _, lc := range cl {
+		if name.Contains(lc.name) {
+			return true
+		}
+	}
+	return false
+}
+
+// ByName returns the sublist of conditions that match `name`.
+func (cl ConditionList) ByName(name ConditionNames) ConditionList {
+	result := make(ConditionList, 0, cl.CountByName(name))
+	for _, lc := range cl {
+		if name.Contains(lc.name) {
+			result = append(result, lc)
+		}
+	}
+	return result
+}
+
+// CountByName returns the size of the sublist of conditions that match `name`.
+func (cl ConditionList) CountByName(name ConditionNames) int {
+	size := 0
+	for _, lc := range cl {
+		if name.Contains(lc.name) {
+			size++
+		}
+	}
+	return size
+}
+
+// HasByOrigin returns true if the list contains any condition originating at `origin`.
+func (cl ConditionList) HasByOrigin(origin *TargetNode) bool {
+	for _, lc := range cl {
+		if lc.origin.name == origin.name {
+			return true
+		}
+	}
+	return false
+}
+
+// ByOrigin returns the sublist of conditions that originate at `origin`.
+func (cl ConditionList) ByOrigin(origin *TargetNode) ConditionList {
+	result := make(ConditionList, 0, cl.CountByOrigin(origin))
+	for _, lc := range cl {
+		if lc.origin.name == origin.name {
+			result = append(result, lc)
+		}
+	}
+	return result
+}
+
+// CountByOrigin returns the size of the sublist of conditions that originate at `origin`.
+func (cl ConditionList) CountByOrigin(origin *TargetNode) int {
+	size := 0
+	for _, lc := range cl {
+		if lc.origin.name == origin.name {
+			size++
+		}
+	}
+	return size
+}
+
+// ConditionNames implements the Contains predicate for slices of condition
+// name strings.
+type ConditionNames []string
+
+// Contains returns true if the name matches one of the ConditionNames.
+func (cn ConditionNames) Contains(name string) bool {
+	for _, cname := range cn {
+		if cname == name {
+			return true
+		}
+	}
+	return false
+}
diff --git a/tools/compliance/condition_test.go b/tools/compliance/condition_test.go
new file mode 100644
index 0000000..0507469
--- /dev/null
+++ b/tools/compliance/condition_test.go
@@ -0,0 +1,218 @@
+// 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
+
+import (
+	"sort"
+	"strings"
+	"testing"
+)
+
+func TestConditionNames(t *testing.T) {
+	impliesShare := ConditionNames([]string{"restricted", "reciprocal"})
+
+	if impliesShare.Contains("notice") {
+		t.Errorf("impliesShare.Contains(\"notice\") got true, want false")
+	}
+
+	if !impliesShare.Contains("restricted") {
+		t.Errorf("impliesShare.Contains(\"restricted\") got false, want true")
+	}
+
+	if !impliesShare.Contains("reciprocal") {
+		t.Errorf("impliesShare.Contains(\"reciprocal\") got false, want true")
+	}
+
+	if impliesShare.Contains("") {
+		t.Errorf("impliesShare.Contains(\"\") got true, want false")
+	}
+}
+
+func TestConditionList(t *testing.T) {
+	tests := []struct {
+		name       string
+		conditions map[string][]string
+		byName     map[string][]string
+		byOrigin   map[string][]string
+	}{
+		{
+			name: "noticeonly",
+			conditions: map[string][]string{
+				"notice": []string{"bin1", "lib1"},
+			},
+			byName: map[string][]string{
+				"notice":     []string{"bin1", "lib1"},
+				"restricted": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1": []string{"notice"},
+				"lib1": []string{"notice"},
+				"bin2": []string{},
+				"lib2": []string{},
+			},
+		},
+		{
+			name:       "empty",
+			conditions: map[string][]string{},
+			byName: map[string][]string{
+				"notice":     []string{},
+				"restricted": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1": []string{},
+				"lib1": []string{},
+				"bin2": []string{},
+				"lib2": []string{},
+			},
+		},
+		{
+			name: "everything",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"bin2":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"lib1":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"lib2":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "allbutoneeach",
+			conditions: map[string][]string{
+				"notice":            []string{"bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"reciprocal", "restricted", "by_exception_only"},
+				"bin2":  []string{"notice", "restricted", "by_exception_only"},
+				"lib1":  []string{"notice", "reciprocal", "by_exception_only"},
+				"lib2":  []string{"notice", "reciprocal", "restricted"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "oneeach",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1"},
+				"reciprocal":        []string{"bin2"},
+				"restricted":        []string{"lib1"},
+				"by_exception_only": []string{"lib2"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1"},
+				"reciprocal":        []string{"bin2"},
+				"restricted":        []string{"lib1"},
+				"by_exception_only": []string{"lib2"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"notice"},
+				"bin2":  []string{"reciprocal"},
+				"lib1":  []string{"restricted"},
+				"lib2":  []string{"by_exception_only"},
+				"other": []string{},
+			},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			lg := newLicenseGraph()
+			cl := toConditionList(lg, tt.conditions)
+			for names, expected := range tt.byName {
+				name := ConditionNames(strings.Split(names, ":"))
+				if cl.HasByName(name) {
+					if len(expected) == 0 {
+						t.Errorf("unexpected ConditionList.HasByName(%q): got true, want false", name)
+					}
+				} else {
+					if len(expected) != 0 {
+						t.Errorf("unexpected ConditionList.HasByName(%q): got false, want true", name)
+					}
+				}
+				if len(expected) != cl.CountByName(name) {
+					t.Errorf("unexpected ConditionList.CountByName(%q): got %d, want %d", name, cl.CountByName(name), len(expected))
+				}
+				byName := cl.ByName(name)
+				if len(expected) != len(byName) {
+					t.Errorf("unexpected ConditionList.ByName(%q): got %v, want %v", name, byName, expected)
+				} else {
+					sort.Strings(expected)
+					actual := make([]string, 0, len(byName))
+					for _, lc := range byName {
+						actual = append(actual, lc.Origin().Name())
+					}
+					sort.Strings(actual)
+					for i := 0; i < len(expected); i++ {
+						if expected[i] != actual[i] {
+							t.Errorf("unexpected ConditionList.ByName(%q) index %d in %v: got %s, want %s", name, i, actual, actual[i], expected[i])
+						}
+					}
+				}
+			}
+			for origin, expected := range tt.byOrigin {
+				onode := newTestNode(lg, origin)
+				if cl.HasByOrigin(onode) {
+					if len(expected) == 0 {
+						t.Errorf("unexpected ConditionList.HasByOrigin(%q): got true, want false", origin)
+					}
+				} else {
+					if len(expected) != 0 {
+						t.Errorf("unexpected ConditionList.HasByOrigin(%q): got false, want true", origin)
+					}
+				}
+				if len(expected) != cl.CountByOrigin(onode) {
+					t.Errorf("unexpected ConditionList.CountByOrigin(%q): got %d, want %d", origin, cl.CountByOrigin(onode), len(expected))
+				}
+				byOrigin := cl.ByOrigin(onode)
+				if len(expected) != len(byOrigin) {
+					t.Errorf("unexpected ConditionList.ByOrigin(%q): got %v, want %v", origin, byOrigin, expected)
+				} else {
+					sort.Strings(expected)
+					actual := make([]string, 0, len(byOrigin))
+					for _, lc := range byOrigin {
+						actual = append(actual, lc.Name())
+					}
+					sort.Strings(actual)
+					for i := 0; i < len(expected); i++ {
+						if expected[i] != actual[i] {
+							t.Errorf("unexpected ConditionList.ByOrigin(%q) index %d in %v: got %s, want %s", origin, i, actual, actual[i], expected[i])
+						}
+					}
+				}
+			}
+		})
+	}
+}
diff --git a/tools/compliance/conditionset.go b/tools/compliance/conditionset.go
new file mode 100644
index 0000000..d972eb9
--- /dev/null
+++ b/tools/compliance/conditionset.go
@@ -0,0 +1,269 @@
+// 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
+
+import (
+	"fmt"
+)
+
+// NewLicenseConditionSet creates a new instance or variable of *LicenseConditionSet.
+func NewLicenseConditionSet(conditions ...LicenseCondition) *LicenseConditionSet {
+	cs := newLicenseConditionSet()
+	cs.Add(conditions...)
+	return cs
+}
+
+// LicenseConditionSet describes a mutable set of immutable license conditions.
+type LicenseConditionSet struct {
+	// conditions describes the set of license conditions i.e. (condition name, origin target) pairs
+	// by mapping condition name -> origin target -> true.
+	conditions map[string]map[*TargetNode]bool
+}
+
+// Add makes all `conditions` members of the set if they were not previously.
+func (cs *LicenseConditionSet) Add(conditions ...LicenseCondition) {
+	if len(conditions) == 0 {
+		return
+	}
+	for _, lc := range conditions {
+		if _, ok := cs.conditions[lc.name]; !ok {
+			cs.conditions[lc.name] = make(map[*TargetNode]bool)
+		}
+		cs.conditions[lc.name][lc.origin] = true
+	}
+}
+
+// AddSet makes all elements of `conditions` members of the set if they were not previously.
+func (cs *LicenseConditionSet) AddSet(other *LicenseConditionSet) {
+	if len(other.conditions) == 0 {
+		return
+	}
+	for name, origins := range other.conditions {
+		if len(origins) == 0 {
+			continue
+		}
+		if _, ok := cs.conditions[name]; !ok {
+			cs.conditions[name] = make(map[*TargetNode]bool)
+		}
+		for origin := range origins {
+			cs.conditions[name][origin] = other.conditions[name][origin]
+		}
+	}
+}
+
+// ByName returns a list of the conditions in the set matching `names`.
+func (cs *LicenseConditionSet) ByName(names ...ConditionNames) *LicenseConditionSet {
+	other := newLicenseConditionSet()
+	for _, cn := range names {
+		for _, name := range cn {
+			if origins, ok := cs.conditions[name]; ok {
+				other.conditions[name] = make(map[*TargetNode]bool)
+				for origin := range origins {
+					other.conditions[name][origin] = true
+				}
+			}
+		}
+	}
+	return other
+}
+
+// HasAnyByName returns true if the set contains any conditions matching `names` originating at any target.
+func (cs *LicenseConditionSet) HasAnyByName(names ...ConditionNames) bool {
+	for _, cn := range names {
+		for _, name := range cn {
+			if origins, ok := cs.conditions[name]; ok {
+				if len(origins) > 0 {
+					return true
+				}
+			}
+		}
+	}
+	return false
+}
+
+// CountByName returns the number of conditions matching `names` originating at any target.
+func (cs *LicenseConditionSet) CountByName(names ...ConditionNames) int {
+	size := 0
+	for _, cn := range names {
+		for _, name := range cn {
+			if origins, ok := cs.conditions[name]; ok {
+				size += len(origins)
+			}
+		}
+	}
+	return size
+}
+
+// ByOrigin returns all of the conditions that originate at `origin` regardless of name.
+func (cs *LicenseConditionSet) ByOrigin(origin *TargetNode) *LicenseConditionSet {
+	other := newLicenseConditionSet()
+	for name, origins := range cs.conditions {
+		if _, ok := origins[origin]; ok {
+			other.conditions[name] = make(map[*TargetNode]bool)
+			other.conditions[name][origin] = true
+		}
+	}
+	return other
+}
+
+// HasAnyByOrigin returns true if the set contains any conditions originating at `origin` regardless of condition name.
+func (cs *LicenseConditionSet) HasAnyByOrigin(origin *TargetNode) bool {
+	for _, origins := range cs.conditions {
+		if _, ok := origins[origin]; ok {
+			return true
+		}
+	}
+	return false
+}
+
+// CountByOrigin returns the number of conditions originating at `origin` regardless of condition name.
+func (cs *LicenseConditionSet) CountByOrigin(origin *TargetNode) int {
+	size := 0
+	for _, origins := range cs.conditions {
+		if _, ok := origins[origin]; ok {
+			size++
+		}
+	}
+	return size
+}
+
+// AsList returns a list of all the conditions in the set.
+func (cs *LicenseConditionSet) AsList() ConditionList {
+	result := make(ConditionList, 0, cs.Count())
+	for name, origins := range cs.conditions {
+		for origin := range origins {
+			result = append(result, LicenseCondition{name, origin})
+		}
+	}
+	return result
+}
+
+// Count returns the number of conditions in the set.
+func (cs *LicenseConditionSet) Count() int {
+	size := 0
+	for _, origins := range cs.conditions {
+		size += len(origins)
+	}
+	return size
+}
+
+// Copy creates a new LicenseCondition variable with the same value.
+func (cs *LicenseConditionSet) Copy() *LicenseConditionSet {
+	other := newLicenseConditionSet()
+	for name := range cs.conditions {
+		other.conditions[name] = make(map[*TargetNode]bool)
+		for origin := range cs.conditions[name] {
+			other.conditions[name][origin] = cs.conditions[name][origin]
+		}
+	}
+	return other
+}
+
+// HasCondition returns true if the set contains any condition matching both `names` and `origin`.
+func (cs *LicenseConditionSet) HasCondition(names ConditionNames, origin *TargetNode) bool {
+	for _, name := range names {
+		if origins, ok := cs.conditions[name]; ok {
+			_, isPresent := origins[origin]
+			if isPresent {
+				return true
+			}
+		}
+	}
+	return false
+}
+
+// IsEmpty returns true when the set of conditions contains zero elements.
+func (cs *LicenseConditionSet) IsEmpty() bool {
+	for _, origins := range cs.conditions {
+		if 0 < len(origins) {
+			return false
+		}
+	}
+	return true
+}
+
+// RemoveAllByName changes the set to delete all conditions matching `names`.
+func (cs *LicenseConditionSet) RemoveAllByName(names ...ConditionNames) {
+	for _, cn := range names {
+		for _, name := range cn {
+			delete(cs.conditions, name)
+		}
+	}
+}
+
+// Remove changes the set to delete `conditions`.
+func (cs *LicenseConditionSet) Remove(conditions ...LicenseCondition) {
+	for _, lc := range conditions {
+		if _, isPresent := cs.conditions[lc.name]; !isPresent {
+			panic(fmt.Errorf("attempt to remove non-existent condition: %q", lc.asString(":")))
+		}
+		if _, isPresent := cs.conditions[lc.name][lc.origin]; !isPresent {
+			panic(fmt.Errorf("attempt to remove non-existent origin: %q", lc.asString(":")))
+		}
+		delete(cs.conditions[lc.name], lc.origin)
+	}
+}
+
+// removeSet changes the set to delete all conditions also present in `other`.
+func (cs *LicenseConditionSet) RemoveSet(other *LicenseConditionSet) {
+	for name, origins := range other.conditions {
+		if _, isPresent := cs.conditions[name]; !isPresent {
+			continue
+		}
+		for origin := range origins {
+			delete(cs.conditions[name], origin)
+		}
+	}
+}
+
+// compliance-only LicenseConditionSet methods
+
+// newLicenseConditionSet constructs a set of `conditions`.
+func newLicenseConditionSet() *LicenseConditionSet {
+	return &LicenseConditionSet{make(map[string]map[*TargetNode]bool)}
+}
+
+// add changes the set to include each element of `conditions` originating at `origin`.
+func (cs *LicenseConditionSet) add(origin *TargetNode, conditions ...string) {
+	for _, name := range conditions {
+		if _, ok := cs.conditions[name]; !ok {
+			cs.conditions[name] = make(map[*TargetNode]bool)
+		}
+		cs.conditions[name][origin] = true
+	}
+}
+
+// asStringList returns the conditions in the set as `separator`-separated (origin, condition-name) pair strings.
+func (cs *LicenseConditionSet) asStringList(separator string) []string {
+	result := make([]string, 0, cs.Count())
+	for name, origins := range cs.conditions {
+		for origin := range origins {
+			result = append(result, origin.name+separator+name)
+		}
+	}
+	return result
+}
+
+// conditionNamesArray implements a `contains` predicate for arrays of ConditionNames
+type conditionNamesArray []ConditionNames
+
+func (cn conditionNamesArray) contains(name string) bool {
+	for _, names := range cn {
+		if names.Contains(name) {
+			return true
+		}
+	}
+	return false
+}
diff --git a/tools/compliance/conditionset_test.go b/tools/compliance/conditionset_test.go
new file mode 100644
index 0000000..eac0680
--- /dev/null
+++ b/tools/compliance/conditionset_test.go
@@ -0,0 +1,590 @@
+// 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
+
+import (
+	"sort"
+	"strings"
+	"testing"
+)
+
+type byName map[string][]string
+
+func (bn byName) checkPublic(ls *LicenseConditionSet, t *testing.T) {
+	for names, expected := range bn {
+		name := ConditionNames(strings.Split(names, ":"))
+		if ls.HasAnyByName(name) {
+			if len(expected) == 0 {
+				t.Errorf("unexpected LicenseConditionSet.HasAnyByName(%q): got true, want false", name)
+			}
+		} else {
+			if len(expected) != 0 {
+				t.Errorf("unexpected LicenseConditionSet.HasAnyByName(%q): got false, want true", name)
+			}
+		}
+		if len(expected) != ls.CountByName(name) {
+			t.Errorf("unexpected LicenseConditionSet.CountByName(%q): got %d, want %d", name, ls.CountByName(name), len(expected))
+		}
+		byName := ls.ByName(name).AsList()
+		if len(expected) != len(byName) {
+			t.Errorf("unexpected LicenseConditionSet.ByName(%q): got %v, want %v", name, byName, expected)
+		} else {
+			sort.Strings(expected)
+			actual := make([]string, 0, len(byName))
+			for _, lc := range byName {
+				actual = append(actual, lc.Origin().Name())
+			}
+			sort.Strings(actual)
+			for i := 0; i < len(expected); i++ {
+				if expected[i] != actual[i] {
+					t.Errorf("unexpected LicenseConditionSet.ByName(%q) index %d in %v: got %s, want %s", name, i, actual, actual[i], expected[i])
+				}
+			}
+		}
+	}
+}
+
+type byOrigin map[string][]string
+
+func (bo byOrigin) checkPublic(lg *LicenseGraph, ls *LicenseConditionSet, t *testing.T) {
+	expectedCount := 0
+	for origin, expected := range bo {
+		expectedCount += len(expected)
+		onode := newTestNode(lg, origin)
+		if ls.HasAnyByOrigin(onode) {
+			if len(expected) == 0 {
+				t.Errorf("unexpected LicenseConditionSet.HasAnyByOrigin(%q): got true, want false", origin)
+			}
+		} else {
+			if len(expected) != 0 {
+				t.Errorf("unexpected LicenseConditionSet.HasAnyByOrigin(%q): got false, want true", origin)
+			}
+		}
+		if len(expected) != ls.CountByOrigin(onode) {
+			t.Errorf("unexpected LicenseConditionSet.CountByOrigin(%q): got %d, want %d", origin, ls.CountByOrigin(onode), len(expected))
+		}
+		byOrigin := ls.ByOrigin(onode).AsList()
+		if len(expected) != len(byOrigin) {
+			t.Errorf("unexpected LicenseConditionSet.ByOrigin(%q): got %v, want %v", origin, byOrigin, expected)
+		} else {
+			sort.Strings(expected)
+			actual := make([]string, 0, len(byOrigin))
+			for _, lc := range byOrigin {
+				actual = append(actual, lc.Name())
+			}
+			sort.Strings(actual)
+			for i := 0; i < len(expected); i++ {
+				if expected[i] != actual[i] {
+					t.Errorf("unexpected LicenseConditionSet.ByOrigin(%q) index %d in %v: got %s, want %s", origin, i, actual, actual[i], expected[i])
+				}
+			}
+		}
+	}
+	if expectedCount != ls.Count() {
+		t.Errorf("unexpected LicenseConditionSet.Count(): got %d, want %d", ls.Count(), expectedCount)
+	}
+	if ls.IsEmpty() {
+		if expectedCount != 0 {
+			t.Errorf("unexpected LicenseConditionSet.IsEmpty(): got true, want false")
+		}
+	} else {
+		if expectedCount == 0 {
+			t.Errorf("unexpected LicenseConditionSet.IsEmpty(): got false, want true")
+		}
+	}
+}
+
+func TestConditionSet(t *testing.T) {
+	tests := []struct {
+		name       string
+		conditions map[string][]string
+		add        map[string][]string
+		byName     map[string][]string
+		byOrigin   map[string][]string
+	}{
+		{
+			name:       "empty",
+			conditions: map[string][]string{},
+			add:        map[string][]string{},
+			byName: map[string][]string{
+				"notice":     []string{},
+				"restricted": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1": []string{},
+				"lib1": []string{},
+				"bin2": []string{},
+				"lib2": []string{},
+			},
+		},
+		{
+			name: "noticeonly",
+			conditions: map[string][]string{
+				"notice": []string{"bin1", "lib1"},
+			},
+			byName: map[string][]string{
+				"notice":     []string{"bin1", "lib1"},
+				"restricted": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1": []string{"notice"},
+				"lib1": []string{"notice"},
+				"bin2": []string{},
+				"lib2": []string{},
+			},
+		},
+		{
+			name: "noticeonlyadded",
+			conditions: map[string][]string{
+				"notice": []string{"bin1", "lib1"},
+			},
+			add: map[string][]string{
+				"notice": []string{"bin1", "bin2"},
+			},
+			byName: map[string][]string{
+				"notice":     []string{"bin1", "bin2", "lib1"},
+				"restricted": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1": []string{"notice"},
+				"lib1": []string{"notice"},
+				"bin2": []string{"notice"},
+				"lib2": []string{},
+			},
+		},
+		{
+			name: "everything",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			add: map[string][]string{
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"bin2":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"lib1":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"lib2":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "allbutoneeach",
+			conditions: map[string][]string{
+				"notice":            []string{"bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"reciprocal", "restricted", "by_exception_only"},
+				"bin2":  []string{"notice", "restricted", "by_exception_only"},
+				"lib1":  []string{"notice", "reciprocal", "by_exception_only"},
+				"lib2":  []string{"notice", "reciprocal", "restricted"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "allbutoneeachadded",
+			conditions: map[string][]string{
+				"notice":            []string{"bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1"},
+			},
+			add: map[string][]string{
+				"notice":            []string{"bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"reciprocal", "restricted", "by_exception_only"},
+				"bin2":  []string{"notice", "restricted", "by_exception_only"},
+				"lib1":  []string{"notice", "reciprocal", "by_exception_only"},
+				"lib2":  []string{"notice", "reciprocal", "restricted"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "allbutoneeachfilled",
+			conditions: map[string][]string{
+				"notice":            []string{"bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1"},
+			},
+			add: map[string][]string{
+				"notice":            []string{"bin1", "bin2", "lib1"},
+				"reciprocal":        []string{"bin1", "bin2", "lib2"},
+				"restricted":        []string{"bin1", "lib1", "lib2"},
+				"by_exception_only": []string{"bin2", "lib1", "lib2"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"bin2":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"lib1":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"lib2":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "oneeach",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1"},
+				"reciprocal":        []string{"bin2"},
+				"restricted":        []string{"lib1"},
+				"by_exception_only": []string{"lib2"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1"},
+				"reciprocal":        []string{"bin2"},
+				"restricted":        []string{"lib1"},
+				"by_exception_only": []string{"lib2"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"notice"},
+				"bin2":  []string{"reciprocal"},
+				"lib1":  []string{"restricted"},
+				"lib2":  []string{"by_exception_only"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "oneeachoverlap",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1"},
+				"reciprocal":        []string{"bin2"},
+				"restricted":        []string{"lib1"},
+				"by_exception_only": []string{"lib2"},
+			},
+			add: map[string][]string{
+				"notice":            []string{"lib2"},
+				"reciprocal":        []string{"lib1"},
+				"restricted":        []string{"bin2"},
+				"by_exception_only": []string{"bin1"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1", "lib2"},
+				"reciprocal":        []string{"bin2", "lib1"},
+				"restricted":        []string{"bin2", "lib1"},
+				"by_exception_only": []string{"bin1", "lib2"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"by_exception_only", "notice"},
+				"bin2":  []string{"reciprocal", "restricted"},
+				"lib1":  []string{"reciprocal", "restricted"},
+				"lib2":  []string{"by_exception_only", "notice"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "oneeachadded",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1"},
+				"reciprocal":        []string{"bin2"},
+				"restricted":        []string{"lib1"},
+				"by_exception_only": []string{"lib2"},
+			},
+			add: map[string][]string{
+				"notice":            []string{"bin1"},
+				"reciprocal":        []string{"bin2"},
+				"restricted":        []string{"lib1"},
+				"by_exception_only": []string{"lib2"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1"},
+				"reciprocal":        []string{"bin2"},
+				"restricted":        []string{"lib1"},
+				"by_exception_only": []string{"lib2"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"notice"},
+				"bin2":  []string{"reciprocal"},
+				"lib1":  []string{"restricted"},
+				"lib2":  []string{"by_exception_only"},
+				"other": []string{},
+			},
+		},
+	}
+	for _, tt := range tests {
+		testPublicInterface := func(lg *LicenseGraph, cs *LicenseConditionSet, t *testing.T) {
+			byName(tt.byName).checkPublic(cs, t)
+			byOrigin(tt.byOrigin).checkPublic(lg, cs, t)
+		}
+		t.Run(tt.name+"_public_interface", func(t *testing.T) {
+			lg := newLicenseGraph()
+			cs := NewLicenseConditionSet(toConditionList(lg, tt.conditions)...)
+			if tt.add != nil {
+				cs.Add(toConditionList(lg, tt.add)...)
+			}
+			testPublicInterface(lg, cs, t)
+		})
+
+		t.Run("Copy() of "+tt.name+"_public_interface", func(t *testing.T) {
+			lg := newLicenseGraph()
+			cs := NewLicenseConditionSet(toConditionList(lg, tt.conditions)...)
+			if tt.add != nil {
+				cs.Add(toConditionList(lg, tt.add)...)
+			}
+			testPublicInterface(lg, cs.Copy(), t)
+		})
+
+		testPrivateInterface := func(lg *LicenseGraph, cs *LicenseConditionSet, t *testing.T) {
+			slist := make([]string, 0, cs.Count())
+			for origin, expected := range tt.byOrigin {
+				for _, name := range expected {
+					slist = append(slist, origin+";"+name)
+				}
+			}
+			actualSlist := cs.asStringList(";")
+			if len(slist) != len(actualSlist) {
+				t.Errorf("unexpected LicenseConditionSet.asStringList(\";\"): got %v, want %v", actualSlist, slist)
+			} else {
+				sort.Strings(slist)
+				sort.Strings(actualSlist)
+				for i := 0; i < len(slist); i++ {
+					if slist[i] != actualSlist[i] {
+						t.Errorf("unexpected LicenseConditionSet.asStringList(\";\") index %d in %v: got %s, want %s", i, actualSlist, actualSlist[i], slist[i])
+					}
+				}
+			}
+		}
+
+		t.Run(tt.name+"_private_list_interface", func(t *testing.T) {
+			lg := newLicenseGraph()
+			cs := newLicenseConditionSet()
+			for name, origins := range tt.conditions {
+				for _, origin := range origins {
+					cs.add(newTestNode(lg, origin), name)
+				}
+			}
+			if tt.add != nil {
+				cs.Add(toConditionList(lg, tt.add)...)
+			}
+			testPrivateInterface(lg, cs, t)
+		})
+
+		t.Run(tt.name+"_private_set_interface", func(t *testing.T) {
+			lg := newLicenseGraph()
+			cs := newLicenseConditionSet()
+			for name, origins := range tt.conditions {
+				for _, origin := range origins {
+					cs.add(newTestNode(lg, origin), name)
+				}
+			}
+			if tt.add != nil {
+				other := newLicenseConditionSet()
+				for name, origins := range tt.add {
+					for _, origin := range origins {
+						other.add(newTestNode(lg, origin), name)
+					}
+				}
+				cs.AddSet(other)
+			}
+			testPrivateInterface(lg, cs, t)
+		})
+	}
+}
+
+func TestConditionSet_Removals(t *testing.T) {
+	tests := []struct {
+		name         string
+		conditions   map[string][]string
+		removeByName []ConditionNames
+		removeSet    map[string][]string
+		byName       map[string][]string
+		byOrigin     map[string][]string
+	}{
+		{
+			name:         "emptybyname",
+			conditions:   map[string][]string{},
+			removeByName: []ConditionNames{{"reciprocal", "restricted"}},
+			byName: map[string][]string{
+				"notice":     []string{},
+				"restricted": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1": []string{},
+				"lib1": []string{},
+				"bin2": []string{},
+				"lib2": []string{},
+			},
+		},
+		{
+			name:       "emptybyset",
+			conditions: map[string][]string{},
+			removeSet: map[string][]string{
+				"notice":     []string{"bin1", "bin2"},
+				"restricted": []string{"lib1", "lib2"},
+			},
+			byName: map[string][]string{
+				"notice":     []string{},
+				"restricted": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1": []string{},
+				"lib1": []string{},
+				"bin2": []string{},
+				"lib2": []string{},
+			},
+		},
+		{
+			name: "everythingremovenone",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			removeByName: []ConditionNames{{"permissive", "unencumbered"}},
+			removeSet: map[string][]string{
+				"notice": []string{"apk1"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"bin2":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"lib1":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"lib2":  []string{"notice", "reciprocal", "restricted", "by_exception_only"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "everythingremovesome",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			removeByName: []ConditionNames{{"restricted", "by_exception_only"}},
+			removeSet: map[string][]string{
+				"notice": []string{"lib1"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{"bin1", "bin2", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{},
+				"by_exception_only": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{"notice", "reciprocal"},
+				"bin2":  []string{"notice", "reciprocal"},
+				"lib1":  []string{"reciprocal"},
+				"lib2":  []string{"notice", "reciprocal"},
+				"other": []string{},
+			},
+		},
+		{
+			name: "everythingremoveall",
+			conditions: map[string][]string{
+				"notice":            []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted":        []string{"bin1", "bin2", "lib1", "lib2"},
+				"by_exception_only": []string{"bin1", "bin2", "lib1", "lib2"},
+			},
+			removeByName: []ConditionNames{{"restricted", "by_exception_only"}},
+			removeSet: map[string][]string{
+				"notice":     []string{"bin1", "bin2", "lib1", "lib2"},
+				"reciprocal": []string{"bin1", "bin2", "lib1", "lib2"},
+				"restricted": []string{"bin1"},
+			},
+			byName: map[string][]string{
+				"permissive":        []string{},
+				"notice":            []string{},
+				"reciprocal":        []string{},
+				"restricted":        []string{},
+				"by_exception_only": []string{},
+			},
+			byOrigin: map[string][]string{
+				"bin1":  []string{},
+				"bin2":  []string{},
+				"lib1":  []string{},
+				"lib2":  []string{},
+				"other": []string{},
+			},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			lg := newLicenseGraph()
+			cs := newLicenseConditionSet()
+			for name, origins := range tt.conditions {
+				for _, origin := range origins {
+					cs.add(newTestNode(lg, origin), name)
+				}
+			}
+			if tt.removeByName != nil {
+				cs.RemoveAllByName(tt.removeByName...)
+			}
+			if tt.removeSet != nil {
+				other := newLicenseConditionSet()
+				for name, origins := range tt.removeSet {
+					for _, origin := range origins {
+						other.add(newTestNode(lg, origin), name)
+					}
+				}
+				cs.RemoveSet(other)
+			}
+			byName(tt.byName).checkPublic(cs, t)
+			byOrigin(tt.byOrigin).checkPublic(lg, cs, t)
+		})
+	}
+}
diff --git a/tools/compliance/graph.go b/tools/compliance/graph.go
new file mode 100644
index 0000000..9dcfa66
--- /dev/null
+++ b/tools/compliance/graph.go
@@ -0,0 +1,503 @@
+// 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
+
+import (
+	"fmt"
+	"sort"
+	"strings"
+	"sync"
+)
+
+// LicenseGraph describes the immutable license metadata for a set of root
+// targets and the transitive closure of their dependencies.
+//
+// Alternatively, a graph is a set of edges. In this case directed, annotated
+// edges from targets to dependencies.
+//
+// A LicenseGraph provides the frame of reference for all of the other types
+// defined here. It is possible to have multiple graphs, and to have targets,
+// edges, and resolutions from multiple graphs. But it is an error to try to
+// mix items from different graphs in the same operation.
+// May panic if attempted.
+//
+// The compliance package assumes specific private implementations of each of
+// these interfaces. May panic if attempts are made to combine different
+// implementations of some interfaces with expected implementations of other
+// interfaces here.
+type LicenseGraph struct {
+	// rootFiles identifies the original set of files to read. (immutable)
+	//
+	// Defines the starting "top" for top-down walks.
+	//
+	// Alternatively, an instance of licenseGraphImp conceptually defines a scope within
+	// the universe of build graphs as a sub-graph rooted at rootFiles where all edges
+	// and targets for the instance are defined relative to and within that scope. For
+	// most analyses, the correct scope is to root the graph at all of the distributed
+	// artifacts.
+	rootFiles []string
+
+	// edges lists the directed edges in the graph from target to dependency. (guarded by mu)
+	//
+	// Alternatively, the graph is the set of `edges`.
+	edges []*dependencyEdge
+
+	// targets identifies, indexes by name, and describes the entire set of target node files.
+	/// (guarded by mu)
+	targets map[string]*TargetNode
+
+	// index facilitates looking up edges from targets. (creation guarded by my)
+	//
+	// This is a forward index from target to dependencies. i.e. "top-down"
+	index map[string][]*dependencyEdge
+
+	// rsBU caches the results of a full bottom-up resolve. (creation guarded by mu)
+	//
+	// A bottom-up resolve is a prerequisite for all of the top-down resolves so caching
+	// the result is a performance win.
+	rsBU *ResolutionSet
+
+	// rsTD caches the results of a full top-down resolve. (creation guarded by mu)
+	//
+	// A top-down resolve is a prerequisite for final resolutions.
+	// e.g. a shipped node inheriting a `restricted` condition from a parent through a
+	// dynamic dependency implies a notice dependency on the parent; even though, the
+	// distribution does not happen as a result of the dynamic dependency itself.
+	rsTD *ResolutionSet
+
+	// shippedNodes caches the results of a full walk of nodes identifying targets
+	// distributed either directly or as derivative works. (creation guarded by mu)
+	shippedNodes *TargetNodeSet
+
+	// mu guards against concurrent update.
+	mu sync.Mutex
+}
+
+// TargetNode returns the target node identified by `name`.
+func (lg *LicenseGraph) TargetNode(name string) *TargetNode {
+	if _, ok := lg.targets[name]; !ok {
+		panic(fmt.Errorf("target node %q missing from graph", name))
+	}
+	return lg.targets[name]
+}
+
+// HasTargetNode returns true if a target node identified by `name` appears in
+// the graph.
+func (lg *LicenseGraph) HasTargetNode(name string) bool {
+	_, isPresent := lg.targets[name]
+	return isPresent
+}
+
+// Edges returns the list of edges in the graph. (unordered)
+func (lg *LicenseGraph) Edges() TargetEdgeList {
+	edges := make(TargetEdgeList, 0, len(lg.edges))
+	for _, e := range lg.edges {
+		edges = append(edges, TargetEdge{lg, e})
+	}
+	return edges
+}
+
+// Targets returns the list of target nodes in the graph. (unordered)
+func (lg *LicenseGraph) Targets() TargetNodeList {
+	targets := make(TargetNodeList, 0, len(lg.targets))
+	for target := range lg.targets {
+		targets = append(targets, lg.targets[target])
+	}
+	return targets
+}
+
+// compliance-only LicenseGraph methods
+
+// newLicenseGraph constructs a new, empty instance of LicenseGraph.
+func newLicenseGraph() *LicenseGraph {
+	return &LicenseGraph{
+		rootFiles: []string{},
+		edges:     make([]*dependencyEdge, 0, 1000),
+		targets:   make(map[string]*TargetNode),
+	}
+}
+
+// indexForward guarantees the `index` map is populated to look up edges by
+// `target`.
+func (lg *LicenseGraph) indexForward() {
+	lg.mu.Lock()
+	defer func() {
+		lg.mu.Unlock()
+	}()
+
+	if lg.index != nil {
+		return
+	}
+
+	lg.index = make(map[string][]*dependencyEdge)
+	for _, e := range lg.edges {
+		if _, ok := lg.index[e.target]; ok {
+			lg.index[e.target] = append(lg.index[e.target], e)
+		} else {
+			lg.index[e.target] = []*dependencyEdge{e}
+		}
+	}
+}
+
+// TargetEdge describes a directed, annotated edge from a target to a
+// dependency. (immutable)
+//
+// A LicenseGraph, above, is a set of TargetEdges.
+//
+// i.e. `Target` depends on `Dependency` in the manner described by
+// `Annotations`.
+type TargetEdge struct {
+	// lg identifies the scope, i.e. license graph, in which the edge appears.
+	lg *LicenseGraph
+
+	// e identifies describes the target, dependency, and annotations of the edge.
+	e *dependencyEdge
+}
+
+// Target identifies the target that depends on the dependency.
+//
+// Target needs Dependency to build.
+func (e TargetEdge) Target() *TargetNode {
+	return e.lg.targets[e.e.target]
+}
+
+// Dependency identifies the target depended on by the target.
+//
+// Dependency builds without Target, but Target needs Dependency to build.
+func (e TargetEdge) Dependency() *TargetNode {
+	return e.lg.targets[e.e.dependency]
+}
+
+// Annotations describes the type of edge by the set of annotations attached to
+// it.
+//
+// Only annotations prescribed by policy have any meaning for licensing, and
+// the meaning for licensing is likewise prescribed by policy. Other annotations
+// are preserved and ignored by policy.
+func (e TargetEdge) Annotations() TargetEdgeAnnotations {
+	return e.e.annotations
+}
+
+// TargetEdgeList orders lists of edges by target then dependency then annotations.
+type TargetEdgeList []TargetEdge
+
+// Len returns the count of the elmements in the list.
+func (l TargetEdgeList) Len() int      { return len(l) }
+
+// Swap rearranges 2 elements so that each occupies the other's former position.
+func (l TargetEdgeList) 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.
+func (l TargetEdgeList) Less(i, j int) bool {
+	if l[i].e.target == l[j].e.target {
+		if l[i].e.dependency == l[j].e.dependency {
+			return l[i].e.annotations.Compare(l[j].e.annotations) < 0
+		}
+		return l[i].e.dependency < l[j].e.dependency
+	}
+	return l[i].e.target < l[j].e.target
+}
+
+// TargetEdgePath describes a sequence of edges starting at a root and ending
+// at some final dependency.
+type TargetEdgePath []TargetEdge
+
+// NewTargetEdgePath creates a new, empty path with capacity `cap`.
+func NewTargetEdgePath(cap int) *TargetEdgePath {
+	p := make(TargetEdgePath, 0, cap)
+	return &p
+}
+
+// Push appends a new edge to the list verifying that the target of the new
+// edge is the dependency of the prior.
+func (p *TargetEdgePath) Push(edge TargetEdge) {
+	if len(*p) == 0 {
+		*p = append(*p, edge)
+		return
+	}
+	if (*p)[len(*p)-1].e.dependency != edge.e.target {
+		panic(fmt.Errorf("disjoint path %s does not end at %s", p.String(), edge.e.target))
+	}
+	*p = append(*p, edge)
+}
+
+// Pop shortens the path by 1 edge.
+func (p *TargetEdgePath) Pop() {
+	if len(*p) == 0 {
+		panic(fmt.Errorf("attempt to remove edge from empty path"))
+	}
+	*p = (*p)[:len(*p)-1]
+}
+
+// Clear makes the path length 0.
+func (p *TargetEdgePath) Clear() {
+	*p = (*p)[:0]
+}
+
+// String returns a string representation of the path: [n1 -> n2 -> ... -> nn].
+func (p *TargetEdgePath) String() string {
+	if p == nil {
+		return "nil"
+	}
+	if len(*p) == 0 {
+		return "[]"
+	}
+	var sb strings.Builder
+	fmt.Fprintf(&sb, "[")
+	for _, e := range *p {
+		fmt.Fprintf(&sb, "%s -> ", e.e.target)
+	}
+	fmt.Fprintf(&sb, "%s]", (*p)[len(*p)-1].e.dependency)
+	return sb.String()
+}
+
+// TargetNode describes a module or target identified by the name of a specific
+// metadata file. (immutable)
+//
+// Each metadata file corresponds to a Soong module or to a Make target.
+//
+// A target node can appear as the target or as the dependency in edges.
+// Most target nodes appear as both target in one edge and as dependency in
+// other edges.
+type TargetNode targetNode
+
+// Name returns the string that identifies the target node.
+// i.e. path to license metadata file
+func (tn *TargetNode) Name() string {
+	return tn.name
+}
+
+// PackageName returns the string that identifes the package for the target.
+func (tn *TargetNode) PackageName() string {
+	return tn.proto.GetPackageName()
+}
+
+// ModuleTypes returns the list of module types implementing the target.
+// (unordered)
+//
+// In an ideal world, only 1 module type would implement each target, but the
+// interactions between Soong and Make for host versus product and for a
+// variety of architectures sometimes causes multiple module types per target
+// (often a regular build target and a prebuilt.)
+func (tn *TargetNode) ModuleTypes() []string {
+	return append([]string{}, tn.proto.ModuleTypes...)
+}
+
+// ModuleClasses returns the list of module classes implementing the target.
+// (unordered)
+func (tn *TargetNode) ModuleClasses() []string {
+	return append([]string{}, tn.proto.ModuleClasses...)
+}
+
+// Projects returns the projects defining the target node. (unordered)
+//
+// In an ideal world, only 1 project defines a target, but the interaction
+// between Soong and Make for a variety of architectures and for host versus
+// product means a module is sometimes defined more than once.
+func (tn *TargetNode) Projects() []string {
+	return append([]string{}, tn.proto.Projects...)
+}
+
+// LicenseKinds returns the list of license kind names for the module or
+// target. (unordered)
+//
+// e.g. SPDX-license-identifier-MIT or legacy_proprietary
+func (tn *TargetNode) LicenseKinds() []string {
+	return append([]string{}, tn.proto.LicenseKinds...)
+}
+
+// LicenseConditions returns a copy of the set of license conditions
+// originating at the target. The values that appear and how each is resolved
+// is a matter of policy. (unordered)
+//
+// e.g. notice or proprietary
+func (tn *TargetNode) LicenseConditions() *LicenseConditionSet {
+	result := newLicenseConditionSet()
+	result.add(tn, tn.proto.LicenseConditions...)
+	return result
+}
+
+// LicenseTexts returns the paths to the files containing the license texts for
+// the target. (unordered)
+func (tn *TargetNode) LicenseTexts() []string {
+	return append([]string{}, tn.proto.LicenseTexts...)
+}
+
+// IsContainer returns true if the target represents a container that merely
+// aggregates other targets.
+func (tn *TargetNode) IsContainer() bool {
+	return tn.proto.GetIsContainer()
+}
+
+// Built returns the list of files built by the module or target. (unordered)
+func (tn *TargetNode) Built() []string {
+	return append([]string{}, tn.proto.Built...)
+}
+
+// Installed returns the list of files installed by the module or target.
+// (unordered)
+func (tn *TargetNode) Installed() []string {
+	return append([]string{}, tn.proto.Installed...)
+}
+
+// InstallMap returns the list of path name transformations to make to move
+// files from their original location in the file system to their destination
+// inside a container. (unordered)
+func (tn *TargetNode) InstallMap() []InstallMap {
+	result := make([]InstallMap, 0, len(tn.proto.InstallMap))
+	for _, im := range tn.proto.InstallMap {
+		result = append(result, InstallMap{im.GetFromPath(), im.GetContainerPath()})
+	}
+	return result
+}
+
+// Sources returns the list of file names depended on by the target, which may
+// be a proper subset of those made available by dependency modules.
+// (unordered)
+func (tn *TargetNode) Sources() []string {
+	return append([]string{}, tn.proto.Sources...)
+}
+
+// InstallMap describes the mapping from an input filesystem file to file in a
+// container.
+type InstallMap struct {
+	// FromPath is the input path on the filesystem.
+	FromPath string
+
+	// ContainerPath is the path to the same file inside the container or
+	// installed location.
+	ContainerPath string
+}
+
+// TargetEdgeAnnotations describes an immutable set of annotations attached to
+// an edge from a target to a dependency.
+//
+// Annotations typically distinguish between static linkage versus dynamic
+// versus tools that are used at build time but are not linked in any way.
+type TargetEdgeAnnotations struct {
+	annotations map[string]bool
+}
+
+// newEdgeAnnotations creates a new instance of TargetEdgeAnnotations.
+func newEdgeAnnotations() TargetEdgeAnnotations {
+	return TargetEdgeAnnotations{make(map[string]bool)}
+}
+
+// HasAnnotation returns true if an annotation `ann` is in the set.
+func (ea TargetEdgeAnnotations) HasAnnotation(ann string) bool {
+	_, ok := ea.annotations[ann]
+	return ok
+}
+
+// Compare orders TargetAnnotations returning:
+// -1 when ea < other,
+// +1 when ea > other, and
+// 0 when ea == other.
+func (ea TargetEdgeAnnotations) Compare(other TargetEdgeAnnotations) int {
+	a1 := ea.AsList()
+	a2 := other.AsList()
+	sort.Strings(a1)
+	sort.Strings(a2)
+	for k := 0; k < len(a1) && k < len(a2); k++ {
+		if a1[k] < a2[k] {
+			return -1
+		}
+		if a1[k] > a2[k] {
+			return 1
+		}
+	}
+	if len(a1) < len(a2) {
+		return -1
+	}
+	if len(a1) > len(a2) {
+		return 1
+	}
+	return 0
+}
+
+// AsList returns the list of annotation names attached to the edge.
+// (unordered)
+func (ea TargetEdgeAnnotations) AsList() []string {
+	l := make([]string, 0, len(ea.annotations))
+	for ann := range ea.annotations {
+		l = append(l, ann)
+	}
+	return l
+}
+
+// TargetNodeSet describes a set of distinct nodes in a license graph.
+type TargetNodeSet struct {
+	nodes map[*TargetNode]bool
+}
+
+// Contains returns true when `target` is an element of the set.
+func (ts *TargetNodeSet) Contains(target *TargetNode) bool {
+	_, isPresent := ts.nodes[target]
+	return isPresent
+}
+
+// AsList returns the list of target nodes in the set. (unordered)
+func (ts *TargetNodeSet) AsList() TargetNodeList {
+	result := make(TargetNodeList, 0, len(ts.nodes))
+	for tn := range ts.nodes {
+		result = append(result, tn)
+	}
+	return result
+}
+
+// Names returns the array of target node namess in the set. (unordered)
+func (ts *TargetNodeSet) Names() []string {
+	result := make([]string, 0, len(ts.nodes))
+	for tn := range ts.nodes {
+		result = append(result, tn.name)
+	}
+	return result
+}
+
+// TargetNodeList orders a list of targets by name.
+type TargetNodeList []*TargetNode
+
+// Len returns the count of elements in the list.
+func (l TargetNodeList) Len() int      { return len(l) }
+
+// Swap rearranges 2 elements so that each occupies the other's former position.
+func (l TargetNodeList) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
+
+// Less returns true when the `i`th element is lexicographicallt less than the `j`th.
+func (l TargetNodeList) Less(i, j int) bool {
+	return l[i].name < l[j].name
+}
+
+// String returns a string representation of the list.
+func (l TargetNodeList) String() string {
+	var sb strings.Builder
+	fmt.Fprintf(&sb, "[")
+	sep := ""
+	for _, tn := range l {
+		fmt.Fprintf(&sb, "%s%s", sep, tn.name)
+		sep = " "
+	}
+	fmt.Fprintf(&sb, "]")
+	return sb.String()
+}
+
+// Names returns an array the names of the nodes in the same order as the nodes in the list.
+func (l TargetNodeList) Names() []string {
+	result := make([]string, 0, len(l))
+	for _, tn := range l {
+		result = append(result, tn.name)
+	}
+	return result
+}
diff --git a/tools/compliance/readgraph.go b/tools/compliance/readgraph.go
new file mode 100644
index 0000000..0b5ebfe
--- /dev/null
+++ b/tools/compliance/readgraph.go
@@ -0,0 +1,259 @@
+// 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
+
+import (
+	"fmt"
+	"io"
+	"io/fs"
+	"strings"
+	"sync"
+
+	"android/soong/compliance/license_metadata_proto"
+
+	"google.golang.org/protobuf/encoding/prototext"
+)
+
+var (
+	// ConcurrentReaders is the size of the task pool for limiting resource usage e.g. open files.
+	ConcurrentReaders = 5
+)
+
+// result describes the outcome of reading and parsing a single license metadata file.
+type result struct {
+	// file identifies the path to the license metadata file
+	file string
+
+	// target contains the parsed metadata or nil if an error
+	target *TargetNode
+
+	// edges contains the parsed dependencies
+	edges []*dependencyEdge
+
+	// err is nil unless an error occurs
+	err error
+}
+
+// receiver coordinates the tasks for reading and parsing license metadata files.
+type receiver struct {
+	// lg accumulates the read metadata and becomes the final resulting LicensGraph.
+	lg *LicenseGraph
+
+	// rootFS locates the root of the file system from which to read the files.
+	rootFS fs.FS
+
+	// stderr identifies the error output writer.
+	stderr io.Writer
+
+	// task provides a fixed-size task pool to limit concurrent open files etc.
+	task chan bool
+
+	// results returns one license metadata file result at a time.
+	results chan *result
+
+	// wg detects when done
+	wg sync.WaitGroup
+}
+
+// ReadLicenseGraph reads and parses `files` and their dependencies into a LicenseGraph.
+//
+// `files` become the root files of the graph for top-down walks of the graph.
+func ReadLicenseGraph(rootFS fs.FS, stderr io.Writer, files []string) (*LicenseGraph, error) {
+	if len(files) == 0 {
+		return nil, fmt.Errorf("no license metadata to analyze")
+	}
+	if ConcurrentReaders < 1 {
+		return nil, fmt.Errorf("need at least one task in pool")
+	}
+
+	lg := newLicenseGraph()
+	for _, f := range files {
+		if strings.HasSuffix(f, ".meta_lic") {
+			lg.rootFiles = append(lg.rootFiles, f)
+		} else {
+			lg.rootFiles = append(lg.rootFiles, f+".meta_lic")
+		}
+	}
+
+	recv := &receiver{
+		lg:      lg,
+		rootFS:  rootFS,
+		stderr:  stderr,
+		task:    make(chan bool, ConcurrentReaders),
+		results: make(chan *result, ConcurrentReaders),
+		wg:      sync.WaitGroup{},
+	}
+	for i := 0; i < ConcurrentReaders; i++ {
+		recv.task <- true
+	}
+
+	readFiles := func() {
+		lg.mu.Lock()
+		// identify the metadata files to schedule reading tasks for
+		for _, f := range lg.rootFiles {
+			lg.targets[f] = nil
+		}
+		lg.mu.Unlock()
+
+		// schedule tasks to read the files
+		for _, f := range lg.rootFiles {
+			readFile(recv, f)
+		}
+
+		// schedule a task to wait until finished and close the channel.
+		go func() {
+			recv.wg.Wait()
+			close(recv.task)
+			close(recv.results)
+		}()
+	}
+	go readFiles()
+
+	// tasks to read license metadata files are scheduled; read and process results from channel
+	var err error
+	for recv.results != nil {
+		select {
+		case r, ok := <-recv.results:
+			if ok {
+				// handle errors by nil'ing ls, setting err, and clobbering results channel
+				if r.err != nil {
+					err = r.err
+					fmt.Fprintf(recv.stderr, "%s\n", err.Error())
+					lg = nil
+					recv.results = nil
+					continue
+				}
+
+				// record the parsed metadata (guarded by mutex)
+				recv.lg.mu.Lock()
+				recv.lg.targets[r.file] = r.target
+				if len(r.edges) > 0 {
+					recv.lg.edges = append(recv.lg.edges, r.edges...)
+				}
+				recv.lg.mu.Unlock()
+			} else {
+				// finished -- nil the results channel
+				recv.results = nil
+			}
+		}
+	}
+
+	return lg, err
+
+}
+
+// targetNode contains the license metadata for a node in the license graph.
+type targetNode struct {
+	proto license_metadata_proto.LicenseMetadata
+
+	// name is the path to the metadata file
+	name string
+}
+
+// dependencyEdge describes a single edge in the license graph.
+type dependencyEdge struct {
+	// target identifies the target node being built and/or installed.
+	target string
+
+	// dependency identifies the target node being depended on.
+	//
+	// i.e. `dependency` is necessary to build `target`.
+	dependency string
+
+	// annotations are a set of text attributes attached to the edge.
+	//
+	// Policy prescribes meaning to a limited set of annotations; others
+	// are preserved and ignored.
+	annotations TargetEdgeAnnotations
+}
+
+// addDependencies converts the proto AnnotatedDependencies into `edges`
+func addDependencies(edges *[]*dependencyEdge, target string, dependencies []*license_metadata_proto.AnnotatedDependency) error {
+	for _, ad := range dependencies {
+		dependency := ad.GetFile()
+		if len(dependency) == 0 {
+			return fmt.Errorf("missing dependency name")
+		}
+		annotations := newEdgeAnnotations()
+		for _, a := range ad.Annotations {
+			if len(a) == 0 {
+				continue
+			}
+			annotations.annotations[a] = true
+		}
+		*edges = append(*edges, &dependencyEdge{target, dependency, annotations})
+	}
+	return nil
+}
+
+// readFile is a task to read and parse a single license metadata file, and to schedule
+// additional tasks for reading and parsing dependencies as necessary.
+func readFile(recv *receiver, file string) {
+	recv.wg.Add(1)
+	<-recv.task
+	go func() {
+		f, err := recv.rootFS.Open(file)
+		if err != nil {
+			recv.results <- &result{file, nil, nil, fmt.Errorf("error opening license metadata %q: %w", file, err)}
+			return
+		}
+
+		// read the file
+		data, err := io.ReadAll(f)
+		if err != nil {
+			recv.results <- &result{file, nil, nil, fmt.Errorf("error reading license metadata %q: %w", file, err)}
+			return
+		}
+
+		tn := &TargetNode{name: file}
+
+		err = prototext.Unmarshal(data, &tn.proto)
+		if err != nil {
+			recv.results <- &result{file, nil, nil, fmt.Errorf("error license metadata %q: %w", file, err)}
+			return
+		}
+
+		edges := []*dependencyEdge{}
+		err = addDependencies(&edges, file, tn.proto.Deps)
+		if err != nil {
+			recv.results <- &result{file, nil, nil, fmt.Errorf("error license metadata dependency %q: %w", file, err)}
+			return
+		}
+		tn.proto.Deps = []*license_metadata_proto.AnnotatedDependency{}
+
+		// send result for this file and release task before scheduling dependencies,
+		// but do not signal done to WaitGroup until dependencies are scheduled.
+		recv.results <- &result{file, tn, edges, nil}
+		recv.task <- true
+
+		// schedule tasks as necessary to read dependencies
+		for _, e := range edges {
+			// decide, signal and record whether to schedule task in critical section
+			recv.lg.mu.Lock()
+			_, alreadyScheduled := recv.lg.targets[e.dependency]
+			if !alreadyScheduled {
+				recv.lg.targets[e.dependency] = nil
+			}
+			recv.lg.mu.Unlock()
+			// schedule task to read dependency file outside critical section
+			if !alreadyScheduled {
+				readFile(recv, e.dependency)
+			}
+		}
+
+		// signal task done after scheduling dependencies
+		recv.wg.Done()
+	}()
+}
diff --git a/tools/compliance/readgraph_test.go b/tools/compliance/readgraph_test.go
new file mode 100644
index 0000000..6248209
--- /dev/null
+++ b/tools/compliance/readgraph_test.go
@@ -0,0 +1,139 @@
+// 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
+
+import (
+	"bytes"
+	"sort"
+	"strings"
+	"testing"
+)
+
+func TestReadLicenseGraph(t *testing.T) {
+	tests := []struct {
+		name            string
+		fs              *testFS
+		roots           []string
+		expectedError   string
+		expectedEdges   []edge
+		expectedTargets []string
+	}{
+		{
+			name: "trivial",
+			fs: &testFS{
+				"app.meta_lic": []byte("package_name: \"Android\"\n"),
+			},
+			roots:           []string{"app.meta_lic"},
+			expectedEdges:   []edge{},
+			expectedTargets: []string{"app.meta_lic"},
+		},
+		{
+			name: "unterminated",
+			fs: &testFS{
+				"app.meta_lic": []byte("package_name: \"Android\n"),
+			},
+			roots:         []string{"app.meta_lic"},
+			expectedError: `invalid character '\n' in string`,
+		},
+		{
+			name: "danglingref",
+			fs: &testFS{
+				"app.meta_lic": []byte(AOSP + "deps: {\n  file: \"lib.meta_lic\"\n}\n"),
+			},
+			roots:         []string{"app.meta_lic"},
+			expectedError: `unknown file "lib.meta_lic"`,
+		},
+		{
+			name: "singleedge",
+			fs: &testFS{
+				"app.meta_lic": []byte(AOSP + "deps: {\n  file: \"lib.meta_lic\"\n}\n"),
+				"lib.meta_lic": []byte(AOSP),
+			},
+			roots:           []string{"app.meta_lic"},
+			expectedEdges:   []edge{{"app.meta_lic", "lib.meta_lic"}},
+			expectedTargets: []string{"app.meta_lic", "lib.meta_lic"},
+		},
+		{
+			name: "fullgraph",
+			fs: &testFS{
+				"apex.meta_lic": []byte(AOSP + "deps: {\n  file: \"app.meta_lic\"\n}\ndeps: {\n  file: \"bin.meta_lic\"\n}\n"),
+				"app.meta_lic":  []byte(AOSP),
+				"bin.meta_lic":  []byte(AOSP + "deps: {\n  file: \"lib.meta_lic\"\n}\n"),
+				"lib.meta_lic":  []byte(AOSP),
+			},
+			roots: []string{"apex.meta_lic"},
+			expectedEdges: []edge{
+				{"apex.meta_lic", "app.meta_lic"},
+				{"apex.meta_lic", "bin.meta_lic"},
+				{"bin.meta_lic", "lib.meta_lic"},
+			},
+			expectedTargets: []string{"apex.meta_lic", "app.meta_lic", "bin.meta_lic", "lib.meta_lic"},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			stderr := &bytes.Buffer{}
+			lg, err := ReadLicenseGraph(tt.fs, stderr, tt.roots)
+			if err != nil {
+				if len(tt.expectedError) == 0 {
+					t.Errorf("unexpected error: got %w, want no error", err)
+				} else if !strings.Contains(err.Error(), tt.expectedError) {
+					t.Errorf("unexpected error: got %w, want %q", err, tt.expectedError)
+				}
+				return
+			}
+			if 0 < len(tt.expectedError) {
+				t.Errorf("unexpected success: got no error, want %q err", tt.expectedError)
+				return
+			}
+			if lg == nil {
+				t.Errorf("missing license graph: got nil, want license graph")
+				return
+			}
+			actualEdges := make([]edge, 0)
+			for _, e := range lg.Edges() {
+				actualEdges = append(actualEdges, edge{e.Target().Name(), e.Dependency().Name()})
+			}
+			sort.Sort(byEdge(tt.expectedEdges))
+			sort.Sort(byEdge(actualEdges))
+			if len(tt.expectedEdges) != len(actualEdges) {
+				t.Errorf("unexpected number of edges: got %v with %d elements, want %v with %d elements",
+					actualEdges, len(actualEdges), tt.expectedEdges, len(tt.expectedEdges))
+			} else {
+				for i := 0; i < len(actualEdges); i++ {
+					if tt.expectedEdges[i] != actualEdges[i] {
+						t.Errorf("unexpected edge at element %d: got %s, want %s", i, actualEdges[i], tt.expectedEdges[i])
+					}
+				}
+			}
+			actualTargets := make([]string, 0)
+			for _, t := range lg.Targets() {
+				actualTargets = append(actualTargets, t.Name())
+			}
+			sort.Strings(tt.expectedTargets)
+			sort.Strings(actualTargets)
+			if len(tt.expectedTargets) != len(actualTargets) {
+				t.Errorf("unexpected number of targets: got %v with %d elements, want %v with %d elements",
+					actualTargets, len(actualTargets), tt.expectedTargets, len(tt.expectedTargets))
+			} else {
+				for i := 0; i < len(actualTargets); i++ {
+					if tt.expectedTargets[i] != actualTargets[i] {
+						t.Errorf("unexpected target at element %d: got %s, want %s", i, actualTargets[i], tt.expectedTargets[i])
+					}
+				}
+			}
+		})
+	}
+}
diff --git a/tools/compliance/resolution.go b/tools/compliance/resolution.go
new file mode 100644
index 0000000..0865ecd
--- /dev/null
+++ b/tools/compliance/resolution.go
@@ -0,0 +1,208 @@
+// 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
+
+import (
+	"fmt"
+	"sort"
+	"strings"
+)
+
+// Resolution describes an action to resolve one or more license conditions.
+//
+// `AttachesTo` identifies the target node that when distributed triggers the action.
+// `ActsOn` identifies the target node that is the object of the action.
+// `Resolves` identifies one or more license conditions that the action resolves.
+//
+// e.g. Suppose an MIT library is linked to a binary that also links to GPL code.
+//
+// A resolution would attach to the binary to share (act on) the MIT library to
+// resolve the restricted condition originating from the GPL code.
+type Resolution struct {
+	attachesTo, actsOn *TargetNode
+	cs                 *LicenseConditionSet
+}
+
+// AttachesTo returns the target node the resolution attaches to.
+func (r Resolution) AttachesTo() *TargetNode {
+	return r.attachesTo
+}
+
+// ActsOn returns the target node that must be acted on to resolve the condition.
+//
+// i.e. The node for which notice must be given or whose source must be shared etc.
+func (r Resolution) ActsOn() *TargetNode {
+	return r.actsOn
+}
+
+// Resolves returns the set of license condition the resolution satisfies.
+func (r Resolution) Resolves() *LicenseConditionSet {
+	return r.cs.Copy()
+}
+
+// asString returns a string representation of the resolution.
+func (r Resolution) asString() string {
+	var sb strings.Builder
+	cl := r.cs.AsList()
+	sort.Sort(cl)
+	fmt.Fprintf(&sb, "%s -> %s -> %s", r.attachesTo.name, r.actsOn.name, cl.String())
+	return sb.String()
+}
+
+// ResolutionList represents a partial order of Resolutions ordered by
+// AttachesTo() and ActsOn() leaving `Resolves()` unordered.
+type ResolutionList []Resolution
+
+// Len returns the count of elements in the list.
+func (l ResolutionList) Len() int      { return len(l) }
+
+// Swap rearranges 2 elements so that each occupies the other's former position.
+func (l ResolutionList) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
+
+// Less returns true when the `i`th element is lexicographically less than tht `j`th.
+func (l ResolutionList) Less(i, j int) bool {
+	if l[i].attachesTo.name == l[j].attachesTo.name {
+		return l[i].actsOn.name < l[j].actsOn.name
+	}
+	return l[i].attachesTo.name < l[j].attachesTo.name
+}
+
+// String returns a string representation of the list.
+func (rl ResolutionList) String() string {
+	var sb strings.Builder
+	fmt.Fprintf(&sb, "[")
+	sep := ""
+	for _, r := range rl {
+		fmt.Fprintf(&sb, "%s%s", sep, r.asString())
+		sep = ", "
+	}
+	fmt.Fprintf(&sb, "]")
+	return sb.String()
+}
+
+// AllConditions returns the union of all license conditions resolved by any
+// element of the list.
+func (rl ResolutionList) AllConditions() *LicenseConditionSet {
+	result := newLicenseConditionSet()
+	for _, r := range rl {
+		result.AddSet(r.cs)
+	}
+	return result
+}
+
+// ByName returns the sub-list of resolutions resolving conditions matching
+// `names`.
+func (rl ResolutionList) ByName(names ConditionNames) ResolutionList {
+	result := make(ResolutionList, 0, rl.CountByName(names))
+	for _, r := range rl {
+		if r.Resolves().HasAnyByName(names) {
+			result = append(result, Resolution{r.attachesTo, r.actsOn, r.cs.ByName(names)})
+		}
+	}
+	return result
+}
+
+// CountByName returns the number of resolutions resolving conditions matching
+// `names`.
+func (rl ResolutionList) CountByName(names ConditionNames) int {
+	c := 0
+	for _, r := range rl {
+		if r.Resolves().HasAnyByName(names) {
+			c++
+		}
+	}
+	return c
+}
+
+// CountConditionsByName returns a count of distinct resolution/conditions
+// pairs matching `names`.
+//
+// A single resolution might resolve multiple conditions matching `names`.
+func (rl ResolutionList) CountConditionsByName(names ConditionNames) int {
+	c := 0
+	for _, r := range rl {
+		c += r.Resolves().CountByName(names)
+	}
+	return c
+}
+
+// ByAttachesTo returns the sub-list of resolutions attached to `attachesTo`.
+func (rl ResolutionList) ByAttachesTo(attachesTo *TargetNode) ResolutionList {
+	result := make(ResolutionList, 0, rl.CountByActsOn(attachesTo))
+	for _, r := range rl {
+		if r.attachesTo == attachesTo {
+			result = append(result, r)
+		}
+	}
+	return result
+}
+
+// CountByAttachesTo returns the number of resolutions attached to
+// `attachesTo`.
+func (rl ResolutionList) CountByAttachesTo(attachesTo *TargetNode) int {
+	c := 0
+	for _, r := range rl {
+		if r.attachesTo == attachesTo {
+			c++
+		}
+	}
+	return c
+}
+
+// ByActsOn returns the sub-list of resolutions matching `actsOn`.
+func (rl ResolutionList) ByActsOn(actsOn *TargetNode) ResolutionList {
+	result := make(ResolutionList, 0, rl.CountByActsOn(actsOn))
+	for _, r := range rl {
+		if r.actsOn == actsOn {
+			result = append(result, r)
+		}
+	}
+	return result
+}
+
+// CountByActsOn returns the number of resolutions matching `actsOn`.
+func (rl ResolutionList) CountByActsOn(actsOn *TargetNode) int {
+	c := 0
+	for _, r := range rl {
+		if r.actsOn == actsOn {
+			c++
+		}
+	}
+	return c
+}
+
+// ByOrigin returns the sub-list of resolutions resolving license conditions
+// originating at `origin`.
+func (rl ResolutionList) ByOrigin(origin *TargetNode) ResolutionList {
+	result := make(ResolutionList, 0, rl.CountByOrigin(origin))
+	for _, r := range rl {
+		if r.Resolves().HasAnyByOrigin(origin) {
+			result = append(result, Resolution{r.attachesTo, r.actsOn, r.cs.ByOrigin(origin)})
+		}
+	}
+	return result
+}
+
+// CountByOrigin returns the number of resolutions resolving license conditions
+// originating at `origin`.
+func (rl ResolutionList) CountByOrigin(origin *TargetNode) int {
+	c := 0
+	for _, r := range rl {
+		if r.Resolves().HasAnyByOrigin(origin) {
+			c++
+		}
+	}
+	return c
+}
diff --git a/tools/compliance/resolutionset.go b/tools/compliance/resolutionset.go
new file mode 100644
index 0000000..ea49db9
--- /dev/null
+++ b/tools/compliance/resolutionset.go
@@ -0,0 +1,304 @@
+// 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
+
+import (
+	"fmt"
+	"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.
+//
+// Ultimately, the purpose of recording the license metadata and building a
+// license graph is to identify, describe, and verify the necessary actions or
+// operations for compliance policy.
+//
+// i.e. What is the source-sharing policy? Has it been met? Meet it.
+//
+// i.e. Are there incompatible policy requirements? Such as a source-sharing
+// policy applied to code that policy also says may not be shared? If so, stop
+// and remove the dependencies that create the situation.
+//
+// The ResolutionSet is the base unit for mapping license conditions to the
+// targets triggering some necessary action per policy. Different ResolutionSet
+// values may be calculated for different contexts.
+//
+// e.g. Suppose an unencumbered binary links in a notice .a library.
+//
+// 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
+// the binary, the ResolutionSet stipulates the policy that the release of the
+// unencumbered binary must provide suitable notice for the .a library.
+//
+// The resulting ResolutionSet could be used for building a notice file, for
+// 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
+}
+
+// String returns a 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())
+		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
+}
+
+// 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]bool)
+	for _, as := range rs.resolutions {
+		for actsOn := range as {
+			tset[actsOn] = true
+		}
+	}
+	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]bool)
+	for _, as := range rs.resolutions {
+		for _, cs := range as {
+			for _, origins := range cs.conditions {
+				for origin := range origins {
+					tset[origin] = true
+				}
+			}
+		}
+	}
+	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))
+	for actsOn, cs := range as {
+		result = append(result, Resolution{attachedTo, actsOn, cs.Copy()})
+	}
+	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]bool)
+	for attachesTo, as := range rs.resolutions {
+		for _, cs := range as {
+			if cs.HasAnyByOrigin(origin) {
+				tset[attachesTo] = true
+				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)
+	}
+}
diff --git a/tools/compliance/resolutionset_test.go b/tools/compliance/resolutionset_test.go
new file mode 100644
index 0000000..265357a
--- /dev/null
+++ b/tools/compliance/resolutionset_test.go
@@ -0,0 +1,201 @@
+// 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
+
+import (
+	"sort"
+	"testing"
+)
+
+var (
+	// bottomUp describes the bottom-up resolve of a hypothetical graph
+	// the graph has a container image, a couple binaries, and a couple
+	// libraries. bin1 statically links lib1 and dynamically links lib2;
+	// bin2 dynamically links lib1 and statically links lib2.
+	// binc represents a compiler or other toolchain binary used for
+	// building the other binaries.
+	bottomUp = []res{
+		{"image", "image", "image", "notice"},
+		{"image", "image", "bin2", "restricted"},
+		{"image", "bin1", "bin1", "reciprocal"},
+		{"image", "bin2", "bin2", "restricted"},
+		{"image", "lib1", "lib1", "notice"},
+		{"image", "lib2", "lib2", "notice"},
+		{"binc", "binc", "binc", "proprietary"},
+		{"bin1", "bin1", "bin1", "reciprocal"},
+		{"bin1", "lib1", "lib1", "notice"},
+		{"bin2", "bin2", "bin2", "restricted"},
+		{"bin2", "lib2", "lib2", "notice"},
+		{"lib1", "lib1", "lib1", "notice"},
+		{"lib2", "lib2", "lib2", "notice"},
+	}
+
+	// notice describes bottomUp after a top-down notice resolve.
+	notice = []res{
+		{"image", "image", "image", "notice"},
+		{"image", "image", "bin2", "restricted"},
+		{"image", "bin1", "bin1", "reciprocal"},
+		{"image", "bin2", "bin2", "restricted"},
+		{"image", "lib1", "lib1", "notice"},
+		{"image", "lib2", "bin2", "restricted"},
+		{"image", "lib2", "lib2", "notice"},
+		{"bin1", "bin1", "bin1", "reciprocal"},
+		{"bin1", "lib1", "lib1", "notice"},
+		{"bin2", "bin2", "bin2", "restricted"},
+		{"bin2", "lib2", "bin2", "restricted"},
+		{"bin2", "lib2", "lib2", "notice"},
+		{"lib1", "lib1", "lib1", "notice"},
+		{"lib2", "lib2", "lib2", "notice"},
+	}
+
+	// share describes bottomUp after a top-down share resolve.
+	share = []res{
+		{"image", "image", "bin2", "restricted"},
+		{"image", "bin1", "bin1", "reciprocal"},
+		{"image", "bin2", "bin2", "restricted"},
+		{"image", "lib2", "bin2", "restricted"},
+		{"bin1", "bin1", "bin1", "reciprocal"},
+		{"bin2", "bin2", "bin2", "restricted"},
+		{"bin2", "lib2", "bin2", "restricted"},
+	}
+
+	// proprietary describes bottomUp after a top-down proprietary resolve.
+	// Note that the proprietary binc is not reachable through the toolchain
+	// dependency.
+	proprietary = []res{}
+)
+
+func TestResolutionSet_JoinResolutionSets(t *testing.T) {
+	lg := newLicenseGraph()
+
+	rsNotice := toResolutionSet(lg, notice)
+	rsShare := toResolutionSet(lg, share)
+	rsExpected := toResolutionSet(lg, append(notice, share...))
+
+	rsActual := JoinResolutionSets(rsNotice, rsShare)
+	checkSame(rsActual, rsExpected, t)
+}
+
+func TestResolutionSet_JoinResolutionsEmpty(t *testing.T) {
+	lg := newLicenseGraph()
+
+	rsShare := toResolutionSet(lg, share)
+	rsProprietary := toResolutionSet(lg, proprietary)
+	rsExpected := toResolutionSet(lg, append(share, proprietary...))
+
+	rsActual := JoinResolutionSets(rsShare, rsProprietary)
+	checkSame(rsActual, rsExpected, t)
+}
+
+func TestResolutionSet_Origins(t *testing.T) {
+	lg := newLicenseGraph()
+
+	rsShare := toResolutionSet(lg, share)
+
+	origins := make([]string, 0)
+	for _, target := range rsShare.Origins() {
+		origins = append(origins, target.Name())
+	}
+	sort.Strings(origins)
+	if len(origins) != 2 {
+		t.Errorf("unexpected number of origins: got %v with %d elements, want [\"bin1\", \"bin2\"] with 2 elements", origins, len(origins))
+	}
+	if origins[0] != "bin1" {
+		t.Errorf("unexpected origin at element 0: got %s, want \"bin1\"", origins[0])
+	}
+	if origins[1] != "bin2" {
+		t.Errorf("unexpected origin at element 0: got %s, want \"bin2\"", origins[0])
+	}
+}
+
+func TestResolutionSet_AttachedToTarget(t *testing.T) {
+	lg := newLicenseGraph()
+
+	rsShare := toResolutionSet(lg, share)
+
+	if rsShare.AttachedToTarget(newTestNode(lg, "binc")) {
+		t.Errorf("unexpected AttachedToTarget(\"binc\"): got true, want false")
+	}
+	if !rsShare.AttachedToTarget(newTestNode(lg, "image")) {
+		t.Errorf("unexpected AttachedToTarget(\"image\"): got false want true")
+	}
+}
+
+func TestResolutionSet_AnyByNameAttachToTarget(t *testing.T) {
+	lg := newLicenseGraph()
+
+	rs := toResolutionSet(lg, bottomUp)
+
+	pandp := ConditionNames{"permissive", "proprietary"}
+	pandn := ConditionNames{"permissive", "notice"}
+	p := ConditionNames{"proprietary"}
+	r := ConditionNames{"restricted"}
+
+	if rs.AnyByNameAttachToTarget(newTestNode(lg, "image"), pandp, p) {
+		t.Errorf("unexpected AnyByNameAttachToTarget(\"image\", \"proprietary\", \"permissive\"): want false, got true")
+	}
+	if !rs.AnyByNameAttachToTarget(newTestNode(lg, "binc"), p) {
+		t.Errorf("unexpected AnyByNameAttachToTarget(\"binc\", \"proprietary\"): want true, got false")
+	}
+	if !rs.AnyByNameAttachToTarget(newTestNode(lg, "image"), pandn) {
+		t.Errorf("unexpected AnyByNameAttachToTarget(\"image\", \"permissive\", \"notice\"): want true, got false")
+	}
+	if !rs.AnyByNameAttachToTarget(newTestNode(lg, "image"), r, pandn) {
+		t.Errorf("unexpected AnyByNameAttachToTarget(\"image\", \"restricted\", \"notice\"): want true, got false")
+	}
+	if !rs.AnyByNameAttachToTarget(newTestNode(lg, "image"), r, p) {
+		t.Errorf("unexpected AnyByNameAttachToTarget(\"image\", \"restricted\", \"proprietary\"): want true, got false")
+	}
+}
+
+func TestResolutionSet_AllByNameAttachToTarget(t *testing.T) {
+	lg := newLicenseGraph()
+
+	rs := toResolutionSet(lg, bottomUp)
+
+	pandp := ConditionNames{"permissive", "proprietary"}
+	pandn := ConditionNames{"permissive", "notice"}
+	p := ConditionNames{"proprietary"}
+	r := ConditionNames{"restricted"}
+
+	if rs.AllByNameAttachToTarget(newTestNode(lg, "image"), pandp, p) {
+		t.Errorf("unexpected AllByNameAttachToTarget(\"image\", \"proprietary\", \"permissive\"): want false, got true")
+	}
+	if !rs.AllByNameAttachToTarget(newTestNode(lg, "binc"), p) {
+		t.Errorf("unexpected AllByNameAttachToTarget(\"binc\", \"proprietary\"): want true, got false")
+	}
+	if !rs.AllByNameAttachToTarget(newTestNode(lg, "image"), pandn) {
+		t.Errorf("unexpected AllByNameAttachToTarget(\"image\", \"notice\"): want true, got false")
+	}
+	if !rs.AllByNameAttachToTarget(newTestNode(lg, "image"), r, pandn) {
+		t.Errorf("unexpected AllByNameAttachToTarget(\"image\", \"restricted\", \"notice\"): want true, got false")
+	}
+	if rs.AllByNameAttachToTarget(newTestNode(lg, "image"), r, p) {
+		t.Errorf("unexpected AllByNameAttachToTarget(\"image\", \"restricted\", \"proprietary\"): want false, got true")
+	}
+}
+
+func TestResolutionSet_AttachesToTarget(t *testing.T) {
+	lg := newLicenseGraph()
+
+	rsShare := toResolutionSet(lg, share)
+
+	if rsShare.AttachesToTarget(newTestNode(lg, "binc")) {
+		t.Errorf("unexpected hasTarget(\"binc\"): got true, want false")
+	}
+	if !rsShare.AttachesToTarget(newTestNode(lg, "image")) {
+		t.Errorf("unexpected AttachesToTarget(\"image\"): got false want true")
+	}
+}
diff --git a/tools/compliance/test_util.go b/tools/compliance/test_util.go
new file mode 100644
index 0000000..46df45e
--- /dev/null
+++ b/tools/compliance/test_util.go
@@ -0,0 +1,215 @@
+// 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
+
+import (
+	"fmt"
+	"io"
+	"io/fs"
+	"sort"
+	"strings"
+	"testing"
+)
+
+const (
+	// AOSP starts a test metadata file for Android Apache-2.0 licensing.
+	AOSP = `` +
+		`package_name: "Android"
+license_kinds: "SPDX-license-identifier-Apache-2.0"
+license_conditions: "notice"
+`
+)
+
+// 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}
+	}
+	return lg.targets[targetName]
+}
+
+// testFS implements a test file system (fs.FS) simulated by a map from filename to []byte content.
+type testFS map[string][]byte
+
+// Open implements fs.FS.Open() to open a file based on the filename.
+func (fs *testFS) Open(name string) (fs.File, error) {
+	if _, ok := (*fs)[name]; !ok {
+		return nil, fmt.Errorf("unknown file %q", name)
+	}
+	return &testFile{fs, name, 0}, nil
+}
+
+// testFile implements a test file (fs.File) based on testFS above.
+type testFile struct {
+	fs   *testFS
+	name string
+	posn int
+}
+
+// Stat not implemented to obviate implementing fs.FileInfo.
+func (f *testFile) Stat() (fs.FileInfo, error) {
+	return nil, fmt.Errorf("unimplemented")
+}
+
+// Read copies bytes from the testFS map.
+func (f *testFile) Read(b []byte) (int, error) {
+	if f.posn < 0 {
+		return 0, fmt.Errorf("file not open: %q", f.name)
+	}
+	if f.posn >= len((*f.fs)[f.name]) {
+		return 0, io.EOF
+	}
+	n := copy(b, (*f.fs)[f.name][f.posn:])
+	f.posn += n
+	return n, nil
+}
+
+// Close marks the testFile as no longer in use.
+func (f *testFile) Close() error {
+	if f.posn < 0 {
+		return fmt.Errorf("file already closed: %q", f.name)
+	}
+	f.posn = -1
+	return nil
+}
+
+// edge describes test data edges to define test graphs.
+type edge struct {
+	target, dep string
+}
+
+// String returns a string representation of the edge.
+func (e edge) String() string {
+	return e.target + " -> " + e.dep
+}
+
+// byEdge orders edges by target then dep name then annotations.
+type byEdge []edge
+
+// Len returns the count of elements in the slice.
+func (l byEdge) Len() int      { return len(l) }
+
+// Swap rearranges 2 elements of the slice so that each occupies the other's
+// former position.
+func (l byEdge) 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 byEdge) Less(i, j int) bool {
+	if l[i].target == l[j].target {
+		return l[i].dep < l[j].dep
+	}
+	return l[i].target < l[j].target
+}
+
+// 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)
+	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)
+		}
+		if _, ok := rmap[attachesTo][actsOn]; !ok {
+			rmap[attachesTo][actsOn] = newLicenseConditionSet()
+		}
+		rmap[attachesTo][actsOn].add(origin, r.condition)
+	}
+	return &ResolutionSet{rmap}
+}
+
+// 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)}
+	testNode := newTestNode(lg, "test")
+	rsActual.resolutions[testNode] = asActual
+	rsExpected.resolutions[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) {
+	expectedTargets := rsExpected.AttachesTo()
+	sort.Sort(expectedTargets)
+	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)
+			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: got %s with %d elements, want %s with %d elements",
+				target.name, actualRl, len(actualRl), expectedRl, 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().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",
+					target.name, expectedRl[i].actsOn.name,
+					actualConditions, len(actualConditions),
+					expectedConditions, len(expectedConditions))
+				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)
+				}
+			}
+		}
+
+	}
+	actualTargets := rsActual.AttachesTo()
+	sort.Sort(actualTargets)
+	for i, 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)
+		}
+	}
+}