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
//! The relation kinds' MongoDB row: [`MongoRefComparison`] for a predicate reached THROUGH a
//! reference, [`MongoDerivedComparison`] for the reverse position that has none, and
//! [`MongoRelatedDocument`] — the collection on the far side and the field each nesting depth lands
//! its rows in.
//!
//! # These were a REFUSAL, and the aggregation lane is what retired it
//!
//! Both kinds used to answer [`MongoLoweringError`]`::Relation` for any non-empty predicate, and the
//! sentence was true as written: a relation is a join, `find` has none, and `$lookup` lives in a
//! pipeline this family had no way to reach. What changed is one layer up — every MongoDB lane
//! renders an AGGREGATION now, a flat query included — so the stage has a position, and the refusal
//! became this rendering. Issue #137 is where that was ruled.
//!
//! What survives of it is the two shapes `$lookup` genuinely has no spelling for:
//! [`MongoLoweringError::ElementRelation`] and [`MongoLoweringError::NegatedRelation`], each named
//! at the row that raises it.
//!
//! # One relation is THREE stages, and consuming the field is what makes the naming work
//!
//! ```text
//! { $lookup:  { from, localField, foreignField, as: "__ig_keyframe_1__", pipeline: [ … ] } }
//! { $match:   { "__ig_keyframe_1__": { $ne: [] } } }
//! { $project: { "__ig_keyframe_1__": 0 } }
//! ```
//!
//! The `$lookup` gathers the related documents into a field, the `$match` asks whether it found any,
//! and the `$project` drops the field again. That is a SEMI-JOIN in the sense the SQL family's
//! `EXISTS` is — the answer is about existence and the joined documents never reach a caller — and
//! it is honest about the half a projection cannot change: the server MATERIALIZES the array into
//! the document before the `$match` reads it, so a join is bounded by the sixteen megabytes a
//! document holds. A parent with more matching children than fit is the shape to watch, and a
//! `$lookup` that exceeds it fails the query rather than answering wrongly.
//!
//! The `$project` also does work no reader should have to infer: it is what lets the join field be
//! named by NESTING DEPTH alone. Two SIBLING relations at one depth — `any` beside `none` on one
//! position, or two references to one collection — mint the same name, and two `$lookup` stages
//! writing one document key would leave the second overwriting the first with no error anywhere.
//! Each run consumes its field before the next opens, so the repeat is harmless rather than
//! surviving as a silent wrong answer. Nesting is the axis that genuinely must differ, and it does:
//! an inner run is a stage of the OUTER lookup's own pipeline, at a depth one further in.
//!
//! # The mint is this family's OWN, and the default it shares
//!
//! [`SqlQuery::ALIASES`](crate::query::sql::SqlQuery::ALIASES) is unreachable from here — it hangs
//! off a binding whose parameter is an `sqlx::Database`, and a build carrying this backend need not
//! carry sqlx at all — so [`MongoQuery::ALIASES`](crate::query::mongo::MongoQuery::ALIASES) is the
//! twin a document binding states. What the two share is the DEFAULT depth:
//! [`DEPTH_CEILING`](crate::query::DEPTH_CEILING) is the query layer's rather than either family's,
//! because a filter answerable on one deployment's storage choice and refused on another's is the
//! one thing the wire face is arranged not to be. A declaration that names its own depth names it
//! per database, which is a choice about ONE deployment rather than a difference between backends.
//!
//! # WHERE THE TWO BACKENDS ANSWER DIFFERENTLY, and it is `all` over a missing field
//!
//! `all` is *no child fails*, and both families render it as the absence of a counterexample. SQL's
//! counterexample test is `NOT ( <predicate> )`, which is three-valued: a child whose `title` is
//! `NULL` makes the negation `NULL` too, so it is not a counterexample and the parent still passes.
//! MongoDB's is `$nor`, which is two-valued over documents: a child whose `title` is missing or null
//! does not match `{title: {$eq: "Autumn"}}`, so `$nor` DOES match it, so it IS a counterexample and
//! the parent fails.
//!
//! Measured against the SQL family's own two-table corpus, replayed in this module's tests: shot 5
//! has one `Autumn` keyframe and one whose title is `NULL`, and it passes `all` on all three SQL
//! dialects and fails it here. Neither answer is a defect — each is its engine's own truth table —
//! and a caller who needs the SQL reading asks `none` of the negated predicate instead. It is
//! recorded because a filter that crosses backends is exactly the thing this framework offers, and
//! an undocumented divergence in one quantifier is worse than a documented one.
//!
//! # INDEX FACTS, for the deployment that has to provision them
//!
//! `$lookup` with `localField`/`foreignField` uses an index on the FOREIGN field and scans without
//! one, once per input document. So:
//!
//! - a FORWARD reference joins to the target's `_id`, which the server indexes uniquely for every
//!   collection without being asked — nothing to provision;
//! - a REVERSE position joins to the source's own reference column (`shot_id` and its like), and
//!   that one needs an index the schema must declare. Without it, a page of N parents is N
//!   collection scans of the child collection.
//!
//! Provisioning is not this crate's — nothing here emits DDL or index specifications — so what this
//! note can do is name which field each shape reads.

