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            return first.to_vec();
331        }
332        crate::dict::shortest_separator(prev_last, first)
333    }
334}
335
336impl TermOrder {
337    /// The separator of two text literals: a simple literal whose lexical form
338    /// is the shortest string strictly between the two lexical forms (so no
339    /// datatype or tag decides). `None` when there is none (equal or prefix
340    /// lexical forms): the caller keeps `first` whole.
341    fn text_separator(self, prev_last: &[u8], first: &[u8]) -> Option<Vec<u8>> {
342        if group(prev_last) != G_TEXT || group(first) != G_TEXT {
343            return None;
344        }
345        let (sp, sf) = (
346            std::str::from_utf8(prev_last).ok()?,
347            std::str::from_utf8(first).ok()?,
348        );
349        let (bp, _) = crate::terms::literal_parts(sp)?;
350        let (bf, _) = crate::terms::literal_parts(sf)?;
351        let (lp, lf) = (lexical(bp), lexical(bf));
352        if lp.as_ref() >= lf.as_ref() {
353            return None;
354        }
355        let shared = lp
356            .as_bytes()
357            .iter()
358            .zip(lf.as_bytes())
359            .take_while(|(a, b)| a == b)
360            .count();
361        // One byte past the shared prefix, then to a whole character.
362        let mut end = shared + 1;
363        while end < lf.len() && !lf.is_char_boundary(end) {
364            end += 1;
365        }
366        if end >= lf.len() {
367            return None; // the whole of `first`'s lexical form: no shorter key
368        }
369        let key = crate::terms::make_literal(&lf[..end], None, None);
370        // Belt and braces: the key must route between the two.
371        (self.cmp(prev_last, key.as_bytes()) == Ordering::Less
372            && self.cmp(key.as_bytes(), first) != Ordering::Greater)
373            .then(|| key.into_bytes())
374    }
375}
376
377/// How many terms of a section are in each group.
378#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
379pub struct GroupCounts(pub [u32; GROUPS]);
380
381impl GroupCounts {
382    /// Count one term.
383    pub fn add(&mut self, t: &[u8]) {
384        self.0[group(t) as usize] += 1;
385    }
386
387    /// Ids `1..=lit_start()` are blank nodes and IRIs.
388    pub fn lit_start(&self) -> u32 {
389        self.0[G_BLANK as usize].saturating_add(self.0[G_IRI as usize])
390    }
391
392    /// Ids `lit_start()+1..=text_end()` are text literals.
393    pub fn text_end(&self) -> u32 {
394        self.lit_start().saturating_add(self.0[G_TEXT as usize])
395    }
396
397    /// Ids `text_end()+1..=lit_end()` are typed literals; everything after
398    /// is a quoted triple.
399    pub fn lit_end(&self) -> u32 {
400        self.text_end().saturating_add(self.0[G_TYPED as usize])
401    }
402
403    /// Terms in all groups.
404    pub fn total(&self) -> u64 {
405        self.0.iter().map(|&n| n as u64).sum()
406    }
407
408    /// Is section-local id `id` in an order-exact group, so that it compares
409    /// with another exact id of the same section as the terms do?
410    pub fn is_exact(&self, id: u32) -> bool {
411        !(id > self.text_end() && id <= self.lit_end())
412    }
413}
414
415#[cfg(test)]
416mod tests {
417    use super::*;
418
419    fn sorted(order: TermOrder, mut v: Vec<&str>) -> Vec<&str> {
420        v.sort_by(|a, b| order.cmp_str(a, b));
421        v
422    }
423
424    #[test]
425    fn iri_prefix_sorts_before_its_extensions() {
426        let v = vec![
427            "<http://x/Ng8130_provenance>",
428            "<http://x/Ng8>",
429            "<http://x/Ng8->",
430        ];
431        assert_eq!(
432            sorted(TermOrder::Sparql, v.clone()),
433            vec![
434                "<http://x/Ng8>",
435                "<http://x/Ng8->",
436                "<http://x/Ng8130_provenance>"
437            ]
438        );
439        // the bytewise order is the one that put the extension first
440        assert_eq!(
441            TermOrder::Bytewise.cmp_str("<http://x/Ng8130_provenance>", "<http://x/Ng8>"),
442            Ordering::Less
443        );
444    }
445
446    #[test]
447    fn kinds_group_in_sparql_order() {
448        let v = vec![
449            "\"z\"",
450            "<http://a>",
451            "_:b",
452            "\"5\"^^<http://www.w3.org/2001/XMLSchema#integer>",
453            "<<_:a <http://p> _:b>>",
454            "\"a\"@en",
455        ];
456        assert_eq!(
457            sorted(TermOrder::Sparql, v),
458            vec![
459                "_:b",
460                "<http://a>",
461                "\"a\"@en",
462                "\"z\"",
463                "\"5\"^^<http://www.w3.org/2001/XMLSchema#integer>",
464                "<<_:a <http://p> _:b>>",
465            ]
466        );
467    }
468
469    #[test]
470    fn text_literals_order_by_lexical_form_not_by_closing_quote() {
471        let v = vec!["\"a b\"", "\"a\"", "\"a\"@en", "\"a!\"", "\"B\""];
472        // lexical: "B" < "a" < "a b" < "a!"; at "a": rdf:langString < xsd:string
473        assert_eq!(
474            sorted(TermOrder::Sparql, v),
475            vec!["\"B\"", "\"a\"@en", "\"a\"", "\"a b\"", "\"a!\""]
476        );
477    }
478
479    #[test]
480    fn escapes_compare_unescaped() {
481        // `a"b` unescaped sorts between `a!` and `a#`; escaped (`a\"b`) the
482        // backslash would put it after `a#`.
483        let v = vec!["\"a#\"", "\"a\\\"b\"", "\"a!\""];
484        assert_eq!(
485            sorted(TermOrder::Sparql, v),
486            vec!["\"a!\"", "\"a\\\"b\"", "\"a#\""]
487        );
488    }
489
490    #[test]
491    fn non_ascii_is_codepoint_order() {
492        let v = vec!["<http://x/\u{e9}>", "<http://x/z>", "<http://x/\u{1f600}>"];
493        assert_eq!(
494            sorted(TermOrder::Sparql, v),
495            vec!["<http://x/z>", "<http://x/\u{e9}>", "<http://x/\u{1f600}>"]
496        );
497    }
498
499    #[test]
500    fn xsd_string_is_text_and_other_datatypes_are_typed() {
501        assert_eq!(
502            group(b"\"x\"^^<http://www.w3.org/2001/XMLSchema#string>"),
503            G_TEXT
504        );
505        assert_eq!(group(b"\"x\"^^<http://example/dt>"), G_TYPED);
506        assert_eq!(group(b"\"x\""), G_TEXT);
507        assert_eq!(group(b"\"x\"@en-GB"), G_TEXT);
508        assert_eq!(group(b"\"x\"@en--ltr"), G_TEXT);
509        assert_eq!(group(b"_:b"), G_BLANK);
510        assert_eq!(group(b"<<a b c>>"), G_TRIPLE);
511        assert_eq!(group(b"<x>"), G_IRI);
512        assert_eq!(group(b""), G_TYPED);
513    }
514
515    /// A probe is the order: `probe(b).cmp_stored(a)` is `cmp(a, b)` for every
516    /// pair, in both orders, over well-formed and malformed tokens alike (a
517    /// file is searched with one and was sorted with the other).
518    #[test]
519    fn a_probe_compares_as_the_order_does() {
520        let mut tokens: Vec<Vec<u8>> = [
521            "",
522            "_:b0",
523            "_:b1",
524            "_",
525            "<http://x/a>",
526            "<http://x/a/b>",
527            "<http://x/Ng8>",
528            "<http://x/Ng8130_provenance>",
529            "<<<s> <p> <o>>>",
530            "<<",
531            "<",
532            "<unclosed",
533            "\"\"",
534            "\"a\"",
535            "\"a\"@en",
536            "\"a\"@EN",
537            "\"a\"@en-GB",
538            "\"a\"@en--ltr",
539            "\"a\"^^<http://www.w3.org/2001/XMLSchema#string>",
540            "\"a\"^^<http://www.w3.org/2001/XMLSchema#integer>",
541            "\"ab\"",
542            "\"a\\\"b\"",
543            "\"a\\nb\"",
544            "\"a\\\\\"",
545            "\"A\"",
546            "\"\u{e9}t\u{e9}\"",
547            "\"\u{e9}t\u{e9}\"@fr",
548            "\"10\"^^<http://www.w3.org/2001/XMLSchema#integer>",
549            "\"9\"^^<http://www.w3.org/2001/XMLSchema#integer>",
550            "\"2018-04-05\"^^<http://www.w3.org/2001/XMLSchema#date>",
551            "\"unclosed",
552            "\"a\"junk",
553            "\"a\"^^",
554            "\"",
555            "plain",
556            "42",
557        ]
558        .iter()
559        .map(|t| t.as_bytes().to_vec())
560        .collect();
561        // Not UTF-8, in each kind of token.
562        tokens.push(b"\"\xff\"".to_vec());
563        tokens.push(b"\"a\"@\xff".to_vec());
564        tokens.push(b"<http://x/\xff>".to_vec());
565        tokens.push(vec![0xff, 0xfe]);
566        for order in [TermOrder::Bytewise, TermOrder::Sparql] {
567            for b in &tokens {
568                let probe = order.probe(b);
569                for a in &tokens {
570                    assert_eq!(
571                        probe.cmp_stored(a),
572                        order.cmp(a, b),
573                        "{order:?}: {:?} against {:?}",
574                        String::from_utf8_lossy(a),
575                        String::from_utf8_lossy(b)
576                    );
577                }
578            }
579        }
580    }
581
582    #[test]
583    fn it_is_a_total_order() {
584        let terms = [
585            "_:a",
586            "_:b",
587            "<a>",
588            "<a",
589            "<ab>",
590            "\"x\"",
591            "\"x\"^^<http://www.w3.org/2001/XMLSchema#string>",
592            "\"X\"@EN",
593            "\"X\"@en",
594            "\"1\"^^<http://www.w3.org/2001/XMLSchema#integer>",
595            "<<a b c>>",
596            "junk",
597        ];
598        for o in [TermOrder::Bytewise, TermOrder::Sparql] {
599            for a in terms {
600                for b in terms {
601                    let ab = o.cmp_str(a, b);
602                    assert_eq!(ab, o.cmp_str(b, a).reverse(), "{a} {b}");
603                    assert_eq!(ab == Ordering::Equal, a == b, "{a} {b}");
604                    for c in terms {
605                        if ab == Ordering::Less && o.cmp_str(b, c) == Ordering::Less {
606                            assert_eq!(o.cmp_str(a, c), Ordering::Less, "{a} {b} {c}");
607                        }
608                    }
609                }
610            }
611        }
612    }
613
614    #[test]
615    fn a_separator_routes_between_its_neighbours() {
616        let o = TermOrder::Sparql;
617        let pairs = [
618            ("<http://x/Ng8>", "<http://x/Ng8130_provenance>"),
619            ("<http://x/a>", "<http://x/b>"),
620            ("<http://x/z>", "\"lit\""),
621            ("\"a\"", "\"b\""),
622            ("\"aaa\"@en", "\"abcdef\"@en"),
623            ("\"caf\u{e9}1\"", "\"caf\u{e9}2 and much more text\""),
624        ];
625        for (p, f) in pairs {
626            let k = o.separator(p.as_bytes(), f.as_bytes());
627            assert_eq!(o.cmp(p.as_bytes(), &k), Ordering::Less, "{p} < key {k:?}");
628            assert_ne!(
629                o.cmp(&k, f.as_bytes()),
630                Ordering::Greater,
631                "key {k:?} <= {f}"
632            );
633        }
634        // and for text literals
635        let k = o.separator(b"\"aaa\"", b"\"abcdef ghij klmn\"");
636        assert_eq!(k, b"\"ab\"");
637        // shorter than the whole term for IRIs
638        let k = o.separator(b"<http://example.org/aaa/1>", b"<http://example.org/bbb/2>");
639        assert!(k.len() < b"<http://example.org/bbb/2>".len());
640    }
641
642    #[test]
643    fn counts_name_the_exact_ranges() {
644        let mut c = GroupCounts::default();
645        for t in [
646            "_:a",
647            "<a>",
648            "<b>",
649            "\"x\"",
650            "\"1\"^^<http://e/d>",
651            "\"2\"^^<http://e/d>",
652        ] {
653            c.add(t.as_bytes());
654        }
655        assert_eq!((c.lit_start(), c.text_end(), c.lit_end()), (3, 4, 6));
656        assert!(c.is_exact(1) && c.is_exact(4));
657        assert!(!c.is_exact(5) && !c.is_exact(6));
658        assert!(c.is_exact(7));
659    }
660}