blazingly-aasa 0.1.5

//! Evaluating a URL against a compiled document.
//!
//! The result says what the *document* considers eligible. It deliberately does not claim what a
//! device will do: that also depends on whether the app is installed, what its Associated Domains
//! entitlement says, what Apple's CDN currently serves, and how the user got to the link.
//!
//! There are two entry points. [`CompiledAasa::decide`] answers the question and allocates almost
//! nothing. [`CompiledAasa::match_url`] answers it and builds a full [`MatchTrace`], which costs a
//! string per compared component. Use the first in a hot loop and the second when a human needs to
//! understand the answer.

use crate::compile::{CompiledAasa, CompiledPath, CompiledQuery, CompiledRule};
use crate::error::UrlError;
use crate::explain::{
    ComponentReason, ComponentTrace, DetailTrace, MatchDecision, MatchResult, MatchTrace,
    RuleTrace, StopReason, UrlComponent,
};
use crate::model::EffectiveDefaults;
use crate::pattern::{str_eq, Pattern, Shape};
use crate::url::{percent_decode, UrlParts};

/// Query items, either borrowed straight out of the URL or owned after percent-decoding.
#[derive(Clone, Copy)]
enum Items<'a> {
    Encoded(&'a [(&'a str, &'a str)]),
    Decoded(&'a [(String, String)]),
}

impl<'a> Items<'a> {
    fn len(self) -> usize {
        match self {
            Self::Encoded(items) => items.len(),
            Self::Decoded(items) => items.len(),
        }
    }

    fn get(self, index: usize) -> (&'a str, &'a str) {
        match self {
            Self::Encoded(items) => items[index],
            Self::Decoded(items) => (items[index].0.as_str(), items[index].1.as_str()),
        }
    }
}

/// The percent-decoded forms, built only when some rule actually asks for them.
struct Decoded {
    path: String,
    /// Trailing slash run removed, computed once per match rather than once per rule.
    trimmed: String,
    /// The trimmed path without its leading slash, when it has one.
    bare: Option<String>,
    query: String,
    fragment: String,
    items: Vec<(String, String)>,
}

/// The URL components a rule can be compared against.
struct Inputs<'a> {
    path: &'a str,
    /// Trailing slash run removed. Precomputed: a rule loop that trims the path per rule spends
    /// more time scanning the same string than it does matching.
    trimmed: &'a str,
    /// The trimmed path without its leading slash, for the rare pattern that lacks one.
    bare: Option<&'a str>,
    query: &'a str,
    fragment: &'a str,
    items: Vec<(&'a str, &'a str)>,
    decoded: Option<Decoded>,
}

impl<'a> Inputs<'a> {
    fn new(parts: &UrlParts<'a>, needs_decoded: bool, needs_items: bool) -> Self {
        // A document that never uses a `?` dictionary never needs the query split at all.
        let items = if needs_items {
            parts.query_items()
        } else {
            Vec::new()
        };
        let decoded = needs_decoded.then(|| {
            let path = percent_decode(parts.path());
            let trimmed = crate::url::trim_path(&path).to_owned();
            let bare = crate::url::strip_leading_slash(&trimmed).map(str::to_owned);
            Decoded {
                path,
                trimmed,
                bare,
                query: percent_decode(parts.query()),
                fragment: percent_decode(parts.fragment()),
                items: items
                    .iter()
                    .map(|(name, value)| (percent_decode(name), percent_decode(value)))
                    .collect(),
            }
        });
        let trimmed = crate::url::trim_path(parts.path());
        Self {
            path: parts.path(),
            trimmed,
            bare: crate::url::strip_leading_slash(trimmed),
            query: parts.query(),
            fragment: parts.fragment(),
            items,
            decoded,
        }
    }

    fn path_for(&self, percent_encoded: bool) -> &str {
        match (percent_encoded, &self.decoded) {
            (false, Some(decoded)) => &decoded.path,
            _ => self.path,
        }
    }

    /// The path with any trailing slash run removed, which is the form patterns compare against.
    fn trimmed_path_for(&self, percent_encoded: bool) -> &str {
        match (percent_encoded, &self.decoded) {
            (false, Some(decoded)) => &decoded.trimmed,
            _ => self.trimmed,
        }
    }