use bson::{Bson, Document};

use super::{
  MATCH, Mongo, MongoConjunction, MongoCountComparison, MongoLoweringError, MongoOperator,
  MongoPredicate, NOR, PROJECT, count::push_count_slots, field_key, field_path,
};
use crate::{
  FieldName, RecordAddress,
  comparison::{
    At, Backend, CollapsibleComparison, ComplexComparison, RelationDepthError, RelationWidthError,
  },
  query::mongo::MongoQuery,
};

/// The `$lookup` stage's key.
const LOOKUP: &str = "$lookup";

/// The four names a `$lookup` body always carries, and the fifth it carries where the join asks the
/// related documents a question.
const FROM: &str = "from";
const LOCAL_FIELD: &str = "localField";
const FOREIGN_FIELD: &str = "foreignField";
const AS: &str = "as";
const PIPELINE: &str = "pipeline";

/// The documents on the far side of a relation, and every field a nested scope lands them in.
///
/// # Two facts about ONE collection, so they arrive as one value
///
/// The [`RecordAddress`] says which collection to join and which field identifies one of its
/// documents; the alias table says what to CALL the array they land in. Passed as two arguments they
/// could be about two different collections — an address for `keyframe` beside the names minted for
/// `shot` builds a perfectly good `$lookup` that joins the wrong pair — and no layer below could
/// tell. [`of`](Self::of) is what closes that: both halves come off ONE document type's
/// [`MongoQuery`] binding, so there is nothing to mismatch.
///
/// It is the twin of the SQL family's `RelatedRow`, and a separate type rather than that one because
/// the SQL kind's second half is SQL's: an alias there names a row SOURCE in a `FROM`, and here it
/// names a FIELD of a document. The two never mean the same thing at the same time, and the SQL
/// type's own constructor takes an `sqlx::Database` this backend has not got.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct MongoRelatedDocument {
  address: RecordAddress,
  aliases: &'static [&'static str],
}

impl MongoRelatedDocument {
  /// The collection `Row` is stored in, with the join fields its expansion minted — both read off
  /// one binding, which is what makes them impossible to mismatch.
  ///
  /// This is what an emitted relation position writes, and what a hand-written one should: the
  /// alternative spells an address and an alias table beside each other and asks a reader to check
  /// they are about the same collection.
  #[inline]
  #[must_use]
  pub const fn of<Row: MongoQuery>() -> Self {
    Self {
      address: Row::ADDRESS,
      aliases: Row::ALIASES,
    }
  }

  /// The same pair stated directly, for a caller with no document type to read them off.
  #[inline]
  #[must_use]
  pub const fn new(address: RecordAddress, aliases: &'static [&'static str]) -> Self {
    Self { address, aliases }
  }

  /// Which collection this is, and the field identifying one of its documents.
  #[inline]
  #[must_use]
  pub const fn address(&self) -> &RecordAddress {
    &self.address
  }

  /// The field a join opened one level inside `enclosing` lands its documents in.
  ///
  /// Reached by the nested ORDERING as well as by the two relation kinds — a hop is a join like any
  /// other and takes its name from the same table, so a term that follows references too deep is
  /// refused with the same sentence about the same collection. See
  /// [`MongoNesting`](crate::query::mongo::MongoNesting), which is that caller.
  ///
  /// # Errors
  ///
  /// [`MongoLoweringError::RelationDepth`] past the last name minted. Reusing one instead is silent:
  /// a join field is a KEY of the document being joined onto, so a repeat is written twice and the
  /// second `$lookup` overwrites the first — leaving the `$match` beside it testing a set the filter
  /// never asked about.
  pub(crate) fn scope(&self, enclosing: usize) -> Result<&'static str, MongoLoweringError> {
    let depth = enclosing + 1;
    match self.aliases.get(depth) {
      Some(field) => Ok(field),
      None => Err(MongoLoweringError::RelationDepth(RelationDepthError::new(
        self.address.table(),
        depth,
        self.aliases.len(),
      ))),
    }
  }
}

