nautilus_model/orderbook/

aggregation.rs

// -------------------------------------------------------------------------------------------------
//  Copyright (C) 2015-2025 Nautech Systems Pty Ltd. All rights reserved.
//  https://nautechsystems.io
//
//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
//  You may not use this file except in compliance with the License.
//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
//
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// -------------------------------------------------------------------------------------------------

//! Functions related to normalizing and processing top-of-book events.

use crate::{
    data::order::BookOrder,
    enums::{BookType, RecordFlag},
};

/// Generates a stable order ID from a price value.
///
/// # High-Precision Safety
///
/// Under the `high-precision` feature, `PriceRaw` is `i128` (up to ~1.7e29).
/// Casting to `u64` would truncate the upper bits, causing distinct prices to
/// collide on the same synthetic order_id, breaking L2/MBP aggregation.
///
/// This function uses deterministic AHash to compress i128 into u64:
/// - **Deterministic**: Fixed seeds (0,0,0,0) ensure the same price always maps to the same order_id.
/// - **Collision-resistant**: AHash provides high-quality 1-in-2^64 collision probability.
/// - **Correct**: No structural weaknesses; handles all i128 values uniformly.
/// - **Fast**: AHash is optimized for performance while maintaining hash quality.
///
/// # Collision Characteristics
///
/// By the pigeonhole principle, any i128→u64 mapping must have theoretical collisions.
/// However, AHash with fixed seeds ensures:
/// - Truly random 1-in-2^64 collision probability (no systematic patterns).
/// - For realistic orderbooks with ~1000 price levels: collision probability < 10^-15.
/// - No structural weaknesses at edge cases.
///
/// Order-book correctness is binary, so we use a high-quality deterministic hash to
/// push collision probability effectively to zero at negligible performance cost.
#[inline]
fn price_to_order_id(price_raw: i128) -> u64 {
    let build_hasher = ahash::RandomState::with_seeds(0, 0, 0, 0);
    build_hasher.hash_one(price_raw)
}

pub(crate) fn pre_process_order(book_type: BookType, mut order: BookOrder, flags: u8) -> BookOrder {
    match book_type {
        BookType::L1_MBP => order.order_id = order.side as u64,
        #[cfg(feature = "high-precision")]
        BookType::L2_MBP => order.order_id = price_to_order_id(order.price.raw),
        #[cfg(not(feature = "high-precision"))]
        BookType::L2_MBP => order.order_id = price_to_order_id(order.price.raw as i128),
        BookType::L3_MBO => {
            if flags == 0 {
            } else if RecordFlag::F_TOB.matches(flags) {
                order.order_id = order.side as u64;
            } else if RecordFlag::F_MBP.matches(flags) {
                #[cfg(feature = "high-precision")]
                {
                    order.order_id = price_to_order_id(order.price.raw);
                }
                #[cfg(not(feature = "high-precision"))]
                {
                    order.order_id = price_to_order_id(order.price.raw as i128);
                }
            }
        }
    };
    order
}

////////////////////////////////////////////////////////////////////////////////
// Tests
////////////////////////////////////////////////////////////////////////////////

#[cfg(test)]
mod tests {
    use std::{
        collections::HashSet,
        sync::{LazyLock, Mutex},
    };

    use nautilus_core::MUTEX_POISONED;
    use rstest::rstest;

    use super::*;

    #[rstest]
    fn test_price_to_order_id_deterministic() {
        let price1 = 123456789012345678901234567890_i128;
        let price2 = 987654321098765432109876543210_i128;

        // Same price should always produce same order_id
        let id1_a = price_to_order_id(price1);
        let id1_b = price_to_order_id(price1);
        assert_eq!(id1_a, id1_b, "Same price must produce same order_id");

        // Different prices should produce different order_ids
        let id2 = price_to_order_id(price2);
        assert_ne!(
            id1_a, id2,
            "Different prices should produce different order_ids"
        );

        // Verify determinism across multiple calls
        for _ in 0..100 {
            assert_eq!(price_to_order_id(price1), id1_a);
            assert_eq!(price_to_order_id(price2), id2);
        }
    }