    /// The same path without its leading slash, for the rare pattern that lacks one.
    fn bare_path_for(&self, percent_encoded: bool) -> Option<&str> {
        match (percent_encoded, &self.decoded) {
            (false, Some(decoded)) => decoded.bare.as_deref(),
            _ => self.bare,
        }
    }

    fn query_for(&self, percent_encoded: bool) -> &str {
        match (percent_encoded, &self.decoded) {
            (false, Some(decoded)) => &decoded.query,
            _ => self.query,
        }
    }

    fn fragment_for(&self, percent_encoded: bool) -> &str {
        match (percent_encoded, &self.decoded) {
            (false, Some(decoded)) => &decoded.fragment,
            _ => self.fragment,
        }
    }

    fn items_for(&self, percent_encoded: bool) -> Items<'_> {
        match (percent_encoded, &self.decoded) {
            (false, Some(decoded)) => Items::Decoded(&decoded.items),
            _ => Items::Encoded(&self.items),
        }
    }
}

/// Everything the two evaluation paths need to agree on before rules are consulted.
enum Preflight {
    Proceed,
    Stop(StopReason),
}

fn preflight(aasa: &CompiledAasa, domain: &str, parts: &UrlParts<'_>) -> Preflight {
    if !domain.is_empty() && !domain.eq_ignore_ascii_case(parts.host()) {
        return Preflight::Stop(StopReason::HostMismatch {
            expected: domain.to_owned(),
            actual: parts.host().to_owned(),
        });
    }
    if !aasa.has_applinks {
        return Preflight::Stop(StopReason::NoAppLinksSection);
    }
    Preflight::Proceed
}

fn context_notes(parts: &UrlParts<'_>) -> Vec<String> {
    let mut notes = Vec::new();
    if parts.scheme() != "https" {
        notes.push(format!(
            "the URL scheme is `{}`; Apple serves and matches universal links over https only",
            parts.scheme()
        ));
    }
    if let Some(port) = parts.port() {
        notes.push(format!(
            "the URL carries an explicit port ({port}); whether a port is allowed is decided by \
             the app's Associated Domains entitlement, not by this file"
        ));
    }
    notes
}

impl CompiledAasa {
    /// Decides whether this document lets `app_id` open `url` on `domain`, without building a
    /// trace.
    ///
    /// This is the hot-loop entry point: it walks the same rules as [`CompiledAasa::match_url`]
    /// and reaches the same conclusion, but allocates only what URL splitting requires.
    ///
    /// Pass an empty `domain` to skip the host check.
    ///
    /// # Errors
    ///
    /// Returns [`UrlError`] when `url` cannot be split into scheme, host, and path.
    pub fn decide(&self, domain: &str, app_id: &str, url: &str) -> Result<MatchDecision, UrlError> {
        let parts = UrlParts::parse(url)?;
        Ok(self.decide_parts(domain, app_id, &parts))
    }

    /// The same decision, for a URL that has already been split.
    #[must_use]
    pub fn decide_parts(&self, domain: &str, app_id: &str, parts: &UrlParts<'_>) -> MatchDecision {
        if let Preflight::Stop(_) = preflight(self, domain, parts) {
            return MatchDecision::NoMatch;
        }
        let inputs = Inputs::new(parts, self.needs_decoded, self.needs_query_items);
        for detail in &self.details {
            if !detail.applies_to(app_id) {
                continue;
            }
            for rule in &detail.rules {
                if rule_matches(rule, &inputs) {
                    return if rule.exclude {
                        MatchDecision::Exclude
                    } else {
                        MatchDecision::Match
                    };
                }
            }
        }
        MatchDecision::NoMatch
    }

    /// Every app this document would let open `url`, in document order.
    ///
    /// The inverse of [`CompiledAasa::decide`]: instead of asking about one app, ask which apps a
    /// URL reaches. A domain owner auditing "who can open `/buy/*`?" wants this, and answering it
    /// by looping [`CompiledAasa::decide`] over every app would rescan the rules once per app.
    ///
    /// Apps whose verdict is [`MatchDecision::NoMatch`] are omitted, so an empty result means no
    /// app claims the URL. An app that appears in several `details` entries takes its verdict from
    /// the first entry that matched, which is the same rule [`CompiledAasa::decide`] follows.
    ///
    /// # Errors
    ///
    /// Returns [`UrlError`] when `url` cannot be split into scheme, host, and path.
    pub fn apps_for_url(
        &self,
        domain: &str,
        url: &str,
    ) -> Result<Vec<(String, MatchDecision)>, UrlError> {
        let parts = UrlParts::parse(url)?;
        Ok(self.apps_for_url_parts(domain, &parts))
    }

