Commit Briefs

4873aa776d Neels Hofmeyr

fix myers divide: properly trigger division on single midpoints (neels/wip3)


119e506814 Neels Hofmeyr

add test012

test010 has a weird failure to find a good diff. This new test, when setting the permitted_state_size = 100, gives a shorter failure that test010, to allow easier debugging.



4c42e83522 Neels Hofmeyr

fix diff_algo_myers_divide

When forwards and backwards traversals meet, the endpoints of the mid-snake are not the two points in kd_forward and kd_backward, but rather the section that was slid (if any) of the current forward/backward traversal only. For example: o-o-o | | o A | \ o o \ M |\ o o-o-o | | | o o X \ o \ o \ o The backward traversal reached M from the bottom and slid upwards. The forward traversal already reached X, which is not a straight line from M anymore, so picking a mid-snake from M to X would yield a mistake. The correct mid-snake is between M and A. M is where the bottom traversal hit the diagonal that the forwards traversal has already passed, and A is what it reaches when sliding up identical lines.


223979a920 Neels Hofmeyr

debug: myers graph dump tweaks

In debug output: fix some indents, fix printing of max state size, in myers graph, limit x axis labels to 2 digits, print colored markers of current myers graph positions, also print myers-divide positions in myers graph.


0ea9501aa0 Neels Hofmeyr

.gitignore: gmon.out


165321bcd5 Neels Hofmeyr

comment tweak



2ddc199c9d Neels Hofmeyr

add test010, test011


c13c580d7b Neels Hofmeyr

Only print (unified) header in unified format.


Branches

Tags

This repository contains no tags

Tree

.gitignorecommits | blame
GNUmakefilecommits | blame
LICENCEcommits | blame
READMEcommits | blame
compat/
diff/
diff-version.mkcommits | blame
include/
lib/
man/
test/

README

This is a collection of diff algorithms, to test various combinations.

The initial aim was to provide a faster diff implementation for got
(gameoftrees.org) with a BSD license, at the u2k20 OpenBSD hackathon.
A side effect could be improving OpenBSD's /usr/bin/diff utility.

At the time of writing, this is little more than a playground / benchmark basis
/ diff algorithm analysis platform. What could be done:
- add profiling and test series to rate diff algorithm combinations.
- interface with / merge into got.

The Myers and Patience Diff algorithm implementations found here are based on
the explanations found in these blog post series:
  https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
and
  https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ ff.
-- possibly the single most comprehensive explanations of these algorithms.
Many thanks for this valuable door opener!
The source code itself is not based on the code found in those blogs, but
written from scratch with the knowledge gained.

Compile:
  OpenBSD:
    make -C diff
  Linux:
    make -f linux_Makefile -C diff

Test:
  make -C test/