Implement capture group references in substitution strings

[malmaud]

Closes #1820.

Use http://www.pcre.org/current/doc/html/pcre2_substitute.html instead of Julia's native replace when the search pattern is a regex. This allows for capture reference in the substitution string.

Incidentally, it is ~4x faster than Julia's native replace implementation and should probably be used even when the search pattern is a not a regex, although I'll save that for another PR if people are interested.

Once potentially breaking change is how empty matches are handled:
Before, replace("abcd", r"b?", "^") == "^a^c^d^".
Now, replace("abcd", r"b?", "^") == "^a^^c^d^".

There are no set of options to PCRE that could cause it to replicate the old behavior.

Another breaking change is that PCRE doesn't support an option to limit how many replacements are made.

[simonster]

Maybe you could support the limit parameter by constructing a match context and calling pcre2_set_match_limit?

[malmaud]

That's not what match_limit does:

Internally, pcre2_match() uses a function called match(), which it calls repeatedly (sometimes recursively). The limit set by match_limit is imposed on the number of times this function is called during a match, which has the effect of limiting the amount of backtracking that can take place. For patterns that are not anchored, the count restarts from zero for each position in the subject string. This limit is not relevant to pcre2_dfa_match(), which ignores it.

[simonster]

Huh, I would have thought there'd be some way to do this (or at least to replace only the first match), but it's very possible there's not.

[malmaud]

It is possible to replace the only first match by not setting the SUBSTITUTE_GLOBAL flag, but as far as I can find there is no way direct way to find out where the offset should appropriately be set for replacing the second match.

[malmaud]

What do you think, @vtjnash ? If we want to support a limit parameter besides 1 or infinity, we'll either have to patch pcre's substitute function (it's a pretty trivial change) or port the whole function to julia (it's about 200 lines of C code in pcre2_substitute.c).

[StefanKarpinski]

Seems like a good candidate for a patch that we can submit upstream.

[malmaud]

I'm skeptical they'd accept it since it would seem to necessarily involve changing the PCRE API.

[nalimilan]

OTOH if even PCRE doesn't support that option, is it really needed in Julia? I'd say remove it, and if it turns out it's really needed it can always be added back later.

[malmaud]

Since the Julia-native replace has comparable performance now, I'd vote for just changing the julia replace to accept the PCRE $x syntax for including captured groups in the replacement.

[StefanKarpinski]

That would be cool but it seems like you'd need a special string literal type for that. Maybe s"foo$(x)bar" or something like that where the s stands for "substitute".

[ScottPJones]

😀 and then, if you want to combine that syntax with string interpolation, you could use the Swift (and others) \(...) syntax!

[malmaud]

