This is an automated email from the ASF dual-hosted git repository.
pjfanning pushed a commit to branch 1.7.x
in repository https://gitbox.apache.org/repos/asf/pekko.git
The following commit(s) were added to refs/heads/1.7.x by this push:
new 3f0216ac17 fix: match actor selection wildcards without backtracking
(#3506) (#3519)
3f0216ac17 is described below
commit 3f0216ac17d95522d5e633fa770567ce446ea1cd
Author: PJ Fanning <[email protected]>
AuthorDate: Fri Sep 4 11:26:36 2026 +0100
fix: match actor selection wildcards without backtracking (#3506) (#3519)
* fix: match actor selection wildcards without backtracking
Motivation:
SelectChildPattern compiled its glob to a regular expression with
Helpers.makePattern, which turns every '*' into '.*'. A chain of those
backtracks: the 26 character pattern "*a*a*a*a*a*a*a*a*a*a*a*a*b" matched
against a 36 character actor name that cannot satisfy the trailing literal
takes about 42 seconds on one thread.
An ActorSelectionMessage carries its pattern elements in the message, so
that cost is reachable from one small message, and deliverSelection runs
on the caller's thread for a local selection and on the inbound stream
thread for a remote one. Bounding the pattern length would not help, since
26 characters is already enough.
Modification:
Add Glob (@InternalApi), which matches the same grammar - '?' is one
character, '*' is any run, everything else is literal - by remembering only
the most recent '*' rather than by backtracking, so it runs in time
proportional to the product of the two lengths at worst. Match through it
in ActorSelection.deliverSelection.
SelectChildPattern.pattern is kept for compatibility but is now lazy, so
deserializing a selection no longer compiles a regular expression either.
Result:
The same selections match as before, in time linear in practice.
* scalafmt
---
.../apache/pekko/actor/ActorSelectionSpec.scala | 17 ++++
.../scala/org/apache/pekko/util/GlobSpec.scala | 92 ++++++++++++++++++++++
.../org/apache/pekko/actor/ActorSelection.scala | 20 ++++-
.../main/scala/org/apache/pekko/util/Glob.scala | 73 +++++++++++++++++
4 files changed, 198 insertions(+), 4 deletions(-)
diff --git
a/actor-tests/src/test/scala/org/apache/pekko/actor/ActorSelectionSpec.scala
b/actor-tests/src/test/scala/org/apache/pekko/actor/ActorSelectionSpec.scala
index c74d783bda..0b3e796993 100644
--- a/actor-tests/src/test/scala/org/apache/pekko/actor/ActorSelectionSpec.scala
+++ b/actor-tests/src/test/scala/org/apache/pekko/actor/ActorSelectionSpec.scala
@@ -368,6 +368,23 @@ class ActorSelectionSpec extends PekkoSpec with
DefaultTimeout {
d.recipient.path.toStringWithoutAddress should ===("/user/missing")
}
+ "deliver a wildcard selection promptly even when the pattern would make a
regex backtrack" in {
+ val creator = TestProbe()
+ implicit def self: ActorRef = creator.ref
+ val top = system.actorOf(p, "backtrack")
+ // a 36 character child name, the length at which the old regex matching
took tens of
+ // seconds for a 26 character pattern
+ val childName = "a" * 36
+ Await.result((top ? Create(childName)).mapTo[ActorRef], timeout.duration)
+
+ val probe = TestProbe()
+ val pattern = ("*a" * 12) + "*b" // cannot match: the name has no 'b'
+ val started = System.nanoTime()
+ system.actorSelection(s"/user/backtrack/$pattern").tell(Identify(4),
probe.ref)
+ probe.expectMsg(3.seconds, ActorIdentity(4, None))
+ (System.nanoTime() - started) should be < 3.seconds.toNanos
+ }
+
"identify actors with wildcard selection correctly" in {
val creator = TestProbe()
implicit def self: ActorRef = creator.ref
diff --git a/actor-tests/src/test/scala/org/apache/pekko/util/GlobSpec.scala
b/actor-tests/src/test/scala/org/apache/pekko/util/GlobSpec.scala
new file mode 100644
index 0000000000..c03d3d0dc9
--- /dev/null
+++ b/actor-tests/src/test/scala/org/apache/pekko/util/GlobSpec.scala
@@ -0,0 +1,92 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.pekko.util
+
+import org.scalatest.concurrent.TimeLimits
+import org.scalatest.matchers.should.Matchers
+import org.scalatest.time.{ Seconds, Span }
+import org.scalatest.wordspec.AnyWordSpec
+
+class GlobSpec extends AnyWordSpec with Matchers with TimeLimits {
+
+ private def allStrings(alphabet: Seq[Char], maxLength: Int): Seq[String] =
(0 to maxLength).flatMap { n =>
+ (1 to n).foldLeft(Seq("")) { (acc, _) =>
+ acc.flatMap(s => alphabet.map(s + _))
+ }
+ }
+
+ "Glob" must {
+
+ "match the literal cases" in {
+ Glob.matches("abc", "abc") should ===(true)
+ Glob.matches("abc", "abd") should ===(false)
+ Glob.matches("", "") should ===(true)
+ Glob.matches("", "a") should ===(false)
+ Glob.matches("a", "") should ===(false)
+ }
+
+ "treat ? as exactly one character" in {
+ Glob.matches("a?c", "abc") should ===(true)
+ Glob.matches("a?c", "ac") should ===(false)
+ Glob.matches("a?c", "abbc") should ===(false)
+ Glob.matches("???", "abc") should ===(true)
+ }
+
+ "treat * as any run of characters" in {
+ Glob.matches("*", "") should ===(true)
+ Glob.matches("*", "anything") should ===(true)
+ Glob.matches("a*", "a") should ===(true)
+ Glob.matches("a*c", "abbbc") should ===(true)
+ Glob.matches("a*c", "abbbd") should ===(false)
+ Glob.matches("**", "ab") should ===(true)
+ Glob.matches("*b*", "abc") should ===(true)
+ }
+
+ "agree with the regular expression it replaces, exhaustively over short
inputs" in {
+ // Helpers.makePattern is what SelectChildPattern used before; matching
has to be
+ // unchanged, so compare the two over every short pattern and input.
+ val patterns = allStrings(Seq('a', 'b', '*', '?'), 4)
+ val inputs = allStrings(Seq('a', 'b'), 4)
+ patterns.size should be > 300
+ for {
+ pattern <- patterns
+ regex = Helpers.makePattern(pattern)
+ input <- inputs
+ } withClue(s"pattern [$pattern] input [$input]: ") {
+ Glob.matches(pattern, input) should ===(regex.matcher(input).matches)
+ }
+ }
+
+ "match a pattern that makes the regular expression backtrack, promptly" in
{
+ // 26 characters against a 36 character name. Through
Helpers.makePattern this takes
+ // roughly 47 seconds on one thread; here it is immediate.
+ val pattern = ("*a" * 12) + "*b"
+ val name = "a" * 36
+ failAfter(Span(3, Seconds)) {
+ Glob.matches(pattern, name) should ===(false)
+ }
+ }
+
+ "stay prompt as the input grows" in {
+ val pattern = ("*a" * 20) + "*b"
+ failAfter(Span(5, Seconds)) {
+ Glob.matches(pattern, "a" * 2000) should ===(false)
+ }
+ }
+ }
+}
diff --git a/actor/src/main/scala/org/apache/pekko/actor/ActorSelection.scala
b/actor/src/main/scala/org/apache/pekko/actor/ActorSelection.scala
index 1747c218bf..f3797efcde 100644
--- a/actor/src/main/scala/org/apache/pekko/actor/ActorSelection.scala
+++ b/actor/src/main/scala/org/apache/pekko/actor/ActorSelection.scala
@@ -30,7 +30,7 @@ import org.apache.pekko
import pekko.dispatch.ExecutionContexts
import pekko.pattern.ask
import pekko.routing.MurmurHash
-import pekko.util.{ Helpers, JavaDurationConverters, Timeout }
+import pekko.util.{ Glob, Helpers, JavaDurationConverters, Timeout }
import pekko.util.ccompat._
import pekko.util.FutureConverters
@@ -273,13 +273,13 @@ object ActorSelection {
val chldr = refWithCell.children
if (iter.isEmpty) {
// leaf
- val matchingChildren = chldr.filter(c =>
p.pattern.matcher(c.path.name).matches)
+ val matchingChildren = chldr.filter(c =>
p.matches(c.path.name))
if (matchingChildren.isEmpty && !sel.wildcardFanOut)
emptyRef.tell(sel, sender)
else
matchingChildren.foreach(_.tell(sel.msg, sender))
} else {
- val matchingChildren = chldr.filter(c =>
p.pattern.matcher(c.path.name).matches)
+ val matchingChildren = chldr.filter(c =>
p.matches(c.path.name))
// don't send to emptyRef after wildcard fan-out
if (matchingChildren.isEmpty && !sel.wildcardFanOut)
emptyRef.tell(sel, sender)
@@ -355,7 +355,19 @@ private[pekko] final case class SelectChildName(name:
String) extends SelectionP
*/
@SerialVersionUID(2L)
private[pekko] final case class SelectChildPattern(patternStr: String) extends
SelectionPathElement {
- val pattern: Pattern = Helpers.makePattern(patternStr)
+
+ /**
+ * The equivalent regular expression. Kept for compatibility and no longer
used for matching:
+ * it backtracks badly on patterns with several `*`, and the pattern arrives
in the message.
+ * Lazy so that deserializing a selection does not compile it.
+ */
+ lazy val pattern: Pattern = Helpers.makePattern(patternStr)
+
+ /**
+ * True if `name` matches this pattern. Runs without backtracking, see
[[Glob]].
+ */
+ def matches(name: String): Boolean = Glob.matches(patternStr, name)
+
override def toString: String = patternStr
}
diff --git a/actor/src/main/scala/org/apache/pekko/util/Glob.scala
b/actor/src/main/scala/org/apache/pekko/util/Glob.scala
new file mode 100644
index 0000000000..c78356127c
--- /dev/null
+++ b/actor/src/main/scala/org/apache/pekko/util/Glob.scala
@@ -0,0 +1,73 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.pekko.util
+
+import org.apache.pekko.annotation.InternalApi
+
+/**
+ * INTERNAL API
+ *
+ * Glob matching with the same semantics as [[Helpers.makePattern]] — `?`
matches one
+ * character, `*` matches any run of characters, everything else is literal —
without
+ * going through a regular expression.
+ *
+ * The regular expression `makePattern` builds turns every `*` into `.*`, and
a chain of
+ * those backtracks: matching `*a*a*a*a*a*a*a*a*a*a*a*a*b`, 26 characters,
against a
+ * 36 character name that cannot satisfy the trailing literal takes tens of
seconds on one
+ * thread, because the engine tries every way of distributing the literals.
Actor selections
+ * carry their pattern in the message, so that cost is reachable from a single
small message.
+ *
+ * This matcher never revisits a decision more than once per input position,
so it runs in
+ * time proportional to the product of the two lengths at worst, and linearly
in practice.
+ */
+@InternalApi private[pekko] object Glob {
+
+ /**
+ * True if `input` matches the glob `pattern`.
+ */
+ def matches(pattern: String, input: String): Boolean = {
+ var p = 0 // next character of the pattern to match
+ var i = 0 // next character of the input to match
+ // where to resume from if the run consumed by the most recent `*` turns
out to be too short
+ var starP = -1
+ var starI = -1
+
+ while (i < input.length) {
+ if (p < pattern.length && (pattern.charAt(p) == '?' || pattern.charAt(p)
== input.charAt(i))) {
+ p += 1
+ i += 1
+ } else if (p < pattern.length && pattern.charAt(p) == '*') {
+ // remember where to come back to, and start by having the `*` consume
nothing
+ starP = p
+ starI = i
+ p += 1
+ } else if (starP >= 0) {
+ // let the most recent `*` consume one more character and try again
from there
+ starI += 1
+ i = starI
+ p = starP + 1
+ } else {
+ return false
+ }
+ }
+
+ // trailing `*`s may match nothing, anything else left over means no match
+ while (p < pattern.length && pattern.charAt(p) == '*') p += 1
+ p == pattern.length
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
