alibi-plugins 0.7.0

//! Fallible `JavaScriptCore` array ordering for cached metadata. Its relational
//! comparator can be cyclic, so comparison order is observable. Binary
//! insertion, natural runs, Powersort and galloping follow JSC's StableSort.h:
//! <https://github.com/WebKit/WebKit/blob/main/Source/JavaScriptCore/runtime/StableSort.h>
//! The behavior is verified against the installed, pinned Bun runtime.
// Copyright (C) 2024-2026 Apple Inc. All rights reserved.
// Copyright (C) 2018-2026 the V8 project authors. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Copyright (c) 2001-2018 Python Software Foundation; All Rights Reserved.
// Part of JavaScriptCore's galloping merge comes from Python's TimSort.

use alibi_core::{ApiKey, AuthError, AuthResult};
use std::slice::SliceIndex;

fn get<I: SliceIndex<[ApiKey]>>(keys: &[ApiKey], index: I) -> AuthResult<&I::Output> {
    keys.get(index)
        .ok_or_else(|| AuthError::internal("Invalid metadata sort range"))
}

fn get_mut<I: SliceIndex<[ApiKey]>>(keys: &mut [ApiKey], index: I) -> AuthResult<&mut I::Output> {
    keys.get_mut(index)
        .ok_or_else(|| AuthError::internal("Invalid metadata sort range"))
}

struct Order {
    descending: bool,
}

impl Order {
    fn less(&self, left: &ApiKey, right: &ApiKey) -> AuthResult<bool> {
        let ordering =
            super::compare_metadata(left.metadata.as_deref(), right.metadata.as_deref())?;
        Ok(if self.descending {
            ordering.is_gt()
        } else {
            ordering.is_lt()
        })
    }
}

