Regex: Store start and end for the indices of matched groups.

sjrd · sjrd · commit ca4e64ea4c53 · 2021-06-10T18:54:09.000+02:00
And `undefined` for unmatched groups. In addition, store the start
and end of the whole match at index 0.

The indices array is cached directly as a field `indices` on the
`MatchResult`. This allows the cache to be better shared between a
`Matcher` and a `MatchResult`.

This corresponds to the format of the `indices` field of the
`regexp-match-indices` ECMAScript proposal.
diff --git a/javalib/src/main/scala/java/util/regex/IndicesBuilder.scala b/javalib/src/main/scala/java/util/regex/IndicesBuilder.scala
@@ -14,13 +14,18 @@ package java.util.regex
 
 import scala.annotation.{tailrec, switch}
 
-import java.util.HashMap
-
 import scala.scalajs.js
 
-/** The goal of a `GroupStartMapper` is to retrieve the start position of each
- *  group of a matching regular expression where only the strings of the
- *  matched groups are known.
+import Pattern.IndicesArray
+
+/** The goal of a `IndicesBuilder` is to retrieve the start and end positions
+ *  of each group of a matching regular expression.
+ *
+ *  This is essentially a polyfill for the 'd' flag of `js.RegExp`, which is
+ *  a Stage 4 proposal scheduled for inclusion in ECMAScript 2022. Without that
+ *  flag, `js.RegExp` only provides the substrings matched by capturing groups,
+ *  but not their positions. We implement the positions on top of that.
+ *
  *  For that, we use the following observation:
  *  If the regex /A(B)\1/ matches a string at a given index,
  *  then         /(A)(B)\2/ matches the same string at the same index.
@@ -38,7 +43,7 @@ import scala.scalajs.js
  *  - It computes the start of every group thanks to the groups before it
  *  - It builds and returns the mapping of previous group number -> start
  *
- *  The `pattern` that is parsed by `GroupStartMapper` is the *compiled* JS
+ *  The `pattern` that is parsed by `IndicesBuilder` is the *compiled* JS
  *  pattern produced by `PatternCompiler`, not the original Java pattern. This
  *  means that we can simplify a number of things with the knowledge that:
  *
@@ -53,13 +58,13 @@ import scala.scalajs.js
  *
  *  @author Mikaël Mayer
  */
