Class: RGL::ControlFlowGraph

Inherits:

Object

• Object
• RGL::ControlFlowGraph

show all

Includes:

Enumerable, MutableGraph

Defined in:

lib/laser/third_party/rgl/control_flow.rb

Overview

Constant Summary

EDGE_NORMAL =

1 << 0

EDGE_ABNORMAL =

1 << 1

EDGE_FAKE =

1 << 2

EDGE_EXECUTABLE =

1 << 3

EDGE_BLOCK_TAKEN =

1 << 4

Instance Attribute Summary (collapse)

• - (Object) enter readonly

  Returns the value of attribute enter.

• - (Object) exit readonly

  Returns the value of attribute exit.

• - (Object) vertex_lookup readonly

  Returns the value of attribute vertex_lookup.

• - (Object) vertices readonly

  Returns the value of attribute vertices.

Instance Method Summary (collapse)

• - (Object) [](key)
• - (Object) add_edge(u, v, flags = EDGE_NORMAL)

  Adds the edge to the graph.

• - (Object) add_flag(src, dest, flag)
• - (Object) add_vertex(u)

  Adds the vertex to the set of vertices.

• - (Object) degree(u)

  Computes the total degree of the vertex.

• - (Boolean) directed?

  Is the graph directed? Yes, always.

• - (Object) each_adjacent(u, &b)

  Enumerates every vertex adjacent to u.

• - (Object) each_edge

  Jacked from RGL.

