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
//! The text comparison: [`MongoTextComparison`], the regular expression its affix slots lower to,
//! and the escaping that keeps an operand from being read as one.

use bson::{
  Bson, Regex,
  raw::{CString, cstr},
};

use super::{Mongo, MongoCarrier, MongoOperator, field_path, membership};
use crate::{
  TextFilter, TryMapFilter,
  comparison::{At, Backend, ComplexComparison, TextMatch, ToDatabaseComparison, TryFromFilter},
};

/// The start-of-subject assertion a prefix match opens with.
///
/// `\A` rather than `^`, and the reason is the one that decides `END` too: PCRE2 documents `\A`,
/// `\Z` and `\z` as assertions that *only ever match at the very start and end of the subject
/// string, whatever options are set*, where `^` and `$` answer to the `m` option. This family never
/// sets `m` and an operand cannot introduce one — an inline `(?m)` loses its brackets to the
/// escaping — so the two spellings agree today and the absolute pair says so in the pattern rather
/// than in a note about which options were passed.
///
/// It costs nothing at the index: MongoDB names a caret and `\A` as the two left anchors a *prefix
/// expression* may open with, which is the form its planner turns into a range over an index.
const START: &str = "\\A";

/// The end-of-subject assertion a suffix match closes with.
///
/// `\z` rather than `$`, and here the two spellings do NOT agree. PCRE2's dollar *is true only if
/// the current matching point is at the end of the subject string, or immediately before a newline
/// at the end of the string* — so `ends_with: "corp"` spelled `corp$` also matches a field holding
/// `"acme corp\n"`, which is a document the caller did not ask for. `\z` matches only at the end.
const END: &str = "\\z";

/// What a NUL in an operand is written as.
///
/// The BRACED form rather than `\x00`, so the escape cannot run into the operand's next character:
/// `b` is a hex digit, so `"\0b"` written `\x00b` would depend on how many digits `\x` consumes,
/// where `\x{0}b` is closed by its own bracket and depends on nothing.
const NUL: &str = "\\x{0}";

/// Why the pattern's conversion into a [`CString`] cannot fail — see [`escape_into`], which is the
/// only thing that ever writes one.
const NUL_FREE: &str = "a NUL is escaped, so a pattern holds no zero byte";

