Compute diffs between two sequences.

  This function is similar in functionality and spirit to
  difflib.SequenceMatcher.get_opcodes, but it seems to run faster.

  if a_start, a_end, b_start, b_end are specified, then we compute diffs of
  the segments a[a_start:a_end] and b[b_start:b_end].  Returned indices
  are relative to the full sequence.

  We try to match the longest matching segments first, but due to heuristics
  in finding the matches, this is not guaranteed.

  Matching segments shorter than min_match_length are counted as part of the
  surrounding differing segments, unless they are at the beginning or end of
  both sequences.  This helps eliminate junk matches.

  Args:
    a: a sequence
    b: a sequence
    a_start: an optional integer
    a_end: an optional integer
    b_start: an optional integer
    b_end: an optional integer
    min_match_length: an integer
    max_recursion_depth: an integer - avoids crashes in weird corner cases
      involving pairs of long repetitive sequences.

  Returns:
    a list of 5-tuples (tag, i1, i2, j1, j2).
    Each tuple represents the alignment of segment a[i1:i2] with b[j1:j2].
      tag is either "equal" or "diff".  Note that the tags differ from those
      returned by difflib.SequenceMatcher.get_opcodes.

def fast_match_sequences(a,
                         b,
                         a_start=0,
                         a_end=None,
                         b_start=0,
                         b_end=None,
                         min_match_length=3,
                         max_recursion_depth=128):
  """Compute diffs between two sequences.

  This function is similar in functionality and spirit to
  difflib.SequenceMatcher.get_opcodes, but it seems to run faster.

  if a_start, a_end, b_start, b_end are specified, then we compute diffs of
  the segments a[a_start:a_end] and b[b_start:b_end].  Returned indices
  are relative to the full sequence.

  We try to match the longest matching segments first, but due to heuristics
  in finding the matches, this is not guaranteed.

  Matching segments shorter than min_match_length are counted as part of the
  surrounding differing segments, unless they are at the beginning or end of
  both sequences.  This helps eliminate junk matches.

  Args:
    a: a sequence
    b: a sequence
    a_start: an optional integer
    a_end: an optional integer
    b_start: an optional integer
    b_end: an optional integer
    min_match_length: an integer
    max_recursion_depth: an integer - avoids crashes in weird corner cases
      involving pairs of long repetitive sequences.

  Returns:
    a list of 5-tuples (tag, i1, i2, j1, j2).
    Each tuple represents the alignment of segment a[i1:i2] with b[j1:j2].
      tag is either "equal" or "diff".  Note that the tags differ from those
      returned by difflib.SequenceMatcher.get_opcodes.
  """
  if a_end is None:
    a_end = len(a)
  if b_end is None:
    b_end = len(b)
  if a_start == a_end and b_start == b_end:
    return []
  if a_start == a_end or b_start == b_end:
    return [("diff", a_start, a_end, b_start, b_end)]
  # Compute an index from value to first occurrence in the b segment.
  # Technically, we should index and explore all occurrences of a value,
  # but that might be much slower.
  b_index = {}
  for j in range(b_end - 1, b_start - 1, -1):
    b_index[b[j]] = j
  # we will look for the longest match we can find.
  max_match_length = 0
  a_pos = a_start
  while a_pos < a_end:
    val = a[a_pos]
    b_pos = b_index.get(val)
    if b_pos is None:
      a_pos += 1
      continue
    else:
      a_match_start = a_pos
      a_match_end = a_pos + 1
      b_match_start = b_pos
      b_match_end = b_pos + 1
      while (a_match_start > a_start and b_match_start > b_start and
             a[a_match_start - 1] == b[b_match_start - 1]):
        a_match_start -= 1
        b_match_start -= 1
      while (a_match_end < a_end and b_match_end < b_end and
             a[a_match_end] == b[b_match_end]):
        a_match_end += 1
        b_match_end += 1
      # Compute the length of the matching segment.  We prefer the longest.
      match_length = a_match_end - a_match_start
      # Extra credit for matching at the beginning or end of the sequence.
      if a_match_start == 0 and b_match_start == 0:
        match_length += min_match_length
      if a_match_end == len(a) and b_match_end == len(b):
        match_length += min_match_length
      if match_length > max_match_length:
        max_match_length = match_length
        best_match = (a_match_start, a_match_end, b_match_start, b_match_end)
      # advance a_pos to the end of this match to avoid wasting time
      # rediscovering this match.
      a_pos = a_match_end
  if max_match_length < min_match_length or max_recursion_depth == 0:
    return [("diff", a_start, a_end, b_start, b_end)]
  a_match_start, a_match_end, b_match_start, b_match_end = best_match
  return (fast_match_sequences(
      a, b, a_start, a_match_start, b_start, b_match_start, min_match_length,
      max_recursion_depth - 1) + [
          ("equal", a_match_start, a_match_end, b_match_start, b_match_end)
      ] + fast_match_sequences(a, b, a_match_end, a_end, b_match_end, b_end,
                               min_match_length, max_recursion_depth - 1))