fn insertion(keys: &mut [ApiKey], header: usize, order: &Order) -> AuthResult<()> {
    for index in header + 1..keys.len() {
        let mut left = 0;
        let mut right = index;
        while left < right {
            let middle = left + (right - left) / 2;
            if order.less(get(keys, index)?, get(keys, middle)?)? {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        get_mut(keys, left..=index)?.rotate_right(1);
    }
    Ok(())
}

fn run(keys: &mut [ApiKey], begin: usize, order: &Order) -> AuthResult<usize> {
    let mut end = begin;
    if end + 1 < keys.len() {
        let descending = order.less(get(keys, end + 1)?, get(keys, end)?)?;
        end += 1;
        while end + 1 < keys.len() {
            if order.less(get(keys, end + 1)?, get(keys, end)?)? != descending {
                break;
            }
            end += 1;
        }
        if descending {
            get_mut(keys, begin..=end)?.reverse();
        }
    }
    if end - begin < 8 {
        let size = 64.min(keys.len() - begin);
        insertion(get_mut(keys, begin..begin + size)?, end - begin, order)?;
        end = begin + size - 1;
    }
    while end + 1 < keys.len() && !order.less(get(keys, end + 1)?, get(keys, end)?)? {
        end += 1;
    }
    Ok(end)
}

/// Exponential then binary search, retaining JSC's comparator orientation.
fn gallop(
    key: &ApiKey,
    keys: &[ApiKey],
    hint: usize,
    after_equal: bool,
    order: &Order,
) -> AuthResult<usize> {
    let compare = |target: &ApiKey| {
        if after_equal {
            order.less(key, target)
        } else {
            order.less(target, key)
        }
    };
    let go_left = compare(get(keys, hint)?)? == after_equal;
    let mut last = 0;
    let mut offset = 1;
    let limit = if go_left { hint + 1 } else { keys.len() - hint };
    while offset < limit {
        let index = if go_left {
            hint - offset
        } else {
            hint + offset
        };
        if compare(get(keys, index)?)? == (after_equal != go_left) {
            break;
        }
        last = offset;
        offset = offset.saturating_mul(2).saturating_add(1).min(limit);
    }
    let (mut left, mut right) = if go_left {
        (hint + 1 - offset, hint - last)
    } else {
        (hint + last + 1, hint + offset)
    };
    while left < right {
        let middle = left + (right - left) / 2;
        if compare(get(keys, middle)?)? == after_equal {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    Ok(right)
}

fn merge(
    keys: &mut [ApiKey],
    working: &mut [ApiKey],
    begin: usize,
    middle: usize,
    end: usize,
    min_gallop: &mut usize,
    order: &Order,
) -> AuthResult<()> {
    let source = get(keys, begin..end)?;
    let destination = get_mut(working, begin..end)?;
    destination.clone_from_slice(source);
    let middle = middle - begin;
    let mut left = gallop(get(source, middle)?, get(source, ..middle)?, 0, true, order)?;
    if left == middle {
        return Ok(());
    }
    let right_end = middle
        + gallop(
            get(source, middle - 1)?,
            get(source, middle..)?,
            source.len() - middle - 1,
            false,
            order,
        )?;
    let mut right = middle;
    let mut output = left;
    'merging: while left < middle && right < right_end {
        let mut left_wins = 0;
        let mut right_wins = 0;
        while left_wins < *min_gallop && right_wins < *min_gallop {
            if left == middle || right == right_end {
                break 'merging;
            }
            let index = if order.less(get(source, right)?, get(source, left)?)? {
                right_wins += 1;
                left_wins = 0;
                let index = right;
                right += 1;
                index
            } else {
                left_wins += 1;
                right_wins = 0;
                let index = left;
                left += 1;
                index
            };
            get_mut(destination, output)?.clone_from(get(source, index)?);
            output += 1;
        }
        *min_gallop += 1;
        loop {
            *min_gallop = min_gallop.saturating_sub(1).max(1);
            if left == middle || right == right_end {
                break 'merging;
            }
            left_wins = gallop(
                get(source, right)?,
                get(source, left..middle)?,
                0,
                true,
                order,
            )?;
            get_mut(destination, output..output + left_wins)?
                .clone_from_slice(get(source, left..left + left_wins)?);
            output += left_wins;
            left += left_wins;
            get_mut(destination, output)?.clone_from(get(source, right)?);
            output += 1;
            right += 1;
            if left == middle || right == right_end {
                break 'merging;
            }
            right_wins = gallop(
                get(source, left)?,
                get(source, right..right_end)?,
                0,
                false,
                order,
            )?;
            get_mut(destination, output..output + right_wins)?
                .clone_from_slice(get(source, right..right + right_wins)?);
            output += right_wins;
            right += right_wins;
            get_mut(destination, output)?.clone_from(get(source, left)?);
            output += 1;
            left += 1;
            if left == middle || right == right_end {
                break 'merging;
            }
            if left_wins < 7 && right_wins < 7 {
                break;
            }
        }
        *min_gallop += 1;
    }
    for index in (left..middle).chain(right..right_end) {
        get_mut(destination, output)?.clone_from(get(source, index)?);
        output += 1;
    }
    get_mut(keys, begin..end)?.clone_from_slice(destination);
    Ok(())
}

pub(super) fn sort(keys: &mut [ApiKey], direction: Option<&str>) -> AuthResult<()> {
    let order = Order {
        descending: direction == Some("desc"),
    };
    if keys.len() < 8 {
        return insertion(keys, 0, &order);
    }
    let mut working = keys.to_vec();
    let mut min_gallop = 7;
    let mut stack: Vec<(usize, u32)> = Vec::new();
    let mut begin = 0;
    let mut end = run(keys, begin, &order)?;
    while end + 1 < keys.len() {
        let next_begin = end + 1;
        let next_end = run(keys, next_begin, &order)?;
        // Scaled adjacent run midpoints determine their Powersort tree depth.
        let first = ((begin as u128 + next_begin as u128) << 62) / keys.len() as u128;
        let second = ((next_begin as u128 + next_end as u128 + 1) << 62) / keys.len() as u128;
        let power = (first ^ second).leading_zeros();
        while stack.last().is_some_and(|(_, previous)| *previous > power) {
            if let Some((previous, _)) = stack.pop() {
                merge(
                    keys,
                    &mut working,
                    previous,
                    begin,
                    end + 1,
                    &mut min_gallop,
                    &order,
                )?;
                begin = previous;
            }
        }
        stack.push((begin, power));
        begin = next_begin;
        end = next_end;
    }
    while let Some((previous, _)) = stack.pop() {
        merge(
            keys,
            &mut working,
            previous,
            begin,
            end + 1,
            &mut min_gallop,
            &order,
        )?;
        begin = previous;
    }
    Ok(())
}

// LCOV_EXCL_START
#[cfg(test)]
mod tests {
    use super::*;

    fn key(index: usize, metadata: Option<&str>) -> ApiKey {
        serde_json::from_value(serde_json::json!({
            "id": index.to_string(),
            "key": index.to_string(),
            "referenceId": "user",
            "configId": "default",
            "enabled": true,
            "rateLimitEnabled": false,
            "createdAt": "2026-01-01T00:00:00.000Z",
            "updatedAt": "2026-01-01T00:00:00.000Z",
            "metadata": metadata,
        }))
        .unwrap()
    }

    fn patterns(length: usize) -> Vec<(&'static str, Vec<Option<String>>)> {
        let mut state = 0x2545_f491_4f6c_dd1d_u64;
        let mut random = move |modulus: u64| {
            state = state
                .wrapping_mul(6_364_136_223_846_793_005)
                .wrapping_add(1_442_695_040_888_963_407);
            (state >> 33) % modulus
        };
        let shaped = |shape: &dyn Fn(usize) -> Option<u64>| {
            (0..length)
                .map(|index| shape(index).map(|value| value.to_string()))
                .collect::<Vec<_>>()
        };
        let random_values = |modulus: u64, random: &mut dyn FnMut(u64) -> u64| {
            (0..length)
                .map(|_| Some(random(modulus).to_string()))
                .collect::<Vec<_>>()
        };
        let wide = random_values(1000, &mut random);
        let ties = random_values(3, &mut random);
        let sparse = (0..length)
            .map(|_| (random(4) == 0).then(|| random(5).to_string()))
            .collect();
        let mixed = (0..length)
            .map(|index| match index % 5 {
                0 => None,
                1 => Some(r#"{"a":1}"#.to_owned()),
                2 => Some(r#""text""#.to_owned()),
                3 => Some(random(10).to_string()),
                _ => Some("[1,2]".to_owned()),
            })
            .collect();
        vec![
            ("random", wide),
            ("ties", ties),
            ("sparse", sparse),
            ("ascending", shaped(&|index| Some(index as u64))),
            ("descending", shaped(&|index| Some((length - index) as u64))),
            (
                "blocks",
                shaped(&|index| ((index / 25) % 2 == 0).then_some(1)),
            ),
            (
                "interleaved runs",
                shaped(&|index| Some(((index % 50) * 2 + index / 50 % 2) as u64)),
            ),
            (
                "long left wins",
                shaped(&|index| {
                    Some(if index < length / 2 {
                        (index * 3) as u64
                    } else {
                        (index - length / 2) as u64 * 3 + 1
                    })
                }),
            ),
            (
                "organ pipe",
                shaped(&|index| Some(index.min(length - index) as u64)),
            ),
            ("mixed", mixed),
        ]
    }

    fn ids(keys: &[ApiKey]) -> Vec<String> {
        keys.iter().map(|key| key.id.clone()).collect()
    }

    #[test]
    fn matches_a_stable_sort_for_consistent_orderings() {
        for length in [0, 1, 7, 8, 9, 63, 64, 65, 100, 129, 200, 513] {
            for (name, metadata) in patterns(length) {
                if name == "mixed" {
                    continue;
                }
                for direction in [None, Some("asc"), Some("desc")] {
                    let keys = metadata
                        .iter()
                        .enumerate()
                        .map(|(index, metadata)| key(index, metadata.as_deref()))
                        .collect::<Vec<_>>();
                    let mut expected = keys.clone();
                    expected.sort_by(|left, right| {
                        let order = super::super::compare_metadata(
                            left.metadata.as_deref(),
                            right.metadata.as_deref(),
                        )
                        .unwrap();
                        if direction == Some("desc") {
                            order.reverse()
                        } else {
                            order
                        }
                    });
                    let mut sorted = keys;
                    sort(&mut sorted, direction).unwrap();
                    assert_eq!(
                        ids(&sorted),
                        ids(&expected),
                        "{name} {length} {direction:?}"
                    );
                }
            }
        }
    }

    #[test]
    fn mixed_types_keep_every_key() {
        let metadata = patterns(200)
            .into_iter()
            .find(|(name, _)| *name == "mixed")
            .unwrap()
            .1;
        let mut keys = metadata
            .into_iter()
            .enumerate()
            .map(|(index, metadata)| key(index, metadata.as_deref()))
            .collect::<Vec<_>>();
        sort(&mut keys, Some("desc")).unwrap();
        let mut sorted = ids(&keys);
        sorted.sort_by_key(|id| id.parse::<usize>().unwrap());
        assert_eq!(
            sorted,
            (0..200).map(|index| index.to_string()).collect::<Vec<_>>()
        );
    }
}
// LCOV_EXCL_STOP