didbot_scope/

set.rs

//! A canonical set of atoms, and the intersection a ceiling is applied with.

use std::fmt;

use crate::read::read;
use crate::{
    NsidPattern, Scope, ScopeParseError, ScopeWarning, Transition, MAX_GRANT_ATOMS,
    MAX_GRANT_BYTES, MAX_SCOPE_ATOMS, MAX_SCOPE_BYTES,
};

/// A space-separated set of [`Scope`]s, as carried on a `scope` parameter or
/// a token response.
///
/// Canonical by construction: [`ScopeSet::new`] sorts, dedupes, and drops
/// any atom already admitted by another atom of its kind, so two sets
/// built from the same members in different orders — or with redundant
/// members — compare equal. Policy is a set of records in a repository,
/// which has no inherent order, so a ceiling has to be a function of the
/// rule set alone; a `ScopeSet` that could represent the same ceiling two
/// different ways would let vector order silently change what a policy
/// means, which is exactly the failure this type exists to rule out.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct ScopeSet(pub Vec<Scope>);

impl ScopeSet {
    /// Builds a canonical [`ScopeSet`] from a bag of atoms: sorted, deduped,
    /// and with every atom already admitted by another atom of its kind
    /// dropped. Containment among distinct atoms is a strict partial order —
    /// two distinct atoms can never admit each other — so which atom
    /// survives never depends on the input order.
    ///
    /// Only an atom of the same kind stands in for another. A ceiling judges
    /// each kind on its own ([`ScopeSet::narrow`]), and this server never
    /// grants a `transition:` scope, so `transition:generic` does not absorb
    /// the `repo:` scopes asked for beside it.
    pub fn new(atoms: Vec<Scope>) -> Self {
        let mut atoms = atoms;
        atoms.sort();
        atoms.dedup();
        let kept = atoms
            .iter()
            .enumerate()
            .filter(|(i, atom)| {
                !atoms.iter().enumerate().any(|(j, other)| {
                    j != *i && other.kind() == atom.kind() && other.contains(atom)
                })
            })
            .map(|(_, atom)| atom.clone())
            .collect();
        ScopeSet(kept)
    }

    /// Whether some atom of this set admits `wanted`, which is what a token
    /// carrying this set may do.
    pub fn covers(&self, wanted: &Scope) -> bool {
        self.0.iter().any(|atom| atom.contains(wanted))
    }

    /// Whether a token carrying this set may act at another service: call
    /// `lxm` there through `atproto-proxy`, or take a token for it from
    /// `com.atproto.server.getServiceAuth`. `aud` names the service, as a
    /// DID or a DID and a service fragment.
    ///
    /// `None` asks for a token bound to no method. An `rpc:*` scope for
    /// `aud` admits one, and so does `transition:generic`, as the reference
    /// PDS reads it.
    pub fn permits_rpc(&self, lxm: Option<&str>, aud: &str) -> bool {
        if lxm.is_none() && self.0.contains(&Scope::Transition(Transition::Generic)) {
            return true;
        }
        self.covers(&Scope::Rpc {
            method: lxm.map_or(NsidPattern::Any, |lxm| NsidPattern::Exact(lxm.to_owned())),
            aud: Some(aud.to_owned()),
        })
    }

    /// Parses a whole `scope` string: OAuth2's space-separated list of atoms.
    ///
    /// Checks [`MAX_SCOPE_BYTES`] before reading any atom, and
    /// [`MAX_SCOPE_ATOMS`] against the scopes they name. An atom this grammar
    /// cannot read is kept as [`Scope::Unknown`]; see [`ScopeSet::read`].
    pub fn parse(s: &str) -> Result<Self, ScopeParseError> {
        Self::read(s).map(|(set, _)| set)
    }

    /// Reads a scope an app asked for: the set, and each warning its atoms'
    /// forms carry, beside the atom as the app wrote it.
    ///
    /// Every form the permission spec defines reads without a warning. A form
    /// it does not define is read as well as it can be, with a warning
    /// saying how. An atom that names no scope this grammar reads is kept as
    /// [`Scope::Unknown`], with a warning, rather than failing the string: a
    /// server can drop it and grant the rest. Only the bounds and a character
    /// no scope may hold fail the whole string.
    pub fn read(s: &str) -> Result<(Self, Vec<(String, ScopeWarning)>), ScopeParseError> {
        Self::read_within(s, MAX_SCOPE_BYTES, MAX_SCOPE_ATOMS)
    }

    /// Parses a grant this server stored, which may be larger than any
    /// request: each `include:` in the request became the atoms its
    /// permission set grants.
    ///
    /// Checks [`MAX_GRANT_BYTES`] and [`MAX_GRANT_ATOMS`] before parsing any
    /// atom.
    pub fn parse_grant(s: &str) -> Result<Self, ScopeParseError> {
        Self::read_within(s, MAX_GRANT_BYTES, MAX_GRANT_ATOMS).map(|(set, _)| set)
    }

