Skip to main content

rete_core/
term_order.rs

1//! The order of the terms inside a dictionary section (SPEC.md §5).
2//!
3//! Dictionary ids are lexical ranks, so *which* lexical order a section uses
4//! decides what id order means.
5//!
6//! * [`TermOrder::Bytewise`] is the order of formats `0x05` to `0x07`: the
7//!   UTF-8 bytes of the stored token (`<iri>`, `_:b`, `"lit"…`). It is not the
8//!   SPARQL order: `<…Ng8130_provenance>` sorts before `<…Ng8>` because `1`
9//!   is below `>`, and literals sort before IRIs before blank nodes.
10//! * [`TermOrder::Sparql`] is the order of format `0x08`. Terms group by kind,
11//!   in the order SPARQL 1.1 §15.1 gives (blank nodes, IRIs, literals), and
12//!   within a group sort so that **id order is the engine's `ORDER BY` order**
13//!   wherever the engine's order is a function of the term alone and cheap to
14//!   state:
15//!
16//!   | group | terms | sorted by |
17//!   |---|---|---|
18//!   | 0 blank | `_:…` | the token |
19//!   | 1 IRI | `<…>` | the IRI text without `<` and `>`, by code point (UTF-8 byte order) |
20//!   | 2 text | simple, `xsd:string` and language-tagged literals | lexical form unescaped, then datatype, then lower-cased tag, then the token |
21//!   | 3 typed | every other literal (numbers, dates, booleans, other datatypes) and anything else | the token, bytewise |
22//!   | 4 triple | `<< … >>` | the token |
23//!
24//!   Groups 0, 1, 2 and 4 are **order-exact**: two terms of one section in
25//!   those groups compare as their ids do. Group 3 is not: `ORDER BY` puts
26//!   numbers by value, and the dictionary does not.
27//!
28//! One function, [`TermOrder::cmp`], is the order; every writer sorts with it
29//! and every lookup searches with it, so a file and its reader cannot disagree.
30
31use std::cmp::Ordering;
32
33/// How a dictionary section orders its terms. The format generation says
34/// which: `0x05`-`0x07` are [`Bytewise`](Self::Bytewise), `0x08` is
35/// [`Sparql`](Self::Sparql).
36#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
37pub enum TermOrder {
38    /// The bytes of the stored token.
39    #[default]
40    Bytewise,
41    /// Kind, then the SPARQL `ORDER BY` order; see the module docs.
42    Sparql,
43}
44
45thread_local! {
46    static BUILDER_ORDER: std::cell::Cell<Option<TermOrder>> = const { std::cell::Cell::new(None) };
47}
48
49/// Run `f` with every [`crate::DictionaryBuilder::new`] on this thread sorting in
50/// `order`. The tests that need an input in an older generation (`0x05` to
51/// `0x07` are byte-ordered) build it this way; a builder made on another
52/// thread is not affected.
53#[doc(hidden)]
54pub fn with_builder_order<R>(order: TermOrder, f: impl FnOnce() -> R) -> R {
55    struct Restore(Option<TermOrder>);
56    impl Drop for Restore {
57        fn drop(&mut self) {
58            BUILDER_ORDER.with(|c| c.set(self.0));
59        }
60    }
61    let _restore = Restore(BUILDER_ORDER.with(|c| c.replace(Some(order))));
62    f()
63}
64
65/// The order [`with_builder_order`] set on this thread, if any.
66pub(crate) fn builder_order_override() -> Option<TermOrder> {
67    BUILDER_ORDER.with(|c| c.get())
68}
69
70/// Term group (the kind ranks of [`TermOrder::Sparql`]).
71pub const G_BLANK: u8 = 0;
72/// IRIs.
73pub const G_IRI: u8 = 1;
74/// Simple, `xsd:string` and language-tagged literals.
75pub const G_TEXT: u8 = 2;
76/// Literals of any other datatype, and anything that is no term at all.
77pub const G_TYPED: u8 = 3;
78/// RDF-star quoted triples.
79pub const G_TRIPLE: u8 = 4;
80/// Number of groups.
81pub const GROUPS: usize = 5;
82
83const XSD_STRING_SUFFIX: &str = "^^<http://www.w3.org/2001/XMLSchema#string>";
84
85/// The group of a term token.
86pub fn group(t: &[u8]) -> u8 {
87    match t.first() {
88        Some(b'<') => {
89            if t.starts_with(b"<<") && t.ends_with(b">>") {
90                G_TRIPLE
91            } else {
92                G_IRI
93            }
94        }
95        Some(b'_') if t.get(1) == Some(&b':') => G_BLANK,
96        Some(b'"') => match std::str::from_utf8(t) {
97            Ok(s) => literal_group(s),
98            Err(_) => G_TYPED,
99        },
100        _ => G_TYPED,
101    }
102}
103
104fn literal_group(s: &str) -> u8 {
105    match crate::terms::literal_parts(s) {
106        Some((_, "")) => G_TEXT,
107        Some((_, suffix)) if suffix.starts_with('@') || suffix == XSD_STRING_SUFFIX => G_TEXT,
108        _ => G_TYPED,
109    }
110}
111
112/// The IRI text of an `<…>` token (the whole token when it is not bracketed,
113/// as the engine's `ORDER BY` reads it).
114fn iri_text(t: &[u8]) -> &[u8] {
115    if t.len() >= 2 && t[0] == b'<' && t[t.len() - 1] == b'>' {
116        &t[1..t.len() - 1]
117    } else {
118        t
119    }
120}
121
122fn lexical(body: &str) -> std::borrow::Cow<'_, str> {
123    if body.contains('\\') {
124        std::borrow::Cow::Owned(crate::terms::unescape_literal(body))
125    } else {
126        std::borrow::Cow::Borrowed(body)
127    }
128}
129
130/// 0 `rdf:dirLangString`, 1 `rdf:langString`, 2 `xsd:string`: the order of
131/// those datatype IRIs as strings.
132fn datatype_rank(suffix: &str) -> u8 {
133    if let Some(tag) = suffix.strip_prefix('@') {
134        if tag.contains("--") {
135            0
136        } else {
137            1
138        }
139    } else {
140        2
141    }
142}
143
144/// Order two group-2 tokens: `(lexical form, datatype, lower-cased tag, token)`,
145/// the engine's text-literal order (`sparql::value::order_cmp`).
146fn text_cmp(a: &[u8], b: &[u8]) -> Ordering {
147    // Both passed `literal_group`, so both are UTF-8 and well formed.
148    let (Ok(sa), Ok(sb)) = (std::str::from_utf8(a), std::str::from_utf8(b)) else {
149        return a.cmp(b);
150    };
151    let (Some((ba, xa)), Some((bb, xb))) = (
152        crate::terms::literal_parts(sa),
153        crate::terms::literal_parts(sb),
154    ) else {
155        return a.cmp(b);
156    };
157    lexical(ba)
158        .as_ref()
159        .cmp(lexical(bb).as_ref())
160        .then_with(|| datatype_rank(xa).cmp(&datatype_rank(xb)))
161        .then_with(|| {
162            let ta = xa.strip_prefix('@').unwrap_or("").bytes();
163            let tb = xb.strip_prefix('@').unwrap_or("").bytes();
164            ta.map(|c| c.to_ascii_lowercase())
165                .cmp(tb.map(|c| c.to_ascii_lowercase()))
166        })
167        .then_with(|| a.cmp(b))
168}
169
170/// A term being looked up in a section, read once: its group and, for a text
171/// literal, the parts its order is made of.
172///
173/// [`TermOrder::cmp`] reads both of its terms on every call: for two text
174/// literals that is the group of each (a UTF-8 check and a scan for the
175/// closing quote) and then their parts again. A lookup compares one term
176/// against a few dozen stored ones in every section it searches, so it read
177/// the term it was looking for a few hundred times: a `BIND` that made
178/// 195,000 new strings spent five times as long finding out they were new as
179/// it did on a byte-ordered file. [`Probe::cmp_stored`] is the same order
180/// with the looked-up side read once and the stored side read at most once.
181pub struct Probe<'t> {
182    order: TermOrder,
183    token: &'t [u8],
184    group: u8,
185    /// A text literal's lexical form, datatype rank and language tag.
186    text: Option<(std::borrow::Cow<'t, str>, u8, &'t str)>,
187}
188
189impl Probe<'_> {
190    /// `order.cmp(stored, term)`: where a stored token sorts against the term
191    /// this probe was made for.
192    pub fn cmp_stored(&self, a: &[u8]) -> Ordering {
193        let b = self.token;
194        if self.order == TermOrder::Bytewise {
195            return a.cmp(b);
196        }
197        if a.is_empty() || b.is_empty() {
198            return a.len().cmp(&b.len());
199        }
200        // The stored token's group. Only a literal against a literal has to
201        // be read to its closing quote: text and typed literals are
202        // neighbours, and every other group shows in the first bytes.
203        let mut parts: Option<(&str, &str)> = None;
204        let ga = match a[0] {
205            b'<' => {
206                if a.starts_with(b"<<") && a.ends_with(b">>") {
207                    G_TRIPLE
208                } else {
209                    G_IRI
210                }
211            }
212            b'_' if a.get(1) == Some(&b':') => G_BLANK,
213            b'"' => {
214                if self.group < G_TEXT {
215                    return Ordering::Greater;
216                }
217                if self.group > G_TYPED {
218                    return Ordering::Less;
219                }
220                match std::str::from_utf8(a).ok().map(crate::terms::literal_parts) {
221                    Some(Some((body, suffix)))
222                        if suffix.is_empty()
223                            || suffix.starts_with('@')
224                            || suffix == XSD_STRING_SUFFIX =>
225                    {
226                        parts = Some((body, suffix));
227                        G_TEXT
228                    }
229                    _ => G_TYPED,
230                }
231            }
232            _ => G_TYPED,
233        };
234        if ga != self.group {
235            return ga.cmp(&self.group);
236        }
237        match (ga, parts, &self.text) {
238            (G_IRI, _, _) => iri_text(a).cmp(iri_text(b)).then_with(|| a.cmp(b)),
239            (G_TEXT, Some((ba, xa)), Some((lex, rank, tag))) => lexical(ba)
240                .as_ref()
241                .cmp(lex.as_ref())
242                .then_with(|| datatype_rank(xa).cmp(rank))
243                .then_with(|| {
244                    let ta = xa.strip_prefix('@').unwrap_or("").bytes();
245                    ta.map(|c| c.to_ascii_lowercase())
246                        .cmp(tag.bytes().map(|c| c.to_ascii_lowercase()))
247                })
248                .then_with(|| a.cmp(b)),
249            _ => a.cmp(b),
250        }
251    }
252}
253
254impl TermOrder {
255    /// Read `term` once, to compare stored tokens against it
256    /// ([`Probe::cmp_stored`]).
257    pub fn probe(self, term: &[u8]) -> Probe<'_> {
258        let group = if self == TermOrder::Sparql && !term.is_empty() {
259            group(term)
260        } else {
261            G_TYPED
262        };
263        let text = (self == TermOrder::Sparql && group == G_TEXT)
264            .then(|| {
265                let s = std::str::from_utf8(term).ok()?;
266                let (body, suffix) = crate::terms::literal_parts(s)?;
267                Some((
268                    lexical(body),
269                    datatype_rank(suffix),
270                    suffix.strip_prefix('@').unwrap_or(""),
271                ))
272            })
273            .flatten();
274        Probe {
275            order: self,
276            token: term,
277            group,
278            text,
279        }
280    }
281
282    /// Compare two term tokens in this order. A total order: two tokens
283    /// compare equal only when they are the same bytes. The empty slice sorts
284    /// before everything (a chunk directory's first key is empty).
285    pub fn cmp(self, a: &[u8], b: &[u8]) -> Ordering {
286        match self {
287            TermOrder::Bytewise => a.cmp(b),
288            TermOrder::Sparql => {
289                if a.is_empty() || b.is_empty() {
290                    return a.len().cmp(&b.len());
291                }
292                let (ga, gb) = (group(a), group(b));
293                if ga != gb {
294                    return ga.cmp(&gb);
295                }
296                match ga {
297                    G_IRI => iri_text(a).cmp(iri_text(b)).then_with(|| a.cmp(b)),
298                    G_TEXT => text_cmp(a, b),
299                    _ => a.cmp(b),
300                }
301            }
302        }
303    }
304
305    /// `self.cmp(a, b)` on strings.
306    pub fn cmp_str(self, a: &str, b: &str) -> Ordering {
307        self.cmp(a.as_bytes(), b.as_bytes())
308    }
309
310    /// A chunk directory's routing key between two neighbouring chunks: a
311    /// short byte string `k` with `prev_last < k <= first` in this order.
312    ///
313    /// Bytewise it is [`crate::dict::shortest_separator`]. In the SPARQL order
314    /// two IRIs get the shortest separator of their texts, written as an IRI
315    /// token; every other boundary keeps `first` whole.
316    pub fn separator(self, prev_last: &[u8], first: &[u8]) -> Vec<u8> {
317        if self == TermOrder::Sparql {
318            let iri = |t: &[u8]| group(t) == G_IRI && t.len() >= 2 && t[t.len() - 1] == b'>';
319            if iri(prev_last) && iri(first) && self.cmp(prev_last, first) == Ordering::Less {
320                let s = crate::dict::shortest_separator(iri_text(prev_last), iri_text(first));
321                let mut k = Vec::with_capacity(s.len() + 2);
322                k.push(b'<');
323                k.extend_from_slice(&s);
324                k.push(b'>');
325                return k;
326            }
327            if let Some(k) = self.text_separator(prev_last, first) {
328                return k;
329            }
330            if let Some(k) = self.typed_separator(prev_last, first) {
331                return k;
332            }
333            return first.to_vec();
334        }
335        crate::dict::shortest_separator(prev_last, first)
336    }
337}
338
339impl TermOrder {
340    /// The separator of two typed-literal tokens. The group is ordered by the
341    /// token's bytes, so a key that is a *typed literal with a shortened
342    /// lexical form* (`"UklGRb"^^<dt>`: `first`'s body cut one byte past the
343    /// divergence, closed again, with `first`'s own suffix) routes between
344    /// them, and a long literal (an embedded image, a WKT polygon) costs the
345    /// directory a few bytes, not its whole text. Keeping `first` whole made
346    /// every directory entry as large as the literal: a file of 137 KiB
347    /// literals had an 800 MB directory, which a first scan read. The cut must
348    /// be re-closed rather than truncated: an unterminated `"…` reads as a
349    /// simple literal, the text group, which sorts below every typed token.
350    /// `None` when no short key routes (the caller keeps `first`).
351    fn typed_separator(self, prev_last: &[u8], first: &[u8]) -> Option<Vec<u8>> {
352        if group(prev_last) != G_TYPED || group(first) != G_TYPED || prev_last >= first {
353            return None;
354        }
355        let sf = std::str::from_utf8(first).ok()?;
356        let (body, suffix) = crate::terms::literal_parts(sf)?;
357        if suffix.is_empty() || suffix.starts_with('@') {
358            return None;
359        }
360        let shared = prev_last
361            .iter()
362            .zip(first)
363            .take_while(|(a, b)| a == b)
364            .count();
365        // First candidate: one byte past the divergence. A byte below `"` in
366        // `first` (a space, `!`) would put the closing quote above it; try the
367        // next cut, a few times.
368        let mut end = shared.max(1);
369        for _ in 0..8 {
370            end += 1;
371            while end <= body.len() && !body.is_char_boundary(end - 1) {
372                end += 1;
373            }
374            let cut = end - 1;
375            if cut >= body.len() || !body.is_char_boundary(cut) {
376                return None;
377            }
378            let mut key = Vec::with_capacity(cut + suffix.len() + 2);
379            key.push(b'"');
380            key.extend_from_slice(&body.as_bytes()[..cut]);
381            key.push(b'"');
382            key.extend_from_slice(suffix.as_bytes());
383            let routes = group(&key) == G_TYPED
384                && self.cmp(prev_last, &key) == Ordering::Less
385                && self.cmp(&key, first) != Ordering::Greater;
386            if routes {
387                return Some(key);
388            }
389        }
390        None
391    }
392
393    /// The separator of two text literals: a simple literal whose lexical form
394    /// is the shortest string strictly between the two lexical forms (so no
395    /// datatype or tag decides). `None` when there is none (equal or prefix
396    /// lexical forms): the caller keeps `first` whole.
397    fn text_separator(self, prev_last: &[u8], first: &[u8]) -> Option<Vec<u8>> {
398        if group(prev_last) != G_TEXT || group(first) != G_TEXT {
399            return None;
400        }
401        let (sp, sf) = (
402            std::str::from_utf8(prev_last).ok()?,
403            std::str::from_utf8(first).ok()?,
404        );
405        let (bp, _) = crate::terms::literal_parts(sp)?;
406        let (bf, _) = crate::terms::literal_parts(sf)?;
407        let (lp, lf) = (lexical(bp), lexical(bf));
408        if lp.as_ref() >= lf.as_ref() {
409            return None;
410        }
411        let shared = lp
412            .as_bytes()
413            .iter()
414            .zip(lf.as_bytes())
415            .take_while(|(a, b)| a == b)
416            .count();
417        // One byte past the shared prefix, then to a whole character.
418        let mut end = shared + 1;
419        while end < lf.len() && !lf.is_char_boundary(end) {
420            end += 1;
421        }
422        if end >= lf.len() {
423            return None; // the whole of `first`'s lexical form: no shorter key
424        }
425        let key = crate::terms::make_literal(&lf[..end], None, None);
426        // Belt and braces: the key must route between the two.
427        (self.cmp(prev_last, key.as_bytes()) == Ordering::Less
428            && self.cmp(key.as_bytes(), first) != Ordering::Greater)
429            .then(|| key.into_bytes())
430    }
431}
432
433/// How many terms of a section are in each group.
434#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
435pub struct GroupCounts(pub [u32; GROUPS]);
436
437impl GroupCounts {
438    /// Count one term.
439    pub fn add(&mut self, t: &[u8]) {
440        self.0[group(t) as usize] += 1;
441    }
442
443    /// Ids `1..=lit_start()` are blank nodes and IRIs.
444    pub fn lit_start(&self) -> u32 {
445        self.0[G_BLANK as usize].saturating_add(self.0[G_IRI as usize])
446    }
447
448    /// Ids `lit_start()+1..=text_end()` are text literals.
449    pub fn text_end(&self) -> u32 {
450        self.lit_start().saturating_add(self.0[G_TEXT as usize])
451    }
452
453    /// Ids `text_end()+1..=lit_end()` are typed literals; everything after
454    /// is a quoted triple.
455    pub fn lit_end(&self) -> u32 {
456        self.text_end().saturating_add(self.0[G_TYPED as usize])
457    }
458
459    /// Terms in all groups.
460    pub fn total(&self) -> u64 {
461        self.0.iter().map(|&n| n as u64).sum()
462    }
463
464    /// Is section-local id `id` in an order-exact group, so that it compares
465    /// with another exact id of the same section as the terms do?
466    pub fn is_exact(&self, id: u32) -> bool {
467        !(id > self.text_end() && id <= self.lit_end())
468    }
469}
470
471#[cfg(test)]
472mod tests {
473    use super::*;
474
475    fn sorted(order: TermOrder, mut v: Vec<&str>) -> Vec<&str> {
476        v.sort_by(|a, b| order.cmp_str(a, b));
477        v
478    }
479
480    #[test]
481    fn iri_prefix_sorts_before_its_extensions() {
482        let v = vec![
483            "<http://x/Ng8130_provenance>",
484            "<http://x/Ng8>",
485            "<http://x/Ng8->",
486        ];
487        assert_eq!(
488            sorted(TermOrder::Sparql, v.clone()),
489            vec![
490                "<http://x/Ng8>",
491                "<http://x/Ng8->",
492                "<http://x/Ng8130_provenance>"
493            ]
494        );
495        // the bytewise order is the one that put the extension first
496        assert_eq!(
497            TermOrder::Bytewise.cmp_str("<http://x/Ng8130_provenance>", "<http://x/Ng8>"),
498            Ordering::Less
499        );
500    }
501
502    #[test]
503    fn kinds_group_in_sparql_order() {
504        let v = vec![
505            "\"z\"",
506            "<http://a>",
507            "_:b",
508            "\"5\"^^<http://www.w3.org/2001/XMLSchema#integer>",
509            "<<_:a <http://p> _:b>>",
510            "\"a\"@en",
511        ];
512        assert_eq!(
513            sorted(TermOrder::Sparql, v),
514            vec![
515                "_:b",
516                "<http://a>",
517                "\"a\"@en",
518                "\"z\"",
519                "\"5\"^^<http://www.w3.org/2001/XMLSchema#integer>",
520                "<<_:a <http://p> _:b>>",
521            ]
522        );
523    }
524
525    #[test]
526    fn text_literals_order_by_lexical_form_not_by_closing_quote() {
527        let v = vec!["\"a b\"", "\"a\"", "\"a\"@en", "\"a!\"", "\"B\""];
528        // lexical: "B" < "a" < "a b" < "a!"; at "a": rdf:langString < xsd:string
529        assert_eq!(
530            sorted(TermOrder::Sparql, v),
531            vec!["\"B\"", "\"a\"@en", "\"a\"", "\"a b\"", "\"a!\""]
532        );
533    }
534
535    #[test]
536    fn escapes_compare_unescaped() {
537        // `a"b` unescaped sorts between `a!` and `a#`; escaped (`a\"b`) the
538        // backslash would put it after `a#`.
539        let v = vec!["\"a#\"", "\"a\\\"b\"", "\"a!\""];
540        assert_eq!(
541            sorted(TermOrder::Sparql, v),
542            vec!["\"a!\"", "\"a\\\"b\"", "\"a#\""]
543        );
544    }
545
546    #[test]
547    fn non_ascii_is_codepoint_order() {
548        let v = vec!["<http://x/\u{e9}>", "<http://x/z>", "<http://x/\u{1f600}>"];
549        assert_eq!(
550            sorted(TermOrder::Sparql, v),
551            vec!["<http://x/z>", "<http://x/\u{e9}>", "<http://x/\u{1f600}>"]
552        );
553    }
554
555    #[test]
556    fn xsd_string_is_text_and_other_datatypes_are_typed() {
557        assert_eq!(
558            group(b"\"x\"^^<http://www.w3.org/2001/XMLSchema#string>"),
559            G_TEXT
560        );
561        assert_eq!(group(b"\"x\"^^<http://example/dt>"), G_TYPED);
562        assert_eq!(group(b"\"x\""), G_TEXT);
563        assert_eq!(group(b"\"x\"@en-GB"), G_TEXT);
564        assert_eq!(group(b"\"x\"@en--ltr"), G_TEXT);
565        assert_eq!(group(b"_:b"), G_BLANK);
566        assert_eq!(group(b"<<a b c>>"), G_TRIPLE);
567        assert_eq!(group(b"<x>"), G_IRI);
568        assert_eq!(group(b""), G_TYPED);
569    }
570
571    /// A probe is the order: `probe(b).cmp_stored(a)` is `cmp(a, b)` for every
572    /// pair, in both orders, over well-formed and malformed tokens alike (a
573    /// file is searched with one and was sorted with the other).
574    #[test]
575    fn a_probe_compares_as_the_order_does() {
576        let mut tokens: Vec<Vec<u8>> = [
577            "",
578            "_:b0",
579            "_:b1",
580            "_",
581            "<http://x/a>",
582            "<http://x/a/b>",
583            "<http://x/Ng8>",
584            "<http://x/Ng8130_provenance>",
585            "<<<s> <p> <o>>>",
586            "<<",
587            "<",
588            "<unclosed",
589            "\"\"",
590            "\"a\"",
591            "\"a\"@en",
592            "\"a\"@EN",
593            "\"a\"@en-GB",
594            "\"a\"@en--ltr",
595            "\"a\"^^<http://www.w3.org/2001/XMLSchema#string>",
596            "\"a\"^^<http://www.w3.org/2001/XMLSchema#integer>",
597            "\"ab\"",
598            "\"a\\\"b\"",
599            "\"a\\nb\"",
600            "\"a\\\\\"",
601            "\"A\"",
602            "\"\u{e9}t\u{e9}\"",
603            "\"\u{e9}t\u{e9}\"@fr",
604            "\"10\"^^<http://www.w3.org/2001/XMLSchema#integer>",
605            "\"9\"^^<http://www.w3.org/2001/XMLSchema#integer>",
606            "\"2018-04-05\"^^<http://www.w3.org/2001/XMLSchema#date>",
607            "\"unclosed",
608            "\"a\"junk",
609            "\"a\"^^",
610            "\"",
611            "plain",
612            "42",
613        ]
614        .iter()
615        .map(|t| t.as_bytes().to_vec())
616        .collect();
617        // Not UTF-8, in each kind of token.
618        tokens.push(b"\"\xff\"".to_vec());
619        tokens.push(b"\"a\"@\xff".to_vec());
620        tokens.push(b"<http://x/\xff>".to_vec());
621        tokens.push(vec![0xff, 0xfe]);
622        for order in [TermOrder::Bytewise, TermOrder::Sparql] {
623            for b in &tokens {
624                let probe = order.probe(b);
625                for a in &tokens {
626                    assert_eq!(
627                        probe.cmp_stored(a),
628                        order.cmp(a, b),
629                        "{order:?}: {:?} against {:?}",
630                        String::from_utf8_lossy(a),
631                        String::from_utf8_lossy(b)
632                    );
633                }
634            }
635        }
636    }
637
638    #[test]
639    fn it_is_a_total_order() {
640        let terms = [
641            "_:a",
642            "_:b",
643            "<a>",
644            "<a",
645            "<ab>",
646            "\"x\"",
647            "\"x\"^^<http://www.w3.org/2001/XMLSchema#string>",
648            "\"X\"@EN",
649            "\"X\"@en",
650            "\"1\"^^<http://www.w3.org/2001/XMLSchema#integer>",
651            "<<a b c>>",
652            "junk",
653        ];
654        for o in [TermOrder::Bytewise, TermOrder::Sparql] {
655            for a in terms {
656                for b in terms {
657                    let ab = o.cmp_str(a, b);
658                    assert_eq!(ab, o.cmp_str(b, a).reverse(), "{a} {b}");
659                    assert_eq!(ab == Ordering::Equal, a == b, "{a} {b}");
660                    for c in terms {
661                        if ab == Ordering::Less && o.cmp_str(b, c) == Ordering::Less {
662                            assert_eq!(o.cmp_str(a, c), Ordering::Less, "{a} {b} {c}");
663                        }
664                    }
665                }
666            }
667        }
668    }
669
670    #[test]
671    fn a_separator_routes_between_its_neighbours() {
672        let o = TermOrder::Sparql;
673        let pairs = [
674            ("<http://x/Ng8>", "<http://x/Ng8130_provenance>"),
675            ("<http://x/a>", "<http://x/b>"),
676            ("<http://x/z>", "\"lit\""),
677            ("\"a\"", "\"b\""),
678            ("\"aaa\"@en", "\"abcdef\"@en"),
679            ("\"caf\u{e9}1\"", "\"caf\u{e9}2 and much more text\""),
680        ];
681        for (p, f) in pairs {
682            let k = o.separator(p.as_bytes(), f.as_bytes());
683            assert_eq!(o.cmp(p.as_bytes(), &k), Ordering::Less, "{p} < key {k:?}");
684            assert_ne!(
685                o.cmp(&k, f.as_bytes()),
686                Ordering::Greater,
687                "key {k:?} <= {f}"
688            );
689        }
690        // and for text literals
691        let k = o.separator(b"\"aaa\"", b"\"abcdef ghij klmn\"");
692        assert_eq!(k, b"\"ab\"");
693        // shorter than the whole term for IRIs
694        let k = o.separator(b"<http://example.org/aaa/1>", b"<http://example.org/bbb/2>");
695        assert!(k.len() < b"<http://example.org/bbb/2>".len());
696    }
697
698    #[test]
699    fn counts_name_the_exact_ranges() {
700        let mut c = GroupCounts::default();
701        for t in [
702            "_:a",
703            "<a>",
704            "<b>",
705            "\"x\"",
706            "\"1\"^^<http://e/d>",
707            "\"2\"^^<http://e/d>",
708        ] {
709            c.add(t.as_bytes());
710        }
711        assert_eq!((c.lit_start(), c.text_end(), c.lit_end()), (3, 4, 6));
712        assert!(c.is_exact(1) && c.is_exact(4));
713        assert!(!c.is_exact(5) && !c.is_exact(6));
714        assert!(c.is_exact(7));
715    }
716
717    #[test]
718    fn typed_literal_separators_are_short_and_route() {
719        let o = TermOrder::Sparql;
720        let dt = "^^<http://www.w3.org/2001/XMLSchema#base64Binary>";
721        let big = |head: &str| format!("\"{head}{}\"{dt}", "Q".repeat(150_000));
722        let (a, b) = (big("UklGRaaa"), big("UklGRbbb"));
723        assert!(o.cmp_str(&a, &b) == Ordering::Less);
724        let k = o.separator(a.as_bytes(), b.as_bytes());
725        assert!(
726            k.len() < dt.len() + 16,
727            "a {} B key for a 150 KB literal",
728            k.len()
729        );
730        assert_eq!(o.cmp(a.as_bytes(), &k), Ordering::Less);
731        assert_ne!(o.cmp(&k, b.as_bytes()), Ordering::Greater);
732        // A cut that ends on a closing quote would read as a text literal and
733        // sort below the typed group, mis-routing the previous chunk's last
734        // term: the writer keeps the whole term there.
735        let (p, f) = ("\"ab!\"^^<http://e/d>", "\"ab\"^^<http://e/d>");
736        assert_eq!(o.cmp_str(p, f), Ordering::Less);
737        let k = o.separator(p.as_bytes(), f.as_bytes());
738        assert_eq!(o.cmp(p.as_bytes(), &k), Ordering::Less);
739        assert_ne!(o.cmp(&k, f.as_bytes()), Ordering::Greater);
740    }
741}