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