tools/compliance/graph.go - SHIFTPHONES/android_build - Gitiles

 // 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 TargetEdgeList

 	// targets identifies, indexes, and describes the entire set of target node files.
 	/// (guarded by mu)
 	targets map[string]*TargetNode

 	// wgBU becomes non-nil when the bottom-up resolve begins and reaches 0
 	// (i.e. Wait() proceeds) when the bottom-up resolve completes. (guarded by mu)
 	wgBU *sync.WaitGroup

 	// wgTD becomes non-nil when the top-down resolve begins and reaches 0 (i.e. Wait()
 	// proceeds) when the top-down resolve completes. (guarded by mu)
 	wgTD *sync.WaitGroup

 	// 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
 }

 // Edges returns the list of edges in the graph. (unordered)
 func (lg *LicenseGraph) Edges() TargetEdgeList {
 	edges := make(TargetEdgeList, 0, len(lg.edges))
 	edges = append(edges, lg.edges...)
 	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, target)
 	}
 	return targets
 }

 // compliance-only LicenseGraph methods

 // newLicenseGraph constructs a new, empty instance of LicenseGraph.
 func newLicenseGraph() *LicenseGraph {
 	return &LicenseGraph{
 		rootFiles: []string{},
 		targets:   make(map[string]*TargetNode),
 	}
 }

 // 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 {
 	// target and dependency identify the nodes connected by the edge.
 	target, dependency *TargetNode

 	// annotations identifies the set of compliance-relevant annotations describing the edge.
 	annotations TargetEdgeAnnotations
 }

 // Target identifies the target that depends on the dependency.
 //
 // Target needs Dependency to build.
 func (e *TargetEdge) Target() *TargetNode {
 	return 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.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.annotations
 }

 // String returns a human-readable string representation of the edge.
 func (e *TargetEdge) String() string {
 	return fmt.Sprintf("%s -[%s]> %s", e.target.name, strings.Join(e.annotations.AsList(), ", "), e.dependency.name)
 }

 // 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 {
 	namei := l[i].target.name
 	namej := l[j].target.name
 	if namei == namej {
 		namei = l[i].dependency.name
 		namej = l[j].dependency.name
 	}
 	if namei == namej {
 		return l[i].annotations.Compare(l[j].annotations) < 0
 	}
 	return namei < namej
 }

 // TargetEdgePathSegment describes a single arc in a TargetPath associating the
 // edge with a context `ctx` defined by whatever process is creating the path.
 type TargetEdgePathSegment struct {
 	edge *TargetEdge
 	ctx  interface{}
 }

 // Target identifies the target that depends on the dependency.
 //
 // Target needs Dependency to build.
 func (s TargetEdgePathSegment) Target() *TargetNode {
 	return s.edge.target
 }

 // Dependency identifies the target depended on by the target.
 //
 // Dependency builds without Target, but Target needs Dependency to build.
 func (s TargetEdgePathSegment) Dependency() *TargetNode {
 	return s.edge.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 (s TargetEdgePathSegment) Annotations() TargetEdgeAnnotations {
 	return s.edge.annotations
 }

 // Context returns the context associated with the path segment. The type and
 // value of the context defined by the process creating the path.
 func (s TargetEdgePathSegment) Context() interface{} {
 	return s.ctx
 }

 // String returns a human-readable string representation of the edge.
 func (s TargetEdgePathSegment) String() string {
 	return fmt.Sprintf("%s -[%s]> %s", s.edge.target.name, strings.Join(s.edge.annotations.AsList(), ", "), s.edge.dependency.name)
 }

 // TargetEdgePath describes a sequence of edges starting at a root and ending
 // at some final dependency.
 type TargetEdgePath []TargetEdgePathSegment

 // 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, ctx interface{}) {
 	if len(*p) == 0 {
 		*p = append(*p, TargetEdgePathSegment{edge, ctx})
 		return
 	}
 	if (*p)[len(*p)-1].edge.dependency != edge.target {
 		panic(fmt.Errorf("disjoint path %s does not end at %s", p.String(), edge.target.name))
 	}
 	*p = append(*p, TargetEdgePathSegment{edge, ctx})
 }

 // 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]
 }

 // Copy makes a new path with the same value.
 func (p *TargetEdgePath) Copy() *TargetEdgePath {
 	result := make(TargetEdgePath, 0, len(*p))
 	for _, e := range *p {
 		result = append(result, e)
 	}
 	return &result
 }

 // 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 _, s := range *p {
 		fmt.Fprintf(&sb, "%s -> ", s.edge.target.name)
 	}
 	lastSegment := (*p)[len(*p)-1]
 	fmt.Fprintf(&sb, "%s]", lastSegment.edge.dependency.name)
 	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
 }

 // Dependencies returns the list of edges to dependencies of `tn`.
 func (tn *TargetNode) Dependencies() TargetEdgeList {
 	edges := make(TargetEdgeList, 0, len(tn.edges))
 	edges = append(edges, tn.edges...)
 	return edges
 }

 // 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 {
 	return tn.licenseConditions
 }

 // 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...)
 }

 // TargetFiles returns the list of files built or installed by the module or
 // target. (unordered)
 func (tn *TargetNode) TargetFiles() []string {
 	return append(tn.proto.Built, 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]struct{}
 }

 // newEdgeAnnotations creates a new instance of TargetEdgeAnnotations.
 func newEdgeAnnotations() TargetEdgeAnnotations {
 	return TargetEdgeAnnotations{make(map[string]struct{})}
 }

 // 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]struct{}
 }

 // 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
 }

 // String returns a human-readable string representation of the set.
 func (ts *TargetNodeSet) String() string {
 	return fmt.Sprintf("{%s}", strings.Join(ts.Names(), ", "))
 }

 // 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
 }
	// 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 TargetEdgeList

	// targets identifies, indexes, and describes the entire set of target node files.
	/// (guarded by mu)
	targets map[string]*TargetNode

	// wgBU becomes non-nil when the bottom-up resolve begins and reaches 0
	// (i.e. Wait() proceeds) when the bottom-up resolve completes. (guarded by mu)
	wgBU *sync.WaitGroup

	// wgTD becomes non-nil when the top-down resolve begins and reaches 0 (i.e. Wait()
	// proceeds) when the top-down resolve completes. (guarded by mu)
	wgTD *sync.WaitGroup

	// 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
	}

	// Edges returns the list of edges in the graph. (unordered)
	func (lg *LicenseGraph) Edges() TargetEdgeList {
	edges := make(TargetEdgeList, 0, len(lg.edges))
	edges = append(edges, lg.edges...)
	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, target)
	}
	return targets
	}

	// compliance-only LicenseGraph methods

	// newLicenseGraph constructs a new, empty instance of LicenseGraph.
	func newLicenseGraph() *LicenseGraph {
	return &LicenseGraph{
	rootFiles: []string{},
	targets: make(map[string]*TargetNode),
	}
	}

	// 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 {
	// target and dependency identify the nodes connected by the edge.
	target, dependency *TargetNode

	// annotations identifies the set of compliance-relevant annotations describing the edge.
	annotations TargetEdgeAnnotations
	}

	// Target identifies the target that depends on the dependency.
	//
	// Target needs Dependency to build.
	func (e TargetEdge) Target() TargetNode {
	return 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.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.annotations
	}

	// String returns a human-readable string representation of the edge.
	func (e *TargetEdge) String() string {
	return fmt.Sprintf("%s -[%s]> %s", e.target.name, strings.Join(e.annotations.AsList(), ", "), e.dependency.name)
	}

	// 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 {
	namei := l[i].target.name
	namej := l[j].target.name
	if namei == namej {
	namei = l[i].dependency.name
	namej = l[j].dependency.name
	}
	if namei == namej {
	return l[i].annotations.Compare(l[j].annotations) < 0
	}
	return namei < namej
	}

	// TargetEdgePathSegment describes a single arc in a TargetPath associating the
	// edge with a context `ctx` defined by whatever process is creating the path.
	type TargetEdgePathSegment struct {
	edge *TargetEdge
	ctx interface{}
	}

	// Target identifies the target that depends on the dependency.
	//
	// Target needs Dependency to build.
	func (s TargetEdgePathSegment) Target() *TargetNode {
	return s.edge.target
	}

	// Dependency identifies the target depended on by the target.
	//
	// Dependency builds without Target, but Target needs Dependency to build.
	func (s TargetEdgePathSegment) Dependency() *TargetNode {
	return s.edge.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 (s TargetEdgePathSegment) Annotations() TargetEdgeAnnotations {
	return s.edge.annotations
	}

	// Context returns the context associated with the path segment. The type and
	// value of the context defined by the process creating the path.
	func (s TargetEdgePathSegment) Context() interface{} {
	return s.ctx
	}

	// String returns a human-readable string representation of the edge.
	func (s TargetEdgePathSegment) String() string {
	return fmt.Sprintf("%s -[%s]> %s", s.edge.target.name, strings.Join(s.edge.annotations.AsList(), ", "), s.edge.dependency.name)
	}

	// TargetEdgePath describes a sequence of edges starting at a root and ending
	// at some final dependency.
	type TargetEdgePath []TargetEdgePathSegment

	// 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, ctx interface{}) {
	if len(*p) == 0 {
	p = append(p, TargetEdgePathSegment{edge, ctx})
	return
	}
	if (p)[len(p)-1].edge.dependency != edge.target {
	panic(fmt.Errorf("disjoint path %s does not end at %s", p.String(), edge.target.name))
	}
	p = append(p, TargetEdgePathSegment{edge, ctx})
	}

	// 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]
	}

	// Copy makes a new path with the same value.
	func (p TargetEdgePath) Copy() TargetEdgePath {
	result := make(TargetEdgePath, 0, len(*p))
	for _, e := range *p {
	result = append(result, e)
	}
	return &result
	}

	// 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 _, s := range *p {
	fmt.Fprintf(&sb, "%s -> ", s.edge.target.name)
	}
	lastSegment := (p)[len(p)-1]
	fmt.Fprintf(&sb, "%s]", lastSegment.edge.dependency.name)
	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
	}

	// Dependencies returns the list of edges to dependencies of `tn`.
	func (tn *TargetNode) Dependencies() TargetEdgeList {
	edges := make(TargetEdgeList, 0, len(tn.edges))
	edges = append(edges, tn.edges...)
	return edges
	}

	// 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 {
	return tn.licenseConditions
	}

	// 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...)
	}

	// TargetFiles returns the list of files built or installed by the module or
	// target. (unordered)
	func (tn *TargetNode) TargetFiles() []string {
	return append(tn.proto.Built, 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]struct{}
	}

	// newEdgeAnnotations creates a new instance of TargetEdgeAnnotations.
	func newEdgeAnnotations() TargetEdgeAnnotations {
	return TargetEdgeAnnotations{make(map[string]struct{})}
	}

	// 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]struct{}
	}

	// 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
	}

	// String returns a human-readable string representation of the set.
	func (ts *TargetNodeSet) String() string {
	return fmt.Sprintf("{%s}", strings.Join(ts.Names(), ", "))
	}

	// 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
	}