/// A predicate over the document a `ref` field POINTS AT, lowered as a semi-join through the
/// reference.
///
/// ```text
/// { $lookup:  { from: "keyframe", localField: "cover_id", foreignField: "_id",
///               as: "__ig_keyframe_1__", pipeline: [ { $match: { title: { $eq: "Autumn" } } } ] } }
/// { $match:   { "__ig_keyframe_1__": { $ne: [] } } }
/// { $project: { "__ig_keyframe_1__": 0 } }
/// ```
///
/// # It holds the nested comparison BARE, not behind an `Option`
///
/// An absent nested predicate and an empty one ask the same question — *nothing* — and both write no
/// stage at all. A second state with no second meaning is one a caller can reason wrongly about, so
/// the emptiness is the nested comparison's own [`is_empty`](ComplexComparison::is_empty) and there
/// is no wrapper to unwrap. That is also what a degenerate join with no sub-pipeline would have
/// been: not *nothing* but *this reference is live*, which is a question about the field's presence
/// wearing a relation's clothes.
///
/// # The nested comparison must be COLLAPSIBLE, which is the optimisation being on by default
///
/// The bound is [`CollapsibleComparison`] rather than [`ComplexComparison`], so every target
/// comparison answers whether the predicate constrains its id alone — and when it does, this kind
/// renders that constraint on the REFERENCE field and opens no join. A target that declines answers
/// `None` and pays for one. The reasoning, and the referential-integrity law it rests on, is the
/// trait's own and does not change with the backend.
///
/// # No inherent conjunct count
///
/// Every other kind here carries one, and this one cannot: its count depends on whether the nested
/// predicate collapses, which is a capability of `C` that an inherent method has no bound to ask
/// for.
#[derive(Debug, Clone, PartialEq)]
pub struct MongoRefComparison<C> {
  target: MongoRelatedDocument,
  nested: C,
}

impl<C> MongoRefComparison<C> {
  /// A predicate over `target`'s document, reached through the reference this comparison is applied
  /// at.
  #[inline]
  pub const fn new(target: MongoRelatedDocument, nested: C) -> Self {
    Self { target, nested }
  }

  /// The collection this reference points at, the field identifying one of its documents, and the
  /// names a join lands them under.
  #[inline]
  pub const fn target(&self) -> &MongoRelatedDocument {
    &self.target
  }

  /// The predicate asked of that document.
  #[inline]
  pub const fn nested(&self) -> &C {
    &self.nested
  }
}

/// A predicate over the documents whose own `ref` field points BACK at this one, asked through the
/// four quantifiers a collection is asked through.
///
/// ```text
/// any    $lookup … pipeline: [ { $match: <nested> } ]      →  { <as>: { $ne: [] } }
/// none   the same join                                     →  { <as>: { $eq: [] } }
/// all    $lookup … pipeline: [ { $match: { $nor: […] } } ] →  { <as>: { $eq: [] } }
/// count  $lookup … with no pipeline at all                 →  { $expr: { $size: … } … }
/// ```
///
/// # The vocabulary is the COLLECTION's, verbatim
///
/// `any` / `all` / `none` / `count` — one word, one meaning, whether the members are an array's
/// elements or another collection's documents. The slots are also the SQL kind's, because the FILTER
/// a client writes is one shape whichever backend answers it: a position that could be asked `all`
/// on SQLite and not here would be a wire schema that varies with a deployment's storage choice.
///
/// # `all` is the DOUBLE NEGATION, and it is the one quantifier that does not nest
///
/// *Every child satisfies P* is *no child fails P*, so the join's own pipeline matches the children
/// P EXCLUDES — `{$nor: [<P>]}` — and the position holds where that comes back empty. `$nor` takes
/// filter DOCUMENTS, so a P that is itself a relation has no stage position inside one and this
/// kind answers [`MongoLoweringError::NegatedRelation`]. Its three neighbours pass their predicate
/// through unnegated and nest without limit.
///
/// # `all` over a document with NO children is TRUE
///
/// The join finds nothing to exclude, so the field is empty and the position holds — which is the
/// same vacuous reading every other backend gives it, and it costs no branch. An EMPTY predicate
/// needs none either: `{$nor: [{}]}` parses, matches no document, and leaves the field empty for
/// every parent, which is the tautology the SQL family has to spell `1 = 1` because `NOT ( )` does
/// not parse.
///
/// # It names no field of this document, so the applied PATH goes unread
///
/// A reverse position is stored nowhere — the only fields it touches are the child's reference and
/// this document's `_id`, and both are known without it — so the same comparison renders identically
/// wherever a caller frames it.
#[derive(Debug, Clone, PartialEq)]
pub struct MongoDerivedComparison<C> {
  source: MongoRelatedDocument,
  points_back: &'static FieldName,
  any: Option<C>,
  all: Option<C>,
  none: Option<C>,
  count: Option<MongoCountComparison<i64>>,
}

