[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Chicken-hackers] [PATCH] Update irregex to new upstream release: 0.9.4,

From: Peter Bex
Subject: [Chicken-hackers] [PATCH] Update irregex to new upstream release: 0.9.4, and reduce differences
Date: Thu, 17 Dec 2015 22:12:01 +0100
User-agent: Mutt/1.5.21 (2010-09-15)

Hi all,

Caolan McMahon reported on IRC that (irregex-match "[a-z]{0,42}" "testing@")
would take about 2 minutes to find that there was no match.  This was due
to the translation of "a{3,6}" to aaaa?a?a?a?a?a?, which would result in
excessive backtracking caused by a combinatorial explosion: It would try
to match all permutations of the As in the pattern.  Even though the
first a is identical to, say, the fourth, it would still match them as
if they were not.

The fix is simple (though it took me a while to come up with a patch):
just try to match the As in sequence: if one A fails, the next will fail
as well.

In case you're wondering: the cset-contains? performance improvement I
posted in another thread should still be applied: it's still relevant and
I haven't come up with a sane way to do this portably.

I've also added a second patch to make the diff between upstream and our
own version smaller: I removed the %irregex-error custom procedure, which
was probably a remnant from a very old version of Irregex.  It was
overridden as a compiler macro to expand to "error" anyway, which is
also shipped with upstream irregex as a simple helper procedure for
Schemes that do not support it.  The definition is compatible with
CHICKEN's built-in version, so it's fine to just use it.

The diff still includes a change of using symbol names instead of strings
whereever the procedure name is passed as a first argument to error,
because it's converted to a 'location property on the 'exn condition.
I've kept this because it's a bit more user-friendly, even though it
looks like a gratuitous change when you're looking at the diff.


Attachment: 0001-Update-irregex-to-upstream-version-0.9.4.patch
Description: Text Data

Attachment: 0002-Reduce-difference-with-upstream-irregex.patch
Description: Text Data

Attachment: signature.asc
Description: Digital signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]