blob: 58547f84d5eae708c9f77d115b5e02c5ab7d305c [file] [log] [blame]
// 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
}