[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#33249: [PATCH] grep: grouping of patterns including back reference
From: |
Paul Eggert |
Subject: |
bug#33249: [PATCH] grep: grouping of patterns including back reference |
Date: |
Sun, 22 Dec 2019 16:57:12 -0800 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.2.2 |
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
Description: Text Data
- bug#33249: [PATCH] grep: grouping of patterns including back reference,
Paul Eggert <=