    #[rstest]
    fn test_price_to_order_id_no_collisions() {
        use std::collections::HashSet;

        // Test that similar prices don't collide
        let base = 1000000000_i128;
        let mut seen = HashSet::new();

        for i in 0..1000 {
            let price = base + i;
            let id = price_to_order_id(price);
            assert!(seen.insert(id), "Collision detected for price {price}");
        }
    }

    #[rstest]
    fn test_price_to_order_id_no_collision_across_64bit_boundary() {
        // Test the specific collision case: price_raw = 1 vs price_raw = 1 << 64
        let price1 = 1_i128;
        let price2 = 1_i128 << 64; // This is 2^64

        let id1 = price_to_order_id(price1);
        let id2 = price_to_order_id(price2);

        assert_ne!(
            id1, id2,
            "Collision detected: price 1 and price 2^64 must have different order_ids"
        );
    }

    #[rstest]
    fn test_price_to_order_id_handles_negative_prices() {
        use std::collections::HashSet;

        let mut seen = HashSet::new();

        // Test negative prices including edge case of -2
        let negative_prices = vec![
            -1_i128,
            -2_i128,
            -100_i128,
            -1000000000_i128,
            i128::MIN,
            i128::MIN + 1,
        ];

        for &price in &negative_prices {
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected for negative price {price}"
            );
        }

        // Also verify negative prices don't collide with positive ones
        let positive_prices = vec![1_i128, 2_i128, 100_i128, 1000000000_i128, i128::MAX];