impl<C> MongoDerivedComparison<C> {
  /// The documents of `source` whose `points_back` field carries this document's id — with no
  /// quantifier asked yet.
  #[inline]
  pub const fn new(source: MongoRelatedDocument, points_back: &'static FieldName) -> Self {
    Self {
      source,
      points_back,
      any: None,
      all: None,
      none: None,
      count: None,
    }
  }

  /// Ask whether SOME of those documents satisfy `nested`.
  #[inline]
  #[must_use]
  pub fn with_any(mut self, nested: C) -> Self {
    self.any = Some(nested);
    self
  }

  /// Ask whether EVERY one of them does — vacuously true where there are none.
  #[inline]
  #[must_use]
  pub fn with_all(mut self, nested: C) -> Self {
    self.all = Some(nested);
    self
  }

  /// Ask whether NONE of them does.
  #[inline]
  #[must_use]
  pub fn with_none(mut self, nested: C) -> Self {
    self.none = Some(nested);
    self
  }

  /// Ask HOW MANY there are — the cardinality of the whole position, which no nested predicate
  /// narrows, exactly as a collection's `count` counts its elements rather than its matches.
  #[inline]
  #[must_use]
  pub fn with_count(mut self, count: MongoCountComparison<i64>) -> Self {
    self.count = Some(count);
    self
  }

  /// The collection the position gathers, and the field of it that carries this document's id.
  #[inline]
  pub const fn source(&self) -> (&MongoRelatedDocument, &'static FieldName) {
    (&self.source, self.points_back)
  }

  /// The predicate SOME of those documents must satisfy, or `None` while the quantifier is absent.
  #[inline]
  pub const fn any(&self) -> Option<&C> {
    self.any.as_ref()
  }

  /// The predicate EVERY one of them must satisfy.
  #[inline]
  pub const fn all(&self) -> Option<&C> {
    self.all.as_ref()
  }

  /// The predicate NONE of them may satisfy.
  #[inline]
  pub const fn none(&self) -> Option<&C> {
    self.none.as_ref()
  }

  /// The comparison the position's cardinality is asked under.
  #[inline]
  pub const fn count(&self) -> Option<&MongoCountComparison<i64>> {
    self.count.as_ref()
  }

  /// How many conjuncts this comparison lowers to — one per quantifier, plus the cardinality's own.
  ///
  /// A present quantifier counts ONCE however much the predicate inside it holds, because those
  /// conjuncts land inside a join that is itself one question — including where the predicate is
  /// empty, which is the quantifier asked of the position itself. A present cardinality counts what
  /// IT counts, its expressions landing beside these rather than inside them.
  #[inline]
  pub const fn conjuncts(&self) -> usize {
    (self.any.is_some() as usize)
      + (self.all.is_some() as usize)
      + (self.none.is_some() as usize)
      + match &self.count {
        Some(count) => count.conjuncts(),
        None => 0,
      }
  }

  /// True while no quantifier is asked, so a lowering would write nothing.
  #[inline]
  pub const fn is_empty(&self) -> bool {
    self.conjuncts() == 0
  }
}