• - (Object) each_vertex(&b) (also: #each)

  Enumerates the vertices.

• - (Object) edges

  Gets all the edges.

• - (Boolean) empty?

  Does the graph have no vertices? O(1).

• - (Boolean) has_edge?(u, v)
• - (Boolean) has_vertex?(u)

  Does the graph contain this vertex? O(1).

• - (Object) in_degree(u)

  What is the in-degree of the vertex u? O(1).

• - (ControlFlowGraph) initialize constructor

  A new instance of ControlFlowGraph.

• - (Boolean) is_abnormal?(src, dest)
• - (Boolean) is_block_taken?(src, dest)
• - (Boolean) is_executable?(src, dest)
• - (Boolean) is_fake?(src, dest)
• - (Object) num_edges

  How many edges are in the graph? O(V).

• - (Object) num_vertices (also: #size)

  Counts the number of vertices.

• - (Object) out_degree(u)

  What is the out-degree of the vertex u? O(1).

• - (Object) remove_edge(u, v)

  Removes the edge from the graph.

• - (Object) remove_flag(src, dest, flag)
• - (Object) remove_vertex(u)

  Removes the vertex from the graph.

• - (Object) to_a

  Returns an array of vertices in this graph.

• - (Object) vertex_with_name(key)

Methods included from MutableGraph

#add_edges, #add_graph, #add_graphs, #add_vertices, #cycles, #cycles_with_vertex, #from_graphxml, #remove_vertices

Methods included from Graph

#acyclic?, #adjacent_vertices, #bfs_iterator, #bfs_search_tree_from, #build_dfst, #condensation_graph, #depth_first_search, #depth_first_spanning_tree, #depth_first_visit, #dfs_iterator, #dominance_frontier, #dominator_tree, #dotty, #each_connected_component, #edge_class, #edges_filtered_by, #eql?, #implicit_graph, #iterated_dominance_frontier, #print_dotted_on, #reverse, #strongly_connected_components, #to_adjacency, #to_dot_graph, #to_s, #to_undirected, #topsort_iterator, #transitive_closure, #transitive_reduction, #vertices_filtered_by, #write_to_graphic_file

Methods included from Enumerable

#all?, #any?, #chunk, #collect, #collect_concat, #count, #cycle, #detect, #drop, #drop_while, #each_cons, #each_entry, #each_slice, #each_with_index, #each_with_object, #entries, #find_index, #first, #flat_map, #grep, #group_by, #include?, #inject, #map, #max, #max_by, #min, #min_by, #minmax, #minmax_by, #none?, #one?, #partition, #reject, #reverse_each, #select, #slice_before, #sort, #sort_by, #take, #take_while, #to_set, #zip

21
22
23
24
25
26

# File 'lib/laser/third_party/rgl/control_flow.rb', line 21

def initialize
  @enter = Laser::Analysis::ControlFlow::TerminalBasicBlock.new('Enter')
  @exit = Laser::Analysis::ControlFlow::TerminalBasicBlock.new('Exit')
  @vertices = Set[@enter, @exit]
  @vertex_lookup = {'Enter' => @enter, 'Exit' => @exit}
end

18
19
20

# File 'lib/laser/third_party/rgl/control_flow.rb', line 18

def enter
  @enter
end

18
19
20

# File 'lib/laser/third_party/rgl/control_flow.rb', line 18

def exit
  @exit
end

19
20
21

# File 'lib/laser/third_party/rgl/control_flow.rb', line 19

def vertex_lookup
  @vertex_lookup
end

19
20
21

# File 'lib/laser/third_party/rgl/control_flow.rb', line 19

def vertices
  @vertices
end

28
29
30

# File 'lib/laser/third_party/rgl/control_flow.rb', line 28

def [](key)
  vertex_with_name(key.name)
end

66
67
68
69

# File 'lib/laser/third_party/rgl/control_flow.rb', line 66

def add_edge(u, v, flags = EDGE_NORMAL)
  u.join(v)
  u.set_flag(v, flags)
end

87
88
89

# File 'lib/laser/third_party/rgl/control_flow.rb', line 87

def add_flag(src, dest, flag)
  src.add_flag(dest, flag)
end

60
61
62
63

# File 'lib/laser/third_party/rgl/control_flow.rb', line 60

def add_vertex(u)
  @vertex_lookup[u.name] = u
  vertices << u
end

151
152
153

# File 'lib/laser/third_party/rgl/control_flow.rb', line 151

def degree(u)
  in_degree(u) + out_degree(u)
end

146
147
148

# File 'lib/laser/third_party/rgl/control_flow.rb', line 146

def directed?
  true
end

48
49
50

# File 'lib/laser/third_party/rgl/control_flow.rb', line 48

def each_adjacent(u, &b)
  self[u].successors.each(&b)
end

53
54
55
56
57

# File 'lib/laser/third_party/rgl/control_flow.rb', line 53

def each_edge
  each_vertex { |u|
    each_adjacent(u) { |v| yield u,v }
  }
end

42
43
44

# File 'lib/laser/third_party/rgl/control_flow.rb', line 42

def each_vertex(&b)
  vertices.each(&b)
end

37
38
39

# File 'lib/laser/third_party/rgl/control_flow.rb', line 37

def edges
  vertices.map { |vert| vert.successors.map { |succ| [vert, succ] }}.flatten 1
end

127
128
129

# File 'lib/laser/third_party/rgl/control_flow.rb', line 127

def empty?
  vertices.empty?
end

136
137
138

# File 'lib/laser/third_party/rgl/control_flow.rb', line 136

def has_edge?(u, v)
  self[u].successors.include?(v)
end

132
133
134

# File 'lib/laser/third_party/rgl/control_flow.rb', line 132

def has_vertex?(u)
  vertices.include?(u)
end

156
157
158

# File 'lib/laser/third_party/rgl/control_flow.rb', line 156

def in_degree(u)
  self[u].predecessors.size
end

75
76
77

# File 'lib/laser/third_party/rgl/control_flow.rb', line 75

def is_abnormal?(src, dest)
  src.has_flag?(dest, EDGE_ABNORMAL)
end

71
72
73

# File 'lib/laser/third_party/rgl/control_flow.rb', line 71

def is_block_taken?(src, dest)
  src.has_flag?(dest, EDGE_BLOCK_TAKEN)
end

83
84
85

# File 'lib/laser/third_party/rgl/control_flow.rb', line 83

def is_executable?(src, dest)
  src.has_flag?(dest, EDGE_EXECUTABLE)
end

79
80
81

# File 'lib/laser/third_party/rgl/control_flow.rb', line 79

def is_fake?(src, dest)
  src.has_flag?(dest, EDGE_FAKE)
end

166
167
168

# File 'lib/laser/third_party/rgl/control_flow.rb', line 166

def num_edges
  vertices.map { vertices.successors.size }.inject(:+)
end

121
122
123

# File 'lib/laser/third_party/rgl/control_flow.rb', line 121

def num_vertices
  vertices.size
end

161
162
163

# File 'lib/laser/third_party/rgl/control_flow.rb', line 161

def out_degree(u)
  self[u].successors.size
end

112
113
114
115
116
117
118

# File 'lib/laser/third_party/rgl/control_flow.rb', line 112

def remove_edge(u, v)
  
  looked_up_u, looked_up_v = self[u], self[v]
  looked_up_u.disconnect(looked_up_v)
  # looked_up_u.remove_successor looked_up_v
  # looked_up_v.remove_predecessor looked_up_u
end

91
92
93

# File 'lib/laser/third_party/rgl/control_flow.rb', line 91

def remove_flag(src, dest, flag)
  src.remove_flag(dest, flag)
end

96
97
98
99
100
101
102
103
104
105
106
107
108
109

# File 'lib/laser/third_party/rgl/control_flow.rb', line 96

def remove_vertex(u)
  u.clear_edges
  looked_up = self[u]
  # looked_up.successors.each do |succ|
  #   self[succ].remove_predecessor looked_up
  #   self[looked_up].delete_all_flags succ
  # end
  # looked_up.predecessors.each do |pred|
  #   self[pred].remove_successor looked_up
  #   self[pred].delete_all_flags looked_up
  # end
  @vertex_lookup.delete looked_up.name
  vertices.delete looked_up
end

141
142
143

# File 'lib/laser/third_party/rgl/control_flow.rb', line 141

def to_a
  vertices.to_a
end

32
33
34

# File 'lib/laser/third_party/rgl/control_flow.rb', line 32

def vertex_with_name(key)
  @vertex_lookup[key]
end