Quelle  policy_walk.go   Sprache: unbekannt

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

// EdgeContextProvider is an interface for injecting edge-specific context
// into walk paths.
type EdgeContextProvider interface {
 // Context returns the context for `edge` when added to `path`.
 Context(lg *LicenseGraph, path TargetEdgePath, edge *TargetEdge) interface{}
}

// NoEdgeContext implements EdgeContextProvider for walks that use no context.
type NoEdgeContext struct{}

// Context returns nil.
func (ctx NoEdgeContext) Context(lg *LicenseGraph, path TargetEdgePath, edge *TargetEdge) interface{} {
 return nil
}

// ApplicableConditionsContext provides the subset of conditions in `universe`
// that apply to each edge in a path.
type ApplicableConditionsContext struct {
 universe LicenseConditionSet
}

// Context returns the LicenseConditionSet applicable to the edge.
func (ctx ApplicableConditionsContext) Context(lg *LicenseGraph, path TargetEdgePath, edge *TargetEdge) interface{} {
 universe := ctx.universe
 if len(path) > 0 {
  universe = path[len(path)-1].ctx.(LicenseConditionSet)
 }
 return conditionsAttachingAcrossEdge(lg, edge, universe)
}

// VisitNode is called for each root and for each walked dependency node by
// WalkTopDown and WalkTopDownBreadthFirst. When VisitNode returns true, WalkTopDown will proceed to walk
// down the dependences of the node
type VisitNode func(lg *LicenseGraph, target *TargetNode, path TargetEdgePath) bool

// WalkTopDown does a top-down walk of `lg` calling `visit` and descending
// into depenencies when `visit` returns true.
func WalkTopDown(ctx EdgeContextProvider, lg *LicenseGraph, visit VisitNode) {
 path := NewTargetEdgePath(32)

 var walk func(fnode *TargetNode)
 walk = func(fnode *TargetNode) {
  visitChildren := visit(lg, fnode, *path)
  if !visitChildren {
   return
  }
  for _, edge := range fnode.edges {
   var edgeContext interface{}
   if ctx == nil {
    edgeContext = nil
   } else {
    edgeContext = ctx.Context(lg, *path, edge)
   }
   path.Push(edge, edgeContext)
   walk(edge.dependency)
   path.Pop()
  }
 }

 for _, r := range lg.rootFiles {
  path.Clear()
  walk(lg.targets[r])
 }
}

// WalkTopDownBreadthFirst performs a Breadth-first top down walk of `lg` calling `visit` and descending
// into depenencies when `visit` returns true.
func WalkTopDownBreadthFirst(ctx EdgeContextProvider, lg *LicenseGraph, visit VisitNode) {
 path := NewTargetEdgePath(32)

 var walk func(fnode *TargetNode)
 walk = func(fnode *TargetNode) {
  edgesToWalk := make(TargetEdgeList, 0, len(fnode.edges))
  for _, edge := range fnode.edges {
   var edgeContext interface{}
   if ctx == nil {
    edgeContext = nil
   } else {
    edgeContext = ctx.Context(lg, *path, edge)
   }
   path.Push(edge, edgeContext)
   if visit(lg, edge.dependency, *path) {
    edgesToWalk = append(edgesToWalk, edge)
   }
   path.Pop()
  }

  for _, edge := range edgesToWalk {
   var edgeContext interface{}
   if ctx == nil {
    edgeContext = nil
   } else {
    edgeContext = ctx.Context(lg, *path, edge)
   }
   path.Push(edge, edgeContext)
   walk(edge.dependency)
   path.Pop()
  }
 }

 path.Clear()
 rootsToWalk := make([]*TargetNode, 0, len(lg.rootFiles))
 for _, r := range lg.rootFiles {
  if visit(lg, lg.targets[r], *path) {
   rootsToWalk = append(rootsToWalk, lg.targets[r])
  }
 }

 for _, rnode := range rootsToWalk {
  walk(rnode)
 }
}

// resolutionKey identifies results from walking a specific target for a
// specific set of conditions.
type resolutionKey struct {
 target *TargetNode
 cs     LicenseConditionSet
}