    /// The same, for a URL that has already been split.
    #[must_use]
    pub fn apps_for_url_parts(
        &self,
        domain: &str,
        parts: &UrlParts<'_>,
    ) -> Vec<(String, MatchDecision)> {
        let mut found: Vec<(String, MatchDecision)> = Vec::new();
        if let Preflight::Stop(_) = preflight(self, domain, parts) {
            return found;
        }
        let inputs = Inputs::new(parts, self.needs_decoded, self.needs_query_items);

        for detail in &self.details {
            let Some(rule) = detail.rules.iter().find(|rule| rule_matches(rule, &inputs)) else {
                continue;
            };
            let decision = if rule.exclude {
                MatchDecision::Exclude
            } else {
                MatchDecision::Match
            };
            for app_id in &detail.app_ids {
                if !found.iter().any(|(existing, _)| existing == app_id) {
                    found.push((app_id.clone(), decision));
                }
            }
        }
        found
    }

    /// Decides, and records why.
    ///
    /// Pass an empty `domain` to skip the host check, for example when testing a file in
    /// isolation.
    ///
    /// # Errors
    ///
    /// Returns [`UrlError`] when `url` cannot be split into scheme, host, and path.
    pub fn match_url(
        &self,
        domain: &str,
        app_id: &str,
        url: &str,
    ) -> Result<MatchResult, UrlError> {
        let parts = UrlParts::parse(url)?;
        Ok(self.match_parts(domain, app_id, &parts, url))
    }

    /// The same, for a URL that has already been split. `url_text` is echoed into the result.
    #[must_use]
    pub fn match_parts(
        &self,
        domain: &str,
        app_id: &str,
        parts: &UrlParts<'_>,
        url_text: &str,
    ) -> MatchResult {
        let mut result = MatchResult {
            decision: MatchDecision::NoMatch,
            domain: domain.to_owned(),
            app_id: app_id.to_owned(),
            url: url_text.to_owned(),
            trace: MatchTrace {
                details: Vec::new(),
                selected_detail: None,
                selected_rule: None,
                stop_reason: StopReason::NoRuleMatched,
                closest_failure: None,
            },
            notes: context_notes(parts),
        };

        if let Preflight::Stop(reason) = preflight(self, domain, parts) {
            result.trace.stop_reason = reason;
            return result;
        }

        let inputs = Inputs::new(parts, self.needs_decoded, self.needs_query_items);
        let mut any_applicable = false;
        let mut closest: Option<RuleTrace> = None;

        'outer: for detail in &self.details {
            let applies = detail.applies_to(app_id);
            any_applicable |= applies;
            let mut detail_trace = DetailTrace {
                index: detail.index,
                app_ids: detail.app_ids.clone(),
                applies,
                rules: Vec::new(),
            };

            if applies {
                for rule in &detail.rules {
                    let trace = evaluate(rule, &inputs);
                    let matched = trace.matched;
                    if !matched {
                        // Keep the rule that got furthest. Ties keep the earlier rule, which is
                        // the one a reader will look at first.
                        let better = closest.as_ref().map_or(true, |current| {
                            trace.matched_component_count() > current.matched_component_count()
                        });
                        if better {
                            closest = Some(trace.clone());
                        }
                    }
                    detail_trace.rules.push(trace);
                    if matched {
                        result.decision = if rule.exclude {
                            MatchDecision::Exclude
                        } else {
                            MatchDecision::Match
                        };
                        result.trace.stop_reason = if rule.exclude {
                            StopReason::Excluded
                        } else {
                            StopReason::Matched
                        };
                        result.trace.selected_detail = Some(rule.detail_index);
                        result.trace.selected_rule = Some(rule.rule_index);
                        result.trace.details.push(detail_trace);
                        break 'outer;
                    }
                }
            }
            result.trace.details.push(detail_trace);
        }

