#!/bin/env python
"""Brainfuck interpreter in python, hopefully including graphical debugger soon"""

from __future__ import generators

import sys
import pprint

def validate(program):
  """validates whether the []s are balanced. raises ValueError if not."""
  depth=0;
  for char in program:
    depth += char=="["
    depth -= char=="]"
    if depth <0:
      raise ValueError
  if depth!=0: raise ValueError

def concvalidate(program):
  """validates correct balancing of []s and {|}s. raises ValueError is not."""
  validate(program)
  depth=0;
  for char in program:
    depth += char=="{"
    depth -= char=="}"
    if depth <0:
      raise ValueError
  if depth!=0: raise ValueError
  if program.find("|")>=0:
    if program.index("|")<program.index("{"): raise ValueError
    if program.rindex("|")>program.rindex("}"): raise ValueError

    
class Memory(dict):
  """Simulates the brainfuck Memory"""
  def __getitem__(self, key):
    try:
      return dict.__getitem__(self, key)
    except KeyError:
      return 0
      
class Machine:
  """A "normal" Brainfuck machine"""
  def __init__(self, program, mem=None, stdin=sys.stdin, stdout=sys.stdout, startip=0, startaddr=0):
    validate(program)
    self.program = program
    if mem != None:
      self.mem = mem
    else:
      self.mem = Memory()
    self.stdin = stdin
    self.stdout = stdout
    self.ip = startip
    self.addr = startaddr
    self.microcode = {"+": self.add,
      	       "-": self.sub,
	       "<": self.down,
	       ">": self.up,
	       ".": self.write,
	       ",": self.read,
	       "[": self.whilst,
	       "]": self.wend}
	       
  def __repr__(self):
    return pprint.pformat({"Source": self.program, 
     	      	      	   "Instruction": self.ip,
		      	   "Address": self.addr,
		      	   "Memory": self.mem})
			   
  def add(self):
    self.mem[self.addr] += 1
  
  def sub(self):
    self.mem[self.addr] -= 1
    
  def up(self):
    self.addr += 1
  
  def down(self):
    self.addr -= 1
  
  def write(self):
    self.stdout.write(chr(self.mem[self.addr]))
    
  def read(self):
    self.mem[self.addr]=ord(self.stdin.read(1))
    
  def whilst(self):
    if self.mem[self.addr] != 0:
      return

    depth=1
    while depth>0:
      self.ip += 1;
      if self.program[self.ip]=="[" :
      	depth += 1
      elif self.program[self.ip]=="]" :
        depth -= 1
	
  def wend(self): 
    if self.mem[self.addr] == 0:
      return
      
    depth=1;
    while depth>0:
      self.ip -= 1;
      if self.program[self.ip]=="[" :
      	depth -= 1
      elif self.program[self.ip]=="]" :
        depth += 1
    self.ip -= 1
  
  def step(self):
    try:
      self.microcode[self.program[self.ip]]()
    except KeyError:
      pass
    self.ip += 1
  
  def run(self):
    try:
      while 1:
      	self.step()
    except IndexError:
      pass

class ConcurrentMachine:
  """A Concurrent Brainfuck machine"""
  def __init__(self, program, mem=None, stdin=sys.stdin, stdout=sys.stdout, startip=0, startaddr=0):
    concvalidate(program)
    self.program = program
    if mem != None:
      self.mem = mem
    else:
      self.mem = Memory()
    self.stdin = stdin
    self.stdout = stdout
    self.ips = [startip]
    self.addrs = [startaddr]
    self.thread=0
    self.tcounts = Memory()

  def __repr__(self):
    return pprint.pformat({"Source": self.program, 
     	      	      	   "Instruction": self.ips,
		      	   "Address": self.addrs,
		      	   "Memory": self.mem,
			   "TCounts": self.tcounts,
			   "Thread": self.thread})
    
  def step(self):
    self.thread += 1
    self.thread *= self.thread<len(self.ips)
    opcode = self.program[self.ips[self.thread]]
    #print "executing opcode",opcode
    if opcode=="+":
      self.mem[self.addrs[self.thread]] += 1
    elif opcode=="-":
      self.mem[self.addrs[self.thread]] -= 1
    elif opcode==">":
      self.addrs[self.thread] += 1
    elif opcode=="<":
      self.addrs[self.thread] -= 1
    elif opcode==".":
      self.stdout.write(chr(self.mem[self.addrs[self.thread]]))
    elif opcode==",":
      self.mem[self.addrs[self.thread]]=ord(self.stdin.read(1))
    elif opcode=="[":
      if self.mem[self.addrs[self.thread]] == 0:
	depth=1
	while depth>0:
	  self.ips[self.thread] += 1;
	  if self.program[self.ips[self.thread]]=="[" :
      	    depth += 1
	  elif self.program[self.ips[self.thread]]=="]" :
            depth -= 1
    elif opcode=="]":
      if self.mem[self.addrs[self.thread]] != 0:
	depth=1;
	while depth>0:
	  self.ips[self.thread] -= 1;
	  if self.program[self.ips[self.thread]]=="[" :
      	    depth -= 1
	  elif self.program[self.ips[self.thread]]=="]" :
            depth += 1
    elif opcode=="{":
      depth=1
      ip = self.ips[self.thread]
      count = 0
      while depth>0:
	ip += 1;
	if self.program[ip]=="{":
      	  depth += 1
	elif self.program[ip]=="}":
          depth -= 1
      	elif (self.program[ip]=="|") and (depth==1):
	  self.addrs.append(self.addrs[self.thread])
	  self.ips.append(ip+1)
	  count += 1
      self.tcounts[ip]+=count
    elif opcode=="|":
      depth=1
      ip = self.ips[self.thread]
      count = 1
      while depth>0:
	ip += 1;
	if self.program[ip]=="{":
      	  depth += 1
	elif self.program[ip]=="}":
          depth -= 1
      self.ips[self.thread]=ip-1
    elif opcode=="}":
      if self.tcounts[self.ips[self.thread]]:
	self.tcounts[self.ips[self.thread]] -= 1
	del self.ips[self.thread]
	del self.addrs[self.thread]
	return   	
    self.ips[self.thread] += 1

  def run(self):
    try:
      while 1:
      	self.step()
    except IndexError:
      pass

