~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
1069 lines · 43.4 KB Raw History
//! Permission sets: `include:` scopes (`spec/OAUTH-PERMISSION-SETS.md`);
//! and space type declarations, which `space:` scopes name and which are
//! resolved the same way (`spec/OAUTH-SCOPES.md`, "Spaces"). A document is
//! resolved by its NSID: the authority's DID from DNS (or
//! `PDS_LEXICON_AUTHORITY_DID`), that DID's document, its schema record
//! fetched from its PDS with the record's proof checked, and the document
//! checked; then kept a while, in memory. What a set grants is its
//! permissions that are valid, written as scope strings.

use super::space_scope::SpacePermission;
use crate::Service;
use crate::space_credentials::jwt::Key;
use hickory_resolver::TokioResolver;
use pds_repo::data::{valid_did, valid_nsid};
use serde_json::{Map, Value as Json};
use std::borrow::Cow;
use std::collections::HashMap;
use std::net::SocketAddr;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex, OnceLock, PoisonError};
use std::time::Duration;

/// How long a set resolved is used before it is resolved again, in seconds.
const STALE: u64 = 60 * 60;
/// How long after it last resolved a set kept is used when resolving it again fails.
const EXPIRY: u64 = 90 * 24 * 60 * 60;
/// How long a set that did not resolve is not tried again.
const FAILED: u64 = 5 * 60;
/// The most sets kept; past it, the one least recently asked for goes.
const KEPT: usize = 10_000;
/// The most a schema record's answer may hold, and how long it may take.
const RECORD_MAX: usize = 1 << 20;
const RECORD_WAIT: Duration = Duration::from_secs(10);
/// The collection of Lexicon schema records.
const SCHEMA: &str = "com.atproto.lexicon.schema";
/// What an audience keeps as it is in a scope string: what JavaScript's
/// `encodeURIComponent` keeps, and `:` and `/`; so `#` is `%23`.
const AUDIENCE: &percent_encoding::AsciiSet = &percent_encoding::NON_ALPHANUMERIC
    .remove(b'-')
    .remove(b'_')
    .remove(b'.')
    .remove(b'!')
    .remove(b'~')
    .remove(b'*')
    .remove(b'\'')
    .remove(b'(')
    .remove(b')')
    .remove(b':')
    .remove(b'/');
/// A record action and its place in a scope string, in the order written.
const ACTIONS: [&str; 3] = ["create", "update", "delete"];

/// An `include:` scope that parses: the set's NSID, and the audience it
/// gives the set's `rpc` permissions that inherit one.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Include {
    pub nsid: String,
    pub aud: Option<String>,
}

/// The `include:` scope `token` is, if it parses: an `nsid`, positional or
/// as a parameter, that is an NSID, and at most an `aud`, a DID with a `#`
/// service fragment (not `*`), percent-decoded, and no other parameter.
pub(crate) fn include(token: &str) -> Option<Include> {
    let (head, query) = token.split_once('?').unwrap_or((token, ""));
    let (resource, positional) = head.split_once(':').unwrap_or((head, ""));
    if resource != "include" {
        return None;
    }
    let decode = |s: &str| {
        percent_encoding::percent_decode_str(s)
            .decode_utf8()
            .ok()
            .map(|c| c.into_owned())
    };
    let mut nsid = if positional.is_empty() {
        None
    } else {
        Some(decode(positional)?)
    };
    let mut aud = None;
    for pair in query.split('&').filter(|p| !p.is_empty()) {
        let (k, v) = pair.split_once('=')?;
        let slot = match decode(k)?.as_str() {
            "nsid" => &mut nsid,
            "aud" => &mut aud,
            _ => return None,
        };
        if slot.replace(decode(v)?).is_some() {
            return None;
        }
    }
    let nsid = nsid.filter(|n| valid_nsid(n))?;
    let service = |a: &String| {
        a.split_once('#')
            .is_some_and(|(did, id)| valid_did(did) && !id.is_empty())
    };
    if aud.as_ref().is_some_and(|a| !service(a)) {
        return None;
    }
    Some(Include { nsid, aud })
}

/// An NSID's authority: its segments but the last, reversed.
pub(crate) fn authority(nsid: &str) -> String {
    let mut segments: Vec<&str> = nsid.split('.').collect();
    segments.pop();
    segments.reverse();
    segments.join(".")
}

/// Why a document cannot be used: it does not resolve, or what it resolves
/// to is not a set, or not a space type declaration.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Unresolved {
    Fails(String),
    NotASet,
    NotASpace,
}

/// A document resolved: its `defs.main`, as published, a set's or a
/// declaration's; or why not.
pub(crate) type Resolved = Result<Arc<Json>, Unresolved>;

/// What resolving a document gave: a set's or a declaration's `defs.main`,
/// or a document that is neither.
type Got = Result<Arc<Json>, ()>;

/// A set kept: what it last resolved to and when, and when resolving it
/// last failed, and why; and when it was last asked for, as a count.
struct Kept {
    got: Option<(Got, u64)>,
    failed: Option<(u64, String)>,
    asked: u64,
}

impl Kept {
    /// What it last resolved to, if that is within `EXPIRY` at `now`.
    fn fallback(&self, now: u64) -> Option<Resolved> {
        let (got, at) = self.got.as_ref()?;
        (now < at + EXPIRY).then(|| answer(got))
    }
}

