On Mon, Feb 14, 2022 at 03:58:49PM -0600, Nick Timkovich wrote:

While definitely not as bad and not as likely as SQL injection, I think the possibility of regex DoS is totally missing in the stdlib re docs. Should there be something added there about if you need to put user input into an expression, best practice is to re.escape it?

That doesn't help you when you wish to allow the user to specify a regex as the search term. -- Steve

How embarassing... I apologize for all the signature garbage at the end of my message.

On Mon, Feb 14, 2022 at 05:13:38PM -0600, Tim Peters wrote:

An interesting lesson nobody wants to learn: the original major string-processing language, SNOBOL, had powerful pattern matching but no regexps. Griswold's more modern successor language, Icon, found no reason to change that.

I've been interested in the existence of SNOBOL string scanning for a long time, but I know very little about it. How does it differ from regexes, and why have programming languages pretty much standardised on regexes rather than other forms of string matching?

Naive regexps are both clumsy and prone to bad timing in many tasks that "should be" very easy to express. For example, "now match up to the next occurrence of 'X'". In SNOBOL and Icon, that's trivial. 75% of regexp users will write ".*X", with scant understanding that it may match waaaay more than they intended.

Indeed, I've been bitten by that many times :-)

Another 20% will write ".*?X", with scant understanding that may extend beyond _just_ "the next" X in some cases.

But this surprises me. Do you have an example?

That leaves the happy 5% who write "[^X]*X", which finally says what they intended from the start.

Doesn't that only work if X is literally a single character?

...

...

import re string = "This is some spam and extra spam." re.search('[^spam]*spam', string) <re.Match object; span=(11, 17), match='e spam'>

Whereas this seems to do what I expected:

...

...

re.search('.*?spam', string) <re.Match object; span=(0, 17), match='This is some spam'>

-- Steve

[Tim]

...

...

That leaves the happy 5% who write "[^X]*X", which finally says what they intended from the start.

[Steven]

...

Doesn't that only work if X is literally a single character?

RIght. It was an examp[e, not a meta-example. Even for a _single character_, "match up to the next, but never more or less than that" is a puzzle for most regexp users. [Chris]

Yes, but if X is actually "spam", then you can probably do other assertions to guarantee the right match. It gets pretty clunky though.

Assertions aren't needed, but it is nightmarish to get right. (|[^s]|s(|[^p]|p(|[^a]|a(|[^m]))))*spam The "spam" at the end is the only obvious part ;-) Before then, we match 0 or more instances of nothing or not 's' or 's' followed by nothing or not 'p' or 'p' followed by nothing or not 'a' or 'a' followed by nothing or not 'm' "spam" itself can't get through that maze, so backtracking into it after its first match can't consume the matched "spam" to find a later one. In SNOBOL, as I recall, it could be spelled ARB "spam" FENCE Those are all pattern objects, and infix whitespace is a binary pattern catenation operator. ARB is a builtin pattern that matches the empty string at first, and extends what it matches by one character each time it's backtracked into. "spam" matches the obvious string. Then FENCE is a builtin pattern that matches an empty string, but acts as a backtracking barrier: if the overall match attempt fails, backtracking will not move "to the left" of FENCE. So, here, ARB will not get a chance to consume more characters after the leftmost "spam" is found.

[Tim]

...

In SNOBOL, as I recall, it could be spelled

ARB "spam" FENCE

[Chris]

Ah, so that's a bit more complicated than the "no-backtracking" parsing style of REXX and scanf.

Oh, a lot more complex. In SNOBOL, arbitrary computation can be performed at any point in pattern matching.. Yet _simple_ things are simple to say. Going back to the original one-letter "find the leftmost 'x' after the current point" is just BREAK('X') 'X' BREAK is a builtin function that returns a pattern that consumes all the characters until the first occurrence of one of the letters in its argument. If it's backed up into via backtracking, it fails: the shortest string is the only one it will consume. If you want something fancier, fine - you can code anything you like. For example, here's a pattern object (BAL) that matches the longest non-empty substring balanced with respect to parentheses: BALEXP = NOTANY('()') '(' ARBNO( *BALEXP) ')' BAL = BALEXP ARBNO(BALEXP) ARBNO is akin to a regexp .*? quantifier. The '*' in front of BALEXP in the first line tells SNOBOL to delay evaluating BALEXP until the pattern runs; at the time BALEXP is _defined_ by that line, BALEXP isn't yet bound to anything useful.

Does this guarantee anything about performance, or is it primarily to allow you to write patterns that can't mismatch strings?

They were inventing "pattern matching" in the 1960s. and were looking for expressive notations that were easy for experts to use. Regular expressions were much more of theoretical interest at the time, and offered far feebler abilities than SNOBOL's pattern abilities anyway. It's still interesting to me that they settled on a relatively "wordy" notation, wh\ch is pretty easy to pick up. This is perhaps because regexps are so feeble in comparison that they allowed proving mountains of properties, so a hyper-concise notation for them was invented to make publishing long-winded proofs possible ;-) But while SNOBOL was wildly inventive for its time, it was always intended to be used "to get real work done". Note too that potential backtracking isn't hiding in notation: it's quite explicit in names like ARB and ARBNO, and, of course, in pattern alternation (the infix binary "|" operator). Most builtin pattern functions and objects in SNOBOL are "one and done" (they match or they don't, and fail if backtracked into). Want a string of digits? SPAN('0123456789'). LIke a regexp's \d+, but will _only_ match the longest string of digits starting at the current point. The possibility for backtracking at the _lexical_ level is almost always a misfeature. Which didn't matter in the seminal lex+yacc scheme. yacc consumed the tokens lex's regexps produced, and if yacc failed to match the grammar lex didn't go on to try a different way of tokenizing. In effect, \d+ in lex acted like SNOBOL's SPAN. regexps didn['t manage the transition from "a tool" to "a solution" gracefully ;-)

On Tue, Feb 15, 2022 at 05:39:33AM -0600, Tim Peters wrote:

([^s]|s(?!pam))*spam

Bingo. That pattern is easy enough to understand

You and I have very different definitions of the word "easy" :-)

(if not to invent the first time): we can chew up a character if it's not an "s", or if it is an "s" but one _not_ followed immediately by "pam".

It is times like this that I am reminded why I prefer to just call string.find("spam") :-) -- Steve

