# 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.)
# Test case for video prediction.

# To make the test case practically computable, do it by fudging the
# generate_explanations method.  The video is [0,1,0].
# If n is between 0 and 5 it returns the real value, if n is more it
# returns the empty list unless n is right for a TM program that would
# lead to one of the following solutions:
# [0,1,0,1,...] alternating forever
# [0,1,0,0,...] where the only 1 is at position 1 in the list and the
# rest are 0,
# and the previous two where the perception function sees the inverse
# of what's there.
# Also include some programs that are garbage bits appended to
# existing programs.
# Also include a physical law that generates 3 frames and then fails.
# Also include a perceptual model that fails intermittently.
# Also include a physical law that simply returns wrong answers, say
# all 0's.

import machine
import test_util
import bits
from constants import left, right, end, done, truncate
from compile import turing_program, turing_compile
from compile_and_run import compile_and_run
from video_prediction import Video_prediction_problem, next_frame, \
     Video_prediction_explanation
from speed_prior import Speed_prior
from test_util import assert_equals
from turing_tape import turing_tape

t0 = turing_tape(length=1, bits=0)
t1 = turing_tape(length=1, bits=1)

# A frame of video is a Turing machine tape, which is a pair
# (length, goedel-number for the tape contents).
# The test problem has alternating 0's and 1's.
the_video = [t0,t1,t0,t1]
the_other_video = [t0,t1,t0,t1,t1]

# Flip is the physical law for the solution to the test problem.
# An empty tape gives us an initial state, which is a tape with just a 0.
# A tape with a 0 gives us a tape with a 1.
# A tape with a 1 gives us a tape with a 0.
flip_as = turing_program("start",
                         start={end:(0, left, "done"),
                                0:(1, right, "done"),
                                1:(0, right, "done")},
                         done=done)

flip = Speed_prior(absyn=flip_as,logtime=1)
assert_equals(flip.run(machine.empty_tape), t0)
assert_equals(flip.run(t0), t1)
assert_equals(flip.run(t1), t0)

# If you animate and you gave the abstract syntax, the state names
# should be as specified in the abstract syntax.
assert "done" in \
       test_util.with_output_to_string(lambda:flip.run(machine.empty_tape, animate=True))["output"]

no_as_flip = Speed_prior(program=turing_compile(flip_as).program, logtime=1)
s = test_util.with_output_to_string(lambda:no_as_flip.run(machine.empty_tape, animate=True))["output"]
assert "001" in s
assert "done" not in s

# identity is the perceptual apparatus.  It simply exits immediately,
# leaving the tape unchanged.
identity_as = turing_program("start", start=done)
identity = Speed_prior(program=turing_compile(identity_as).program, logtime=0)
def check_identity(i):
    assert_equals(identity.run(t0), t0)
    assert_equals(identity.run(t1), t1)
check_identity(identity)

longer_identity = Speed_prior(program=
                              identity.program + (1L << (identity.program_length() + 3)),
                              logtime=0)
check_identity(longer_identity)
assert identity.is_prefix(longer_identity)

correct_law = Video_prediction_explanation(physics=flip,
                                         perception=identity,
                                         name="correct_law")
longer_law = Video_prediction_explanation(physics=flip,
                                        perception=longer_identity,
                                        name="longer_law")

assert correct_law.is_prefix(longer_law)

incorrect_law = Video_prediction_explanation(physics=identity,
                                           perception=flip,
                                           name="incorrect_law")

longer_incorrect_law = Video_prediction_explanation(physics=longer_identity,
                                                  perception=flip,
                                                  name="longer_incorrect_law")

assert "longer_incorrect_law" in "%s" % (longer_incorrect_law,)
assert "longer_incorrect_law" in "%r" % (longer_incorrect_law,)

# clock maps empty to 0, and otherwise increments forever.
clock_as = turing_program("start",
                          start={end:(0, left, "done"),
                                 0: (1, right,"done"),
                                 1: (0, left, "inc")},
                          inc={end:(1, left, "done"),
                               0: (1, right, "done"),
                               1: (0, left, "inc")},
                          done=done)

