Source file src/tawesoft.co.uk/go/loader/dag.go

Documentation: src/tawesoft.co.uk/go/loader/dag.go

     1  package loader
     2  
     3  import (
     4      "fmt"
     5      "strings"
     6  )
     7  
     8  // dag is directed acyclic graph of dependencies, made up of disconnected
     9  // subgraphs.
    10  type dag struct {
    11      // nodes is an array of Tasks.
    12      // The array index is the index in the DAG.
    13      nodes      []*Task
    14  
    15      // requires means that this Task cannot complete until these Tasks complete.
    16      // The array index is the index in the DAG.
    17      requires   [][]int
    18  
    19      // requiredBy means that this Task blocks these Tasks from completing.
    20      // The array index is the index in the DAG.
    21      requiredBy [][]int
    22  
    23      // resultRequires means that this Task requires the result of these Tasks
    24      // (which may have completed). NOTE: This array is ordered!
    25      // The array index is the index in the DAG.
    26      resultRequires [][]int
    27  
    28      // resultRequiredBy means that this task still needs to provide a result
    29      // to these Tasks.
    30      // The array index is the index in the DAG.
    31      resultRequiredBy [][]int
    32  
    33      // every leaf node until it is removed from pending
    34      pending []int
    35  
    36      // every result collected, which may be set to nil when no longer needed.
    37      // The array index is the index in the DAG.
    38      results []interface{}
    39  }
    40  
    41  // scope provides scoping for task names across subsequent sibling tasks and
    42  // child subtasks, additionally scoped by a single invocation of Loader Add
    43  type scope map[string]int
    44  
    45  // dup creates a copy of scope. In this way the function callstack can
    46  // implement a stack of scope states.
    47  func (s scope) dup() scope {
    48      n := make(map[string]int)
    49      for k, v := range s {
    50          n[k] = v
    51      }
    52      return n
    53  }
    54  
    55  // scope stringer for debugging
    56  func (s scope) String() string {
    57      result := make([]string, 0)
    58      for k, v := range s {
    59          result = append(result, fmt.Sprintf("%q=>%d", k, v))
    60      }
    61      return strings.Join(result, ", ")
    62  }
    63  
    64  func (dag *dag) isLeaf(idx int) bool {
    65      return len(dag.requires[idx]) == 0
    66  }
    67  
    68  // addEdge such that "a requires b" and "a requires the result of b"
    69  func (dag *dag) addEdge(a int, b int) {
    70      dag.requires[a]         = append(dag.requires[a],         b)
    71      dag.requiredBy[b]       = append(dag.requiredBy[b],       a)
    72      dag.resultRequires[a]   = append(dag.resultRequires[a],   b)
    73      dag.resultRequiredBy[b] = append(dag.resultRequiredBy[b], a)
    74  }
    75  
    76  // add: see the loader Add method
    77  func (dag *dag) add(tasks []Task) error {
    78      return dag.addTasks(tasks, -1, make(scope))
    79  }
    80  
    81  // addTasks: see the loader Add method
    82  func (dag *dag) addTasks(tasks []Task, parent int, scope scope) error {
    83      subscope := scope.dup()
    84  
    85      dag.results = append(dag.results, make([]interface{}, len(tasks))...)
    86  
    87      for i, task := range tasks {
    88  
    89          dag.nodes            = append(dag.nodes,            &tasks[i])
    90          dag.requires         = append(dag.requires,         make([]int, 0))
    91          dag.requiredBy       = append(dag.requiredBy,       make([]int, 0))
    92          dag.resultRequires = append(dag.resultRequires,   make([]int, 0))
    93          dag.resultRequiredBy = append(dag.resultRequiredBy, make([]int, 0))
    94  
    95          idx := len(dag.nodes) - 1
    96  
    97          if parent >= 0 {
    98              // parent always < idx
    99              dag.addEdge(parent, idx)
   100          }
   101  
   102          if task.Name != "" {
   103              subscope[task.Name] = idx
   104          }
   105  
   106          for _, named := range task.RequiresNamed {
   107              namedDep, exists := subscope[named]
   108              if !exists {
   109                  return fmt.Errorf("error adding task: named requirement %q not in scope", named)
   110              }
   111              dag.addEdge(idx, namedDep)
   112          }
   113  
   114          if tasks[i].RequiresDirect != nil {
   115              err := dag.addTasks(tasks[i].RequiresDirect, idx, subscope)
   116              if err != nil { return err }
   117          }
   118  
   119          if dag.isLeaf(idx) {
   120              dag.pending = append(dag.pending, idx)
   121          }
   122      }
   123  
   124      return nil
   125  }
   126  
   127  func (dag *dag) inputs(idx int) []interface{} {
   128      var inputs []interface{}
   129      for _, requirement := range dag.resultRequires[idx] {
   130          inputs = append(inputs, dag.results[requirement])
   131      }
   132      return inputs
   133  }
   134  
   135  func (dag *dag) registerResult(idx int, result interface{}) {
   136      dag.results[idx] = result
   137  
   138      // remove the edges between the task and its parents
   139      parents := dag.requiredBy[idx]
   140      for _, parent := range parents {
   141          dag.requires[parent] = intArrayFindAndDeleteElement(dag.requires[parent], idx)
   142      }
   143      dag.requiredBy[idx] = dag.requiredBy[idx][0:0] // empty
   144  
   145      // if any parent is now a leaf, it is added to pending
   146      for _, parent := range parents {
   147          if dag.isLeaf(parent) {
   148              dag.pending = append(dag.pending, parent)
   149          }
   150      }
   151  }
   152  
   153  /*
   154  func edgesString(xs [][]int) string {
   155      result := make([]string, 0)
   156      edgesStringF(xs, func(s string) {
   157          result = append(result, s)
   158      })
   159      return strings.Join(result, "")
   160  }
   161  
   162  func edgesStringF(xs [][]int, result func(string)) {
   163      result("{\n")
   164      for i, x := range xs {
   165          result(fmt.Sprintf("    %d => {", i))
   166  
   167          for _, y := range x {
   168              result(fmt.Sprintf("%d, ", y))
   169          }
   170  
   171          result("}\n")
   172      }
   173      result("}")
   174  }
   175  */
   176  

View as plain text