String matching problem/bug

Question

I expected this code below to evaluate to True (it does evaluate to False):

StringMatchQ["«TITLE:Load(1,2)»",
 (StartOfString ~~ "«" ~~ prop__ ~~ ":Load»" ~~ EndOfString) |
 (StartOfString ~~ "«" ~~ prop__ ~~ ":Load(" ~~ params___ ~~ ")»" ~~ 
EndOfString)]

Especially since this simpler one does indeed evaluate to True:

StringMatchQ["«TITLE:Load(1,2)»",
 ("JUST A RANDOM STRING WHICH IS NOT MATCHED ANYWAY")|
  (StartOfString ~~ "«" ~~ prop__ ~~ ":Load(" ~~ params___ ~~ ")»" ~~ 
    EndOfString)]

Have I just found a bug or am I missing some subtlety?

Answer 1

Summary

The behaviour we see is due to bug in the way that a string pattern is converted into a regular expression for execution. A second occurrence of a pattern name is unconditionally represented as a back-reference to the first occurrence of that name within the regular expression. But this conversion fails to take into account the possibility that the first and second references are mutually exclusive when they appear on different sides of the | operator. In such circumstances a back-reference is not appropriate.

Work-around

As Carl Woll notes in a comment, the problem can be worked around by omitting the pattern names:

StringMatchQ[
  {"«TITLE:Load»", "«TITLE:Load(1,2)»"}
,   (StartOfString~~"«"~~__~~":Load»"~~EndOfString)
  | (StartOfString~~"«"~~__~~":Load("~~___~~")»"~~EndOfString)
]

(* {True, True} *)

or by using a distinct name for prop in the second alternative:

StringMatchQ[
  {"«TITLE:Load»", "«TITLE:Load(1,2)»"}
,   (StartOfString~~"«"~~prop__~~":Load»"~~EndOfString)
  | (StartOfString~~"«"~~prop2__~~":Load("~~params___~~")»"~~EndOfString)
]

(* True, True *)

In the latter case, only one of prop or prop2 will be bound to a non-empty value. This fact makes it easy, for example, to extract the matched values:

StringCases[
  {"«TITLE:Load»", "«TITLE:Load(1,2)»"}
,   (StartOfString~~"«"~~prop__~~":Load»"~~EndOfString)
  | (StartOfString~~"«"~~prop2__~~":Load("~~params___~~")»"~~EndOfString)
  :> prop~~prop2~~"("~~params~~")"
]

(* {{"TITLE()"}, {"TITLE(1,2)"}} *)

Discussion (current as of Mathematica 11.2)

Note that the observed problem only affects the second pattern alternative:

StringMatchQ[
  {"«TITLE:Load»", "«TITLE:Load(1,2)»"}
,   (StartOfString ~~ "«" ~~ prop__ ~~ ":Load»" ~~ EndOfString)
  | (StartOfString ~~ "«" ~~ prop__ ~~ ":Load(" ~~ params___ ~~ ")»" ~~ EndOfString)
]

(* {True, False} *)

This behaviour highlights a (likely unintentional) difference between general pattern-matching and string pattern-matching. Let us consider some simpler patterns.

Consider the following general match:

Cases[{{1, 2}, {a}}, {_, x_} | {x_} :> x]

(* {2, a} *)

The repetition of the pattern name x poses no problems even though it is re-used in mutually exclusive alternatives. But an analogous string pattern does not work as expected:

StringCases[{"12", "a"}, (_ ~~ x_) | x_]

(* {{"12"}, {}} *)

Note how the second pattern alternative does not match.

Mathematica implements string patterns using PCRE regular expressions. We can use the lightly documented function PatternConvert to see how our string pattern is interpreted as a regular expression:

StringPattern`PatternConvert[(_ ~~ x_) | x_]

(* {"(?ms)(?:.(.)|(?:\g{1}))", {{Hold[x], 1}}, {}, Hold[None]} *)

The result is a list of two elements. The first element is the generated regular expression. The second element describes, among other things, the symbols to associate with any "captured" matches. In this case {Hold[x], 1} specifies the name x for the first and only captured match.

This generated expression is problematic. Note the emphasized subpatterns of the regular expression, (.) and \g{1}. The dot in (.) indicates that any character will be matched and the parentheses indicate that the match should be captured. \g{1} is a back-reference to that first match. If the pattern did not contain the | alternative operator, then this back-reference would make sense and would indicate that whatever characters were captured by the first subpattern must be repeated again at the point of the second subpattern.

But since these subpatterns appear mutually-exclusive alternatives, the back-reference \g{1} will be used if and only if the first alternative containing (.) failed to match. In that circumstance, the captured text for (.) will be the empty string. This prevents the match we seek in the example.

From this we conclude that the regular expression generated for (_ ~~ x_) | x_ is nonsensical. The regular expression for the original pattern exhibits the same flaw:

First@StringPattern`PatternConvert[
  (StartOfString~~"«"~~prop__~~":Load»"~~EndOfString)
| (StartOfString~~"«"~~prop__~~":Load("~~params___~~")»"~~EndOfString)
]

(* (?ms)(?:\A«(.+):Load»\z|\A«(?:\g{1}):Load((.*))»\z) *)

We can also see how changing the pattern name for the second alternative generates a useful regular expression with a second capture group instead of the problematic back-reference:

First@StringPattern`PatternConvert[
  (StartOfString~~"«"~~prop__~~":Load»"~~EndOfString)
| (StartOfString~~"«"~~prop2__~~":Load("~~params___~~")»"~~EndOfString)
]

(* "(?ms)(?:\A«(.+):Load»\z|\A«(.+):Load\((.*)\)»\z)" *)

Bug?

The nonsensical back-reference would seem to be a bug, albeit quite a subtle one. In any event, there is a simple work-around as shown at the beginning of this post.