ingraph 0.1.0

A declaration-driven indexing framework: records and nodes are written as Rust types, and the storage rows, the dataflow between them and the GraphQL query surface are emitted from the declaration.
Documentation
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
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
//! A written order, as the cursor machinery reads it: [`OrderTerm`], the [`TermName`] that
//! identifies one, the [`OrderSignature`] over the sequence, and the [`Walk`] a page runs in.

use crate::{ColumnShape, FieldName, OrderDirection, OrderLevel, name::borrowed_name};

borrowed_name! {
  /// WHICH orderable column an ordering term names — the identity a per-database rename cannot
  /// move.
  ///
  /// # It is a second name beside the column's, and the two must not be one type
  ///
  /// An [`OrderTerm`] carries both: this identity, and the [`FieldName`] the term's column is
  /// SPELLED as in the database being queried. `<db>(rename)` is what makes them differ —
  /// one declaration's `created_at` is `created_at` in SQLite and `created` in Postgres — so a term
  /// holds two names of the same column and exactly one of them is allowed to reach the SQL text.
  ///
  /// With one type they are two arguments of one type standing next to each other, which is the
  /// defect [`quote_qualified`](crate::comparison::sql::quote_qualified) takes two arguments to
  /// close and the one [`Path`](crate::Path) closes by making a layer PUSH its own segment. Swapped,
  /// the column renders under its pre-rename name — a query error at best, and at worst a column
  /// that exists under both names and answers about the wrong one. Two types make the swap `E0308`.
  ///
  /// # It never becomes SQL text, and that is the difference from [`FieldName`]
  ///
  /// A field name is *the one thing on the lowering path that becomes SQL TEXT rather than a bind*.
  /// This one becomes neither: it is folded into an [`OrderSignature`] and compared, and it reaches
  /// no statement and no bind list at all. So the quoting seam does not apply to it and there is
  /// nothing here for a bracket to escape.
  ///
  /// # What a declaration must answer with
  ///
  /// The RECORD FIELD's own name — the one `<db>(rename)` renames FROM. Any name a
  /// per-database block can move is disqualified by construction: a cursor minted against one
  /// deployment's dialect would be refused by the next, which is one order SPLIT apart, and two
  /// columns whose renames cross would be one order ALIASED with another. The generated order-by
  /// VARIANT is the same identity one layer up — `ingraph-codegen` already matches on the variant
  /// rather than the rendered name, for exactly this reason — so a derive supplies the variant's
  /// own column and this type is where that choice is stated.
  ///
  /// It validates nothing, for [`FieldName`]'s reason: every `&str` a declaration can produce is a
  /// legal identity, and what makes one right is where it came from rather than what it spells.
  pub struct TermName;
}

impl TermName {
  /// View `name` as a term's identity.
  ///
  /// `const`, so the identities a schema declares can be built in a constant — which is where they
  /// are.
  #[inline]
  pub const fn new(name: &str) -> &Self {
    Self::view(name)
  }
}

/// What a term's subject IS in the database the term was built for: one value in a column of the
/// row, or a COLLECTION — and, where it is one, which of the two places this database keeps it.
///
/// # It is a STORAGE fact, and an [`OrderTerm`] is the one type that may carry one
///
/// The generated order-by is not: its variants are the record's columns and one value of it means
/// the same thing at every database, which is what lets a client write one order for a deployment
/// it does not know the storage of. A term is minted PER DATABASE — `<db>_order_term` is where the
/// column's own name and its nullability are already read off that database's block — so this rides
/// beside them rather than being a fact the wire order carries.
///
/// # Three members for the collection, because the three are refused for different reasons
///
/// [`Array`](Self::Array) is a column of the row, so a backend either orders it the framework's way
/// or does not; [`Edge`](Self::Edge) is not a column of the row at all, so no backend's `ORDER BY`
/// has anything to name; [`Shadow`](Self::Shadow) is an edge table WITH a column of the row beside
/// it, so what is asked of the backend is whether it orders a binary column bytewise. See
/// [`Unpushable`](crate::query::Unpushable), which carries one member per reason.
///
/// # A collection has no NULL state, so no collection member is ever nullable
///
/// An edge table holds ONE observable for a column holding nothing — no rows — where
/// `Option<Vec<T>>` spells two, and the marker layer spends the `Option` for exactly that reason.
/// So the three collection constructors take no nullability and there is no fourth one to write.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum TermSubject {
  /// ONE value, in a column of the row.
  Value,
  /// MANY values, in a column of the row — the native array the backends that have one keep a
  /// collection in.
  Array,
  /// MANY values, in a table of their own, so the row being ordered has no column for them.
  Edge,
  /// MANY values, in a table of their own, MIRRORED into an order-preserving companion column of
  /// the row — the `sortable` word's answer on a database that keeps the collection in an edge
  /// table.
  ///
  /// The term's [`column`](OrderTerm::column) is the COMPANION's name and not the collection's,
  /// because the companion is what the statement orders by: the bytes are
  /// [`collection_sort_key`](crate::collection_sort_key)'s, whose bytewise order IS
  /// [`compare_collections`](crate::query::compare_collections). The
  /// [`identity`](OrderTerm::identity) stays the collection field's, so a cursor minted where the
  /// dialect keeps a native array and one minted where it keeps a shadow share a signature.
  Shadow,
  /// NO values, because this deployment's database has no column for the term at all — the
  /// declaration narrowed it out of this dialect and stores it in the record's others.
  ///
  /// # It is the DECLARATION-TRUTH schema's runtime half
  ///
  /// A per-database-narrowed column keeps its word in the schema, because a schema states the
  /// DECLARATION's truth rather than any one deployment's: `orderBy: score` is the same constant
  /// wherever the service runs. What varies is whether the database behind THIS deployment stores
  /// it, and that is a runtime fact — so the word is offered, and a request that spends it here is
  /// refused BY NAME rather than rendered into a statement the engine would answer with *no such
  /// column*.
  ///
  /// The payload is the DIALECT the term was minted for, so the refusal names both halves of the
  /// combination the declaration's author owns: which column, and which database has not got it.
  ///
  /// # It is refused rather than DEGRADED, which is what tells it apart from [`Edge`](Self::Edge)
  ///
  /// An edge-stored collection is a value the row really holds, somewhere the ordering statement
  /// cannot reach — so a scan may complete that order in memory and answer the client's question.
  /// A narrowed column holds no value here at all: a raise supplies the fill its declaration named,
  /// which is one CONSTANT for every row, and an order over a constant is not the order that was
  /// written. So the whole request is refused —
  /// [`Unpushable::NotStored`](crate::query::Unpushable::NotStored), which both
  /// [`SqlOrder::new`](crate::comparison::sql::SqlOrder::new) and
  /// [`MongoOrder::new`](crate::query::mongo::MongoOrder::new) turn into a named error before a row
  /// is read.
  Absent(&'static str),
}

