Class: MilkTea::ControlFlow::Dataflow

Inherits:
Object
  • Object
show all
Defined in:
lib/milk_tea/core/control_flow/dataflow.rb

Defined Under Namespace

Classes: Result

Class Method Summary collapse

Class Method Details

.solve(graph, direction:, initial:, join:, transfer: nil, edge_transfer: nil, boundary_in: {}, boundary_out: {}) ⇒ Object

Raises:

  • (ArgumentError) 


8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/milk_tea/core/control_flow/dataflow.rb', line 8

def self.solve(graph, direction:, initial:, join:, transfer: nil, edge_transfer: nil, boundary_in: {}, boundary_out: {})
  raise ArgumentError, "direction must be :forward or :backward" unless %i[forward backward].include?(direction)
  raise ArgumentError, "provide either transfer: or edge_transfer:" if transfer.nil? && edge_transfer.nil?

  in_states  = {}
  out_states = {}
  edge_out   = {}  # [from_id, to_id] => state  (only when edge_transfer given)
  all_ids = graph.ids
  all_ids.each do |id|
    in_states[id]  = initial.call
    out_states[id] = initial.call
  end

  changed = true
  while changed
    changed = false
    iteration_ids = direction == :forward ? graph.rpo_ids : all_ids.reverse
    iteration_ids.each do |id|
      node = graph.nodes[id]

      if direction == :forward
        incoming =
          if boundary_in.key?(id)
            boundary_in[id]
          elsif edge_transfer
            join.call(node.preds.map { |pred| edge_out[[pred, id]] || initial.call })
          else
            join.call(node.preds.map { |pred| out_states[pred] })
          end

        if edge_transfer
          node.succs.each do |succ|
            label     = graph.edge_label(id, succ)
            new_edge  = edge_transfer.call(node, incoming, succ, label)
            old_edge  = edge_out[[id, succ]]
            if old_edge != new_edge
              edge_out[[id, succ]] = new_edge
              changed = true
            end
          end
          new_out = node.succs.empty? ? initial.call : join.call(node.succs.map { |s| edge_out[[id, s]] || initial.call })
        else
          new_out = boundary_out.fetch(id) { transfer.call(node, incoming) }
        end

        if in_states[id] != incoming || out_states[id] != new_out
          in_states[id]  = incoming
          out_states[id] = new_out
          changed = true
        end
      else
        outgoing = boundary_out.fetch(id) { join.call(node.succs.map { |succ| in_states[succ] }) }
        incoming = boundary_in.fetch(id)  { transfer.call(node, outgoing) }
        if in_states[id] != incoming || out_states[id] != outgoing
          in_states[id]  = incoming
          out_states[id] = outgoing
          changed = true
        end
      end
    end
  end

  Result.new(in_states:, out_states:)
end