/// The forward reference: the collapsed predicate where the target constrains its id alone, one join
/// where it does not, and nothing at all where it asks nothing.
///
/// # The refusals are raised in the order the FACTS are about the relation
///
/// The WIDTH first, before anything is written and whichever branch follows: `$lookup` joins one
/// field to one field, so a target addressed by several is a broken relation rather than a broken
/// predicate, and the same relation must not answer one filter and refuse another.
///
/// The emptiness next, because a position nobody asked about writes nothing — which is what keeps a
/// record carrying relation slots queryable for every field that is not one.
///
/// The DEPTH last, because it is a fact about the join this position is about to open and a position
/// that opens none — the collapsed form, the empty one — has not reached any ceiling.
impl<C: CollapsibleComparison<Mongo>> ComplexComparison<Mongo> for MongoRefComparison<C> {
  fn conjuncts(&self) -> usize {
    match self.nested.only_id() {
      // The collapsed form is the id's OWN conjuncts, not one: `{ id: { gt: 3, lt: 9 } }` lands on
      // the reference field as two operators at this level, where the join would have held both
      // inside one question.
      Some(id) => id.conjuncts(),
      None => usize::from(!self.nested.is_empty()),
    }
  }

  fn apply<'q>(
    &'q self,
    at: At<'_>,
    mut builder: <Mongo as Backend>::Builder<'q>,
  ) -> Result<<Mongo as Backend>::Builder<'q>, <Mongo as Backend>::Error> {
    let target = one_key(self.target.address())?;
    if let Some(collapsed) = self.nested.only_id() {
      // The whole optimisation: the target's constraint on its own id, merged at the REFERENCE
      // field's address instead. Every operator and every operand is the id comparison's own, so
      // there is no second spelling of the collapsed predicate to keep in step, and no join is
      // opened — the collapsed form stays at THIS depth.
      return collapsed.apply(at, builder);
    }
    if self.nested.is_empty() {
      return Ok(builder);
    }
    let field = self.target.scope(at.depth())?;
    let lookup = Lookup {
      from: self.target.address().table(),
      local: field_path(at),
      foreign: field_key(self.target.address(), target),
      field,
    };
    // The target's own top level, ONE LEVEL IN: the nested comparison frames its fields below this,
    // and a nested relation reads the target's address and its depth off it.
    let (pipeline, reads) = sub_pipeline(
      self
        .nested
        .apply(
          At::nested(self.target.address(), at.depth(), field),
          MongoConjunction::new(),
        )?
        .into_predicate(),
    );
    builder.join(
      lookup.stages(pipeline, populated(field)).into(),
      lookup.reads(reads),
    );
    Ok(builder)
  }
}

/// **MongoDB's answer to the reverse position's crossing map** — the SQL family's row one dialect
/// over, and the two are told apart by that row's `Db: sqlx::Database` head bound.
///
/// It asks NOTHING of `C`, as the SQL row does not: the map carries no item bound, so a row has no
/// promise to prove and this kind's own lowering clause stays on the [`ComplexComparison`] impl below
/// and on the [`ToLoweredRelatedComparison`](crate::comparison::ToLoweredRelatedComparison) row
/// beside this one. See [`ToRelatedComparison`](crate::ToRelatedComparison) for the cycle a restated
/// bound closed on the ordinary mutual pair.
impl<F, C> crate::ToRelatedComparison<C, Mongo> for crate::RelatedFilter<F> {
  type Comparison = MongoDerivedComparison<C>;
}

/// The FORWARD half of the same answer — a `ref` column's widened filter, one dialect over.
///
/// Optional for the SQL row's reason: *nothing was asked* has no value to be, since this kind holds
/// the far side's comparison bare and an emitted comparison has no `Default`.
impl<F, R, C> crate::ToRelatedComparison<C, Mongo> for crate::RefFilter<F, R> {
  type Comparison = Option<MongoRefComparison<C>>;
}

/// The reverse position's LOWERING, one dialect over — reached through the quantifier vocabulary, so
/// a record's emitted lowering names no projection at a generic dialect.
impl<F, C: ComplexComparison<Mongo>> crate::comparison::ToLoweredRelatedComparison<C, Mongo>
  for crate::RelatedFilter<F>
{
  #[inline]
  fn conjuncts(comparison: &Self::Comparison) -> usize {
    ComplexComparison::<Mongo>::conjuncts(comparison)
  }

  #[inline]
  fn apply<'q>(
    comparison: &'q Self::Comparison,
    at: At<'_>,
    builder: <Mongo as Backend>::Builder<'q>,
  ) -> Result<<Mongo as Backend>::Builder<'q>, <Mongo as Backend>::Error> {
    ComplexComparison::<Mongo>::apply(comparison, at, builder)
  }
}

