# Text diffing

This unit provides routines to compare to pieces of text and figure out what
lines we need to add and/or remove to the first one so that it becomes the same
as the second one.

It also provides routines to format this diff in the "Unified diff" standard.

This unit uses LF as a line separator.

## The algorithm

First of all, each text is separated into lines and each line has a checksum
computed. Therefore, what we compare here are two arrays of integers.

So, we begin on the first line on each side (let's call the original text the
"left" one and the new next the "right" one) and during the whole process, we
gradually "advance" on each side, not necessarily at the same speed.

The process consists of accumulating Hunk structures (see below). Our active
hunk beings at left/right indexes 0 and both counts to 0.

We begin by simply advancing as long as both sides are equal.

Then, as soon as we have a difference, we begin the Largest Common Sequence LCS
procedure, that is, we scn the right side for the largest block that matches our
current position on the left side and we also scan the left side for the largest
block that matches our current right side position.

The easiest case is when there is no match on either side. As long as there is
no match of the left side (that is, not a single line) in the right side, we
advance leftidx and increase delcnt. As long as there is no match on the right
side in the left side, we advance rightidx and increase addcnt.

If this brings us to a situations where we're equal again, close the hunk, we're
rolling.

Otherwise, this will bring us in a situation where we have two match blocks,
each with a skipcount and a matchcount figure. Now we need to choose the most
efficient side: deleting the left's skip count or adding the right's skip count.

After whichever of those operations, we can close the hunk and advance both
pointers by the matchcount of the chosen side.

To choose the best side, we assign a score to each, the score being
matchcount-skipcount. The highest (signed comparison) score wins.

And that's it, we repeat until we've reached the end of both sides.

When we reach one end before the other, then there's a last hunk with either
an addition or a deletion.

## API

### Constants

CONTEXTSZ  3. Number of lines around hunks we show off in diff printing.

### Structures

struct Hunk {
  uint leftidx rightidx delcnt addcnt ;
}

Structures yielded by diff[].

leftidx  The index in the left text where lines are removed or added.
rightidx The index in the right text where lines are added.
delcnt   Number of lines deleted on the left
addcnt   Number of lines added on the left, copied from the right

### Words

diff[] ( left u right u -- a u )
  Given two ranges of characters "left u" and "right u", transform them into
  arrays of CRCs and computes an array "a u" of Hunk structures (not pointers)
  which it yields.

  The CRCs and the Hunk structure need a temporary storage space, which is a
  static buffer managed by this routine using [mem/reuse]. The yielded result
  is only valid until the next call to "diff[]".

.diff[] ( left u right u -- )
  Do a diff check with "diff[]" and then print the changes in the form of a
  unified diff.

### Private words

max[]= ( a1 u1 a2 u2 -- n )
  Compare the two supplied ranges for equality and stop as soon as they're
  unequal, yielding the number of elements that match.

  Both arguments are aligned ranges of 32-bit elements.

lcs ( a1 u1 a2 u2 -- ?idx n-or-0 )
  In "a2 u2", find the largest sequence that matches the beginning of "a1 u1".

  Both arguments are aligned ranges of 32-bit elements.

  If the first element of "a1 u1" is not present anywhere in "a2 u2", yield u=0
  and idx is absent.

  Otherwise, yield the index, in "a2 u2" of the beginning of that sequence as
  well as the length of that matching sequence as "u".

diffcrcs[] ( left u right u -- ... n )
  Given two ranges of line checksums "left u" and "right u", compute the series
  of changes that must be applied to "left" in order to obtain "right.

  Those changes are yielded as a "... n" PS list of *quads* (not Hunk
  pointers) (leftidx, rightidx, delcnt, addcnt) with "addcnt" on PS top. They
  are yielded in reverse order of occurrence, that is, the last change on PS
  top.

lines>crcs ( ... n a u  -- ... n )
  With "a u" being a range characters, compute the crcs [num/crc] of each line
  (CR and/or LF are line separators), accumulating it into the "... n" PS list.

  This routine is designed to be ran on "readbuf" results, which means that
  lines can be cut in two. When input "n" is not 0, the top item of the PS list
  is the initial CRC. Otherwise, "crc32$" is called to get that initial value.

hunkctx ( hunk -- lo hi )
  Yield the context range a hunk covers in terms of low and high line indexes on
  the *left* side. CONTEXTSZ is both subtracted and added to enlarge the range.
  Deleted lines are also counted in that range so that this index range really
  represent the line coverage on the left.

grouphunks ( a u -- a u n )
  Given an array of Hunks as yielded by "diff[]", group the first hunks of the
  array as long as their context touch. Yield the number of hunks is that group.