Skip to main content

ingraph/ordering/
lower.rs

1//! The interpretation → level-sequence map: [`ToDatabaseOrderBy`], the refinement an emitted order
2//! CROSSES through ([`ToCrossedOrderBy`]), and the [`OrderLevel`] both are written in.
3//!
4//! This is the ORDER axis's twin of [`comparison::lower`](crate::comparison::lower), and the
5//! geography is deliberately the same: a marker-keyed map per dialect, and a refinement beside it
6//! carrying what an emitted expansion actually CALLS. What differs is the answer's kind. A filter's
7//! crossing names a TYPE — the comparison it becomes — so its map carries an associated type and
8//! pays the four bound walls that type costs at a generic dialect. An order's crossing names a
9//! SEQUENCE, which is data, so this map carries a `const` and there is no projection for a `where`
10//! clause to normalise.
11//!
12//! That difference is recorded rather than glossed, because it decides how much of the comparison
13//! family's machinery is REAL here. [`ToCrossedComparison`](crate::comparison::ToCrossedComparison)
14//! puts its crossing on METHODS to keep a projection off every bound — four measured errors are why.
15//! [`ToCrossedOrderBy`] keeps the method SHAPE without the wall behind it: nothing in its signature
16//! is a projection, so a caller at a generic `Db` was never going to be asked what the SQL family
17//! demands of one. The shape is kept because the day a level sequence becomes a TYPE — a dialect
18//! that lowers an order into its own sort document rather than into this crate's terms — the seat is
19//! already the one that survives that change, and a caller written against it does not move.
20
21use crate::{
22  ColumnKind,
23  comparison::Backend,
24  marker::{
25    BoolMarker, BytesMarker, CompositeMarker, DurationMarker, EnumMarker, ListMarker, Marker,
26    NullableMarker, OptionalMarker, QuantifiedMarker, ScalarMarker, SetMarker, StringMarker,
27  },
28  state::{Extracted, Inner, State},
29};
30
31/// ONE level of the order a single wire term runs in: WHICH of the column type's leaves this level
32/// sorts by, as an ordinal into that type's own [`SEGMENTS`](crate::ColumnKind::SEGMENTS).
33///
34/// # An ordinal rather than a name, and the reason is the joining law
35///
36/// A leaf's COLUMN NAME is never spelled in this crate: `at_nanos` is
37/// [`Backend::write_column`](crate::Backend::write_column)'s join of the field's name and the
38/// segment's, made once so that a `SELECT`, a `WHERE` and an `ORDER BY` are one join rather than
39/// three concatenations free to differ. A level that named its leaf by string would be a second
40/// joining rule and the first thing to drift. An ordinal names the same leaf through the walk that
41/// already renders it.
42///
43/// The numbering is the LEAF numbering — the one [`width`](crate::width) counts and
44/// [`OrderTerm::width`](crate::OrderTerm::width) iterates — and NOT the segment-list index. A nested
45/// composite contributes its own leaves, so `MediaTimestamp`'s three segments are four levels:
46/// `pts` is `0`, the timebase's `num` and `den` are `1` and `2`, and the derived `nanos` is `3`.
47///
48/// # A newtype rather than a bare `usize`
49///
50/// A leaf ordinal and a level ordinal are two numberings of one term that are equal only by
51/// accident, and both are `usize`. Wrapping the one a type DECLARES is what keeps a sequence written
52/// in the wrong numbering from compiling — the house rule a [`TermName`](crate::TermName) beside a
53/// [`FieldName`](crate::FieldName) already states one seam over.
54#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
55pub struct OrderLevel(usize);
56
57impl OrderLevel {
58  /// The level sorting by the `leaf`-th column of the type's own segment tree.
59  ///
60  /// `const`, because a type's order sequence is declared once, with the type, and is read from a
61  /// `const` item — the same shape [`ColumnKind::SEGMENTS`](crate::ColumnKind::SEGMENTS) is written
62  /// in.
63  #[inline]
64  #[must_use]
65  pub const fn new(leaf: usize) -> Self {
66    Self(leaf)
67  }
68
69  /// Which leaf this level sorts by.
70  #[inline]
71  #[must_use]
72  pub const fn leaf(self) -> usize {
73    self.0
74  }
75}
76
77/// An INTERPRETATION mapped to the LEVEL SEQUENCE one wire term over it sorts by, at one backend.
78///
79/// Implemented for the markers in [`crate::marker`] and for nothing else — [`ToGraphqlFilter`]'s
80/// keying, for [`ToGraphqlFilter`]'s reason: a type does not determine its own reading, so a trait
81/// keyed on the type would answer once, for the declarer. A declaration reaches this through
82/// [`DefaultMarker`](crate::DefaultMarker).
83///
84/// # The EMPTY sequence is the DECLARATION ORDER, and it is the default for that reason
85///
86/// Almost every reading sorts by its leaves in the sequence the type declares them, and a scalar —
87/// one leaf — cannot sort any other way. So `&[]` is the answer that means *the segments, as
88/// declared*, exactly as an empty [`SEGMENTS`](crate::ColumnKind::SEGMENTS) is the answer that means
89/// *one column*. A reading that states nothing here is behaviourally identical to what this
90/// framework rendered before the map existed, which is what makes the map's arrival a
91/// no-op for every existing declaration.
92///
93/// # Where a NON-default sequence comes from, and why it is not stated here
94///
95/// The type's own, through [`ColumnKind::ORDER`](crate::ColumnKind::ORDER). A composite citizen
96/// declares what it is stored as and, beside it, what ORDER those columns mean — which is one fact
97/// about one type, written where the other one is. A row here that named a citizen would be this
98/// map deciding a downstream type's semantics, which is the closed surface the framework refuses
99/// everywhere else: a downstream citizen teaches its own order by overriding a const in the
100/// [`ColumnKind`](crate::ColumnKind) impl it already writes, with no second registration to
101/// remember.
102///
103/// # `Db` is a parameter even where every dialect agrees today
104///
105/// All three shipped SQL dialects sort a composite's leaves the same way, so every row below ignores
106/// its parameter. It is carried all the same, for
107/// [`ToDatabaseComparison`](crate::ToDatabaseComparison)'s reason one axis over: what a dialect
108/// SORTS BY is a dialect's answer, and a document family that nests a composite rather than
109/// flattening it has a genuinely different sequence to give. A map without the parameter would have
110/// to grow one the day that row is written, and every caller would move with it.
111///
112/// [`ToGraphqlFilter`]: crate::ToGraphqlFilter
113pub trait ToDatabaseOrderBy<Db: Backend> {
114  /// The leaves one wire term over this reading sorts by, in ORDER sequence — EMPTY for the
115  /// declaration order, which is every reading's answer but a semantic citizen's.
116  const LEVELS: &'static [OrderLevel] = &[];
117}
118
119// The FLAT readings, and every one of them takes the declaration order. A scalar, a string, a byte
120// string, an enum, a boolean and a duration are each ONE column, so there is no sequence for a row
121// here to permute — the empty answer is not a deferral but the only order one column has.
122impl<T, Db: Backend> ToDatabaseOrderBy<Db> for ScalarMarker<T> {}
123
124impl<T, Db: Backend> ToDatabaseOrderBy<Db> for StringMarker<T> {}
125
126impl<T, Db: Backend> ToDatabaseOrderBy<Db> for BytesMarker<T> {}
127
128impl<T, Db: Backend> ToDatabaseOrderBy<Db> for EnumMarker<T> {}
129
130impl<T, Db: Backend> ToDatabaseOrderBy<Db> for BoolMarker<T> {}
131
132impl<T, Db: Backend> ToDatabaseOrderBy<Db> for DurationMarker<T> {}
133
134#[cfg(feature = "flags")]
135impl<T, Db: Backend> ToDatabaseOrderBy<Db> for crate::FlagsMarker<T> {}
136
137/// The ONE reading whose sequence can differ from its declaration, and the whole reason this map is
138/// not a constant.
139///
140/// It reads [`ColumnKind::ORDER`] rather than carrying a table of citizens, which is the
141/// framework-open half of the design: what a composite MEANS is the composite's, so the type that
142/// declares what it is stored as declares what order those columns are in, and a downstream citizen
143/// joins by overriding one const in an impl it already writes.
144impl<T: ColumnKind, Db: Backend> ToDatabaseOrderBy<Db> for CompositeMarker<T> {
145  const LEVELS: &'static [OrderLevel] = <T as ColumnKind>::ORDER;
146}
147
148// The three COLLECTION readings. A collection is ONE column of the row whatever it holds — the width
149// `impl<T> ColumnKind for Vec<T>` states — so like the flat readings it has no sequence to permute.
150// That holds for all three storage forms: a native array is one column, an edge-stored collection is
151// no column of this row at all, and a `sortable` one is its companion's single blob.
152impl<T, VM, Db: Backend> ToDatabaseOrderBy<Db> for ListMarker<T, VM>
153where
154  VM: Marker,
155  T: State<Extracted<Inner>, Output = VM::Marked>,
156{
157}
158
159impl<T, VM, Db: Backend> ToDatabaseOrderBy<Db> for SetMarker<T, VM>
160where
161  VM: Marker,
162  T: State<Extracted<Inner>, Output = VM::Marked>,
163{
164}
165
166impl<T, VM, Db: Backend> ToDatabaseOrderBy<Db> for QuantifiedMarker<T, VM>
167where
168  VM: Marker,
169  T: State<Extracted<Inner>, Output = VM::Marked>,
170{
171}
172
173// The two TRANSPARENT readings, which add no column and therefore no level: an optional or nullable
174// composite is stored in exactly the columns the composite is, with the same meaning in the same
175// sequence, and what the wrapper changes is whether they may be `NULL` rather than what order they
176// run in. So each forwards its inner reading's sequence and states none of its own — the same
177// transparency `ToGraphqlFilter` gives the pair one axis over.
178impl<T, VM, Db: Backend> ToDatabaseOrderBy<Db> for NullableMarker<T, VM>
179where
180  VM: ToDatabaseOrderBy<Db> + Marker,
181  T: State<Extracted<Inner>, Output = VM::Marked>,
182{
183  const LEVELS: &'static [OrderLevel] = <VM as ToDatabaseOrderBy<Db>>::LEVELS;
184}
185
186impl<T, VM, Db: Backend> ToDatabaseOrderBy<Db> for OptionalMarker<T, VM>
187where
188  VM: ToDatabaseOrderBy<Db> + Marker,
189  T: State<Extracted<Inner>, Output = VM::Marked>,
190{
191  const LEVELS: &'static [OrderLevel] = <VM as ToDatabaseOrderBy<Db>>::LEVELS;
192}
193
194/// **The level sequence an emitted order SPENDS on one column, reached without naming a numbering**
195/// — the map above refined to the two questions a lowering actually asks it.
196///
197/// # Why the facts are METHODS, and what is honestly NOT the reason
198///
199/// [`ToCrossedComparison`](crate::comparison::ToCrossedComparison) puts its crossing on methods to
200/// keep a projection off every bound, and its note carries the four measured errors that forced it.
201/// **That wall does not bite here**, and saying so is worth more than borrowing the argument: this
202/// map's answer is a `const`, not an associated type, so there is no projection for a `where` clause
203/// to resolve and nothing for a generic `Db` to be asked about.
204///
205/// What the methods buy instead is the SPELLING. A caller wants *the `at`-th leaf of this column's
206/// order*, and reading it off the const means writing the empty-sequence fallback at every call
207/// site — the `if LEVELS.is_empty() { at } else { LEVELS[at].leaf() }` that turns one convention
208/// into N copies of it. One method is that convention held in one place, which is the same reason
209/// [`OrderTerm::width`](crate::OrderTerm::width) exists beside
210/// [`segments`](crate::OrderTerm::segments).
211///
212/// # Blanket-implemented, deliberately — a downstream joins one level down
213///
214/// [`ToCrossedComparison`](crate::comparison::ToCrossedComparison)'s arrangement, for its reason:
215/// nothing implements this by hand, and a reading joins by having a [`ToDatabaseOrderBy`] row. There
216/// is no second registration, and no way for the refinement to disagree with the map it refines.
217#[diagnostic::on_unimplemented(
218  message = "`{Self}` has no order at `{Db}` — nothing says which leaves one term over it sorts by",
219  label = "this column's reading cannot be ordered at that database",
220  note = "a reading is orderable where it has a `ToDatabaseOrderBy<{Db}>` row; a composite citizen \
221          states a non-default sequence through `ColumnKind::ORDER`"
222)]
223pub trait ToCrossedOrderBy<Db: Backend>: ToDatabaseOrderBy<Db> {
224  /// The `at`-th leaf this reading's one wire term sorts by.
225  ///
226  /// `at` is a LEVEL ordinal and the answer is a LEAF ordinal; for the declaration order the two are
227  /// equal, which is exactly what the empty sequence means. Out of range for a declared sequence is
228  /// `at` itself — the identity — rather than a panic: a caller iterating a term's own
229  /// [`width`](crate::OrderTerm::width) cannot reach it, and a sequence shorter than the type is
230  /// a declaration bug that should surface as the leaf it forgot rather than as a crash inside a
231  /// statement.
232  #[inline]
233  fn level(at: usize) -> usize {
234    match <Self as ToDatabaseOrderBy<Db>>::LEVELS.get(at) {
235      Some(level) => level.leaf(),
236      None => at,
237    }
238  }
239
240  /// Whether this reading states an order of its own, rather than taking its leaves as declared.
241  ///
242  /// What a renderer asks before it walks: a reading that answers `false` needs no permutation at
243  /// all, which is the case every scalar and every non-semantic composite is in.
244  #[inline]
245  fn reorders() -> bool {
246    !<Self as ToDatabaseOrderBy<Db>>::LEVELS.is_empty()
247  }
248}
249
250/// The row itself — see the trait's note for why nothing implements it by hand.
251impl<M, Db> ToCrossedOrderBy<Db> for M
252where
253  Db: Backend,
254  M: ToDatabaseOrderBy<Db>,
255{
256}
257
258#[cfg(test)]
259mod tests;