clock = Speed_prior(absyn=clock_as, logtime=2)

assert_equals(clock.run(machine.empty_tape), t0)
assert_equals(clock.run(t0), t1)
assert_equals(clock.run(t1), turing_tape(length=2, bits=2))
assert_equals(clock.run(turing_tape(length=2, bits=2)),
              turing_tape(length=2, bits=3))
assert_equals(clock.run(turing_tape(length=2, bits=3)),
              turing_tape(length=3, bits=4))

# special_case_as is the perception meant to be used with clock_as as
# the law of physics.  If it sees 0 or 2, it returns 0, otherwise it
# returns 1.  Thus it leads to the predicted frames of video
# (0, 1, 0, 1, 1, 1, 1, ...), which is consistent with the video
# observed, but "wrong" in the sense that this is more complex than
# the simple alternating solution.
special_case_as = turing_program(
    "start",
    start={(end, 0):(0, left, "mb02"),
           1: (1, left, "trunc")},
    trunc={(0,1,end):(truncate, left, "done")},
    done=done,
    # At mb02, it may be a 0 or a 2.  We are one step from the
    # right end of the tape, and the bit to our right is a 0.
    mb02={end: (truncate, left, "done"),
          0: (truncate, right, "isnt2b"),
          1: (1, left, "mb2")},
    # At mb2, it may be a 2.  We are two steps from the right
    # and the bits to our right are 10.
    mb2={end: (truncate, right, "is2"),
         (1, 0): (truncate, right, "isnt2")},
    # The tape has 10 as its entire contents, and we're on the 1.
    is2={(end, 0, 1): (truncate, right, "done")},
    # The tape has 10 as its entire contents, and we're on the
    # 1, but we have to put a 1 at the right because it had
    # garbage to the left. 
    isnt2={(end, 0, 1): (truncate, right, "isnt2b")},
    # The tape has 0 as its entire contents.  We want to put a
    # 1 there.
    isnt2b={(end, 0, 1): (1, left, "done")})

special_case = Speed_prior(absyn=special_case_as, logtime=3)
assert_equals(special_case.run(t0), t0)
assert_equals(special_case.run(t1), t1)
assert_equals(special_case.run(turing_tape(length=2, bits=0)), t1)
assert_equals(special_case.run(turing_tape(length=2, bits=2)), t0)
assert_equals(special_case.run(turing_tape(length=3, bits=6)), t1)

other_law = Video_prediction_explanation(perception=special_case,
                                       physics=clock,
                                       name="other_law")

# correct_law.program_size() is 36.
# One program takes 2**0 steps and one takes 2**1, so
# -bits.log2(correct_law.probability()) = 36 + 0 + 1 = 37.

def check_video(ringers):
    # ringers are the high complexity explanations we throw into the
    # sham physical law generator.
    all_explanations = []
    for i in range(4):
        all_explanations.extend(Video_prediction_problem([])
                              .generate_explanations(i))
    all_explanations.extend(ringers)
    class Test_video_prediction_problem(Video_prediction_problem):
        # Sham physical law generator.
        def generate_explanations(self, n):
            result = [explanation for explanation in all_explanations
                                        if explanation.size() == n]
            return result
    problem = Test_video_prediction_problem(video=the_video)
    problem.matches(correct_law)
    problem.matches(other_law)
    test_util.expect_exception(lambda: problem.matches(incorrect_law))
    # Specify a low eps so the physical law finder explores other_law,
    # which has complexity 196.
    assert next_frame(the_video, eps=1e-70,
                      problem_class=Test_video_prediction_problem) == t0
    assert next_frame(the_other_video, eps=1e-70,
                      problem_class=Test_video_prediction_problem) == t1
    assert next_frame(the_video+[t0], eps=1e-70,
                      problem_class=Test_video_prediction_problem) == t1

# Skip the simple tests for now.
#check_video([correct_law])
#check_video([correct_law, longer_law])
check_video([correct_law, longer_law, incorrect_law,
             longer_incorrect_law, other_law])