require "../spec_helper"

include Parcom

enum BFOpType
  Add
  Shift
  ByteIn
  ByteOut
  LoopStart
  LoopEnd
end

alias BFOp = {
  type: BFOpType,
  amount: Int32,
}

def find_jumps(ops : Array(BFOp)) : Hash(Int32, Int32)
  jumps = {} of Int32 => Int32
  stack = [] of Int32

  ops.each_index do |i|
    if ops[i][:type] == BFOpType::LoopStart
      stack << i
    end

    if ops[i][:type] == BFOpType::LoopEnd
      jumps[i] = stack.pop
      jumps[jumps[i]] = i
    end
  end

  jumps
end

def interpret_bf(ops : Array(BFOp)) : Array(Char)
  jumps = find_jumps(ops)
  mem = Hash(Int32, Int32).new(0)
  i_ptr = 0
  m_ptr = 0
  output = [] of Char
  while i_ptr < ops.size
    op = ops[i_ptr]
    case op[:type]
      in BFOpType::Add
        mem[m_ptr] = (mem[m_ptr] + op[:amount]) % 256
      in BFOpType::Shift
        m_ptr += op[:amount]
      in BFOpType::ByteIn
        raise "Test suite for BF simulation does not support input instruction"
      in BFOpType::ByteOut
        c = mem[m_ptr].chr
        op[:amount].times { output << c }
      in BFOpType::LoopStart
        i_ptr = jumps[i_ptr] if mem[m_ptr] == 0
      in BFOpType::LoopEnd
        i_ptr = jumps[i_ptr] unless mem[m_ptr] == 0
    end
    i_ptr += 1
  end
  output
end

describe "brainfuck parser" do
  # From https://esolangs.org/wiki/Brainfuck#Examples
  hello_world_str = "1 +++++ +++               Set Cell #0 to 8
 2 [
 3     >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
 4     [                   as the cell will be cleared by the loop
 5         >++             Add 4*2 to Cell #2
 6         >+++            Add 4*3 to Cell #3
 7         >+++            Add 4*3 to Cell #4
 8         >+              Add 4 to Cell #5
 9         <<<<-           Decrement the loop counter in Cell #1
10     ]                   Loop till Cell #1 is zero
11     >+                  Add 1 to Cell #2
12     >+                  Add 1 to Cell #3
13     >-                  Subtract 1 from Cell #4
14     >>+                 Add 1 to Cell #6
15     [<]                 Move back to the first zero cell you find; this will
16                         be Cell #1 which was cleared by the previous loop
17     <-                  Decrement the loop Counter in Cell #0
18 ]                       Loop till Cell #0 is zero
19 
20 The result of this is:
21 Cell No :   0   1   2   3   4   5   6
22 Contents:   0   0  72 104  88  32   8
23 Pointer :   ^
24 
25 >>.                     Cell #2 has value 72 which is 'H'
26 >---.                   Subtract 3 from Cell #3 to get 101 which is 'e'
27 +++++ ++..+++.          Likewise for 'llo' from Cell #3
28 >>.                     Cell #5 is 32 for the space
29 <-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
30 <.                      Cell #3 was set to 'o' from the end of 'Hello'
31 +++.----- -.----- ---.  Cell #3 for 'rl' and 'd'
32 >>+.                    Add 1 to Cell #5 gives us an exclamation point
33 >++.                    And finally a newline from Cell #6"

  bf_chars = Set{'+', '-', '.', ',', '<', '>', '[', ']'}
  other = Parser(Char, Char).satisfy { |c| !bf_chars.includes?(c) }
  bf_char = Parser(Char, Char).satisfy { |c| bf_chars.includes?(c) }

  char_body = bf_char.some.sep_by(other.some).map(&.flatten)
  just_bf_chars = other.many >> char_body << other.many

  loop_start = Parser(Char, Char).token('[').map_const({type: BFOpType::LoopStart, amount: 0})

  loop_end = Parser(Char, Char).token(']').map_const({type: BFOpType::LoopEnd, amount: 0})

  read_block = Parser(Char, Char).token(',').some.map do |cs|
    {type: BFOpType::ByteIn, amount: cs.size}
  end

  write_block = Parser(Char, Char).token('.').some.map do |cs|
    {type: BFOpType::ByteOut, amount: cs.size}
  end

  shift_block = (Parser.token('<') | Parser.token('>')).some.map do |cs|
    left_count = cs.count(&.==('<'))
    right_count = cs.size - left_count
    {type: BFOpType::Shift, amount: right_count - left_count}
  end

  add_block = (Parser.token('+') | Parser.token('-')).some.map do |cs|
    minus_count = cs.count(&.==('-'))
    plus_count = cs.size - minus_count
    {type: BFOpType::Add, amount: plus_count - minus_count}
  end

  bf_token = Parser.first_of([
    loop_start,
    loop_end,
    read_block,
    write_block,
    shift_block,
    add_block,
  ])

  tokenizer = Parser(Char, Array(BFOp)).new("BF tokenizer") do |tokens|
    result = just_bf_chars.parse(tokens)
    chars = Tokens.new(result.value)
    bf_token.some.parse(chars)
  end

  tokens = Tokens.from_string(hello_world_str)
  result = tokenizer.parse(tokens)

  exec_result = interpret_bf(result.value)
  exec_result.should eq("Hello World!\n".chars)
end