// WalkResolutionsForCondition performs a top-down walk of the LicenseGraph
// resolving all distributed works for `conditions`.
func WalkResolutionsForCondition(lg *LicenseGraph, conditions LicenseConditionSet) ResolutionSet {
 shipped := ShippedNodes(lg)

 // rmap maps 'attachesTo' targets to the `actsOn` targets and applicable conditions
 rmap := make(map[resolutionKey]ActionSet)

 // cmap identifies previously walked target/condition pairs.
 cmap := make(map[resolutionKey]struct{})

 // result accumulates the resolutions to return.
 result := make(ResolutionSet)
 WalkTopDown(ApplicableConditionsContext{conditions}, lg, func(lg *LicenseGraph, tn *TargetNode, path TargetEdgePath) bool {
  universe := conditions
  if len(path) > 0 {
   universe = path[len(path)-1].ctx.(LicenseConditionSet)
  }

  if universe.IsEmpty() {
   return false
  }
  key := resolutionKey{tn, universe}

  if _, alreadyWalked := cmap[key]; alreadyWalked {
   pure := true
   for _, p := range path {
    target := p.Target()
    tkey := resolutionKey{target, universe}
    if _, ok := rmap[tkey]; !ok {
     rmap[tkey] = make(ActionSet)
    }
    // attach prior walk outcome to ancestor
    for actsOn, cs := range rmap[key] {
     rmap[tkey][actsOn] = cs
    }
    // if prior walk produced results, copy results
    // to ancestor.
    if _, ok := result[tn]; ok && pure {
     if _, ok := result[target]; !ok {
      result[target] = make(ActionSet)
     }
     for actsOn, cs := range result[tn] {
      result[target][actsOn] = cs
     }
     pure = target.IsContainer()
    }
   }
   // if all ancestors are pure aggregates, attach
   // matching prior walk conditions to self. Prior walk
   // will not have done so if any ancestor was not an
   // aggregate.
   if pure {
    match := rmap[key][tn].Intersection(universe)
    if !match.IsEmpty() {
     if _, ok := result[tn]; !ok {
      result[tn] = make(ActionSet)
     }
     result[tn][tn] = match
    }
   }
   return false
  }
  // no need to walk node or dependencies if not shipped
  if !shipped.Contains(tn) {
   return false
  }
  if _, ok := rmap[key]; !ok {
   rmap[key] = make(ActionSet)
  }
  // add self to walk outcome
  rmap[key][tn] = tn.resolution
  cmap[key] = struct{}{}
  cs := tn.resolution
  if !cs.IsEmpty() {
   cs = cs.Intersection(universe)
   pure := true
   for _, p := range path {
    target := p.Target()
    tkey := resolutionKey{target, universe}
    if _, ok := rmap[tkey]; !ok {
     rmap[tkey] = make(ActionSet)
    }
    // copy current node's action into ancestor
    rmap[tkey][tn] = tn.resolution
    // conditionally put matching conditions into
    // result
    if pure && !cs.IsEmpty() {
     if _, ok := result[target]; !ok {
      result[target] = make(ActionSet)
     }
     result[target][tn] = cs
     pure = target.IsContainer()
    }
   }
   // if all ancestors are pure aggregates, attach
   // matching conditions to self.
   if pure && !cs.IsEmpty() {
    if _, ok := result[tn]; !ok {
     result[tn] = make(ActionSet)
    }
    result[tn][tn] = cs
   }
  }
  return true
 })

 return result
}

// WalkActionsForCondition performs a top-down walk of the LicenseGraph
// resolving all distributed works for `conditions`.
func WalkActionsForCondition(lg *LicenseGraph, conditions LicenseConditionSet) ActionSet {
 // amap maps 'actsOn' targets to the applicable conditions
 //
 // amap is the resulting ActionSet
 amap := make(ActionSet)

 for tn := range ShippedNodes(lg) {
  if cs := conditions.Intersection(tn.resolution); !cs.IsEmpty() {
   amap[tn] = cs
  }
 }

 return amap
}