class SyntaxTree::YARV::DataFlowGraph

Constructs a data-flow-graph of a YARV instruction sequence, via a control-flow-graph. Data flow is discovered locally and then globally. The graph only considers data flow through the stack - local variables and objects are considered fully escaped in this analysis.

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

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

Attributes

block_flows[R]

cfg[R]

insn_flows[R]

Public Class Methods

compile(cfg) click to toggle source

# File lib/syntax_tree/yarv/data_flow_graph.rb, line 204
def self.compile(cfg)
  Compiler.new(cfg).compile
end

new(cfg, insn_flows, block_flows) click to toggle source

# File lib/syntax_tree/yarv/data_flow_graph.rb, line 68
def initialize(cfg, insn_flows, block_flows)
  @cfg = cfg
  @insn_flows = insn_flows
  @block_flows = block_flows
end

Public Instance Methods

blocks() click to toggle source

# File lib/syntax_tree/yarv/data_flow_graph.rb, line 74
def blocks
  cfg.blocks
end

disasm() click to toggle source

# File lib/syntax_tree/yarv/data_flow_graph.rb, line 78
def disasm
  fmt = Disassembler.new(cfg.iseq)
  fmt.puts("== dfg: #{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

      block_flow = block_flows.fetch(block.id)
      unless block_flow.in.empty?
        fmt.puts("#{prefix}== in: #{block_flow.in.join(", ")}")
      end

      fmt.format_insns!(block.insns, block.block_start) do |_, length|
        insn_flow = insn_flows[length]
        next if insn_flow.in.empty? && insn_flow.out.empty?

        fmt.print(" # ")
        unless insn_flow.in.empty?
          fmt.print("in: #{insn_flow.in.join(", ")}")
          fmt.print("; ") unless insn_flow.out.empty?
        end

        unless insn_flow.out.empty?
          fmt.print("out: #{insn_flow.out.join(", ")}")
        end
      end

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

      unless block_flow.out.empty?
        fmt.puts("#{prefix}== out: #{block_flow.out.join(", ")}")
      end
    end
  end

  fmt.string
end

to_mermaid() click to toggle source

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

    blocks.each do |block|
      block_flow = block_flows.fetch(block.id)
      graph_name =
        if block_flow.in.any?
          "#{block.id} #{block_flows[block.id].in.join(", ")}"
        else
          block.id
        end

      flowchart.subgraph(graph_name) do
        previous = nil

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

          flowchart.link(previous, node, color: :red) if previous
          insn_flows[length].in.each do |input|
            if input.is_a?(LocalArgument)
              from = flowchart.fetch("node_#{input.length}")
              flowchart.link(from, node, color: :green)
            end
          end

          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, color: :red)
      end
    end
  end
end

to_son() click to toggle source

# File lib/syntax_tree/yarv/data_flow_graph.rb, line 123
def to_son
  SeaOfNodes.compile(self)
end

verify() click to toggle source

Verify that we constructed the data flow graph correctly.

# File lib/syntax_tree/yarv/data_flow_graph.rb, line 179
def verify
  # Check that the first block has no arguments.
  raise unless block_flows.fetch(blocks.first.id).in.empty?

  # Check all control flow edges between blocks pass the right number of
  # arguments.
  blocks.each do |block|
    block_flow = block_flows.fetch(block.id)

    if block.outgoing_blocks.empty?
      # With no outgoing blocks, there should be no output arguments.
      raise unless block_flow.out.empty?
    else
      # Check with outgoing blocks...
      block.outgoing_blocks.each do |outgoing_block|
        outgoing_flow = block_flows.fetch(outgoing_block.id)

        # The block should have as many output arguments as the
        # outgoing block has input arguments.
        raise unless block_flow.out.size == outgoing_flow.in.size
      end
    end
  end
end