Class: MilkTea::ControlFlow::Graph

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



9
10
11
12
13
14
15
16
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 9

def initialize
  @nodes = {}
  @next_id = 1
  @entry_id = nil
  @exit_id = nil
  @edge_labels = {}      # Hash[(from_id, to_id) → :true_branch | :false_branch]
  @edge_refinements = {} # Hash[(from_id, to_id) → Hash[binding_key → :non_null | :null]]
end

Instance Attribute Details

#entry_id ⇒ Object

Returns the value of attribute entry_id.



6
7
8
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 6

def entry_id
  @entry_id
end

#exit_id ⇒ Object

Returns the value of attribute exit_id.



6
7
8
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 6

def exit_id
  @exit_id
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



7
8
9
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 7

def nodes
  @nodes
end

Instance Method Details

#add_edge(from, to, label: nil) ⇒ Object 



36
37
38
39
40
41
42
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 36

def add_edge(from, to, label: nil)
  return unless @nodes[from] && @nodes[to]

  @nodes[from].succs << to unless @nodes[from].succs.include?(to)
  @nodes[to].preds << from unless @nodes[to].preds.include?(from)
  @edge_labels[[from, to]] = label if label
end

#add_node(kind:, statement: nil, line: nil, reads: Set.new, reads_info: [], writes: Set.new, writes_info: []) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 18

def add_node(kind:, statement: nil, line: nil, reads: Set.new, reads_info: [], writes: Set.new, writes_info: [])
  id = @next_id
  @next_id += 1
  @nodes[id] = Node.new(
    id:,
    kind:,
    statement:,
    line:,
    reads: reads.dup,
    reads_info: reads_info.map(&:dup),
    writes: writes.dup,
    writes_info: writes_info.map(&:dup),
    succs: [],
    preds: []
  )
  id
end

#each_node ⇒ Object 



56
57
58
59
60
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 56

def each_node
  return enum_for(:each_node) unless block_given?

  @nodes.each_value { |node| yield node }
end

#edge_label(from, to) ⇒ Object 



44
45
46
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 44

def edge_label(from, to)
  @edge_labels[[from, to]]
end

#edge_refinement(from, to) ⇒ Object 



48
49
50
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 48

def edge_refinement(from, to)
  @edge_refinements[[from, to]]
end

#ids ⇒ Object 



62
63
64
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 62

def ids
  @nodes.keys
end

#read_bindings ⇒ Object 



83
84
85
86
87
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 83

def read_bindings
  keys = Set.new
  each_node { |node| keys.merge(node.reads) }
  keys
end

#rpo_ids ⇒ Object 



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 66

def rpo_ids
  visited = {}
  order = []

  dfs = lambda do |id|
    return if visited[id]

    visited[id] = true
    node = @nodes[id]
    node&.succs&.each { |succ| dfs.call(succ) }
    order.unshift(id)
  end

  dfs.call(@entry_id) if @entry_id
  order
end

#set_edge_refinement(from, to, refinement) ⇒ Object 



52
53
54
 
# File 'lib/milk_tea/core/control_flow/graph.rb', line 52

def set_edge_refinement(from, to, refinement)
  @edge_refinements[[from, to]] = refinement
end