#!/usr/bin/python3
"""Variants of Russ Cox’s bisect algorithm to find a minimal satisfying subseq

(Invoke from the command line with or without ``-easy`` and ``-long``
to demo different variants.)

<https://research.swtch.com/bisect> presents an algorithm previously
presented in <https://bernsteinbear.com/blog/cinder-jit-bisect/> for
finding a locally minimal satisfying subsequence Σ of a sequence Π
satisfying some predicate that has the property that if a sequence Φ
is satisfying, all the longer subsequences of the original sequence Π
of which Φ is a subsequence are also satisfying.

“Subsequence” here is “subsequence” in the LCS sense, not “substring”:
“ktb” is a subsequence of “kitab”, for example, but not a substring.

This is useful for automatic debugging because “My program crashes on
input Σ” is very often such a predicate, and simple binary search for
a single substring of the input is often insufficient, because the
necessary input to crash the program is not always a contiguous chunk
of the input stream.  But it is not limited to that application.

This does *not* implement the hash-based bisection method that is the
main focus of Cox’s post.  It also doesn’t implement the “easy/hard”
algorithm.  In fact, before I implemented the “easy” algorithm, I
implemented how I misremembered the “easy” algorithm, which turns out
to be an arguably simpler algorithm that also works.  That’s
``bisect_dumb`` below.

Here’s the output on a test from Zeller’s _Why Programs Fail_, which
this algorithm solves with 21 probes instead of Zeller’s 48::

    ☑ '<SELECT NAME="priority" MULTIPLE SIZE=7>'
    ☒ '<SELECT NAME="priori'
    ☒ '<SELECT NAME="priority" MULTIP'
    ☒ '<SELECT NAME="priority" MULTIPLE SI'
    ☒ '<SELECT NAME="priority" MULTIPLE SIZE='
    ☒ '<SELECT NAME="priority" MULTIPLE SIZE=7'
    Found required item > at 39
    ☑ '<SELECT NAME="prior>'
    ☑ '<SELECT N>'
    ☒ '<SEL>'
    ☑ '<SELECT>'
    ☒ '<SELEC>'
    Found required item T at 6
    ☒ '<SET>'
    ☒ '<SELET>'
    Found required item C at 5
    ☒ '<SCT>'
    ☒ '<SELCT>'
    Found required item E at 4
    ☒ '<SECT>'
    ☒ '<SEECT>'
    Found required item L at 3
    ☒ '<LECT>'
    ☒ '<SLECT>'
    Found required item E at 2
    ☒ '<ELECT>'
    Found required item S at 1
    ☒ 'SELECT>'
    Found required item < at 0
    [0, 1, 2, 3, 4, 5, 6, 39]
    '<SELECT>'

With ``-easy``, using Cox’s "easy" algorithm, it instead produces::

    ☒ ''
    ☒ 'ty" MULTIPLE SIZE=7>'
    ☒ 'ME="priority" MULTIPLE SIZE=7>'
    ☒ 'CT NAME="priority" MULTIPLE SIZE=7>'
    ☒ 'ELECT NAME="priority" MULTIPLE SIZE=7>'
    ☒ 'SELECT NAME="priority" MULTIPLE SIZE=7>'
    Found on left ['<']
    ☒ '<ELECT NAME="priority" MULTIPLE SIZE=7>'
    Found on right ['S']
    Found on left ['<', 'S']
    ☒ '<SCT NAME="priority" MULTIPLE SIZE=7>'
    ☒ '<SLECT NAME="priority" MULTIPLE SIZE=7>'
    Found on left ['E']
    ☒ '<SECT NAME="priority" MULTIPLE SIZE=7>'
    ☒ '<SEECT NAME="priority" MULTIPLE SIZE=7>'
    Found on left ['L']
    ☒ '<SELCT NAME="priority" MULTIPLE SIZE=7>'
    Found on right ['E']
    Found on right ['L', 'E']
    Found on right ['E', 'L', 'E']
    Found on left ['<', 'S', 'E', 'L', 'E']
    ☒ '<SELEME="priority" MULTIPLE SIZE=7>'
    ☒ '<SELE NAME="priority" MULTIPLE SIZE=7>'
    ☒ '<SELET NAME="priority" MULTIPLE SIZE=7>'
    Found on left ['C']
    ☒ '<SELEC NAME="priority" MULTIPLE SIZE=7>'
    Found on right ['T']
    Found on left ['C', 'T']
    ☑ '<SELECTME="priority" MULTIPLE SIZE=7>'
    Found on right []
    Found on right ['C', 'T']
    Found on left ['<', 'S', 'E', 'L', 'E', 'C', 'T']
    ☑ '<SELECTty" MULTIPLE SIZE=7>'
    Found on right []
    Found on left ['<', 'S', 'E', 'L', 'E', 'C', 'T']
    ☒ '<SELECT'
    ☑ '<SELECTLE SIZE=7>'
    Found on left []
    ☒ '<SELECT'
    ☑ '<SELECTZE=7>'
    Found on left []
    ☒ '<SELECT'
    ☑ '<SELECT=7>'
    Found on left []
    ☒ '<SELECT'
    ☑ '<SELECT7>'
    Found on left []
    ☒ '<SELECT'
    ☑ '<SELECT>'
    Found on left []
    ☒ '<SELECT'
    Found on right ['>']
    Found on right ['>']
    Found on right ['>']
    Found on right ['>']
    Found on right ['>']
    Found on right ['>']
    [0, 1, 2, 3, 4, 5, 6, 39]
    '<SELECT>'

Note that, just like Zeller’s `ddmin` algorithm, both of these return
a locally minimal sequence, having previously tried each of the
possible individual-item removals.

"""
import re
import sys


