kcode_k1_web_cache_resolution/

lib.rs

use kcode_k1_transaction_id::TxId;
use kcode_k1_web_package::{DependencySelector, SourceFile, SourcePackage, WebFamily, WebId};
use sha2::{Digest as _, Sha256};
use std::collections::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,
}

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(|e| e.to_string())?
            .next()
            .is_some()
        {
            return Err("resolution target is not empty".into());
        }
        fs::write(root.join("manifest"), &self.manifest).map_err(|e| e.to_string())?;
        let web_libs = root.join("web-libs");
        fs::create_dir(&web_libs).map_err(|e| e.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(|e| e.to_string())?;
            let relative = entry.path().strip_prefix(root).map_err(|e| e.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(|e| e.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(|e| e.to_string())?));
            } else if relative.starts_with("web-libs") && entry.file_type().is_dir() {
                if fs::read_dir(entry.path())
                    .map_err(|e| e.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: BTreeSet<_> = selected
        .iter()
        .map(|item| (item.0.family.clone(), item.0.selector.clone()))
        .collect();
    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(|e| e.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> {
    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 rows = Vec::new();
    let mut routes = BTreeSet::new();
    let mut winners = BTreeSet::new();
    let mut expected = BTreeSet::new();
    for line in lines {
        let fields = line.split('\t').collect::<Vec<_>>();
        match fields.as_slice() {
            ["r", authority, name, selector, version, winner]
                if fields[1..].iter().all(component) =>
            {
                if !routes.insert((*authority, *name, *selector)) {
                    return Err("duplicate manifest route".into());
                }
                winners.insert(((*authority, *name, *version), *winner));
                rows.push(line);
            }
            ["f", path, digest]
                if safe_path(path)
                    && digest.len() == 64
                    && digest
                        .bytes()
                        .all(|byte| byte.is_ascii_hexdigit() && !byte.is_ascii_uppercase()) =>
            {
                if !expected.insert(format!("{path}\t{digest}")) {
                    return Err("duplicate manifest file".into());
                }
                rows.push(line);
            }
            _ => return Err("malformed manifest record".into()),
        }
    }
    if rows.is_empty() || rows.windows(2).any(|pair| pair[0] >= pair[1]) {
        return Err("noncanonical manifest".into());
    }
    for (identity, winner) in &winners {
        if winners
            .iter()
            .any(|(other, value)| other == identity && value != winner)
        {
            return Err("inconsistent manifest winner".into());
        }
    }
    for (path, bytes) in files {
        if !expected.remove(&format!("{path}\t{}", hex(&hash(bytes)))) {
            return Err("manifest file mismatch".into());
        }
    }
    if !expected.is_empty() {
        return Err("missing manifest file".into());
    }
    for (path, _) in files {
        let parts = path.split('/').collect::<Vec<_>>();
        if !winners.iter().any(|((authority, name, version), _)| {
            *authority == parts[1] && *name == parts[2] && *version == parts[3]
        }) {
            return Err("file has no resolved manifest identity".into());
        }
    }
    Ok(())
}
fn component(value: &&str) -> bool {
    !value.is_empty() && !value.contains(['\t', '\n', '\r'])
}
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(|e| e.to_string())?;
        fs::write(target, file.bytes()).map_err(|e| e.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);
}