On Wed, Feb 16, 2022 at 01:02:44AM +1100, Chris Angelico wrote:

Yeah, regexes always look terrible when they're used for simple examples :) But try matching a line that has (somewhere in it) the word "spam", then whitespace, then a number (or if you prefer: then a sequence of ASCII digits). It's easy to write "spam\s+[0-9]+"

After this thread, I no longer trust that "easy" regexes will do what they "obviously" look like they should do :-( I'm not trying to be funny or snarky. I *thought* I had a reasonable understanding of regexes, and now I have learned that I don't, and that the regexes I've been writing don't do what I thought they did, and presumedly the only reason they haven't blown up in my face (either performance-wise, or the wrong output) is blind luck. Now I have *three* problems :-( -- Steve

[Steven D'Aprano <steve@pearwood.info>]

After this thread, I no longer trust that "easy" regexes will do what they "obviously" look like they should do :-(

I'm not trying to be funny or snarky. I *thought* I had a reasonable understanding of regexes, and now I have learned that I don't, and that the regexes I've been writing don't do what I thought they did, and presumedly the only reason they haven't blown up in my face (either performance-wise, or the wrong output) is blind luck.

Reading Friedl's book is a cure for the confusion, but not for the angst ;-) I believe the single most practical addition in recent decades has been the introduction of "possessive quantifiers" This is a variant of the "greedy" quantifiers that does what most people at the start _believe_ they do: one-and-done. After its initial match, backtracking into it fails. So, e.g., \s++ matches the longest string of whitespace at the time, period. Why "++"? Regexps ;-) It's essentially gibberish syntax that previously didn't have a sensible meaning. For example,

...

...

regex.search("^x+[a-z]{4}k", "xxxxxk") <regex.Match object; span=(0, 6), match='xxxxxk'>

is what we're used to if we're paying attention: sucking up as many x's as possible fails to match (there's nothing for [a-z]{4} to match except the trailing "k"). But we keep backtracking into it, trying to match one less "x" at a time, until [a-z]{4} finally matches the rightmost 4 x's. But make it possessive and the match as a whole fails right away:

...

...

regex.search("^x++[a-z]{4}k", "xxxxxk")

++ refuses to give back any of what it matched the first time. At this point there are probably more regexp engines that support this feature than don't. Python's re does not, but the regex extension does., Cutting unwanted chances for backtracking greatly cuts the chance of stumbling into timing disasters. Where does that leave Python:? Pretty much aging itself into obsolescence. Regexps keep "evolving", it appears Fredrik lost interest in keeping up long before he died, and nobody else has stepped up. regex _has_ kept up, but isn't in the core. So "install regex" is ever more the best advice. Note that just slamming possessive quantifiers into CPython's engine isn't a good approach for more than just the obvious reasons: possessive quantifiers are themselves just syntax sugar (or chili peppers) for one instance of a more general new feature, "atomic groups". Another that's all but a de facto industry standard now, which Python's re doesn't support (but regex does). Putting just part of that in is half-assed.

Now I have *three* problems :-(

You're quite welcome ;-)

On 2022-02-16 02:11, Chris Angelico wrote:

On Wed, 16 Feb 2022 at 12:56, Tim Peters <tim.peters@gmail.com> wrote:

...

Regexps keep "evolving"...

Once upon a time, a "regular expression" was a regular grammar. That is no longer the case.

Once upon a time, a regular expression could be broadly compatible with multiple different parser engines. That is being constantly eroded.

So far, I think they still count as expressions. That's about all we can depend on.

Is there any sort of standardization of regexp syntax and semantics, or does everyone just extend it in their own directions, borrowing ideas from each other to give some not-always-false assurance of compatibility?

The only regex standard I know of is the POSIX standard, but I don't know of a common implementation that follows it. Most tend to follow Perl, although Perl borrowed named groups from Python, though with a slightly different syntax ("(?<name>...)" instead of "(?P<name>...)").

[Chris Angelico <rosuav@gmail.com>]

Is there any sort of standardization of regexp syntax and semantics,

Sure. "The nice thing about standards is that you have so many to choose from" ;-) For example, POSIX defines a regexp flavor so it can specify what things like grep do. The ECMAScruot standard defines its own standard, ditto Java, etc.

or does everyone just extend it in their own directions, borrowing ideas from each other to give some not-always-false assurance of compatibility?

In real life, everyone strives to copy what Perl does, because regexps are ubiquitous in Perl and Larry Wall worked hard at the time to put in every useful regexp feature everyone else already had, but with more uniform syntax. Perl's love of regexps strikes me as clinically pathological, but that doesn't diminish my respect for the relative sanity Perl brought to this area. There's a little bit flowing _into_ Perl too. An example close to my heart: Guido and I obtained Larry's promise that he'd never use a (?P prefix, so that Python could use that for its own purposes. Which amounted to introducing the concept of named groups. Which Perl in turn later adopted - although Perl dropped the "P" for named groups. Ah - I see MRAB replied while I was typing this, saying much the same. But I'm worider, so I won't waste the eff\ort ;-)

[Tim, on trying to match only the next instance of "spam"]

,,, It's actually far easier if assertions are used, and I'm too old to bother trying to repair the non-assertion mess:

([^s]|s(?!pam))*spam

Since then, Serhiy rehabilitated an old patch to add "atomic groups" and "possessive quantifiers" to CPython's `re`, and merged it today. So in 3.11, you'll be able to do the far easier: (?>.*?spam) instead. (?>,,,) delimits an "atomic group", and `...` can be any regexp. The group is non-capturing. `...` is matched in the normal way, but with a twist: _after_ it matches (if it ever does), it's done. The first match it finds is also the last match it will try. If, after succeeding, the overall match fails to the right of the atomic group, backing up into the group fails at once - no other alternatives for `...` are tried. So, in the example, .*?spam finds the closest (if any) following instance of "spam", and that's all. It won't ever go on to try to match a later instance of "spam". Which is probably what most people had in mind all along when they wrote plain .*?spam but were instead delighted by mysterious cases of exponential-time backtracking ;-) "Possessive quantif\iers" are syntactic sugar for particular simple instances of atomic groups. Where R is a regexp, R++ is short for (?>R+) R*+ is short for (?>R*) R{m,n}+ is short for (?>R{m,n}) R?+ is short for (?>R?) In all cases, they take the longest match possible for R starting right here, right now, without any consideration for whether that may or may not cause the rest of the pattern to fail, and then they hold on to that longest-possible match no matter what. No backtracking after the first success. You should feel free to use these in 3.11. There are few modern regexp engines that don't support them, and they were the most conspicuous of the "missing features" in Python's `re`.

Tim Peters writes:

Chris didn't say this, but I will: I'm amazed that things much _simpler_ than regexps, like his scanf and REXX PARSE examples, haven't spread more.

scanf just isn't powerful enough. For example, consider parsing user input dates: scanf("%d/%d/%d", &year, &month, &day). This is nice and simple, but handling "2022-02-15" as well requires a bit of thinking and several extra statements in C. In Python, I guess it would probably look something like year, sep1, month, sep2, day = scanf("%d%c%d%c%d") if not ('/' == sep1 == sep2 or '-' == sep1 == sep2): raise DateFormatUnacceptableError # range checks for month and day go here which isn't too bad, though. But year, month, day = re.match(r"(\d+)[-/](\d+)[-/](\d+)").groups() if not sep1 == sep2: raise DateFormatUnacceptableError # range checks for month and day go here expresses the intent a lot more clearly, I think. Sure, it's easy to write uninterpretable regexps, but up to that point regexps are very expressive. And that example can be reduced to one line (plus the comment) at the expense of a less symmetric, slightly less readable expression like r"(\d+)([-/])(\d+)\2(\d+)". Some folks might like that one better.

Simple solutions to simple problems are very appealing to me.

The Zawinski quote is motivated by the perception that people seem to think that simplicity lies in minimizing the number of tools you need to learn. REXX and SNOBOL pattern matching quite a bit more specialized to particular tools than regexps. That is, all regexp implementations support the same basic language which is sufficient for most tasks most programmers want regexps for. I think you'd need to implement such a facility in a very popular scripting language such as sh, Perl, or Python for it to have the success of regexps.

Although, to be fair, I get a kick too out of massive overkill ;l-)

Don't we all, though? Steve

Chris Angelico writes:

On Wed, 16 Feb 2022 at 01:54, Stephen J. Turnbull <stephenjturnbull@gmail.com> wrote:

...

That is, all regexp implementations support the same basic language which is sufficient for most tasks most programmers want regexps for.

The problem is that that's an illusion.

It isn't for me. I write a lot of regexps for several languages (Python, grep, sed, Emacs Lisp), I rarely have to debug one, and in a year there may be one that debugging requires more than reading each character out loud and recognizing a typo. As a sometime Emacsen dev, I also do a fair amount of debugging of other people's regexps. Yuck! But it's almost always the case that (modulo efficiency considerations) it's pretty easy to figure out what they *want*, and rewrite the code (*not* the *regexp(s)*!) to use simpler regexps (usually parts of the original) in a more controlled way.

If you restrict yourself to the subset that's supported by every regexp implementation, you'll quickly find tasks that you can't handle.

That's true of everything in programming, there are no tools that can handle everything until you have a Turing-complete programming language, and even then, practically there are always things that are too painful even for masochists to do in that language. But with regexps, I don't, you see. Besides regexps, I write a lot of (trivial to simple) parsers. For the regexps, I don't need much more than ()[]+*?.\s\d\t\r\n most of the time (and those last 3 are due to tab-separated value files and RFC 822, special cases). I could probably use scanf (except that Python, sed, and Emacs Lisp don't have it ;-) but for the lack of []. Occasionally for things like date parsing and other absolutely fixed-field contexts I'll use {}. I do sanity-checking on the result frequently. If the regexp engine supports it, I'll use named groups and other such syntactic sugar. In a general purpose programming language, if it supports "literate regexps", I use those, if not, I use separate strings (which also makes it easy to back out of a large regexp into statements if I need to establish backtracking boundaries). Sure, if you want to do all of that *in* a single regexp, you are indeed going to run into things you can't do that way. When I wrote, "what people want to do" I meant tasks where regexps could do a lot of the task, but not that they could do the whole thing in one regexp. For my style, regexps are something that's available in a very wide array of contexts, and consistent enough to get the job done. I treat complex regexps the way I treat C extensions: only if the performance benefit is human-perceptible, which is pretty rare.

