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

[enh]

On Fri, May 3, 2019 at 11:59 AM Rob Landley <rob at landley.net> wrote:
>
> 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.

yeah, that's what i meant by only ensuring that the first n characters
are right.

> 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