sed behaving strangely when -n and the delete command are combined

[Rob Landley]

On Thursday 09 July 2009 08:50:31 Denys Vlasenko wrote:
> > That said, this change isn't nearly complex enough to justify 250 lines
> > worth of changes:
> >
> >  editors/sed.c       |  462
> > ++++++++++++++++++++++++++--------------------------
> >  testsuite/sed.tests |   13 +
> >  2 files changed, 252 insertions(+), 223 deletions(-)
> >
> > I only looked through the first two pages of that patch, which seemed to
> > be full of random unrelated stuff, and then started doing range
> > comparisons that don't seem right.  But the way this patch is structured,
> > it's really hard to see what you actually changed and what's noise.
>
> Please find attached patch which has indentation change filtered out.

Analyzing sed behavior always puts me in a bad mood.  It's so fiddly...

Ok, let's see:

>--- busybox.4/editors/sed.c 2009-07-09 15:47:57.000000000 +0200
>+++ busybox.5/editors/sed.c 2009-06-30 19:19:15.000000000 +0200
>@@ -865,21 +865,23 @@ static void process_files(void)
>    /* Prime the pump */
>    next_line = get_next_line(&next_gets_char);
>
>-   /* go through every line in each file */
>+   /* Go through every line in each file */
>  again:
>    substituted = 0;
>
>    /* Advance to next line.  Stop if out of lines. */
>    pattern_space = next_line;
>-   if (!pattern_space) return;
>+   if (!pattern_space)
>+       return;
>    last_gets_char = next_gets_char;
>
>    /* Read one line in advance so we can act on the last line,
>     * the '$' address */
>    next_line = get_next_line(&next_gets_char);
>    linenum++;
>+
>+   /* For every line, go through all the commands */
>  restart:
>-   /* for every line, go through all the commands */
>    for (sed_cmd = G.sed_cmd_head.next; sed_cmd; sed_cmd = sed_cmd->next) {
>        int old_matched, matched;

So the first page of the patch is still nothing but white noise...

>@@ -893,35 +894,51 @@ static void process_files(void)
>
>            || (!sed_cmd->beg_line && !sed_cmd->end_line
>
>                && !sed_cmd->beg_match && !sed_cmd->end_match)
>            /* Or did we match the start of a numerical range? */
>-           || (sed_cmd->beg_line > 0 && (sed_cmd->beg_line == linenum))
>+           || (sed_cmd->beg_line > 0 && (sed_cmd->beg_line == linenum
>+                           /* "shadowed beginning" case: "1d;1,ENDp" - p
> still matches at line 2 +                            * even though 1d
> skipped line 1 which is a start line for p */

It's somewhat disturbing to have a comment inside a nested parenthetical.  The 
indentation gives no hints so it's a bit hard to track the structure here.

I note the comment could just be one line:

/* "1d;1,ENDp" should start matching at line 2. */

> +                          
> || (sed_cmd->end_line && sed_cmd->beg_line < linenum && sed_cmd->end_line
> >= linenum)

This is more complicated than it needs to be.

If you're going to slavishly copy what gnu does, you might want to run a few 
more tests to see what that actually is.  Specifically:

  echo -e "one\ntwo\nthree\nfour" | sed -ne '2d;2,1p'
  three

So the logic can be simplified: when your start is a number it triggers on the 
next line >= to that number.   Just change the match start to >=, and then 
disable numerical starting matches are disabled after the first hit.  Beyond 
that, you want to fall through like it was already doing to the normal match 
ending logic, which has had <= linenum since my days.

So you can get closer to the gnu behavior by changing the code _less_.  Which 
means you don't have to avoid snapshotting the line and continuing on to the 
"should we end the match now" logic.

Also, why do you discard the comment about snapshotting the line?  The 
ordering is funky, it has to happen _between_ the match start and match end 
tests, which is why I added a comment to point it out (after it got moved to 
the wrong place twice, anyway).

> >+                           || (sed_cmd->end_match &&
> sed_cmd->beg_line < linenum) +                       )
>+           )
>            /* Or does this line match our begin address regex? */
>
>            || (beg_match(sed_cmd, pattern_space))
>
>            /* Or did we match last line of input? */
>
>            || (sed_cmd->beg_line == -1 && next_line == NULL);
>
>-       /* Snapshot the value */
>-
>        matched = sed_cmd->in_match;
>
>-       /* Is this line the end of the current match? */
>+       //bb_error_msg("cmd:'%c' matched:%d beg_line:%d end_line:%d
> linenum:%d", +       //sed_cmd->cmd, matched, sed_cmd->beg_line,
> sed_cmd->end_line, linenum);

