Future of our regular expression code
As those who've been paying attention to it know, our regular expression
library is based on code originally developed by Henry Spencer and
contributed by him to the Tcl project. We adopted it out of Tcl in
2003. Henry intended to package the code as a standalone library as
well, but that never happened --- AFAICT, Henry dropped off the net
around 2002, and I have no idea what happened to him.
Since then, we've been acting as though the Tcl guys are upstream
maintainers for the regex code, but in point of fact there does not
appear to be anybody there with more than the first clue about that
code. This was brought home to me a few days ago when I started talking
to them about possible ways to fix the quantified-backrefs problem that
depesz recently complained of (which turns out to have been an open bug
in their tracker since 2005). As soon as I betrayed any indication of
knowing the difference between a DFA and an NFA, they offered me commit
privileges :-(. And they haven't fixed any other significant bugs in
the engine in years, either.
So I think it's time to face facts and accept that Tcl are not a useful
upstream for the regex code. And we can't just let it sit quietly,
because we have bugs to fix (at least the one) as well as enhancement
requests such as the nearby discussion about recognizing high Unicode
code points as letters.
A radical response to this would be to drop the Spencer regex engine and
use something else instead --- probably PCRE, because there are not all
that many alternatives out there. I do not care much for this idea
though. It would be a significant amount of work in itself, and there's
no real guarantee that PCRE will continue to be maintained either, and
there would be some user-visible compatibility issues because the regex
flavor is a bit different. A larger point is that it'd be a real shame
for the Spencer regex engine to die off, because it is in fact one of
the best pieces of regex technology on the planet. See Jeffrey Friedl's
"Mastering Regular Expressions" (O'Reilly) --- at least, that's what he
thought in the 2002 edition I have, and it's unlikely that things have
changed much.
So I'm feeling that we gotta suck it up and start acting like we are
the lead maintainers for this code, not just consumers.
Another possible long-term answer is to finish the work Henry never did,
that is make the code into a standalone library. That would make it
available to more projects and perhaps attract other people to help
maintain it. However, that looks like a lot of work too, with distant
and uncertain payoff.
Comments, other ideas?
regards, tom lane
On Sat, Feb 18, 2012 at 6:15 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
So I'm feeling that we gotta suck it up and start acting like we are
the lead maintainers for this code, not just consumers.
By "we", I take it you mean you personally?
There are many requests I might make for allocations of your time and
that wouldn't even be a lower priority item on such a list. Of course,
your time allocation is not my affair, so please take my words as a
suggestion and a compliment.
Do we have volunteers that might save Tom from taking on this task?
It's not something that requires too much knowledge and experience of
PostgreSQL, so is an easier task for a newcomer.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
* Simon Riggs (simon@2ndQuadrant.com) wrote:
On Sat, Feb 18, 2012 at 6:15 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
So I'm feeling that we gotta suck it up and start acting like we are
the lead maintainers for this code, not just consumers.By "we", I take it you mean you personally?
I'm pretty sure he meant the PG project, and I'd agree with him- we're
going to have to do it if no one else is. I suspect the Tcl folks will
be happy to look at incorporating anything we fix, if they can, but it
doesn't sound like they'll be able to help with fixing things much.
Do we have volunteers that might save Tom from taking on this task?
It's not something that requires too much knowledge and experience of
PostgreSQL, so is an easier task for a newcomer.
Sure, it doesn't require knowledge of PG, but I dare say there aren't
very many newcomers who are going to walk in knowing how to manage
complex regex code.. I haven't seen too many who can update gram.y,
much less make our regex code handle Unicode better. I'm all for
getting other people to help with the code, of course, but I wouldn't
hold my breath and leave existing bugs open on the hopes that someone's
gonna show up.
Thanks,
Stephen
Stephen Frost <sfrost@snowman.net> writes:
* Simon Riggs (simon@2ndQuadrant.com) wrote:
Do we have volunteers that might save Tom from taking on this task?
It's not something that requires too much knowledge and experience of
PostgreSQL, so is an easier task for a newcomer.
Sure, it doesn't require knowledge of PG, but I dare say there aren't
very many newcomers who are going to walk in knowing how to manage
complex regex code.. I haven't seen too many who can update gram.y,
much less make our regex code handle Unicode better. I'm all for
getting other people to help with the code, of course, but I wouldn't
hold my breath and leave existing bugs open on the hopes that someone's
gonna show up.
Yeah ... if you *don't* know the difference between a DFA and an NFA,
you're likely to find yourself in over your head. Having said that,
this is eminently learnable stuff and pretty self-contained, so somebody
who had the time and interest could make themselves into an expert in
a reasonable amount of time. I'm not really eager to become the
project's regex guru, but only because I have ninety-nine other things
to do not because I don't find it interesting. Right at the moment I'm
probably far enough up the learning curve that I can fix the backref
problem faster than anyone else, so I'm kind of inclined to go do that.
But I'd be entirely happy to let someone else become the lead hacker in
this area going forward. What we can't do is just pretend that it
doesn't need attention.
In the long run I do wish that Spencer's code would become a standalone
package and have more users than just us and Tcl, but that is definitely
work I don't have time for now. I think somebody would need to commit
significant amounts of time over multiple years to give it any real hope
of success.
One immediate consequence of deciding that we are lead maintainers and
not just consumers is that we should put in some regression tests,
instead of taking the attitude that the Tcl guys are in charge of that.
I have a head cold today and am not firing on enough cylinders to do
anything actually complicated, so I was thinking of spending the
afternoon transliterating the Tcl regex test cases into SQL as a
starting point.
regards, tom lane
On Sat, Feb 18, 2012 at 7:52 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
One immediate consequence of deciding that we are lead maintainers and
not just consumers is that we should put in some regression tests,
instead of taking the attitude that the Tcl guys are in charge of that.
I have a head cold today and am not firing on enough cylinders to do
anything actually complicated, so I was thinking of spending the
afternoon transliterating the Tcl regex test cases into SQL as a
starting point.
Having just had that brand of virus, I'd skip it and take the time
off, like I should have.
Translating the test cases is a great way in for a volunteer, so
please leave a few easy things to get people started on the road to
maintaining that.
--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
On Sat, Feb 18, 2012 at 21:04, Simon Riggs <simon@2ndquadrant.com> wrote:
On Sat, Feb 18, 2012 at 7:52 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
One immediate consequence of deciding that we are lead maintainers and
not just consumers is that we should put in some regression tests,
instead of taking the attitude that the Tcl guys are in charge of that.
I have a head cold today and am not firing on enough cylinders to do
anything actually complicated, so I was thinking of spending the
afternoon transliterating the Tcl regex test cases into SQL as a
starting point.Having just had that brand of virus, I'd skip it and take the time
off, like I should have.Translating the test cases is a great way in for a volunteer, so
please leave a few easy things to get people started on the road to
maintaining that.
I would be willing to have a go at translating test cases. I do not (yet)
have the C knowledge to maintain the regex code, though.
On 02/18/2012 02:25 PM, Stephen Frost wrote:
Do we have volunteers that might save Tom from taking on this task?
It's not something that requires too much knowledge and experience of
PostgreSQL, so is an easier task for a newcomer.Sure, it doesn't require knowledge of PG, but I dare say there aren't
very many newcomers who are going to walk in knowing how to manage
complex regex code.. I haven't seen too many who can update gram.y,
much less make our regex code handle Unicode better. I'm all for
getting other people to help with the code, of course, but I wouldn't
hold my breath and leave existing bugs open on the hopes that someone's
gonna show up.
Indeed, the number of people in the community who can hit the ground
running with this is probably vanishingly small, sadly. (I haven't
touched any formal DFA/NFA code in a couple of decades.)
cheers
andrew
Vik Reykja <vikreykja@gmail.com> writes:
On Sat, Feb 18, 2012 at 21:04, Simon Riggs <simon@2ndquadrant.com> wrote:
Translating the test cases is a great way in for a volunteer, so
please leave a few easy things to get people started on the road to
maintaining that.
I would be willing to have a go at translating test cases. I do not (yet)
have the C knowledge to maintain the regex code, though.
Sure, have at it. I was thinking that we should make a new regex.sql
test file for any cases that are locale-independent. If they have any
that are dependent on recognizing non-ASCII characters as letters,
we could perhaps drop those into collate.linux.utf8.sql --- note that
we might need my draft patch from yesterday before anything outside the
LATIN1 character set would pass.
regards, tom lane
Tom Lane <tgl@sss.pgh.pa.us> writes:
Yeah ... if you *don't* know the difference between a DFA and an NFA,
you're likely to find yourself in over your head. Having said that,
So, here's a paper I found very nice to get started into this subject:
http://swtch.com/~rsc/regexp/regexp1.html
If anyone's interested into becoming our PostgreSQL regexp hero and
still needs a good kicker, I would recommend starting here :)
I see this paper mention the regexp code from Plan9, which supports both
UTF8 and other muti-byte encodings, and is released as a library under
the MIT licence:
http://swtch.com/plan9port/unix/
Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support
Dimitri Fontaine <dimitri@2ndQuadrant.fr> writes:
Tom Lane <tgl@sss.pgh.pa.us> writes:
Yeah ... if you *don't* know the difference between a DFA and an NFA,
you're likely to find yourself in over your head. Having said that,
So, here's a paper I found very nice to get started into this subject:
http://swtch.com/~rsc/regexp/regexp1.html
Yeah, I just found that this afternoon myself; it's a great intro.
If you follow the whole sequence of papers (there are 4) you'll find out
that this guy built a new regexp engine for Google, and these papers are
basically introducing/defending its design. It turns out they've
released it under a BSD-ish license, so for about half a minute I was
thinking there might be a new contender for something we could adopt.
But there turn out to be at least two killer reasons why we won't:
* it's in C++ not C
* it doesn't support backrefs, as well as a few other features that
maybe aren't as interesting but still would represent compatibility
gotchas if they went away.
Too bad. But the papers are well worth reading. One thing I took away
from them is that it's possible to do capturing parens, though not
backrefs, without back-tracking. Spencer's code treats both of those
features as "messy" (ie, slow, because they force use of the NFA-style
backtracking search code). So there might be reason to reimplement
the parens-but-no-backrefs case using some ideas from these papers.
regards, tom lane
On Sun, Feb 19, 2012 at 1:55 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Dimitri Fontaine <dimitri@2ndQuadrant.fr> writes:
Tom Lane <tgl@sss.pgh.pa.us> writes:
Yeah ... if you *don't* know the difference between a DFA and an NFA,
you're likely to find yourself in over your head. Having said that,So, here's a paper I found very nice to get started into this subject:
http://swtch.com/~rsc/regexp/regexp1.htmlYeah, I just found that this afternoon myself; it's a great intro.
If you follow the whole sequence of papers (there are 4) you'll find out
that this guy built a new regexp engine for Google, and these papers are
basically introducing/defending its design. It turns out they've
released it under a BSD-ish license, so for about half a minute I was
thinking there might be a new contender for something we could adopt.
But there turn out to be at least two killer reasons why we won't:
* it's in C++ not C
* it doesn't support backrefs, as well as a few other features that
maybe aren't as interesting but still would represent compatibility
gotchas if they went away.
Another interesting library, technology-wise, is libtre:
http://laurikari.net/tre/about/
http://laurikari.net/tre/documentation/
NetBSD plans to replace the libc regex with it:
http://netbsd-soc.sourceforge.net/projects/widechar-regex/
http://groups.google.com/group/muc.lists.netbsd.current-users/browse_thread/thread/db5628e2e8f810e5/a99c368a6d22b6f8?lnk=gst&q=libtre#a99c368a6d22b6f8
Another useful project - AT&T regex tests:
http://www2.research.att.com/~gsf/testregex/
About our Spencer code - if we don't have resources (not called Tom)
to clean it up and make available as library (in short term - at least
to TCL folks) we should drop it. Because it means it's dead end,
however good it is.
--
marko
On Sat, Feb 18, 2012 at 7:24 PM, Marko Kreen <markokr@gmail.com> wrote:
About our Spencer code - if we don't have resources (not called Tom)
Is there anything that would be worth talking about directly with
Henry? He's in one of my circles of colleagues; had dinner with a
group that included him on Thursday.
--
When confronted by a difficult problem, solve it by reducing it to the
question, "How would the Lone Ranger handle this?"
Christopher Browne <cbbrowne@gmail.com> writes:
On Sat, Feb 18, 2012 at 7:24 PM, Marko Kreen <markokr@gmail.com> wrote:
About our Spencer code - if we don't have resources (not called Tom)
Is there anything that would be worth talking about directly with
Henry? He's in one of my circles of colleagues; had dinner with a
group that included him on Thursday.
Really!? I had about come to the conclusion he was dead, because he's
sure been damn invisible as far as I could find. Is he still interested
in what happens with his regex code, or willing to answer questions
about it?
regards, tom lane
On 19 February 2012 06:52, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Yeah ... if you *don't* know the difference between a DFA and an NFA,
you're likely to find yourself in over your head. Having said that,
this is eminently learnable stuff and pretty self-contained, so somebody
who had the time and interest could make themselves into an expert in
a reasonable amount of time.
I find myself in possession of both time and interest. I have to
admit up-front that I don't have experience with regex code, but I do
have some experience with parsers generally, and I'd like to think
some of that skillset would transfer to this problem. I also find
regexes fascinating and extremely useful, so learning more about them
will be no hardship.
I'd happily cede to an expert, should one appear, but otherwise I'm
all for moving the regex code into a discrete library, and I'm
volunteering to take a swing at it.
Cheers,
BJ
Brendan Jurd <direvus@gmail.com> writes:
On 19 February 2012 06:52, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Yeah ... if you *don't* know the difference between a DFA and an NFA,
you're likely to find yourself in over your head. �Having said that,
this is eminently learnable stuff and pretty self-contained, so somebody
who had the time and interest could make themselves into an expert in
a reasonable amount of time.
I find myself in possession of both time and interest. I have to
admit up-front that I don't have experience with regex code, but I do
have some experience with parsers generally, and I'd like to think
some of that skillset would transfer to this problem. I also find
regexes fascinating and extremely useful, so learning more about them
will be no hardship.
I'd happily cede to an expert, should one appear, but otherwise I'm
all for moving the regex code into a discrete library, and I'm
volunteering to take a swing at it.
That sounds great.
BTW, if you don't have it already, I'd highly recommend getting a copy
of Friedl's "Mastering Regular Expressions". It's aimed at users not
implementers, but there is a wealth of valuable context information in
there, as well as a really good not-too-technical overview of typical
implementation techniques for RE engines. You'd probably still want one
of the more academic presentations such as the dragon book for
reference, but I think Freidl's take on it is extremely useful.
regards, tom lane
On 19 February 2012 15:49, Tom Lane <tgl@sss.pgh.pa.us> wrote:
That sounds great.
BTW, if you don't have it already, I'd highly recommend getting a copy
of Friedl's "Mastering Regular Expressions". It's aimed at users not
implementers, but there is a wealth of valuable context information in
there, as well as a really good not-too-technical overview of typical
implementation techniques for RE engines. You'd probably still want one
of the more academic presentations such as the dragon book for
reference, but I think Freidl's take on it is extremely useful.
Thanks for the recommendations Tom. I've now got Friedl, and there's
a dead-tree copy of 'Compilers' making its gradual way to me (no
ebook).
I've also been reading the article series by Russ Cox linked upthread
-- it's good stuff.
Are you far enough into the backrefs bug that you'd prefer to see it
through, or would you like me to pick it up?
Cheers,
BJ
Brendan Jurd <direvus@gmail.com> writes:
Are you far enough into the backrefs bug that you'd prefer to see it
through, or would you like me to pick it up?
Actually, what I've been doing today is a brain dump. This code is
never going to be maintainable by anybody except its original author
without some internals documentation, so I've been trying to write
some based on what I've managed to reverse-engineer so far. It's
not very complete, but I do have some words about the DFA/NFA stuff,
which I will probably revise and fill in some more as I work on the
backref fix, because that's where that bug lives. I have also got
a bunch of text about the colormap management code, which I think
is interesting right now because that is what we are going to have
to fix if we want decent performance for Unicode \w and related
classes (cf the other current -hackers thread about regexes).
I was hoping to prevail on you to pick that part up as your first
project. I will commit what I've got in a few minutes --- look
for src/backend/regex/README in that commit. I encourage you to
add to that file as you figure stuff out. We could stand to upgrade
a lot of the code comments too, of course, but I think a narrative
description is pretty useful before diving into code.
regards, tom lane
On 20 February 2012 10:42, Tom Lane <tgl@sss.pgh.pa.us> wrote:
I have also got
a bunch of text about the colormap management code, which I think
is interesting right now because that is what we are going to have
to fix if we want decent performance for Unicode \w and related
classes (cf the other current -hackers thread about regexes).
I was hoping to prevail on you to pick that part up as your first
project. I will commit what I've got in a few minutes --- look
for src/backend/regex/README in that commit.
Okay, I've read through your README content, it was very helpful.
I'll now go chew through some more reading material and then start
studying our existing regex source code. Once I'm firing on all
cylinders with this stuff, I'll begin to tackle the colormap.
Cheers,
BJ
Tom,
I did a google search, and found the following:
http://www.arglist.com/regex/
Which states that Tcl uses the same library from Henry. Maybe someone
involved with that project would help explain the library? Also I noticed
at the url above is a few ports people did from Henry's code. I didn't
download and analyze their code, but maybe they have made some comments
that could help, or maybe have some improvements to the code..
Just a thought.. :)
Billy Earney
On Sun, Feb 19, 2012 at 5:42 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Show quoted text
Brendan Jurd <direvus@gmail.com> writes:
Are you far enough into the backrefs bug that you'd prefer to see it
through, or would you like me to pick it up?Actually, what I've been doing today is a brain dump. This code is
never going to be maintainable by anybody except its original author
without some internals documentation, so I've been trying to write
some based on what I've managed to reverse-engineer so far. It's
not very complete, but I do have some words about the DFA/NFA stuff,
which I will probably revise and fill in some more as I work on the
backref fix, because that's where that bug lives. I have also got
a bunch of text about the colormap management code, which I think
is interesting right now because that is what we are going to have
to fix if we want decent performance for Unicode \w and related
classes (cf the other current -hackers thread about regexes).
I was hoping to prevail on you to pick that part up as your first
project. I will commit what I've got in a few minutes --- look
for src/backend/regex/README in that commit. I encourage you to
add to that file as you figure stuff out. We could stand to upgrade
a lot of the code comments too, of course, but I think a narrative
description is pretty useful before diving into code.regards, tom lane
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Billy Earney <billy.earney@gmail.com> writes:
I did a google search, and found the following:
http://www.arglist.com/regex/
Hmm ... might be worth looking at those two pre-existing attempts at
making a standalone library from Henry's code, just to see what choices
they made.
Which states that Tcl uses the same library from Henry. Maybe someone
involved with that project would help explain the library?
Um ... did you see the head message in this thread?
regards, tom lane
