sunchao commented on code in PR #5415: URL: https://github.com/apache/datafusion-comet/pull/5415#discussion_r3836596233
########## spark/src/main/scala/org/apache/comet/expressions/CometRegex.scala: ########## @@ -0,0 +1,279 @@ +/* + * 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.comet.expressions + +import org.apache.comet.serde.{Compatible, Incompatible, SupportLevel} + +/** + * Regex flavor for [[CometRegex]]. The first version only implements [[RegexFlavor.RLike]]; later + * flavors (for example `regexp_replace` / `split`) can add extra reject rules such as empty-match + * divergence without changing the scanner's whitelist core. + */ +sealed trait RegexFlavor + +object RegexFlavor { + case object RLike extends RegexFlavor +} + +/** + * Plan-time whitelist analyzer for literal Java regex patterns. A pattern is [[Compatible]] only + * when every construct is one the analyzer positively recognizes as equivalent on Spark's + * `java.util.regex` engine and Comet's Rust `regex` crate. Anything unrecognized is + * [[Incompatible]]: the safe direction, so a missed construct never silently takes the native + * path. + * + * This is a recursive-descent scan, not a search for forbidden substrings. `[(?=]` is a character + * class of literals, not a lookahead; `\\d` is a literal backslash plus `d`, not a digit class. + */ +object CometRegex { + + def supportLevel(pattern: String, flavor: RegexFlavor = RegexFlavor.RLike): SupportLevel = { + flavor match { + case RegexFlavor.RLike => + val scanner = new Scanner(pattern) + if (scanner.parseExpr() && !scanner.remaining) { + Compatible() + } else { + Incompatible(None) + } + } + } + + private val MetaEscapes: Set[Char] = + Set('.', '*', '+', '?', '(', ')', '[', ']', '{', '}', '|', '^', '$', '\\') + + private class Scanner(pattern: String) { + private var i = 0 + + def remaining: Boolean = i < pattern.length + + private def peek: Char = pattern.charAt(i) + + private def peekOffset(n: Int): Option[Char] = { + val idx = i + n + if (idx < pattern.length) Some(pattern.charAt(idx)) else None + } + + private def consume(): Char = { + val c = peek + i += 1 + c + } + + private def startsWith(s: String): Boolean = pattern.startsWith(s, i) + + def parseExpr(): Boolean = { + if (!parseTerm()) { + return false + } + while (remaining && peek == '|') { + consume() + if (!parseTerm()) { + return false + } + } + true + } + + private def parseTerm(): Boolean = { + while (remaining && peek != '|' && peek != ')') { + if (!parseFactor()) { + return false + } + } + true + } + + private def parseFactor(): Boolean = { + if (!parseAtom()) { + return false + } + parseOptionalQuantifier() + } + + private def parseAtom(): Boolean = { + if (!remaining) { + return false + } + peek match { + case '\\' => parseEscape(inClass = false).isDefined + case '[' => parseClass() + case '(' => parseGroup() + case '.' | '^' | '$' | '*' | '+' | '?' | '{' | '}' | ')' | ']' | '|' => + false + case c if isPrintableAscii(c) => + consume() + true + case _ => false + } + } + + private def parseGroup(): Boolean = { + consume() // '(' + if (!remaining) { + return false + } + if (startsWith("?:")) { + i += 2 + } else if (peek == '?') { + // lookaround, flags, named groups, atomic groups, comments, ... + return false + } + if (!parseExpr()) { + return false + } + remaining && consume() == ')' + } + + private def parseOptionalQuantifier(): Boolean = { + if (!remaining) { + return true + } + peek match { + case '*' | '+' | '?' => + consume() + if (remaining && (peek == '+' || peek == '?')) { + // possessive or lazy + false + } else { + true + } + case '{' => parseCountedQuantifier() + case _ => true + } + } + + private def parseCountedQuantifier(): Boolean = { + consume() // '{' + val n = parseNonNegInt() match { + case Some(v) => v + case None => return false + } + if (!remaining) { + return false + } + peek match { + case '}' => + consume() + !isLazyOrPossessiveSuffix + case ',' => + consume() + if (!remaining) { + return false + } + if (peek == '}') { + consume() + !isLazyOrPossessiveSuffix + } else { + val m = parseNonNegInt() match { + case Some(v) => v + case None => return false + } + if (m < n) { + return false + } + remaining && consume() == '}' && !isLazyOrPossessiveSuffix + } + case _ => false + } + } + + private def isLazyOrPossessiveSuffix: Boolean = + remaining && (peek == '+' || peek == '?') + + private def parseNonNegInt(): Option[Int] = { + if (!remaining || !isAsciiDigit(peek)) { + return None + } + var v = 0L + while (remaining && isAsciiDigit(peek)) { + v = v * 10 + (consume() - '0') + if (v > Int.MaxValue) { + return None + } + } + Some(v.toInt) + } + + private def parseClass(): Boolean = { + consume() // '[' + if (remaining && peek == '^') { + consume() + } + var contentStarted = false + var lastAtom: Option[Char] = None + while (remaining && !(peek == ']' && contentStarted)) { + if (startsWith("&&") || peek == '[') { + return false + } + val ranging = lastAtom.isDefined && peek == '-' && peekOffset(1).exists(_ != ']') + if (ranging) { + consume() // '-' + parseClassAtom() match { + case Some(end) if end >= lastAtom.get => Review Comment: [P2] Reject ranges starting at an unescaped leading closing bracket The initial literal `]` is stored in `lastAtom` and then accepted as a range endpoint. For the admitted pattern `[]-a]`, Java/Spark interpret the range from `]` through `a`, but Rust treats this spelling as the literals `]`, `-`, and `a`. On both Spark 3.5.9 and 4.0.4, interpreted and generated evaluation return `true` for `_` and `false` for `-`; the locked native regex returns the opposite results. The negated form also differs. This default-native wrong-answer case contains neither `~~` nor `--`, so rejecting set operators alone will not fix it. Reject this class-boundary form, or normalize it only after establishing equivalent semantics, and cover both positive and negated variants. ########## spark/src/main/scala/org/apache/comet/expressions/CometRegex.scala: ########## @@ -0,0 +1,279 @@ +/* + * 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.comet.expressions + +import org.apache.comet.serde.{Compatible, Incompatible, SupportLevel} + +/** + * Regex flavor for [[CometRegex]]. The first version only implements [[RegexFlavor.RLike]]; later + * flavors (for example `regexp_replace` / `split`) can add extra reject rules such as empty-match + * divergence without changing the scanner's whitelist core. + */ +sealed trait RegexFlavor + +object RegexFlavor { + case object RLike extends RegexFlavor +} + +/** + * Plan-time whitelist analyzer for literal Java regex patterns. A pattern is [[Compatible]] only + * when every construct is one the analyzer positively recognizes as equivalent on Spark's + * `java.util.regex` engine and Comet's Rust `regex` crate. Anything unrecognized is + * [[Incompatible]]: the safe direction, so a missed construct never silently takes the native + * path. + * + * This is a recursive-descent scan, not a search for forbidden substrings. `[(?=]` is a character + * class of literals, not a lookahead; `\\d` is a literal backslash plus `d`, not a digit class. + */ +object CometRegex { + + def supportLevel(pattern: String, flavor: RegexFlavor = RegexFlavor.RLike): SupportLevel = { + flavor match { + case RegexFlavor.RLike => + val scanner = new Scanner(pattern) + if (scanner.parseExpr() && !scanner.remaining) { + Compatible() Review Comment: [P2] Preserve JVM routing for patterns beyond native compile limits Successful syntax scanning does not ensure `Regex::new` can compile the pattern. For example, this analyzer admits `[^;]{20000}` and `a{1000000}`; real Spark 3.5.9/4.0.4 evaluate them on a column containing `a` as `false`, but the locked Rust engine rejects both with `Compiled regex exceeds size limit of 10485760 bytes.` Nested counted repetitions have the same problem, and 251 nested groups exceed Rust's separate depth limit while succeeding in Spark. The unchanged `RLike::try_new` and native builder propagate these errors from plan creation, with no dispatcher retry, so previously successful default-config queries now fail without opt-in. Require conservative native size/depth applicability or a reliable compilation-validation/fallback path before returning `Compatible`. ########## spark/src/main/scala/org/apache/comet/expressions/CometRegex.scala: ########## @@ -0,0 +1,279 @@ +/* + * 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.comet.expressions + +import org.apache.comet.serde.{Compatible, Incompatible, SupportLevel} + +/** + * Regex flavor for [[CometRegex]]. The first version only implements [[RegexFlavor.RLike]]; later + * flavors (for example `regexp_replace` / `split`) can add extra reject rules such as empty-match + * divergence without changing the scanner's whitelist core. + */ +sealed trait RegexFlavor + +object RegexFlavor { + case object RLike extends RegexFlavor +} + +/** + * Plan-time whitelist analyzer for literal Java regex patterns. A pattern is [[Compatible]] only + * when every construct is one the analyzer positively recognizes as equivalent on Spark's + * `java.util.regex` engine and Comet's Rust `regex` crate. Anything unrecognized is + * [[Incompatible]]: the safe direction, so a missed construct never silently takes the native + * path. + * + * This is a recursive-descent scan, not a search for forbidden substrings. `[(?=]` is a character + * class of literals, not a lookahead; `\\d` is a literal backslash plus `d`, not a digit class. + */ +object CometRegex { + + def supportLevel(pattern: String, flavor: RegexFlavor = RegexFlavor.RLike): SupportLevel = { + flavor match { + case RegexFlavor.RLike => + val scanner = new Scanner(pattern) + if (scanner.parseExpr() && !scanner.remaining) { + Compatible() + } else { + Incompatible(None) + } + } + } + + private val MetaEscapes: Set[Char] = + Set('.', '*', '+', '?', '(', ')', '[', ']', '{', '}', '|', '^', '$', '\\') + + private class Scanner(pattern: String) { + private var i = 0 + + def remaining: Boolean = i < pattern.length + + private def peek: Char = pattern.charAt(i) + + private def peekOffset(n: Int): Option[Char] = { + val idx = i + n + if (idx < pattern.length) Some(pattern.charAt(idx)) else None + } + + private def consume(): Char = { + val c = peek + i += 1 + c + } + + private def startsWith(s: String): Boolean = pattern.startsWith(s, i) + + def parseExpr(): Boolean = { + if (!parseTerm()) { + return false + } + while (remaining && peek == '|') { + consume() + if (!parseTerm()) { + return false + } + } + true + } + + private def parseTerm(): Boolean = { + while (remaining && peek != '|' && peek != ')') { + if (!parseFactor()) { + return false + } + } + true + } + + private def parseFactor(): Boolean = { + if (!parseAtom()) { + return false + } + parseOptionalQuantifier() + } + + private def parseAtom(): Boolean = { + if (!remaining) { + return false + } + peek match { + case '\\' => parseEscape(inClass = false).isDefined + case '[' => parseClass() + case '(' => parseGroup() + case '.' | '^' | '$' | '*' | '+' | '?' | '{' | '}' | ')' | ']' | '|' => + false + case c if isPrintableAscii(c) => + consume() + true + case _ => false + } + } + + private def parseGroup(): Boolean = { + consume() // '(' + if (!remaining) { + return false + } + if (startsWith("?:")) { + i += 2 + } else if (peek == '?') { + // lookaround, flags, named groups, atomic groups, comments, ... + return false + } + if (!parseExpr()) { + return false + } + remaining && consume() == ')' + } + + private def parseOptionalQuantifier(): Boolean = { + if (!remaining) { + return true + } + peek match { + case '*' | '+' | '?' => + consume() + if (remaining && (peek == '+' || peek == '?')) { + // possessive or lazy + false + } else { + true + } + case '{' => parseCountedQuantifier() + case _ => true + } + } + + private def parseCountedQuantifier(): Boolean = { + consume() // '{' + val n = parseNonNegInt() match { + case Some(v) => v + case None => return false + } + if (!remaining) { + return false + } + peek match { + case '}' => + consume() + !isLazyOrPossessiveSuffix + case ',' => + consume() + if (!remaining) { + return false + } + if (peek == '}') { + consume() + !isLazyOrPossessiveSuffix + } else { + val m = parseNonNegInt() match { + case Some(v) => v + case None => return false + } + if (m < n) { + return false + } + remaining && consume() == '}' && !isLazyOrPossessiveSuffix + } + case _ => false + } + } + + private def isLazyOrPossessiveSuffix: Boolean = + remaining && (peek == '+' || peek == '?') + + private def parseNonNegInt(): Option[Int] = { + if (!remaining || !isAsciiDigit(peek)) { + return None + } + var v = 0L + while (remaining && isAsciiDigit(peek)) { + v = v * 10 + (consume() - '0') + if (v > Int.MaxValue) { + return None + } + } + Some(v.toInt) + } + + private def parseClass(): Boolean = { + consume() // '[' + if (remaining && peek == '^') { + consume() + } + var contentStarted = false + var lastAtom: Option[Char] = None + while (remaining && !(peek == ']' && contentStarted)) { + if (startsWith("&&") || peek == '[') { + return false + } Review Comment: [P2] Exclude Rust-only class operators from automatic native routing This gate rejects `&&` but admits `~~` and subtraction forms such as `[a-z--b]`. The pinned analyzer returns `Compatible` for `[a~~b]`; Spark 3.5.9/4.0.4 return `true` on subject `~`, while the locked Rust regex 1.13.1 returns `false` because `~~` is symmetric difference. Likewise, `[a-z--b]` matches `b` in Spark but not Rust. I verified the Spark results in both interpreted and generated evaluation with a non-foldable input. Since `CometRLike.convert` now sends these literals to the unchanged native matcher without `allowIncompatible=true`, existing projections and filters silently change results. Keep these class forms outside automatic admission and add differential/routing regressions before selecting native for them. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
