use std::cmp::Ordering;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
pub enum TermOrder {
#[default]
Bytewise,
Sparql,
}
thread_local! {
static BUILDER_ORDER: std::cell::Cell<Option<TermOrder>> = const { std::cell::Cell::new(None) };
}
#[doc(hidden)]
pub fn with_builder_order<R>(order: TermOrder, f: impl FnOnce() -> R) -> R {
struct Restore(Option<TermOrder>);
impl Drop for Restore {
fn drop(&mut self) {
BUILDER_ORDER.with(|c| c.set(self.0));
}
}
let _restore = Restore(BUILDER_ORDER.with(|c| c.replace(Some(order))));
f()
}
pub(crate) fn builder_order_override() -> Option<TermOrder> {
BUILDER_ORDER.with(|c| c.get())
}
pub const G_BLANK: u8 = 0;
pub const G_IRI: u8 = 1;
pub const G_TEXT: u8 = 2;
pub const G_TYPED: u8 = 3;
pub const G_TRIPLE: u8 = 4;
pub const GROUPS: usize = 5;
const XSD_STRING_SUFFIX: &str = "^^<http://www.w3.org/2001/XMLSchema#string>";
pub fn group(t: &[u8]) -> u8 {
match t.first() {
Some(b'<') => {
if t.starts_with(b"<<") && t.ends_with(b">>") {
G_TRIPLE
} else {
G_IRI
}
}
Some(b'_') if t.get(1) == Some(&b':') => G_BLANK,
Some(b'"') => match std::str::from_utf8(t) {
Ok(s) => literal_group(s),
Err(_) => G_TYPED,
},
_ => G_TYPED,
}
}
fn literal_group(s: &str) -> u8 {
match crate::terms::literal_parts(s) {
Some((_, "")) => G_TEXT,
Some((_, suffix)) if suffix.starts_with('@') || suffix == XSD_STRING_SUFFIX => G_TEXT,
_ => G_TYPED,
}
}
fn iri_text(t: &[u8]) -> &[u8] {
if t.len() >= 2 && t[0] == b'<' && t[t.len() - 1] == b'>' {
&t[1..t.len() - 1]
} else {
t
}
}
fn lexical(body: &str) -> std::borrow::Cow<'_, str> {
if body.contains('\\') {
std::borrow::Cow::Owned(crate::terms::unescape_literal(body))
} else {
std::borrow::Cow::Borrowed(body)
}
}
fn datatype_rank(suffix: &str) -> u8 {
if let Some(tag) = suffix.strip_prefix('@') {
if tag.contains("--") {
0
} else {
1
}
} else {
2
}
}
fn text_cmp(a: &[u8], b: &[u8]) -> Ordering {
let (Ok(sa), Ok(sb)) = (std::str::from_utf8(a), std::str::from_utf8(b)) else {
return a.cmp(b);
};
let (Some((ba, xa)), Some((bb, xb))) = (
crate::terms::literal_parts(sa),
crate::terms::literal_parts(sb),
) else {
return a.cmp(b);
};
lexical(ba)
.as_ref()
.cmp(lexical(bb).as_ref())
.then_with(|| datatype_rank(xa).cmp(&datatype_rank(xb)))
.then_with(|| {
let ta = xa.strip_prefix('@').unwrap_or("").bytes();
let tb = xb.strip_prefix('@').unwrap_or("").bytes();
ta.map(|c| c.to_ascii_lowercase())
.cmp(tb.map(|c| c.to_ascii_lowercase()))
})
.then_with(|| a.cmp(b))
}
pub struct Probe<'t> {
order: TermOrder,
token: &'t [u8],
group: u8,
text: Option<(std::borrow::Cow<'t, str>, u8, &'t str)>,
}
impl Probe<'_> {
pub fn cmp_stored(&self, a: &[u8]) -> Ordering {
let b = self.token;
if self.order == TermOrder::Bytewise {
return a.cmp(b);
}
if a.is_empty() || b.is_empty() {
return a.len().cmp(&b.len());
}
let mut parts: Option<(&str, &str)> = None;
let ga = match a[0] {
b'<' => {
if a.starts_with(b"<<") && a.ends_with(b">>") {
G_TRIPLE
} else {
G_IRI
}
}
b'_' if a.get(1) == Some(&b':') => G_BLANK,
b'"' => {
if self.group < G_TEXT {
return Ordering::Greater;
}
if self.group > G_TYPED {
return Ordering::Less;
}
match std::str::from_utf8(a).ok().map(crate::terms::literal_parts) {
Some(Some((body, suffix)))
if suffix.is_empty()
|| suffix.starts_with('@')
|| suffix == XSD_STRING_SUFFIX =>
{
parts = Some((body, suffix));
G_TEXT
}
_ => G_TYPED,
}
}
_ => G_TYPED,
};
if ga != self.group {
return ga.cmp(&self.group);
}
match (ga, parts, &self.text) {
(G_IRI, _, _) => iri_text(a).cmp(iri_text(b)).then_with(|| a.cmp(b)),
(G_TEXT, Some((ba, xa)), Some((lex, rank, tag))) => lexical(ba)
.as_ref()
.cmp(lex.as_ref())
.then_with(|| datatype_rank(xa).cmp(rank))
.then_with(|| {
let ta = xa.strip_prefix('@').unwrap_or("").bytes();
ta.map(|c| c.to_ascii_lowercase())
.cmp(tag.bytes().map(|c| c.to_ascii_lowercase()))
})
.then_with(|| a.cmp(b)),
_ => a.cmp(b),
}
}
}
impl TermOrder {
pub fn probe(self, term: &[u8]) -> Probe<'_> {
let group = if self == TermOrder::Sparql && !term.is_empty() {
group(term)
} else {
G_TYPED
};
let text = (self == TermOrder::Sparql && group == G_TEXT)
.then(|| {
let s = std::str::from_utf8(term).ok()?;
let (body, suffix) = crate::terms::literal_parts(s)?;
Some((
lexical(body),
datatype_rank(suffix),
suffix.strip_prefix('@').unwrap_or(""),
))
})
.flatten();
Probe {
order: self,
token: term,
group,
text,
}
}
pub fn cmp(self, a: &[u8], b: &[u8]) -> Ordering {
match self {
TermOrder::Bytewise => a.cmp(b),
TermOrder::Sparql => {
if a.is_empty() || b.is_empty() {
return a.len().cmp(&b.len());
}
let (ga, gb) = (group(a), group(b));
if ga != gb {
return ga.cmp(&gb);
}
match ga {
G_IRI => iri_text(a).cmp(iri_text(b)).then_with(|| a.cmp(b)),
G_TEXT => text_cmp(a, b),
_ => a.cmp(b),
}
}
}
}
pub fn cmp_str(self, a: &str, b: &str) -> Ordering {
self.cmp(a.as_bytes(), b.as_bytes())
}
pub fn separator(self, prev_last: &[u8], first: &[u8]) -> Vec<u8> {
if self == TermOrder::Sparql {
let iri = |t: &[u8]| group(t) == G_IRI && t.len() >= 2 && t[t.len() - 1] == b'>';
if iri(prev_last) && iri(first) && self.cmp(prev_last, first) == Ordering::Less {
let s = crate::dict::shortest_separator(iri_text(prev_last), iri_text(first));
let mut k = Vec::with_capacity(s.len() + 2);
k.push(b'<');
k.extend_from_slice(&s);
k.push(b'>');
return k;
}
if let Some(k) = self.text_separator(prev_last, first) {
return k;
}
return first.to_vec();
}
crate::dict::shortest_separator(prev_last, first)
}
}
impl TermOrder {
fn text_separator(self, prev_last: &[u8], first: &[u8]) -> Option<Vec<u8>> {
if group(prev_last) != G_TEXT || group(first) != G_TEXT {
return None;
}
let (sp, sf) = (
std::str::from_utf8(prev_last).ok()?,
std::str::from_utf8(first).ok()?,
);
let (bp, _) = crate::terms::literal_parts(sp)?;
let (bf, _) = crate::terms::literal_parts(sf)?;
let (lp, lf) = (lexical(bp), lexical(bf));
if lp.as_ref() >= lf.as_ref() {
return None;
}
let shared = lp
.as_bytes()
.iter()
.zip(lf.as_bytes())
.take_while(|(a, b)| a == b)
.count();
let mut end = shared + 1;
while end < lf.len() && !lf.is_char_boundary(end) {
end += 1;
}
if end >= lf.len() {
return None; }
let key = crate::terms::make_literal(&lf[..end], None, None);
(self.cmp(prev_last, key.as_bytes()) == Ordering::Less
&& self.cmp(key.as_bytes(), first) != Ordering::Greater)
.then(|| key.into_bytes())
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct GroupCounts(pub [u32; GROUPS]);
impl GroupCounts {
pub fn add(&mut self, t: &[u8]) {
self.0[group(t) as usize] += 1;
}
pub fn lit_start(&self) -> u32 {
self.0[G_BLANK as usize].saturating_add(self.0[G_IRI as usize])
}
pub fn text_end(&self) -> u32 {
self.lit_start().saturating_add(self.0[G_TEXT as usize])
}
pub fn lit_end(&self) -> u32 {
self.text_end().saturating_add(self.0[G_TYPED as usize])
}
pub fn total(&self) -> u64 {
self.0.iter().map(|&n| n as u64).sum()
}
pub fn is_exact(&self, id: u32) -> bool {
!(id > self.text_end() && id <= self.lit_end())
}
}
#[cfg(test)]
mod tests {
use super::*;
fn sorted(order: TermOrder, mut v: Vec<&str>) -> Vec<&str> {
v.sort_by(|a, b| order.cmp_str(a, b));
v
}
#[test]
fn iri_prefix_sorts_before_its_extensions() {
let v = vec![
"<http://x/Ng8130_provenance>",
"<http://x/Ng8>",
"<http://x/Ng8->",
];
assert_eq!(
sorted(TermOrder::Sparql, v.clone()),
vec![
"<http://x/Ng8>",
"<http://x/Ng8->",
"<http://x/Ng8130_provenance>"
]
);
assert_eq!(
TermOrder::Bytewise.cmp_str("<http://x/Ng8130_provenance>", "<http://x/Ng8>"),
Ordering::Less
);
}
#[test]
fn kinds_group_in_sparql_order() {
let v = vec![
"\"z\"",
"<http://a>",
"_:b",
"\"5\"^^<http://www.w3.org/2001/XMLSchema#integer>",
"<<_:a <http://p> _:b>>",
"\"a\"@en",
];
assert_eq!(
sorted(TermOrder::Sparql, v),
vec![
"_:b",
"<http://a>",
"\"a\"@en",
"\"z\"",
"\"5\"^^<http://www.w3.org/2001/XMLSchema#integer>",
"<<_:a <http://p> _:b>>",
]
);
}
#[test]
fn text_literals_order_by_lexical_form_not_by_closing_quote() {
let v = vec!["\"a b\"", "\"a\"", "\"a\"@en", "\"a!\"", "\"B\""];
assert_eq!(
sorted(TermOrder::Sparql, v),
vec!["\"B\"", "\"a\"@en", "\"a\"", "\"a b\"", "\"a!\""]
);
}
#[test]
fn escapes_compare_unescaped() {
let v = vec!["\"a#\"", "\"a\\\"b\"", "\"a!\""];
assert_eq!(
sorted(TermOrder::Sparql, v),
vec!["\"a!\"", "\"a\\\"b\"", "\"a#\""]
);
}
#[test]
fn non_ascii_is_codepoint_order() {
let v = vec!["<http://x/\u{e9}>", "<http://x/z>", "<http://x/\u{1f600}>"];
assert_eq!(
sorted(TermOrder::Sparql, v),
vec!["<http://x/z>", "<http://x/\u{e9}>", "<http://x/\u{1f600}>"]
);
}
#[test]
fn xsd_string_is_text_and_other_datatypes_are_typed() {
assert_eq!(
group(b"\"x\"^^<http://www.w3.org/2001/XMLSchema#string>"),
G_TEXT
);
assert_eq!(group(b"\"x\"^^<http://example/dt>"), G_TYPED);
assert_eq!(group(b"\"x\""), G_TEXT);
assert_eq!(group(b"\"x\"@en-GB"), G_TEXT);
assert_eq!(group(b"\"x\"@en--ltr"), G_TEXT);
assert_eq!(group(b"_:b"), G_BLANK);
assert_eq!(group(b"<<a b c>>"), G_TRIPLE);
assert_eq!(group(b"<x>"), G_IRI);
assert_eq!(group(b""), G_TYPED);
}
#[test]
fn a_probe_compares_as_the_order_does() {
let mut tokens: Vec<Vec<u8>> = [
"",
"_:b0",
"_:b1",
"_",
"<http://x/a>",
"<http://x/a/b>",
"<http://x/Ng8>",
"<http://x/Ng8130_provenance>",
"<<<s> <p> <o>>>",
"<<",
"<",
"<unclosed",
"\"\"",
"\"a\"",
"\"a\"@en",
"\"a\"@EN",
"\"a\"@en-GB",
"\"a\"@en--ltr",
"\"a\"^^<http://www.w3.org/2001/XMLSchema#string>",
"\"a\"^^<http://www.w3.org/2001/XMLSchema#integer>",
"\"ab\"",
"\"a\\\"b\"",
"\"a\\nb\"",
"\"a\\\\\"",
"\"A\"",
"\"\u{e9}t\u{e9}\"",
"\"\u{e9}t\u{e9}\"@fr",
"\"10\"^^<http://www.w3.org/2001/XMLSchema#integer>",
"\"9\"^^<http://www.w3.org/2001/XMLSchema#integer>",
"\"2018-04-05\"^^<http://www.w3.org/2001/XMLSchema#date>",
"\"unclosed",
"\"a\"junk",
"\"a\"^^",
"\"",
"plain",
"42",
]
.iter()
.map(|t| t.as_bytes().to_vec())
.collect();
tokens.push(b"\"\xff\"".to_vec());
tokens.push(b"\"a\"@\xff".to_vec());
tokens.push(b"<http://x/\xff>".to_vec());
tokens.push(vec![0xff, 0xfe]);
for order in [TermOrder::Bytewise, TermOrder::Sparql] {
for b in &tokens {
let probe = order.probe(b);
for a in &tokens {
assert_eq!(
probe.cmp_stored(a),
order.cmp(a, b),
"{order:?}: {:?} against {:?}",
String::from_utf8_lossy(a),
String::from_utf8_lossy(b)
);
}
}
}
}
#[test]
fn it_is_a_total_order() {
let terms = [
"_:a",
"_:b",
"<a>",
"<a",
"<ab>",
"\"x\"",
"\"x\"^^<http://www.w3.org/2001/XMLSchema#string>",
"\"X\"@EN",
"\"X\"@en",
"\"1\"^^<http://www.w3.org/2001/XMLSchema#integer>",
"<<a b c>>",
"junk",
];
for o in [TermOrder::Bytewise, TermOrder::Sparql] {
for a in terms {
for b in terms {
let ab = o.cmp_str(a, b);
assert_eq!(ab, o.cmp_str(b, a).reverse(), "{a} {b}");
assert_eq!(ab == Ordering::Equal, a == b, "{a} {b}");
for c in terms {
if ab == Ordering::Less && o.cmp_str(b, c) == Ordering::Less {
assert_eq!(o.cmp_str(a, c), Ordering::Less, "{a} {b} {c}");
}
}
}
}
}
}
#[test]
fn a_separator_routes_between_its_neighbours() {
let o = TermOrder::Sparql;
let pairs = [
("<http://x/Ng8>", "<http://x/Ng8130_provenance>"),
("<http://x/a>", "<http://x/b>"),
("<http://x/z>", "\"lit\""),
("\"a\"", "\"b\""),
("\"aaa\"@en", "\"abcdef\"@en"),
("\"caf\u{e9}1\"", "\"caf\u{e9}2 and much more text\""),
];
for (p, f) in pairs {
let k = o.separator(p.as_bytes(), f.as_bytes());
assert_eq!(o.cmp(p.as_bytes(), &k), Ordering::Less, "{p} < key {k:?}");
assert_ne!(
o.cmp(&k, f.as_bytes()),
Ordering::Greater,
"key {k:?} <= {f}"
);
}
let k = o.separator(b"\"aaa\"", b"\"abcdef ghij klmn\"");
assert_eq!(k, b"\"ab\"");
let k = o.separator(b"<http://example.org/aaa/1>", b"<http://example.org/bbb/2>");
assert!(k.len() < b"<http://example.org/bbb/2>".len());
}
#[test]
fn counts_name_the_exact_ranges() {
let mut c = GroupCounts::default();
for t in [
"_:a",
"<a>",
"<b>",
"\"x\"",
"\"1\"^^<http://e/d>",
"\"2\"^^<http://e/d>",
] {
c.add(t.as_bytes());
}
assert_eq!((c.lit_start(), c.text_end(), c.lit_end()), (3, 4, 6));
assert!(c.is_exact(1) && c.is_exact(4));
assert!(!c.is_exact(5) && !c.is_exact(6));
assert!(c.is_exact(7));
}
}