/// The forward position's, its twin — the far side must COLLAPSE here, because the semi-join asks it
/// whether the reference's own field answers the whole question.
impl<F, R, C: CollapsibleComparison<Mongo>> crate::comparison::ToLoweredRelatedComparison<C, Mongo>
  for crate::RefFilter<F, R>
{
  #[inline]
  fn conjuncts(comparison: &Self::Comparison) -> usize {
    ComplexComparison::<Mongo>::conjuncts(comparison)
  }

  #[inline]
  fn apply<'q>(
    comparison: &'q Self::Comparison,
    at: At<'_>,
    builder: <Mongo as Backend>::Builder<'q>,
  ) -> Result<<Mongo as Backend>::Builder<'q>, <Mongo as Backend>::Error> {
    ComplexComparison::<Mongo>::apply(comparison, at, builder)
  }
}

/// The reverse position: one join per quantifier, each consuming its field before the next opens.
impl<C: ComplexComparison<Mongo>> ComplexComparison<Mongo> for MongoDerivedComparison<C> {
  #[inline]
  fn conjuncts(&self) -> usize {
    Self::conjuncts(self)
  }

  fn apply<'q>(
    &'q self,
    at: At<'_>,
    mut builder: <Mongo as Backend>::Builder<'q>,
  ) -> Result<<Mongo as Backend>::Builder<'q>, <Mongo as Backend>::Error> {
    // The PARENT's id is what the child's reference meets, so the width refused here is this
    // document's — the forward kind refuses its target's, and the two are the same law seen from
    // either end.
    let parent = one_key(at.record())?;
    if self.is_empty() {
      return Ok(builder);
    }
    let field = self.source.scope(at.depth())?;
    let lookup = Lookup {
      from: self.source.address().table(),
      local: field_key(at.record(), parent).to_owned(),
      foreign: field_key(self.source.address(), self.points_back),
      field,
    };
    // Built once, because the four quantifiers open four joins of the same shape at the same depth.
    let inner = At::nested(self.source.address(), at.depth(), field);
    push_quantifiers(self, &lookup, inner, &mut builder)?;
    push_related_count(self.count.as_ref(), &lookup, &mut builder);
    Ok(builder)
  }
}

/// The one join every relation opens, and the four names its body always carries.
///
/// A value rather than four arguments threaded through the walk below, for the reason the SQL
/// family's `Correlation` is one: a position asked several quantifiers joins the same two fields
/// several times, and naming them once is what keeps four stages from disagreeing about which pair
/// they meet on.
///
/// Reached by the nested ORDERING too, which opens the same `$lookup` and then does something else
/// with the field it fills — see [`lookup`](Self::lookup) and
/// [`MongoNesting`](crate::query::mongo::MongoNesting). One body, two consumers, so a join written
/// for an order and a join written for a filter cannot differ in which pair they meet on.
pub(crate) struct Lookup<'a> {
  /// The collection joined FROM, which is also the one the package records as read.
  pub(crate) from: &'static FieldName,
  /// The field of THIS document the join matches on — the reference for a forward position, this
  /// document's own `_id` for a reverse one, and the previous hop's array for an ordering chain.
  ///
  /// OWNED where its three neighbours borrow, and the asymmetry is the sources': a forward
  /// position's is a rendered PATH, which [`field_path`] assembles, and every other name here is a
  /// `&'static` one a declaration wrote.
  pub(crate) local: String,
  /// The field of the joined document it matches against — the target's `_id` forward, the child's
  /// own reference back.
  pub(crate) foreign: &'a str,
  /// The field the joined documents land in, and the one the stage beside it reads.
  pub(crate) field: &'a str,
}

