<commit_before>require 'mfactor/image'
require 'mfactor/dot'
require 'mfactor/stack'
require 'parslet'


module MFactor

  # compilation:
  # for each definition:
  #  3. upgrade compatible types between the inferred stack effect and the user-provided one
  #  4. initialize virtual stacks (factor implementation calls them meta-d and meta-r for
  #  the data stack and the retain stack, respectiverly)
  #  for each word:
  #   1. if it is a primitive, record an operation into the stack (see below)
  #   2. if it is a shuffling word, execute it on the virtual stacks
  #   3. if it is another word, record a call operation into the stack (see below)
  #   4. if it is call, inline the quotation which MUST reside on the stack
  #  5. take the resulting operation graph, and generate a dot file
  #  6. generate a c file

  # Recording an operation involves taking the operands from the stack, and pushing one or
  # more items, which link the original input items on the stack with the corresponding
  # operation.  Also, the stack effect must be updated.  When doing so, the updated stack
  # effect must be checked against the given stack effect.  This can result in upgrading

  # Note on handling conditionals: when hitting if, both paths are virtually executed using
  # a copy of the currently active parameter and return stack.  After that, both stack
  # versions have to look the same, otherwise no compilation is possible, only execution.  A
  # phi node is inserted for every stack element that has been modified during the execution
  # of both possible paths.  To keep track of which stack elements need to be phi'd, the
  # stack is instructed to track the modifications since from the beginning of the if
  # execution part.  The stack containing the deepest modifications determines the number of
  # arguments that have to phi'd.

  class MFStaticCompiler
    attr_accessor :mf
    def initialize(mf)
      @mf=mf
      @compiled_definitions={}
    end
    def infer_word(name)
      infer mf.find_name(name).body
    end
    def compile_definition(name)
      puts "compiling definition: #{name}"
      graph=CDFG.new
      d=mf.find_name(name)      # get definition
      puts d.effect.inputs
      $stdout.flush
      inputs=d.effect.inputs.map{|i| MFInput.new(i.name,i.type)}
      saved_inputs=inputs.dup
      pstack = MFStack.new inputs
      rstack = MFStack.new
      if d.normal_word?
        compile_quotation(d.body,pstack,rstack,graph)
        outputs=pstack
        raise "#{d.err_loc}: `#{name}` leaves quotations on stack, not supported yet" if
          outputs.items.any?{|i| i.is_a? Array}
        # @compiled_definitions[name]=MFCompiledCall.new(d,inputs,outputs)
        raise "#{d.err_loc}: number of defined outputs (#{d.effect.outputs.length}) does not match with computed (#{outputs.length})" unless
          d.effect.outputs.length == outputs.length
        output_items=outputs.items.map.with_index do |x,i|
          o=Output.new(d.effect.outputs[i].name)
          graph.add_data_edge(x,o)
          o
        end
        print "final_p:"; pstack.show
        print "final_r:"; rstack.show
        input_record=MFStack.new(saved_inputs)
        graph.add_node input_record
        output_record=MFStack.new(output_items)
        graph.add_node output_record
        # dummy calls to compute ports, workaround so that ports are
        # sure to have their record fields set to avoid false duplicates when drawing
        output_record.get_port_nodes
        input_record.get_port_nodes
        d.graph = graph
        return graph
      else
        raise "word not normal: #{d.name}"
      end
    end
    def compile_quotation(q,pstack,rstack,graph,control=nil)
      print "compiling quotation: "; puts MFactor::see_word(q)
      q.each do |word|
        print "p:"; pstack.show
        print "r:"; rstack.show
        case word
        when MFWord then
          case word.name
          when "dup" then pstack._dup
          when "drop" then pstack.drop
          when "swap" then pstack.swap
          when ">r" then rstack.push pstack.pop
          when "r>" then pstack.push rstack.pop
          when "call" then
            puts "inlining literal quotation call"
            called_q=pstack.pop
            raise "#{word.err_loc}:Error: call must be compiled with literal quotation on stack" unless called_q.is_a? Array
            control=compile_quotation(called_q,pstack,rstack,graph,control)
          when "if" then
            puts "compiling `if`"
            elsecode=pstack.pop
            thencode=pstack.pop
            condition=pstack.pop
            raise "#{word.err_loc}:Error: if needs two literal quotations" unless
              (elsecode.is_a?(Array)) && (thencode.is_a?(Array))
            cnode=ChoiceNode.new("if")
            graph.add_control_edge(control,cnode)
            thenstack=pstack.dup.mark
            elsestack=pstack.mark
            res_then=compile_quotation(thencode,thenstack,rstack.dup,graph,cnode)
            res_else=compile_quotation(elsecode,elsestack,rstack,graph,cnode)
            #TODO: maybe insert crazy stack correctnes checking here
            raise "#{word.err_loc}:Error: alternatives not stack effect compatible in `if`" unless
              thenstack.length == elsestack.length
            num_phis=[thenstack.get_marked,elsestack.get_marked].max
            phi=MFPhiNode.new(condition,[thenstack.items.last(num_phis),elsestack.items.last(num_phis)])
            #graph.add_node phi
            graph.add_data_edge condition,phi
            graph.add_control_edge res_then,phi
            graph.add_control_edge res_else,phi
            control=phi
            pstack.pop_n(thenstack.length)
            pstack.push_n phi.outputs
          else
            if word.definition.inline?
              puts "inlining `#{word.definition.name}` by definition"
              control=compile_quotation(word.definition.body,pstack,rstack,graph,control)
            elsif pstack.items.last(word.definition.effect.inputs.length).any?{|i| i.is_a? Array }
              puts "auto-inlining `#{word.definition.name}` with quotation inputs"
              control=compile_quotation(word.definition.body,pstack,rstack,graph,control)
            else
              control=compile_word_call(word,pstack,graph,control)
            end
          end
        when MFIntLit then pstack.push word
        when MFByteLit then pstack.push word
        when Array then pstack.push word
        else raise "unable to compile word of type: #{word.class}"
        end
      end
      control                      # return control
    end
    def compile_word_call(word,pstack,graph,control)
      # todo: type inference here!
      puts "compiling call to #{word.definition.name}"
      d=word.definition<commit_msg>add missing data edges to phi inputs<commit_after>require 'mfactor/image'
