StartOfLine and EndOfLine not working well inside Shortest

Question

Suppose that I want to replace lines containing "b" with a new "XXX" line. This works as expected with regular expressions:

StringReplace["a\n_b_\nc", RegularExpression["(?m)^.+b.+$"] -> "XXX"]

"a
XXX
c"

The (?m) activates multi-line mode so that ^ and $ can refer to each of the line beginnings and ends in the string. This is kind of cryptic so I prefer to use string expressions, but then, I get a different result:

StringReplace["a\n_b_\nc", 
    Shortest[StartOfLine ~~ ___ ~~ "b" ~~ ___ ~~ EndOfLine] -> "XXX"]

"XXX
c"

As a workaround, I can make it work like this:

StringReplace["a\n_b_\nc", 
    Shortest["\n" ~~ ___ ~~ "b" ~~ ___ ~~ "\n"] -> "\nXXX\n"]

"a
XXX
c"

but I would think that one should be able to use StartOfLine and EndOfLine.

What is going on? Are StartOfLine and EndOfLine incompatible with Shortest?

Answer 1

I confirmed with Wolfram support that this is not a bug [CASE:4214621]. This is what they said:

I believe that Shortest is behaving as designed here. The reason seems to be described under Details in ref/Shortest:

"If several Shortest objects occur in the same expression, those that appear first are given higher priority to match shortest sequences."

"Shortest[p] may not correspond to the absolutely shortest expression matching p if there are additional constraints elsewhere in the pattern."

We can actually verify that the desired answer is part of the matches but it is being prioritized lower. For instance, consider the following:

In[1]:= StringCases["a\n_b_\nc", 
          Shortest[StartOfLine ~~ ___ ~~ "b" ~~ ___ ~~ EndOfLine], Overlaps -> True]
Out[1]= {"a\n_b_", "_b_"}

I find this information very useful, by using Overlaps -> True one can understand what is going on. The issue is the usage of multiple BlankNullSequence (___) inside Shortest. With this knowledge I can now use a simpler string expression:

StringReplace["a\n_b_\nc", Except["\n"] ... ~~ "b" ~~ Except["\n"] ... -> "XXX"]

"a XXX c"

Answer 2

Looks like a bug to me. We can see what going on by looking this evaluation:

StringReplace[
  "a\n_b_\nc",
  s : Shortest[StartOfLine ~~ ___ ~~ "b" ~~ ___ ~~ EndOfLine] -> "*" ~~ s ~~ "*"]

"*a _b_* c"

Clearly, the 1st "\n" is not being handled properly. However and strangely,

StringReplace[
  "a\n_b_\nc",
  Shortest[StartOfLine ~~ s___ ~~ EndOfLine] -> "*" ~~ s ~~ "*"]

works and gives

"*a* *_b_* *c*"

From this 2nd result, we can derive a work-around.

StringReplace[
  "a\n_b_\nc",
  Shortest[StartOfLine ~~ s___ ~~ EndOfLine] :> If[StringContainsQ[s, "b"], "XXX", s]]

"a XXX c"

Not very pretty, I admit.

Another sign pointing to Shortest being buggy. Evaluating

StringReplace[
  "a\n_b_\nc",
  Shortest[StartOfLine ~~ _ ~~ "b" ~~ ___ ~~ EndOfLine] -> "XXX"]

gives the correct result.

Answer 3

I agree with the support that everything works as expected here. I would add to their explanation that the actual source of the differences in behavior of the RegularExpression and the StringExpression is that the latter always adds the s modifier which means dot matches newline. We can check this by converting StringExpression into the corresponding RegularExpression (what Mathematica always does internally):

StringPattern`PatternConvert[
 Shortest[StartOfLine ~~ ___ ~~ "b" ~~ ___ ~~ EndOfLine]]

{"(?ms)^.*?b.*?$", {}, {}, Hold[None]}

One can see the (?ms) at the beginning of the regex. It is easy to check that addition of the s modifier will break behavior of the regex described at the top of the original question:

StringReplace["a\n_b_\nc", 
 RegularExpression["(?ms)^.+b.+$"] -> "XXX"]

"XXX"

Note that the OP's regex uses greedy quantifier + (what is equivalent to Longest). If instead we will use lasy quantifier +? (which is equivalent to Shortest), we will get exactly what StringExpression returns:

StringReplace["a\n_b_\nc", 
 RegularExpression["(?ms)^.+?b.+?$"] -> "XXX"]

"XXX
c"

StringExpression has no option to switch off the mode when _ (equivalent to . in regex) matches newline. So the only way to achieve this is to use Except["\n"] instead of _ (what was found by the OP).