Skip to main content

uqa_sql/expr/range/
construction.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Selected endpoint input, ordering and canonicalization share admitted range constructors.
8
9use super::{
10    CanonicalMultirange, CanonicalRange, Ordering, ProductionControl, Result, SQLError, Value,
11};
12use uqa_core::memory::{MemoryReservation, Produced, ProductionVec};
13
14mod ordering;
15
16/// A host constructor supplies already converted endpoints. An absent bound is unbounded; an empty range invokes neither endpoint input nor canonical support.
17pub enum RangeBoundsInput {
18    Empty,
19    Bounds {
20        lower: Produced<Option<Value>>,
21        upper: Produced<Option<Value>>,
22        lower_inclusive: bool,
23        upper_inclusive: bool,
24    },
25}
26
27impl RangeBoundsInput {
28    pub fn construct_with_operations<O: RangeConstruction + ?Sized>(
29        self,
30        operations: &O,
31        control: &ProductionControl<'_>,
32    ) -> Result<Produced<CanonicalRange<O::Identity>>> {
33        control.check()?;
34        match self {
35            Self::Empty => Ok(control.finish(
36                CanonicalRange::empty(operations.identity()),
37                control.empty_reservation(),
38            )?),
39            Self::Bounds {
40                lower,
41                upper,
42                lower_inclusive,
43                upper_inclusive,
44            } => range_from_bounds_with_operations(
45                lower,
46                upper,
47                lower_inclusive,
48                upper_inclusive,
49                operations,
50                control,
51            ),
52        }
53    }
54}
55
56/// Operations selected by the range definition, independently of its endpoint layout. Invocation state and effects belong to the caller; observation never uses this interface.
57pub trait RangeConstruction {
58    type Identity: Copy + Eq;
59
60    fn identity(&self) -> Self::Identity;
61
62    /// Whether the definition selected a canonical function. Adjacency may invoke it on the gap between disjoint bounds.
63    fn has_canonical_function(&self) -> bool;
64
65    /// Decode one present endpoint, including its selected input and domain checks.
66    fn input_bound(
67        &self,
68        value: &Value,
69        control: &ProductionControl<'_>,
70    ) -> Result<Produced<Value>>;
71
72    fn compare_bounds(
73        &self,
74        left: &Value,
75        right: &Value,
76        control: &ProductionControl<'_>,
77    ) -> Result<Ordering>;
78
79    /// Invoke the optional canonical function for a nonempty range. `None` retains the borrowed input unchanged; a replacement must own all its allocations under `control`. Returning SQL NULL is an invocation error, not `None`. The input's owner remains live throughout the call and cannot escape with an empty replacement lease.
80    fn canonicalize(
81        &self,
82        _range: &CanonicalRange<Self::Identity>,
83        _control: &ProductionControl<'_>,
84    ) -> Result<Option<Produced<CanonicalRange<Self::Identity>>>> {
85        Ok(None)
86    }
87}
88
89// The complete live value precedes its lease, including while endpoints move between work buffers.
90pub(super) struct RangeWorkspace<T> {
91    pub(super) value: T,
92    pub(super) memory: Option<MemoryReservation>,
93}
94
95impl<T> RangeWorkspace<T> {
96    pub(super) fn from_produced(value: Produced<T>) -> Self {
97        let (value, memory) = value.into_parts();
98        Self { value, memory }
99    }
100}
101
102/// Validate a range constructor's explicit flags argument. The two-argument constructor supplies `Some("[)")`; SQL NULL remains an error.
103pub fn range_bound_flags(flags: Option<&str>) -> Result<(bool, bool)> {
104    let Some(flags) = flags else {
105        return Err(SQLError::Routine {
106            sqlstate: "22000".into(),
107            message: "range constructor flags argument must not be null".into(),
108        });
109    };
110    match flags.as_bytes() {
111        [lower @ (b'[' | b'('), upper @ (b']' | b')')] => Ok((*lower == b'[', *upper == b']')),
112        _ => Err(SQLError::Diagnostic {
113            sqlstate: "42601".into(),
114            message: "invalid range bound flags".into(),
115            detail: None,
116            hint: Some("Valid values are \"[]\", \"[)\", \"(]\", and \"()\".".into()),
117        }),
118    }
119}
120
121/// Parse complete range syntax, then input the lower and upper endpoints in order. Already empty input does not invoke endpoint or canonical functions.
122pub fn parse_range_with_operations<O: RangeConstruction + ?Sized>(
123    text: &str,
124    operations: &O,
125    control: &ProductionControl<'_>,
126) -> Result<Produced<CanonicalRange<O::Identity>>> {
127    control.check()?;
128    let Some(input) = super::input::range(text, control)? else {
129        return Ok(control.finish(
130            CanonicalRange::empty(operations.identity()),
131            control.empty_reservation(),
132        )?);
133    };
134    let lower = parse_bound(input.lower, operations, control)?;
135    let upper = parse_bound(input.upper, operations, control)?;
136    range_from_bounds_with_operations(
137        lower,
138        upper,
139        input.lower_inclusive,
140        input.upper_inclusive,
141        operations,
142        control,
143    )
144}
145
146/// Construct from already coerced, admitted, non-NULL endpoints; `None` represents an unbounded endpoint. This does not repeat endpoint input or domain checks. Bounds are validated before the optional canonical call; the canonical result is returned without a second call or validation pass.
147pub fn range_from_bounds_with_operations<O: RangeConstruction + ?Sized>(
148    lower: Produced<Option<Value>>,
149    upper: Produced<Option<Value>>,
150    lower_inclusive: bool,
151    upper_inclusive: bool,
152    operations: &O,
153    control: &ProductionControl<'_>,
154) -> Result<Produced<CanonicalRange<O::Identity>>> {
155    control.check()?;
156    let lower_inclusive = lower_inclusive && lower.is_some();
157    let upper_inclusive = upper_inclusive && upper.is_some();
158    let (lower, lower_memory) = lower.into_parts();
159    let (upper, upper_memory) = upper.into_parts();
160    let mut owned = RangeWorkspace {
161        value: CanonicalRange {
162            subtype: operations.identity(),
163            lower,
164            upper,
165            lower_inclusive,
166            upper_inclusive,
167            empty: false,
168        },
169        memory: control.combine(lower_memory, upper_memory),
170    };
171    if bounds_are_empty(&owned.value, operations, control)? {
172        owned.value = CanonicalRange::empty(operations.identity());
173    } else if let Some(replacement) = canonicalize(&owned.value, operations, control)? {
174        return Ok(replacement);
175    }
176    Ok(control.finish(owned.value, owned.memory)?)
177}
178
179pub(super) fn bounds_are_empty<O: RangeConstruction + ?Sized>(
180    range: &CanonicalRange<O::Identity>,
181    operations: &O,
182    control: &ProductionControl<'_>,
183) -> Result<bool> {
184    Ok(match (&range.lower, &range.upper) {
185        (Some(lower), Some(upper)) => match operations.compare_bounds(lower, upper, control)? {
186            Ordering::Greater => {
187                return Err(SQLError::Routine {
188                    sqlstate: "22000".into(),
189                    message: "range lower bound must be less than or equal to range upper bound"
190                        .into(),
191                })
192            }
193            Ordering::Equal => !(range.lower_inclusive && range.upper_inclusive),
194            Ordering::Less => false,
195        },
196        _ => false,
197    })
198}
199
200fn canonicalize<O: RangeConstruction + ?Sized>(
201    range: &CanonicalRange<O::Identity>,
202    operations: &O,
203    control: &ProductionControl<'_>,
204) -> Result<Option<Produced<CanonicalRange<O::Identity>>>> {
205    control.check()?;
206    if !operations.has_canonical_function() {
207        return Ok(None);
208    }
209    let Some(replacement) = operations.canonicalize(range, control)? else {
210        control.check()?;
211        return Ok(None);
212    };
213    require_identity(&replacement, operations.identity())?;
214    let (value, memory) = replacement.into_parts();
215    Ok(Some(control.finish(value, memory)?))
216}
217
218/// Parse each member through the same range constructor before sorting and joining overlapping or adjacent members.
219pub fn parse_multirange_with_operations<O: RangeConstruction + ?Sized>(
220    text: &str,
221    operations: &O,
222    control: &ProductionControl<'_>,
223) -> Result<Produced<CanonicalMultirange<O::Identity>>> {
224    control.check()?;
225    let mut input = super::input::MultirangeInput::new(text, control)?;
226    let mut ranges = ProductionVec::new(*control);
227    while let Some(item) = input.next_range(control)? {
228        let range = parse_range_with_operations(item, operations, control)?;
229        if !range.empty {
230            ranges.push_produced(range)?;
231        }
232    }
233    multirange_from_ranges_with_operations(ranges.finish()?, operations, control)
234}
235
236/// Normalize already constructed members without repeating their input or canonical calls. Every union invokes the selected canonical operation once, as range construction does.
237pub fn multirange_from_ranges_with_operations<O: RangeConstruction + ?Sized>(
238    ranges: Produced<Vec<CanonicalRange<O::Identity>>>,
239    operations: &O,
240    control: &ProductionControl<'_>,
241) -> Result<Produced<CanonicalMultirange<O::Identity>>> {
242    let (ranges, memory) = ranges.into_parts();
243    normalize_ranges(ranges, operations, control, memory)
244}
245
246pub(super) fn normalize_ranges<O: RangeConstruction + ?Sized>(
247    ranges: impl IntoIterator<Item = CanonicalRange<O::Identity>>,
248    operations: &O,
249    control: &ProductionControl<'_>,
250    memory: Option<MemoryReservation>,
251) -> Result<Produced<CanonicalMultirange<O::Identity>>> {
252    let mut collecting = RangeWorkspace {
253        value: (ranges.into_iter(), ProductionVec::new(*control)),
254        memory,
255    };
256    let (input, ordered) = &mut collecting.value;
257    for range in input {
258        control.check()?;
259        require_identity(&range, operations.identity())?;
260        ordered.push_produced(control.finish(range, control.empty_reservation())?)?;
261    }
262    let (input, ordered) = collecting.value;
263    drop(input);
264    let mut ordered = RangeWorkspace::from_produced(ordered.finish()?);
265    ordered.memory = control.combine(collecting.memory, ordered.memory);
266    ordering::sort(&mut ordered.value, operations, control)?;
267    let mut normalized = ProductionVec::new(*control);
268    normalized.reserve(ordered.value.len())?;
269    let normalized = RangeWorkspace::from_produced(normalized.finish()?);
270    // The current canonical replacement can be superseded. Keep its lease separate from completed members, and drop live values before this lease on failure.
271    let mut active_memory = control.empty_reservation();
272    let mut merging = RangeWorkspace {
273        value: (ordered.value.into_iter(), normalized.value),
274        memory: control.combine(ordered.memory, normalized.memory),
275    };
276    let (input, normalized) = &mut merging.value;
277    for range in input {
278        control.check()?;
279        if range.empty {
280            continue;
281        }
282        let joins_previous = normalized
283            .last()
284            .map(|previous| joins(previous, &range, operations, control))
285            .transpose()?
286            .unwrap_or(false);
287        if joins_previous {
288            let previous = normalized.pop().expect("previous range");
289            if previous.empty {
290                drop(previous);
291                active_memory = control.empty_reservation();
292                normalized.push(range);
293                continue;
294            }
295            let merged = merge_owned(previous, range, operations, control)?;
296            if bounds_are_empty(&merged, operations, control)? {
297                drop(merged);
298                active_memory = control.empty_reservation();
299                normalized.push(CanonicalRange::empty(operations.identity()));
300            } else if let Some(replacement) = canonicalize(&merged, operations, control)? {
301                let (value, memory) = replacement.into_parts();
302                drop(merged);
303                active_memory = memory;
304                normalized.push(value);
305            } else {
306                normalized.push(merged);
307            }
308        } else {
309            merging.memory = control.combine(merging.memory.take(), active_memory.take());
310            active_memory = control.empty_reservation();
311            // Capacity was admitted for every input member before normalization.
312            normalized.push(range);
313        }
314    }
315    let (input, normalized) = merging.value;
316    drop(input);
317    Ok(control.finish(
318        CanonicalMultirange {
319            subtype: operations.identity(),
320            ranges: normalized,
321        },
322        control.combine(merging.memory, active_memory),
323    )?)
324}
325
326fn require_identity<I: PartialEq>(range: &CanonicalRange<I>, identity: I) -> Result<()> {
327    if range.subtype != identity {
328        return Err(SQLError::Routine {
329            sqlstate: "XX000".into(),
330            message: "range types do not match".into(),
331        });
332    }
333    Ok(())
334}
335
336fn parse_bound<O: RangeConstruction + ?Sized>(
337    input: Option<super::input::BoundInput<'_>>,
338    operations: &O,
339    control: &ProductionControl<'_>,
340) -> Result<Produced<Option<Value>>> {
341    let Some(input) = input else {
342        return Ok(control.finish(None, control.empty_reservation())?);
343    };
344    let (text, memory) = input.decode(control)?.into_parts();
345    let source = RangeWorkspace {
346        value: Value::Str(text),
347        memory,
348    };
349    let (value, memory) = operations.input_bound(&source.value, control)?.into_parts();
350    Ok(control.finish(Some(value), memory)?)
351}
352
353fn joins<O: RangeConstruction + ?Sized>(
354    left: &CanonicalRange<O::Identity>,
355    right: &CanonicalRange<O::Identity>,
356    operations: &O,
357    control: &ProductionControl<'_>,
358) -> Result<bool> {
359    // A canonical callback can return empty; union with it preserves the next member without another callback.
360    if left.empty {
361        return Ok(true);
362    }
363    Ok(match (left.upper(), right.lower()) {
364        (None, _) | (_, None) => true,
365        (Some(upper), Some(lower)) => match operations.compare_bounds(upper, lower, control)? {
366            Ordering::Less if operations.has_canonical_function() => {
367                let gap_lower = copy_bound(Some(upper), control)?;
368                let gap_upper = copy_bound(Some(lower), control)?;
369                range_from_bounds_with_operations(
370                    gap_lower,
371                    gap_upper,
372                    !left.upper_inclusive,
373                    !right.lower_inclusive,
374                    operations,
375                    control,
376                )?
377                .empty
378            }
379            Ordering::Less => false,
380            Ordering::Greater => true,
381            Ordering::Equal => left.upper_inclusive || right.lower_inclusive,
382        },
383    })
384}
385
386pub(super) fn copy_bound(
387    value: Option<&Value>,
388    control: &ProductionControl<'_>,
389) -> Result<Produced<Option<Value>>> {
390    match value {
391        Some(value) => {
392            let (value, memory) = control.copy_value(value)?.into_parts();
393            Ok(control.finish(Some(value), memory)?)
394        }
395        None => Ok(control.finish(None, control.empty_reservation())?),
396    }
397}
398
399fn merge_owned<O: RangeConstruction + ?Sized>(
400    mut left: CanonicalRange<O::Identity>,
401    mut right: CanonicalRange<O::Identity>,
402    operations: &O,
403    control: &ProductionControl<'_>,
404) -> Result<CanonicalRange<O::Identity>> {
405    if left.empty {
406        return Ok(right);
407    }
408    // PostgreSQL's union chooses the right operand when equal bounds have distinct physical spellings.
409    if super::comparison::compare_lower_bounds_by(&left, &right, control, |a, b, control| {
410        operations.compare_bounds(a, b, control)
411    })? != Ordering::Less
412    {
413        left.lower = right.lower.take();
414        left.lower_inclusive = right.lower_inclusive;
415    }
416    match (left.upper(), right.upper()) {
417        (None, _) => {}
418        (_, None) => {
419            left.upper = None;
420            left.upper_inclusive = false;
421        }
422        (Some(a), Some(b)) => match operations
423            .compare_bounds(a, b, control)?
424            .then_with(|| left.upper_inclusive.cmp(&right.upper_inclusive))
425        {
426            Ordering::Less | Ordering::Equal => {
427                left.upper = right.upper.take();
428                left.upper_inclusive = right.upper_inclusive;
429            }
430            Ordering::Greater => {}
431        },
432    }
433    Ok(left)
434}
435
436#[cfg(test)]
437mod tests;