require 'mfactor/dot'
require 'mfactor/stack'
require 'parslet'


module MFactor

  # compilation:
  # for each definition:
  #  3. upgrade compatible types between the inferred stack effect and the user-provided one
  #  4. initialize virtual stacks (factor implementation calls them meta-d and meta-r for
  #  the data stack and the retain stack, respectiverly)
  #  for each word:
  #   1. if it is a primitive, record an operation into the stack (see below)
  #   2. if it is a shuffling word, execute it on the virtual stacks
  #   3. if it is another word, record a call operation into the stack (see below)
  #   4. if it is call, inline the quotation which MUST reside on the stack
  #  5. take the resulting operation graph, and generate a dot file
  #  6. generate a c file

  # Recording an operation involves taking the operands from the stack, and pushing one or
  # more items, which link the original input items on the stack with the corresponding
  # operation.  Also, the stack effect must be updated.  When doing so, the updated stack
  # effect must be checked against the given stack effect.  This can result in upgrading

  # Note on handling conditionals: when hitting if, both paths are virtually executed using
  # a copy of the currently active parameter and return stack.  After that, both stack
  # versions have to look the same, otherwise no compilation is possible, only execution.  A
  # phi node is inserted for every stack element that has been modified during the execution
  # of both possible paths.  To keep track of which stack elements need to be phi'd, the
  # stack is instructed to track the modifications since from the beginning of the if
  # execution part.  The stack containing the deepest modifications determines the number of
  # arguments that have to phi'd.

  class MFStaticCompiler
    attr_accessor :mf
    def initialize(mf)
      @mf=mf
      @compiled_definitions={}
    end
    def infer_word(name)
      infer mf.find_name(name).body
    end
    def compile_definition(name)
      puts "compiling definition: #{name}"
      graph=CDFG.new
      d=mf.find_name(name)      # get definition
      puts d.effect.inputs
      $stdout.flush
      inputs=d.effect.inputs.map{|i| MFInput.new(i.name,i.type)}
      saved_inputs=inputs.dup
      pstack = MFStack.new inputs
      rstack = MFStack.new
      if d.normal_word?
        compile_quotation(d.body,pstack,rstack,graph)
        outputs=pstack
        raise "#{d.err_loc}: `#{name}` leaves quotations on stack, not supported yet" if
          outputs.items.any?{|i| i.is_a? Array}
        # @compiled_definitions[name]=MFCompiledCall.new(d,inputs,outputs)
        raise "#{d.err_loc}: number of defined outputs (#{d.effect.outputs.length}) does not match with computed (#{outputs.length})" unless
          d.effect.outputs.length == outputs.length
        output_items=outputs.items.map.with_index do |x,i|
          o=Output.new(d.effect.outputs[i].name)
          graph.add_data_edge(x,o)
          o
        end
        print "final_p:"; pstack.show
        print "final_r:"; rstack.show
        input_record=MFStack.new(saved_inputs)
        graph.add_node input_record
        output_record=MFStack.new(output_items)
        graph.add_node output_record
        # dummy calls to compute ports, workaround so that ports are
        # sure to have their record fields set to avoid false duplicates when drawing
        output_record.get_port_nodes
        input_record.get_port_nodes
        d.graph = graph
        return graph
      else
        raise "word not normal: #{d.name}"
      end
    end
    def compile_quotation(q,pstack,rstack,graph,control=nil)
      print "compiling quotation: "; puts MFactor::see_word(q)
      q.each do |word|
        print "p:"; pstack.show
        print "r:"; rstack.show
        case word
        when MFWord then
          case word.name
          when "dup" then pstack._dup
          when "drop" then pstack.drop
          when "swap" then pstack.swap
          when ">r" then rstack.push pstack.pop
          when "r>" then pstack.push rstack.pop
          when "call" then
            puts "inlining literal quotation call"
            called_q=pstack.pop
            raise "#{word.err_loc}:Error: call must be compiled with literal quotation on stack" unless called_q.is_a? Array
            control=compile_quotation(called_q,pstack,rstack,graph,control)
          when "if" then
            puts "compiling `if`"
            elsecode=pstack.pop
            thencode=pstack.pop
            condition=pstack.pop
            raise "#{word.err_loc}:Error: if needs two literal quotations" unless
              (elsecode.is_a?(Array)) && (thencode.is_a?(Array))
            cnode=ChoiceNode.new("if")
            graph.add_control_edge(control,cnode)
            thenstack=pstack.dup.mark
            elsestack=pstack.mark
            res_then=compile_quotation(thencode,thenstack,rstack.dup,graph,cnode)
            res_else=compile_quotation(elsecode,elsestack,rstack,graph,cnode)
            #TODO: maybe insert crazy stack correctnes checking here
            raise "#{word.err_loc}:Error: alternatives not stack effect compatible in `if`" unless
              thenstack.length == elsestack.length
            num_phis=[thenstack.get_marked,elsestack.get_marked].max
            phi=MFPhiNode.new(condition,[thenstack.items.last(num_phis),elsestack.items.last(num_phis)])
            #graph.add_node phi
            num_phis.times do |i|
              graph.add_data_edge thenstack.items[-(num_phis-i)], phi.phi_inputs[i]
              graph.add_data_edge elsestack.items[-(num_phis-i)], phi.phi_inputs[i]
            end
            graph.add_data_edge condition,phi
            graph.add_control_edge res_then,phi
            graph.add_control_edge res_else,phi
            control=phi
            pstack.pop_n(thenstack.length)
            pstack.push_n phi.outputs
          else
            if word.definition.inline?
              puts "inlining `#{word.definition.name}` by definition"
              control=compile_quotation(word.definition.body,pstack,rstack,graph,control)
            elsif pstack.items.last(word.definition.effect.inputs.length).any?{|i| i.is_a? Array }
              puts "auto-inlining `#{word.definition.name}` with quotation inputs"
              control=compile_quotation(word.definition.body,pstack,rstack,graph,control)
            else
              control=compile_word_call(word,pstack,graph,control)
            end
          end
        when MFIntLit then pstack.push word
        when MFByteLit then pstack.push word
        when Array then pstack.push word
        else raise "unable to compile word of type: #{word.class}"
        end
      end
      control                      # return control
    end
    def compile_word_call(word,pstack,graph,control)
      # todo: type inference here!
      puts "compiling call to #{word.definition.name}"
      d=word.definition
{'fraction_non_alphanumeric': 0.07974309013494985, 'fraction_numerical': 0.001154651078877102, 'mean_word_length': 2.5790289256198347, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5142396', 'n_tokens_mistral': 3996, 'n_tokens_neox': 3919, 'n_words': 1217}