1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
//! The ORDER-PRESERVING form a collection is mirrored into — the bytes a `sortable` collection's
//! companion column holds, and the trait one element type joins that form by.
//!
//! # What it is for
//!
//! A collection kept in a table of its own has no column on the row being ordered, so
//! [`Unpushable::CollectionTable`](crate::query::Unpushable::CollectionTable) refuses every term
//! over one and the order is completed in memory or the page is refused. The `sortable` word buys
//! the missing column back: the row carries ONE opaque blob per sortable collection, holding the
//! whole collection in a form whose BYTEWISE order is the framework's own collection order —
//! [`compare_collections`](crate::query::compare_collections), element by element with
//! shorter-is-less on a prefix.
//!
//! That is the whole mechanism. The statement orders by an ordinary binary column, the engine
//! indexes it like any other, and nothing about the ordering asks the edge table a question.
//!
//! # The FRAME, and why it is two bytes rather than none
//!
//! ```text
//! [] 00
//! [a] 01 <a> 00
//! [a, b] 01 <a> 01 <b> 00
//! ```
//!
//! `0x01` before each element and `0x00` after the last. Every rule of the pin falls out of
//! `0x00 < 0x01` alone:
//!
//! - the EMPTY collection is one byte and every other starts with `0x01`, so it is least;
//! - a PREFIX ends where the longer one continues, and there the shorter has `0x00` against `0x01`;
//! - the FIRST DIFFERING ELEMENT decides, because the elements before it wrote identical bytes at
//! identical offsets.
//!
//! The offsets stay aligned because [`SortKey`] is PREFIX-FREE — see its contract. Without that the
//! marker bytes would not save the frame: one element's bytes running into the next element's
//! marker is exactly the ambiguity a length-free concatenation has.
//!
//! # It is ONE encoding, and the element half is the house's existing one
//!
//! [`BeU64::to_blob`](crate::BeU64::to_blob) and its two siblings are what the wide-integer storage
//! forms already store, and their rows here CALL those methods rather than writing the bytes again —
//! the discipline `storage`'s own note states, one type promising one thing. What is new is the
//! FRAME above and the escape a variable-width element needs, neither of which any type in this
//! crate had a form for.
//!
//! # Floats have no row, and the absence is the refusal
//!
//! [`compare_collections`](crate::query::compare_collections) demands `Ord` of its elements, which
//! `f32` and `f64` do not implement: there is no pin for a collection of them to agree with, so
//! there is nothing here for one to be encoded into. A `sortable` collection of floats is therefore
//! `E0277` naming [`SortKey`] at the declaration rather than a silent second opinion about `NaN`.
//!
//! # A downstream element joins by writing ONE impl
//!
//! The trait is open for the reason
//! [`PgCollectionStorage`](crate::comparison::sql::PgCollectionStorage) is: what an element type is
//! is the declaring crate's, and a closed list would be a framework deciding which types may be
//! collected. The rows below are the ones this crate ships a collection codec for already.
/// The ORDER-PRESERVING bytes one value of a collection element contributes.
///
/// # The contract is TWO promises, and both are load-bearing
///
/// For any two values `a` and `b` of the implementing type:
///
/// 1. **order-preserving** — comparing the written bytes bytewise gives the same answer as
/// `a.cmp(&b)`. This is what makes a database's ordering over the companion column the
/// framework's ordering over the collection;
/// 2. **prefix-free** — neither value's bytes are a PROPER PREFIX of the other's. This is what keeps
/// the frame's element offsets aligned, and it is the promise a reader is most likely to
/// overlook.
///
/// A FIXED-WIDTH encoding satisfies the second by construction, which is why every integer row below
/// simply writes its big-endian bytes. A VARIABLE-WIDTH one satisfies it with a terminator its own
/// body cannot contain, which is what [`push_escaped`] is.
///
/// Nothing here decodes. The companion column is written and ordered by and never read back into a
/// value — the collection itself is what the edge table holds — so a one-way form is the whole of
/// what this needs, and the round trip [`BeU64::from_blob`](crate::BeU64::from_blob) offers is
/// deliberately not restated.
///
/// # Examples
///
/// The whole of what a downstream element type writes:
///
/// ```
/// use ingraph::SortKey;
///
/// /// A tag, ordered by its text.
/// #[derive(PartialEq, Eq, PartialOrd, Ord)]
/// pub struct Tag(String);
///
/// impl SortKey for Tag {
/// fn write_sort_key(&self, out: &mut Vec<u8>) {
/// self.0.write_sort_key(out);
/// }
/// }
///
/// let mut bytes = Vec::new();
/// Tag("a".to_owned()).write_sort_key(&mut bytes);
/// assert_eq!(bytes, [b'a', 0x00, 0x01]);
/// ```
/// The byte a frame writes BEFORE each element.
///
/// It is above [`END`] and that is the entire prefix rule: where one collection has run out and
/// another has not, the shorter is at its terminator and the longer at this.
const ITEM: u8 = 0x01;
/// The byte a frame writes after the last element.
const END: u8 = 0x00;
/// The byte a variable-width element's escape doubles up on — the one byte its body may not contain
/// unescaped, so that the terminator is unambiguous.
const ESCAPE: u8 = 0x00;
/// What an escaped `0x00` is followed by. Above [`TERMINATOR`], so a body byte of `0x00` sorts ABOVE
/// the end of a shorter body — which is what makes a prefix least.
const ESCAPED: u8 = 0xFF;
/// What the terminating `0x00` is followed by.
const TERMINATOR: u8 = 0x01;
/// `elements`' order-preserving bytes — the value a `sortable` collection's companion column holds.
///
/// **This is the read of [`compare_collections`](crate::query::compare_collections) that a database
/// can perform.** Comparing two of these bytewise answers exactly as comparing the two collections
/// element by element does, so a `BLOB`/`bytea` column holding them orders the rows the way the
/// framework means.
///
/// It takes an ITERATOR for [`compare_collections`](crate::query::compare_collections)'s own reason:
/// a row holds a `Vec`, a write lane may hold a slice, and the pin is stated over what both are.
///
/// # Examples
///
/// The three rules of the pin, read off the bytes:
///
/// ```
/// use core::cmp::Ordering;
///
/// use ingraph::{collection_sort_key, query::compare_collections};
///
/// let empty = collection_sort_key::<[i32; 0]>([]);
/// let one = collection_sort_key([1i32]);
/// let two = collection_sort_key([1i32, 2]);
/// let other = collection_sort_key([2i32]);
///
/// // the empty collection is least
/// assert_eq!(empty.cmp(&one), Ordering::Less);
/// // a prefix is below what extends it
/// assert_eq!(one.cmp(&two), Ordering::Less);
/// // and the first differing element decides, whatever the lengths are
/// assert_eq!(other.cmp(&two), Ordering::Greater);
///
/// // which is the pin, on the same four collections
/// assert_eq!(compare_collections::<[i32; 0], _>([], [1]), Ordering::Less);
/// assert_eq!(compare_collections([1, 2], [1, 2, 3]), Ordering::Less);
/// assert_eq!(compare_collections([2], [1, 9]), Ordering::Greater);
/// ```
/// [`collection_sort_key`], appending to a buffer a caller already holds.
///
/// The form a WRITE lane spends, which encodes one collection per sortable column of a row and has
/// no reason to allocate a `Vec` apiece.
/// Append `bytes` in the ESCAPED form a variable-width element takes: every `0x00` doubled up with
/// `0xFF`, and a `0x00 0x01` terminator no body can spell.
///
/// # Why the pair, rather than a length prefix
///
/// A length prefix is not order-preserving: `"b"` is one byte and `"ab"` is two, so a leading length
/// would put the SHORTER first whatever the content, where the pin puts `"ab"` below `"b"`. The
/// escape has no such leading field — the bytes compare directly — and the terminator is what tells
/// a prefix from a continuation, at the one position where they differ.
///
/// # Both promises, checked
///
/// **Order-preserving.** Where two bodies differ at a byte, the escaped forms differ at the
/// corresponding position with the same relation: an escape ADDS a byte after a `0x00`, and it does
/// so in both forms at every `0x00` they share. Where one body is a prefix of the other, the shorter
/// reaches its terminator's `0x00`; the longer is at its next body byte, which is either above
/// `0x00` or is itself a `0x00` followed by [`ESCAPED`] where the terminator has [`TERMINATOR`], and
/// `0x01 < 0xFF`.
///
/// **Prefix-free.** Inside a body every `0x00` is followed by `0xFF`, and the terminator's is
/// followed by `0x01`, so no encoded value can continue past another's terminator.
/// A BORROW of an element is that element, which is what lets one signature take a collection of
/// values and a collection of references both.
///
/// A row holds a `Vec<String>` and hands out `&String`s where a write lane may hold a `&[String]`
/// and hand out `&String`s too, so [`collection_sort_key`]'s bound is stated over the ITEM and this
/// is what makes the two spellings satisfy it. `?Sized` because [`str`] and `[u8]` are where the
/// borrow is the only form there is.
/// A boolean is one byte, and `false < true` is what `0 < 1` already says.
/// The UNSIGNED integers, at their own widths: equal-length big-endian blobs compare bytewise
/// exactly as the numbers do, which is the fact
/// [`storage`](crate::BeU64)'s own note states and the reason those carriers exist.
unsigned_sort_keys!;
/// The SIGNED integers, offset by a SIGN-BIT FLIP so the negative range sorts below the positive
/// one.
///
/// Without it `-1` encodes as `ff…ff` and would sort above every positive value — the same
/// correction [`BeI128::to_blob`](crate::BeI128::to_blob) makes, in the same direction, and it is
/// here rather than borrowed from there because that type is `i128`'s alone.
signed_sort_keys!;
/// The three WIDE-INTEGER storage forms, through the codec each already owns.
///
/// `to_blob` rather than a second encoding: `BeU64` promises the order-preserving eight-byte
/// big-endian blob and `BeI128` promises the sign-flipped sixteen, and two parties writing those
/// bytes would be two encodings that agree today and are free to stop. This is the same call the
/// carrier rows make.
blob_sort_keys!;
/// Text, as its UTF-8 BYTES — which is what [`Ord`] for [`str`] already compares, so the encoding
/// states no second opinion about characters.
///
/// **A database COLLATION is a different question and this is not it.** The companion column is
/// binary on every dialect, so its ordering is byte order wherever it is stored — where a native
/// array of text is ordered by the column's collation. The two agree under a byte-order collation
/// and differ under any other, which is the ELEMENT-level inheritance
/// [`query::order`](crate::query)'s own note already records for the array path.
/// A byte string, as itself.