<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Aug 21, 2022 at 9:12 AM Ray Gardner <<a href="mailto:raygard@gmail.com">raygard@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I guess I'll skip writing up an explanation of these algos then; I<br>
thought you were looking for a less "mathematical" explanation ("why<br>
can nobody explain what the old stuff is doing without pretending it's<br>
math instead of an algorithm?" "Doug McIlroy's old diff paper from<br>
1976 is still written in math-ese. It SEEMS to be describing very<br>
simple concepts but it's trying to explain them as if this is<br>
calculus, which it is not." etc.) But that's moot if you're going with<br>
what appears to be the old "look ahead a little for matching lines to<br>
re-sync on" heuristic diff method.<br></blockquote><div><br></div><div>(fwiw, i think such a document would be a useful thing to leave lying around on the internet ... someone will want it sooner or later :-) )</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Anyway, I applied your 1-or-2 line patch to the Aug. 8 attachment.c<br>
you posted and it still chokes on the two files I sent you (dif_old2.c<br>
and dif_new.c). So maybe you've made some other significant changes to<br>
that code, if it works for you? It appeared to be stuck in dump_hunk()<br>
but I didn't look any deeper.<br>
<br>
<br>
<br>
On Sat, Aug 20, 2022 at 4:49 AM Rob Landley <<a href="mailto:rob@landley.net" target="_blank">rob@landley.net</a>> wrote:<br>
><br>
> On 8/19/22 21:08, Ray Gardner wrote:<br>
> > Finally got subscribed here, thanks.<br>
><br>
> Yay!<br>
><br>
> > As I mentioned somewhere, I've been working on a diff.c that uses a<br>
> > longest common subsequence (LCS) algorithm. I've attached a version<br>
> > here. It handles only -u for now, only two files, and I think it does<br>
> > it correctly. But it's at least a proof of concept.<br>
><br>
> I've got an algorithm working, the part I've been reimplementing now (since the<br>
> block copied help text has convinced me not to use any of the previous<br>
> submission for potential licensing reasons) is all the directory traversal<br>
> stuff. I've read what posix had to say, and made it through a chunk of the diff<br>
> man page, and I'm adding --from-file support and so on that the previous one<br>
> didn't have. I'm also trying to fill out diff.tests to something meaningful.<br>
><br>
> My big hangup with this part was trying to figure out whether or not to use<br>
> lib/dirtree.c which was one of those "the two options are close enough there's<br>
> no clear winner" problems. (In academia the fighting is so vicious because the<br>
> stakes are so small.) The problem is dirtree isn't designed to traverse two<br>
> directories in parallel, and _making_ it do so wasn't really an improvement over<br>
> just writing a new one. (The reason cp/mv could get away with it is they don't<br>
> care what's in the target directory unless it collides, so they never do a<br>
> readdir() on dest. But diff has to provide "only in" messages, which means<br>
> actually doing a readdir() on dest, plus the stable output order requiring a<br>
> sort of the directory contents).<br>
><br>
> Doing new infrastructure that does its own readdir meant also reimplementing<br>
> things like dirtree_path(), which offended my aesthetic sensibilities but I got<br>
> over it eventually. :)<br>
><br>
> > This uses my modification of Kuo and Cross's modification of Hunt and<br>
> > Szymanski's LCS algorithm. I have read your (Rob's) posts regarding<br>
> > grokking how LCS algos work and the opacity of the technical papers. I<br>
> > am working on a blog post or two where I will try to explain the algos<br>
> > in a somewhat informal but convincing manner (I hope).<br>
><br>
> I posted my diff.c when I got an algorithm working. The endless loop was because<br>
> the hunk detection logic wasn't handling EOF correctly, a one line fix in<br>
> find_hunks():<br>
><br>
> // matching lines. Hunks can't overlap so first line of new hunk can't be<br>
> // within old hunk so shorter matching run than end+start won't break hunk.<br>
> while (!h1->done || !h2->done) {<br>
> - if (!h1->done && h1->len<h2->len) ii = back_search(start, h1, h2);<br>
> + if (!h1->done && (h2->done || h1->len<h2->len))<br>
> + ii = back_search(start, h1, h2);<br>
> else ii = back_search(start, h2, h1);<br>
> if (!ii) continue;<br>
><br>
> Ok, 2 lines because it went over 80 chars so I split it. :)<br>
><br>
> > But pending that, I thought I'd get this out to y'all to take a look<br>
> > at. It's standalone, not integrated into toybox. Just gcc diff.c may<br>
> > work.<br>
><br>
> So I tried to look at four diff algorithms before the one I posted (all of which<br>
> required loading in the entire file at once instead of a streaming approach that<br>
> only kept the current hunk in memory), and now you've done a fifth along the<br>
> same lines and want me to look at it.<br>
><br>
> Let me get diff.c finished and promoted (which may include support for things<br>
> like --ifdef) and then maybe I'll revisit this for diff -d support? (I still<br>
> haven't looked at pathological inputs that would drive my diff algorithm nuts; I<br>
> have a linux-fullhist git repository going back to 0.0.1 and I want to have my<br>
> algorithm diff every version in "git log" all the way back to make sure that<br>
> whatever output it produces run through my "patch" recreates the second tree.<br>
> That's my criteria to consider the new implementation load-bearing. Modulo I'm<br>
> not sure how "binary diff" works in here, and yes the linux git repo has some<br>
> binary files in it, )<br>
><br>
> Rob<br>
_______________________________________________<br>
Toybox mailing list<br>
<a href="mailto:Toybox@lists.landley.net" target="_blank">Toybox@lists.landley.net</a><br>
<a href="http://lists.landley.net/listinfo.cgi/toybox-landley.net" rel="noreferrer" target="_blank">http://lists.landley.net/listinfo.cgi/toybox-landley.net</a><br>
</blockquote></div></div>