        if result.decision == MatchDecision::NoMatch {
            result.trace.stop_reason = if any_applicable {
                StopReason::NoRuleMatched
            } else {
                StopReason::NoApplicableDetail
            };
            result.trace.closest_failure = closest;
        }
        result
    }
}

/// The trace-free evaluation. Short-circuits on the first failing component.
fn rule_matches(rule: &CompiledRule, inputs: &Inputs<'_>) -> bool {
    let effective = rule.effective;
    let case_sensitive = effective.case_sensitive;

    if let Some(path) = &rule.path {
        let trimmed = inputs.trimmed_path_for(effective.percent_encoded);
        let bare = inputs.bare_path_for(effective.percent_encoded);
        if !path.matches(trimmed, bare, case_sensitive) {
            return false;
        }
    }

    match &rule.query {
        // An ignored dictionary constrains nothing, exactly as swcutil treats it.
        None | Some(CompiledQuery::IgnoredDictionary(_)) => {}
        Some(CompiledQuery::Whole(pattern)) => {
            if !pattern.matches_with(inputs.query_for(effective.percent_encoded), case_sensitive) {
                return false;
            }
        }
        Some(CompiledQuery::Items(predicates)) => {
            let items = inputs.items_for(effective.percent_encoded);
            for (name, pattern) in predicates {
                if !query_item_matches(name, pattern, items, case_sensitive) {
                    return false;
                }
            }
        }
    }

    if let Some(pattern) = &rule.fragment {
        if !pattern.matches_with(
            inputs.fragment_for(effective.percent_encoded),
            case_sensitive,
        ) {
            return false;
        }
    }
    true
}

/// Whether the named query item satisfies `pattern`.
///
/// Two rules, both taken from `swcutil` rather than from the documentation, which says nothing
/// about either:
///
/// * An item the URL does not carry counts as present with an empty value. `{"b": "*"}` therefore
///   matches a URL with no `b` at all, while `{"b": "?*"}` does not.
/// * When a name repeats, **every** occurrence must match. `{"id": "42"}` does not match
///   `?id=7&id=42`, and `{"id": "7"}` does match `?id=7&id=7`.
fn query_item_matches(
    name: &str,
    pattern: &Pattern,
    items: Items<'_>,
    case_sensitive: bool,
) -> bool {
    let mut seen = false;
    for index in 0..items.len() {
        let (candidate, value) = items.get(index);
        if !str_eq(candidate, name, case_sensitive) {
            continue;
        }
        seen = true;
        if !pattern.matches_with(value, case_sensitive) {
            return false;
        }
    }
    if seen {
        return true;
    }
    pattern.matches_with("", case_sensitive)
}

fn evaluate(rule: &CompiledRule, inputs: &Inputs<'_>) -> RuleTrace {
    let effective = rule.effective;
    let mut components = Vec::new();

    components.push(compare_path(
        rule.path.as_ref(),
        inputs.path_for(effective.percent_encoded),
        inputs.trimmed_path_for(effective.percent_encoded),
        inputs.bare_path_for(effective.percent_encoded),
        effective,
    ));

    match &rule.query {
        None => components.push(compare(
            UrlComponent::Query,
            None,
            inputs.query_for(effective.percent_encoded),
            effective,
        )),
        Some(CompiledQuery::IgnoredDictionary(keys)) => {
            for name in keys {
                components.push(ComponentTrace {
                    component: UrlComponent::QueryItem(name.clone()),
                    pattern: None,
                    input: String::new(),
                    matched: true,
                    reason: ComponentReason::UnsupportedPredicate,
                });
            }
        }
        Some(CompiledQuery::Whole(pattern)) => components.push(compare(
            UrlComponent::Query,
            Some(pattern),
            inputs.query_for(effective.percent_encoded),
            effective,
        )),
        Some(CompiledQuery::Items(predicates)) => {
            let items = inputs.items_for(effective.percent_encoded);
            for (name, pattern) in predicates {
                components.push(compare_query_item(name, pattern, items, effective));
            }
        }
    }

    components.push(compare(
        UrlComponent::Fragment,
        rule.fragment.as_ref(),
        inputs.fragment_for(effective.percent_encoded),
        effective,
    ));

    let matched = components.iter().all(|component| component.matched);
    RuleTrace {
        detail_index: rule.detail_index,
        rule_index: rule.rule_index,
        legacy: rule.legacy,
        exclude: rule.exclude,
        comment: rule.comment.clone(),
        effective,
        components,
        matched,
    }
}