"why are other things not ALSO popular". I honestly think that scanf parsing, if implemented ad-hoc by different programming languages and extended to their needs, would end up

... becoming regexp-like, and not just in the sense of

no less different from each other than different regexp engines are - the most-used parts would also be the most-compatible, just like with regexps.

;-) What I think is more interesting than simpler (but more robust for what they can do) facilities is better parser support in standard libraries (not just Python's), and more use of them in place of hand-written "parsers" that just eat tokens defined by regexps in order. If one could, for example, write [ "Sun|Mon|Tue|Wed|Thu|Fri|Sat" : dow, ", ". "(?: |\d)\d)" : day, " ", "Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec" : month, " ", "\d\d\d\d" : year, " ", "\d\d:\d\d:\d\d" : time, " ", "[+-]\d\d\d\d" : tzoffset ] (which is not legal Python syntax but I'm too lazy to try to come up with something better) to parse an RFC 822 date, I think people would use that. Sure, for something *that* regular, most people would probably use the evident "literate" regexp with named groups, but it wouldn't take much complexity to make such a parser generator worthwhile to programmers. Steve

On Wed, 16 Feb 2022 at 10:23, Chris Angelico <rosuav@gmail.com> wrote:

On Wed, 16 Feb 2022 at 21:01, Stephen J. Turnbull <stephenjturnbull@gmail.com> wrote:

