GNU bug report logs - #33249
[PATCH] grep: grouping of patterns including back reference

Previous Next

Full log

Message #22 received at 33249-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 33249-done <at> debbugs.gnu.org
Subject: Re: bug#33249: [PATCH] grep: grouping of patterns including back
 reference
Date: Sun, 22 Dec 2019 16:57:12 -0800

[Message part 1 (text/plain, inline)]

On 11/3/18 9:25 PM, Norihiro Tanaka wrote:

>   $ seq -f '%040g' 0 9999 | sed '1s/$/\\(0\\)\\1/' >pat

Thanks for the test case and sorry about the delay. And thanks for spotting the
speedup opportunity. I found a few problems with the proposed patch, though:

> +        if (keys[1] == '\\')
> +          keys++;

This mishandles the case where the input byte sequence contains '\', '\', '1'
where the first '\' is the last byte of a multibyte character. Such a byte
sequence can contain backreferences but the function will say it doesn't.

> +      if (backref && prev < p)
> +        {
> +          len = p - prev;
> +          buf = xrealloc (buf, (buflen + len) * sizeof *buf);
> +          memcpy (buf + buflen, p, len);
> +          buflen += len;
> +        }

This seems to have three problems. First, the memcpy copies from P, but it
should copy from PREV. Second, this code assigns to LEN, which breaks a later
use of LEN. Third, if there are many patterns with backreferences, repeated use
of realloc will have O(N**2) behavior.

> +      for (size_t i = 0; i < dc->pcount; i++)
> +        dc->patterns[i + 1] = dc->patterns[i];

This copies dc->patterns[0] to the later values in that array, when a memmove
was intended.

So, after installing the patch, I immediately installed the attached patch,
which should address the abovementioned issues.

Thanks again. You did the hard work - I merely proofread it.

[0001-grep-fix-some-bugs-in-pattern-grouping-speedup.patch (text/x-patch, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.