fn answer(got: &Got) -> Resolved {
    got.clone().map_err(|()| Unresolved::NotASet)
}

/// The sets resolved, shared by every account and session, in memory alone.
#[derive(Default)]
pub(crate) struct Sets {
    kept: Mutex<HashMap<String, Kept>>,
    asked: AtomicU64,
    dns: OnceLock<Result<TokioResolver, String>>,
}

impl Sets {
    /// The set `nsid` names: the one kept if it resolved within `STALE`;
    /// else resolved now, unless that failed within `FAILED`; and should
    /// it not resolve, the one kept if it resolved within `EXPIRY`.
    pub async fn resolve(&self, svc: &Service, nsid: &str) -> Resolved {
        let now = svc.sessions.now();
        let asked = self.asked.fetch_add(1, Ordering::Relaxed);
        {
            let mut kept = self.kept.lock().unwrap_or_else(PoisonError::into_inner);
            if let Some(k) = kept.get_mut(nsid) {
                k.asked = asked;
                if let Some((got, at)) = &k.got
                    && now < at + STALE
                {
                    return answer(got);
                }
                if let Some((at, why)) = &k.failed
                    && now < at + FAILED
                {
                    return k
                        .fallback(now)
                        .unwrap_or_else(|| Err(Unresolved::Fails(why.clone())));
                }
            }
        }
        let fetched = self.fetch(svc, nsid).await;
        let mut kept = self.kept.lock().unwrap_or_else(PoisonError::into_inner);
        let k = kept.entry(nsid.to_string()).or_insert(Kept {
            got: None,
            failed: None,
            asked,
        });
        k.asked = k.asked.max(asked);
        let out = match fetched {
            Ok(got) => {
                k.got = Some((got.clone(), now));
                k.failed = None;
                answer(&got)
            }
            Err(why) => {
                let out = k
                    .fallback(now)
                    .unwrap_or_else(|| Err(Unresolved::Fails(why.clone())));
                k.failed = Some((now, why));
                out
            }
        };
        if kept.len() > KEPT
            && let Some(least) = kept
                .iter()
                .min_by_key(|(_, k)| k.asked)
                .map(|(n, _)| n.clone())
        {
            kept.remove(&least);
        }
        out
    }

    /// Each distinct set `scope`'s `include:` tokens name, resolved; or the
    /// first that cannot be used, with why.
    pub async fn resolve_all(
        &self,
        svc: &Service,
        scope: &[String],
    ) -> Result<HashMap<String, Arc<Json>>, (String, Unresolved)> {
        let mut out = HashMap::new();
        for i in scope.iter().filter_map(|t| include(t)) {
            if out.contains_key(&i.nsid) {
                continue;
            }
            let set = self
                .resolve(svc, &i.nsid)
                .await
                .and_then(|m| {
                    if m["type"] == "permission-set" {
                        Ok(m)
                    } else {
                        Err(Unresolved::NotASet)
                    }
                })
                .map_err(|u| (i.nsid.clone(), u))?;
            out.insert(i.nsid, set);
        }
        Ok(out)
    }

    /// Each distinct space type `scope` names (`space_types`), with the
    /// sets it includes `sets`, its declaration resolved; or the first that
    /// cannot be used, with why.
    pub async fn resolve_spaces(
        &self,
        svc: &Service,
        scope: &[String],
        sets: &HashMap<String, Arc<Json>>,
    ) -> Result<HashMap<String, Arc<Json>>, (String, Unresolved)> {
        let mut out = HashMap::new();
        for nsid in space_types(scope, sets) {
            let main = self
                .resolve(svc, &nsid)
                .await
                .and_then(|m| {
                    if m["type"] == "space" {
                        Ok(m)
                    } else {
                        Err(Unresolved::NotASpace)
                    }
                })
                .map_err(|u| match u {
                    Unresolved::NotASet => (nsid.clone(), Unresolved::NotASpace),
                    u => (nsid.clone(), u),
                })?;
            out.insert(nsid, main);
        }
        Ok(out)
    }

    /// What a session's scope is expanded with: its sets, then its space
    /// types' declarations; or the first that cannot be used, with why.
    pub async fn for_token(
        &self,
        svc: &Service,
        scope: &[String],
    ) -> Result<Expansion, (String, Unresolved)> {
        let sets = self.resolve_all(svc, scope).await?;
        let spaces = self.resolve_spaces(svc, scope, &sets).await?;
        Ok(Expansion { sets, spaces })
    }

