kcode_k1_web_cache_resolution/

lib.rs

use kcode_k1_transaction_id::TxId;
use kcode_k1_web_package::{
    AuthorityId, DependencySelector, SourceFile, SourcePackage, WebFamily, WebId,
};
use semver::Version;
use sha2::{Digest as _, Sha256};
use std::collections::{BTreeMap, BTreeSet};
use std::fs;
use std::path::Path;
use std::sync::Arc;
use walkdir::WalkDir;

#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct Digest(pub [u8; 32]);

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct ResolutionEntry {
    pub family: WebFamily,
    pub selector: DependencySelector,
    pub resolved: WebId,
    pub winning: TxId,
}

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct ResolutionView {
    entries: Vec<ResolutionEntry>,
    packages: Vec<Arc<SourcePackage>>,
    manifest: Vec<u8>,
    digest: Digest,
}

struct ManifestRoute {
    family: WebFamily,
    selector: DependencySelector,
    resolved: WebId,
    winning: TxId,
}

impl ResolutionView {
    pub fn from_snapshot(
        candidate: &SourcePackage,
        mut selected: Vec<(ResolutionEntry, Arc<SourcePackage>)>,
    ) -> Result<Self, String> {
        selected.sort_by(|a, b| route_key(&a.0).cmp(&route_key(&b.0)));
        if selected
            .windows(2)
            .any(|pair| route_key(&pair[0].0) == route_key(&pair[1].0))
        {
            return Err("duplicate resolution route".into());
        }
        validate_routes(candidate, &selected)?;
        let packages = selected_packages(&selected)?;
        let entries = selected.into_iter().map(|item| item.0).collect::<Vec<_>>();
        let manifest = encode_manifest(&entries, &packages);
        let digest = prepared_digest(&manifest, &packages);
        Ok(Self {
            entries,
            packages,
            manifest,
            digest,
        })
    }

    pub fn entries(&self) -> &[ResolutionEntry] {
        &self.entries
    }

    pub fn route(
        &self,
        family: &WebFamily,
        selector: &DependencySelector,
    ) -> Option<&ResolutionEntry> {
        self.entries
            .iter()
            .find(|entry| &entry.family == family && &entry.selector == selector)
    }

    pub const fn digest(&self) -> Digest {
        self.digest
    }

    pub fn materialize(&self, empty_root: impl AsRef<Path>) -> Result<(), String> {
        let root = empty_root.as_ref();
        directory(root)?;
        if fs::read_dir(root)
            .map_err(|error| error.to_string())?
            .next()
            .is_some()
        {
            return Err("resolution target is not empty".into());
        }
        fs::write(root.join("manifest"), &self.manifest).map_err(|error| error.to_string())?;
        let web_libs = root.join("web-libs");
        fs::create_dir(&web_libs).map_err(|error| error.to_string())?;
        for package in &self.packages {
            let id = package.id();
            let package_root = web_libs
                .join(id.family().authority().to_string())
                .join(id.family().logical_name())
                .join(id.version().to_string());
            write_files(&package_root, package.files())?;
        }
        if Self::inspect(root)? != Some(self.digest) {
            return Err("materialized view mismatch".into());
        }
        Ok(())
    }