impl TermSubject {
  /// Whether this subject is many-valued — any of the three collection members.
  ///
  /// It is the vocabulary's own question and no longer the PAGE's: a boundary asks the narrower
  /// [`binds_the_collection`](Self::binds_the_collection), because a companion column is many-valued
  /// and binds as one ordinary blob. The two came apart when the third member arrived, and keeping
  /// this one is what lets a party that really does mean *is this many-valued* say so.
  #[inline]
  #[must_use]
  pub const fn is_collection(self) -> bool {
    match self {
      Self::Array | Self::Edge | Self::Shadow => true,
      Self::Value | Self::Absent(_) => false,
    }
  }

  /// Whether this deployment's database stores the term's column at all.
  ///
  /// [`Absent`](Self::Absent) alone answers NO, and it is asked BEFORE every capability row: a
  /// backend answers about the value form it is handed, and here there is no value form to hand it.
  #[inline]
  #[must_use]
  pub const fn is_stored(self) -> bool {
    match self {
      Self::Value | Self::Array | Self::Edge | Self::Shadow => true,
      Self::Absent(_) => false,
    }
  }

  /// The DIALECT a term this subject was minted for names, or [`None`] where the column is stored
  /// and the dialect is therefore not part of any refusal.
  #[inline]
  #[must_use]
  pub const fn absent_from(self) -> Option<&'static str> {
    match self {
      Self::Absent(database) => Some(database),
      Self::Value | Self::Array | Self::Edge | Self::Shadow => None,
    }
  }

  /// Whether a boundary at this subject is the WHOLE COLLECTION bound as ONE value — the question
  /// [`OrderCapability::COLLECTION_BOUNDARY`](crate::query::OrderCapability::COLLECTION_BOUNDARY)
  /// answers, asked rather than read off [`is_collection`](Self::is_collection).
  ///
  /// [`Array`](Self::Array) alone, and the three that answer NO answer it for three reasons.
  /// [`Value`](Self::Value) is not a collection. [`Edge`](Self::Edge) is refused one layer out,
  /// under [`Unpushable::CollectionTable`](crate::query::Unpushable::CollectionTable), and never
  /// reaches the boundary question. And a [`Shadow`](Self::Shadow) boundary is the COMPANION
  /// COLUMN's own bytes — an ordinary value a dialect binds like any other blob — so the array row
  /// decides nothing about it, which is exactly why reading this off the collection question would
  /// be wrong.
  ///
  /// An exhaustive match rather than a `matches!`, because the answer is part of what adding a
  /// member to this vocabulary MEANS: a fifth subject that compiled without deciding would take the
  /// array answer by silence.
  #[inline]
  #[must_use]
  pub const fn binds_the_collection(self) -> bool {
    match self {
      Self::Array => true,
      Self::Value | Self::Edge | Self::Shadow | Self::Absent(_) => false,
    }
  }

  /// Whether a boundary at this subject is the COMPANION COLUMN's own bytes — the question
  /// [`OrderCapability::SHADOW_BOUNDARY`](crate::query::OrderCapability::SHADOW_BOUNDARY) answers,
  /// and [`binds_the_collection`](Self::binds_the_collection)'s twin one storage form over.
  ///
  /// [`Shadow`](Self::Shadow) alone, and the three that answer NO answer it for the reasons its twin
  /// lists inverted. [`Value`](Self::Value) is not a collection. [`Edge`](Self::Edge) is refused one
  /// layer out, under [`Unpushable::CollectionTable`](crate::query::Unpushable::CollectionTable),
  /// and never reaches the boundary question — a collection with NO companion has no bytes on the
  /// row to resume at, which is exactly what the `sortable` word buys and what its absence costs.
  /// And an [`Array`](Self::Array) boundary is the whole LIST, which a dialect binds as one array
  /// parameter or not at all: a different value against a different carrier, so the two rows decide
  /// independently and a backend can honestly answer them differently.
  ///
  /// An exhaustive match for its twin's reason: the answer is part of what adding a member to this
  /// vocabulary MEANS, and a fifth subject that compiled without deciding would take the companion
  /// answer by silence.
  #[inline]
  #[must_use]
  pub const fn binds_the_companion(self) -> bool {
    match self {
      Self::Shadow => true,
      Self::Value | Self::Edge | Self::Array | Self::Absent(_) => false,
    }
  }
}

