compliance package structures for license metadata
package to read, consume, and analyze license metadata and dependency
graph.
Bug: 68860345
Bug: 151177513
Bug: 151953481
Change-Id: I3ebf44e4d5195b9851fd076161049bf82ed76dd2
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)
+ }
+ }
+}