impl Lookup<'_> {
  /// The `$lookup` alone, running `pipeline` over the joined collection.
  ///
  /// Split out from [`stages`](Self::stages) because the join and what is DONE with the field it
  /// fills are two decisions: a relation tests the field and drops it, a nested ordering takes one
  /// value off it and drops it. The body they share is this.
  ///
  /// An EMPTY `pipeline` is OMITTED rather than written as `[]`, and the two are the same join: the
  /// key exists to ask the related documents a question, and a position that asks none — a `count`,
  /// an `any` with no predicate, every ordering hop — is the plain field-to-field form. Writing the
  /// empty key would leave a reader deciding whether a `$lookup` with no stages meant something.
  ///
  /// `localField`/`foreignField` BESIDE a `pipeline` is a MongoDB 5.0 form, which is this lane's
  /// server floor for two other reasons already — see
  /// [`lane`](crate::query::mongo) for both. Below it the server refuses the stage rather than
  /// answering from an unfiltered join. An ordering hop passes no pipeline and so asks nothing of
  /// that floor.
  pub(crate) fn lookup(&self, pipeline: Vec<Document>) -> Document {
    let mut lookup = Document::new();
    lookup.insert(FROM, Bson::String(self.from.as_str().to_owned()));
    lookup.insert(LOCAL_FIELD, Bson::String(self.local.clone()));
    lookup.insert(FOREIGN_FIELD, Bson::String(self.foreign.to_owned()));
    lookup.insert(AS, Bson::String(self.field.to_owned()));
    if !pipeline.is_empty() {
      lookup.insert(
        PIPELINE,
        Bson::Array(pipeline.into_iter().map(Bson::Document).collect()),
      );
    }
    stage(LOOKUP, lookup)
  }

  /// The three stages one relation contributes: the `$lookup` running `pipeline` over the joined
  /// collection, the `$match` asking `test`, and the `$project` dropping the field again.
  fn stages(&self, pipeline: Vec<Document>, test: Document) -> [Document; 3] {
    let mut dropped = Document::new();
    dropped.insert(self.field, Bson::Int32(0));

    [
      self.lookup(pipeline),
      stage(MATCH, test),
      stage(PROJECT, dropped),
    ]
  }

  /// Every collection this join's stages read: the one it joins, and whatever a nested relation
  /// under it joined in turn.
  fn reads(&self, nested: Vec<&'static FieldName>) -> Vec<&'static FieldName> {
    let mut reads = Vec::with_capacity(nested.len() + 1);
    reads.push(self.from);
    reads.extend(nested);
    reads
  }
}

/// The four quantifier slots in the order the vocabulary declares them — this kind's walk, held
/// beside the impl rather than inside it so the order is one statement rather than an inlined habit.
///
/// `count` is not here: it asks the children nothing, so it opens a join of a different shape and
/// [`push_related_count`] is where that is said.
fn push_quantifiers<C: ComplexComparison<Mongo>>(
  comparison: &MongoDerivedComparison<C>,
  lookup: &Lookup<'_>,
  at: At<'_>,
  out: &mut MongoConjunction,
) -> Result<(), MongoLoweringError> {
  if let Some(nested) = &comparison.any {
    let (pipeline, reads) = sub_pipeline(inner(nested, at)?);
    out.join(
      lookup.stages(pipeline, populated(lookup.field)).into(),
      lookup.reads(reads),
    );
  }
  if let Some(nested) = &comparison.all {
    let (pipeline, reads) = negated_pipeline(inner(nested, at)?)?;
    out.join(
      lookup.stages(pipeline, empty(lookup.field)).into(),
      lookup.reads(reads),
    );
  }
  if let Some(nested) = &comparison.none {
    let (pipeline, reads) = sub_pipeline(inner(nested, at)?);
    out.join(
      lookup.stages(pipeline, empty(lookup.field)).into(),
      lookup.reads(reads),
    );
  }
  Ok(())
}

/// The `count` slot: the WHOLE position joined, and the cardinality expressions read off the field
/// it landed in.
///
/// The join carries no sub-pipeline, which is the cardinality being the position's rather than the
/// match's — a collection's `count` counts its elements and not its matches, and the reverse
/// position is asked the same way.
///
/// The expressions are [`push_count_slots`]'s own, over a field path that happens to be a join's
/// output rather than a stored array. Its `$isArray` guard is redundant here — a `$lookup` writes an
/// array for every input document, matching or not — and it is kept because the guard belongs to the
/// expression it guards: one authority renders all eight operators, and a second copy without the
/// guard would be a second place for the cardinality to be spelled.
///
/// An EMPTY cardinality comparison asks nothing, so it opens NO join. That is the same reading its
/// conjunct count already has, and without the guard the position would pay for a join and then
/// `$match` on `{}`.
fn push_related_count(
  count: Option<&MongoCountComparison<i64>>,
  lookup: &Lookup<'_>,
  out: &mut MongoConjunction,
) {
  let Some(count) = count.filter(|count| !count.is_empty()) else {
    return;
  };
  let mut expressions = MongoConjunction::new();
  push_count_slots(count, lookup.field, &mut expressions);
  out.join(
    lookup
      .stages(Vec::new(), expressions.into_document())
      .into(),
    lookup.reads(Vec::new()),
  );
}