/// The regular expression `operand` matches as: `kind`'s anchoring around the operand's characters
/// made inert, and `nocase` in the options.
///
/// Public, so a comparison kind declared downstream gets the escaping rather than rewriting it —
/// the standing this family's SQL analogue `like_pattern` has, for the same reason. It is the one
/// thing a second text-shaped kind can take from this one.
///
/// # A member decides two characters here, and the `kind` is therefore an ARGUMENT
///
/// [`TextMatch`] is one vocabulary across both families; where they put the difference is not the
/// same. A SQL dialect answers each member with its own SQL — `instr`, `LIKE '%v%'`,
/// `substr(col, 1, length(v))` — and MongoDB answers all three with one `$regex` whose operand is
/// IDENTICAL and whose anchors differ. So on this backend a member decides two characters and
/// nothing else, which is why it is read beside the operand rather than dispatched on.
///
/// # The operand becomes part of a PATTERN, which is the whole of why this function exists
///
/// MongoDB has no `LIKE`. The three affix forms are one `$regex` under different anchors, so the
/// operand is *read* rather than compared — and the two halves of that hazard are
/// `contains: "a.b"` matching `axb`, which is a wrong result set reported as a right one, and
/// `contains: "("`, which is not a wrong answer but no answer, since the server refuses a pattern
/// it cannot compile.
///
/// # Everything but `[0-9A-Za-z_]` is escaped, and that is a RULE rather than a list
///
/// PCRE2 — MongoDB's engine since 6.1, and PCRE before it — documents both halves of the rule this
/// rests on. A backslash *followed by a character that is not a digit or a letter takes away any
/// special meaning that character may have*, and *only ASCII digits and letters have any special
/// meaning after a backslash*. So quoting every ASCII character outside `[0-9A-Za-z]` is total by
/// the engine's own definition, where a metacharacter LIST would have to be kept in step with a
/// syntax the rule does not depend on. It is Perl's `quotemeta`, which is what `\Q…\E` means, and
/// PCRE is Perl-compatible by construction.
///
/// `_` passes through, and that is the one concession: it needs no escape under either half of the
/// rule, and it is the character a real prefix operand is most likely to contain. MongoDB's prefix
/// optimization takes a left anchor *followed by a string of simple symbols*, so a backslash inside
/// the prefix is what stops it — and `starts_with: "IMG_"` is the case that would pay for a
/// backslash bought for tidiness.
///
/// Non-ASCII passes through as well. No metacharacter has a code point above 127, so quoting one
/// changes nothing except the size of every operand not written in ASCII.
///
/// # The NUL is escaped for a BSON reason rather than a regex one
///
/// A BSON regular expression is stored as two cstrings, so [`Regex::pattern`] is a
/// [`CString`] and a `String` holding a zero byte does not convert. A Rust `&str` may hold one and
/// a GraphQL `String` may carry one, so an operand can — and `\x{0}` is the same character in bytes
/// the cstring admits. That is what makes the conversion below total rather than merely lucky:
/// [`escape_into`] is the only writer and it never emits the one byte the type refuses.
///
/// # The options ride INSIDE the regular expression, because `$options` is not an operator
///
/// `{field: {$regex: "…", $options: "i"}}` is two keys in one field's operator document, and this
/// family's accumulator merges one (field, operator, value) at a time. Two comparisons at one path
/// would then separate them — the second `$regex` overflows into `$and` and its flag does not —
/// leaving a case-insensitive pattern matched case-sensitively, in silence. A BSON regular
/// expression carries its own options and is ONE value, which is MongoDB's own third syntax:
/// `{ <field>: { $regex: /pattern/<options> } }`.
///
/// That closes the option vocabulary at `i`, and deliberately: MongoDB requires `$options` for `x`
/// and `s`, so neither can ride here at all. Neither is reachable from the filter, and an operand
/// cannot smuggle one in, since `(?x)` loses its brackets to the escaping.
///
/// # `i` is PCRE2's caseless matching, which is NOT the collation question SQL's `_nocase` asks
///
/// SQL folds inside the query — `ILIKE` on Postgres, `LOWER` around both sides on MySQL, `lower`
/// on SQLite — and what those fold by is the column's collation or the dialect's own function, so
/// the three do not agree with each other either. MongoDB's `i` is a flag on the regex engine, and
/// `$regex` is documented as *not collation-aware*: a collection collation does not change what it
/// matches and a case-insensitive index does not serve it. So the pattern here is byte-identical to
/// the case-sensitive one and only the options differ.
pub fn text_regex(operand: &str, kind: TextMatch, nocase: bool) -> Regex {
  let mut pattern = String::with_capacity(operand.len() + START.len() + END.len());
  if matches!(kind, TextMatch::Prefix) {
    pattern.push_str(START);
  }
  escape_into(operand, &mut pattern);
  if matches!(kind, TextMatch::Suffix) {
    pattern.push_str(END);
  }
  Regex {
    pattern: CString::try_from(pattern).expect(NUL_FREE),
    options: if nocase { cstr!("i") } else { cstr!("") }.into(),
  }
}

/// `operand`'s characters appended to `out`, each of them inert.
///
/// Separate from the anchoring above so that the anchors are pushed OUTSIDE it, which is the
/// property that keeps `starts_with: "^a"` from anchoring: an operand's `^` arrives here and
/// leaves as a character to look for, where a `format!` around the raw operand would have let it
/// assert a position instead.
fn escape_into(operand: &str, out: &mut String) {
  for ch in operand.chars() {
    if ch == '\0' {
      out.push_str(NUL);
    } else if ch.is_ascii() && !ch.is_ascii_alphanumeric() && ch != '_' {
      out.push('\\');
      out.push(ch);
    } else {
      out.push(ch);
    }
  }
}

mongo_comparison_kind! {
  /// A [`TextFilter`]'s storage-side twin: the same twenty operators, over the type this database
  /// stores the field as.
  ///
  /// # The twelve affix slots read as a table, not as twelve renderings
  ///
  /// `contains` / `starts_with` / `ends_with`, each with a negated and a case-insensitive variant,
  /// are (kind × negated × nocase) triples over one [`TextMatch`] — so the walk is a
  /// twelve-row table and a loop. The SQL family arrives at that same table and then hands its rows
  /// to a per-dialect leaf, because `instr`, `LIKE` and `substr` are three different pieces of SQL.
  /// Here there is no leaf: the triple picks two anchors, one option character and one of two
  /// operator keys, and [`text_regex`] does the rest.
  MongoTextComparison {
    one {
      eq,
      ne,
      gt,
      gte,
      lt,
      lte,
      contains,
      contains_nocase,
      not_contains,
      not_contains_nocase,
      starts_with,
      starts_with_nocase,
      not_starts_with,
      not_starts_with_nocase,
      ends_with,
      ends_with_nocase,
      not_ends_with,
      not_ends_with_nocase,
    }
    many { in_, not_in }
  }
}