-private[regex] class GroupStartMapper private (pattern: String, flags: String,
-    node: GroupStartMapper.Node, groupCount: Int,
+private[regex] class IndicesBuilder private (pattern: String, flags: String,
+    node: IndicesBuilder.Node, groupCount: Int,
     jsRegExpForFind: js.RegExp, jsRegExpForMatches: js.RegExp) {
 
-  import GroupStartMapper._
+  import IndicesBuilder._
 
-  def apply(forMatches: Boolean, string: String, index: Int): js.Array[Int] = {
+  def apply(forMatches: Boolean, string: String, index: Int): IndicesArray = {
     val regExp =
       if (forMatches) jsRegExpForMatches
       else jsRegExpForFind
@@ -73,31 +78,35 @@ private[regex] class GroupStartMapper private (pattern: String, flags: String,
           s"Original pattern '$pattern' with flags '$flags' did match however.")
     }
 
-    // Prepare a `groupStartMap` array with the correct length filled with -1
-    val len = groupCount + 1 // index 0 is not used
-    val groupStartMap = new js.Array[Int](len)
-    var i = 0
+    val start = index // by definition
+    val end = start + allMatchResult(0).get.length()
+
+    // Prepare an `indices` array with the correct length filled with undefined
+    val len = groupCount + 1 // index 0 is the whole match
+    val indices = new IndicesArray(len)
+    indices(0) = js.Tuple2(start, end)
+    var i = 1
     while (i != len) {
-      groupStartMap(i) = -1
+      indices(i) = js.undefined
       i += 1
     }
 
-    node.propagateFromStart(allMatchResult, groupStartMap, index)
+    node.propagate(allMatchResult, indices, start, end)
 
-    groupStartMap
+    indices
   }
 }
 
-private[regex] object GroupStartMapper {
-  def apply(pattern: String, flags: String): GroupStartMapper = {
+private[regex] object IndicesBuilder {
+  def apply(pattern: String, flags: String): IndicesBuilder = {
     val parser = new Parser(pattern)
     val node = parser.parseTopLevel()
     node.setNewGroup(1)
     val allMatchingPattern = node.buildRegex(parser.groupNodeMap)
     val jsRegExpForFind = new js.RegExp(allMatchingPattern, flags + "g")
     val jsRegExpForMatches =
       new js.RegExp(Pattern.wrapJSPatternForMatches(allMatchingPattern), flags)
-    new GroupStartMapper(pattern, flags, node, parser.parsedGroupCount,
+    new IndicesBuilder(pattern, flags, node, parser.parsedGroupCount,
         jsRegExpForFind, jsRegExpForMatches)
   }
 
@@ -155,16 +164,16 @@ private[regex] object GroupStartMapper {
      *  `end`, while other nodes propagate the `start`.
      */
     def propagate(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int, end: Int): Unit
+        indices: IndicesArray, start: Int, end: Int): Unit
 
     /** Propagates the appropriate positions to the descendants of this node
      *  from its end position.
      */
     final def propagateFromEnd(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], end: Int): Unit = {
+        indices: IndicesArray, end: Int): Unit = {
 
       val start = matchResult(newGroup).fold(-1)(matched => end - matched.length)
-      propagate(matchResult, groupStartMap, start, end)
+      propagate(matchResult, indices, start, end)
     }
 
     /** Propagates the appropriate positions to the descendants of this node
@@ -173,10 +182,10 @@ private[regex] object GroupStartMapper {
      *  @return the end position of this node, as a convenience for `SequenceNode.propagate`
      */
     final def propagateFromStart(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int): Int = {
+        indices: IndicesArray, start: Int): Int = {
 
       val end = matchResult(newGroup).fold(-1)(matched => start + matched.length)
-      propagate(matchResult, groupStartMap, start, end)
+      propagate(matchResult, indices, start, end)
       end
     }
   }
@@ -190,15 +199,15 @@ private[regex] object GroupStartMapper {
       "(" + inner.buildRegex(groupNodeMap) + ")"
 
     def propagate(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int, end: Int): Unit = {
+        indices: IndicesArray, start: Int, end: Int): Unit = {
       /* #3901: A GroupNode within a negative look-ahead node may receive
        * `start != -1` from above, yet not match anything itself. We must
        * always keep the default `-1` if this group node does not match
        * anything.
        */
       if (matchResult(newGroup).isDefined)
-        groupStartMap(number) = start
-      inner.propagate(matchResult, groupStartMap, start, end)
+        indices(number) = js.Tuple2(start, end)
+      inner.propagate(matchResult, indices, start, end)
     }
   }
 
@@ -217,11 +226,11 @@ private[regex] object GroupStartMapper {
       "((" + indicator + inner.buildRegex(groupNodeMap) + "))"
 
     def propagate(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int, end: Int): Unit = {
+        indices: IndicesArray, start: Int, end: Int): Unit = {
       if (isLookBehind)
-        inner.propagateFromEnd(matchResult, groupStartMap, end)
+        inner.propagateFromEnd(matchResult, indices, end)
       else
-        inner.propagateFromStart(matchResult, groupStartMap, start)
+        inner.propagateFromStart(matchResult, indices, start)
     }
   }
 
@@ -236,8 +245,8 @@ private[regex] object GroupStartMapper {
       "(" + inner.buildRegex(groupNodeMap) + repeater + ")"
 
     def propagate(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int, end: Int): Unit = {
-      inner.propagateFromEnd(matchResult, groupStartMap, end)
+        indices: IndicesArray, start: Int, end: Int): Unit = {
+      inner.propagateFromEnd(matchResult, indices, end)
     }
   }
 
@@ -247,7 +256,7 @@ private[regex] object GroupStartMapper {
       "(" + regex + ")"
 
     def propagate(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int, end: Int): Unit = {
+        indices: IndicesArray, start: Int, end: Int): Unit = {
       // nothing to do
     }
   }
@@ -262,7 +271,7 @@ private[regex] object GroupStartMapper {
     }
 
     def propagate(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int, end: Int): Unit = {
+        indices: IndicesArray, start: Int, end: Int): Unit = {
       // nothing to do
     }
   }
@@ -292,13 +301,13 @@ private[regex] object GroupStartMapper {
     }
 
     def propagate(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int, end: Int): Unit = {
+        indices: IndicesArray, start: Int, end: Int): Unit = {
       val len = sequence.length
       var i = 0
       var nextStart = start
       while (i != len) {
         nextStart =
-          sequence(i).propagateFromStart(matchResult, groupStartMap, nextStart)
+          sequence(i).propagateFromStart(matchResult, indices, nextStart)
         i += 1
       }
     }
@@ -333,11 +342,11 @@ private[regex] object GroupStartMapper {
     }
 
     def propagate(matchResult: js.RegExp.ExecResult,
-        groupStartMap: js.Array[Int], start: Int, end: Int): Unit = {
+        indices: IndicesArray, start: Int, end: Int): Unit = {
       val len = alternatives.length
       var i = 0
       while (i != len) {
-        alternatives(i).propagate(matchResult, groupStartMap, start, end)
+        alternatives(i).propagate(matchResult, indices, start, end)
         i += 1
       }
     }
diff --git a/javalib/src/main/scala/java/util/regex/Matcher.scala b/javalib/src/main/scala/java/util/regex/Matcher.scala
@@ -12,12 +12,12 @@
 
 package java.util.regex
 
-import scala.language.implicitConversions
-
 import scala.annotation.switch
 
 import scala.scalajs.js
 
+import Pattern.IndicesArray
+
 final class Matcher private[regex] (
     private var pattern0: Pattern, private var input0: String)
     extends AnyRef with MatchResult {
@@ -67,7 +67,6 @@ final class Matcher private[regex] (
       position = inputstr.length() + 1
     }
     lastMatchIsForMatches = false
-    startOfGroupCache = null
     lastMatch ne null
   }
 
@@ -151,7 +150,6 @@ final class Matcher private[regex] (
     position = 0
     lastMatch = null
     appendPos = 0
-    startOfGroupCache = null
     this
   }
 
@@ -172,7 +170,6 @@ final class Matcher private[regex] (
     // note that `position` and `appendPos` are left unchanged
     pattern0 = pattern
     lastMatch = null
-    startOfGroupCache = null
     this
   }
 
@@ -190,11 +187,11 @@ final class Matcher private[regex] (
   def end(): Int = start() + group().length
   def group(): String = ensureLastMatch(0).get
 
-  private def startInternal(compiledGroup: Int): Int = {
-    val s = startOfGroup(compiledGroup)
-    if (s == -1) -1
-    else s + regionStart()
-  }
+  private def indices: IndicesArray =
+    pattern().getIndices(ensureLastMatch, lastMatchIsForMatches)
+
+  private def startInternal(compiledGroup: Int): Int =
+    indices(compiledGroup).fold(-1)(_._1 + regionStart())
 
   def start(group: Int): Int = {
     if (group == 0) start()
@@ -204,11 +201,8 @@ final class Matcher private[regex] (
   def start(name: String): Int =
     startInternal(pattern().namedGroup(name))
 
-  private def endInternal(compiledGroup: Int): Int = {
-    val s = startOfGroup(compiledGroup)
-    if (s == -1) -1
-    else s + ensureLastMatch(compiledGroup).get.length + regionStart()
-  }
+  private def endInternal(compiledGroup: Int): Int =
+    indices(compiledGroup).fold(-1)(_._2 + regionStart())
 
   def end(group: Int): Int =
     if (group == 0) end()
@@ -225,10 +219,8 @@ final class Matcher private[regex] (
 
   // Seal the state
 
-  def toMatchResult(): MatchResult = {
-    new SealedResult(inputstr, lastMatch, lastMatchIsForMatches, pattern(),
-        regionStart(), startOfGroupCache)
-  }
+  def toMatchResult(): MatchResult =
+    new SealedResult(lastMatch, lastMatchIsForMatches, pattern(), regionStart())
 
   // Other query state methods
 
@@ -255,16 +247,6 @@ final class Matcher private[regex] (
 
   def hasAnchoringBounds(): Boolean = true
   //def useAnchoringBounds(b: Boolean): Matcher
-
-  // Lazily computed by `startOfGroup`, reset every time `lastMatch` changes
-  private var startOfGroupCache: js.Array[Int] = _
-
-  /** Returns a mapping from the group number to the respective start position. */
-  private def startOfGroup: js.Array[Int] = {
-    if (startOfGroupCache eq null)
-      startOfGroupCache = pattern0.groupStartMapper(lastMatchIsForMatches, inputstr, ensureLastMatch.index)
-    startOfGroupCache
-  }
 }
 
 object Matcher {
@@ -282,10 +264,8 @@ object Matcher {
     result
   }
 
-  private final class SealedResult(inputstr: String,
-      lastMatch: js.RegExp.ExecResult, lastMatchIsForMatches: Boolean,
-      pattern: Pattern, regionStart: Int,
-      private var startOfGroupCache: js.Array[Int])
+  private final class SealedResult(lastMatch: js.RegExp.ExecResult,
+      lastMatchIsForMatches: Boolean, pattern: Pattern, regionStart: Int)
       extends MatchResult {
 
     def groupCount(): Int = pattern.groupCount
@@ -294,36 +274,18 @@ object Matcher {
     def end(): Int = start() + group().length
     def group(): String = ensureLastMatch(0).get
 
-    private def startOfGroup: js.Array[Int] = {
-      if (startOfGroupCache eq null)
-        startOfGroupCache = pattern.groupStartMapper(lastMatchIsForMatches, inputstr, ensureLastMatch.index)
-      startOfGroupCache
-    }
+    private def indices: IndicesArray =
+      pattern.getIndices(ensureLastMatch, lastMatchIsForMatches)
 
     /* Note that MatchResult does *not* define the named versions of `group`,
      * `start` and `end`, so we don't have them here either.
      */
 
-    private def startInternal(compiledGroup: Int): Int = {
-      val s = startOfGroup(compiledGroup)
-      if (s == -1) -1
-      else s + regionStart
-    }
-
-    def start(group: Int): Int = {
-      if (group == 0) start()
-      else startInternal(pattern.numberedGroup(group))
-    }
-
-    private def endInternal(compiledGroup: Int): Int = {
-      val s = startOfGroup(compiledGroup)
-      if (s == -1) -1
-      else s + ensureLastMatch(compiledGroup).get.length + regionStart
-    }
+    def start(group: Int): Int =
+      indices(pattern.numberedGroup(group)).fold(-1)(_._1 + regionStart)
 
     def end(group: Int): Int =
-      if (group == 0) end()
-      else endInternal(pattern.numberedGroup(group))
+      indices(pattern.numberedGroup(group)).fold(-1)(_._2 + regionStart)
 
     def group(group: Int): String =
       ensureLastMatch(pattern.numberedGroup(group)).orNull
diff --git a/javalib/src/main/scala/java/util/regex/Pattern.scala b/javalib/src/main/scala/java/util/regex/Pattern.scala
