## 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/math/gcd.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 arrow::array::{new_null_array, ArrayRef, AsArray, Int64Array, PrimitiveArray};
    19
    use arrow::compute::try_binary;
    20
    use arrow::datatypes::{DataType, Int64Type};
    21
    use arrow::error::ArrowError;
    22
    use std::any::Any;
    23
    use std::mem::swap;
    24
    use std::sync::Arc;
    25
    26
    use datafusion_common::{exec_err, internal_datafusion_err, Result, ScalarValue};
    27
    use datafusion_expr::{
    28
        ColumnarValue, Documentation, ScalarFunctionArgs, ScalarUDFImpl, Signature,
    29
        Volatility,
    30
    };
    31
    use datafusion_macros::user_doc;
    32
    33
    #[user_doc(
    34
        doc_section(label = "Math Functions"),
    35
        description = "Returns the greatest common divisor of `expression_x` and `expression_y`. Returns 0 if both inputs are zero.",
    36
        syntax_example = "gcd(expression_x, expression_y)",
    37
        sql_example = r#"```sql
    38
    > SELECT gcd(48, 18);
    39
    +------------+
    40
    | gcd(48,18) |
    41
    +------------+
    42
    | 6          |
    43
    +------------+
    44
    ```"#,
    45
        standard_argument(name = "expression_x", prefix = "First numeric"),
    46
        standard_argument(name = "expression_y", prefix = "Second numeric")
    47
    )]
    48
    #[derive(Debug, PartialEq, Eq, Hash)]
    49
    pub struct GcdFunc {
    50
        signature: Signature,
    51
    }
    52
    53
    impl Default for GcdFunc {
    54
    0
        fn default() -> Self {
    55
    0
            Self::new()
    56
    0
        }
    57
    }
    58
    59
    impl GcdFunc {
    60
    0
        pub fn new() -> Self {
    61
    0
            Self {
    62
    0
                signature: Signature::uniform(
    63
    0
                    2,
    64
    0
                    vec![DataType::Int64],
    65
    0
                    Volatility::Immutable,
    66
    0
                ),
    67
    0
            }
    68
    0
        }
    69
    }
    70
    71
    impl ScalarUDFImpl for GcdFunc {
    72
    0
        fn as_any(&self) -> &dyn Any {
    73
    0
            self
    74
    0
        }
    75
    76
    0
        fn name(&self) -> &str {
    77
    0
            "gcd"
    78
    0
        }
    79
    80
    0
        fn signature(&self) -> &Signature {
    81
    0
            &self.signature
    82
    0
        }
    83
    84
    0
        fn return_type(&self, _arg_types: &[DataType]) -> Result<DataType> {
    85
    0
            Ok(DataType::Int64)
    86
    0
        }
    87
    88
    0
        fn invoke_with_args(&self, args: ScalarFunctionArgs) -> Result<ColumnarValue> {
    89
    0
            let args: [ColumnarValue; 2] = args.args.try_into().map_err(|_| {
    90
    0
                internal_datafusion_err!("Expected 2 arguments for function gcd")
    91
    0
            })?;
    92
    93
    0
            match args {
    94
    0
                [ColumnarValue::Array(a), ColumnarValue::Array(b)] => {
    95
    0
                    compute_gcd_for_arrays(&a, &b)
    96
                }
    97
    0
                [ColumnarValue::Scalar(ScalarValue::Int64(a)), ColumnarValue::Scalar(ScalarValue::Int64(b))] => {
    98
    0
                    match (a, b) {
    99
    0
                        (Some(a), Some(b)) => Ok(ColumnarValue::Scalar(ScalarValue::Int64(
    100
    0
                            Some(compute_gcd(a, b)?),
    101
                        ))),
    102
    0
                        _ => Ok(ColumnarValue::Scalar(ScalarValue::Int64(None))),
    103
                    }
    104
                }
    105
    0
                [ColumnarValue::Array(a), ColumnarValue::Scalar(ScalarValue::Int64(b))] => {
    106
    0
                    compute_gcd_with_scalar(&a, b)
    107
                }
    108
    0
                [ColumnarValue::Scalar(ScalarValue::Int64(a)), ColumnarValue::Array(b)] => {
    109
    0
                    compute_gcd_with_scalar(&b, a)
    110
                }
    111
    0
                _ => exec_err!("Unsupported argument types for function gcd"),
    112
            }
    113
    0
        }
    114
    115
    0
        fn documentation(&self) -> Option<&Documentation> {
    116
    0
            self.doc()
    117
    0
        }
    118
    }
    119
    120
    0
    fn compute_gcd_for_arrays(a: &ArrayRef, b: &ArrayRef) -> Result<ColumnarValue> {
    121
    0
        let a = a.as_primitive::<Int64Type>();
    122
    0
        let b = b.as_primitive::<Int64Type>();
    123
    0
        try_binary(a, b, compute_gcd)
    124
    0
            .map(|arr: PrimitiveArray<Int64Type>| {
    125
    0
                ColumnarValue::Array(Arc::new(arr) as ArrayRef)
    126
    0
            })
    127
    0
            .map_err(Into::into) // convert ArrowError to DataFusionError
    128
    0
    }
    129
    130
    0
    fn compute_gcd_with_scalar(arr: &ArrayRef, scalar: Option<i64>) -> Result<ColumnarValue> {
    131
    0
        match scalar {
    132
    0
            Some(scalar_value) => {
    133
    0
                let result: Result<Int64Array> = arr
    134
    0
                    .as_primitive::<Int64Type>()
    135
    0
                    .iter()
    136
    0
                    .map(|val| match val {
    137
    0
                        Some(val) => Ok(Some(compute_gcd(val, scalar_value)?)),
    138
    0
                        _ => Ok(None),
    139
    0
                    })
    140
    0
                    .collect();
    141
    142
    0
                result.map(|arr| ColumnarValue::Array(Arc::new(arr) as ArrayRef))
    143
            }
    144
    0
            None => Ok(ColumnarValue::Array(new_null_array(
    145
    0
                &DataType::Int64,
    146
    0
                arr.len(),
    147
    0
            ))),
    148
        }
    149
    0
    }
    150
    151
    /// Computes gcd of two unsigned integers using Binary GCD algorithm.
    152
    0
    pub(super) fn unsigned_gcd(mut a: u64, mut b: u64) -> u64 {
    153
    0
        if a == 0 {
    154
    0
            return b;
    155
    0
        }
    156
    0
        if b == 0 {
    157
    0
            return a;
    158
    0
        }
    159
    160
    0
        let shift = (a | b).trailing_zeros();
    161
    0
        a >>= a.trailing_zeros();
    162
        loop {
    163
    0
            b >>= b.trailing_zeros();
    164
    0
            if a > b {
    165
    0
                swap(&mut a, &mut b);
    166
    0
            }
    167
    0
            b -= a;
    168
    0
            if b == 0 {
    169
    0
                return a << shift;
    170
    0
            }
    171
        }
    172
    0
    }
    173
    174
    /// Computes greatest common divisor using Binary GCD algorithm.
    175
    0
    pub fn compute_gcd(x: i64, y: i64) -> Result<i64, ArrowError> {
    176
    0
        let a = x.unsigned_abs();
    177
    0
        let b = y.unsigned_abs();
    178
    0
        let r = unsigned_gcd(a, b);
    179
        // gcd(i64::MIN, i64::MIN) = i64::MIN.unsigned_abs() cannot fit into i64
    180
    0
        r.try_into().map_err(|_| {
    181
    0
            ArrowError::ComputeError(format!("Signed integer overflow in GCD({x}, {y})"))
    182
    0
        })
    183
    0
    }