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 return first.to_vec();
331 }
332 crate::dict::shortest_separator(prev_last, first)
333 }
334}
335
336impl TermOrder {
337 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 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; }
369 let key = crate::terms::make_literal(&lf[..end], None, None);
370 (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#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
379pub struct GroupCounts(pub [u32; GROUPS]);
380
381impl GroupCounts {
382 pub fn add(&mut self, t: &[u8]) {
384 self.0[group(t) as usize] += 1;
385 }
386
387 pub fn lit_start(&self) -> u32 {
389 self.0[G_BLANK as usize].saturating_add(self.0[G_IRI as usize])
390 }
391
392 pub fn text_end(&self) -> u32 {
394 self.lit_start().saturating_add(self.0[G_TEXT as usize])
395 }
396
397 pub fn lit_end(&self) -> u32 {
400 self.text_end().saturating_add(self.0[G_TYPED as usize])
401 }
402
403 pub fn total(&self) -> u64 {
405 self.0.iter().map(|&n| n as u64).sum()
406 }
407
408 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 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 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 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 #[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 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 let k = o.separator(b"\"aaa\"", b"\"abcdef ghij klmn\"");
636 assert_eq!(k, b"\"ab\"");
637 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}