tools/compliance/policy/resolve.go

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

// ResolveBottomUpConditions performs a bottom-up walk of the LicenseGraph
// propagating conditions up the graph as necessary according to the properties
// of each edge and according to each license condition in question.
//
// Subsequent top-down walks of the graph will filter some resolutions and may
// introduce new resolutions.
//
// e.g. if a "restricted" condition applies to a binary, it also applies to all
// of the statically-linked libraries and the transitive closure of their static
// dependencies; even if neither they nor the transitive closure of their
// dependencies originate any "restricted" conditions. The bottom-up walk will
// not resolve the library and its transitive closure, but the later top-down
// walk will.
func ResolveBottomUpConditions(lg *LicenseGraph) *ResolutionSet {

	// short-cut if already walked and cached
	lg.mu.Lock()
	rs := lg.rsBU
	lg.mu.Unlock()

	if rs != nil {
		return rs
	}

	// must be indexed for fast lookup
	lg.indexForward()

	rs = resolveBottomUp(lg, make(map[*TargetNode]actionSet) /* empty map; no prior resolves */)

	// if not yet cached, save the result
	lg.mu.Lock()
	if lg.rsBU == nil {
		lg.rsBU = rs
	} else {
		// if we end up with 2, release the later for garbage collection
		rs = lg.rsBU
	}
	lg.mu.Unlock()

	return rs
}

// ResolveTopDownCondtions performs a top-down walk of the LicenseGraph
// resolving all reachable nodes for `condition`. Policy establishes the rules
// for transforming and propagating resolutions down the graph.
//
// e.g. For current policy, none of the conditions propagate from target to
// dependency except restricted. For restricted, the policy is to share the
// source of any libraries linked to restricted code and to provide notice.
func ResolveTopDownConditions(lg *LicenseGraph) *ResolutionSet {

	// short-cut if already walked and cached
	lg.mu.Lock()
	rs := lg.rsTD
	lg.mu.Unlock()

	if rs != nil {
		return rs
	}

	// start with the conditions propagated up the graph
	rs = ResolveBottomUpConditions(lg)

	// rmap maps 'appliesTo' targets to their applicable conditions
	//
	// rmap is the resulting ResolutionSet
	rmap := make(map[*TargetNode]actionSet)

	// cmap contains the set of targets walked as pure aggregates. i.e. containers
	cmap := make(map[*TargetNode]bool)

	var walk func(fnode *TargetNode, cs *LicenseConditionSet, treatAsAggregate bool)

	walk = func(fnode *TargetNode, cs *LicenseConditionSet, treatAsAggregate bool) {
		if _, ok := rmap[fnode]; !ok {
			rmap[fnode] = make(actionSet)
		}
		rmap[fnode].add(fnode, cs)
		if treatAsAggregate {
			cmap[fnode] = true
		}
		// add conditions attached to `fnode`
		cs = cs.Copy()
		for _, fcs := range rs.resolutions[fnode] {
			cs.AddSet(fcs)
		}
		// for each dependency
		for _, edge := range lg.index[fnode.name] {
			e := TargetEdge{lg, edge}
			// dcs holds the dpendency conditions inherited from the target
			dcs := targetConditionsApplicableToDep(e, cs, treatAsAggregate)
			if dcs.IsEmpty() && !treatAsAggregate {
				continue
			}
			dnode := lg.targets[edge.dependency]
			if as, alreadyWalked := rmap[dnode]; alreadyWalked {
				diff := dcs.Copy()
				diff.RemoveSet(as.conditions())
				if diff.IsEmpty() {
					// no new conditions

					// pure aggregates never need walking a 2nd time with same conditions
					if treatAsAggregate {
						continue
					}
					// non-aggregates don't need walking as non-aggregate a 2nd time
					if _, asAggregate := cmap[dnode]; !asAggregate {
						continue
					}
					// previously walked as pure aggregate; need to re-walk as non-aggregate
					delete(cmap, dnode)
				}
			}
			// add the conditions to the dependency
			walk(dnode, dcs, treatAsAggregate && lg.targets[edge.dependency].IsContainer())
		}
	}

	// walk each of the roots
	for _, r := range lg.rootFiles {
		rnode := lg.targets[r]
		as, ok := rs.resolutions[rnode]
		if !ok {
			// no conditions in root or transitive closure of dependencies
			continue
		}
		if as.isEmpty() {
			continue
		}

		// add the conditions to the root and its transitive closure
		walk(rnode, newLicenseConditionSet(), lg.targets[r].IsContainer())
	}

	// back-fill any bottom-up conditions on targets missed by top-down walk
	for attachesTo, as := range rs.resolutions {
		if _, ok := rmap[attachesTo]; !ok {
			rmap[attachesTo] = as.copy()
		} else {
			rmap[attachesTo].addSet(as)
		}
	}

	// propagate any new conditions back up the graph
	rs = resolveBottomUp(lg, rmap)

	// if not yet cached, save the result
	lg.mu.Lock()
	if lg.rsTD == nil {
		lg.rsTD = rs
	} else {
		// if we end up with 2, release the later for garbage collection
		rs = lg.rsTD
	}
	lg.mu.Unlock()

	return rs
}

// resolveBottomUp implements a bottom-up resolve propagating conditions both
// from the graph, and from a `priors` map of resolutions.
func resolveBottomUp(lg *LicenseGraph, priors map[*TargetNode]actionSet) *ResolutionSet {
	rs := newResolutionSet()

	// cmap contains an entry for every target that was previously walked as a pure aggregate only.
	cmap := make(map[string]bool)

	var walk func(f string, treatAsAggregate bool) actionSet

	walk = func(f string, treatAsAggregate bool) actionSet {
		target := lg.targets[f]
		result := make(actionSet)
		result[target] = newLicenseConditionSet()
		result[target].add(target, target.proto.LicenseConditions...)
		if pas, ok := priors[target]; ok {
			result.addSet(pas)
		}
		if preresolved, ok := rs.resolutions[target]; ok {
			if treatAsAggregate {
				result.addSet(preresolved)
				return result
			}
			if _, asAggregate := cmap[f]; !asAggregate {
				result.addSet(preresolved)
				return result
			}
			// previously walked in a pure aggregate context,
			// needs to walk again in non-aggregate context
			delete(cmap, f)
		}
		if treatAsAggregate {
			cmap[f] = true
		}

		// add all the conditions from all the dependencies
		for _, edge := range lg.index[f] {
			// walk dependency to get its conditions
			as := walk(edge.dependency, treatAsAggregate && lg.targets[edge.dependency].IsContainer())

			// turn those into the conditions that apply to the target
			as = depActionsApplicableToTarget(TargetEdge{lg, edge}, as, treatAsAggregate)

			// add them to the result
			result.addSet(as)
		}

		// record these conditions as applicable to the target
		rs.addConditions(target, result)
		if len(priors) == 0 {
			// on the first bottom-up resolve, parents have their own sharing and notice needs
			// on the later resolve, if priors is empty, there will be nothing new to add
			rs.addSelf(target, result.byName(ImpliesRestricted))
		}

		// return this up the tree
		return result
	}

	// walk each of the roots
	for _, r := range lg.rootFiles {
		_ = walk(r, lg.targets[r].IsContainer())
	}

	return rs
}