...

What I think is more interesting than simpler (but more robust for what they can do) facilities is better parser support in standard libraries (not just Python's), and more use of them in place of hand-written "parsers" that just eat tokens defined by regexps in order. If one could, for example, write

[ "Sun|Mon|Tue|Wed|Thu|Fri|Sat" : dow, ", ". "(?: |\d)\d)" : day, " ", "Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec" : month, " ", "\d\d\d\d" : year, " ", "\d\d:\d\d:\d\d" : time, " ", "[+-]\d\d\d\d" : tzoffset ]

(which is not legal Python syntax but I'm too lazy to try to come up with something better) to parse an RFC 822 date, I think people would use that. Sure, for something *that* regular, most people would probably use the evident "literate" regexp with named groups, but it wouldn't take much complexity to make such a parser generator worthwhile to programmers.

That's an interesting concept. I can imagine writing it declaratively like this:

class Date(parser): dow: "Sun|Mon|Tue|Wed|Thu|Fri|Sat" _: ", " day: "(?: |\d)\d)"

I find it mildly amusing that even this "better" solution fell victim to an incorrect regexp ;-) However, I do like the idea of having a better parser library in the stdlib. But it's pretty easy to write such a thing and publish it on PyPI, so the lack of an obvious "best in class" answer for this problem suggests that people would be less likely to use such a feature than we're assuming. The two obvious examples on PyPI are: 1. PyParsing - https://pypi.org/project/pyparsing/. To me, this has the feel of the sort of functional approach SNOBOL used. 2. parse - https://pypi.org/project/parse/. A scanf-style approach inspired by format rather than printf. Do people choose regexes over these because re is in the stdlib? Are they simply less well known? Or is there an attraction to regexes that makes people prefer them in spite of the complexity/maintainability issues? Paul

Paul Moore writes:

However, I do like the idea of having a better parser library in the stdlib. But it's pretty easy to write such a thing and publish it on PyPI,

It's not easy to write a good one. I've tried in two languages (Python and Lisp). I'm not saying I'm competent, so that's a faint damn.

so the lack of an obvious "best in class" answer for this problem suggests that people would be less likely to use such a feature than we're assuming.

To me it suggests that it's hard to come up with a UI that's clearly better than regexp.

Do people choose regexes over these because re is in the stdlib?

Almost certainly, to some extent.

Or is there an attraction to regexes that makes people prefer them in spite of the complexity/maintainability issues?

I think that a lot of it is that people are extremely comfortable with globbing, and re at first glance looks like globbing on steroids with no downside. On the other hand, parsing is "known" (note scare quotes) to be hard, people *hate* "grammar", and unlike grep and sed which are simple enough to be usable at the command line, not only isn't lex embedded in yacc, but both really need to be saved in files and compiled, then run, to be tested. It just feels really heavy compared to regexp. I think that if experienced people used parsers more they would get general uptake. But people seem to think that parsers are for experts, more so than regexp. That's why I chose a simple list-with-annotations rather than something like Chris's idea which in Python looks like magic. "If we could just make it *this* simple ..." Steve

On Wed, 16 Feb 2022 at 10:15, Steven D'Aprano <steve@pearwood.info> wrote:

On Tue, Feb 15, 2022 at 11:51:41PM +0900, Stephen J. Turnbull wrote:

...

scanf just isn't powerful enough. For example, consider parsing user input dates: scanf("%d/%d/%d", &year, &month, &day). This is nice and simple, but handling "2022-02-15" as well requires a bit of thinking and several extra statements in C. In Python, I guess it would probably look something like

year, sep1, month, sep2, day = scanf("%d%c%d%c%d") if not ('/' == sep1 == sep2 or '-' == sep1 == sep2): raise DateFormatUnacceptableError # range checks for month and day go here

Assuming that scanf raises if there is no match, I would probably go with:

Having scanf raise is one option; another option would be to have it return a partial result, which would raise ValueError when unpacked in this simple way. (Partial results are FAR easier to debug than a simple "didn't match", plus they can be extremely useful in some situations.)

try: # Who writes ISO-8601 dates using slashes? day, month, year = scanf("%d/%d/%d") if ALLOW_TWO_DIGIT_YEARS and len(year) == 2: year = "20" + year except ScanError: year, month, day = scanf("%d-%d-%d")

It all depends on what your goal is. Do you want to support multiple different formats (d/m/y, y-m-d, etc)? Do you want one format with multiple options for delimiter? Is it okay if someone mismatches delimiters? Most likely, I'd not care if someone uses y/m-d, but I wouldn't allow d/m/y or m/d/y, so I'd write it like this: year, month, day = scanf("%d%*[-/]%d%*[-/]%d") But realistically, if we're doing actual ISO 8601 date parsing, then *not one of these is correct*, and we should be using an actual ISO 8601 library :) The simple cases like log file parsing are usually consuming the output of exactly one program, so you can mandate the delimiter completely. Here's something that can parse the output of 'git blame': commit, name, y,m,d, h,m,s, tz, line, text = \ scanf("%s (%s %d-%d-%d %d:%d:%d %d %d) %s") (Of course, you should use --porcelain instead, but this is an example.) There's a spectrum of needs, and a spectrum of tools that can fulfil them. At one extreme, simple method calls, the "in" operator, etc - very limited, very fast, easy to read. At the other extreme, full-on language parsers with detailed grammars. In between? Well, sscanf is a bit simpler than regexp, REXX's parse is probably somewhere near sscanf, SNOBOL is probably a bit to the right of regexp, etc, etc, etc. We shouldn't have to stick to a single tool just because it's capable of spanning a wide range.

