ARRAYLIST_IDX deals with the head pointer. Explicitly cast to unsigned long and use %lu in the format string. Clang 10.0.1 used to complain as follows: arraylist_test.c:19:2: warning: format specifies type 'int' but the argument has type 'long' [-Wformat] arraylist_test.c:15:24: note: expanded from macro 'dump' printf("[%d] %d\n", ARRAYLIST_IDX(p, list), *p); \ ~~ ^~~~~~~~~~~~~~~~~~~~~~

They will be needed to implement 'got stage -p' and 'got revert -p', etc. Chunks stored in diff_result still need post-processing in order to be displayed as expected by diff_output_unidiff_chunk(). Exposing these functions allows API consumers to implement the same chunk merging loop as used internally by output_unidiff() and output_edscript(). (Perhaps, ideally, the public diff API would provide pre-merged chunks at some point in the future? Then this commit could probably be reverted.) Change return values from bool to int to avoid making stdbool.h a requirement for the public diff API.

Fixes test failures on OpenBSD due to unstable results of qsort if two or more elements are equal. Add a compat copy of OpenBSD mergesort(3) for Linux.

Not adding new tests since this behaviour is covered by tests in Got.

This uncovered a bug in diff_algo_none(), so let's keep it.

Now allocating patience specific data only when patience is going to be used. This may allow using forward-Myers more often, since the state size per line is significantly smaller. Patience instead allocates an array, puts it in the current diff_data, and also place a pointer of the current diff_data in the root diff_data (since each atom points to the root diff_data).

The idea was that for each diff box within the files, the atoms would have a backpointer to the current layer of diff_data (indicating the current section), but it is not actually needed to update the backpointer in each atom to the current diff_data. That is why the current code always points atom->d to the root diff_data for the entire file. Clarify by proper name. Constructs like atom->d->root->foo are redundant, just use atom->root->foo.

-p is traditionally used for "show which C function each change is in", so don't use it for choosing Patience. Instead add two options for using Patience, -P for only Patience and -Q to attempt forward-Myers first. Also add -T for a trivial diff (diff_algo_none).