/// One term of a WRITTEN order: which column, which way it runs, whether it can hold `NULL`, what
/// its subject is in this database, and the identity that survives a rename.
///
/// # Six facts, because five of them have different readers
///
/// | fact | read by |
/// |---|---|
/// | [`identity`](Self::identity) | the [`OrderSignature`], and nothing else |
/// | [`relation`](Self::relation) | the [`OrderSignature`], beside the identity it was reached through |
/// | [`column`](Self::column) | the `ORDER BY` rendering and the keyset predicate, both as SQL text |
/// | [`direction`](Self::direction) | both of those, and inverted by a backward [`Walk`] |
/// | [`is_nullable`](Self::is_nullable) | the NULL position — stated in the ordering, honoured in the comparison |
/// | [`subject`](Self::subject) | the capability frame, which decides what a backend can put in its own ordering |
///
/// # A NESTED term's identity is TWO names, and they are never joined
///
/// An order may name a column of another record — `cover_keyframe_id.title`, the title of the
/// keyframe a shot covers — and the leaf name alone does not identify that subject: two records may
/// both declare `title`, and one record may reach two of them. So a term built by
/// [`through`](Self::through) carries the relation BESIDE the leaf and the
/// [`OrderSignature`] folds both, each length-prefixed. The joined literal never exists: see
/// [`through`](Self::through) for why building one is either a language feature Rust does not have
/// or a leak, and [`SubjectPath`](crate::SubjectPath) for the party whose job the human spelling is.
///
/// **A path deeper than one hop has no identity ON THIS TYPE, and it does not need one.** The
/// relation slot holds ONE name, so `cover.strip.label` cannot be minted here: the middle segment
/// would have to be pushed onto a term that already carries its own, and composing a `&'static`
/// chain at runtime is the leak the two-part shape exists to avoid.
///
/// That is a ceiling on the TERM and not on the identity. [`OrderFold`] is where an N-hop subject is
/// fingerprinted: a recursive walk folds one length-prefixed segment per hop AS IT DESCENDS, each
/// segment the literal that level already holds, so nothing anywhere carries more than one borrow at
/// a time. A term's own one-hop slot stays what a FLAT order's nested leaf is built with, and the two
/// agree by construction — [`OrderFold::leaf`] is [`OrderSignature::of`]'s own loop body.
///
/// # A term is ONE subject, and [`segments`](Self::segments) is what a subject of several COLUMNS is
///
/// A term's column may be a type that spans more than one — the framework's own
/// [`Timestamp`](crate::Timestamp) is the first, at `at_secs` and `at_nanos` — and the sequence is
/// held HERE rather than as a sequence of terms. What reads it is the SQL family, which FLATTENS a
/// composite into a table: the `ORDER BY` renders one entry per column and the keyset compares them
/// as a row value. A document family NESTS one, so MongoDB reads [`column`](Self::column) alone and
/// sorts the sub-document — the asymmetry the `flatten` refusal already states, arriving here as two
/// readings of one term rather than as two term lists.
///
/// # …unless the type states a SEQUENCE, and then the term EXPANDS into its levels
///
/// [`levels`](Self::levels) is where [`ColumnKind::ORDER`](crate::ColumnKind::ORDER) is spent: a
/// term over a citizen that declares a semantic order becomes ONE ORDINARY TERM PER LEVEL, each
/// naming one leaf through [`leaf`](Self::leaf), each one column wide, each carrying the whole
/// term's direction. A wide term IS still the shape for every reading that states no sequence, which
/// is every one but the semantic citizens.
///
/// The two objections a wide term used to be argued from are both answered by the expansion rather
/// than dodged by it:
///
/// - **the identity.** A level keeps its field's identity, and the levels of one term are
///   consecutive — so the [`OrderSignature`] folds the same identity once per level, which is a
///   stable fingerprint of the same written order and is what both ends of a cursor compute. No
///   identity is invented, because none is needed: what tells two levels apart is
///   [`leaf`](Self::leaf), which no client writes and no signature has to carry.
/// - **the slot.** The cursor still holds ONE slot per TERM — and after the expansion a term IS a
///   level, so the slot is ONE LEAF's value, read through the citizen's own
///   [`OrderLeaves`](crate::OrderLeaves) vocabulary. That is what makes a level's operand an
///   ordinary scalar operand: it binds through the leaf type's own
///   [`Carrier`](crate::Carrier) row, and nothing anywhere grows a per-leaf bind face.
///
/// Nullability is DECLARED rather than inferred from the cursor's value, and the difference is a
/// wrong page: a nullable column whose cursor value happens to be present still needs the
/// null-admitting arm of its comparison, because the rows on the other side of the boundary may
/// hold `NULL` where the cursor's row did not.
///
/// # There is no default direction and no default order
///
/// A term is one column AND one direction, mirroring the generated order-by whose variant carries
/// its own [`OrderDirection`]: there is no entry for a default to complete. What refuses an order of
/// NO terms is the party that consumes one — see
/// [`SqlOrder::new`](crate::comparison::sql::SqlOrder::new) — because "ordered by nothing" is not a
/// term that could be built here.
///
/// # The two names cannot be swapped
///
/// They are two TYPES for that reason, so handing the identity to the position that renders a
/// column is `E0308` rather than a query about the pre-rename name:
///
/// ```compile_fail,E0308
/// use ingraph::{FieldName, OrderDirection, OrderTerm, TermName};
///
/// let _ = OrderTerm::new(
///   FieldName::new("created_at"),
///   TermName::new("created"),
///   OrderDirection::Asc,
/// );
/// ```
///
/// Its twin, which must COMPILE — stable rustdoc runs a `compile_fail` block just far enough to see
/// it fail and never checks why, so the pair shares its call shape and one half is positive:
///
/// ```
/// use ingraph::{FieldName, OrderDirection, OrderTerm, TermName};
///
/// let term = OrderTerm::new(
///   TermName::new("created_at"),
///   FieldName::new("created"),
///   OrderDirection::Asc,
/// );
/// assert_eq!(term.column(), FieldName::new("created"));
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct OrderTerm {
  identity: &'static TermName,
  relation: Option<&'static TermName>,
  column: &'static FieldName,
  segments: &'static [ColumnShape],
  // The SEQUENCE the segments mean, EMPTY for the declaration order — the type's own
  // `ColumnKind::ORDER`, carried so that `levels` can be asked of a value rather than of a type. It
  // is cleared on a level: a level is one leaf and has nothing left to permute, so expanding one is
  // the identity and the expansion is idempotent by construction.
  order: &'static [OrderLevel],
  // WHICH leaf of `segments` this term is, or `None` for the whole subject. `Some` is what a LEVEL
  // is, and it makes the term one column wide whatever its type spans.
  leaf: Option<usize>,
  direction: OrderDirection,
  nullable: bool,
  subject: TermSubject,
}

impl OrderTerm {
  /// A term over a `NOT NULL` column holding ONE value: `identity` is the column's rename-proof
  /// name, `column` is what this database spells it, and `direction` is which way it runs.
  ///
  /// The nullable case has [its own constructor](Self::nullable) rather than a `bool` parameter
  /// here, and the two collection cases have [theirs](Self::array). Every spelling is one word at a
  /// call site and only the named ones say which word — the same trade
  /// [`OrderDirection::is_descending`] makes in the other direction, where a `bool` is what the
  /// builder takes and the enum is what a caller writes.
  ///
  /// The column spans ONE column, which is the scalar answer and the one a hand-written order over a
  /// name is making. [`spanning`](Self::spanning) is the same term with its type's own segments,
  /// which is what an emitted order writes for every column uniformly.
  #[inline]
  #[must_use]
  pub const fn new(
    identity: &'static TermName,
    column: &'static FieldName,
    direction: OrderDirection,
  ) -> Self {
    Self {
      identity,
      relation: None,
      column,
      segments: &[],
      order: &[],
      leaf: None,
      direction,
      nullable: false,
      subject: TermSubject::Value,
    }
  }

  /// A term over a NULLABLE column — the framework's NULL position is stated in the ordering and
  /// honoured in the cursor's comparison.
  #[inline]
  #[must_use]
  pub const fn nullable(
    identity: &'static TermName,
    column: &'static FieldName,
    direction: OrderDirection,
  ) -> Self {
    Self {
      nullable: true,
      ..Self::new(identity, column, direction)
    }
  }