def brainfuck2python(program):
  validate(program)
  result = ["import brainfulm", "import sys", "mem = brainfulm.Memory()", "MP=0"]
  depth=0;
  for char in program:
    if char=="+":
      result.append(" "*depth+"mem[MP]+=1")
    elif char=="-":
      result.append(" "*depth+"mem[MP]-=1")
    elif char=="<":
      result.append(" "*depth+"MP-=1")
    elif char==">":
      result.append(" "*depth+"MP+=1")
    elif char=="[":
      result.append(" "*depth+"while mem[MP]:")
      depth+=1
    elif char=="]":
      depth-=1
    elif char==",":
      result.append(" "*depth+"mem[MP]=ord(sys.stdin.read(1))")
    elif char==".":
      result.append(" "*depth+"sys.stdout.write(chr(mem[MP]))")
  result.append(" "*depth+"sys.exit()\n") #handles unmatched []s correctly?
  return "\n".join(result)

def brainfopt2python(program):
  validate(program)
  result = ["import brainfulm", "import sys", "m = brainfulm.Memory()", "p = 0"]
  depth=0; last=None; count=0
  for char in program:
    if (char == last) and (char in "+-<>"):
      result[-1] = result[-1][:depth+7]+str(int(result[-1][depth+7:])+1)
    else:
      if char=="+":
	result.append(" "*depth+"m[p]+= 1")
      elif char=="-":
	result.append(" "*depth+"m[p]-= 1")
      elif char=="<":
	result.append(" "*depth+"p   -= 1")
      elif char==">":
	result.append(" "*depth+"p   += 1")
      elif char=="[":
	result.append(" "*depth+"while m[p]:")
	depth+=1
      elif char=="]":
	depth-=1
      elif char==",":
	result.append(" "*depth+"m[p]=ord(sys.stdin.read(1))")
      elif char==".":
	result.append(" "*depth+"sys.stdout.write(chr(m[p]))")
    last = char
  result.append(" "*depth+"sys.exit()\n") #handles unmatched []s correctly?
  return "\n".join(result)

def Sequencer(program, mem=None, eingabe=sys.stdin, ausgabe=sys.stdout, pc=0, mp=0):
  validate(program)
  if not mem:
    mem = Memory()
  while 0<=pc<len(program):
    command = program[pc]
    if command=="+":
      mem[mp] += 1
    elif command=="-":
      mem[mp] -= 1
    elif command=="<":
      mp -= 1
    elif command==">":
      mp += 1
    elif command=="[":
      if mem[mp] == 0:
	depth=1
	while depth>0:
	  pc += 1;
	  if program[pc]=="[" :
      	    depth += 1
	  elif program[pc]=="]" :
            depth -= 1
    elif command=="]":
      if mem[mp] != 0:
    	depth=1;
	while depth>0:
	  pc -= 1;
	  if program[pc]=="[" :
      	    depth -= 1
	  elif program[pc]=="]" :
            depth += 1
	pc -= 1
    elif command==",":
      mem[mp]=ord(eingabe.read(1))
    elif command==".":
      ausgabe.write(chr(mem[mp]))
    yield(pc,mp,mem,command,mem[mp])
    pc += 1

if __name__=="__main__":
  if len(sys.argv) != 2:
    sys.stderr.write("Usage: "+sys.argv[0]+" program.bf\n")
    sys.exit(1)
  ConcurrentMachine(file(sys.argv[1],"r").read()).run()