impl<V> MongoTextComparison<V> {
  /// Cross a [`TextFilter`] into this comparison, converting each operand with `f`.
  ///
  /// The entry point a DECLARED converter uses (`mongo(into = …)`), and the same call the
  /// trait crossing below makes with the storage type's own [`TryFrom`] supplied.
  ///
  /// All twenty operands cross through the one converter, substring operands included. A stored
  /// form that is not a substring of another stored form where the domain values were — a
  /// compressed or re-encoded text — therefore changes what `contains` MEANS, and that is a
  /// property of the declared conversion rather than something this layer can check.
  ///
  /// The filter is a BOUND rather than a spelling — see
  /// [`SqlScalarComparison::try_from_filter_with`](crate::comparison::sql::SqlScalarComparison::try_from_filter_with),
  /// where the wall that closes is written up.
  pub fn try_from_filter_with<D, I, E, F, X>(filter: X, f: F) -> Result<Self, E>
  where
    X: TryMapFilter<D, V, Mapped = TextFilter<V, I>>,
    F: FnMut(D) -> Result<V, E>,
  {
    let stored = filter.try_map_filter(f)?;
    Ok(Self {
      eq: stored.eq,
      ne: stored.ne,
      gt: stored.gt,
      gte: stored.gte,
      lt: stored.lt,
      lte: stored.lte,
      contains: stored.contains,
      contains_nocase: stored.contains_nocase,
      not_contains: stored.not_contains,
      not_contains_nocase: stored.not_contains_nocase,
      starts_with: stored.starts_with,
      starts_with_nocase: stored.starts_with_nocase,
      not_starts_with: stored.not_starts_with,
      not_starts_with_nocase: stored.not_starts_with_nocase,
      ends_with: stored.ends_with,
      ends_with_nocase: stored.ends_with_nocase,
      not_ends_with: stored.not_ends_with,
      not_ends_with_nocase: stored.not_ends_with_nocase,
      in_: stored.in_,
      not_in: stored.not_in,
    })
  }
}

/// The crossing states the LOWERING's bounds rather than the carrier's alone, so a storage type
/// whose text this backend cannot read is refused where it is DECLARED.
///
/// Its SQL twin cannot do that. Three concrete impls whose bounds disagree have no bound list to
/// restate, so the SQL row names `SqlTextComparison<V, Db>: ComplexComparison<Db>` instead. This
/// family has one lowering, so its two bounds are the honest statement and the error a declarer
/// gets names the missing trait.
///
/// The READING parameter is carried but never read: what a crossing spends is the OPERANDS, and the
/// wire form they arrived under is spent by the time one is built. Generic over it so a declarer's
/// own text type — whose filter names a marker that crate owns — reaches storage exactly as
/// `TextFilter<String>` does.
impl<D, I, V: MongoCarrier + AsRef<str>> ToDatabaseComparison<V, Mongo> for TextFilter<D, I> {
  type Comparison = MongoTextComparison<V>;
}

/// The crossing with no declared converter — see
/// [`MongoScalarComparison`](super::MongoScalarComparison)'s for what the identity case buys. A
/// `String` field stored as `String` is the common one, and it reaches its comparison with an
/// [`Infallible`](core::convert::Infallible) error.
impl<D, I, V: TryFrom<D>> TryFromFilter<TextFilter<D, I>> for MongoTextComparison<V> {
  type Error = V::Error;

  fn try_from_filter(filter: TextFilter<D, I>) -> Result<Self, Self::Error> {
    Self::try_from_filter_with(filter, V::try_from)
  }
}

/// The text kind answers for its two PLAIN operators alone — see the SQL twin's note, whose reading
/// of what the collapse assumes about two columns is this one's too.
impl<V> crate::comparison::ReferentialComparison<Mongo> for MongoTextComparison<V> {
  #[inline]
  fn is_referential(&self) -> bool {
    Self::conjuncts(self) == 1 && (self.eq.is_some() || self.in_.is_some())
  }
}

