#![forbid(unsafe_code)] use std::collections::{HashMap, HashSet, VecDeque}; use chrono::{DateTime, Utc}; use futures::future::{join, join_all}; use serde::{Deserialize, Serialize}; use serde_json::Value; mod car; pub mod market; #[cfg(feature = "native")] mod http; #[cfg(feature = "wasm")] mod wasm; pub use car::{record_cid, verify_record}; pub use market::market_contract_held; #[cfg(feature = "native")] pub use http::{ContractHeldFn, HttpIo}; pub const ENDORSEMENT_NSID: &str = "link.ident.endorsement"; pub const ASSOCIATION_NSID: &str = "com.publicdomainrelay.temp.market.association"; pub const AGENT_OF_PREFIX: &str = "https://ident.link/agent-of/"; pub const MAX_DEPTH: usize = 100; pub const BUDGET: usize = 256; pub type Error = Box; #[derive(Clone, Debug, Default, Deserialize)] #[serde(rename_all = "camelCase")] pub struct DidDoc { #[serde(default)] pub id: String, #[serde(default)] pub also_known_as: Vec, #[serde(default)] pub verification_method: Vec, #[serde(default)] pub service: Vec, } #[derive(Clone, Debug, Deserialize)] #[serde(rename_all = "camelCase")] pub struct VerificationMethod { pub id: String, #[serde(default)] pub public_key_multibase: Option, } #[derive(Clone, Debug, Deserialize)] #[serde(rename_all = "camelCase")] pub struct Service { pub id: String, #[serde(rename = "type", default)] pub kind: String, #[serde(default)] pub service_endpoint: Value, } impl DidDoc { pub fn signing_key(&self) -> Option<&str> { self.verification_method .iter() .find(|m| self.is_fragment(&m.id, "#atproto"))? .public_key_multibase .as_deref() } pub fn pds(&self) -> Option<&str> { self.service .iter() .find(|s| self.is_fragment(&s.id, "#atproto_pds") && s.kind == "AtprotoPersonalDataServer")? .service_endpoint .as_str() } fn is_fragment(&self, id: &str, fragment: &str) -> bool { id == fragment || id.strip_prefix(self.id.as_str()) == Some(fragment) } } #[derive(Clone, Debug, PartialEq, Eq, Hash, Deserialize, Serialize)] pub struct StrongRef { pub uri: String, pub cid: String, } #[derive(Clone, Copy, Debug, Deserialize)] #[serde(rename_all = "camelCase", default)] pub struct Options { pub max_depth: usize, pub budget: usize, } impl Default for Options { fn default() -> Self { Self { max_depth: MAX_DEPTH, budget: BUDGET } } } #[derive(Clone, Debug, PartialEq, Eq, Deserialize, Serialize)] #[serde(rename_all = "camelCase")] pub struct Ancestor { pub did: String, pub depth: usize, #[serde(default, skip_serializing_if = "Option::is_none")] pub expires_at: Option>, } #[derive(Clone, Debug, PartialEq, Eq, Serialize)] #[serde(rename_all = "camelCase")] pub struct Walk { pub agent: String, pub ancestors: Vec, pub roots: Vec, #[serde(skip_serializing_if = "Option::is_none")] pub expires_at: Option>, pub truncated: bool, pub errors: Vec, } #[allow(async_fn_in_trait)] pub trait Io { async fn resolve_did(&self, did: &str) -> Result, Error>; async fn get_record(&self, repo: &str, collection: &str, rkey: &str) -> Result, Error>; async fn contract_held(&self, contract: &StrongRef, authorities: &[String]) -> Result; fn now(&self) -> DateTime; } pub fn is_did(s: &str) -> bool { let Some((method, id)) = s.strip_prefix("did:").and_then(|r| r.split_once(':')) else { return false; }; s.len() <= 2048 && !method.is_empty() && method.bytes().all(|b| b.is_ascii_lowercase()) && !id.is_empty() && id.bytes().all(|b| b.is_ascii_alphanumeric() || b"._:%-".contains(&b)) && !id.ends_with([':', '%']) } pub fn agent_of(also_known_as: &[String]) -> Vec { let mut out: Vec = Vec::new(); for p in also_known_as.iter().filter_map(|e| e.strip_prefix(AGENT_OF_PREFIX)) { if is_did(p) && !out.iter().any(|o| o == p) { out.push(p.to_string()); } } out } struct Edge { from: String, to: String, expires_at: Option>, contract: Option, alive: bool, } struct Grant { expires_at: Option>, contract: Option, } fn grant(value: &Value, agent: &str, now: DateTime) -> Option { if value.get("agent")?.as_str()? != agent { return None; } let expires_at = match value.get("expiresAt") { None => None, Some(v) => Some(DateTime::parse_from_rfc3339(v.as_str()?).ok()?.with_timezone(&Utc)), }; let contract = match value.get("contract") { None => None, Some(v) => Some(StrongRef::deserialize(v).ok()?), }; if expires_at.is_some_and(|e| now >= e) || (contract.is_some() && expires_at.is_none()) { return None; } Some(Grant { expires_at, contract }) } fn record(result: Result, Error>, uri: String, errors: &mut Vec) -> Option { result.unwrap_or_else(|e| { errors.push(format!("getRecord {uri}: {e}")); None }) } fn up(edges: &[Edge], start: &str) -> Vec { let mut out = Vec::new(); let mut seen = HashSet::from([start]); let mut queue = VecDeque::from([(start, 0, None)]); while let Some((x, d, exp)) = queue.pop_front() { for e in edges.iter().filter(|e| e.alive && e.from == x) { if seen.insert(e.to.as_str()) { let exp = min(exp, e.expires_at); out.push(Ancestor { did: e.to.clone(), depth: d + 1, expires_at: exp }); queue.push_back((&e.to, d + 1, exp)); } } } out } fn min(a: Option>, b: Option>) -> Option> { match (a, b) { (Some(a), Some(b)) => Some(a.min(b)), (a, b) => a.or(b), } } pub async fn walk(io: &I, agent: &str, options: Options) -> Walk { let now = io.now(); let mut errors = Vec::new(); let mut edges: Vec = Vec::new(); let mut stuck: HashSet = HashSet::new(); let mut truncated = false; let mut seen = HashSet::from([agent.to_string()]); let mut queue = VecDeque::from([(agent.to_string(), 0, vec![agent.to_string()])]); let mut lookups = 0; while let Some((x, d, path)) = queue.pop_front() { let doc = match io.resolve_did(&x).await { Ok(Some(doc)) => doc, Ok(None) => continue, Err(e) => { errors.push(format!("resolveDid {x}: {e}")); continue; } }; for p in agent_of(&doc.also_known_as) { if path.contains(&p) { stuck.insert(x.clone()); continue; } if d < options.max_depth { lookups += 2; } if d + 1 > options.max_depth || lookups > options.budget { truncated = true; stuck.insert(x.clone()); continue; } let (e, g) = join( io.get_record(&p, ENDORSEMENT_NSID, &x), io.get_record(&p, ASSOCIATION_NSID, &x), ) .await; let e = record(e, format!("at://{p}/{ENDORSEMENT_NSID}/{x}"), &mut errors); let g = record(g, format!("at://{p}/{ASSOCIATION_NSID}/{x}"), &mut errors); let endorsed = e.is_some_and(|e| e.get("agent").and_then(Value::as_str) == Some(x.as_str())); let Some(g) = g.and_then(|g| grant(&g, &x, now)).filter(|_| endorsed) else { continue; }; edges.push(Edge { from: x.clone(), to: p.clone(), expires_at: g.expires_at, contract: g.contract, alive: true }); if seen.insert(p.clone()) { let mut path = path.clone(); path.push(p.clone()); queue.push_back((p, d + 1, path)); } } } let mut held: HashMap> = HashMap::new(); loop { let checks: Vec<(usize, Vec)> = edges .iter() .enumerate() .filter(|(_, e)| e.alive && e.contract.is_some()) .map(|(i, e)| (i, std::iter::once(e.to.clone()).chain(up(&edges, &e.to).into_iter().map(|a| a.did)).collect())) .filter(|(i, authorities)| held.get(i) != Some(authorities)) .collect(); if checks.is_empty() { break; } let results = join_all(checks.iter().map(|(i, a)| io.contract_held(edges[*i].contract.as_ref().unwrap(), a))).await; for ((i, authorities), result) in checks.into_iter().zip(results) { match result { Ok(true) => { held.insert(i, authorities); } Ok(false) => edges[i].alive = false, Err(e) => { errors.push(format!("contractHeld {}: {e}", edges[i].contract.as_ref().unwrap().uri)); edges[i].alive = false; } } } } let mut ancestors = up(&edges, agent); let reached = ancestors.len(); ancestors.retain(|a| a.depth <= options.max_depth); truncated |= ancestors.len() < reached; let mut roots = Vec::new(); let mut expires_at = None; let nodes = std::iter::once((agent, None)).chain(ancestors.iter().map(|a| (a.did.as_str(), a.expires_at))); for (n, exp) in nodes { if !stuck.contains(n) && !edges.iter().any(|e| e.alive && e.from == n) { roots.push(n.to_string()); expires_at = min(expires_at, exp); } } Walk { agent: agent.to_string(), ancestors, roots, expires_at, truncated, errors } }