        for &price in &positive_prices {
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected between negative and positive price: {price}"
            );
        }
    }

    #[rstest]
    fn test_price_to_order_id_handles_large_values() {
        use std::collections::HashSet;

        let mut seen = HashSet::new();

        // Test values that exceed u64::MAX
        // Note: (u64::MAX + 1) and (1 << 64) are the same value (2^64)
        let large_values = vec![
            u64::MAX as i128, // 2^64 - 1
            1_i128 << 64,     // 2^64 (same as u64::MAX + 1)
            (u64::MAX as i128) + 1000,
            1_i128 << 65,  // 2^65
            1_i128 << 100, // 2^100
            i128::MAX - 1,
            i128::MAX,
        ];

        for &price in &large_values {
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected for large price value {price}"
            );
        }
    }

    #[rstest]
    fn test_price_to_order_id_multiples_of_2_pow_64() {
        use std::collections::HashSet;

        let mut seen = HashSet::new();

        // Test that multiples of 2^64 don't collide
        // These would all collapse to the same value with naive XOR folding
        for i in 0..10 {
            let price = i * (1_i128 << 64);
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected for price {price} (multiple of 2^64)"
            );
        }
    }

    #[rstest]
    fn test_price_to_order_id_realistic_orderbook_prices() {
        use std::collections::HashSet;

        let mut seen = HashSet::new();

        // Test realistic order book scenarios with fixed precision (9 decimals)
        // BTCUSD at ~$50,000 with 9 decimal precision
        let btc_base = 50000_000000000_i128;
        for i in -1000..1000 {
            let price = btc_base + i; // Prices from $49,999 to $50,001
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected for BTC price offset {i}"
            );
        }

        // EURUSD at ~1.1000 with 9 decimal precision
        let forex_base = 1_100000000_i128;
        for i in -10000..10000 {
            let price = forex_base + i; // Tight spreads
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected for EURUSD price offset {i}"
            );
        }

        // Crypto with high precision (e.g., DOGEUSDT at $0.10)
        let doge_base = 100000000_i128; // $0.10 with 9 decimals
        for i in -100000..100000 {
            let price = doge_base + i;
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected for DOGE price offset {i}"
            );
        }
    }

    #[rstest]
    fn test_price_to_order_id_edge_case_patterns() {
        use std::collections::HashSet;

        let mut seen = HashSet::new();

        // Test powers of 2 (common in binary representations)
        // Note: 1 << 127 produces i128::MIN (sign bit set), so this covers both positive and negative extremes
        for power in 0..128 {
            let price = 1_i128 << power;
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected for 2^{power} = {price}"
            );
        }

        // Test negative powers of 2
        // We stop at 126 because -(1 << 127) would overflow (can't negate i128::MIN)
        for power in 0..127 {
            let price = -(1_i128 << power);
            let id = price_to_order_id(price);
            assert!(
                seen.insert(id),
                "Collision detected for -2^{power} = {price}"
            );
        }
    }

    #[rstest]
    fn test_price_to_order_id_sequential_negative_values() {
        use std::collections::HashSet;

        let mut seen = HashSet::new();

        // Test sequential negative values (important for spread instruments)
        for i in -10000..=0 {
            let price = i as i128;
            let id = price_to_order_id(price);
            assert!(seen.insert(id), "Collision detected for price {i}");
        }
    }

    #[rstest]
    #[case::max(i128::MAX)]
    #[case::max_minus_1(i128::MAX - 1)]
    #[case::min(i128::MIN)]
    #[case::min_plus_1(i128::MIN + 1)]
    #[case::u64_max(u64::MAX as i128)]
    #[case::u64_max_minus_1((u64::MAX as i128) - 1)]
    #[case::u64_max_plus_1((u64::MAX as i128) + 1)]
    #[case::neg_u64_max(-(u64::MAX as i128))]
    #[case::neg_u64_max_minus_1(-(u64::MAX as i128) - 1)]
    #[case::neg_u64_max_plus_1(-(u64::MAX as i128) + 1)]
    #[case::zero(0_i128)]
    #[case::one(1_i128)]
    #[case::neg_one(-1_i128)]
    fn test_price_to_order_id_extreme_values_no_collision(#[case] price: i128) {
        // Each test case runs independently and checks that its price
        // produces a unique order_id by storing in a static set
        static SEEN: LazyLock<Mutex<HashSet<u64>>> = LazyLock::new(|| Mutex::new(HashSet::new()));

        let id = price_to_order_id(price);
        let mut seen = SEEN.lock().expect(MUTEX_POISONED);
        assert!(
            seen.insert(id),
            "Collision detected for extreme value: {price} (order_id: {id})"
        );
    }

    #[rstest]
    fn test_price_to_order_id_avalanche_effect() {
        // Test that small changes in price produce large changes in hash
        // (avalanche property)
        let base_price = 1000000000000_i128;
        let id1 = price_to_order_id(base_price);
        let id2 = price_to_order_id(base_price + 1);

        // Count differing bits
        let xor = id1 ^ id2;
        let differing_bits = xor.count_ones();

        // With good avalanche, ~50% of bits should differ for a 1-bit input change
        // We'll be lenient and require at least 20% (12 out of 64 bits)
        assert!(
            differing_bits >= 12,
            "Poor avalanche: only {differing_bits}/64 bits differ for adjacent prices"
        );
    }

    #[rstest]
    fn test_price_to_order_id_comprehensive_collision_check() {
        use std::collections::HashSet;

        // Comprehensive test combining all edge cases
        let mut seen = HashSet::new();
        let mut collision_count = 0;
        const TOTAL_TESTS: usize = 500_000;

        // Test 1: Dense range around zero
        for i in -100_000..100_000 {
            let id = price_to_order_id(i as i128);
            if !seen.insert(id) {
                collision_count += 1;
            }
        }

        // Test 2: Powers and near-powers of 2
        for power in 0..64 {
            for offset in -10..=10 {
                let price = (1_i128 << power) + offset;
                let id = price_to_order_id(price);
                if !seen.insert(id) {
                    collision_count += 1;
                }
            }
        }

        // Test 3: Realistic price levels
        for base in [100, 1000, 10000, 100000, 1000000, 10000000] {
            for i in 0..1000 {
                let price = base * 1_000_000_000_i128 + i;
                let id = price_to_order_id(price);
                if !seen.insert(id) {
                    collision_count += 1;
                }
            }
        }

        // Calculate collision rate
        let collision_rate = collision_count as f64 / TOTAL_TESTS as f64;

        // For a good 128→64 bit hash, collision rate should be negligible in realistic scenarios
        // This test uses pathological patterns (500k consecutive integers, powers of 2, etc.)
        // AHash provides truly random collision distribution with ~0.0007% rate for such dense patterns
        // Real orderbooks are sparse (~1000 levels) with collision probability < 10^-15
        assert!(
            collision_rate < 0.001,
            "High collision rate: {collision_rate:.6}% ({collision_count}/{TOTAL_TESTS})"
        );

        println!(
            "✓ Tested {} unique prices, {} collisions ({:.6}%)",
            TOTAL_TESTS,
            collision_count,
            collision_rate * 100.0
        );
    }
}