/// One quantifier's predicate, lowered at the joined collection's own top level.
fn inner<C: ComplexComparison<Mongo>>(
  nested: &C,
  at: At<'_>,
) -> Result<MongoPredicate, MongoLoweringError> {
  Ok(nested.apply(at, MongoConjunction::new())?.into_predicate())
}

/// The stages a `$lookup`'s own pipeline runs, and the collections they read.
///
/// An empty `$match` is NOT written, which is where this parts from a package's own stage list: a
/// package writes one always so that every package is one shape a reader can check, and a no-op
/// stage inside a join is noise a reader has to rule out.
fn sub_pipeline(predicate: MongoPredicate) -> (Vec<Document>, Vec<&'static FieldName>) {
  let (filter, joins, reads) = predicate.into_parts();
  let mut pipeline = Vec::with_capacity(joins.len() + 1);
  if !filter.is_empty() {
    pipeline.push(stage(MATCH, filter));
  }
  pipeline.extend(joins);
  (pipeline, reads)
}

/// [`sub_pipeline`] for `all`, whose join matches the children its predicate EXCLUDES.
///
/// # Errors
///
/// [`MongoLoweringError::NegatedRelation`] where the predicate joined anything of its own. `$nor`
/// takes filter documents and a stage is not one, so a relation nested inside an `all` has nowhere
/// to be negated; the alternative — leaving its stages outside the `$nor` — would apply them
/// unnegated and answer a different question with no error.
fn negated_pipeline(
  predicate: MongoPredicate,
) -> Result<(Vec<Document>, Vec<&'static FieldName>), MongoLoweringError> {
  let (filter, joins, reads) = predicate.into_parts();
  if !joins.is_empty() {
    return Err(MongoLoweringError::NegatedRelation);
  }
  let mut negation = Document::new();
  negation.insert(NOR, Bson::Array(vec![Bson::Document(filter)]));
  Ok((vec![stage(MATCH, negation)], reads))
}

/// `{<field>: {$ne: []}}` — the join found something, which is `any` and the forward reference both.
///
/// The operand is the EMPTY ARRAY rather than a `$size` expression, and the two agree here for a
/// reason particular to a join's output: a `$lookup` writes an array of DOCUMENTS, and a document is
/// never itself an array, so MongoDB's rule that an array operand also matches an array CONTAINING
/// it has nothing to match on.
fn populated(field: &str) -> Document {
  test(field, MongoOperator::Ne)
}

/// `{<field>: {$eq: []}}` — the join found nothing, which is `none` and the outer half of `all`.
fn empty(field: &str) -> Document {
  test(field, MongoOperator::Eq)
}

/// One join field compared against the empty array.
fn test(field: &str, op: MongoOperator) -> Document {
  let mut operators = Document::new();
  operators.insert(op.as_str(), Bson::Array(Vec::new()));

  let mut predicate = Document::new();
  predicate.insert(field, Bson::Document(operators));
  predicate
}

/// `{<name>: <body>}` — one stage, which is a document with exactly one key.
fn stage(name: &str, body: Document) -> Document {
  let mut stage = Document::new();
  stage.insert(name, Bson::Document(body));
  stage
}

/// The ONE field a relation's two sides meet on.
///
/// A `ref` field carries `<Target as Identifiable>::Id` and an id is one field, so a document
/// addressed by several has no name for either side of the join. It bites twice here: [`field_key`]
/// maps a SINGLE-field address onto `_id`, so a wide address has no `_id` for a join to name at all.
///
/// # Errors
///
/// [`MongoLoweringError::RelationWidth`], naming the document whose address is too wide.
pub(crate) fn one_key(row: &RecordAddress) -> Result<&'static FieldName, MongoLoweringError> {
  match row.keys() {
    [only] => Ok(only),
    fields => Err(MongoLoweringError::RelationWidth(RelationWidthError::new(
      row.table(),
      fields.len(),
    ))),
  }
}

#[cfg(test)]
mod tests;