  /// [`new`](Self::new) over a column whose TYPE answers with `segments` — `&[]` being the scalar
  /// answer, so this is the ONE spelling an emission writes and the compiler selects which it is.
  ///
  /// It is [`shape`](crate::shape)'s arrangement at the ordering seam: `at: Timestamp` and
  /// `title: String` are the same tokens, so a macro asked which of them spans two columns would be
  /// guessing. It writes `<T as ColumnKind>::SEGMENTS` at every term and a scalar lands back on
  /// [`new`](Self::new)'s answer.
  ///
  /// # THE LEAVES RUN IN `order`'s SEQUENCE, and an EMPTY one is the declaration order
  ///
  /// `order` is the type's own [`ColumnKind::ORDER`](crate::ColumnKind::ORDER), written at every
  /// term for [`segments`](Self::segments)' reason: a macro asked which types mean their columns in
  /// a different sequence would be guessing, so it writes one spelling and the compiler selects. A
  /// scalar and a composite that means its columns as declared both answer `&[]` and this term stays
  /// exactly what it was.
  ///
  /// A NON-empty answer makes this term EXPAND — see [`levels`](Self::levels) — into one ordinary
  /// term per level. Both renderings of a page then walk levels rather than a wide subject: the
  /// `ORDER BY` renders one entry each, the keyset writes its ordinary per-level expansion, and each
  /// level's operand binds ONE placeholder through the leaf type's own scalar
  /// [`Carrier`](crate::Carrier) row.
  ///
  /// # Why the derived leaf LEADS for the shipped instant, and what that fixed
  ///
  /// `at: MediaTimestamp` used to sort by `at_pts` first, which is the sequence its columns are
  /// WRITTEN in. A `pts` is a count in a unit the next row may not share, so that is not a time
  /// order across timebases at all: `900` at `1/1000` is earlier than `30` at `1/25`, and the
  /// count-led sort put them the other way round. Its `ORDER` states *nanos, pts, num, den* — the
  /// one unit every stored row shares, with the value leaves as the tie-break that gives two rows at
  /// one instant a stable total order — and this is where that statement reaches a statement.
  ///
  /// The 2026-08-29 law's two halves are now both landed. The SEMANTIC half is the sequence above.
  /// The STRUCTURAL half is that no judgment of PRESENCE walks a derived leaf — see
  /// [`value_width`](Self::value_width) — and the expansion is what makes the two compose rather
  /// than compete: after it, a level's null test is about that level's own column, so the derived
  /// leaf is asked about only where it is the subject and never as a proxy for whether the value is
  /// there. A row stored past the ±292-year ceiling — value leaves exact, derived leaf `NULL` — sits
  /// in the `NULL` group of the nanos LEVEL and is separated from a genuinely absent instant by the
  /// pts level below it, which is ingraph #454's repair holding under the sequence rather than
  /// against it.
  #[inline]
  #[must_use]
  pub const fn spanning(
    identity: &'static TermName,
    column: &'static FieldName,
    segments: &'static [ColumnShape],
    order: &'static [OrderLevel],
    direction: OrderDirection,
  ) -> Self {
    Self {
      segments,
      order,
      ..Self::new(identity, column, direction)
    }
  }

  /// [`spanning`](Self::spanning) over a NULLABLE column — [`nullable`](Self::nullable)'s twin, for
  /// the emission's uniform spelling.
  ///
  /// A NULLABLE COMPOSITE **is** a state a declaration reaches now — `Option<Timestamp>` loads,
  /// the encoding being *every VALUE column `NULL`* — so the null arms this renders are exercised
  /// rather than defensive. They are conjunctive over the leaves because the row-value spelling is
  /// not portable: measured on SQLite 3.51.0, `(a, b) IS NULL` is *row value misused*.
  ///
  /// **REPAIRED (ingraph #454).** Those arms once walked the term's whole WIDTH, so a composite
  /// carrying a DERIVED leaf — `MediaTimestamp`'s `at_nanos` — had that column in its null test,
  /// where the presence test one lane over deliberately does not: a row past the ±292-year ceiling
  /// is `NULL` there AND present, so pagination called absent what the decode and the filter both
  /// called present, and no page could reach it. The walk is now the VALUE leaves —
  /// [`value_width`](Self::value_width) is the count and `OrderSubjects::push_value_entry` is the
  /// per-leaf write — so the three readers agree by construction rather than by convention. See
  /// `comparison::sql::keyset`'s own note, which is the other half of this one.
  ///
  /// # The nullability of a LEVEL is the FIELD's or the LEAF's, whichever says yes
  ///
  /// A term this constructor built has every level nullable, the field being optional. A term
  /// [`spanning`](Self::spanning) built may still have one: a leaf declared
  /// [`Nullable`](crate::ColumnShape::Nullable) holds `NULL` whatever its field is, which is exactly
  /// the shipped instant's derived column. So the two grains compose at the level exactly as they
  /// compose at the DDL — see [`levels`](Self::levels), which is where the pair is spent — and a
  /// required `at: MediaTimestamp` gets the `NULL`-admitting arms on its nanos level alone.
  ///
  /// Being DERIVED is not what makes a level nullable, and the level reads the same bit the DDL
  /// does. A leaf declared [`Derived`](crate::ColumnShape::Derived) is outside the value and never
  /// `NULL`, so a level over one renders through [`spanning`](Self::spanning)'s arms with no
  /// null partition to pay for.
  #[inline]
  #[must_use]
  pub const fn spanning_nullable(
    identity: &'static TermName,
    column: &'static FieldName,
    segments: &'static [ColumnShape],
    order: &'static [OrderLevel],
    direction: OrderDirection,
  ) -> Self {
    Self {
      nullable: true,
      ..Self::spanning(identity, column, segments, order, direction)
    }
  }

  /// A term over a COLLECTION this database keeps in a column of the row — a native array.
  ///
  /// Whether such a column is this backend's to order by is
  /// [`OrderCapability::COLLECTIONS`](crate::query::OrderCapability::COLLECTIONS), because the
  /// backends that have an array do not agree about what ordering two of them means.
  ///
  /// It takes no segments and has none to take: a collection is ONE column whatever it holds — the
  /// width [`ColumnKind for Vec<T>`](crate::ColumnKind) states — so the two axes this type carries
  /// never both leave their default on one term.
  #[inline]
  #[must_use]
  pub const fn array(
    identity: &'static TermName,
    column: &'static FieldName,
    direction: OrderDirection,
  ) -> Self {
    Self {
      subject: TermSubject::Array,
      ..Self::new(identity, column, direction)
    }
  }

  /// A term over a COLLECTION this database keeps in a table of its own.
  ///
  /// `column` is still the collection's own name — the path the edge table is derived from — and it
  /// reaches no ordering statement on any backend: the row being ordered has no such column, which
  /// is [`Unpushable::CollectionTable`](crate::query::Unpushable::CollectionTable).
  #[inline]
  #[must_use]
  pub const fn edge(
    identity: &'static TermName,
    column: &'static FieldName,
    direction: OrderDirection,
  ) -> Self {
    Self {
      subject: TermSubject::Edge,
      ..Self::new(identity, column, direction)
    }
  }