    fn read_within(
        s: &str,
        max_bytes: usize,
        max_scopes: usize,
    ) -> Result<(Self, Vec<(String, ScopeWarning)>), ScopeParseError> {
        if s.len() > max_bytes {
            return Err(ScopeParseError::TooLong {
                len: s.len(),
                max: max_bytes,
            });
        }
        // Every atom names at least one scope, so a string with too many atoms
        // is refused before any is read.
        let atoms: Vec<&str> = s.split_whitespace().collect();
        if atoms.len() > max_scopes {
            return Err(ScopeParseError::TooManyAtoms {
                count: atoms.len(),
                max: max_scopes,
            });
        }
        let mut scopes = Vec::new();
        let mut warnings = Vec::new();
        for atom in atoms {
            let read = match read(atom) {
                Ok(read) => read,
                Err(
                    error @ (ScopeParseError::AtomTooLong(_)
                    | ScopeParseError::ForbiddenCharacter(_)),
                ) => return Err(error),
                Err(error) => crate::read::Read {
                    scopes: vec![Scope::Unknown(atom.to_owned())],
                    warnings: vec![ScopeWarning::Unreadable(error.to_string())],
                },
            };
            scopes.extend(read.scopes);
            warnings.extend(
                read.warnings
                    .into_iter()
                    .map(|warning| (atom.to_owned(), warning)),
            );
        }
        if scopes.len() > max_scopes {
            return Err(ScopeParseError::TooManyAtoms {
                count: scopes.len(),
                max: max_scopes,
            });
        }
        Ok((ScopeSet::new(scopes), warnings))
    }

    /// Is every requested scope admitted by some scope in `ceiling`?
    ///
    /// Returns the whole intersected grant on success. On refusal, returns
    /// the first requested scope that no ceiling scope admits at all —
    /// `plan/scope-policy.md`'s "refuse rather than silently narrow, and say
    /// which scope", which needs this exact atom to build the
    /// `WWW-Authenticate: Bearer error="insufficient_scope", scope="…"`
    /// header.
    ///
    /// A requested atom's grant is the *union* of its overlap with every
    /// ceiling atom, not the single largest overlap: `ceiling` is a set with
    /// no inherent order, so a ceiling atom that grants `create` and one
    /// that grants `delete` must both survive regardless of which one this
    /// loop visits first. [`ScopeSet::new`] then collapses any overlap that
    /// one of its siblings already subsumes.
    ///
    /// An overlap counts only in the requested atom's own kind, as in
    /// [`ScopeSet::narrow`]: `transition:generic` under a `repo:*` ceiling is
    /// refused, not paid out as `repo:*`.
    pub fn intersect(&self, ceiling: &ScopeSet) -> Result<ScopeSet, ScopeRefused> {
        let mut granted = Vec::with_capacity(self.0.len());
        for requested in &self.0 {
            let mut admitted = false;
            for ceiling_scope in &ceiling.0 {
                let Some(overlap) = ceiling_scope.intersect(requested) else {
                    continue;
                };
                if overlap.kind() == requested.kind() {
                    granted.push(overlap);
                    admitted = true;
                }
            }
            if !admitted {
                return Err(ScopeRefused(requested.clone()));
            }
        }
        Ok(ScopeSet::new(granted))
    }

    /// The same overlap, split into what the ceiling granted and what it
    /// did not.
    ///
    /// [`ScopeSet::intersect`] refuses the whole request the moment one
    /// atom falls outside the ceiling, which is what `token` and every
    /// other caller checking a grant against a ceiling wants. A consent
    /// decision wants the other answer: the grant that *is* available, plus
    /// the part of the request it does not cover, so the record an agent
    /// approves can name both.
    ///
    /// Projection runs from the requested atom onto the ceiling and never
    /// the other way, and only ever within one kind: a granted atom is
    /// always a narrowing of something the request named, of that atom's own
    /// kind. So a wide atom is never paid out in capabilities of a kind
    /// nobody asked for — `transition:generic` overlaps `repo:*` and
    /// `rpc:*`, and a ceiling holding those grants it nothing.
    ///
    /// `cut` is every requested atom that no granted atom contains — the
    /// atoms the ceiling dropped outright and the atoms it shrank alike.
    /// The grammar has no difference operation, so an atom the ceiling
    /// narrowed (`repo:*?action=create&action=delete` against a ceiling holding
    /// `repo:*?action=create`) is named whole rather than as the sliver
    /// removed from it. An empty `cut` means the ceiling granted the
    /// request exactly as asked, which is the only case
    /// [`ScopeSet::intersect`] and this agree on completely.
    pub fn narrow(&self, ceiling: &ScopeSet) -> (ScopeSet, ScopeSet) {
        let mut overlaps = Vec::with_capacity(self.0.len());
        for requested in &self.0 {
            for ceiling_scope in &ceiling.0 {
                let Some(overlap) = requested.intersect(ceiling_scope) else {
                    continue;
                };
                // Same kind, or nothing. An overlap of a different variant
                // than the atom that was asked for is not a narrowing of
                // that atom, it is a *re-expression* of it as capabilities
                // the request never named: `transition:generic` overlaps
                // `repo:*` and `rpc:*`, and taking those would hand back a
                // grant nobody asked for in that form — a wide atom paid out
                // as its pieces. An atom whose every overlap is refused this
                // way is granted nothing and lands in `cut`.
                if overlap.kind() == requested.kind() {
                    overlaps.push(overlap);
                }
            }
        }
        let granted = ScopeSet::new(overlaps);
        let cut = ScopeSet::new(
            self.0
                .iter()
                .filter(|requested| !granted.0.iter().any(|atom| atom.contains(requested)))
                .cloned()
                .collect(),
        );
        (granted, cut)
    }
}

/// The exact scope a ceiling refused, for `insufficient_scope`.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[error("scope `{0}` is outside this agent's ceiling")]
pub struct ScopeRefused(pub Scope);

impl fmt::Display for ScopeSet {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let joined = self
            .0
            .iter()
            .map(ToString::to_string)
            .collect::<Vec<_>>()
            .join(" ");
        write!(f, "{joined}")
    }
}