
import random

TESTRESULT_NOFAILURE = "NoFailure"
TESTRESULT_KEEPSUFFIX = "KeepSuffix"
TESTRESULT_KEEPPREFIX = "KeepPrefix"
TESTRESULTS = set([TESTRESULT_NOFAILURE, TESTRESULT_KEEPSUFFIX,
                   TESTRESULT_KEEPPREFIX])


class ListReducer(object):
    """Reduce lists of objects. Inspired by llvm bugpoint"""

    def __init__(self, l):
        self.target_list = l
        # Maximal number of allowed splitting iterations,
        # before the elements are randomly shuffled.
        self.max_iters_without_progress = 3

        # Maximal number of allowed single-element trim iterations. We add a
        # threshhold here as single-element reductions may otherwise take a
        # very long time to complete.
        self.max_trim_iterations_without_back_jump = 3
        self.shuffling_enabled = True

        self.num_iters_without_progress = 0
        self.mid_top = 0
        self.max_iters = self.max_iters_without_progress

    def _reset_progress(self):
        self.max_iters = self.max_iters_without_progress
        self.num_iters_without_progress = 0

    def run_test(self, prefix, suffix):
        raise RuntimeError("Abstract method")

    def _should_continue(self, result):
        if result == TESTRESULT_KEEPPREFIX:
            # We are done, we have the base case and the base case fails.
            if len(self.target_list) == 1:
                return {'should_continue': False, 'result': True}
            else:
                # There is an error, and we can narrow it down further.
                return {'should_continue': True, 'result': None}

        if result == TESTRESULT_KEEPSUFFIX:
            raise RuntimeError("ListReducer internal error: Selected empty "
                               "set!")
        raise RuntimeError('Unknown test result: %s' % result)

    def _test_shuffle_slow_converging_list(self):
        if not self.shuffling_enabled or \
           self.num_iters_without_progress <= self.max_iters_without_progress:
            return

        print("*** Testing shuffled set...")
        shuffled_list = list(self.target_list)
        random.shuffle(shuffled_list)
        # TODO: Is this correct? I guess we are always doing something.
        self.num_iters_without_progress = 0

        # Check that the random shuffle does not lose the bug.
        (result, _, _) = self.run_test(shuffled_list, [])
        if result != TESTRESULT_KEEPPREFIX:
            # If we fail here, disable any further shuffling...
            self.shuffling_enabled = False
            print("*** Shuffling hides the bug...")
            return

        self.mid_top = len(shuffled_list)
        self.max_iters = self.max_iters + 2
        print("*** Shuffling does not hide the bug...")
        self.target_list = shuffled_list

    def _test_prefix_suffix(self, mid, prefix, suffix):
        (result, prefix, suffix) = self.run_test(prefix, suffix)

        if result == TESTRESULT_KEEPSUFFIX:
            # The property still holds. We can just drop the prefix
            # elements, and shorten the list to the "kept" elements.
            self.target_list = suffix
            self.mid_top = len(self.target_list)

            # Reset the progress threshold
            self._reset_progress()
            return False

        if result == TESTRESULT_KEEPPREFIX:
            # The predicate still holds, shorten the list to the prefix
            # elements.
            self.target_list = prefix
            self.mid_top = len(self.target_list)
            self._reset_progress()
            return False

        assert(result == TESTRESULT_NOFAILURE)
        # The property does not hold. Some of the elements we removed must
        # be necessary to maintain the property.
        self.mid_top = mid
        self.num_iters_without_progress = \
            self.num_iters_without_progress + 1
        return False

    def _trim_target_list(self):
        self.mid_top = len(self.target_list)
        self.max_iters = self.max_iters_without_progress

        # Binary split reduction loop
        while self.mid_top > 1:
            # If the loop doesn't make satisfying progress, try shuffling.
            # The purpose of shuffling is to avoid the heavy tails of the
            # distribution (improving the speed of convergence).
            self._test_shuffle_slow_converging_list()

            # Split the list into a prefix, suffix list and then run test on
            # those.
            mid = self.mid_top/2
            if not self._test_prefix_suffix(mid, self.target_list[:mid],
                                            self.target_list[mid:]):
                # If we returned false, then we did some sort of work and there
                # was not an error, so continue.
                continue

            # Otherwise, the test routine signaled an error, so return True to
            # signal error.
            return True
        # If we reach this point, return False, we have no further work we can
        # do.
        return False

    def _trim_try_backjump_and_trim_suffix(self):
        backjump_probability = 10
        if len(self.target_list) <= 2:
            return False
        changed = True
        trim_iters = 0

        # Trimming loop
        while changed:
            changed = False

            # If the binary split reduction loop made an unfortunate sequence
            # of splits, the trimming loop might be left off with a huge
            # number of remaining elements (large search space). Backjumping
            # out of that search space and attempting a different split can
            # significantly improve the convergence speed.
            if random.randint(0, 100) < backjump_probability:
                return True

            # Check interior elements, using an offset to make sure we do not
            # skip elements when we trim.
            offset = 0
            for i in range(1, len(self.target_list)-1):
                real_i = i + offset
                test_list = self.target_list[real_i:]
                (result, prefix, suffix) = self.run_test([], test_list)
                if result == TESTRESULT_KEEPSUFFIX:
                    # We can trim the list!
                    self.target_list = test_list
                    offset = offset - 1
                    changed = True
            if trim_iters >= self.max_trim_iterations_without_back_jump:
                return False
            trim_iters = trim_iters + 1

    def reduce_list(self):
        random.seed(0x6e5ea738)  # Seed the random number generator
        (result, self.target_list, kept) = self.run_test(self.target_list, [])
        assert(result in TESTRESULTS)
        (should_continue, result) = self._should_continue(result)
        if not should_continue:
            return result

        # Now try to trim the list.
        should_backjump = True
        while should_backjump:
            # If self._trim_target_list returns True, then we failed to
            # reduce. Bail!
            if self._trim_target_list():
                return False

            # Finally decide if we should back_jump
            should_backjump = self._trim_try_backjump_and_trim_suffix()

        # There are some failure and we've narrowed them down
        return True