1use std::cmp::Ordering;
32
33#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
37pub enum TermOrder {
38 #[default]
40 Bytewise,
41 Sparql,
43}
44
45thread_local! {
46 static BUILDER_ORDER: std::cell::Cell<Option<TermOrder>> = const { std::cell::Cell::new(None) };
47}
48
49#[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
65pub(crate) fn builder_order_override() -> Option<TermOrder> {
67 BUILDER_ORDER.with(|c| c.get())
68}
69
70pub const G_BLANK: u8 = 0;
72pub const G_IRI: u8 = 1;
74pub const G_TEXT: u8 = 2;
76pub const G_TYPED: u8 = 3;
78pub const G_TRIPLE: u8 = 4;
80pub const GROUPS: usize = 5;
82
83const XSD_STRING_SUFFIX: &str = "^^<http://www.w3.org/2001/XMLSchema#string>";
84
85pub 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
112fn 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
130fn 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
144fn text_cmp(a: &[u8], b: &[u8]) -> Ordering {
147 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
170pub struct Probe<'t> {
182 order: TermOrder,
183 token: &'t [u8],
184 group: u8,
185 text: Option<(std::borrow::Cow<'t, str>, u8, &'t str)>,
187}
188
189impl Probe<'_> {
190 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 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 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 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 pub fn cmp_str(self, a: &str, b: &str) -> Ordering {
307 self.cmp(a.as_bytes(), b.as_bytes())
308 }
309
310 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 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 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 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 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; }
425 let key = crate::terms::make_literal(&lf[..end], None, None);
426 (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#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
435pub struct GroupCounts(pub [u32; GROUPS]);
436
437impl GroupCounts {
438 pub fn add(&mut self, t: &[u8]) {
440 self.0[group(t) as usize] += 1;
441 }
442
443 pub fn lit_start(&self) -> u32 {
445 self.0[G_BLANK as usize].saturating_add(self.0[G_IRI as usize])
446 }
447
448 pub fn text_end(&self) -> u32 {
450 self.lit_start().saturating_add(self.0[G_TEXT as usize])
451 }
452
453 pub fn lit_end(&self) -> u32 {
456 self.text_end().saturating_add(self.0[G_TYPED as usize])
457 }
458
459 pub fn total(&self) -> u64 {
461 self.0.iter().map(|&n| n as u64).sum()
462 }
463
464 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 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 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 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 #[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 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 let k = o.separator(b"\"aaa\"", b"\"abcdef ghij klmn\"");
692 assert_eq!(k, b"\"ab\"");
693 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 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}