monty 0.0.21

//! Implementation of the min() and max() builtin functions.

use std::{cmp::Ordering, mem};

use crate::{
    args::{ArgValues, FromArgs},
    bytecode::VM,
    defer_drop, defer_drop_mut,
    exception_private::{ExcType, ExcTypeExt, RunError, RunResult, SimpleException},
    heap::DropGuard,
    types::{CmpOrder, PyTrait},
    value::Value,
};

/// Implementation of the min() builtin function.
///
/// Returns the smallest item in an iterable or the smallest of two or more arguments.
/// Supports two forms:
/// - `min(iterable)` - returns smallest item from iterable
/// - `min(arg1, arg2, ...)` - returns smallest of the arguments
pub fn builtin_min(vm: &mut VM<'_>, args: ArgValues) -> RunResult<Value> {
    let MinArgs { args, key, default } = MinArgs::from_args(args, vm)?;
    run_min_max(vm, args, key, default, true)
}

/// Implementation of the max() builtin function.
///
/// Returns the largest item in an iterable or the largest of two or more arguments.
/// Supports two forms:
/// - `max(iterable)` - returns largest item from iterable
/// - `max(arg1, arg2, ...)` - returns largest of the arguments
pub fn builtin_max(vm: &mut VM<'_>, args: ArgValues) -> RunResult<Value> {
    let MaxArgs { args, key, default } = MaxArgs::from_args(args, vm)?;
    run_min_max(vm, args, key, default, false)
}

/// Shared implementation for min() and max() after argument extraction.
///
/// When `is_min` is true, returns the minimum; otherwise returns the maximum.
fn run_min_max(
    vm: &mut VM<'_>,
    args: Vec<Value>,
    key: Value,
    default: Option<Value>,
    is_min: bool,
) -> RunResult<Value> {
    let func_name = if is_min { "min" } else { "max" };
    let key_context = if is_min {
        "min() key argument"
    } else {
        "max() key argument"
    };

    // Normalise `key=None` to "no key function" so the comparison path can
    // skip the call entirely.
    let key_fn = match key {
        Value::None => {
            key.drop_with(vm);
            None
        }
        _ => Some(key),
    };
    defer_drop!(key_fn, vm);

    defer_drop_mut!(default, vm);
    defer_drop_mut!(args, vm);

    if args.is_empty() {
        return Err(SimpleException::new_msg(
            ExcType::TypeError,
            format!("{func_name} expected at least 1 argument, got 0"),
        )
        .into());
    }

    let first_arg = args.remove(0);

    if args.is_empty() {
        // Single argument: iterate over it
        let iter = first_arg.into_py_iter(vm)?;
        defer_drop!(iter, vm);
        let mut iter = iter.read(vm);

        let Some(result) = iter.py_next(vm)? else {
            if let Some(default) = default.take() {
                return Ok(default);
            }
            return Err(SimpleException::new_msg(
                ExcType::ValueError,
                format!("{func_name}() iterable argument is empty"),
            )
            .into());
        };

        if let Some(key_fn) = key_fn {
            let mut result_guard = DropGuard::new(result, vm);
            {
                let (result, vm) = result_guard.as_parts_mut();
                let result_key = evaluate_key(result.clone_with_heap(vm), key_fn, key_context, vm)?;
                defer_drop_mut!(result_key, vm);

                while let Some(item) = iter.py_next(vm)? {
                    defer_drop_mut!(item, vm);
                    let item_key = evaluate_key(item.clone_with_heap(vm), key_fn, key_context, vm)?;
                    defer_drop_mut!(item_key, vm);

                    if candidate_wins(result_key, item_key, is_min, vm)? {
                        mem::swap(result, item);
                        mem::swap(result_key, item_key);
                    }
                }
            }
            Ok(result_guard.into_inner())
        } else {
            let mut result_guard = DropGuard::new(result, vm);
            let (result, vm) = result_guard.as_parts_mut();

            while let Some(item) = iter.py_next(vm)? {
                defer_drop_mut!(item, vm);

                if candidate_wins(result, item, is_min, vm)? {
                    mem::swap(result, item);
                }
            }

            Ok(result_guard.into_inner())
        }
    } else {
        // Multiple arguments: compare them directly
        if default.is_some() {
            first_arg.drop_with(vm);
            // The deferred drops release `default` and remaining arguments.
            return Err(default_with_multiple_args(func_name));
        }

        if let Some(key_fn) = key_fn {
            let mut result_guard = DropGuard::new(first_arg, vm);
            {
                let (result, vm) = result_guard.as_parts_mut();
                let result_key = evaluate_key(result.clone_with_heap(vm), key_fn, key_context, vm)?;
                defer_drop_mut!(result_key, vm);

                for item in args.drain(..) {
                    defer_drop_mut!(item, vm);
                    let item_key = evaluate_key(item.clone_with_heap(vm), key_fn, key_context, vm)?;
                    defer_drop_mut!(item_key, vm);

                    if candidate_wins(result_key, item_key, is_min, vm)? {
                        mem::swap(result, item);
                        mem::swap(result_key, item_key);
                    }
                }
            }
            Ok(result_guard.into_inner())
        } else {
            let mut result_guard = DropGuard::new(first_arg, vm);
            let (result, vm) = result_guard.as_parts_mut();

            for item in args.drain(..) {
                defer_drop_mut!(item, vm);

                if candidate_wins(result, item, is_min, vm)? {
                    mem::swap(result, item);
                }
            }

            Ok(result_guard.into_inner())
        }
    }
}

