class SyntaxTree::YARV::DataFlowGraph::Compiler

def compile
  find_internal_flow
  find_external_flow
  DataFlowGraph.new(cfg, insn_flows, block_flows).tap(&:verify)
end

def find_external_flow
  stack = [*cfg.blocks]
  until stack.empty?
    block = stack.pop
    block_flow = block_flows.fetch(block.id)
    block.incoming_blocks.each do |incoming_block|
      incoming_flow = block_flows.fetch(incoming_block.id)
      # Does a predecessor block have fewer outputs than the successor
      # has inputs?
      if incoming_flow.out.size < block_flow.in.size
        # If so then add arguments to pass data through from the
        # incoming block's incoming blocks.
        (block_flow.in.size - incoming_flow.out.size).times do |index|
          name = BlockArgument.new(:"pass_#{index}")
          incoming_flow.in.unshift(name)
          incoming_flow.out.unshift(name)
        end
        # Since we modified the incoming block, add it back to the stack
        # so it'll be considered as an outgoing block again, and
        # propogate the external data flow back up the control flow
        # graph.
        stack << incoming_block
      end
    end
  end
end

def find_internal_flow
  cfg.blocks.each do |block|
    block_flow = block_flows.fetch(block.id)
    stack = []
    # Go through each instruction in the block.
    block.each_with_length do |insn, length|
      insn_flow = insn_flows[length]
      # How many values will be missing from the local stack to run this
      # instruction? This will be used to determine if the values that
      # are being used by this instruction are coming from previous
      # instructions or from previous basic blocks.
      missing = insn.pops - stack.size
      # For every value the instruction pops off the stack.
      insn.pops.times do
        # Was the value it pops off from another basic block?
        if stack.empty?
          # If the stack is empty, then there aren't enough values being
          # pushed from previous instructions to fulfill the needs of
          # this instruction. In that case the values must be coming
          # from previous basic blocks.
          missing -= 1
          argument = BlockArgument.new(:"in_#{missing}")
          insn_flow.in.unshift(argument)
          block_flow.in.unshift(argument)
        else
          # Since there are values in the stack, we can connect this
          # consumer to the producer of the value.
          insn_flow.in.unshift(stack.pop)
        end
      end
      # Record on our abstract stack that this instruction pushed
      # this value onto the stack.
      insn.pushes.times { stack << LocalArgument.new(length) }
    end
    # Values that are left on the stack after going through all
    # instructions are arguments to the basic block that we jump to.
    stack.reverse_each.with_index do |producer, index|
      block_flow.out << producer
      argument = BlockArgument.new(:"out_#{index}")
      insn_flows[producer.length].out << argument
    end
  end
  # Go backwards and connect from producers to consumers.
  cfg.insns.each_key do |length|
    # For every instruction that produced a value used in this
    # instruction...
    insn_flows[length].in.each do |producer|
      # If it's actually another instruction and not a basic block
      # argument...
      if producer.is_a?(LocalArgument)
        # Record in the producing instruction that it produces a value
        # used by this construction.
        insn_flows[producer.length].out << LocalArgument.new(length)
      end
    end
  end
end

def initialize(cfg)
  @cfg = cfg
  @insn_flows = cfg.insns.to_h { |length, _| [length, DataFlow.new] }
  @block_flows = cfg.blocks.to_h { |block| [block.id, DataFlow.new] }
end