# 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.)
from turing_tape import turing_tape, binarytape
import test_util
from test_util import assert_equals
import compile
import machine
import speed_prior
from compile_and_run import compile_and_run
from compile import turing_program, turing_compile
from constants import left, right, end, done, truncate

# Make an empty tape.
empty_as = turing_program("trunc",
                          trunc = {(0,1,end):(truncate, right, "done")},
                          done = done)

assert compile_and_run(
    absyn=empty_as, inputsize=10, inputtape=0123, steps=5) == \
    turing_tape(length=0, bits=0)

# Put the integer 3 on the tape.
three_as = turing_program("b0",
                          b0={(0,1,end):(truncate, left, "b1")},
                          b1={(0,1,end):(1, right, "b2")},
                          b2={(0,1,end):(1, right, "b3")},
                          b3=done)

assert compile_and_run(
    absyn=three_as, inputstring="1011010", steps=5) == binarytape("11")

# Generate a program that writes the integer n to the tape.
def constant_as(n):
    # If I'm asked to put 0 on the tape, I want "0", not an empty
    # tape, so length starts as 1, not as 0.
    length = 1
    while (1 << length) < n:
        length += 1
    states={"trunc": {(0,1,end):(truncate, right, "trunc2")},
            "trunc2": {(0,1,end):(0, left, "0")}}
    for i in range(0, length):
        states[str(i)] = {(0,1,end):(n&1, left, str(i+1))}
        n = n >> 1
    states[str(length)]={(0,1,end):done}
    return turing_program("trunc", **states)

assert compile_and_run(constant_as(0), 16, 0123, 40) == \
       turing_tape(length=1, bits=0)
assert compile_and_run(constant_as(936), 16, 0123, 40) == \
       turing_tape (length=10, bits=936)

# Double the input number.  This requires inserting a 0 and
# maintaining state information to copy each bit until we get to the
# end.

double_as = turing_program("haszero",
                           haszero={0:(0, left, "haszero"),
                                     1:(0, left, "hasone"),
                                     end:(0, left, "end")},
                           hasone={0:(1, left, "haszero"),
                                   1:(1, left, "hasone"),
                                   end:(1, left, "end")},
                           end={(0,1,end):done})

car = compile_and_run(double_as, 8, 37, 10)
assert car == turing_tape(length=9, bits=74), "car is %r" % (car,)

# Check that running out of time is implemented.
test_util.expect_exception(lambda: compile_and_run(double_as, 8, 37, 2))

assert speed_prior.Speed_prior(logtime=4, program_length=50,
                               program=turing_compile(double_as).program)\
                               .run(turing_tape(length=8, bits=37)) == \
                               turing_tape(length=9, bits=74)

# If the tape is empty, put a 0.  If we see a 0, put a 1.  If we see a
# 1, put a 0.
complement_as = turing_program("look",
                               look={0:(1, left, "end"),
                                     1:(0, left, "end"),
                                     end:(0, left, "end")},
                               end=done)
assert compile_and_run(complement_as, 0, 0, 5) == turing_tape(length=1, bits=0)
assert compile_and_run(complement_as, 1, 0, 5) == turing_tape(length=1, bits=1)
assert compile_and_run(complement_as, 1, 1, 5) == turing_tape(length=1, bits=0)
# 24 million or so.
# print turing_compile(complement_as)["program"]

do_nothing_as = turing_program("nothing",
                               nothing ={(0,1,end):done})
assert compile_and_run(do_nothing_as, 1, 1, 5) == turing_tape(length=1, bits=1)

assert_equals(test_util.with_output_to_string(
    lambda: compile_and_run(do_nothing_as, 1, 1, 5, animate=True))["output"],
"""  >1< state nothing 0>dnl nothing 1>dnl nothing end>dnl nothing
  >1<
""")
# The next one prints 1638:
# print turing_compile(do_nothing_as).program
# If we could guess do_nothing_as and complement_as, then we could do
# a test run of the laws-of-physics program with the universe states
# 0, 1, 0, 1, 0, 1 and see if the next states are probably 0 and then 1.
# But I'm not sure I can guess that much.
# We could leave out perception, and then only have 24 million to
# search through.  I don't think so:
# We're in an intepreted language.
# My code wants to have all 24M of them in memory at once.
# Turing machines are such an inefficient representation.