Class: Build::Graph::Walker

Inherits:
Object
  • Object
show all
Defined in:
lib/build/graph/walker.rb

Overview

A walker walks over a graph and applies a task to each node.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(&block) ⇒ Walker

Returns a new instance of Walker.



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/build/graph/walker.rb', line 32

def initialize(&block)
  # Node -> Task mapping.
  @tasks = {}
  
  @update = block
  
  @outputs = {}
  
  @parents = {}
  
  # Failed output paths:
  @failed_tasks = []
  @failed_outputs = Set.new
  
  @monitor = Files::Monitor.new
end

Instance Attribute Details

#count ⇒ Object (readonly)

Returns the value of attribute count.



56
57
58
 
# File 'lib/build/graph/walker.rb', line 56

def count
  @count
end

#dirty ⇒ Object (readonly)

Returns the value of attribute dirty.



57
58
59
 
# File 'lib/build/graph/walker.rb', line 57

def dirty
  @dirty
end

#failed_outputs ⇒ Object (readonly)

Returns the value of attribute failed_outputs.



54
55
56
 
# File 'lib/build/graph/walker.rb', line 54

def failed_outputs
  @failed_outputs
end

#failed_tasks ⇒ Object (readonly)

Returns the value of attribute failed_tasks.



53
54
55
 
# File 'lib/build/graph/walker.rb', line 53

def failed_tasks
  @failed_tasks
end

#monitor ⇒ Object (readonly)

Returns the value of attribute monitor.



61
62
63
 
# File 'lib/build/graph/walker.rb', line 61

def monitor
  @monitor
end

#outputs ⇒ Object (readonly)

Returns the value of attribute outputs.



51
52
53
 
# File 'lib/build/graph/walker.rb', line 51

def outputs
  @outputs
end

#parents ⇒ Object (readonly)

Returns the value of attribute parents.



59
60
61
 
# File 'lib/build/graph/walker.rb', line 59

def parents
  @parents
end

#tasks ⇒ Object (readonly)

=> Task



49
50
51
 
# File 'lib/build/graph/walker.rb', line 49

def tasks
  @tasks
end

Instance Method Details

#call(node) ⇒ Object 



69
70
71
72
73
74
75
76
77
 
# File 'lib/build/graph/walker.rb', line 69

def call(node)
  # We try to fetch the task if it has already been invoked, otherwise we create a new task.
  @tasks.fetch(node) do
    @update.call(self, node)
    
    # This should now be defined:
    @tasks[node]
  end
end

#clear_failed ⇒ Object 



179
180
181
182
183
184
185
186
 
# File 'lib/build/graph/walker.rb', line 179

def clear_failed
  @failed_tasks.each do |task|
    self.delete(task.node)
  end if @failed_tasks
  
  @failed_tasks = []
  @failed_outputs = Set.new
end

#delete(node) ⇒ Object 



173
174
175
176
177
 
# File 'lib/build/graph/walker.rb', line 173

def delete(node)
  if task = @tasks.delete(node)
    @monitor.delete(task)
  end
end

#enter(task) ⇒ Object 



132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/build/graph/walker.rb', line 132

def enter(task)
  # puts "--> #{task.node.process}"
  @tasks[task.node] = task
  
  # In order to wait on outputs, they must be known before entering the task. This might seem odd, but unless we know outputs are being generated, waiting for them to complete is impossible - unless this was somehow specified ahead of time. The implications of this logic is that all tasks must be sequential in terms of output -> input chaning. This is not a problem in practice.
  if outputs = task.outputs
    outputs.each do |path|
      @outputs[path.to_s] = []
    end
  end
end

#exit(task) ⇒ Object 



144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 
# File 'lib/build/graph/walker.rb', line 144

def exit(task)
  # puts "<-- #{task.node.process}"
  
  # Fail outputs if the node failed:
  if task.failed?
    @failed_tasks << task
    
    if task.outputs
      @failed_outputs += task.outputs.collect{|path| path.to_s}
    end
  end
  
  # Clean the node's outputs:
  task.outputs.each do |path|
    path = path.to_s
    
    if edges = @outputs.delete(path)
      edges.each{|edge| edge.traverse(task)}
    end
  end
  
  # Notify the parent nodes that the child is done:
  if parents = @parents.delete(task.node)
    parents.each{|edge| edge.traverse(task)}
  end
  
  @monitor.add(task)
end

#failed? ⇒ Boolean

Returns:

  • (Boolean) 


79
80
81
 
# File 'lib/build/graph/walker.rb', line 79

def failed?
  @failed_tasks.size > 0
end

#update(nodes) ⇒ Object 



63
64
65
66
67
 
# File 'lib/build/graph/walker.rb', line 63

def update(nodes)
  Array(nodes).each do |node|
    @update.call(self, node)
  end
end

#wait_for_children(parent, children) ⇒ Object

A parent task only completes once all it’s children are complete.



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/build/graph/walker.rb', line 107

def wait_for_children(parent, children)
  # Consider only incomplete/failed children:
  children = children.select{|child| !child.complete?}
  
  # If there are no children like this, then done:
  return true if children.size == 0
  
  # Otherwise, construct an edge to track state changes:
  edge = Edge.new
  
  children.each do |child|
    if child.failed?
      edge.skip!(child)
    else
      # We are waiting for this child to finish:
      edge.increment!
      
      @parents[child.node] ||= []
      @parents[child.node] << edge
    end
  end
  
  return edge.wait
end

#wait_on_paths(paths) ⇒ Object 



83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/build/graph/walker.rb', line 83

def wait_on_paths(paths)
  # If there are no paths, we are done:
  return true if paths.count == 0
  
  # We create a new directed hyper-graph edge which waits for all paths to be ready (or failed):
  edge = Edge.new
  
  paths = paths.collect(&:to_s)
  
  paths.each do |path|
    # Is there a task generating this output?
    if outputs = @outputs[path]
      # When the output is ready, trigger this edge:
      outputs << edge
      edge.increment!
    end
  end
  
  failed = paths.any?{|path| @failed_outputs.include? path}
  
  return edge.wait && !failed
end