mbutrovich commented on code in PR #73:
URL: https://github.com/apache/datafusion-spark/pull/73#discussion_r4615328402
##########
crates/spark/src/function/string/regexp_extract.rs:
##########
@@ -0,0 +1,596 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+use std::collections::HashMap;
+use std::hash::{Hash, Hasher};
+use std::sync::{Arc, Mutex};
+
+use arrow::array::{
+ Array, ArrayRef, AsArray, Int32Array, StringArray, StringArrayType,
StringBuilder,
+ new_null_array,
+};
+use arrow::compute::{can_cast_types, cast};
+use arrow::datatypes::DataType;
+use datafusion_common::cast::as_int32_array;
+use datafusion_common::utils::offset_span_len;
+use datafusion_common::{
+ DataFusionError, Result, ScalarValue, exec_datafusion_err, exec_err,
+ internal_datafusion_err, internal_err, plan_err,
+};
+use datafusion_expr::{
+ ColumnarValue, Documentation, ScalarFunctionArgs, ScalarUDFImpl, Signature,
+ Volatility,
+};
+use datafusion_macros::user_doc;
+use regex::{CaptureLocations, Regex};
+
+use crate::function::error_utils::invalid_arg_count_exec_err;
+
+const NAME: &str = "regexp_extract";
+
+/// Spark-compatible `regexp_extract` expression.
+///
+/// <https://spark.apache.org/docs/latest/api/sql/index.html#regexp_extract>
+#[user_doc(
+ doc_section(label = "Regular Expression Functions"),
+ description = "Returns the text matched by group `idx` of the first match
of `regexp` in `str`. \
+ Unlike DataFusion's `regexp_match`, which returns a list of every
capture group, this returns a single string. \
+ Returns an empty string if there is no match, or if the group did not
take part in the match. \
+ `idx` is only checked when the pattern matches: an `idx` outside
`0..=groupCount` is an error \
+ (`INVALID_PARAMETER_VALUE.REGEX_GROUP_INDEX`, as in Spark 3.5 and
later; Spark 3.4 raised \
+ `_LEGACY_ERROR_TEMP_2006`/`2007`) on a row that matches, and an empty
string on a row that does not. \
+ An invalid pattern is an error (`INVALID_PARAMETER_VALUE.PATTERN`).
Returns NULL if any argument is NULL, \
+ and a NULL row is not checked, so an invalid pattern is only reported
on a row it is applied to. \
+ As in Spark, `str` and `regexp` are cast to strings and `idx` to INT. \
+ Known differences from Spark
(https://github.com/apache/datafusion-spark/issues/255): patterns use the Rust \
+ `regex` engine, not Java's `java.util.regex`. Look-around,
backreferences, quoting with `\\Q...\\E`, \
+ `\\Z`, `\\h`, atomic groups `(?>...)`, the `(?d)` flag, and patterns
that exceed the Rust engine's \
+ compiled-size limit raise an \"unsupported regex pattern\" error,
where Spark evaluates them. Only unclosed \
+ or unopened groups and classes, invalid class ranges and repetitions,
and unknown flags are reported as \
+ `INVALID_PARAMETER_VALUE.PATTERN`; any other pattern the Rust engine
rejects is reported as unsupported, \
+ including a few that Java rejects too, such as `\\y`. \
+ Possessive quantifiers are read as nested greedy repetition (`a++` as
`(a+)+`), so they can match \
+ where Java's would not. \
+ `\\d`, `\\w` and `\\s` match Unicode characters, where Java's match
only ASCII. \
+ `.` matches `\\r`, where Java's does not. `$` matches only at the very
end of the input, where Java's also \
+ matches before a final line terminator. `(?i)` folds case using
Unicode rules (so `k` matches the Kelvin \
+ sign), where Java folds only ASCII by default. Rust's `(?P<name>...)`
named groups are accepted, where Java \
+ rejects them as an invalid pattern.",
+ syntax_example = "regexp_extract(str, regexp[, idx])",
+ sql_example = r#"```sql
+> SELECT regexp_extract('1a 2b 14m', '(\d+)([a-z]+)');
+1
+> SELECT regexp_extract('1a 2b 14m', '(\d+)([a-z]+)', 0);
+1a
+> SELECT regexp_extract('1a 2b 14m', '(\d+)([a-z]+)', 2);
+a
+> SELECT regexp_extract('abc', '(\d+)', 1);
+-- empty string
+> SELECT regexp_extract('a1', '(\d+)', NULL);
+NULL
+```"#,
+ argument(
+ name = "str",
+ description = "String expression to search. Values of other types,
such as numbers and binary, are cast to a string. NULL returns NULL."
+ ),
+ argument(
+ name = "regexp",
+ description = "String regular expression in Rust `regex` syntax.
Values of other types are cast to a string. NULL returns NULL."
+ ),
+ argument(
+ name = "idx",
+ description = "Optional capture group index, cast to INT (numeric and
string values are accepted). Defaults to 1; 0 is the whole match. NULL returns
NULL."
+ )
+)]
+#[derive(Debug)]
+pub struct SparkRegexpExtract {
+ signature: Signature,
+ /// Literal patterns compiled by earlier batches. One instance serves every
+ /// query in a session, so the cache is keyed by pattern.
+ patterns: PatternCache,
+}
+
+// The cache does not affect the result, so two instances with the same
+// signature are equal.
+impl PartialEq for SparkRegexpExtract {
+ fn eq(&self, other: &Self) -> bool {
+ self.signature == other.signature
+ }
+}
+
+impl Eq for SparkRegexpExtract {}
+
+impl Hash for SparkRegexpExtract {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ self.signature.hash(state);
+ }
+}
+
+/// The literal patterns kept compiled. When it is full it is cleared, which
+/// bounds its size if many different literal patterns are used.
+const PATTERN_CACHE_SIZE: usize = 64;
+
+#[derive(Debug, Default)]
+struct PatternCache(Mutex<HashMap<String, Regex>>);
+
+impl PatternCache {
+ fn get_or_compile(&self, pattern: &str) -> Result<Regex> {
+ let lock = || {
+ self.0
+ .lock()
+ .unwrap_or_else(|poisoned| poisoned.into_inner())
+ };
+ if let Some(regex) = lock().get(pattern) {
+ return Ok(regex.clone());
+ }
+ let regex = compile(pattern)?;
+ let mut patterns = lock();
+ if patterns.len() >= PATTERN_CACHE_SIZE {
+ patterns.clear();
+ }
+ patterns.insert(pattern.to_string(), regex.clone());
+ Ok(regex)
+ }
+}
+
+impl Default for SparkRegexpExtract {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl SparkRegexpExtract {
+ pub fn new() -> Self {
+ Self {
+ signature: Signature::user_defined(Volatility::Immutable),
+ patterns: PatternCache::default(),
+ }
+ }
+}
+
+impl ScalarUDFImpl for SparkRegexpExtract {
+ fn name(&self) -> &str {
+ NAME
+ }
+
+ fn signature(&self) -> &Signature {
+ &self.signature
+ }
+
+ fn return_type(&self, _arg_types: &[DataType]) -> Result<DataType> {
+ Ok(DataType::Utf8)
+ }
+
+ fn documentation(&self) -> Option<&Documentation> {
+ self.doc()
+ }
+
+ fn coerce_types(&self, arg_types: &[DataType]) -> Result<Vec<DataType>> {
+ if !(2..=3).contains(&arg_types.len()) {
+ return Err(invalid_arg_count_exec_err(NAME, (2, 3),
arg_types.len()));
+ }
+ // Like Spark's implicit casts: str and regexp are cast to strings,
idx to INT.
+ let castable_to_string = |t: &DataType| {
+ *t == DataType::Null || (!t.is_nested() && can_cast_types(t,
&DataType::Utf8))
+ };
+ for (name, arg_type) in ["str", "regexp"].iter().zip(arg_types) {
+ if !castable_to_string(arg_type) {
+ return plan_err!("{NAME} expects a string {name}, got
{arg_type}");
+ }
+ }
+ let mut coerced = vec![DataType::Utf8, DataType::Utf8];
+ if let Some(idx) = arg_types.get(2) {
+ let castable_to_int = idx.is_numeric()
+ || matches!(
+ idx,
+ DataType::Null
+ | DataType::Utf8
+ | DataType::LargeUtf8
+ | DataType::Utf8View
+ );
+ if !castable_to_int {
+ return plan_err!("{NAME} expects an INT idx, got {idx}");
+ }
+ coerced.push(DataType::Int32);
+ }
+ Ok(coerced)
+ }
+
+ fn invoke_with_args(&self, args: ScalarFunctionArgs) ->
Result<ColumnarValue> {
+ let all_scalar = args
+ .args
+ .iter()
+ .all(|arg| matches!(arg, ColumnarValue::Scalar(_)));
+ let len = if all_scalar { 1 } else { args.number_rows };
+
+ // The usual call has a literal pattern and idx: keep those as scalars
so
+ // the pattern is compiled once and no per-row copies are allocated.
+ let pattern_column = match &args.args[1] {
+ ColumnarValue::Scalar(_) => None,
+ ColumnarValue::Array(array) => Some(to_utf8("regexp", array)?),
+ };
+ let pattern = match (&args.args[1], &pattern_column) {
+ (_, Some(patterns)) => Pattern::Array(patterns.as_string::<i32>()),
+ (ColumnarValue::Scalar(scalar), None) => match scalar_str(scalar)?
{
+ Some(pattern) => Pattern::Scalar(pattern),
+ None => return null_result(len, all_scalar),
+ },
+ (ColumnarValue::Array(_), None) => unreachable!("converted above"),
+ };
+ let index = match args.args.get(2) {
+ None => Index::Scalar(1),
+ Some(ColumnarValue::Scalar(ScalarValue::Int32(Some(idx)))) => {
+ Index::Scalar(*idx)
+ }
+ Some(ColumnarValue::Scalar(ScalarValue::Int32(None) |
ScalarValue::Null)) => {
+ return null_result(len, all_scalar);
+ }
+ Some(ColumnarValue::Scalar(other)) => {
+ return internal_err!(
+ "{NAME} expects an INT idx, got {}",
+ other.data_type()
+ );
+ }
+ Some(ColumnarValue::Array(array)) =>
Index::Array(as_int32_array(array)?),
+ };
+
+ // A caller that builds the physical expression directly, such as
Comet,
+ // can pass any string type. Each result is a substring of its input,
so
+ // the bytes of the visible input values bound the output.
+ let strings = args.args[0].to_array(len)?;
+ let result = match strings.data_type() {
+ DataType::Utf8 => {
+ let strings = strings.as_string::<i32>();
+ let capacity = offset_span_len(strings.offsets());
+ extract(strings, capacity, pattern, index, &self.patterns)?
+ }
+ DataType::LargeUtf8 => {
+ let strings = strings.as_string::<i64>();
+ let capacity = offset_span_len(strings.offsets());
+ extract(strings, capacity, pattern, index, &self.patterns)?
+ }
+ DataType::Utf8View => {
+ let strings = strings.as_string_view();
+ let capacity = strings.lengths().map(|len| len as usize).sum();
+ extract(strings, capacity, pattern, index, &self.patterns)?
+ }
+ other => return exec_err!("{NAME} expects a string str, got
{other}"),
+ };
+ if all_scalar {
+ Ok(ColumnarValue::Scalar(ScalarValue::try_from_array(
+ &result, 0,
+ )?))
+ } else {
+ Ok(ColumnarValue::Array(result))
+ }
+ }
+}
+
+#[derive(Clone, Copy)]
+enum Pattern<'a> {
+ Scalar(&'a str),
+ Array(&'a StringArray),
+}
+
+#[derive(Clone, Copy)]
+enum Index<'a> {
+ Scalar(i32),
+ Array(&'a Int32Array),
+}
+
+/// A pattern column as `Utf8`. Other string types are cast, and anything else
+/// is an error.
+fn to_utf8(name: &str, array: &ArrayRef) -> Result<ArrayRef> {
+ match array.data_type() {
+ DataType::Utf8 => Ok(Arc::clone(array)),
+ DataType::LargeUtf8 | DataType::Utf8View => Ok(cast(array,
&DataType::Utf8)?),
+ other => exec_err!("{NAME} expects a string {name}, got {other}"),
+ }
+}
+
+fn scalar_str(scalar: &ScalarValue) -> Result<Option<&str>> {
+ match scalar {
+ ScalarValue::Null => Ok(None),
+ other => other.try_as_str().ok_or_else(|| {
+ internal_datafusion_err!(
+ "{NAME} expects a string regexp, got {}",
+ other.data_type()
+ )
+ }),
+ }
+}
+
+fn null_result(len: usize, all_scalar: bool) -> Result<ColumnarValue> {
+ Ok(if all_scalar {
+ ColumnarValue::Scalar(ScalarValue::Utf8(None))
+ } else {
+ ColumnarValue::Array(new_null_array(&DataType::Utf8, len))
+ })
+}
+
+fn extract<'a, S: StringArrayType<'a> + Copy>(
+ strings: S,
+ capacity: usize,
+ pattern: Pattern,
+ index: Index,
+ cache: &PatternCache,
+) -> Result<ArrayRef> {
+ let mut builder = StringBuilder::with_capacity(strings.len(), capacity);
+ // A literal pattern comes from the cache on the first non-NULL row, so a
NULL
+ // row is not checked. A column pattern keeps only the last one compiled,
+ // since it rarely changes per row. The capture buffer is reused across
rows
+ // instead of allocated per match.
+ let mut cached: Option<(&str, Regex, CaptureLocations)> = None;
+
+ for row in 0..strings.len() {
+ let row_pattern = match pattern {
+ Pattern::Scalar(pattern) => Some(pattern),
+ Pattern::Array(patterns) => {
+ (!patterns.is_null(row)).then(|| patterns.value(row))
+ }
+ };
+ let idx = match index {
+ Index::Scalar(idx) => Some(idx),
+ Index::Array(indexes) => (!indexes.is_null(row)).then(||
indexes.value(row)),
+ };
+ let (false, Some(pattern_str), Some(idx)) =
+ (strings.is_null(row), row_pattern, idx)
+ else {
+ builder.append_null();
+ continue;
+ };
+ let (_, regex, locations) = match &mut cached {
+ Some(entry) if entry.0 == pattern_str => entry,
+ _ => {
+ let regex = match pattern {
+ Pattern::Scalar(_) => cache.get_or_compile(pattern_str)?,
+ Pattern::Array(_) => compile(pattern_str)?,
+ };
+ let locations = regex.capture_locations();
+ cached.insert((pattern_str, regex, locations))
+ }
+ };
+ let subject = strings.value(row);
+ // Like Spark, idx is only checked when the pattern matches.
+ let text = match regex.captures_read(locations, subject) {
+ None => "",
+ Some(_) => locations
+ .get(check_group_index(regex, idx)?)
+ .map_or("", |(start, end)| &subject[start..end]),
+ };
+ builder.append_value(text);
+ }
+ Ok(Arc::new(builder.finish()))
+}
+
+fn check_group_index(regex: &Regex, idx: i32) -> Result<usize> {
+ let group_count = regex.captures_len() - 1;
+ usize::try_from(idx)
+ .ok()
+ .filter(|group| *group <= group_count)
+ .ok_or_else(|| {
+ exec_datafusion_err!(
+ "[INVALID_PARAMETER_VALUE.REGEX_GROUP_INDEX] The value of
parameter(s) \
+ `idx` in `{NAME}` is invalid: Expects group index between 0
and \
+ {group_count}, but got {idx}. SQLSTATE: 22023"
+ )
+ })
+}
+
+fn compile(pattern: &str) -> Result<Regex> {
+ Regex::new(pattern).map_err(|err| {
+ let quoted = to_sql_value(pattern);
+ match unsupported_reason(pattern, &err) {
+ Some(reason) => DataFusionError::NotImplemented(format!(
+ "Unsupported regex pattern {quoted} in `{NAME}`: {reason}. \
+ See https://github.com/apache/datafusion-spark/issues/255"
+ )),
+ None => exec_datafusion_err!(
+ "[INVALID_PARAMETER_VALUE.PATTERN] The value of parameter(s)
`regexp` in \
+ `{NAME}` is invalid: {quoted}. SQLSTATE: 22023"
+ ),
+ }
+ })
+}
Review Comment:
> Every pattern is now parsed and walked before it is compiled.
Every pattern in my table now errors, and `(?R)a$` and `\b{start}abc` get
Spark's exact message.
[`visit_pre`](https://github.com/apache/datafusion-spark/blob/9a984b9c24312b8d897b35a17bd2a917c4fbe111/crates/spark/src/function/string/regexp_extract.rs#L545-L588)
doesn't look at repetitions or literals yet, so these still compile and return
something other than Spark's result. PySpark 4.2.0 gives the same results with
ANSI mode on and off:
| Pattern | Subject | Spark 4.2.0 | This PR |
|---|---|---|---|
| `a++a` | `aaa` | empty string | `aaa` |
| `\d++\d` | `123` | empty string | `123` |
| `a{2}+` | `aaaa` | `aa` | `aaaa` |
| `a{2}{3}` | `aaaaaa` | `aa` | `aaaaaa` |
| `a**` | `aa` | `INVALID_PARAMETER_VALUE.PATTERN` | `aa` |
| `\v` | `a`, newline, `b` | newline | empty string |
| `\u{41}` | `A` | `INVALID_PARAMETER_VALUE.PATTERN` | `A` |
| `\U00000041` | `A` | `INVALID_PARAMETER_VALUE.PATTERN` | `A` |
Java reads a quantifier followed by `+` as possessive (it never gives back
what it matched), and rejects `a**` and most other stacked quantifiers. The
Rust parser reads all of them as a repetition of a repetition (`a++` as
`(a+)+`). Java's `\v` is any vertical whitespace,
`[\n\x0B\f\r\x85\u2028\u2029]` in the [`Pattern`
docs](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/regex/Pattern.html),
where Rust's is U+000B only. Java has no `\u{...}`, `\U{...}`, or `\UXXXXXXXX`
escapes.
Could `visit_pre` report these too? For example:
```rust
// Java reads `a++`, `a*+`, `a?+` and `a{2}+` as possessive, and rejects or
// reads differently any other quantifier applied to a quantifier.
Ast::Repetition(rep) if matches!(*rep.ast, Ast::Repetition(_)) => {
Err(JavaDifference::Unsupported(
"Java reads a quantifier after a quantifier as possessive, or
rejects it"
.to_string(),
))
}
Ast::Literal(literal) => Self::check_literal(literal),
```
```rust
fn check_literal(literal: &Literal) -> Result<(), JavaDifference> {
match literal.kind {
LiteralKind::Special(SpecialLiteralKind::VerticalTab) => {
Err(JavaDifference::Unsupported(
"Java's \\v matches any vertical whitespace, where the Rust
regex \
engine's matches only U+000B"
.to_string(),
))
}
// Java has no \u{...}, \U{...} or \UXXXXXXXX.
LiteralKind::HexBrace(HexLiteralKind::UnicodeShort |
HexLiteralKind::UnicodeLong)
| LiteralKind::HexFixed(HexLiteralKind::UnicodeLong) =>
Err(JavaDifference::Invalid),
_ => Ok(()),
}
}
```
[`visit_class_set_item_pre`](https://github.com/apache/datafusion-spark/blob/9a984b9c24312b8d897b35a17bd2a917c4fbe111/crates/spark/src/function/string/regexp_extract.rs#L590-L603)
would need the same literal check for `ClassSetItem::Literal` and both ends of
a `ClassSetItem::Range`, because Java's `[\v]` matches U+2028 and Rust's
doesn't. A lazy quantifier (`a+?`) parses as one repetition, so it stays
accepted. `a**` and the other stacked quantifiers that Java rejects would get
the unsupported error, the way `\y` does now. The doc's sentence about
possessive quantifiers would then move to the unsupported list.
--
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]