<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Jul 15, 2022 at 9:34 AM Rob Landley <<a href="mailto:rob@landley.net">rob@landley.net</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">On 7/14/22 18:53, enh wrote:<br>
> On Wed, Jul 13, 2022 at 11:58 PM Rob Landley <<a href="mailto:rob@landley.net" target="_blank">rob@landley.net</a><br>
> <mailto:<a href="mailto:rob@landley.net" target="_blank">rob@landley.net</a>>> wrote:<br>
> <br>
> On 7/12/22 19:13, enh via Toybox wrote:<br>
> > so.. --transform works (though it confused people that it's not in the --help<br>
> > output; they didn't know that there's a --xform synonym),<br>
> <br>
> Well, it doesn't FULLY work yet: those trailing type indicators aren't in yet. I<br>
> have a todo thingy for it and think I know how I want to handle it now (sed<br>
> --tartransform enabling extra s///X trailing selectors, making the result NULL<br>
> terminated, disabling NULL output repacement so it doesn't get out of sync, and<br>
> stripping a file type indicator character from the start of each input line; yes<br>
> this is the correct use for a --longopt, internal nonsense one program passes to<br>
> another which no human should ever type...)<br>
> <br>
> yeah, no worries --- sufficient unto the day are the bugs that are currently<br>
> getting in people's way :-)<br>
<br>
Yeah but August 6 is 3 months from the previous release and I'd like to do that<br>
on a more regular schedule (modulo maybe slipping a bit to sync up with kernel<br>
releases for mkroot), meaning I want to finish this properly soonish. :)<br>
<br>
I have a half dozen open cans of worms right now... dd, sh, mkroot walkthrough,<br>
diff, tar --transform, a redo of lib/passwd.c and everything depending on it,<br>
and in file.c:<br>
<br>
+ * TODO: XZ, JPEG size, dpkg.deb, rpm, mp3, odt, mp4, iso<br>
+ * MBR boot sector (partition X: startsector %d, %d sectors;)<br>
+ * word (.docx: Word 2007+), excel<br></blockquote><div><br></div><div>you shouldn't do those yourself --- you should make each of those a separate bug on github with a "help wanted" or "starter project" label, and then next time you have someone asking "hey, is there something i can look at?", you have stuff ready and waiting...</div><div><br></div><div>(not that you can 100% trust me not to do some of those when i've had a week when i didn't get to write even a line of code and i'm looking for something to do. but i'm trying to _stop_ doing all the easy little pieces myself at work for similar reasons!)</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">
Trying to close tabs for a release. :)<br>
<br>
> And the streaming approach does not care at ALL about the size of the _file_.<br>
> You can feed it gigabytes of input and for the matching sections it's going<br>
> read/compare/discard cycling through three trailing lines of context so it can<br>
> start a new hunk when it sees a difference...<br>
> <br>
> I strongly suspect there are pathological inputs that break this, or else why<br>
> would all these guys have done the complicated "read the whole file in at once"<br>
> approach in the first place? But I can't find what those inputs ARE. My real<br>
> problem here is a shortage of good TEST CASES...<br>
> <br>
> (i know nothing useful about diff, other than where to find the pdf of the<br>
> original paper :-) )<br>
<br>
Neither did I at the start of this mess. Alas, I've read that paper through<br>
twice and have not managed to turn their explanation into pseudo-code, and<br>
that's WITH an implementation in front of me. (No guarantee that implementation<br>
is what the paper describes, of course...)<br>
<br>
There are two main schools of programming: the burned out ex-mathematicians and<br>
ascended plumbers. I am firmly in the plumber camp, water wheels driving<br>
clockwork make sense to me. I got a math minor for the same reason an acrophobic<br>
person would go skydiving (I refused to be beaten by it), and can usually<br>
translate from mathematician-speak to plumber-speak, but this one's being stroppy.<br>
<br>
(I've met plenty of math-side programmers and generally pair program with them<br>
quite well. They're always disgusted when I pile up overlapping heuristics to<br>
cover the entire input space, but I'm very good at getting them unblocked when<br>
they're blocked because I've basically never NOT got a way to do whatever it is.<br>
I have a black belt in disgusting solutions, I can show you the Wrong Way To Do<br>
It whatever it is, and then we clean it up from there.<br>
<br>
I can pull apart what the current code is doing but there's four different<br>
algorithms in play, and I do NOT understand why they didn't just do the simple<br>
thing... which is sort of a fifth? Except I think it's a subset of the N^2 one,<br>
except it's N^2 on hunk size not file size if you do it right, which means "big<br>
enough to hurt" should almost never come up?<br>
<br>
Stream forward until you hit a diff, and then accumulate lines from each file<br>
one at a time scanning BACKWARDS in the other file to find matching lines (where<br>
does new last line of file 2 match in the list-since-difference of file1), and<br>
when you find -U *2 lines of match you've ended the hunk. Flush what you've seen<br>
(keeping the usual three lines of starting context) and move forward again as<br>
matched. This usually leaves unconsumed lines in the other file (sometimes ALL<br>
of what we've loaded from one file is unconsumed, that happens when you add or<br>
remove a single line in isolation for example) but you just need to feed those<br>
back in as "new" lines to the search algorithm...<br>
<br>
Yeah it's an N^2 search algorithm but what's the biggest hunk you've ever seen,<br>
200 lines? 1000? Modern hardware doing N^2 search over 1000 lines isn't going to<br>
break stride. The INPUT FILE size doesn't matter, except as a theoretical bound<br>
on the upper size of the hunk if you diff two completely unrelated files, but<br>
optimizing for that case seems silly?<br></blockquote><div><br></div><div>aye, though -- like you -- i assume that's the kind of pathological case they were thinking of. (because although it never happens "for real", it happens interactively, and that's probably when people are most sensitive to speed.) i don't remember seeing a single hunk more than tens of lines (except the other pathological case of "new file"). </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, that's the rathole I'm going down there. If it doesn't work I go back to<br>
the other thing, but this SHOULD be tiny and simple and basically an inverse of<br>
the patch.c I wrote way back when. AND it means you don't have to special case<br>
FIFO input and stuff because it doesn't have to be seekable, you're doing<br>
xgetline() in a loop...<br>
<br>
> > but in the meantime<br>
> > the kernel build script now uses --null with<br>
> ><br>
> -T: <a href="https://cs.android.com/android/kernel/superproject/+/common-android-mainline:build/kernel/build.sh;l=964" rel="noreferrer" target="_blank">https://cs.android.com/android/kernel/superproject/+/common-android-mainline:build/kernel/build.sh;l=964</a><br>
> <<a href="https://cs.android.com/android/kernel/superproject/+/common-android-mainline:build/kernel/build.sh;l=964" rel="noreferrer" target="_blank">https://cs.android.com/android/kernel/superproject/+/common-android-mainline:build/kernel/build.sh;l=964</a>><br>
> ><br>
> <<a href="https://cs.android.com/android/kernel/superproject/+/common-android-mainline:build/kernel/build.sh;l=964" rel="noreferrer" target="_blank">https://cs.android.com/android/kernel/superproject/+/common-android-mainline:build/kernel/build.sh;l=964</a><br>
> <<a href="https://cs.android.com/android/kernel/superproject/+/common-android-mainline:build/kernel/build.sh;l=964" rel="noreferrer" target="_blank">https://cs.android.com/android/kernel/superproject/+/common-android-mainline:build/kernel/build.sh;l=964</a>>><br>
> ><br>
> > i think implementing that is a sub-line change here...<br>
> ><br>
> > for (;TT.T; TT.T = TT.T->next) do_lines(xopenro(TT.T->arg), '\n', do_XT);<br>
> <br>
> What does this... ah, another null termination variant.<br>
> <br>
> The man page says "subsequent". Affecting _subsequent_ -T. So technically, you<br>
> could have:<br>
> <br>
> tar -T file-with-newlines.txt --null file-with-nulls.txt<br>
> <br>
> Which lib/args.c fundamentally can't cope with because all command line<br>
> arguments get processed before the command's main gets called. There's a similar<br>
> issue in sed.c:<br>
> <br>
> <a href="https://github.com/landley/toybox/blob/0.8.7/toys/posix/sed.c#L1009" rel="noreferrer" target="_blank">https://github.com/landley/toybox/blob/0.8.7/toys/posix/sed.c#L1009</a><br>
> <<a href="https://github.com/landley/toybox/blob/0.8.7/toys/posix/sed.c#L1009" rel="noreferrer" target="_blank">https://github.com/landley/toybox/blob/0.8.7/toys/posix/sed.c#L1009</a>><br>
> <br>
> > ...but i'm assuming you'd also want to add --no-null (last one wins),<br>
> <br>
> Yeah, modulo it still won't help the sequencing issue above. <br>
> <br>
> in a sense, it makes it worse --- they explicitly document that you can have<br>
> stuff like `--null -T nulls --no-null -T newlines`. and yet it's only the -T<br>
> file. not the -X file. (i mean, i get YAGNI, but there's an argument for<br>
> orthogonality, and personally i'd put "--null should work with all file lists"<br>
> over "i should be able to alternate between nulls and newlines if i want".)<br>
<br>
Sigh. I do know HOW to make that work, it's just... really ugly:<br>
<br>
Have --null and --no-null be two separate flags. If EITHER is set, iterate<br>
through toys.argv (which is the raw unparsed command line saved for exactly this<br>
sort of nonsense) to find the "--null" and "--no-null" entries in there, and the<br>
-T entries (which are single dash then any "T" in the resulting string) so you<br>
can count through the collected arg_list and annotate them appropriately.<br>
<br>
Note: this approach will be thrown off if you have a file argument named --null<br>
or -T and I'm willing to call that pilot error in this instance. (Although<br>
--null -T --no-null would actually do what you want, it would just screw up<br>
SUBSEQUENT arguments, if any. And the failure wouldn't be a segfault, it would<br>
be a -T entry parsed in the wrong terminator mode, which is not the end of the<br>
world.)<br>
<br>
> But as with<br>
> "truncate -s 8G" not working on 32 bits (because # parses into a long), there<br>
> are some corner cases in the plumbing that I have TODO items about but the fix<br>
> is uglier than the problem until somebody comes to me with a real world bug it<br>
> causes...<br>
> <br>
> i'm interpreting this as a "will accept patch for just --null [that affects all<br>
> -Ts, not just following ones], since that's all anyone wants right now"...<br>
<br>
I was about to ask if you wanted to write it or if I should do it. :)<br>
<br>
> sent!<br>
<br>
And apparently eaten by gmail's spam filter? Yes, that's where it was. (Thanks<br>
gmail, you are EATING MESSAGES ACTUALLY COMING FROM <a href="http://GOOGLE.COM" rel="noreferrer" target="_blank">GOOGLE.COM</a>. Again.)<br>
<br>
But now that I've gone "well here's the 80/20 solution to handling mode shifts",<br>
I'm tempted to code that up instead. Lemme see if I get to it this weekend, if<br>
not I owe you this applied before monday.<br></blockquote><div><br></div><div>sgtm. i've been trying to stop committing things on fridays, so monday's the earliest i'd be giving the kernel folks a new prebuilt anyway :-)</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">
Thanks,<br>
<br>
Rob<br>
</blockquote></div></div>