# Copyright (c) 2009 Tim Freeman
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.
#
# (This is the standard MIT License, copied from
# http://www.opensource.org/licenses/mit-license.php on 24 Apr 2007.)
#desc Turing machine interpreter.
import bits
from turing_tape import turing_tape

# A Turing machine tape is a tuple (length, tapebits), where length is
# the number of bits on the tape and tapebits is a (probably long)
# nonnegative integer that encodes the bits on the tape.  The least
# significant bit of tapebits is the rightmost cell on the tape.  The
# machine can't access to the right of the right cell, but it can extend
# to the left of the leftmost cell.

# The machine has these bits, from right to left:

# An encoding of the number of bits needed to identify a state.  The
# leading bit of the encoding is 0 and the rest are 1.  The length of
# the encoding is the number of bits.  So if the machine ends in
# ...011 we have 3 bits per state and therefore have 8 states.

# The machine starts in state 0.

# Then we have encodings of each state, starting with state 0.

# Each state has three actions.  We do the rightmost action if the bit
# under the head is 0, the middle one if the bit is 1, and the left
# one if the head is off the end of the tape.

# An action has three things:
# The rightmost 2 bits say what to do next:
#    00 - Write a 0 to the output tape.
#    01 - Write a 1 to the output tape.
#    10 - Truncate the output tape.  After this operation the head is
#         just past the end of the tape.
#    11 - The machine has finished its computation.
# Then we have one bit that says how to move:
#    0 - Move left
#    1 - Move right
# Then we have a next state.

# (The total number of bits describing what to do and how to move is 3,
# so if the number of bits per state is a multiple of 3 we can eyeball
# these machines somewhat by printing them in octal.)

# If we try to write past the right end of the tape, there is no
# effect.  We used to exit and return None in that case, but with that
# policy there's no good next move after you have scanned to the right
# end of the tape.  If we try to write past the left end of the tape,
# it makes the tape longer. 

# A function to print steps of the Turing machine simulation.  By
# default, we print nothing.
def silent_do_animation(tape_length, tape_bits, headpos, sn, state,
                        bpsn, short):
    pass

empty_tape = turing_tape(length=0,bits=0)

class Machine_failure(bits.Doesnt_match):
    pass

# This return the output tape, which is a pair (outputlength,
# outputbits).  If we run out of time or truncate when it doesn't make
# sense, throw Machine_failure.
def turing(machine, tape, time, animate = silent_do_animation):
    try:
        (tape_length, tape_bits) = (tape.length, tape.bits)
    except:
        raise Exception("Wrong type for tape argument to turing: %r" % (tape,))
    bpsn = 0 
    while machine & 1:
        bpsn += 1
        machine >>= 1
    bpsn += 1 # Discard the zero. Now bpsn = bits per state number
    machine >>= 1
    sn = 0 # sn = state number
    # headpos is the position of the read/write head of the Turing
    # machine, counting from the least significant bit.
    headpos = 0 
    bpa = bpsn + 3 # bpa = bits per action
    bps = bpa * 3 # bps = bits per state.
    while time > 0:
        time -= 1
        state = bits.getbits(machine, sn * bps, bps)
        animate(tape_length, tape_bits, headpos, sn, state, bpsn, short=False)
        if headpos < 0 or headpos >= tape_length:
            state = bits.getbits(state, 2*bpa, bpa)
        elif bits.getbits(tape_bits, headpos, 1):
            state = bits.getbits(state, bpa, bpa)
        else: state = bits.getbits(state, 0, bpa)
        action = bits.getbits(state, 0, 2)
        motion = bits.getbits(state, 2, 1)
        sn = bits.getbits(state, 3, bpsn)
        if action == 0 or action == 1: # Write a 0 or 1.
            # If headpos is negative, don't do anything.
            if headpos >= 0:
                if headpos >= tape_length:
                    tape_length = headpos + 1
                tape_bits = bits.setbit(tape_bits, headpos, action)
        elif action == 2: # Truncate.
            if headpos < 0: raise Machine_failure("Truncate when past right")
            tape_length = max(headpos,0)
            tape_bits &= (long(1) << tape_length) - 1
        elif action == 3: # Done.
            animate (tape_length, tape_bits, headpos, sn, state, bpsn,
                     short=True)
            return turing_tape(length=tape_length, bits=tape_bits)
        if motion: headpos -= 1
        else: headpos += 1
    raise Machine_failure("Out of time.")