    pub fn inspect(root: impl AsRef<Path>) -> Result<Option<Digest>, String> {
        let root = root.as_ref();
        directory(root)?;
        let mut files = Vec::new();
        let (mut manifest, mut web_libs) = (None, false);
        for entry in WalkDir::new(root).min_depth(1).sort_by_file_name() {
            let entry = entry.map_err(|error| error.to_string())?;
            let relative = entry
                .path()
                .strip_prefix(root)
                .map_err(|error| error.to_string())?;
            let depth = relative.components().count();
            if !(entry.file_type().is_file() || entry.file_type().is_dir()) {
                return Err("non-ordinary resolution entry".into());
            }
            if depth == 1 && entry.file_type().is_file() && entry.file_name() == "manifest" {
                manifest = Some(fs::read(entry.path()).map_err(|error| error.to_string())?);
            } else if depth == 1 && entry.file_type().is_dir() && entry.file_name() == "web-libs" {
                web_libs = true;
            } else if relative.starts_with("web-libs") && entry.file_type().is_file() && depth >= 5
            {
                let path = relative
                    .to_str()
                    .ok_or("resolution path is not UTF-8")?
                    .replace('\\', "/");
                if !safe_path(&path) {
                    return Err("unsafe resolution path".into());
                }
                files.push((
                    path,
                    fs::read(entry.path()).map_err(|error| error.to_string())?,
                ));
            } else if relative.starts_with("web-libs") && entry.file_type().is_dir() {
                if fs::read_dir(entry.path())
                    .map_err(|error| error.to_string())?
                    .next()
                    .is_none()
                {
                    return Err("empty resolution directory".into());
                }
            } else {
                return Err("unexpected resolution entry".into());
            }
        }
        if manifest.is_none() && !web_libs && files.is_empty() {
            return Ok(None);
        }
        let manifest = manifest.ok_or("incomplete resolution view")?;
        if !web_libs {
            return Err("incomplete resolution view".into());
        }
        validate_manifest(&manifest, &files)?;
        files.push(("manifest".into(), manifest));
        files.sort_by(|a, b| a.0.cmp(&b.0));
        Ok(Some(digest_files(
            files
                .iter()
                .map(|item| (item.0.as_str(), item.1.as_slice())),
        )))
    }
}

fn validate_routes(
    candidate: &SourcePackage,
    selected: &[(ResolutionEntry, Arc<SourcePackage>)],
) -> Result<(), String> {
    for (entry, package) in selected {
        if entry.resolved.family() != &entry.family
            || !entry.selector.matches(entry.resolved.version())
            || package.id() != &entry.resolved
        {
            return Err("resolution route does not match its package".into());
        }
    }
    let mut pending = dependency_keys(candidate)?;
    let mut reached = BTreeSet::new();
    while let Some(key) = pending.pop() {
        if !reached.insert(key.clone()) {
            continue;
        }
        let index = selected
            .binary_search_by(|item| route_key(&item.0).cmp(&(&key.0, &key.1)))
            .map_err(|_| "resolution closure is incomplete")?;
        pending.extend(dependency_keys(selected[index].1.as_ref())?);
    }
    let actual = selected
        .iter()
        .map(|item| (item.0.family.clone(), item.0.selector.clone()))
        .collect::<BTreeSet<_>>();
    if actual != reached {
        return Err("resolution contains an unrelated route".into());
    }
    Ok(())
}

fn selected_packages(
    selected: &[(ResolutionEntry, Arc<SourcePackage>)],
) -> Result<Vec<Arc<SourcePackage>>, String> {
    let mut packages = selected
        .iter()
        .map(|(entry, package)| (entry.resolved.clone(), entry.winning, Arc::clone(package)))
        .collect::<Vec<_>>();
    packages.sort_by(|a, b| a.0.cmp(&b.0));
    if packages.windows(2).any(|pair| {
        pair[0].0 == pair[1].0 && (pair[0].1 != pair[1].1 || pair[0].2.files() != pair[1].2.files())
    }) {
        return Err("one resolved identity has differing winner or bytes".into());
    }
    packages.dedup_by(|a, b| a.0 == b.0);
    Ok(packages.into_iter().map(|item| item.2).collect())
}

fn dependency_keys(
    package: &SourcePackage,
) -> Result<Vec<(WebFamily, DependencySelector)>, String> {
    package
        .dependencies()
        .iter()
        .map(|dependency| {
            WebFamily::new(dependency.authority(), dependency.name().to_owned())
                .map(|family| (family, dependency.selector().clone()))
                .map_err(|error| error.to_string())
        })
        .collect()
}

fn route_key(entry: &ResolutionEntry) -> (&WebFamily, &DependencySelector) {
    (&entry.family, &entry.selector)
}