    /// Resolve the set `nsid` names now (`spec/OAUTH-PERMISSION-SETS.md`,
    /// "Resolving a set"), or say why it does not resolve.
    async fn fetch(&self, svc: &Service, nsid: &str) -> Result<Got, String> {
        let did = match &svc.config.lexicon_authority {
            Some(did) => did.clone(),
            None => {
                let dns = self
                    .dns
                    .get_or_init(|| resolver(svc.config.lexicon_dns))
                    .as_ref()
                    .map_err(Clone::clone)?;
                authority_did(dns, &authority(nsid)).await?
            }
        };
        let doc = crate::space_authz::document(svc, &did)
            .await
            .ok_or_else(|| format!("{did}'s document cannot be read"))?;
        let key = Key::of_document(&doc, &did)
            .ok_or_else(|| format!("{did}'s document names no #atproto key"))?;
        let endpoint = crate::proxy::service_endpoint(&doc, &did, "atproto_pds", None)
            .and_then(|e| crate::outbound::origin(&Json::String(e)))
            .ok_or_else(|| format!("{did}'s document names no #atproto_pds endpoint"))?;
        let mut url = endpoint
            .join("/xrpc/com.atproto.sync.getRecord")
            .map_err(|e| e.to_string())?;
        url.query_pairs_mut()
            .append_pair("did", &did)
            .append_pair("collection", SCHEMA)
            .append_pair("rkey", nsid);
        let out = &svc.outbound;
        let got = out
            .fetch_limited(
                crate::ops::Target::Lexicon,
                out.client().get(url),
                RECORD_MAX,
                RECORD_WAIT,
            )
            .await?;
        if got.status != 200 {
            return Err(format!("{nsid}'s record: answered {}", got.status));
        }
        let path = format!("{SCHEMA}/{nsid}");
        let record = pds_repo::proven_record(&got.body, &did, &path, |message, sig| {
            key.verifies(key.alg(), message, sig, false)
        })
        .map_err(|why| format!("{nsid}'s record: {why}"))?;
        document(&pds_repo::data::to_json(&record), nsid)
    }
}

/// The DNS resolver `_lexicon` records are looked up with: the system's,
/// or one asking only `server` (the tests' stub).
fn resolver(server: Option<SocketAddr>) -> Result<TokioResolver, String> {
    use hickory_resolver::config::{ConnectionConfig, NameServerConfig, ResolverConfig};
    use hickory_resolver::net::runtime::TokioRuntimeProvider;
    let built = match server {
        Some(addr) => {
            let mut udp = ConnectionConfig::udp();
            udp.port = addr.port();
            let config = ResolverConfig::from_name_servers(vec![NameServerConfig::new(
                addr.ip(),
                true,
                vec![udp],
            )]);
            TokioResolver::builder_with_config(config, TokioRuntimeProvider::default()).build()
        }
        None => TokioResolver::builder_tokio().and_then(|b| b.build()),
    };
    built.map_err(|e| format!("a DNS resolver: {e}"))
}

/// The DID an authority's `_lexicon` TXT record names: the one record whose
/// text begins `did=`.
async fn authority_did(dns: &TokioResolver, authority: &str) -> Result<String, String> {
    use hickory_resolver::proto::rr::RData;
    let name = format!("_lexicon.{authority}.");
    let found = dns
        .txt_lookup(name.as_str())
        .await
        .map_err(|e| format!("{name}: {e}"))?;
    let dids: Vec<String> = found
        .answers()
        .iter()
        .filter_map(|r| match &r.data {
            RData::TXT(t) => Some(
                t.txt_data
                    .iter()
                    .map(|s| String::from_utf8_lossy(s))
                    .collect::<String>(),
            ),
            _ => None,
        })
        .filter_map(|text| text.strip_prefix("did=").map(str::to_string))
        .collect();
    match dids.as_slice() {
        [did] if valid_did(did) => Ok(did.clone()),
        [_] => Err(format!("{name} names no DID")),
        [] => Err(format!("{name} has no did= record")),
        _ => Err(format!("{name} has more than one did= record")),
    }
}

/// A schema record's value checked (`spec/OAUTH-PERMISSION-SETS.md`, "Resolving
/// a set", 5; `spec/OAUTH-SCOPES.md`, "Space type declarations"): a set's or
/// a declaration's `defs.main`, a document that is neither, or why it does
/// not resolve.
fn document(doc: &Json, nsid: &str) -> Result<Got, String> {
    let bad = |why: &str| Err(format!("{nsid}'s document: {why}"));
    if doc["$type"] != SCHEMA || doc["lexicon"] != 1 || doc["id"] != nsid {
        return bad("not a lexicon schema of its NSID");
    }
    let Some(main) = doc["defs"].get("main").filter(|m| m.is_object()) else {
        return bad("no defs.main");
    };
    if main["type"] == "space" {
        if !main["key"].is_string() {
            return bad("a space type declaration with no key");
        }
        let declared = main["collections"]
            .as_array()
            .is_some_and(|cs| cs.iter().all(|c| c.as_str().is_some_and(valid_nsid)));
        if !declared {
            return bad("collections not a list of NSIDs");
        }
        return Ok(Ok(Arc::new(main.clone())));
    }
    if main["type"] != "permission-set" {
        return Ok(Err(()));
    }
    let scalar = |v: &Json| v.is_string() || v.is_number() || v.is_boolean();
    let field = |v: &Json| scalar(v) || v.as_array().is_some_and(|a| a.iter().all(scalar));
    let permission = |p: &Json| {
        p.as_object().is_some_and(|p| {
            p.get("type").is_some_and(|t| t == "permission")
                && p.get("resource").is_some_and(Json::is_string)
                && p.values().all(field)
        })
    };
    if !main["permissions"]
        .as_array()
        .is_some_and(|ps| ps.iter().all(permission))
    {
        return bad("permissions not a list of permissions");
    }
    let text = |k: &str| main.get(k).is_none_or(Json::is_string);
    let langs = |k: &str| {
        main.get(k).is_none_or(|v| {
            v.as_object().is_some_and(|m| {
                m.iter()
                    .all(|(tag, s)| pds_lexicon::valid_format("language", tag) && s.is_string())
            })
        })
    };
    if !(text("title") && text("detail") && langs("title:lang") && langs("detail:lang")) {
        return bad("a title or detail not as a set has them");
    }
    Ok(Ok(Arc::new(main.clone())))
}