def first_satisfying_bisect(p, start, end):
    """Return the first i in [start, end) such that p(i), if any.

    This is in a sense the most basic version of the binary search
    algorithm.

    - p:  	predicate to satisfy.
    - start: 	first integer in the candidate range.
    - end:	first integer > start not in the candidate range.

    Subject to the restriction that if p(j) and k > j, p(k) too.  That
    is, once p goes from false to true, it never goes back to false.

    Possibly p(i) is false for all values, in which case this
    algorithm returns end.  But it will never call p(end).

    """
    while start < end:
        # Invariant: the correct return value is in [start, end].
        # Variant: end - start strictly diminishes each iteration.
        mid = start + (end - start) // 2
        if p(mid):
            end = mid  # mid is a valid return value; nothing later can be
        else:
            start = mid + 1  # mid, and everything earlier, is *not* valid

    return start

def bisect_dumb(p, s, log=lambda *args: None):
    """Find a locally-minimal satisfying subseq with a dumb algorithm.

    - p: predicate we are trying to satisfy with a list elements from s.
    - s: a list that satisfies p.

    Returns a list of indices into s.

    This version of the algorithm will suffer a slowdown factor of
    lg M to find needed items at indices near M.  So for example
    prepending 10000 spaces to the test string below makes it require
    120 probes instead of 21.

    """
    assert p(s)
    end, need = len(s), []      # “need” is Cox’s “forced” set.

    while True:
        need.sort()
        needed = [s[j] for j in need]
        # identify index of last required element in [0, end)
        last = first_satisfying_bisect(lambda i: p(s[:i] + needed), 0, end)
        if last == 0:
            return need  # s[:0] + needed is just needed, and is satisfying

        end = last - 1
        need.append(end)      # If s[:7] is needed, we need element 6.
        log("Found required item", s[end], "at", end)


def bisect_easy(p, s, log=lambda *args: None, targets=None, need=[]):
    """The actual “easy” algorithm from Cox’s post.

    I translated this from the first Golang listing, but adapted its
    interface in the process to be compatible with ``bisect_dumb``
    above.  It returns a sorted list of indices into s.  Cox’s version
    returns the actual items from s rather than the indices.

    This requires 29 probes into Zeller’s example rather than the 21
    required by ``bisect_dumb``, but it is more efficient for long
    sequences, requiring only 45 instead of ``bisect_dumb``’s 120 when
    we prepend 10kB of spaces to the test string (``-long``).

    """
    if targets is None:
        targets = list(range(len(s)))
    if not targets or p([s[i] for i in sorted(need)]):
        return []
    if len(targets) == 1:
        return [targets[0]]

    m = len(targets)//2
    left, right = targets[:m], targets[m:]

    left_reduced = bisect_easy(p, s, log, left, right + need)
    log("Found on left", [s[i] for i in left_reduced])

    # It’s important to use `left_reduced` here rather than just
    # `left` if we want to make sure our result is actually
    # satisfying!
    right_reduced = bisect_easy(p, s, log, right, left_reduced + need)
    log("Found on right", [s[i] for i in right_reduced])

    return left_reduced + right_reduced


def trisect_easy(p, s, log=lambda *args: None, targets=None, need=[]):
    """A trisecting version of Cox’s “easy” algorithm.

    I have the intuition that this will be consistently more
    efficient, but tests so far don’t provide strong enough evidence
    for me to either confirm or reject that hypothesis.

    """
    if targets is None:
        targets = list(range(len(s)))
    if not targets or p([s[i] for i in sorted(need)]):
        return []
    if len(targets) == 1:
        return [targets[0]]

    m, n = len(targets)//3, 2*len(targets)//3
    left, mid, right = targets[:m], targets[m:n], targets[n:]

    left_reduced = trisect_easy(p, s, log, left, mid + right + need)
    log("Found on left", [s[i] for i in left_reduced])

    mid_reduced = trisect_easy(p, s, log, mid, left_reduced + right + need)
    log("Found in middle", [s[i] for i in mid_reduced])

    right_reduced = bisect_easy(p, s, log, right, left_reduced + mid_reduced + need)
    log("Found on right", [s[i] for i in right_reduced])

    return left_reduced + mid_reduced + right_reduced


def example_predicate(s):
    """<SELECT> example from Zeller.

    See Zeller’s _Why Programs Fail_, second edition, §5.5, example
    5.8, p. 116 (124/388).  Mozilla was crashing upon the second
    attempt to print the Bugzilla home page, and the problem turned
    out to be that it contained a <select> tag.  The ``bisect_dumb``
    algorithm minimizes the string successfully in 21
    trials, and ``bisect_easy`` in 29, instead
    of the 48 achieved by Zeller’s ``ddmin``.

    """
    return re.compile(r'(?i)<select.*>').search(''.join(s))

example_string = '<SELECT NAME="priority" MULTIPLE SIZE=7>'


def instrument(p, formatter=lambda xs: repr(''.join(xs))):
    def instrumented(xs):
        result = p(xs)
        checkbox = '☑' if result else '☒'
        print(checkbox, formatter(xs))
        return result

    return instrumented
        

if __name__ == '__main__':
    s = example_string
    if '-long' in sys.argv:
        s = ' ' * 10000 + s

    bisect = (trisect_easy if '-tri' else
              bisect_easy if '-easy' in sys.argv else
              bisect_dumb)
    result = bisect(instrument(example_predicate), list(s), log=print)
    print(result)
    print(repr(''.join(s[i] for i in result)))