class SyntaxTree::YARV::ControlFlowGraph

This class represents a control flow graph of a YARV instruction sequence. It constructs a graph of basic blocks that hold subsets of the list of instructions from the instruction sequence.

You can use this class by calling the ::compile method and passing it a YARV instruction sequence. It will return a control flow graph object.

iseq = RubyVM::InstructionSequence.compile("1 + 2")
iseq = SyntaxTree::YARV::InstructionSequence.from(iseq.to_a)
cfg = SyntaxTree::YARV::ControlFlowGraph.compile(iseq)

Attributes

blocks[R]

This is the set of basic blocks that this control-flow graph contains.

insns[R]

This is the list of instructions that this control flow graph contains. It is effectively the same as the list of instructions in the instruction sequence but with line numbers and events filtered out.

iseq[R]

This is the instruction sequence that this control flow graph corresponds to.

Public Class Methods

compile(iseq) click to toggle source

# File lib/syntax_tree/yarv/control_flow_graph.rb, line 252
def self.compile(iseq)
  Compiler.new(iseq).compile
end

new(iseq, insns, blocks) click to toggle source

# File lib/syntax_tree/yarv/control_flow_graph.rb, line 173
def initialize(iseq, insns, blocks)
  @iseq = iseq
  @insns = insns
  @blocks = blocks
end

Public Instance Methods

disasm() click to toggle source

# File lib/syntax_tree/yarv/control_flow_graph.rb, line 179
def disasm
  fmt = Disassembler.new(iseq)
  fmt.puts("== cfg: #{iseq.inspect}")

  blocks.each do |block|
    fmt.puts(block.id)
    fmt.with_prefix("    ") do |prefix|
      unless block.incoming_blocks.empty?
        from = block.incoming_blocks.map(&:id)
        fmt.puts("#{prefix}== from: #{from.join(", ")}")
      end

      fmt.format_insns!(block.insns, block.block_start)

      to = block.outgoing_blocks.map(&:id)
      to << "leaves" if block.insns.last.leaves?
      fmt.puts("#{prefix}== to: #{to.join(", ")}")
    end
  end

  fmt.string
end

to_dfg() click to toggle source

# File lib/syntax_tree/yarv/control_flow_graph.rb, line 202
def to_dfg
  DataFlowGraph.compile(self)
end

to_mermaid() click to toggle source

# File lib/syntax_tree/yarv/control_flow_graph.rb, line 210
def to_mermaid
  Mermaid.flowchart do |flowchart|
    disasm = Disassembler::Squished.new

    blocks.each do |block|
      flowchart.subgraph(block.id) do
        previous = nil

        block.each_with_length do |insn, length|
          node =
            flowchart.node(
              "node_#{length}",
              "%04d %s" % [length, insn.disasm(disasm)]
            )

          flowchart.link(previous, node) if previous
          previous = node
        end
      end
    end

    blocks.each do |block|
      block.outgoing_blocks.each do |outgoing|
        offset =
          block.block_start + block.insns.sum(&:length) -
            block.insns.last.length

        from = flowchart.fetch("node_#{offset}")
        to = flowchart.fetch("node_#{outgoing.block_start}")
        flowchart.link(from, to)
      end
    end
  end
end

to_son() click to toggle source

# File lib/syntax_tree/yarv/control_flow_graph.rb, line 206
def to_son
  to_dfg.to_son
end

verify() click to toggle source

This method is used to verify that the control flow graph is well formed. It does this by checking that each basic block is itself well formed.

# File lib/syntax_tree/yarv/control_flow_graph.rb, line 248
def verify
  blocks.each(&:verify)
end