## Coverage Report

#### Created: 2025-11-22 06:00

next uncovered line (L), next uncovered region (R), next uncovered branch (B)

    /Users/andrewlamb/Software/datafusion/datafusion/functions/src/string/levenshtein.rs

    Line
    Count
    Source
    1
    // Licensed to the Apache Software Foundation (ASF) under one
    2
    // or more contributor license agreements.  See the NOTICE file
    3
    // distributed with this work for additional information
    4
    // regarding copyright ownership.  The ASF licenses this file
    5
    // to you under the Apache License, Version 2.0 (the
    6
    // "License"); you may not use this file except in compliance
    7
    // with the License.  You may obtain a copy of the License at
    8
    //
    9
    //   http://www.apache.org/licenses/LICENSE-2.0
    10
    //
    11
    // Unless required by applicable law or agreed to in writing,
    12
    // software distributed under the License is distributed on an
    13
    // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    14
    // KIND, either express or implied.  See the License for the
    15
    // specific language governing permissions and limitations
    16
    // under the License.
    17
    18
    use std::any::Any;
    19
    use std::sync::Arc;
    20
    21
    use arrow::array::{ArrayRef, Int32Array, Int64Array, OffsetSizeTrait};
    22
    use arrow::datatypes::DataType;
    23
    24
    use crate::utils::{make_scalar_function, utf8_to_int_type};
    25
    use datafusion_common::cast::{as_generic_string_array, as_string_view_array};
    26
    use datafusion_common::types::logical_string;
    27
    use datafusion_common::utils::datafusion_strsim;
    28
    use datafusion_common::utils::take_function_args;
    29
    use datafusion_common::{exec_err, Result};
    30
    use datafusion_expr::type_coercion::binary::{
    31
        binary_to_string_coercion, string_coercion,
    32
    };
    33
    use datafusion_expr::{
    34
        Coercion, ColumnarValue, Documentation, ScalarFunctionArgs, ScalarUDFImpl, Signature,
    35
        TypeSignatureClass, Volatility,
    36
    };
    37
    use datafusion_macros::user_doc;
    38
    39
    #[user_doc(
    40
        doc_section(label = "String Functions"),
    41
        description = "Returns the [`Levenshtein distance`](https://en.wikipedia.org/wiki/Levenshtein_distance) between the two given strings.",
    42
        syntax_example = "levenshtein(str1, str2)",
    43
        sql_example = r#"```sql
    44
    > select levenshtein('kitten', 'sitting');
    45
    +---------------------------------------------+
    46
    | levenshtein(Utf8("kitten"),Utf8("sitting")) |
    47
    +---------------------------------------------+
    48
    | 3                                           |
    49
    +---------------------------------------------+
    50
    ```"#,
    51
        argument(
    52
            name = "str1",
    53
            description = "String expression to compute Levenshtein distance with str2."
    54
        ),
    55
        argument(
    56
            name = "str2",
    57
            description = "String expression to compute Levenshtein distance with str1."
    58
        )
    59
    )]
    60
    #[derive(Debug, PartialEq, Eq, Hash)]
    61
    pub struct LevenshteinFunc {
    62
        signature: Signature,
    63
    }
    64
    65
    impl Default for LevenshteinFunc {
    66
    0
        fn default() -> Self {
    67
    0
            Self::new()
    68
    0
        }
    69
    }
    70
    71
    impl LevenshteinFunc {
    72
    0
        pub fn new() -> Self {
    73
    0
            Self {
    74
    0
                signature: Signature::coercible(
    75
    0
                    vec![
    76
    0
                        Coercion::new_exact(TypeSignatureClass::Native(logical_string())),
    77
    0
                        Coercion::new_exact(TypeSignatureClass::Native(logical_string())),
    78
    0
                    ],
    79
    0
                    Volatility::Immutable,
    80
    0
                ),
    81
    0
            }
    82
    0
        }
    83
    }
    84
    85
    impl ScalarUDFImpl for LevenshteinFunc {
    86
    0
        fn as_any(&self) -> &dyn Any {
    87
    0
            self
    88
    0
        }
    89
    90
    0
        fn name(&self) -> &str {
    91
    0
            "levenshtein"
    92
    0
        }
    93
    94
    0
        fn signature(&self) -> &Signature {
    95
    0
            &self.signature
    96
    0
        }
    97
    98
    0
        fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> {
    99
    0
            if let Some(coercion_data_type) = string_coercion(&arg_types[0], &arg_types[1])
    100
    0
                .or_else(|| binary_to_string_coercion(&arg_types[0], &arg_types[1]))
    101
            {
    102
    0
                utf8_to_int_type(&coercion_data_type, "levenshtein")
    103
            } else {
    104
    0
                exec_err!("Unsupported data types for levenshtein. Expected Utf8, LargeUtf8 or Utf8View")
    105
            }
    106
    0
        }
    107
    108
    0
        fn invoke_with_args(&self, args: ScalarFunctionArgs) -> Result<ColumnarValue> {
    109
    0
            match args.args[0].data_type() {
    110
                DataType::Utf8View | DataType::Utf8 => {
    111
    0
                    make_scalar_function(levenshtein::<i32>, vec![])(&args.args)
    112
                }
    113
                DataType::LargeUtf8 => {
    114
    0
                    make_scalar_function(levenshtein::<i64>, vec![])(&args.args)
    115
                }
    116
    0
                other => {
    117
    0
                    exec_err!("Unsupported data type {other:?} for function levenshtein")
    118
                }
    119
            }
    120
    0
        }
    121
    122
    0
        fn documentation(&self) -> Option<&Documentation> {
    123
    0
            self.doc()
    124
    0
        }
    125
    }
    126
    127
    ///Returns the Levenshtein distance between the two given strings.
    128
    /// LEVENSHTEIN('kitten', 'sitting') = 3
    129
    0
    fn levenshtein<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
    130
    0
        let [str1, str2] = take_function_args("levenshtein", args)?;
    131
    132
    0
        if let Some(coercion_data_type) =
    133
    0
            string_coercion(args[0].data_type(), args[1].data_type()).or_else(|| {
    134
    0
                binary_to_string_coercion(args[0].data_type(), args[1].data_type())
    135
    0
            })
    136
        {
    137
    0
            let str1 = if str1.data_type() == &coercion_data_type {
    138
    0
                Arc::clone(str1)
    139
            } else {
    140
    0
                arrow::compute::kernels::cast::cast(&str1, &coercion_data_type)?
    141
            };
    142
    0
            let str2 = if str2.data_type() == &coercion_data_type {
    143
    0
                Arc::clone(str2)
    144
            } else {
    145
    0
                arrow::compute::kernels::cast::cast(&str2, &coercion_data_type)?
    146
            };
    147
    148
    0
            match coercion_data_type {
    149
                DataType::Utf8View => {
    150
    0
                    let str1_array = as_string_view_array(&str1)?;
    151
    0
                    let str2_array = as_string_view_array(&str2)?;
    152
    0
                    let result = str1_array
    153
    0
                        .iter()
    154
    0
                        .zip(str2_array.iter())
    155
    0
                        .map(|(string1, string2)| match (string1, string2) {
    156
    0
                            (Some(string1), Some(string2)) => {
    157
    0
                                Some(datafusion_strsim::levenshtein(string1, string2) as i32)
    158
                            }
    159
    0
                            _ => None,
    160
    0
                        })
    161
    0
                        .collect::<Int32Array>();
    162
    0
                    Ok(Arc::new(result) as ArrayRef)
    163
                }
    164
                DataType::Utf8 => {
    165
    0
                    let str1_array = as_generic_string_array::<T>(&str1)?;
    166
    0
                    let str2_array = as_generic_string_array::<T>(&str2)?;
    167
    0
                    let result = str1_array
    168
    0
                        .iter()
    169
    0
                        .zip(str2_array.iter())
    170
    0
                        .map(|(string1, string2)| match (string1, string2) {
    171
    0
                            (Some(string1), Some(string2)) => {
    172
    0
                                Some(datafusion_strsim::levenshtein(string1, string2) as i32)
    173
                            }
    174
    0
                            _ => None,
    175
    0
                        })
    176
    0
                        .collect::<Int32Array>();
    177
    0
                    Ok(Arc::new(result) as ArrayRef)
    178
                }
    179
                DataType::LargeUtf8 => {
    180
    0
                    let str1_array = as_generic_string_array::<T>(&str1)?;
    181
    0
                    let str2_array = as_generic_string_array::<T>(&str2)?;
    182
    0
                    let result = str1_array
    183
    0
                        .iter()
    184
    0
                        .zip(str2_array.iter())
    185
    0
                        .map(|(string1, string2)| match (string1, string2) {
    186
    0
                            (Some(string1), Some(string2)) => {
    187
    0
                                Some(datafusion_strsim::levenshtein(string1, string2) as i64)
    188
                            }
    189
    0
                            _ => None,
    190
    0
                        })
    191
    0
                        .collect::<Int64Array>();
    192
    0
                    Ok(Arc::new(result) as ArrayRef)
    193
                }
    194
    0
                other => {
    195
    0
                    exec_err!(
    196
    0
                        "levenshtein was called with {other} datatype arguments. It requires Utf8View, Utf8 or LargeUtf8."
    197
                    )
    198
                }
    199
            }
    200
        } else {
    201
    0
            exec_err!("Unsupported data types for levenshtein. Expected Utf8, LargeUtf8 or Utf8View")
    202
        }
    203
    0
    }
    204
    205
    #[cfg(test)]
    206
    mod tests {
    207
        use arrow::array::StringArray;
    208
    209
        use datafusion_common::cast::as_int32_array;
    210
    211
        use super::*;
    212
    213
        #[test]
    214
        fn to_levenshtein() -> Result<()> {
    215
            let string1_array =
    216
                Arc::new(StringArray::from(vec!["123", "abc", "xyz", "kitten"]));
    217
            let string2_array =
    218
                Arc::new(StringArray::from(vec!["321", "def", "zyx", "sitting"]));
    219
            let res = levenshtein::<i32>(&[string1_array, string2_array]).unwrap();
    220
            let result =
    221
                as_int32_array(&res).expect("failed to initialized function levenshtein");
    222
            let expected = Int32Array::from(vec![2, 3, 2, 3]);
    223
            assert_eq!(&expected, result);
    224
    225
            Ok(())
    226
        }
    227
    }