#!/usr/bin/ruby -w
# Simple BF interpretor, with debug support.
#
# This works by translating input code into an intermediate representation,
# and interpret that intermediate code.  It comes with slightly better error
# messages than bf.rb, and also runs at 1/8 the speed.


# Opcode constants.
OP_IF = 0      # Conditional branch (argument = branch target).
OP_GOTO = 1    # Unconditional branch (argument = branch target).
OP_ADD = 2     # Update current value (argument = added amount).
OP_SHIFT = 3   # Update pointer address (argument = shift amount).
OP_READ = 4    # Read value (no arguments).
OP_WRITE = 5   # Write value (no arguments).

# Tuple indices.
INDEX_OFFSET = 1
INDEX_LINE = 2
INDEX_ARG = 3

# List of (opcode, source offset, line number, argument) tuples.
opcodes = []

# Currently unmatched conditional branches as a list of
# (opcode index, source offset, line number) tuples.
branch_stack = []

# Load input as opcodes.
offset = 0
line = 1
ARGF.each_char{|c|
   case c
   when "+"
      if opcodes.empty? || opcodes[-1][0] != OP_ADD
         opcodes += [[OP_ADD, offset, line, 0]]
      end
      opcodes[-1][INDEX_ARG] += 1
   when "-"
      if opcodes.empty? || opcodes[-1][0] != OP_ADD
         opcodes += [[OP_ADD, offset, line, 0]]
      end
      opcodes[-1][INDEX_ARG] -= 1
   when "<"
      if opcodes.empty? || opcodes[-1][0] != OP_SHIFT
         opcodes += [[OP_SHIFT, offset, line, 0]]
      end
      opcodes[-1][INDEX_ARG] -= 1
   when ">"
      if opcodes.empty? || opcodes[-1][0] != OP_SHIFT
         opcodes += [[OP_SHIFT, offset, line, 0]]
      end
      opcodes[-1][INDEX_ARG] += 1
   when ","
      opcodes += [[OP_READ, offset, line]]
   when "."
      opcodes += [[OP_WRITE, offset, line]]
   when "["
      branch_stack += [[opcodes.size, offset, line]]
      opcodes += [[OP_IF, offset, line]]  # Branch target is appended later.
   when "]"
      if branch_stack.empty?
         raise "Unmatched ] (line = #{line}, offset = #{offset})"
      end
      marker = branch_stack.pop
      opcodes += [[OP_GOTO, offset, line, marker[0]]]
      opcodes[marker[0]] += [opcodes.size]
   when "\n"
      line += 1
   end
   offset += 1
}

if !branch_stack.empty?
   raise "Unmatched [ " +
         "(line = #{branch_stack[-1][INDEX_LINE]}, " +
         "offset = #{branch_stack[-1][INDEX_OFFSET]})"
end

def error_location(opcode, pointer)
   return "(line = #{opcode[INDEX_LINE]}, offset = #{opcode[INDEX_OFFSET]}, " +
          "pointer = #{pointer})"
end

# Execute opcodes.
tape = []
pointer = 0
cursor = 0
while cursor < opcodes.size
   case opcodes[cursor][0]
   when OP_ADD
      if pointer < 0
         if opcodes[cursor][INDEX_ARG] > 0
            raise "Out of bounds + " + error_location(opcodes[cursor], pointer)
         else
            raise "Out of bounds - " + error_location(opcodes[cursor], pointer)
         end
      end
      tape[pointer] ||= 0
      tape[pointer] += opcodes[cursor][INDEX_ARG]
      cursor += 1
   when OP_SHIFT
      pointer += opcodes[cursor][INDEX_ARG]
      cursor += 1
   when OP_IF
      if tape[pointer] && tape[pointer] != 0
         cursor += 1
      else
         cursor = opcodes[cursor][INDEX_ARG]
      end
   when OP_GOTO
      cursor = opcodes[cursor][INDEX_ARG]
   when OP_READ
      if pointer < 0
         raise "Out of bounds write " + error_location(opcodes[cursor], pointer)
      end
      input = STDIN.getc
      if input
         tape[pointer] = input.ord
      else
         # Interpret EOF as -1.
         tape[pointer] = -1
      end
      cursor += 1
   when OP_WRITE
      if pointer < 0
         raise "Out of bounds read " + error_location(opcodes[cursor], pointer)
      elsif !tape[pointer]
         raise "Trying to output undefined value " +
               error_location(opcodes[cursor], pointer)
      elsif tape[pointer] < 0
         raise "Trying to output invalid value (#{tape[pointer]}) " +
               error_location(opcodes[cursor], pointer)
      end
      print tape[pointer].chr
      cursor += 1
   end
end