jsonschema 0.49.6

use crate::canonical::ir::{drop_subsumed, BoundNumber, Divisors, NumberLeaf, Round, Side};

/// Number leaves kept sorted, pairwise unmergeable, and free of leaves another already admits.
/// Inserts are batched; the form is restored before any read, so the order in which leaves arrive
/// cannot change the result.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct NumberLeaves {
    leaves: Vec<NumberLeaf>,
    canonical: bool,
}

impl Default for NumberLeaves {
    fn default() -> Self {
        Self {
            leaves: Vec::new(),
            canonical: true,
        }
    }
}

impl NumberLeaves {
    pub(crate) fn insert(&mut self, leaf: NumberLeaf) {
        self.leaves.push(leaf);
        self.canonical = false;
    }

    fn canonicalize(&mut self) {
        if self.canonical {
            return;
        }
        let was_empty = self.leaves.is_empty();
        self.leaves = merge(std::mem::take(&mut self.leaves));
        // A coarser progression over a wider interval admits every value of a finer one.
        // e.g.  anyOf [
        //         {"type": "number", "multipleOf": 0.5},
        //         {"type": "number", "multipleOf": 1.5}
        //       ]  =>  {"type": "number", "multipleOf": 0.5}
        drop_subsumed(&mut self.leaves, |outer, inner| {
            covers(outer, inner)
                && outer.multiple_of.divide_all(&inner.multiple_of)
                && outer
                    .not_multiple_of
                    .bars_no_more_than(&inner.not_multiple_of)
                && (!outer.excludes_integers || inner.excludes_integers)
        });
        self.canonical = true;
        // `is_empty` reads the batch without canonicalizing, which relies on this.
        debug_assert_eq!(
            self.leaves.is_empty(),
            was_empty,
            "merging emptied the leaves"
        );
    }

    pub(crate) fn clear(&mut self) {
        self.leaves.clear();
        self.canonical = true;
    }

    /// Dropping intervals can neither reorder the rest nor make two of them mergeable.
    pub(crate) fn retain(&mut self, keep: impl FnMut(&NumberLeaf) -> bool) {
        self.canonicalize();
        self.leaves.retain(keep);
    }

    /// Merging never removes the last interval, so this reads the batch without canonicalizing.
    pub(crate) fn is_empty(&self) -> bool {
        self.leaves.is_empty()
    }

    pub(crate) fn as_slice(&mut self) -> &[NumberLeaf] {
        self.canonicalize();
        &self.leaves
    }
}

impl IntoIterator for NumberLeaves {
    type Item = NumberLeaf;
    type IntoIter = std::vec::IntoIter<NumberLeaf>;

    fn into_iter(mut self) -> Self::IntoIter {
        self.canonicalize();
        self.leaves.into_iter()
    }
}

/// Fold intervals that overlap or meet on an admitted point.
/// e.g.  anyOf [
///         {"type": "number", "minimum": 0, "maximum": 2},
///         {"type": "number", "minimum": 2, "maximum": 4}
///       ]  =>  {"type": "number", "minimum": 0, "maximum": 4}
///
/// A gap the progression steps across holds no admitted value either, so those intervals fold too.
/// e.g.  anyOf [
///         {"type": "number", "multipleOf": 1.5, "maximum": 3},
///         {"type": "number", "multipleOf": 1.5, "minimum": 4}
///       ]  =>  {"type": "number", "multipleOf": 1.5}
///
/// Two intervals meeting on a point neither admits leave a hole, so they stay apart.
/// e.g.  anyOf [
///         {"type": "number", "maximum": 2, "exclusiveMaximum": 2},
///         {"type": "number", "exclusiveMinimum": 2}
///       ]  =>  unchanged
///
/// Different divisors admit different values within one interval, so those leaves stay apart too.
/// e.g.  anyOf [
///         {"type": "number", "multipleOf": 0.5},
///         {"type": "number", "multipleOf": 0.75}
///       ]  =>  unchanged
fn merge(mut leaves: Vec<NumberLeaf>) -> Vec<NumberLeaf> {
    if leaves.len() < 2 {
        return leaves;
    }
    // Sort by divisor first so leaves sharing one are adjacent, then by where each interval starts:
    // an absent minimum is unbounded below, and on a shared limit the inclusive end starts earlier
    // than the excluded one.
    leaves.sort_by(|left, right| {
        left.multiple_of
            .cmp(&right.multiple_of)
            .then_with(|| left.not_multiple_of.cmp(&right.not_multiple_of))
            .then_with(|| left.excludes_integers.cmp(&right.excludes_integers))
            .then_with(|| match (&left.minimum, &right.minimum) {
                (Some(left), Some(right)) if left.to_number() == right.to_number() => {
                    right.is_inclusive().cmp(&left.is_inclusive())
                }
                (left, right) => left.cmp(right),
            })
    });
    let mut merged: Vec<NumberLeaf> = Vec::with_capacity(leaves.len());
    for leaf in leaves {
        match merged.last_mut() {
            Some(last)
                if last.multiple_of == leaf.multiple_of
                    && last.not_multiple_of == leaf.not_multiple_of
                    && last.excludes_integers == leaf.excludes_integers
                    && reaches(last, &leaf) =>
            {
                *last = hull(std::mem::take(last), leaf);
            }
            _ => merged.push(leaf),
        }
    }
    merged
}