fn encode_manifest(entries: &[ResolutionEntry], packages: &[Arc<SourcePackage>]) -> Vec<u8> {
    let mut rows = entries
        .iter()
        .map(|entry| {
            format!(
                "r\t{}\t{}\t{}\t{}\t{}",
                entry.family.authority(),
                entry.family.logical_name(),
                entry.selector,
                entry.resolved.version(),
                entry.winning
            )
        })
        .collect::<Vec<_>>();
    for (path, bytes) in package_files(packages) {
        rows.push(format!("f\t{path}\t{}", hex(&hash(&bytes))));
    }
    rows.sort();
    let mut text = String::from("K1WEBRESOLUTION3\n");
    for row in rows {
        text.push_str(&row);
        text.push('\n');
    }
    text.into_bytes()
}

fn package_files(packages: &[Arc<SourcePackage>]) -> Vec<(String, Vec<u8>)> {
    let mut files = Vec::new();
    for package in packages {
        let id = package.id();
        for file in package.files() {
            files.push((
                format!(
                    "web-libs/{}/{}/{}/{}",
                    id.family().authority(),
                    id.family().logical_name(),
                    id.version(),
                    file.path()
                ),
                file.bytes().to_vec(),
            ));
        }
    }
    files.sort_by(|a, b| a.0.cmp(&b.0));
    files
}

fn validate_manifest(manifest: &[u8], files: &[(String, Vec<u8>)]) -> Result<(), String> {
    if !manifest.ends_with(b"\n") {
        return Err("manifest is not canonically terminated".into());
    }
    let text = std::str::from_utf8(manifest).map_err(|_| "manifest is not UTF-8")?;
    let lines = text
        .strip_prefix("K1WEBRESOLUTION3\n")
        .ok_or("invalid manifest header")?
        .split_terminator('\n');
    let (mut previous, mut routes, mut resolved, mut expected) =
        (None, BTreeSet::new(), BTreeMap::new(), BTreeMap::new());
    for line in lines {
        if previous.is_some_and(|value| value >= line) {
            return Err("noncanonical manifest ordering".into());
        }
        previous = Some(line);
        let fields = line.split('\t').collect::<Vec<_>>();
        match fields.as_slice() {
            ["r", authority, name, selector, version, winner] => {
                let route = parse_route(authority, name, selector, version, winner)?;
                if !routes.insert((route.family, route.selector)) {
                    return Err("duplicate manifest route".into());
                }
                if let Some(old) = resolved.insert(route.resolved, route.winning)
                    && old != route.winning
                {
                    return Err("inconsistent manifest winner".into());
                }
            }
            ["f", path, digest] => {
                let (path, digest) = (*path, *digest);
                if !safe_path(path) || digest.len() != 64 || !digest.bytes().all(lower_hex) {
                    return Err("malformed manifest file".into());
                }
                if expected.insert(path, digest).is_some() {
                    return Err("duplicate manifest file".into());
                }
            }
            _ => return Err("malformed manifest record".into()),
        }
    }
    let resolved_ids = resolved.keys().cloned().collect::<BTreeSet<_>>();
    let manifested_ids = expected
        .keys()
        .map(|path| parse_path_id(path))
        .collect::<Result<BTreeSet<_>, _>>()?;
    if manifested_ids != resolved_ids {
        return Err("manifest package identity mismatch".into());
    }
    for (path, bytes) in files {
        let digest = expected
            .remove(path.as_str())
            .ok_or("manifest file mismatch")?;
        if digest != hex(&hash(bytes)) {
            return Err("manifest file mismatch".into());
        }
    }
    if !expected.is_empty() {
        return Err("missing manifest file".into());
    }
    Ok(())
}

fn parse_route(
    authority: &str,
    name: &str,
    selector: &str,
    version: &str,
    winner: &str,
) -> Result<ManifestRoute, String> {
    let resolved = parse_web_id(authority, name, version)?;
    let family = resolved.family().clone();
    let selector_value = DependencySelector::parse(selector).map_err(|error| error.to_string())?;
    if selector_value.to_string() != selector {
        return Err("noncanonical dependency selector".into());
    }
    if !selector_value.matches(resolved.version()) {
        return Err("route does not match resolved identity".into());
    }
    Ok(ManifestRoute {
        family,
        selector: selector_value,
        resolved,
        winning: parse_tx(winner)?,
    })
}