/// The eight value operators lower as the scalar kind's do; the twelve affix slots are the whole of
/// what is new, and they arrive under exactly TWO keys.
///
/// # A text comparison is the first kind that OVERFLOWS ITS OWN ENTRY
///
/// Every affix slot writes `$regex` or `$not`, so a comparison setting more than one of the six
/// positive forms has two `$regex`es for one field — which no document key can hold. The
/// accumulator's answer is already built and it is MongoDB's own: the first merges and the rest
/// become `$and` branches beside it. Nothing is dropped and nothing is refused.
///
/// That is worth stating because the scalar kind cannot reach it. Its eight operators are eight
/// distinct keys, so its merge never overflows from one comparison and the fold looked like a
/// safeguard against two comparisons at one path. Here it is the ordinary case: twenty slots reach
/// at most ten keys, and the other ten fold.
///
/// # `V: AsRef<str>` is a REQUIREMENT here where SQLite's lowering has none
///
/// The pattern is derived from the operand's characters, so a carrier that binds an opaque encoding
/// has no characters to read — the same bound the two `LIKE` dialects carry, for the same reason.
/// SQLite escapes it with `instr`, which takes the operand as a VALUE; MongoDB has no such form,
/// because `$regex` is the only substring question it asks. So a stored text form with no
/// `AsRef<str>` is filterable with `contains` on exactly one of this crate's four backends.
///
/// The omission is a bound naming the missing trait rather than a filter that matches something
/// plausible:
///
/// ```compile_fail,E0599
/// use ingraph::{
///   At, ComplexComparison, FieldName, RecordAddress, TextFilter, TryFromFilter,
///   comparison::mongo::{MongoConjunction, MongoTextComparison},
/// };
///
/// // A text field stored as a blob — `MongoCarrier` through the crate's own `Vec<u8>` row, and no
/// // `AsRef<str>` for a pattern to be built from.
/// let c = MongoTextComparison::<Vec<u8>>::try_from_filter(
///   TextFilter::<String>::new().with_contains("cam".to_owned()),
/// )
/// .unwrap();
/// const ROW: RecordAddress = RecordAddress::new(FieldName::new("t"), &[FieldName::new("id")]);
/// let frame = At::new(&ROW).frame(FieldName::new("n"));
/// c.apply(frame.at(), MongoConjunction::new()).unwrap();
/// ```
///
/// 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 has to be positive:
///
/// ```
/// use bson::doc;
/// use ingraph::{
///   At, ComplexComparison, FieldName, RecordAddress, TextFilter, TryFromFilter,
///   comparison::mongo::{MongoConjunction, MongoTextComparison},
/// };
///
/// let c = MongoTextComparison::<String>::try_from_filter(
///   TextFilter::<String>::new().with_contains("cam".to_owned()),
/// )
/// .unwrap();
/// const ROW: RecordAddress = RecordAddress::new(FieldName::new("t"), &[FieldName::new("id")]);
/// let frame = At::new(&ROW).frame(FieldName::new("n"));
/// let filter = c
///   .apply(frame.at(), MongoConjunction::new())
///   .unwrap()
///   .into_document();
///
/// assert_eq!(filter, doc! { "n": { "$regex": bson::Regex {
///   pattern: "cam".try_into().unwrap(),
///   options: "".try_into().unwrap(),
/// } } });
/// ```
impl<V: MongoCarrier + AsRef<str>> ComplexComparison<Mongo> for MongoTextComparison<V> {
  #[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> {
    let field = field_path(at);
    for (slot, op) in [
      (&self.eq, MongoOperator::Eq),
      (&self.ne, MongoOperator::Ne),
      (&self.gt, MongoOperator::Gt),
      (&self.gte, MongoOperator::Gte),
      (&self.lt, MongoOperator::Lt),
      (&self.lte, MongoOperator::Lte),
    ] {
      if let Some(value) = slot {
        builder.merge(&field, op, value.to_bson());
      }
    }
    // The twelve affix slots, in the order the struct declares them: three kinds, each plain,
    // case-insensitive, negated, and both.
    let matches: [(&Option<V>, TextMatch, bool, bool); 12] = [
      (&self.contains, TextMatch::Contains, false, false),
      (&self.contains_nocase, TextMatch::Contains, false, true),
      (&self.not_contains, TextMatch::Contains, true, false),
      (&self.not_contains_nocase, TextMatch::Contains, true, true),
      (&self.starts_with, TextMatch::Prefix, false, false),
      (&self.starts_with_nocase, TextMatch::Prefix, false, true),
      (&self.not_starts_with, TextMatch::Prefix, true, false),
      (&self.not_starts_with_nocase, TextMatch::Prefix, true, true),
      (&self.ends_with, TextMatch::Suffix, false, false),
      (&self.ends_with_nocase, TextMatch::Suffix, false, true),
      (&self.not_ends_with, TextMatch::Suffix, true, false),
      (&self.not_ends_with_nocase, TextMatch::Suffix, true, true),
    ];
    for (slot, kind, negated, nocase) in matches {
      if let Some(value) = slot {
        let op = if negated {
          MongoOperator::Not
        } else {
          MongoOperator::Regex
        };
        builder.merge(
          &field,
          op,
          Bson::RegularExpression(text_regex(value.as_ref(), kind, nocase)),
        );
      }
    }
    for (slot, op) in [
      (&self.in_, MongoOperator::In),
      (&self.not_in, MongoOperator::Nin),
    ] {
      if let Some(values) = slot {
        builder.merge(&field, op, membership(values));
      }
    }
    Ok(builder)
  }
}

#[cfg(test)]
mod tests;