use std::sync::{Arc, OnceLock};
use crate::dictionary::Dictionary;
use crate::index::{GraphIndex, Pattern};
pub const SECTION: usize = 1;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct DeriveOpts {
pub min_permille: u64,
pub min_bytes: u64,
}
impl Default for DeriveOpts {
fn default() -> Self {
DeriveOpts {
min_permille: 50,
min_bytes: 256 << 10,
}
}
}
impl DeriveOpts {
pub fn threshold(&self, file_len: u64) -> u64 {
(file_len / 1000)
.saturating_mul(self.min_permille)
.max(self.min_bytes)
}
}
pub const MAX_FAMILIES: usize = 16;
pub const MAX_INPUTS: usize = 8;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DeriveError(pub String);
impl std::fmt::Display for DeriveError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.0)
}
}
impl std::error::Error for DeriveError {}
fn err<T>(m: impl Into<String>) -> Result<T, DeriveError> {
Err(DeriveError(m.into()))
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Input {
pub predicate: String,
pub prefix: String,
}
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct Family {
pub literals: Vec<String>,
pub inputs: Vec<Input>,
pub runs: Vec<(usize, usize)>,
}
impl Family {
pub fn new(literals: Vec<String>, inputs: Vec<Input>) -> Result<Family, DeriveError> {
let f = Family {
literals,
inputs,
runs: Vec::new(),
};
f.check()?;
Ok(f)
}
pub fn spec(&self) -> String {
let mut s = String::new();
for (k, lit) in self.literals.iter().enumerate() {
let mut t = lit.as_str();
if k == 0 {
t = t.strip_prefix('<').unwrap_or(t);
}
if k + 1 == self.literals.len() {
t = t.strip_suffix('>').unwrap_or(t);
}
s.push_str(t);
if let Some(i) = self.inputs.get(k) {
s.push('{');
s.push_str(&i.predicate);
s.push('|');
s.push_str(&i.prefix);
s.push('}');
}
}
s
}
pub fn check(&self) -> Result<(), DeriveError> {
let n = self.inputs.len();
if n == 0 || n > MAX_INPUTS {
return err(format!("family: a template has 1 to {MAX_INPUTS} holes"));
}
if self.literals.len() != n + 1 {
return err("family: the literals do not fit the holes");
}
if !self.literals[0].starts_with('<') || !self.literals[n].ends_with('>') {
return err("family: a template is an IRI");
}
for (k, l) in self.literals.iter().enumerate() {
if k > 0 && k < n && l.is_empty() {
return err("family: two holes need a literal between them");
}
}
if self.literals[0].len() < 2 {
return err("family: the template has no IRI text before its first hole");
}
Ok(())
}
pub fn build(&self, values: &[&str]) -> String {
let mut s = String::new();
for (k, lit) in self.literals.iter().enumerate() {
s.push_str(lit);
if let Some(v) = values.get(k) {
s.push_str(v);
}
}
s
}
pub fn split<'a>(&self, term: &'a str) -> Option<Vec<&'a str>> {
let n = self.inputs.len();
let mut rest = term.strip_prefix(self.literals[0].as_str())?;
let mut out = Vec::with_capacity(n);
for k in 0..n {
let lit = self.literals[k + 1].as_str();
if k + 1 < n {
let at = rest.find(lit)?;
out.push(&rest[..at]);
rest = &rest[at + lit.len()..];
} else {
out.push(rest.strip_suffix(lit)?);
}
}
Some(out)
}
pub fn object_token(&self, k: usize, value: &str) -> String {
format!("<{}{}>", self.inputs[k].prefix, value)
}
pub fn value_of<'a>(&self, k: usize, object: &'a str) -> Option<&'a str> {
let v = object
.strip_prefix('<')?
.strip_suffix('>')?
.strip_prefix(self.inputs[k].prefix.as_str())?;
(!v.is_empty()).then_some(v)
}
pub fn derive(&self, objects: &[&str]) -> Option<String> {
if objects.len() != self.inputs.len() {
return None;
}
let mut values = Vec::with_capacity(objects.len());
for (k, o) in objects.iter().enumerate() {
values.push(self.value_of(k, o)?);
}
Some(self.build(&values))
}
pub fn covers(&self, ci: usize) -> bool {
let at = self.runs.partition_point(|&(first, _)| first <= ci);
at > 0 && ci < self.runs[at - 1].0 + self.runs[at - 1].1
}
pub fn chunk_count(&self) -> usize {
self.runs.iter().map(|r| r.1).sum()
}
}
pub fn encode_families(fams: &[Family]) -> Vec<u8> {
use crate::varint::write_uvarint;
let lp = |o: &mut Vec<u8>, s: &str| {
write_uvarint(o, s.len() as u64);
o.extend_from_slice(s.as_bytes());
};
let mut o = Vec::new();
write_uvarint(&mut o, fams.len() as u64);
for f in fams {
write_uvarint(&mut o, f.inputs.len() as u64);
lp(&mut o, &f.literals[0]);
for (k, i) in f.inputs.iter().enumerate() {
lp(&mut o, &i.predicate);
lp(&mut o, &i.prefix);
lp(&mut o, &f.literals[k + 1]);
}
write_uvarint(&mut o, f.runs.len() as u64);
for &(first, n) in &f.runs {
write_uvarint(&mut o, first as u64);
write_uvarint(&mut o, n as u64);
}
}
o
}
pub fn decode_families(p: &[u8], n_chunks: usize) -> Result<Vec<Family>, DeriveError> {
use crate::varint::read_uvarint;
let uv = |pos: &mut usize| -> Result<u64, DeriveError> {
let (v, n) = read_uvarint(p.get(*pos..).unwrap_or(&[]))
.ok_or_else(|| DeriveError("derived-IRI root: truncated varint".into()))?;
*pos += n;
Ok(v)
};
let text = |pos: &mut usize, len: u64| -> Result<String, DeriveError> {
let end = usize::try_from(len)
.ok()
.and_then(|l| pos.checked_add(l))
.filter(|&e| e <= p.len())
.ok_or_else(|| DeriveError("derived-IRI root: a string overruns".into()))?;
let s = std::str::from_utf8(&p[*pos..end])
.map_err(|_| DeriveError("derived-IRI root: a string is not UTF-8".into()))?
.to_string();
*pos = end;
Ok(s)
};
let mut pos = 0usize;
let nf = uv(&mut pos)?;
if nf > MAX_FAMILIES as u64 {
return err("derived-IRI root: too many families");
}
let mut out = Vec::new();
for _ in 0..nf {
let ni = uv(&mut pos)?;
if ni == 0 || ni > MAX_INPUTS as u64 {
return err("derived-IRI root: bad hole count");
}
let mut f = Family::default();
let l = uv(&mut pos)?;
f.literals.push(text(&mut pos, l)?);
for _ in 0..ni {
let l = uv(&mut pos)?;
let predicate = text(&mut pos, l)?;
let l = uv(&mut pos)?;
let prefix = text(&mut pos, l)?;
let l = uv(&mut pos)?;
f.inputs.push(Input { predicate, prefix });
f.literals.push(text(&mut pos, l)?);
}
f.check()?;
let nr = uv(&mut pos)?;
if nr > p.len() as u64 {
return err("derived-IRI root: bad run count");
}
let mut prev_end = 0usize;
for _ in 0..nr {
let first = usize::try_from(uv(&mut pos)?).unwrap_or(usize::MAX);
let n = usize::try_from(uv(&mut pos)?).unwrap_or(usize::MAX);
let end = first.checked_add(n);
if n == 0 || first < prev_end || end.is_none_or(|e| e > n_chunks) {
return err("derived-IRI root: a run is out of order or past the chunks");
}
prev_end = first + n;
f.runs.push((first, n));
}
out.push(f);
}
if pos != p.len() {
return err("derived-IRI root: trailing bytes");
}
let all = elided_runs(&out);
if all.windows(2).any(|w| w[0].0 + w[0].1 > w[1].0) {
return err("derived-IRI root: two families claim a chunk");
}
Ok(out)
}
pub fn elided_runs(fams: &[Family]) -> Vec<(usize, usize)> {
let mut all: Vec<(usize, usize)> = fams.iter().flat_map(|f| f.runs.iter().copied()).collect();
all.sort_unstable();
all
}
const MAX_CANDIDATES: usize = 1 << 20;
type Signature = (usize, Option<u32>, Option<u32>, u64);
struct Memo(std::collections::HashMap<u32, Option<std::sync::Arc<str>>>);
impl Memo {
fn new() -> Self {
Memo(std::collections::HashMap::new())
}
fn object(&mut self, dict: &Dictionary, o: u32) -> Option<std::sync::Arc<str>> {
if self.0.len() > 1 << 16 {
self.0.clear();
}
self.0
.entry(o)
.or_insert_with(|| dict.object_term(o).map(Into::into))
.clone()
}
}
pub struct DerivedTerms {
families: Vec<Family>,
index: OnceLock<Arc<GraphIndex>>,
preds: OnceLock<Vec<Vec<Option<u32>>>>,
last: std::sync::Mutex<Option<(u32, String)>>,
prefetched: std::sync::Mutex<Option<Signature>>,
}
impl DerivedTerms {
pub fn new(families: Vec<Family>) -> Self {
DerivedTerms {
families,
index: OnceLock::new(),
preds: OnceLock::new(),
last: std::sync::Mutex::new(None),
prefetched: std::sync::Mutex::new(None),
}
}
pub fn families(&self) -> &[Family] {
&self.families
}
pub fn wire(&self, index: Arc<GraphIndex>) {
let _ = self.index.set(index);
}
fn preds(&self, dict: &Dictionary) -> &[Vec<Option<u32>>] {
self.preds.get_or_init(|| {
self.families
.iter()
.map(|f| {
f.inputs
.iter()
.map(|i| dict.predicate_id(&format!("<{}>", i.predicate)))
.collect()
})
.collect()
})
}
fn family_of_chunk(&self, ci: usize) -> Option<usize> {
self.families.iter().position(|f| f.covers(ci))
}
fn inputs_of(&self, dict: &Dictionary, fi: usize, s: u32) -> Option<Vec<u32>> {
let index = self.index.get()?;
let mut out = Vec::with_capacity(self.families[fi].inputs.len());
let rows: Vec<(u32, u32, u32)> = index.scan_iter((Some(s), None, None)).collect();
for p in self.preds(dict)[fi].iter() {
let p = (*p)?;
let mut it = rows.iter().filter(|r| r.1 == p);
match (it.next(), it.next()) {
(Some(&(_, _, o)), None) => out.push(o),
_ => return None,
}
}
Some(out)
}
pub fn term(&self, dict: &Dictionary, local: u32) -> Option<String> {
if let Ok(g) = self.last.lock() {
if let Some((l, t)) = g.as_ref() {
if *l == local {
return Some(t.clone());
}
}
}
let t = self.term_uncached(dict, local, &mut Memo::new())?;
if let Ok(mut g) = self.last.lock() {
*g = Some((local, t.clone()));
}
Some(t)
}
fn term_uncached(&self, dict: &Dictionary, local: u32, memo: &mut Memo) -> Option<String> {
let ci = dict.subject_only_chunk(local)?;
let fi = self.family_of_chunk(ci)?;
let s = dict.shared_count().checked_add(local)?;
let objects = self.inputs_of(dict, fi, s)?;
let mut texts: Vec<std::sync::Arc<str>> = Vec::with_capacity(objects.len());
for &o in &objects {
texts.push(memo.object(dict, o)?);
}
let refs: Vec<&str> = texts.iter().map(|t| &**t).collect();
self.families[fi].derive(&refs)
}
pub fn terms(&self, dict: &Dictionary, jobs: &[(u32, usize)], out: &mut [Option<String>]) {
let mut jobs = jobs.to_vec();
jobs.sort_unstable();
let mut ids: Vec<u32> = jobs.iter().map(|j| j.0).collect();
ids.dedup();
self.prefetch(dict, &ids);
let mut memo = Memo::new();
let mut last: Option<(u32, Option<String>)> = None;
for &(local, slot) in &jobs {
if out[slot].is_some() {
continue;
}
let t = match &last {
Some((l, t)) if *l == local => t.clone(),
_ => {
let t = self.term_uncached(dict, local, &mut memo);
last = Some((local, t.clone()));
t
}
};
out[slot] = t;
}
}
pub fn prefetch(&self, dict: &Dictionary, locals: &[u32]) {
let Some(index) = self.index.get() else {
return;
};
if !index.is_remote() {
return;
}
let mut locals = locals.to_vec();
locals.sort_unstable();
locals.dedup();
let sig = (
locals.len(),
locals.first().copied(),
locals.last().copied(),
locals.iter().fold(0u64, |a, &l| {
a.wrapping_mul(0x9E37_79B9_7F4A_7C15).wrapping_add(l as u64)
}),
);
if let Ok(mut g) = self.prefetched.lock() {
if *g == Some(sig) {
return;
}
*g = Some(sig);
}
let locals = &locals[..];
let mut pats: Vec<Pattern> = Vec::new();
let mut wanted: Vec<u32> = Vec::new();
let mut seen = std::collections::BTreeSet::new();
for &l in locals {
let Some(ci) = dict.subject_only_chunk(l) else {
continue;
};
let Some(fi) = self.family_of_chunk(ci) else {
continue;
};
let Some(s) = dict.shared_count().checked_add(l) else {
continue;
};
if !seen.insert(s) {
continue;
}
pats.push((Some(s), None, None));
wanted.extend(self.preds(dict)[fi].iter().flatten());
}
wanted.sort_unstable();
wanted.dedup();
let mut at = 0;
while at < pats.len() {
at += index.prefetch_probe_tiles(&pats[at..]).max(1);
}
let mut nodes = Vec::new();
for pat in &pats {
for (_, p, o) in index.scan_iter(*pat) {
if wanted.contains(&p) {
nodes.push(dict.object_node(o));
}
}
}
nodes.sort_unstable();
nodes.dedup();
dict.prefetch_terms(&nodes, &[]);
}
pub fn lookup_terms(&self, term: &str) -> Vec<String> {
let mut out = Vec::new();
for f in &self.families {
if let Some(vals) = f.split(term) {
for (k, v) in vals.iter().enumerate() {
out.push(f.object_token(k, v));
}
}
}
out
}
pub fn lookup(&self, dict: &Dictionary, term: &str, first: u32, last: u32) -> Option<u32> {
let index = self.index.get()?;
let ci = dict.subject_only_chunk(first)?;
let fi = self.family_of_chunk(ci)?;
let fam = &self.families[fi];
let vals = fam.split(term)?;
if fam.build(&vals) != term {
return None;
}
let preds = self.preds(dict)[fi].clone();
let mut objs = Vec::with_capacity(vals.len());
for (k, v) in vals.iter().enumerate() {
objs.push(dict.object_id_exact(&fam.object_token(k, v))?);
}
let shared = dict.shared_count();
let (lo, hi) = (shared.checked_add(first)?, shared.checked_add(last)?);
let mut cands: Vec<u32> = index
.match_pattern((None, Some(preds[0]?), Some(objs[0])))
.into_iter()
.map(|t| t.0)
.filter(|s| (lo..=hi).contains(s))
.collect();
cands.truncate(MAX_CANDIDATES);
'cand: for s in cands {
for k in 1..vals.len() {
if index
.match_pattern((Some(s), Some(preds[k]?), Some(objs[k])))
.is_empty()
{
continue 'cand;
}
}
return Some(s - shared);
}
None
}
}
#[cfg(test)]
mod tests {
use super::*;
const CITING: &str = "http://purl.org/spar/cito/hasCitingEntity";
const CITED: &str = "http://purl.org/spar/cito/hasCitedEntity";
const BR: &str = "https://w3id.org/oc/meta/br/";
fn input(p: &str, prefix: &str) -> Input {
Input {
predicate: p.into(),
prefix: prefix.into(),
}
}
fn ci() -> Family {
Family::new(
vec![
"<https://w3id.org/oc/index/ci/".into(),
"-".into(),
">".into(),
],
vec![input(CITING, BR), input(CITED, BR)],
)
.unwrap()
}
#[test]
fn a_family_builds_splits_and_derives() {
let f = ci();
assert_eq!(f.inputs.len(), 2);
assert_eq!(
f.spec(),
format!("https://w3id.org/oc/index/ci/{{{CITING}|{BR}}}-{{{CITED}|{BR}}}")
);
assert_eq!(
f.build(&["0601785", "06902211389"]),
"<https://w3id.org/oc/index/ci/0601785-06902211389>"
);
assert_eq!(
f.split("<https://w3id.org/oc/index/ci/0601785-06902211389>"),
Some(vec!["0601785", "06902211389"])
);
assert_eq!(f.split("<https://w3id.org/oc/index/ci/0601785>"), None);
assert_eq!(f.split("<http://other/0601785-1>"), None);
assert_eq!(
f.value_of(0, "<https://w3id.org/oc/meta/br/0601785>"),
Some("0601785")
);
assert_eq!(f.value_of(0, "<https://w3id.org/oc/meta/br/>"), None);
assert_eq!(f.value_of(0, "<http://x/1>"), None);
assert_eq!(
f.derive(&[
"<https://w3id.org/oc/meta/br/0601785>",
"<https://w3id.org/oc/meta/br/06902211389>"
])
.as_deref(),
Some("<https://w3id.org/oc/index/ci/0601785-06902211389>")
);
}
#[test]
fn families_that_cannot_split_are_refused() {
let lit = |v: &[&str]| v.iter().map(|s| s.to_string()).collect::<Vec<_>>();
assert!(Family::new(
lit(&["<http://x/", "", ">"]),
vec![input("a", "b"), input("c", "d")]
)
.is_err());
assert!(Family::new(lit(&["<http://x/>"]), vec![]).is_err());
assert!(Family::new(lit(&["<", ">"]), vec![input("a", "b")]).is_err());
assert!(Family::new(lit(&["<http://x/>"]), vec![input("a", "b")]).is_err());
}
#[test]
fn root_round_trips_and_refuses_bad_runs() {
let mut f = ci();
f.runs = vec![(2, 3), (7, 1)];
let bytes = encode_families(std::slice::from_ref(&f));
assert_eq!(decode_families(&bytes, 10).unwrap(), vec![f.clone()]);
assert!(decode_families(&bytes, 7).is_err(), "run past the chunks");
assert!(decode_families(&bytes[..bytes.len() - 1], 10).is_err());
let mut g = f.clone();
g.runs = vec![(2, 3), (3, 1)];
assert!(decode_families(&encode_families(&[g]), 10).is_err());
assert!(f.covers(2) && f.covers(4) && !f.covers(5) && f.covers(7) && !f.covers(8));
}
}