  /// A term over a COLLECTION this database keeps in a table of its own and MIRRORS into an
  /// order-preserving companion column — the `sortable` word's term.
  ///
  /// `column` is the COMPANION's name rather than the collection's, which is the one place this
  /// family's two names come apart on purpose: the statement orders by a real binary column of the
  /// row, and [`identity`](Self::identity) stays the collection field's so the written order a
  /// client sent, its fingerprint and its refusals all still name what was written.
  ///
  /// The companion's name is the SYNTHESIZED-COLUMN law's — `__ig_<field>_sort__`, minted where the
  /// declaration is read and carried here as any other rendered name is. Nothing in this module
  /// derives it: a term holds names, and joining two of them is the emitter's.
  ///
  /// It takes no segments, for [`array`](Self::array)'s reason: a companion column is ONE column
  /// whatever the collection holds.
  #[inline]
  #[must_use]
  pub const fn shadow(
    identity: &'static TermName,
    column: &'static FieldName,
    direction: OrderDirection,
  ) -> Self {
    Self {
      subject: TermSubject::Shadow,
      ..Self::new(identity, column, direction)
    }
  }

  /// A term over a column `database` HAS NOT GOT — the declaration narrowed it out of this dialect
  /// and stores it in the record's others.
  ///
  /// `column` is the name the column wears where it IS stored, which is the only name there is: a
  /// database that has no such column renamed nothing. It reaches no statement on this dialect —
  /// [`Unpushable::NotStored`](crate::query::Unpushable::NotStored) refuses the whole order by name
  /// before a row is read — and it is carried rather than dropped so that the refusal can say WHICH
  /// term a client wrote.
  ///
  /// It takes no segments and no nullability: both are facts about a column of this row, and the
  /// whole content of this term is that there is not one.
  #[inline]
  #[must_use]
  pub const fn absent(
    identity: &'static TermName,
    column: &'static FieldName,
    direction: OrderDirection,
    database: &'static str,
  ) -> Self {
    Self {
      subject: TermSubject::Absent(database),
      ..Self::new(identity, column, direction)
    }
  }

  /// This term, reached THROUGH a relation position — the nested order's term, whose identity is the
  /// pair `(relation, identity)` rather than one name.
  ///
  /// A nested order names a column of ANOTHER record: `cover_keyframe_id.title` orders shots by the
  /// title of the keyframe each one covers. Two records may both declare `title`, and one record may
  /// reach two of them, so the leaf name alone does not identify the subject and a cursor minted
  /// under `cover.title` would validate against an order written as `hero.title`.
  ///
  /// # It is applied to the TARGET's answer, and that is why it is a method and not a constructor
  ///
  /// The nested arm does not know what its target ordered by — the target answers with a whole
  /// [`OrderTerm`] at runtime — so what this end has is the relation's own name as a literal and the
  /// target's term as a value. This pushes the one onto the other, which is
  /// [`Path::join`](std::path::Path::join)'s direction read from the far end and the only direction
  /// that composes: seven constructors would each need a nested twin, and none of them could take
  /// the target's answer apart to rebuild it.
  ///
  /// # It joins NOTHING, and that is the whole of why it costs no allocation
  ///
  /// The two names stay two `&'static` borrows. `"cover_keyframe_id.title"` is never built — not
  /// here, not in the fold, not anywhere — because building it would mean either a `const`
  /// concatenation the language does not have or a leak: the term is `'static` and the relation is
  /// discovered at the arm, so an owned `String` would have to outlive every page that ever asks.
  /// [`SubjectPath`](crate::SubjectPath) holds a `&'static [&'static TermName]` and shows the cost
  /// concretely — a nested arm cannot prepend a segment to a target's answer without leaking one.
  /// The human spelling belongs to the party that RENDERS a path, which is that type's and not this
  /// one's.
  ///
  /// # It carries exactly ONE segment, and a deeper path is [`OrderFold`]'s
  ///
  /// The composed term holds the relation and the leaf, so applying this to a term that already
  /// carries a relation REPLACES the one it had rather than growing a third segment — there is no
  /// place to put one, for the same reason the joined literal has none: composing the target's
  /// answer with a segment of its own needs a `&'static` node built at runtime.
  ///
  /// A two-hop order is therefore fingerprinted by the WALK rather than by a term: [`OrderFold`]
  /// folds one segment per hop as it descends and the leaf folds itself, which is this method's own
  /// arithmetic with the composition taken out. A term reached through one relation and a fold that
  /// hopped once before that same leaf produce the same signature, which is the seam between the
  /// two halves.
  #[inline]
  #[must_use]
  pub const fn through(self, relation: &'static TermName) -> Self {
    Self {
      relation: Some(relation),
      ..self
    }
  }

