use super::{BlockError, Job, OneCopy, Refusal, Slots, Tracker};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FileMatch {
pub path: String,
pub line_number: u64,
pub line: String,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FileMeasure {
pub path: String,
pub lines: u64,
pub bytes: u64,
}
fn slurp(path: &str) -> Result<Vec<u8>, String> {
std::fs::read(path).map_err(|e| e.to_string())
}
pub(crate) fn without_cr(line: &[u8]) -> &[u8] {
match line.strip_suffix(b"\r") {
Some(trimmed) => trimmed,
None => line,
}
}
pub(crate) fn unterminated_tail(bytes: &[u8]) -> u64 {
match bytes.last() {
None => 0,
Some(&b'\n') => 0,
Some(_last) => 1,
}
}
fn contains(hay: &[u8], needle: &[u8]) -> bool {
if needle.is_empty() {
return true;
}
if needle.len() > hay.len() {
return false;
}
hay.windows(needle.len()).any(|w| w == needle)
}
fn matching_lines(hay: &[u8], needle: &[u8], ignore_case: bool) -> Vec<(u64, String)> {
let mut out = Vec::new();
if needle.is_empty() {
return out;
}
let folded_needle = if ignore_case {
needle.to_ascii_lowercase()
} else {
needle.to_vec()
};
for (idx, raw) in hay.split(|&b| b == b'\n').enumerate() {
let line = without_cr(raw);
let hit = if ignore_case {
contains(&line.to_ascii_lowercase(), &folded_needle)
} else {
contains(line, &folded_needle)
};
if hit {
out.push((idx as u64 + 1, String::from_utf8_lossy(line).into_owned()));
}
}
out
}
struct PerFile<'a, R> {
paths: &'a [String],
rows: Slots<Result<R, Refusal>>,
done: Vec<Result<R, Refusal>>,
tracker: Tracker,
}
impl<'a, R: Send + Sync> PerFile<'a, R> {
fn new(paths: &'a [String]) -> Self {
let n = paths.len();
Self {
paths,
rows: Slots::new(n),
done: Vec::new(),
tracker: Tracker::new((n > 0).then_some(n)),
}
}
fn run(
&self,
phase: usize,
block: usize,
work: impl Fn(&str) -> Result<R, String>,
) -> Result<(), BlockError> {
self.tracker.run(
phase,
block,
&OneCopy(|_phase, block| {
let path = &self.paths[block];
let row = work(path).map_err(|detail| Refusal::unreadable(path, detail));
self.rows.put(block, row);
}),
)
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.tracker.check_ended(phase)?;
self.done = self.rows.take_all()?;
self.tracker.advance(None);
Ok(())
}
fn finish(self) -> Result<Vec<Result<R, Refusal>>, Refusal> {
self.tracker.check_finished()?;
Ok(self.done)
}
}
pub struct SearchFileJob<'a> {
inner: PerFile<'a, Vec<FileMatch>>,
needle: Vec<u8>,
ignore_case: bool,
}
pub fn search_file<'a>(
pattern: &str,
paths: &'a [String],
ignore_case: bool,
) -> Result<SearchFileJob<'a>, Refusal> {
if pattern.is_empty() {
return Err(Refusal::argument("Pattern must not be empty"));
}
Ok(SearchFileJob {
inner: PerFile::new(paths),
needle: pattern.as_bytes().to_vec(),
ignore_case,
})
}
impl Job for SearchFileJob<'_> {
type Answer = Vec<Result<Vec<FileMatch>, Refusal>>;
fn blocks(&self, phase: usize) -> Option<usize> {
self.inner.tracker.blocks(phase)
}
fn state(&self, phase: usize, block: usize) -> Option<super::BlockState> {
self.inner.tracker.state(phase, block)
}
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError> {
self.inner.run(phase, block, |path| {
slurp(path).map(|bytes| {
matching_lines(&bytes, &self.needle, self.ignore_case)
.into_iter()
.map(|(line_number, line)| FileMatch {
path: path.to_string(),
line_number,
line,
})
.collect()
})
})
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.inner.end_phase(phase)
}
fn finish(self) -> Result<Self::Answer, Refusal> {
self.inner.finish()
}
}
pub struct FileLineJob<'a> {
inner: PerFile<'a, FileMeasure>,
}
pub fn file_line(paths: &[String]) -> FileLineJob<'_> {
FileLineJob {
inner: PerFile::new(paths),
}
}
impl Job for FileLineJob<'_> {
type Answer = Vec<Result<FileMeasure, Refusal>>;
fn blocks(&self, phase: usize) -> Option<usize> {
self.inner.tracker.blocks(phase)
}
fn state(&self, phase: usize, block: usize) -> Option<super::BlockState> {
self.inner.tracker.state(phase, block)
}
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError> {
self.inner.run(phase, block, |path| {
slurp(path).map(|bytes| {
let newlines = bytes.iter().filter(|&&b| b == b'\n').count() as u64;
FileMeasure {
path: path.to_string(),
lines: newlines + unterminated_tail(&bytes),
bytes: bytes.len() as u64,
}
})
})
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.inner.end_phase(phase)
}
fn finish(self) -> Result<Self::Answer, Refusal> {
self.inner.finish()
}
}
pub struct FileByteJob<'a> {
inner: PerFile<'a, FileMeasure>,
}
pub fn file_byte(paths: &[String]) -> FileByteJob<'_> {
FileByteJob {
inner: PerFile::new(paths),
}
}
impl Job for FileByteJob<'_> {
type Answer = Vec<Result<FileMeasure, Refusal>>;
fn blocks(&self, phase: usize) -> Option<usize> {
self.inner.tracker.blocks(phase)
}
fn state(&self, phase: usize, block: usize) -> Option<super::BlockState> {
self.inner.tracker.state(phase, block)
}
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError> {
self.inner.run(phase, block, |path| {
std::fs::metadata(path)
.map(|m| FileMeasure {
path: path.to_string(),
lines: 0,
bytes: m.len(),
})
.map_err(|e| e.to_string())
})
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.inner.end_phase(phase)
}
fn finish(self) -> Result<Self::Answer, Refusal> {
self.inner.finish()
}
}
#[cfg(feature = "verify-chain")]
pub use hashing::{
FileHash, FileHashCheckJob, FileHashJob, HashCheck, HashChecked, file_hash, file_hash_check,
file_hash_streamed,
};
#[cfg(feature = "verify-chain")]
mod hashing {
use blake3::hazmat::{
ChainingValue, HasherExt, Mode, left_subtree_len, merge_subtrees_non_root,
merge_subtrees_root,
};
use super::super::{BlockError, BlockState, Job, OneCopy, Refusal, Slots, Tracker};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FileHash {
pub path: String,
pub hash: String,
pub bytes: u64,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct HashCheck {
pub path: String,
pub expected: String,
pub actual: Option<String>,
pub is_match: bool,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct HashChecked {
pub check: HashCheck,
pub refusal: Option<Refusal>,
}
const FILE_CHUNK: usize = 1 << 20;
const MAX_IN_MEMORY: u64 = 1 << 30;
const SUBTREE_LEAF: usize = 1 << 20;
fn hex32(bytes: &[u8; 32]) -> String {
const DIGITS: &[u8; 16] = b"0123456789abcdef";
let mut s = String::with_capacity(64);
for b in bytes {
s.push(DIGITS[(b >> 4) as usize] as char);
s.push(DIGITS[(b & 0x0F) as usize] as char);
}
s
}
fn hash_file_streaming(path: &str) -> Result<(String, u64), String> {
use std::io::Read;
let file = std::fs::File::open(path).map_err(|e| e.to_string())?;
let mut reader = std::io::BufReader::new(file);
let mut hasher = blake3::Hasher::new();
let mut buf = vec![0u8; FILE_CHUNK];
let mut total = 0u64;
loop {
let got = reader.read(&mut buf).map_err(|e| e.to_string())?;
if got == 0 {
break;
}
hasher.update(&buf[..got]);
total += got as u64;
}
Ok((hex32(hasher.finalize().as_bytes()), total))
}
fn plan_subtrees(start: usize, len: usize, out: &mut Vec<(usize, usize)>) {
if len <= SUBTREE_LEAF || len <= blake3::CHUNK_LEN {
out.push((start, len));
return;
}
let left = left_subtree_len(len as u64) as usize;
plan_subtrees(start, left, out);
plan_subtrees(start + left, len - left, out);
}
fn fold_subtrees(len: usize, cvs: &[ChainingValue], next: &mut usize) -> ChainingValue {
if len <= SUBTREE_LEAF || len <= blake3::CHUNK_LEN {
let cv = cvs[*next];
*next += 1;
return cv;
}
let left = left_subtree_len(len as u64) as usize;
let l = fold_subtrees(left, cvs, next);
let r = fold_subtrees(len - left, cvs, next);
merge_subtrees_non_root(&l, &r, Mode::Hash)
}
pub fn file_hash_streamed(path: &str) -> Result<FileHash, Refusal> {
match hash_file_streaming(path) {
Ok((hash, bytes)) => Ok(FileHash {
path: path.to_string(),
hash,
bytes,
}),
Err(detail) => Err(Refusal::unreadable(path, detail)),
}
}
enum Loaded {
Answered(Result<(String, u64), String>),
Held(Vec<u8>),
}
pub struct FileHashJob<'a> {
paths: &'a [String],
streamed: Slots<Result<(String, u64), String>>,
read: Slots<Loaded>,
bytes: Vec<u8>,
spans: Vec<(usize, usize)>,
left_count: usize,
cvs: Slots<ChainingValue>,
answer: Vec<Result<(String, u64), String>>,
tracker: Tracker,
}
pub fn file_hash(paths: &[String]) -> FileHashJob<'_> {
let n = paths.len();
let one = n == 1;
FileHashJob {
paths,
streamed: Slots::new(if one { 0 } else { n }),
read: Slots::new(if one { 1 } else { 0 }),
bytes: Vec::new(),
spans: Vec::new(),
left_count: 0,
cvs: Slots::new(0),
answer: Vec::new(),
tracker: Tracker::new((n > 0).then_some(n)),
}
}
impl FileHashJob<'_> {
fn one_file(&self) -> bool {
self.paths.len() == 1
}
fn read_one(path: &str) -> Loaded {
let size = match std::fs::metadata(path) {
Ok(m) => m.len(),
Err(e) => return Loaded::Answered(Err(e.to_string())),
};
if size > MAX_IN_MEMORY {
return Loaded::Answered(hash_file_streaming(path));
}
match std::fs::read(path) {
Err(e) => Loaded::Answered(Err(e.to_string())),
Ok(bytes) if bytes.len() <= SUBTREE_LEAF => {
let len = bytes.len() as u64;
Loaded::Answered(Ok((hex32(blake3::hash(&bytes).as_bytes()), len)))
}
Ok(bytes) => Loaded::Held(bytes),
}
}
fn rows(&self) -> Vec<Result<FileHash, Refusal>> {
self.answer
.iter()
.zip(self.paths)
.map(|(row, path)| match row {
Ok((hash, bytes)) => Ok(FileHash {
path: path.clone(),
hash: hash.clone(),
bytes: *bytes,
}),
Err(detail) => Err(Refusal::unreadable(path, detail)),
})
.collect()
}
}
impl Job for FileHashJob<'_> {
type Answer = Vec<Result<FileHash, Refusal>>;
fn blocks(&self, phase: usize) -> Option<usize> {
self.tracker.blocks(phase)
}
fn state(&self, phase: usize, block: usize) -> Option<BlockState> {
self.tracker.state(phase, block)
}
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError> {
self.tracker.run(
phase,
block,
&OneCopy(|phase, block| {
if !self.one_file() {
self.streamed
.put(block, hash_file_streaming(&self.paths[block]));
} else if phase == 0 {
self.read.put(block, Self::read_one(&self.paths[0]));
} else {
let (start, len) = self.spans[block];
let cv = blake3::Hasher::new()
.set_input_offset(start as u64)
.update(&self.bytes[start..start + len])
.finalize_non_root();
self.cvs.put(block, cv);
}
}),
)
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.tracker.check_ended(phase)?;
if !self.one_file() {
self.answer = self.streamed.take_all()?;
self.tracker.advance(None);
return Ok(());
}
if phase == 0 {
let Some(read) = self.read.take_all()?.pop() else {
return Err(Refusal::internal("the read of the one file left no result"));
};
match read {
Loaded::Answered(row) => {
self.answer = vec![row];
self.tracker.advance(None);
}
Loaded::Held(bytes) => {
let n = bytes.len();
let left = left_subtree_len(n as u64) as usize;
let mut spans = Vec::new();
plan_subtrees(0, left, &mut spans);
self.left_count = spans.len();
plan_subtrees(left, n - left, &mut spans);
self.cvs = Slots::new(spans.len());
self.tracker.advance(Some(spans.len()));
self.spans = spans;
self.bytes = bytes;
}
}
return Ok(());
}
let cvs = self.cvs.take_all()?;
let n = self.bytes.len();
let left = left_subtree_len(n as u64) as usize;
let mut from_left = 0usize;
let lcv = fold_subtrees(left, &cvs[..self.left_count], &mut from_left);
let mut from_right = 0usize;
let rcv = fold_subtrees(n - left, &cvs[self.left_count..], &mut from_right);
let root = hex32(merge_subtrees_root(&lcv, &rcv, Mode::Hash).as_bytes());
self.answer = vec![Ok((root, n as u64))];
self.bytes = Vec::new();
self.tracker.advance(None);
Ok(())
}
fn finish(self) -> Result<Self::Answer, Refusal> {
self.tracker.check_finished()?;
Ok(self.rows())
}
}
pub struct FileHashCheckJob<'a> {
hashing: FileHashJob<'a>,
manifest: &'a [String],
}
pub fn file_hash_check<'a>(
paths: &'a [String],
manifest: &'a [String],
) -> Result<FileHashCheckJob<'a>, Refusal> {
if paths.len() != manifest.len() {
return Err(Refusal::argument(format!(
"Path has {} entr(ies) and Manifest has {}; each file needs exactly one expected \
root",
paths.len(),
manifest.len()
)));
}
Ok(FileHashCheckJob {
hashing: file_hash(paths),
manifest,
})
}
impl Job for FileHashCheckJob<'_> {
type Answer = Vec<HashChecked>;
fn blocks(&self, phase: usize) -> Option<usize> {
self.hashing.blocks(phase)
}
fn state(&self, phase: usize, block: usize) -> Option<BlockState> {
self.hashing.state(phase, block)
}
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError> {
self.hashing.run(phase, block)
}
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal> {
self.hashing.end_phase(phase)
}
fn finish(self) -> Result<Self::Answer, Refusal> {
let manifest = self.manifest;
let paths = self.hashing.paths;
let rows = self.hashing.finish()?;
Ok(rows
.into_iter()
.zip(manifest)
.zip(paths)
.map(|((row, expected), path)| {
let expected = expected.to_ascii_lowercase();
match row {
Ok(found) => {
let is_match = found.hash == expected;
HashChecked {
check: HashCheck {
path: path.clone(),
expected,
actual: Some(found.hash),
is_match,
},
refusal: None,
}
}
Err(refusal) => HashChecked {
check: HashCheck {
path: path.clone(),
expected,
actual: None,
is_match: false,
},
refusal: Some(refusal),
},
}
})
.collect())
}
}
#[cfg(test)]
mod tests {
use super::super::super::{drive_serial, simd};
use super::*;
fn scratch(name: &str, bytes: &[u8]) -> String {
let dir = std::env::temp_dir().join(format!(
"flynnel-kernels-hash-{}-{name}",
std::process::id()
));
std::fs::create_dir_all(&dir).expect("a scratch directory");
let path = dir.join("input.bin");
std::fs::write(&path, bytes).expect("the scratch file is written");
path.to_string_lossy().into_owned()
}
#[test]
fn one_large_file_hashes_to_the_standard_root_through_its_subtrees() {
let bytes: Vec<u8> = (0..5_000_000u32).map(|i| (i * 31 % 251) as u8).collect();
let path = scratch("large", &bytes);
let paths = vec![path];
let rows = drive_serial(file_hash(&paths)).expect("finishes");
let row = rows[0].as_ref().expect("the file reads");
assert_eq!(row.hash, blake3::hash(&bytes).to_hex().to_string());
assert_eq!(row.bytes, 5_000_000);
}
#[test]
fn an_unreadable_file_is_a_row_naming_it() {
let good = scratch("good", b"abc");
let paths = vec![good, "no-such-file-for-flynnel-kernels".to_string()];
let rows = drive_serial(file_hash(&paths)).expect("finishes");
assert_eq!(
rows[0].as_ref().expect("the good file reads").hash,
blake3::hash(b"abc").to_hex().to_string()
);
let refused = rows[1].as_ref().expect_err("the missing file is refused");
assert!(
refused
.message
.starts_with("no-such-file-for-flynnel-kernels could not be read: ")
);
let manifest = vec![
blake3::hash(b"abc").to_hex().to_uppercase(),
"00".to_string(),
];
let checked = drive_serial(file_hash_check(&paths, &manifest).expect("lengths"))
.expect("finishes");
assert!(checked[0].check.is_match);
assert!(!checked[1].check.is_match);
assert_eq!(checked[1].check.actual, None);
assert!(checked[1].refusal.is_some());
}
#[test]
fn a_hash_answers_the_same_at_every_level() {
let bytes: Vec<u8> = (0..3_000_000u32).map(|i| (i * 31 % 251) as u8).collect();
let paths = vec![scratch("levels", &bytes)];
simd::assert_every_level_agrees("hash", || {
drive_serial(file_hash(&paths)).expect("finishes")
});
}
}
}
#[cfg(test)]
mod tests {
use super::super::{drive_serial, simd};
use super::*;
fn scratch(name: &str, bytes: &[u8]) -> String {
let dir = std::env::temp_dir().join(format!(
"flynnel-kernels-files-{}-{name}",
std::process::id()
));
std::fs::create_dir_all(&dir).expect("a scratch directory");
let path = dir.join("input.txt");
std::fs::write(&path, bytes).expect("the scratch file is written");
path.to_string_lossy().into_owned()
}
#[test]
fn lines_bytes_and_matches_answer_per_file_in_path_order() {
let a = scratch("a", b"one\r\nTwo panic\nthree");
let b = scratch("b", b"panic\n");
let paths = vec![a.clone(), "missing-file-for-flynnel".to_string(), b.clone()];
let lines = drive_serial(file_line(&paths)).expect("finishes");
assert_eq!(lines[0].as_ref().expect("a reads").lines, 3);
assert_eq!(lines[2].as_ref().expect("b reads").lines, 1);
assert!(lines[1].is_err());
let bytes = drive_serial(file_byte(&paths)).expect("finishes");
assert_eq!(bytes[0].as_ref().expect("a reads").bytes, 20);
assert_eq!(bytes[0].as_ref().expect("a reads").lines, 0);
let found =
drive_serial(search_file("PANIC", &paths, true).expect("a pattern")).expect("finishes");
let in_a = found[0].as_ref().expect("a reads");
assert_eq!(in_a.len(), 1);
assert_eq!(in_a[0].line_number, 2);
assert_eq!(in_a[0].line, "Two panic");
assert_eq!(found[2].as_ref().expect("b reads").len(), 1);
let exact = drive_serial(search_file("PANIC", &paths, false).expect("a pattern"))
.expect("finishes");
assert!(exact[0].as_ref().expect("a reads").is_empty());
assert_eq!(
search_file("", &paths, false)
.err()
.map(|r| r.message)
.as_deref(),
Some("Pattern must not be empty")
);
}
#[test]
fn every_kernel_answers_the_baseline_s_bits_at_every_level() {
let mut text = String::new();
let mut i = 0u64;
while text.len() < 400_000 {
text.push_str(&format!("line {i} with panic and PANIC in it\r\n"));
i += 1;
}
let a = scratch("levels-a", text.as_bytes());
let b = scratch("levels-b", b"panic\n");
let paths = vec![a, "missing-file-for-flynnel".to_string(), b];
simd::assert_every_level_agrees("lines", || {
drive_serial(file_line(&paths)).expect("finishes")
});
simd::assert_every_level_agrees("bytes", || {
drive_serial(file_byte(&paths)).expect("finishes")
});
for ignore_case in [true, false] {
simd::assert_every_level_agrees(&format!("search ignore_case={ignore_case}"), || {
drive_serial(search_file("PANIC", &paths, ignore_case).expect("a pattern"))
.expect("finishes")
});
}
}
}