fn compare(
    component: UrlComponent,
    pattern: Option<&Pattern>,
    input: &str,
    effective: EffectiveDefaults,
) -> ComponentTrace {
    let Some(pattern) = pattern else {
        return ComponentTrace {
            component,
            pattern: None,
            input: input.to_owned(),
            matched: true,
            reason: ComponentReason::Unconstrained,
        };
    };
    let (matched, reason) = decide_component(pattern, input, effective.case_sensitive);
    ComponentTrace {
        component,
        pattern: Some(pattern.source().to_owned()),
        input: input.to_owned(),
        matched,
        reason,
    }
}

fn compare_query_item(
    name: &str,
    pattern: &Pattern,
    items: Items<'_>,
    effective: EffectiveDefaults,
) -> ComponentTrace {
    let component = UrlComponent::QueryItem(name.to_owned());
    let mut present: Vec<&str> = Vec::new();
    for index in 0..items.len() {
        let (candidate, value) = items.get(index);
        if str_eq(candidate, name, effective.case_sensitive) {
            present.push(value);
        }
    }

    // An item the URL does not carry counts as present with an empty value.
    if present.is_empty() {
        let (matched, reason) = decide_component(pattern, "", effective.case_sensitive);
        return ComponentTrace {
            component,
            pattern: Some(pattern.source().to_owned()),
            input: String::new(),
            matched,
            reason: if matched {
                reason
            } else {
                ComponentReason::MissingQueryItem
            },
        };
    }

    // Every occurrence of a repeated name must match.
    for value in &present {
        let (matched, reason) = decide_component(pattern, value, effective.case_sensitive);
        if !matched {
            return ComponentTrace {
                component,
                pattern: Some(pattern.source().to_owned()),
                input: (*value).to_owned(),
                matched: false,
                reason,
            };
        }
    }
    let (_, reason) = decide_component(pattern, present[0], effective.case_sensitive);
    ComponentTrace {
        component,
        pattern: Some(pattern.source().to_owned()),
        input: present.join(", "),
        matched: true,
        reason,
    }
}

/// Compares the path against every form Apple accepts, reporting the pattern as written.
fn compare_path(
    path_pattern: Option<&CompiledPath>,
    path: &str,
    trimmed: &str,
    bare: Option<&str>,
    effective: EffectiveDefaults,
) -> ComponentTrace {
    let Some(path_pattern) = path_pattern else {
        return ComponentTrace {
            component: UrlComponent::Path,
            pattern: None,
            input: path.to_owned(),
            matched: true,
            reason: ComponentReason::Unconstrained,
        };
    };
    let matched = path_pattern.matches(trimmed, bare, effective.case_sensitive);
    // Report the reason from the pattern as written, which is the one a reader recognises.
    let (_, reason) = decide_component(&path_pattern.pattern, trimmed, effective.case_sensitive);
    ComponentTrace {
        component: UrlComponent::Path,
        pattern: Some(path_pattern.source().to_owned()),
        input: path.to_owned(),
        matched,
        reason: if matched && reason == ComponentReason::PatternMismatch {
            // A parent-path or bare-path form matched where the primary did not.
            ComponentReason::Wildcard
        } else {
            reason
        },
    }
}

fn decide_component(
    pattern: &Pattern,
    input: &str,
    case_sensitive: bool,
) -> (bool, ComponentReason) {
    if pattern.matches_with(input, case_sensitive) {
        let reason = match pattern.shape() {
            Shape::Any | Shape::Wildcard => ComponentReason::Wildcard,
            Shape::Literal => ComponentReason::Exact,
            Shape::Substitution => ComponentReason::Substitution,
        };
        return (true, reason);
    }
    if case_sensitive && pattern.matches_with(input, false) {
        return (false, ComponentReason::CaseMismatch);
    }
    (false, ComponentReason::PatternMismatch)
}