/// What set `nsid`, whose `defs.main` is `main`, grants with the `include:`'s
/// audience `aud`: its valid permissions, each as a scope string, in order
/// (`spec/OAUTH-PERMISSION-SETS.md`, "What a set grants").
pub(crate) fn grant(nsid: &str, main: &Json, aud: Option<&str>) -> Vec<String> {
    let prefix = &nsid[..nsid.rfind('.').map_or(0, |i| i + 1)];
    let inside = |n: &str| n.len() > prefix.len() && n.starts_with(prefix);
    main["permissions"]
        .as_array()
        .into_iter()
        .flatten()
        .filter_map(|p| permission(p.as_object()?, aud, &inside))
        .collect()
}

/// One permission of a set as a scope string, if it is valid.
fn permission(
    p: &Map<String, Json>,
    aud: Option<&str>,
    inside: &dyn Fn(&str) -> bool,
) -> Option<String> {
    let takes = |fields: &[&str]| {
        p.keys()
            .all(|k| ["type", "resource"].contains(&k.as_str()) || fields.contains(&k.as_str()))
    };
    // One or more NSIDs within the set's namespace, each once, sorted.
    let names = |v: &Json| -> Option<Vec<String>> {
        let mut out = v
            .as_array()?
            .iter()
            .map(|n| {
                n.as_str()
                    .filter(|n| valid_nsid(n) && inside(n))
                    .map(str::to_string)
            })
            .collect::<Option<Vec<String>>>()?;
        out.sort();
        out.dedup();
        (!out.is_empty()).then_some(out)
    };
    // `name:<one>`, or `name?key=<a>&key=<b>`; and the separator before what follows.
    let head = |name: &str, key: &str, values: &[String]| match values {
        [one] => (format!("{name}:{one}"), '?'),
        many => {
            let pairs: Vec<String> = many.iter().map(|v| format!("{key}={v}")).collect();
            (format!("{name}?{}", pairs.join("&")), '&')
        }
    };
    match p.get("resource")?.as_str()? {
        "repo" if takes(&["collection", "action"]) => {
            let collections = names(p.get("collection")?)?;
            let actions = match p.get("action") {
                None => ACTIONS.to_vec(),
                Some(a) => {
                    let given = a
                        .as_array()?
                        .iter()
                        .map(|a| a.as_str().filter(|a| ACTIONS.contains(a)))
                        .collect::<Option<Vec<&str>>>()?;
                    let ordered: Vec<&str> =
                        ACTIONS.into_iter().filter(|a| given.contains(a)).collect();
                    (!ordered.is_empty()).then_some(ordered)?
                }
            };
            let (mut s, mut sep) = head("repo", "collection", &collections);
            if actions.len() < ACTIONS.len() {
                for a in actions {
                    s.push(sep);
                    s.push_str("action=");
                    s.push_str(a);
                    sep = '&';
                }
            }
            Some(s)
        }
        "rpc" if takes(&["lxm", "aud", "inheritAud"]) => {
            let methods = names(p.get("lxm")?)?;
            let audience = match (p.get("aud"), p.get("inheritAud")) {
                (Some(a), None) if a == "*" => "*",
                (None, Some(Json::Bool(true))) => aud?,
                _ => return None,
            };
            let (mut s, sep) = head("rpc", "lxm", &methods);
            s.push(sep);
            s.push_str("aud=");
            s.extend(percent_encoding::utf8_percent_encode(audience, AUDIENCE));
            Some(s)
        }
        // A `space:` token's parameters (`spec/OAUTH-SCOPES.md`, "Spaces",
        // "Which parse"): each a string, or an array of one or more where
        // it takes many, with values the table allows; the type within the
        // set's namespace, its collections under any. Written as a `space:`
        // token is written again, its defaults left out.
        "space" => {
            let params = super::scope::params("space")?;
            let mut given: HashMap<&str, Vec<String>> = HashMap::new();
            for (k, v) in p {
                if k == "type" || k == "resource" {
                    continue;
                }
                let param = params.iter().find(|t| t.name == k.as_str())?;
                let values: Vec<String> = match v {
                    Json::String(s) if !param.many => vec![s.clone()],
                    Json::Array(a) if param.many && !a.is_empty() => a
                        .iter()
                        .map(|x| x.as_str().map(str::to_string))
                        .collect::<Option<_>>()?,
                    _ => return None,
                };
                if !values.iter().all(|v| (param.allows)(v)) {
                    return None;
                }
                given.insert(param.name, values);
            }
            let mut take = |k: &str| given.remove(k);
            let space_type = take("spaceType")?.pop().filter(|t| inside(t))?;
            let permission = SpacePermission::new(
                space_type,
                take("authority").and_then(|mut v| v.pop()),
                take("skey").and_then(|mut v| v.pop()),
                take("collection"),
                take("action"),
                take("manage"),
            );
            Some(permission.to_scope())
        }
        _ => None,
    }
}