I think that

year, sep1, month, sep2, day = re.match(r"(\d+)([-/])(\d+)([-/])(\d+)").groups()

might do it (until Tim or Chris tell me that actually is wrong).

Or use \2 as you suggest later on.

Yeah, \2 much more clearly expresses the intent of "take either of these characters, and then match another of that character". ChrisA

Tim Peters wrote:

""" Some people, when confronted with a problem, think “I know, I'll use regular expressions.” Now they have two problems. - Jamie Zawinski """

Maybe so, but I'm committed now :). I have dozens of regexes to parse specific log messages I'm interested in. I made a little DSL that uses regexes with capture groups, and if the regex matches, takes the resulting groupdict and optionally applies further transformations on the individual fields. This allows me to very concisely specify what I want to extract before doing further analysis and aggregation on the resulting fields. For example: flush_end = Rule( Capture( # Completed flushing /u01/data02/tb_tbi_project02_prd/data_launch_index-4a5f72725b7211eaab635720a1b8a299/aa-26507-bti-Data.db (46.528MiB) for commitlog position CommitLogPosition(segmentId=1615955816662, position=223538288) # Completed flushing /dse/data02/OpsCenter/rollup_state-7b621931ab7511e8b862810a639403e5/bb-21969-bti-Data.db (7.763MiB/2.197MiB on disk/1 files) for commitlog position CommitLogPosition(segmentId=1637403836277, position=9927158) r"Completed flushing (?P<sstable>[^ ]+) \((?P<bytes_flushed>[^)/]+)(/(?P<bytes_on_disk>[^ ]+) on disk/(?P<file_count>[^ ]+) files)?\) for commitlog position CommitLogPosition\(segmentId=(?P<commitlog_segment>[^,]+), position=(?P<commitlog_position>[^)]+)\)" ), Convert( normval, "bytes_flushed", "bytes_on_disk", "commitlog_segment", "commitlog_position", ), table_from_sstable, ) I know there are specialized tools like logstash but it's nice to be able to specify the extraction and subsequent analysis together in Python.

reason to change that. Naive regexps are both clumsy and prone to bad timing in many tasks that "should be" very easy to express. For example, "now match up to the next occurrence of 'X'". In SNOBOL and Icon, that's trivial. 75% of regexp users will write ".*X", with scant understanding that it may match waaaay more than they intended. Another 20% will write ".*?X", with scant understanding that may extend beyond _just_ "the next" X in some cases. That leaves the happy 5% who write "[^X]*X", which finally says what they intended from the start.

If you look in my regex in the example above, you will see that the "[^X]*X" is exactly what I did. The pathological case arose from a simple typo where I had an extra + after a capture group that I failed to notice, and which somehow worked correctly on the expected input but ran forever when the expected terminating character appeared more times than expected in the input string.

On Thu, 17 Feb 2022 at 08:33, J.B. Langston <jblangston@datastax.com> wrote:

Well, I certainly sparked a lot of interesting discussion, which I have quite enjoyed reading. But to bring this thread back around to its original topic, is there support among the Python maintainers for adding a timeout feature to the Python re library? I will look at the third-party regex library that Jonathan suggested but I still believe a timeout option would be a valuable feature to have in the standard library.

I'm not a maintainer, but I'd personally be against a timeout. It would add overhead to common cases in order to put a shield around pathological ones, and it's difficult to impossible to usefully define the cutoff. Instead, I'd recommend trying some of the simpler parsing options, as explored in the ensuing discussion, to see if one of those has better worst-case performance while still being able to do what's needed. (Hence all the discussion of "no-backtracking" options.) ChrisA

On 2022-02-16 22:13, Tim Peters wrote:

[J.B. Langston <jblangston@datastax.com>]

...

Well, I certainly sparked a lot of interesting discussion, which I have quite enjoyed reading. But to bring this thread back around to its original topic, is there support among the Python maintainers for adding a timeout feature to the Python re library?

Buried in the fun discussion was my guess: no way. Python's re is effectively dead legacy code, with no current "owner". Its commit history shows very little activity for some years already. Mos\ commits are due to generic "cod\e cleanup" crusades that have nothing specific to do with the algorithms. None required non-triv\ial knowledge of the implementation.

Here's the most recent I found that actually changed behavior:

""" commit 6cc8ac949907b9a1c0f73709c6978b7a43e634e3 Author: Zackery Spytz <zspytz@gmail.com> Date: Fri May 21 14:02:42 2021 -0700

bpo-40736: Improve the error message for re.search() TypeError (GH-23312)

Include the invalid type in the error message. """"

A trivial change.

...

I will look at the third-party regex library that Jonathan suggested but I still believe a timeout option would be a valuable feature to have in the standard library.

Which is the problem: regex has _dozens_ of features that would be valuable to have in the standard library. reg\ex is in fact one of the best regexp libraries on the planet. It already has timeouts, and other features (like possessive quantifiers) that are actually (unlike timeouts) frequently asked about by many programmers.

In fact regex started life intending to go into core Python, in 2008:

https://bugs.python.org/issue3825

That stretched on and on, and the endless bikeshedding eventually appeared to fizzle out in 2014:

https://bugs.python.org/issue2636

In 2021 a core dev eventually rejected it, as by then MRAB had long since released it as a successful extension module. I assume - but don't know - he got burned out by "the endless bikeshedding" on those issue reports.

I eventually decided against having it added to the standard library because that would tie fixes and additions to Python's release cycle, and there's that adage that Python has "batteries included", but not nuclear reactors. PyPI is a better place for it, for those who need more than what the standard re module provides.

In any cose, no, no core dev I know of is going to devote their limited time to reproducing a tiny subset of regex's many improvements in Python's legacy engine. In fact, "install regex!" is such an obvious choice at this point that I wouldn't even give time to just reviewing a patch that added timeouts.

BTW, I didn't mention regex in your BPO report because I didn't know at the time it already implemented timeouts. I learned that in this thread.

Thanks for the conclusive answer. I will checkout the regex library soon.

On 17 Feb 2022, at 01:04, Tim Peters <tim.peters@gmail.com> wrote:

[J.B. Langston <jblangston@datastax.com> ]

...

Thanks for the conclusive answer.

Not conclusive - just my opinion. Which is informed, but not infallible ;-)

...

I will checkout the regex library soon.

You may not realize how easy this is? Just in case: go to a shell and type

pip install regex

(or, on Windows, "python -m pip install regex" in a DOS box).

That's it. You're done. Now you can use regex. In some cases, you can put "import regex as re" at the top of a module At worst, replace instances of "re" with "regex". Stay away from the new features, and it's highly compatible with Python;s re.

I suspect that like me what was meant is that checkout means read the docs to understand regex features. The install is trivial. Barry

_______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-leave@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/C35D2Z... Code of Conduct: http://python.org/psf/codeofconduct/

[Steven D'Aprano <steve@pearwood.info>]

[skipping FUD about pip]

If the OP: has problems with pip they can't easily resolve, I expect they'll say so. In my experience, effective help consists of sticking to the simplest things that can possibly work at first, not bury a questioner with an exhaustive account of everything that could possibly go wrong. That's your job ;-) Note that there's not the slightest reason to expect that the OP here is a newbie; quite the contrary.

...

Now you can use regex. In some cases, you can put "import regex as re" at the top of a module At worst, replace instances of "re" with "regex". Stay away from the new features, and it's highly compatible with Python;s re.

If you're only using the features that re supports, wouldn't it be easier to just use re?

Th\e OP explicitly doesn't want to stick to th\e features re supports. Specifically, they want to use the optional timeouts that regex supports but re doesn't. What I wrote here is more elaboration on that _trying_ this is easier than they might be thinking: They don't have to, e.g., rewrite their regexps, or invoke different function or method names, or worry that they'll get different results. The packages are highly compatible in syntax and semantics and APIs so long as you stick to the things re does. That in no way suggests they _should_ stick to what re does. It's assuring them \that _getting started_ is close to trivial. Their current code should continue to work unchanged, apart from just changing "re" to "regex".

And, as it turns out, I already had it installed via some transitive dependency. The bigger task will be to testing. Indeed it may be as easy as "import regex as re" but I need to test and make sure my regexes still work as expected and that the performance doesn't take a big hit. Trust, but verify :)

[J.B. Langston <jblangston@datastax.com>]

And unfortunately it does appear that my app took an almost a 20% performance hit from using regex instead of re, unfortunately. Processing time for a test dataset with 700MB of logs went from 77 seconds with the standard library re to 92 seconds with regex. Profiling confirms that the time spent in the groupdict method went from 3.27% to 9.41% and the time spent in match went from 5.19 to 10.33% of the execution time.

I'm mildly surprised! Most times people report that regex is at least modestly faster than re. For peak performance at the expense of flexibility (e.g., no backreferences supported), perhaps you'd get a major speed gain from an entirely different regexp engine approach. Google built such an engine, which has worst-case linear matching runtime (but, depending on details, _may_ require space exponential in the regexp to compile a regexp object). A Python binding for that is here ("pip install pyre2"): https://pypi.org/project/pyre2/ I haven't used it - this isn't a particular area of interest for me. Note that in its "Performance" section, it shows examples where it blows re out of the water. But, in all those cases, regex was modestly to very significantly faster than re too. YMMV.

So this means switching to regex is probably a no go.

The difference between 77 and 92 seconds doesn't, on the face of it, scream "disaster" to me - but suit yourself.

If hanging regexes become a common occurrence for my app I might decide it's worth the performance hit in the name of safety, but at this point I would rather not.

If they were destined to become a common occurrence, they already would have done so. You blamed your bad case on unexpected data, but the _actual_ cause was an unintended typo in one of your regexps. So it goes. You're using a tool with a hyper-concise notation, where a correct expression is pretty much indistinguishable from line noise, and a typo is rarely detectable as a syntax error. So you're learning the hard way that you have to be on crisis-level alert when writing regexps: they're extremely touchy and unforgiving, pyre2 would spare you from all match-time timing disasters, but "touchy and unforgiving" applies all the same. Instead of a typo causing exponential runtime, it may instead cause the regexp to match (or fail to match) in unintended ways. About which no clue of any kind will be left behind, unless you stare at the inputs and outputs and check them yourself. But, in that case, 92 seconds wouldn't even get you through 1000 bytes ;-)