This is an automated email from the ASF dual-hosted git repository.
pjfanning pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/pekko.git
The following commit(s) were added to refs/heads/main by this push:
new ec6293149b fix: match actor selection wildcards without backtracking
(#3506)
ec6293149b is described below
commit ec6293149b2a62cb0889eac1e1f09e13783f3f2b
Author: PJ Fanning <[email protected]>
AuthorDate: Thu Sep 3 09:14:53 2026 +0100
fix: match actor selection wildcards without backtracking (#3506)
* 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 a8e9108e1d..ae1c159999 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 7facfe2e65..e1ceb3fb16 100644
--- a/actor/src/main/scala/org/apache/pekko/actor/ActorSelection.scala
+++ b/actor/src/main/scala/org/apache/pekko/actor/ActorSelection.scala
@@ -29,7 +29,7 @@ import scala.util.Success
import org.apache.pekko
import pekko.pattern.ask
import pekko.routing.MurmurHash
-import pekko.util.{ Helpers, Timeout }
+import pekko.util.{ Glob, Helpers, Timeout }
/**
* An ActorSelection is a logical view of a section of an ActorSystem's tree
of Actors,
@@ -242,13 +242,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)
@@ -324,7 +324,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]