/// What a session's scope is expanded with: the sets it includes, and the
/// declarations of the space types it names, each by its NSID.
#[derive(Clone, Debug, Default)]
pub(crate) struct Expansion {
    pub sets: HashMap<String, Arc<Json>>,
    pub spaces: HashMap<String, Arc<Json>>,
}

/// A scope as the sets `sets` grant it: each `include:` token, in order,
/// replaced by what its set grants, these first; then the other tokens, in
/// order; nothing dropped as a duplicate. Every set `scope` includes must
/// be in `sets`.
fn granted<'a>(scope: &'a [String], sets: &HashMap<String, Arc<Json>>) -> Vec<Cow<'a, str>> {
    let mut out = Vec::new();
    let mut rest = Vec::new();
    for t in scope {
        match include(t) {
            Some(i) => {
                if let Some(main) = sets.get(&i.nsid) {
                    out.extend(
                        grant(&i.nsid, main, i.aud.as_deref())
                            .into_iter()
                            .map(Cow::Owned),
                    );
                }
            }
            None => rest.push(Cow::Borrowed(t.as_str())),
        }
    }
    out.extend(rest);
    out
}

/// The space types a scope names, each once, but `*`: those of its `space:`
/// tokens and of the `space` permissions its sets `sets` grant.
pub(crate) fn space_types(scope: &[String], sets: &HashMap<String, Arc<Json>>) -> Vec<String> {
    super::space_scope::types(granted(scope, sets).iter().map(|t| t.as_ref()))
}

/// Whether a scope, with what its sets `sets` grant, has a `space`
/// permission: whether the authorization page gives `spaces` and
/// `spaceHandles` (`spec/OAUTH-SCOPES.md`, "On the authorization page").
pub(crate) fn has_space(scope: &[String], sets: &HashMap<String, Arc<Json>>) -> bool {
    granted(scope, sets)
        .iter()
        .any(|t| super::space_scope::SpacePermission::of(t).is_some())
}