Sounds good @StefanKarpinski . IMO, we might as well use the more traditional Perl and Python backreference substitution syntax (https://docs.python.org/2/library/re.html#re.sub) instead of the ad-hoc once introduced by PCRE2:

a dollar character is an escape character that can specify the insertion of characters from capturing groups in the pattern. The following forms are recognized:

$$ insert a dollar character
$ insert the contents of group
${} insert the contents of group

[malmaud]

The functionality is implemented now, mimicking the Python API:

replace("abcde", r"(..)(?P<byname>d)", s"\g<byname>xy\1") == "adxybce"

If this API looks good to people, I'll update this PR to include a new section describing it in the manual.

[hayd]

I think it would be good to add a test for when the groupname doesn't exist in the regex.

[malmaud]

Done.

[vtjnash]

@StefanKarpinski why does this need a special string literal? why wouldn't general-purpose "literal" string literal be sufficient?

[yuyichao]

Maybe to avoid API breaking and performance regression?

[malmaud]

bump @StefanKarpinski

[StefanKarpinski]

Sorry, I'm traveling and can't take a look at this (writing this on a plane
without wifi; it'll get delivered whenever I resurface).

On Wednesday, July 8, 2015, Jonathan Malmaud notifications@github.com
wrote:

bump @StefanKarpinski https://github.com/StefanKarpinski

—
Reply to this email directly or view it on GitHub
#11849 (comment).

[malmaud]

Sorry to keep bugging you @StefanKarpinski , but I'm unbelievably excited to reference capture groups in my substitution strings.

[StefanKarpinski]

It's a good change. Sorry my travels are causing a delay here!

[malmaud]

No problem. I think the only real question is the one that @vtjnash brings up - should we introduce the s string macro, or just have users deal with escaping unwanted backcapture references in the substitution strings if the pattern is a regex (as Python, Perl, etc. do)?

[kmsquire]

+1 -- I like this. But I agree with @vtjnash that SubstitutionString should simply be a literal/raw string.

[StefanKarpinski]

On Friday, July 10, 2015, Kevin Squire notifications@github.com wrote:

+1 -- I like this. But I agree with @vtjnash https://github.com/vtjnash
that SubstitutionString should simply be a literal/raw string.

A reason to use a custom string type is to allow splicing Julia code into
substitution strings, but that could be done as a later feature while still
allowing literal strings for compatibility.

[StefanKarpinski]

On Tuesday, July 7, 2015, Jonathan Malmaud notifications@github.com wrote:

The functionality is implemented now, mimicking the Python API:

replace("abcde", r"(..)(?Pd)", s"\gxy\1") == "adxybce"

If this API looks good to people, I'll update this PR to include a new
section describing it in the manual.

Nice. I like the API. Good reason to use a custom string literal for
substitutions.

[malmaud]

I think the question is whether replace(str, pattern::Regex, "\1") should just always interpret the "\1" in the replacement string as a backcapture reference unless the caller escapes it, which would be the quite ugly "\1".

[kmsquire]

My understanding is that raw strings wouldn't modify the string at all, and would simply be a generalization of the s_str proposed here. See #11764.

My main concern about adding _str macros to base is that they then become unavailable for use in packages (or user's own code). You can't even qualify to use them:

julia> Base.r"test"
ERROR: UndefVarError: r not defined

Would we really want to interpolate into a SubstitutionString?

[malmaud]

I'd be on board with using raw strings here to avoid backslash hell, and just using string as an alternative to $ interpolation in the relatively rare case where I need interpolation in my substitution string.

[StefanKarpinski]

I think that always substituting plain strings completely literally – i.e. no \1 substitution – would be for the best and only use a special type with custom literal syntax for interpreting that syntax as doing substitution. Otherwise you end up needing a way to escape those things to indicated that you

[StefanKarpinski]

@github, could you finally fix this horrible UI bug?

... didn't want to substitute. You also have the issue that computed substitutions run the risk of accidentally substituting.

[malmaud]

So just to be clear @StefanKarpinski , you are in favor of a SubstitutionString type? So if I add some docs to this PR, it should be good to go?

[vtjnash]

if we are going to add a SubstitutionString type, I would rather have the API look like:

SubstitutionString(raw"a\1b")

single character string literals are just too unreadable, and too valuable for packages

[malmaud]

If you're already using raw to avoid escaping "\1", then the only thing
you gain from SubstitutionString is avoiding the risk that a computed
substitution string inadvertently contains a backcapture reference. Is it
worth the verbosity and new type definition for that? In Python, you would
use re.escape on the replacement string if it was computed.

On Tue, Jul 14, 2015 at 1:07 PM, Jameson Nash notifications@github.com
wrote:

if we are going to add a SubstitutionString type, I would rather have the
API look like:

SubstitutionString(raw"a\1b")

single character string literals are just too unreadable, and too valuable
for packages

—
Reply to this email directly or view it on GitHub
#11849 (comment).

[hayd]

What about sub".." or subst".." ?

It's quite difficult to find help for single letter things, atm even if your knew it was @s_str

help?> @b_str
Symbol not found. Falling back on apropos search ...
No help information found.

[StefanKarpinski]

@malmaud wrote:

So just to be clear @StefanKarpinski , you are in favor of a SubstitutionString type? So if I add some docs to this PR, it should be good to go?

Yes, I'm all in favor of this – I actually couldn't see the patch before since I was reading email offline and composing messages to be sent later (have been traveling until recently). I like this PR as it is and I also like s"..." as the syntax. Writing SubstitutionString(raw"a\1b") is a total non-starter. Using regular expressions to do search and replace is not some rare thing that can have an awkward, verbose syntax. Perl didn't get popular for it's lovely syntax, it got popular because it made working with strings easy, convenient and fast – in no small part due to it's now-ubiquitous regular expressions.

If you're already using raw to avoid escaping "\1", then the only thing you gain from SubstitutionString is avoiding the risk that a computed substitution string inadvertently contains a backcapture reference. Is it worth the verbosity and new type definition for that? In Python, you would use re.escape on the replacement string if it was computed.

Yes, that's entirely worth it. How many Python programs are buggy because someone didn't call re.escape when they should have? This is the worst kind of bug because it is impossible to fine since it works most of the time because user data rarely contains strings like \1. Just because other languages made mistakes like this doesn't me we ought to repeat them.

[kmsquire]

Probably fine, but it's worth a grep through registered packages to make sure none define s_str.

[malmaud]

@kmsquire Is there an easy way to do that?

[ivarne]

Just clone all the packages in METADATA with a script, or ask someone who has already done so, to grep for you. I think there is great karma to be earned if someone have the skill to properly secure such a search service and provide it to the community.

[malmaud]

At any rate, I added documentation and rebased, so this is g2g once they're consensus on this SubstitutionString/s-prefix business.

[malmaud]

Might be nice to have this in before the .4 RC.

[malmaud]

@tkelman @IainNZ You guys know a lot about packages...are you in a position to quickly check if any registered packages use macro s_str?

[IainNZ]

https://github.com/search?utf8=%E2%9C%93&q=%22macro+s_str%22+language%3AJulia&type=Code&ref=searchresults

[malmaud]

Clever. It looks like https://github.com/andrewcooke/ParserCombinator.jl
and https://github.com/quinnj/Strings.jl are the only true positives.

On Tue, Jul 21, 2015 at 10:52 AM, Iain Dunning notifications@github.com
wrote:

https://github.com/search?utf8=%E2%9C%93&q=%22macro+s_str%22+language%3AJulia&type=Code&ref=searchresults

—
Reply to this email directly or view it on GitHub
#11849 (comment).

[IainNZ]

Strings isn't registered as well

[malmaud]

Still, maybe @vtjnash is right and we should use sub instead of s as the prefix. Less cryptic and less likely to conflict with any future packages.

[StefanKarpinski]

Personally, I like the fact that s comes after r in the alphabet. Am I incorrect that any module that defines its own s_str macro will just end up seeing that?

[mbauman]

I like s for exactly that reason, too. It also evokes the perl/sed syntax s/x/y/ in my head.

ParserCombinator.jl exports s_str, so this breaks uses of s"" after using ParserCombinator unless you add an explicit import (this may be solved independently as part of #12183):

julia> s""
Warning: both Bar and Foo export "@s_str"; uses of it in module Main must be qualified
ERROR: UndefVarError: @s_str not defined

[ScottPJones]

Strings.jl is a work in progress at the moment, I think, @quinnj would have to say if he really wants the s_str macro to be just s"...".

[quinnj]

Don't let Strings.jl get in the way of using s_str. It's currently just a convenience constructor for my own custom string type and has no long-term plans.

[malmaud]

@andrewcooke Would it be problematic for you if Base exports s_str?

[andrewcooke]

well it conflicts with ParserCombinator, but i can change it to some other letter (i have all of one user that i know of right now). and also, isn't there some way to choose which you want on conflicts? if not, i assume there will be at some point... (so, no, nothing terrible, but thanks for asking!)

[malmaud]

OK then. Checks pass, should be g2g.