  /// The column's rename-proof identity — with [`relation`](Self::relation), the
  /// [`OrderSignature`]'s only input from this term besides its direction.
  ///
  /// The LEAF of a nested term: `title`, where the whole subject is `cover_keyframe_id.title`. What
  /// it was reached through is the term's other name.
  #[inline]
  #[must_use]
  pub const fn identity(&self) -> &'static TermName {
    self.identity
  }

  /// The relation position this term reached its column THROUGH, or [`None`] where the column is
  /// this row's own.
  ///
  /// The HEAD of a nested term's two-part identity — see [`through`](Self::through), which is the
  /// only thing that sets one. It is an identity like [`identity`](Self::identity) and not a
  /// rendered name: `<db>(rename)` moves what a relation's foreign key is SPELLED as and
  /// must not move what a client's written order is fingerprinted as.
  #[inline]
  #[must_use]
  pub const fn relation(&self) -> Option<&'static TermName> {
    self.relation
  }

  /// The column as THIS database spells it, which `<db>(rename)` may have moved.
  ///
  /// The FIELD's name, which for a term whose type spans several columns is the name they are
  /// rendered BENEATH rather than a column of its own — `at`, where the table holds `at_secs` and
  /// `at_nanos`. A family that FLATTENS the composite joins it with [`segments`](Self::segments); a
  /// family that NESTS one reads this alone, which is what makes a MongoDB `$sort` over an instant
  /// the sub-document's own order.
  #[inline]
  #[must_use]
  pub const fn column(&self) -> &'static FieldName {
    self.column
  }

  /// What this term's column TYPE spans beneath [`column`](Self::column) — EMPTY for the one-column
  /// answer, which is [`ColumnKind::SEGMENTS`](crate::ColumnKind::SEGMENTS)' own default.
  #[inline]
  #[must_use]
  pub const fn segments(&self) -> &'static [ColumnShape] {
    self.segments
  }

  /// The SEQUENCE this term's columns mean — its type's own
  /// [`ColumnKind::ORDER`](crate::ColumnKind::ORDER), and EMPTY for the declaration order.
  ///
  /// It is what [`levels`](Self::levels) spends. A term that has already been expanded answers
  /// EMPTY, there being nothing left to permute in one leaf.
  #[inline]
  #[must_use]
  pub const fn order(&self) -> &'static [OrderLevel] {
    self.order
  }

  /// WHICH leaf of [`segments`](Self::segments) this term is, or [`None`] where it is the whole
  /// subject.
  ///
  /// [`Some`] is what a LEVEL is — one column of a citizen's own, addressed by the leaf numbering
  /// [`width`](crate::width) counts. It is read by the parties that RENDER a subject, so that one
  /// entry, one operand and one null test all name the same column; nothing else asks.
  #[inline]
  #[must_use]
  pub const fn leaf(&self) -> Option<usize> {
    self.leaf
  }

  /// How many COLUMNS this term names: `1` for the ordinary term and for a LEVEL, and the leaf count
  /// of [`segments`](Self::segments) for a composite one that has not been expanded.
  ///
  /// It is what a party rendering the `ORDER BY` iterates and what the keyset's operand is bracketed
  /// by, so the two cannot disagree about the width of one subject.
  ///
  /// A LEVEL answers `1` however wide its type is, which is the whole content of being one: it names
  /// one column, its operand binds one placeholder, and the bracket a row value would have needed is
  /// not written.
  #[inline]
  #[must_use]
  pub const fn width(&self) -> usize {
    if self.leaf.is_some() || self.segments.is_empty() {
      return 1;
    }
    crate::width(self.segments)
  }

  /// How many of this term's columns hold its VALUE — [`width`](Self::width) counting only the
  /// leaves [`ColumnShape::holds_value`](crate::ColumnShape::holds_value) admits.
  ///
  /// # It is a SECOND numbering of one subject, and the two are asked by two questions
  ///
  /// [`width`](Self::width) is what the `ORDER BY` iterates and what the keyset's row value is
  /// bracketed by — the columns this term SORTS BY. This is what the keyset's NULL TEST iterates —
  /// the columns that say whether the term's value is there at all. For `MediaTimestamp` they are
  /// four and three, and the difference is `at_nanos`, which is `NULL` for a stored instant past the
  /// ±292-year ceiling.
  ///
  /// Reading one where the other is meant is ingraph #454: a pagination null test over the whole
  /// width called such a row ABSENT while the decode and the presence filter both called it present,
  /// so a page could never reach it. The law that settles which is which is
  /// [`ColumnShape`](crate::ColumnShape)'s own.
  ///
  /// A term with no segments answers `1`, exactly as [`width`](Self::width) does: its one column is
  /// its value, whether that column is a name, a companion or a whole sub-select.
  ///
  /// # A LEVEL answers `1` TOO, INCLUDING a level over a derived leaf, and that is not a repeal
  ///
  /// The #454 law is that no judgment of PRESENCE walks a derived leaf, and a level's null test is
  /// not one: after the expansion the subject IS that column, so `at_nanos IS NULL` asks where this
  /// row sits in the nanos level's own order rather than whether the instant is there. The question
  /// the law was written about — *is this term's value at this row at all* — is asked of the wide
  /// term, which is still the shape for every reading that states no sequence, and of the VALUE
  /// levels of an expanded one, whose columns are `NOT NULL` unless the field is optional.
  ///
  /// What that buys is the completeness the wide term could not have: a row past the ceiling is in
  /// the nanos level's `NULL` group and is separated from a row with no instant at all by the pts
  /// level below, so both are reachable and neither is repeated.
  #[inline]
  #[must_use]
  pub const fn value_width(&self) -> usize {
    if self.leaf.is_some() || self.segments.is_empty() {
      return 1;
    }
    crate::value_width(self.segments)
  }

  /// Which way this term runs, as written.
  #[inline]
  #[must_use]
  pub const fn direction(&self) -> OrderDirection {
    self.direction
  }

  /// Whether this term's column can hold `NULL`.
  #[inline]
  #[must_use]
  pub const fn is_nullable(&self) -> bool {
    self.nullable
  }

  /// What this term's subject is in the database it was minted for.
  #[inline]
  #[must_use]
  pub const fn subject(&self) -> TermSubject {
    self.subject
  }

  /// How many LEVELS this term runs as — `1` unless its type states a sequence, and that sequence's
  /// length where it does.
  ///
  /// What a party sizing a cursor asks before it walks: the slots a term contributes is its level
  /// count, because after the expansion a slot is a LEVEL's boundary value.
  #[inline]
  #[must_use]
  pub const fn level_count(&self) -> usize {
    if self.order.is_empty() {
      return 1;
    }
    self.order.len()
  }

  /// This term as the LEVELS it runs as — itself, unless its type states a sequence.
  ///
  /// # It is where [`ColumnKind::ORDER`](crate::ColumnKind::ORDER) is SPENT
  ///
  /// A citizen that means its columns in a sequence other than the one they are written in becomes
  /// one ORDINARY TERM per level here, and nothing after this point is composite-shaped. That is the
  /// whole of the road: the `ORDER BY` renders the levels it always rendered a wide term's leaves
  /// as, the keyset writes the same per-level expansion it writes for a client's own multi-term
  /// order, each level's operand is one scalar bound through its own type's
  /// [`Carrier`](crate::Carrier) row, and the arm a boundary cut at a beyond-ceiling row needs —
  /// `at_nanos IS NOT NULL OR (at_nanos IS NULL AND …)` — is the general form's own third row rather
  /// than a case anybody writes.
  ///
  /// # What a LEVEL carries, and what it drops
  ///
  /// It keeps the identity, the relation, the rendered column, the subject and the DIRECTION —
  /// distributed to every level, because they are one subject read left to right and a pair inverted
  /// in one half and not the other is not the reverse of any order. It keeps the SEGMENTS, since the
  /// column's name is still [`Backend::write_column`](crate::Backend::write_column)'s join of the
  /// field's name and the leaf's, made through the tree rather than spelled. It gains
  /// [`leaf`](Self::leaf), which is what makes it one column wide. And it DROPS the sequence, so a
  /// level cannot expand again and this is idempotent.
  ///
  /// Nullability is the pair the DDL already composes: a level is nullable when its FIELD is
  /// optional **or** when its own leaf is [`Nullable`](crate::ColumnShape::Nullable). A required
  /// `at: MediaTimestamp` therefore yields exactly one nullable level, the derived one, which is the
  /// truth the write already binds.
  ///
  /// # A term with a sequence but NO segments cannot arrive
  ///
  /// A sequence names leaves of a segment tree, and a type with no tree has one leaf and can permute
  /// nothing — [`ColumnKind::ORDER`](crate::ColumnKind::ORDER)'s own default is the empty answer for
  /// exactly that reason. A leaf ordinal that names no leaf keeps the term's declared nullability
  /// rather than inventing one, which surfaces a mis-written sequence as the column it forgot rather
  /// than as a panic inside a statement — [`ToCrossedOrderBy::level`](crate::ToCrossedOrderBy)'s own
  /// standing, one seam up.
  #[inline]
  #[must_use]
  pub const fn levels(self) -> OrderLevels {
    OrderLevels { term: self, at: 0 }
  }

  /// This term as its `at`-th level — see [`levels`](Self::levels), whose body this is.
  fn at_level(self, at: usize) -> Self {
    let leaf = self.order[at].leaf();
    let nullable = self.nullable
      || matches!(crate::leaf_shape(self.segments, leaf), Some(shape) if shape.self_nullable());
    Self {
      order: &[],
      leaf: Some(leaf),
      nullable,
      ..self
    }
  }
}