/// Argument shape for `min(*args, key=None, default=...)`.
///
/// `key` is held as `Value` so `key=None` can be normalised to "no key
/// function". `default` is `Option<Value>` (with `default` attr) so the
/// implementation can distinguish "not provided" from "provided with any
/// value" — that distinction matters because `default=` is only valid with a
/// single iterable argument.
#[derive(FromArgs)]
#[from_args(name = "min")]
struct MinArgs {
    #[from_args(varargs)]
    args: Vec<Value>,
    #[from_args(default = Value::None)]
    key: Value,
    #[from_args(default)]
    default: Option<Value>,
}

/// Argument shape for `max(*args, key=None, default=...)`.
///
/// See [`MinArgs`] for field semantics; the only difference is the function
/// name used in error messages.
#[derive(FromArgs)]
#[from_args(name = "max")]
struct MaxArgs {
    #[from_args(varargs)]
    args: Vec<Value>,
    #[from_args(default = Value::None)]
    key: Value,
    #[from_args(default)]
    default: Option<Value>,
}

/// Calls the user-provided key function for a single candidate value.
///
/// The caller passes an owned clone of the candidate so this helper can forward it
/// into the function call without changing ownership of the original item being
/// tracked as the eventual min/max result.
fn evaluate_key(item: Value, key_fn: &Value, key_context: &'static str, vm: &mut VM<'_>) -> RunResult<Value> {
    vm.evaluate_function(key_context, key_fn, ArgValues::One(item))
}

/// Returns whether `candidate` should replace `current` as the best value seen so far.
///
/// `min()` replaces the current winner when the new candidate compares smaller,
/// while `max()` replaces it when the new candidate compares larger. Equal values
/// keep the existing winner so ties preserve the first-seen item, matching CPython.
fn candidate_wins(current: &Value, candidate: &Value, is_min: bool, vm: &mut VM<'_>) -> RunResult<bool> {
    let ordering = match candidate.py_cmp(current, vm)? {
        CmpOrder::Ordered(ordering) => ordering,
        // A `NaN` candidate (or `NaN`-carrying container) is neither smaller nor
        // larger, so it never displaces the incumbent — matching CPython, where
        // `min`/`max` only swap on a strict `<`/`>` and `NaN` yields neither.
        CmpOrder::Unordered => return Ok(false),
        CmpOrder::Incomparable => return Err(ord_not_supported(candidate, current, is_min, vm)),
    };

    Ok((is_min && ordering == Ordering::Less) || (!is_min && ordering == Ordering::Greater))
}

/// Creates the CPython-compatible error for `default=` with multiple positional args.
#[cold]
fn default_with_multiple_args(func_name: &str) -> RunError {
    SimpleException::new_msg(
        ExcType::TypeError,
        format!("Cannot specify a default for {func_name}() with multiple positional arguments"),
    )
    .into()
}

#[cold]
fn ord_not_supported(left: &Value, right: &Value, is_min: bool, vm: &VM<'_>) -> RunError {
    let left_type = left.py_type_name(vm);
    let right_type = right.py_type_name(vm);
    let operator = if is_min { "<" } else { ">" };
    ExcType::type_error_ordering(operator, &left_type, &right_type)
}