fn parse_path_id(path: &str) -> Result<WebId, String> {
    if !safe_path(path) {
        return Err("unsafe resolution path".into());
    }
    let parts = path.split('/').collect::<Vec<_>>();
    parse_web_id(parts[1], parts[2], parts[3])
}

fn parse_web_id(authority: &str, name: &str, version: &str) -> Result<WebId, String> {
    let family = WebFamily::new(AuthorityId::new(parse_tx(authority)?), name.to_owned())
        .map_err(|error| error.to_string())?;
    if family.logical_name() != name {
        return Err("noncanonical logical name".into());
    }
    let version_value = Version::parse(version).map_err(|error| error.to_string())?;
    if version_value.to_string() != version {
        return Err("noncanonical web version".into());
    }
    WebId::new(family, version_value).map_err(|error| error.to_string())
}

fn parse_tx(text: &str) -> Result<TxId, String> {
    if text.len() != 24 || !text.bytes().all(lower_hex) {
        return Err("noncanonical transaction ID".into());
    }
    let mut bytes = [0; 12];
    for (target, pair) in bytes.iter_mut().zip(text.as_bytes().chunks_exact(2)) {
        *target = (hex_value(pair[0]) << 4) | hex_value(pair[1]);
    }
    Ok(TxId::from_bytes(bytes))
}

fn lower_hex(byte: u8) -> bool {
    byte.is_ascii_digit() || (b'a'..=b'f').contains(&byte)
}
fn hex_value(byte: u8) -> u8 {
    if byte.is_ascii_digit() {
        byte - b'0'
    } else {
        byte - b'a' + 10
    }
}
fn hash(bytes: &[u8]) -> [u8; 32] {
    Sha256::digest(bytes).into()
}
fn hex(bytes: &[u8]) -> String {
    bytes.iter().map(|byte| format!("{byte:02x}")).collect()
}

fn prepared_digest(manifest: &[u8], packages: &[Arc<SourcePackage>]) -> Digest {
    let mut files = package_files(packages);
    files.push(("manifest".to_owned(), manifest.to_vec()));
    files.sort_by(|a, b| a.0.cmp(&b.0));
    digest_files(
        files
            .iter()
            .map(|item| (item.0.as_str(), item.1.as_slice())),
    )
}

fn digest_files<'a>(files: impl IntoIterator<Item = (&'a str, &'a [u8])>) -> Digest {
    let mut hasher = Sha256::new();
    append(&mut hasher, b"K1WEBVIEW1");
    for (path, bytes) in files {
        append(&mut hasher, path.as_bytes());
        append(&mut hasher, bytes);
    }
    Digest(hasher.finalize().into())
}

fn write_files(root: &Path, files: &[SourceFile]) -> Result<(), String> {
    for file in files {
        let target = root.join(file.path());
        fs::create_dir_all(target.parent().ok_or("source path has no parent")?)
            .map_err(|error| error.to_string())?;
        fs::write(target, file.bytes()).map_err(|error| error.to_string())?;
    }
    Ok(())
}

fn safe_path(path: &str) -> bool {
    let parts = path.split('/').collect::<Vec<_>>();
    parts.len() >= 5
        && parts[0] == "web-libs"
        && parts.iter().all(|part| {
            !part.is_empty() && !matches!(*part, "." | "..") && !part.contains([':', '\\', '\0'])
        })
}

fn directory(path: &Path) -> Result<(), String> {
    match fs::symlink_metadata(path) {
        Ok(value) if value.is_dir() && !value.file_type().is_symlink() => Ok(()),
        Ok(_) => Err(format!("unexpected path type: {}", path.display())),
        Err(cause) => Err(cause.to_string()),
    }
}

fn append(hasher: &mut Sha256, bytes: &[u8]) {
    hasher.update((bytes.len() as u64).to_le_bytes());
    hasher.update(bytes);
}