/// The LEVELS one term runs as — [`OrderTerm::levels`]'s iterator.
///
/// A named type rather than an `impl Trait`, so the count is [`ExactSizeIterator`]'s and a caller
/// sizing a cursor's slot list reads it off the iterator it is already holding.
#[derive(Debug, Clone, Copy)]
pub struct OrderLevels {
  term: OrderTerm,
  at: usize,
}

impl Iterator for OrderLevels {
  type Item = OrderTerm;

  fn next(&mut self) -> Option<OrderTerm> {
    if self.at >= self.term.level_count() {
      return None;
    }
    let at = self.at;
    self.at += 1;
    // The un-permuted term is its own single level, which is what makes a scalar's page and a
    // non-semantic composite's byte-identical to what they were: the same value goes through.
    if self.term.order().is_empty() {
      return Some(self.term);
    }
    Some(self.term.at_level(at))
  }

  #[inline]
  fn size_hint(&self) -> (usize, Option<usize>) {
    let left = self.term.level_count() - self.at;
    (left, Some(left))
  }
}

impl ExactSizeIterator for OrderLevels {}

/// A fingerprint of the (columns, directions) sequence a cursor was minted under.
///
/// **It is the teeth of the cursor.** A relay cursor replayed under a different order compares its
/// values against columns they were never taken from, and the page that comes back skips or repeats
/// rows with no error anywhere. Servers commonly ignore this; here it is
/// [`CursorError::Order`](crate::CursorError::Order), raised before any SQL renders.
///
/// # The inputs are the IDENTITIES, never the rendered column names
///
/// Measured against `<db>(rename)`, which is the one thing that can move a column's name
/// without changing the order a client wrote:
///
/// - **Rendered names SPLIT one order apart.** The same written order fingerprints differently on
///   two dialects the moment either renames a column, so a cursor minted while a deployment stored
///   Postgres is refused by the same deployment's SQLite — and the signature stops describing the
///   ORDER and starts describing the storage.
/// - **Rendered names can ALIAS two orders together.** Two columns renamed across two databases may
///   each carry the other's name, so a cursor over one order validates against the other and the
///   page silently pages the wrong column.
/// - **Identities do neither.** A rename does not move them, and a declaration cannot give two
///   columns one identity — the derive already refuses colliding column names and colliding
///   renames.
///
/// # What is deliberately NOT folded in
///
/// - The DIALECT. Folding it in is the split above, written on purpose.
/// - NULLABILITY. It is a schema fact rather than something the client wrote, and a column that
///   becomes nullable changes the ordering and the comparison TOGETHER — so a cursor minted before
///   the change still resumes at the right row.
/// - The page SIZE and the [`Walk`]. A relay client pages forward and backward through one order
///   with one set of cursors, which is the whole of what `before`/`after` are for.
///
/// # It is a FINGERPRINT, and the width is what that word admits
///
/// FNV-1a over the terms, each identity length-prefixed so that no two sequences of identities
/// share an input — `["ab", "c"]` and `["a", "bc"]` differ here, where a plain concatenation would
/// not. A NESTED term contributes TWO length-prefixed parts under that same rule, so the relation it
/// was reached through separates `cover.title` from `hero.title` and neither can be posed by a leaf
/// that spells the joined name — see [`OrderTerm::through`]. An N-HOP subject contributes N+1 under
/// the same rule, one per hop and one for the leaf, folded by [`OrderFold`] as the walk descends.
/// That closes every STRUCTURAL alias;
/// what remains is the 64-bit function's own collision
/// probability, which two honestly declared orders reach at about 2⁻⁶⁴ and a forger reaches at
/// will. The consequence of a forged collision is a wrong page of rows the forger could have asked
/// for by naming the order, so this is a correctness guard rather than an authorisation one and is
/// documented as such.
///
/// The function is written here rather than taken from [`core::hash`]: `DefaultHasher` is
/// explicitly not stable across releases, and a cursor outlives the process that minted it.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct OrderSignature(u64);

/// FNV-1a's 64-bit offset basis.
const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;

/// FNV-1a's 64-bit prime.
const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;

impl OrderSignature {
  /// The signature of `terms`, in the order they run.
  ///
  /// A term reached through a relation folds BOTH of its names, head first, before its direction —
  /// which is the whole of what a nested subject costs here. See the type's note on the two-part
  /// identity for why the pair is folded rather than joined.
  #[must_use]
  pub fn of(terms: &[OrderTerm]) -> Self {
    let mut hash = FNV_OFFSET;
    for term in terms {
      hash = fold_term(hash, term);
    }
    Self(hash)
  }

  /// The fingerprint itself.
  #[inline]
  #[must_use]
  pub const fn get(self) -> u64 {
    self.0
  }

  /// The bytes a cursor carries this signature as: big-endian, the form every durable number in
  /// this crate takes — see [`BeU64::to_blob`](crate::BeU64::to_blob), whose eight bytes these are.
  #[inline]
  #[must_use]
  pub const fn to_blob(self) -> [u8; 8] {
    self.0.to_be_bytes()
  }

  /// The signature `bytes` carries, or [`None`] where they are not eight.
  ///
  /// The width is a fact to check rather than to assume, which is what makes this a round trip and
  /// not a one-way helper — the same standard [`BeU64::from_blob`](crate::BeU64::from_blob) holds.
  #[inline]
  #[must_use]
  pub fn from_blob(bytes: &[u8]) -> Option<Self> {
    Some(Self(u64::from_be_bytes(bytes.try_into().ok()?)))
  }
}