Why are you adding commented out code?  If somebody wants to add printf() 
lines to dump values, do you think they'll really have a hard time doing so in 
future?  Does cluttering up the place with dead code make it more readable?

>+       /* Is this line the end of the current match? */
>        if (matched) {
>-           sed_cmd->in_match = !(
>+           int n = (
>                /* has the ending line come, or is this a single address
> command? */
> -               (sed_cmd->end_line ?
>+               sed_cmd->end_line ?
>                    sed_cmd->end_line == -1 ?
>                        !next_line
>
>                        : (sed_cmd->end_line <= linenum)
>                    :
>                    : !sed_cmd->end_match
>
>-               )
>+               );

I think this is more random cosmetic changes mixed in with the functional 
ones?  Except for not setting in_match immediately, which I think is actually 
a bad thing.

>+           if (!n) {
>                /* or does this line matches our last address regex */
>-               || (sed_cmd->end_match && old_matched
>+               n = (sed_cmd->end_match
>+                    && old_matched
>                     && (regexec(sed_cmd->end_match,
>-                                pattern_space, 0, NULL, 0) == 0))
>+                                pattern_space, 0, NULL, 0) == 0)
>            );
>+               if (n && sed_cmd->beg_line > 0) {
>+                   /* Once matched, "n,regex" range is dead, disabling it
> */ +                   regfree(sed_cmd->end_match);
>+                   free(sed_cmd->end_match);
>+                   sed_cmd->end_match = NULL;
>+               }
>+           }
>+           sed_cmd->in_match = !n;
>        }

Ok, buried in the random wordwrapping changes, you're now calling regfree in 
the middle of a sed, which seems way overkill.

If we're in a match, and beg_line > 0, set beg_line = -1.  That's all you need 
to do to prevent the match from triggering again after we end it.  You can 
even do that test every time, it's small and simple and really cheap, happens 
totally in L1 cache, and more or less parallelizes away on a modern processor 
with multiple execution cores.

>-       /* Skip blocks of commands we didn't match. */
>+       /* Skip blocks of commands we didn't match */
>        if (sed_cmd->cmd == '{') {
>            if (sed_cmd->invert ? matched : !matched) {
>                while (sed_cmd->cmd != '}') {
>@@ -934,7 +951,9 @@ static void process_files(void)
>        }
>

Noise...

>        /* Okay, so did this line match? */
>-       if (sed_cmd->invert ? !matched : matched) {
>+       if (sed_cmd->invert ? matched : !matched)
>+           continue; /* no */
>+

Um, not noise.  This is, in fact, a functional change totally unrelated to the 
rest of the patch of the kind that tends to cause subtle bugs, which I used to 
be very sensitive to in sed because it's so complicated and fiddly.

You left this change in, but didn't change the indentation of everything that 
used to be a block, so the indentation is now misleading.  (I realize this was 
probably fallout from trying to simplify the patch into something other people 
could read, but wouldn't it have been better roll back the above hunk as well 
when doing that?  I'm all for this kind of cleanup, but if something breaks in 
sed and I bisect it to this commit, it's headache time...)

On an unrelated note, instead of adding a comment "no" perhaps it would be 
better to change the comment before to "continue if this line didn't match"?

I believe the rest of the changes to this file are more white noise unrelated 
to the bug at hand.

Rob
-- 
Latency is more important than throughput. It's that simple. - Linus Torvalds