/// A scope expanded for the account `did` (`granted`), each `space:` string
/// then rewritten (`super::space_scope::rewritten`).
pub(crate) fn expand(scope: &[String], e: &Expansion, did: &str) -> Vec<String> {
    granted(scope, &e.sets)
        .iter()
        .map(|t| super::space_scope::rewritten(t, did, &e.spaces))
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    use serde_json::json;

    #[test]
    fn includes() {
        let i = |nsid: &str, aud: Option<&str>| {
            Some(Include {
                nsid: nsid.into(),
                aud: aud.map(str::to_string),
            })
        };
        assert_eq!(
            include("include:com.example.authFull"),
            i("com.example.authFull", None)
        );
        assert_eq!(
            include("include:com.example.authFull?aud=did:web:api.example.com%23svc"),
            i("com.example.authFull", Some("did:web:api.example.com#svc"))
        );
        assert_eq!(
            include("include?nsid=com.example.authFull"),
            i("com.example.authFull", None)
        );
        for bad in [
            "include",
            "include:",
            "include:notansid",
            "include:com.example.a?nsid=com.example.b",
            "include:com.example.a?aud=*",
            "include:com.example.a?aud=did:web:x.com",
            "include:com.example.a?aud=did:web:x.com%23",
            "include:com.example.a?aud=did:web:x.com%23a&aud=did:web:x.com%23b",
            "include:com.example.a?other=1",
            "repo:com.example.a",
        ] {
            assert_eq!(include(bad), None, "{bad}");
        }
        assert_eq!(
            authority("com.example.calendar.basePermissions"),
            "calendar.example.com"
        );
    }

    /// The table of `spec/OAUTH-PERMISSION-SETS.md`, "As scope strings", and
    /// each reason a permission is dropped, alone.
    #[test]
    fn grants() {
        const SET: &str = "com.example.calendar.basePermissions";
        let one = |p: Json, aud: Option<&str>| {
            grant(
                SET,
                &json!({ "type": "permission-set", "permissions": [p] }),
                aud,
            )
        };
        let aud = Some("did:web:api.example.com#cal");
        let ev = "com.example.calendar.event";
        for (p, want) in [
            (
                json!({ "type": "permission", "resource": "repo", "collection": [ev] }),
                "repo:com.example.calendar.event",
            ),
            (
                json!({ "type": "permission", "resource": "repo", "collection": [ev, "com.example.calendar.attendee"] }),
                "repo?collection=com.example.calendar.attendee&collection=com.example.calendar.event",
            ),
            (
                json!({ "type": "permission", "resource": "repo", "collection": [ev], "action": ["delete", "create"] }),
                "repo:com.example.calendar.event?action=create&action=delete",
            ),
            (
                json!({ "type": "permission", "resource": "repo", "collection": [ev], "action": ["create", "update", "delete"] }),
                "repo:com.example.calendar.event",
            ),
            (
                json!({ "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.getEvents"], "aud": "*" }),
                "rpc:com.example.calendar.getEvents?aud=*",
            ),
            (
                json!({ "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.getEvents", "com.example.calendar.addEvent"], "inheritAud": true }),
                "rpc?lxm=com.example.calendar.addEvent&lxm=com.example.calendar.getEvents&aud=did:web:api.example.com%23cal",
            ),
            (
                json!({ "type": "permission", "resource": "repo", "collection": [ev, "com.example.calendar.attendee", ev], "action": ["update"] }),
                "repo?collection=com.example.calendar.attendee&collection=com.example.calendar.event&action=update",
            ),
            (
                json!({ "type": "permission", "resource": "repo", "collection": ["com.example.calendar.sub.thing"] }),
                "repo:com.example.calendar.sub.thing",
            ),
        ] {
            assert_eq!(one(p.clone(), aud), [want], "{p}");
        }
        for p in [
            json!({ "type": "permission", "resource": "blob", "accept": ["*/*"] }),
            json!({ "type": "permission", "resource": "account", "attr": "email" }),
            json!({ "type": "permission", "resource": "repo", "collection": [ev], "other": true }),
            json!({ "type": "permission", "resource": "repo", "collection": [] }),
            json!({ "type": "permission", "resource": "repo" }),
            json!({ "type": "permission", "resource": "repo", "collection": ["*"] }),
            json!({ "type": "permission", "resource": "repo", "collection": [ev], "action": [] }),
            json!({ "type": "permission", "resource": "repo", "collection": [ev], "action": ["read"] }),
            json!({ "type": "permission", "resource": "repo", "collection": [ev], "action": "create" }),
            json!({ "type": "permission", "resource": "repo", "collection": ["com.example.other.x"] }),
            json!({ "type": "permission", "resource": "repo", "collection": ["com.example.calendar"] }),
            json!({ "type": "permission", "resource": "repo", "collection": ["com.example.calendar."] }),
            json!({ "type": "permission", "resource": "repo", "collection": ["com.Example.calendar.event"] }),
            json!({ "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.x"], "aud": "did:web:a.com#x" }),
            json!({ "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.x"], "inheritAud": false }),
            json!({ "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.x"], "aud": "*", "inheritAud": true }),
            json!({ "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.x"] }),
            json!({ "type": "permission", "resource": "rpc", "lxm": ["*"], "aud": "*" }),
            json!({ "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.x"], "inheritAud": "true" }),
        ] {
            assert_eq!(one(p.clone(), aud), Vec::<String>::new(), "{p}");
        }
        // With no `include:` audience, a permission that inherits one is dropped.
        let inherits = json!({ "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.x"], "inheritAud": true });
        assert_eq!(one(inherits, None), Vec::<String>::new());
        // The rest kept, in order, beside one dropped.
        let main = json!({ "permissions": [
            { "type": "permission", "resource": "rpc", "lxm": ["com.example.calendar.b"], "aud": "*" },
            { "type": "permission", "resource": "blob", "accept": ["*/*"] },
            { "type": "permission", "resource": "repo", "collection": [ev] },
        ] });
        assert_eq!(
            grant(SET, &main, None),
            [
                "rpc:com.example.calendar.b?aud=*",
                "repo:com.example.calendar.event"
            ]
        );
        // Expanded: each include's grant, in order, then the other tokens; duplicates kept.
        let sets = Expansion {
            sets: HashMap::from([(SET.to_string(), Arc::new(main))]),
            spaces: HashMap::new(),
        };
        let scope: Vec<String> = [
            "atproto",
            "include:com.example.calendar.basePermissions",
            "repo:com.example.calendar.event",
            "include:com.example.calendar.basePermissions?aud=did:web:x.com%23y",
        ]
        .map(str::to_string)
        .to_vec();
        assert_eq!(
            expand(&scope, &sets, "did:plc:abc"),
            [
                "rpc:com.example.calendar.b?aud=*",
                "repo:com.example.calendar.event",
                "rpc:com.example.calendar.b?aud=*",
                "repo:com.example.calendar.event",
                "atproto",
                "repo:com.example.calendar.event",
            ]
        );
    }

    /// When the authorization page has `spaces` and `spaceHandles`, and the
    /// DIDs whose handles it verifies: a `space:` token's, or a set's
    /// `space` permission's, makes both; only the scope's own tokens name
    /// the DIDs, each once.
    #[test]
    fn on_the_page() {
        const SET: &str = "com.example.forum.access";
        let main = json!({ "type": "permission-set", "permissions": [
            { "type": "permission", "resource": "space", "spaceType": "com.example.forum.board", "authority": "did:plc:set" },
        ] });
        let sets = HashMap::from([(SET.to_string(), Arc::new(main))]);
        let scope = |s: &str| s.split(' ').map(str::to_string).collect::<Vec<_>>();
        let dids =
            |s: &[String]| super::super::space_scope::authorities(s.iter().map(String::as_str));
        // No space permission: neither key.
        let none = scope("atproto repo:* include:com.example.other.set space:forum");
        assert!(!has_space(&none, &sets));
        // One of `*` alone is one.
        assert!(has_space(&scope("atproto space:*?authority=*"), &sets));
        // A set's grant alone: the keys, but no DID to verify.
        let set = scope("atproto include:com.example.forum.access");
        assert!(has_space(&set, &sets));
        assert!(dids(&set).is_empty());
        // The scope's DIDs, each once, in order; `self` and `*` none.
        let own = scope(
            "atproto include:com.example.forum.access space:a.b.c?authority=did:plc:b space:*?authority=did:web:a.com space:a.b.c?authority=did:plc:b&action=read space:a.b.c space:*?authority=* space:a.b.c?authority=me",
        );
        assert!(has_space(&own, &sets));
        assert_eq!(dids(&own), ["did:plc:b", "did:web:a.com"]);
    }

    /// The `space` rows of `spec/OAUTH-PERMISSION-SETS.md`, "As scope
    /// strings", and each reason a `space` permission is dropped, alone; then
    /// its types resolved and its strings rewritten in the expansion.
    #[test]
    fn space_grants() {
        const SET: &str = "com.example.calendar.basePermissions";
        let one = |p: Json| {
            grant(
                SET,
                &json!({ "type": "permission-set", "permissions": [p] }),
                None,
            )
        };
        let st = "com.example.calendar.space";
        let space = |fields: Json| {
            let mut p = json!({ "type": "permission", "resource": "space", "spaceType": st });
            p.as_object_mut()
                .unwrap()
                .extend(fields.as_object().unwrap().clone());
            p
        };
        for (p, want) in [
            (space(json!({})), "space:com.example.calendar.space"),
            (
                space(
                    json!({ "authority": "self", "action": ["delete", "read", "create", "update"] }),
                ),
                "space:com.example.calendar.space",
            ),
            (
                space(
                    json!({ "authority": "did:plc:abc", "skey": "main", "collection": ["org.other.note", "*"], "action": ["create", "read"] }),
                ),
                "space:com.example.calendar.space?authority=did:plc:abc&skey=main&collection=*&action=read&action=create",
            ),
            (
                space(
                    json!({ "collection": ["com.example.calendar.event"], "manage": ["delete", "create"] }),
                ),
                "space:com.example.calendar.space?collection=com.example.calendar.event&manage=create&manage=delete",
            ),
            (
                space(
                    json!({ "authority": "*", "skey": "*", "collection": ["org.b.c", "org.a.c", "org.b.c"], "action": ["read_self", "read_self"] }),
                ),
                "space:com.example.calendar.space?authority=*&collection=org.a.c&collection=org.b.c&action=read_self",
            ),
            (
                space(
                    json!({ "collection": ["*"], "action": ["read", "create", "update", "delete", "read_self"] }),
                ),
                "space:com.example.calendar.space?collection=*&action=read_self&action=read&action=create&action=update&action=delete",
            ),
            (
                json!({ "type": "permission", "resource": "space", "spaceType": "com.example.calendar.sub.space", "manage": ["update"] }),
                "space:com.example.calendar.sub.space?manage=update",
            ),
        ] {
            assert_eq!(one(p.clone()), [want], "{p}");
        }
        for p in [
            json!({ "type": "permission", "resource": "space" }),
            json!({ "type": "permission", "resource": "space", "spaceType": "*" }),
            json!({ "type": "permission", "resource": "space", "spaceType": "com.example.other.space" }),
            json!({ "type": "permission", "resource": "space", "spaceType": "com.example.calendar" }),
            json!({ "type": "permission", "resource": "space", "spaceType": "com.Example.calendar.space" }),
            json!({ "type": "permission", "resource": "space", "spaceType": ["com.example.calendar.space"] }),
            space(json!({ "other": 1 })),
            space(json!({ "aud": "*" })),
            space(json!({ "authority": "me" })),
            space(json!({ "authority": ["self"] })),
            space(json!({ "skey": "a/b" })),
            space(json!({ "skey": 1 })),
            space(json!({ "collection": "com.example.calendar.event" })),
            space(json!({ "collection": [] })),
            space(json!({ "collection": ["notansid"] })),
            space(json!({ "collection": [1] })),
            space(json!({ "action": ["write"] })),
            space(json!({ "action": [] })),
            space(json!({ "action": "read" })),
            space(json!({ "manage": ["read"] })),
            space(json!({ "manage": [] })),
        ] {
            assert_eq!(one(p.clone()), Vec::<String>::new(), "{p}");
        }
        // A set's types beside the scope's own, each once, but `*`; then
        // each `space:` string of the expansion rewritten.
        let main = json!({ "permissions": [
            { "type": "permission", "resource": "space", "spaceType": st },
            { "type": "permission", "resource": "space", "spaceType": st, "authority": "*", "action": ["read"] },
        ] });
        let sets = HashMap::from([(SET.to_string(), Arc::new(main))]);
        let scope: Vec<String> = [
            "space:com.example.forum",
            "include:com.example.calendar.basePermissions",
            "space:*?authority=*&action=read",
        ]
        .map(str::to_string)
        .to_vec();
        assert_eq!(
            space_types(&scope, &sets),
            ["com.example.calendar.space", "com.example.forum"]
        );
        let e = Expansion {
            sets,
            spaces: HashMap::from([(
                st.to_string(),
                Arc::new(
                    json!({ "type": "space", "key": "any", "collections": ["com.example.calendar.event"] }),
                ),
            )]),
        };
        assert_eq!(
            expand(&scope, &e, "did:plc:abc"),
            [
                "space:com.example.calendar.space?authority=did:plc:abc&collection=com.example.calendar.event",
                "space:com.example.calendar.space?authority=*&collection=com.example.calendar.event&action=read",
                "space:com.example.forum?authority=did:plc:abc",
                "space:*?authority=*&action=read",
            ]
        );
    }

    #[test]
    fn documents() {
        const N: &str = "com.example.calendar.basePermissions";
        let doc = |main: Json| json!({ "$type": SCHEMA, "lexicon": 1, "id": N, "defs": { "main": main } });
        let set = json!({ "type": "permission-set", "title": "T", "title:lang": { "en-GB": "T", "ja": "\u{30c6}" }, "detail": "D",
            "permissions": [{ "type": "permission", "resource": "repo", "collection": ["com.example.calendar.event"], "n": 1, "b": [true, "x"] }] });
        assert_eq!(document(&doc(set.clone()), N), Ok(Ok(Arc::new(set))));
        assert_eq!(document(&doc(json!({ "type": "record" })), N), Ok(Err(())));
        let with = |k: &str, v: Json| {
            let mut d = doc(json!({ "type": "permission-set", "permissions": [] }));
            d[k] = v;
            d
        };
        let main_with = |k: &str, v: Json| {
            let mut m = json!({ "type": "permission-set", "permissions": [] });
            m[k] = v;
            doc(m)
        };
        for bad in [
            with("$type", json!("com.example.x")),
            with("lexicon", json!(2)),
            with("id", json!("com.example.calendar.other")),
            with("defs", json!({})),
            main_with("permissions", json!({})),
            main_with("permissions", json!([{ "type": "x", "resource": "repo" }])),
            main_with("permissions", json!([{ "type": "permission" }])),
            main_with(
                "permissions",
                json!([{ "type": "permission", "resource": "repo", "collection": { "a": 1 } }]),
            ),
            main_with(
                "permissions",
                json!([{ "type": "permission", "resource": "repo", "collection": [["a"]] }]),
            ),
            main_with("title", json!(5)),
            main_with("detail:lang", json!({ "not a tag!": "x" })),
            main_with("title:lang", json!({ "en": 5 })),
        ] {
            assert!(document(&bad, N).is_err(), "{bad}");
        }
    }

    /// `_lexicon` TXT records looked up from a stub DNS server: the one
    /// `did=` record names the DID; none, or more than one, names none.
    #[tokio::test]
    async fn authorities_from_dns() {
        let socket = tokio::net::UdpSocket::bind("127.0.0.1:0").await.unwrap();
        let addr = socket.local_addr().unwrap();
        let records: HashMap<&str, Vec<&str>> = HashMap::from([
            (
                "_lexicon.calendar.example.com",
                vec!["did=did:plc:aaaaaaaaaaaaaaaaaaaaaaaa"],
            ),
            (
                "_lexicon.mixed.example.com",
                vec!["v=spf1 -all", "did=did:web:lex.example.com"],
            ),
            (
                "_lexicon.two.example.com",
                vec![
                    "did=did:plc:aaaaaaaaaaaaaaaaaaaaaaaa",
                    "did=did:plc:bbbbbbbbbbbbbbbbbbbbbbbb",
                ],
            ),
            ("_lexicon.other.example.com", vec!["v=spf1 -all"]),
            ("_lexicon.bad.example.com", vec!["did=not a did"]),
        ]);
        let stub = tokio::spawn(async move {
            let mut buf = [0u8; 1500];
            loop {
                let (n, from) = socket.recv_from(&mut buf).await.unwrap();
                let answer = stub_answer(&buf[..n], &records);
                socket.send_to(&answer, from).await.unwrap();
            }
        });
        let dns = resolver(Some(addr)).unwrap();
        assert_eq!(
            authority_did(&dns, "calendar.example.com").await,
            Ok("did:plc:aaaaaaaaaaaaaaaaaaaaaaaa".into())
        );
        assert_eq!(
            authority_did(&dns, "mixed.example.com").await,
            Ok("did:web:lex.example.com".into())
        );
        for none in [
            "two.example.com",
            "other.example.com",
            "bad.example.com",
            "absent.example.com",
        ] {
            assert!(authority_did(&dns, none).await.is_err(), "{none}");
        }
        stub.abort();
    }

    /// A DNS answer to `query`: its TXT records in `records`, or NXDOMAIN.
    fn stub_answer(query: &[u8], records: &HashMap<&str, Vec<&str>>) -> Vec<u8> {
        let mut at = 12;
        let mut labels = Vec::new();
        while query[at] != 0 {
            let len = usize::from(query[at]);
            labels.push(String::from_utf8_lossy(&query[at + 1..at + 1 + len]).to_lowercase());
            at += 1 + len;
        }
        let question = &query[12..at + 5];
        let texts = records.get(labels.join(".").as_str());
        let mut out = query[..2].to_vec();
        out.extend(if texts.is_some() {
            [0x81, 0x80]
        } else {
            [0x81, 0x83]
        });
        let count = texts.map_or(0, Vec::len) as u16;
        out.extend([0, 1]);
        out.extend(count.to_be_bytes());
        out.extend([0, 0, 0, 0]);
        out.extend(question);
        for t in texts.into_iter().flatten() {
            out.extend([0xc0, 12, 0, 16, 0, 1, 0, 0, 0, 60]);
            out.extend(((t.len() + 1) as u16).to_be_bytes());
            out.push(t.len() as u8);
            out.extend(t.as_bytes());
        }
        out
    }
}