/// **A signature BEING BUILT** — the accumulator a RECURSIVE order walk carries down, one
/// length-prefixed segment per hop.
///
/// # It is what an N-HOP identity is, and it exists because a chain cannot be held
///
/// [`OrderTerm`] carries at most ONE relation, and that is a measured ceiling rather than a
/// simplification: a term is `'static` and `Copy`, the hops are discovered one level at a time as a
/// nested arm hands its target's answer back, and a `&'static` chain composed at runtime is a leak
/// that has to outlive every page ever served. The joined literal is worse for the same reason,
/// twice over.
///
/// What a walk CAN do is fold as it descends. Each level knows its own relation name as a literal —
/// the arm the client picked — so it folds that one segment and recurses; the leaf folds itself; and
/// nothing anywhere holds more than one borrow at a time. Zero allocation, zero leak, and the
/// injectivity is the length prefix's, exactly as it is for a flat order. Those are
/// [`Path`](std::path::Path)'s components read as a fingerprint rather than as a string.
///
/// # It AGREES with [`OrderSignature::of`] where both can answer
///
/// A walk that folds no hop and one leaf per term produces exactly the flat signature, and a walk
/// that folds one hop before a leaf produces exactly what the same term built by
/// [`OrderTerm::through`] does. That is not a coincidence to preserve by hand: [`leaf`](Self::leaf)
/// IS the loop body of [`of`](OrderSignature::of), called from the other side.
///
/// # Examples
///
/// Two hops, which no single term can spell:
///
/// ```
/// use ingraph::{FieldName, OrderDirection, OrderFold, OrderTerm, TermName};
///
/// const LABEL: OrderTerm =
///   OrderTerm::new(TermName::new("label"), FieldName::new("label"), OrderDirection::Asc);
///
/// let deep = OrderFold::new()
///   .hop(TermName::new("cover"))
///   .hop(TermName::new("strip"))
///   .leaf(&LABEL)
///   .finish();
/// let shallow = OrderFold::new().hop(TermName::new("cover")).leaf(&LABEL).finish();
///
/// assert_ne!(deep, shallow);
/// ```
///
/// And the flat order is the degenerate walk:
///
/// ```
/// use ingraph::{FieldName, OrderDirection, OrderFold, OrderSignature, OrderTerm, TermName};
///
/// const TITLE: OrderTerm =
///   OrderTerm::new(TermName::new("title"), FieldName::new("title"), OrderDirection::Asc);
///
/// assert_eq!(
///   OrderFold::new().leaf(&TITLE).finish(),
///   OrderSignature::of(&[TITLE]),
/// );
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct OrderFold(u64);

impl OrderFold {
  /// The empty fold — what a walk starts from, and the same basis a flat signature starts from.
  #[inline]
  #[must_use]
  pub const fn new() -> Self {
    Self(FNV_OFFSET)
  }

  /// Descend ONE HOP, folding the relation position this level is reached through.
  ///
  /// Called once per level as the walk descends, OUTERMOST FIRST — the order a subject reads, and
  /// the order the segments have to arrive in for two paths through the same leaf to stay apart.
  #[inline]
  #[must_use]
  pub fn hop(self, relation: &TermName) -> Self {
    Self(fold_part(self.0, relation))
  }

  /// Fold the LEAF this walk arrived at — its own one-hop relation where it has one, its identity,
  /// and its direction.
  ///
  /// It is [`OrderSignature::of`]'s loop body, which is what keeps a walk and a flat fold from
  /// coming to disagree: the two spell one rule once.
  #[inline]
  #[must_use]
  pub fn leaf(self, term: &OrderTerm) -> Self {
    Self(fold_term(self.0, term))
  }

  /// The signature this walk built.
  #[inline]
  #[must_use]
  pub const fn finish(self) -> OrderSignature {
    OrderSignature(self.0)
  }
}

impl Default for OrderFold {
  #[inline]
  fn default() -> Self {
    Self::new()
  }
}

/// ONE TERM folded into `hash` — its relation where it has one, its identity, then its direction.
///
/// Written once and read from both ends: [`OrderSignature::of`] walks a flat slice through it and
/// [`OrderFold::leaf`] calls it after however many hops the walk descended. Two callers, one rule,
/// so a nested walk and a flat fold cannot come to mean different things by the same term.
#[inline]
fn fold_term(mut hash: u64, term: &OrderTerm) -> u64 {
  // The relation BEFORE the leaf, in the order the subject reads: `cover_keyframe_id` then `title`.
  // Sequentially, each part length-prefixed by the same rule one part already had — two
  // individually-`'static` borrows folded one after the other, so no joined name is built and none
  // is leaked.
  if let Some(relation) = term.relation() {
    hash = fold_part(hash, relation);
  }
  hash = fold_part(hash, term.identity());
  fnv(hash, u8::from(term.direction().is_descending()))
}

/// One PART of a term's identity, folded into `hash`: its length, then its bytes.
///
/// The LENGTH before the bytes, so a sequence of parts has one reading. Without it `["ab", "c"]` and
/// `["a", "bc"]` feed the same bytes and two different orders share a fingerprint for a reason that
/// has nothing to do with the hash. That rule is what makes the nested term's TWO-part identity at
/// least as injective as the single joined literal it replaces: `cover.title` as one name is a
/// three-part-long run of bytes where the pair is two self-delimiting ones, and no leaf named
/// `cover.title` can pose as the pair.
///
/// A length that does not fit in `u32` saturates, which is the ONE structural alias this leaves: two
/// identities of four gibibytes or more share a prefix. No declaration reaches it — an identity is a
/// Rust field name — and widening the prefix would change every existing cursor's fingerprint.
#[inline]
fn fold_part(mut hash: u64, part: &TermName) -> u64 {
  let part: &str = part;
  for byte in u32::try_from(part.len()).unwrap_or(u32::MAX).to_be_bytes() {
    hash = fnv(hash, byte);
  }
  for byte in part.as_bytes() {
    hash = fnv(hash, *byte);
  }
  hash
}

/// One FNV-1a step: mix the byte, then multiply.
#[inline]
const fn fnv(hash: u64, byte: u8) -> u64 {
  (hash ^ byte as u64).wrapping_mul(FNV_PRIME)
}

/// Which way a page runs through a written order.
///
/// Relay's `first`/`after` walk one way and `last`/`before` the other, and the backward walk is the
/// SAME order read from the far end: every term's comparator is inverted and the scan is reversed.
/// Re-reversing the rows that come back is the engine's, not this layer's.
///
/// # The framework's NULL position survives the inversion, and that is why it is the position it is
///
/// The framework puts `NULL` BELOW every value — one total order on the domain, spelled
/// `NULLS FIRST` on an ascending term and `NULLS LAST` on a descending one. Reversing such a term
/// gives exactly the other spelling of the same rule, so a backward walk is an order this same
/// machinery already describes.
///
/// A position pinned as a per-direction CONVENTION does not survive it. `NULLS LAST` whichever way
/// the term runs reverses into `NULLS FIRST`, which is a different order from the one the forward
/// page used — so the two directions of one relay connection would disagree about where the nulls
/// are, and a client walking back across a null boundary would skip or repeat exactly the rows on
/// it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Walk {
  /// `first`/`after`: the order as written.
  Forward,
  /// `last`/`before`: the order inverted, to be re-reversed after the rows come back.
  Backward,
}

impl Walk {
  /// The direction a term RUNS IN on this walk — its own going forward, its opposite going back.
  #[inline]
  #[must_use]
  pub const fn direction(self, written: OrderDirection) -> OrderDirection {
    match (self, written) {
      (Self::Forward, direction) => direction,
      (Self::Backward, OrderDirection::Asc) => OrderDirection::Desc,
      (Self::Backward, OrderDirection::Desc) => OrderDirection::Asc,
    }
  }
}

#[cfg(test)]
mod nested_identity_tests;
#[cfg(test)]
mod tests;