sunchao commented on code in PR #5415: URL: https://github.com/apache/datafusion-comet/pull/5415#discussion_r3837609408
########## spark/src/main/scala/org/apache/comet/expressions/CometRegex.scala: ########## @@ -0,0 +1,344 @@ +/* + * 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().isDefined && !scanner.remaining) { + Compatible() + } else { + Incompatible(None) + } + } + } + + private val MetaEscapes: Set[Char] = + Set('.', '*', '+', '?', '(', ')', '[', ']', '{', '}', '|', '^', '$', '\\') + + // Conservative compile-size gates. Rust `regex` rejects large counted + // expansions and deep nesting; a single `{n}` cap is not enough because + // nested repetition multiplies. Stay well below crate defaults (nest 250). + private val MaxGroupDepth = 32 + private val MaxCountedBound = 256 + private val MaxExpansion = 4096L + + private class Scanner(pattern: String) { + private var i = 0 + private var groupDepth = 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) + + // Returns a conservative compiled-size estimate, or None if the construct + // is unrecognized or exceeds the compile budget. + def parseExpr(): Option[Long] = { + val first = parseTerm() match { + case Some(s) => s + case None => return None + } + var total = first + while (remaining && peek == '|') { + consume() + parseTerm() match { + case Some(s) => total = saturatingAdd(total, s) + case None => return None + } + } + Some(total) + } + + private def parseTerm(): Option[Long] = { + var total = 0L + var any = false + while (remaining && peek != '|' && peek != ')') { + parseFactor() match { + case Some(s) => + total = saturatingAdd(total, s) + any = true + case None => + return None + } + } + Some(if (any) total else 1L) + } + + private def parseFactor(): Option[Long] = { + val atomSize = parseAtom() match { + case Some(s) => s + case None => return None + } + parseOptionalQuantifier(atomSize) + } + + private def parseAtom(): Option[Long] = { + if (!remaining) { + return None + } + peek match { + case '\\' => + if (parseEscape(inClass = false).isDefined) Some(1L) else None + case '[' => + if (parseClass()) Some(1L) else None + case '(' => parseGroup() + case '.' | '^' | '$' | '*' | '+' | '?' | '{' | '}' | ')' | ']' | '|' => + None + case c if isPrintableAscii(c) => + consume() + Some(1L) + case _ => None + } + } + + private def parseGroup(): Option[Long] = { + consume() // '(' + if (!remaining) { + return None + } + if (startsWith("?:")) { + i += 2 + } else if (peek == '?') { + // lookaround, flags, named groups, atomic groups, comments, ... + return None + } + if (groupDepth >= MaxGroupDepth) { + return None + } + groupDepth += 1 + val inner = parseExpr() + val closed = remaining && consume() == ')' + groupDepth -= 1 + if (closed) inner else None + } + + private def parseOptionalQuantifier(atomSize: Long): Option[Long] = { + if (!remaining) { + return Some(atomSize) + } + peek match { + case '*' | '+' | '?' => + consume() + if (remaining && (peek == '+' || peek == '?')) { + // possessive or lazy + None + } else { + Some(atomSize) + } + case '{' => parseCountedQuantifier(atomSize) + case _ => Some(atomSize) + } + } + + private def parseCountedQuantifier(atomSize: Long): Option[Long] = { + consume() // '{' + val n = parseNonNegInt() match { + case Some(v) => v + case None => return None + } + if (n > MaxCountedBound) { + return None + } + if (!remaining) { + return None + } + val bound = peek match { + case '}' => + consume() + if (isLazyOrPossessiveSuffix) { + return None + } + n + case ',' => + consume() + if (!remaining) { + return None + } + if (peek == '}') { + consume() + if (isLazyOrPossessiveSuffix) { + return None + } + n + } else { + val m = parseNonNegInt() match { + case Some(v) => v + case None => return None + } + if (m < n || m > MaxCountedBound) { + return None + } + if (!(remaining && consume() == '}' && !isLazyOrPossessiveSuffix)) { + return None + } + m + } + case _ => + return None + } + val expanded = saturatingMul(atomSize, bound.toLong) + if (expanded > MaxExpansion) { + None + } else { + Some(expanded) + } + } + + private def saturatingAdd(a: Long, b: Long): Long = { + val s = a + b + if (s < 0) Long.MaxValue else s + } + + private def saturatingMul(a: Long, b: Long): Long = { + if (a != 0 && b > Long.MaxValue / a) { + Long.MaxValue + } else { + a * b + } + } + + 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)) { + // Rust class set ops (&& / ~~ / --) are not Java literals. Nested + // classes and unescaped `]` as an atom are also out of subset. + if (startsWith("&&") || startsWith("~~") || startsWith("--") || peek == '[') { + return false + } + val ranging = lastAtom.isDefined && peek == '-' && peekOffset(1).exists(_ != ']') + if (ranging) { + consume() // '-' + parseClassAtom() match { + case Some(end) if end >= lastAtom.get => + lastAtom = None + case _ => + return false + } + } else { + parseClassAtom() match { + case Some(c) => + lastAtom = Some(c) + contentStarted = true + case None => + return false + } + } + } + remaining && consume() == ']' + } + + private def parseClassAtom(): Option[Char] = { + if (!remaining) { + return None + } + // Unescaped `]` is only the class closer, never a range endpoint. Java + // treats a leading `]` as a literal/range start; Rust does not. + if (peek == ']') { + return None + } + if (peek == '\\') { + parseEscape(inClass = true) + } else if (isPrintableAscii(peek)) { Review Comment: [P2] Preserve Spark errors for raw `[` range endpoints The `[` guard in `parseClass` runs before the range branch consumes `-`, so this helper can still accept an unescaped `[` as the range endpoint. The exact scanner returns `Compatible` for `[@-[]` (and `[^@-[]`). With a non-foldable string input, real Spark 3.5.9 and 4.0.4 reject these patterns: interpreted RLIKE raises an invalid-pattern error, and forced generated-projection construction raises `PatternSyntaxException` for an unclosed character class. The locked Rust regex 1.13.1 instead compiles `[@-[]` and matches `A`. Because `CometRLike.convert` now trusts this admission result without incompatible opt-in, a malformed-pattern failure becomes a successful predicate under the default native route. Please reject raw `[` in the range-endpoint helper as well; the escaped `[@-\[]` control is valid and equivalent in both engines. -- 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]