/// Whether `outer` admits every real value `inner` does, divisors aside.
fn covers(outer: &NumberLeaf, inner: &NumberLeaf) -> bool {
    // Equal ends are tighter than each other, so only a strictly tighter outer end fails to cover.
    let wider = |outer: &BoundNumber, inner: &BoundNumber, side| {
        !outer.is_tighter_than(inner, side) || inner.is_tighter_than(outer, side)
    };
    let minimum = match (&outer.minimum, &inner.minimum) {
        (None, _) => true,
        (Some(_), None) => false,
        (Some(outer), Some(inner)) => wider(outer, inner, Side::Lower),
    };
    let maximum = match (&outer.maximum, &inner.maximum) {
        (None, _) => true,
        (Some(_), None) => false,
        (Some(outer), Some(inner)) => wider(outer, inner, Side::Upper),
    };
    minimum && maximum
}

/// Whether the two leave no value the leaf admits between them. `next` starts no lower than `last`.
fn reaches(last: &NumberLeaf, next: &NumberLeaf) -> bool {
    // The gap is read off `last` alone, which only a shared progression lets it speak for.
    debug_assert_eq!(
        last.multiple_of, next.multiple_of,
        "intervals compared under different divisors"
    );
    let (Some(end), Some(start)) = (&last.maximum, &next.minimum) else {
        return true;
    };
    let touches = if end.to_number() == start.to_number() {
        // They meet on one point, which closes the gap only if either side admits it.
        end.is_inclusive() || start.is_inclusive()
    } else {
        end.admits(&start.to_number(), Side::Upper)
    };
    touches || steps_over(&last.multiple_of, end, start)
}

/// Whether the progression carries no value into the gap the two ends leave. Only a lone divisor
/// gives a progression to walk, and a multiple no decimal spells leaves the answer unknown, which
/// keeps the intervals apart.
fn steps_over(divisor: &Divisors, end: &BoundNumber, start: &BoundNumber) -> bool {
    let Some(step) = divisor.sole() else {
        return false;
    };
    // The gap opens where the interval below it closes, so each end is admitted by the gap exactly
    // when the interval leaves it out.
    let opens = flipped(end);
    let closes = flipped(start);
    step.multiple_beyond(&opens, Round::Up)
        .is_some_and(|multiple| !closes.admits(&multiple.to_number(), Side::Upper))
}

/// The same limit with the value on it admitted the other way round.
fn flipped(bound: &BoundNumber) -> BoundNumber {
    BoundNumber::new(&bound.to_number(), !bound.is_inclusive())
}

/// The narrowest interval holding both. An absent bound is unbounded, so it swallows the present one.
fn hull(last: NumberLeaf, next: NumberLeaf) -> NumberLeaf {
    // Sorting put the wider minimum first, which is what lets `last` keep it unexamined.
    debug_assert!(
        !(last.minimum.is_some() && next.minimum.is_none()),
        "an unbounded minimum sorted after a bounded one"
    );
    // Equal bounds are tighter than each other, so only a strictly tighter one is out of order.
    debug_assert!(
        !matches!((&last.minimum, &next.minimum), (Some(left), Some(right))
            if left.is_tighter_than(right, Side::Lower)
                && !right.is_tighter_than(left, Side::Lower)),
        "the tighter minimum sorted first"
    );
    // `merge` folds only leaves carrying the same divisors, so `last` speaks for both.
    debug_assert_eq!(
        last.multiple_of, next.multiple_of,
        "folding intervals under different divisors"
    );
    debug_assert_eq!(
        last.not_multiple_of, next.not_multiple_of,
        "folding intervals under different exclusions"
    );
    debug_assert_eq!(
        last.excludes_integers, next.excludes_integers,
        "folding intervals under different integer exclusions"
    );
    NumberLeaf {
        multiple_of: last.multiple_of,
        not_multiple_of: last.not_multiple_of,
        excludes_integers: last.excludes_integers,
        minimum: last.minimum,
        maximum: match (last.maximum, next.maximum) {
            (Some(left), Some(right)) => Some(if left.is_tighter_than(&right, Side::Upper) {
                right
            } else {
                left
            }),
            _ => None,
        },
    }
}