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);
}