[Toybox] pathological case in sed s///g

[Rob Landley]

On 5/3/19 1:56 PM, Rob Landley wrote:
> On 5/3/19 1:05 PM, enh wrote:
> But yeah, the new pessimal case after the change I'm making now would be a
> megabyte of xyxyxyxy with 's/xy/x/g' _THAT_ would need the one output buffer
> thing...

And it can be avoided by an in-place copy that remembers "last gap" and doesn't
copy trailing data until the _next_ hit (or we confirm there's no hit) so we
know how much of the skipped data is "confirmed" and only copy it once we know
we're keeping it.

So every kept byte is only copied once, and it can still be done in place for
the shrinking case. (You'll have to realloc when you expand, but that's probably
unavoidable...)

Rob