tree.v

1//! Walking the working tree: ignore rules, hashing, and the file cache.23module snapshot45import encoding.utf86import os7import time8import src.storage910// FAT filesystems keep mtime in 2-second steps; three covers them too.11const racy_window_ns = i64(3_000_000_000)1213// One tracked file in one tree.14pub struct FileEntry {15pub:16	path       string17	hash       string18	size       i6419	executable bool20}2122pub struct WalkReport {23pub:24	files        []FileEntry25	unsafe_paths []string26}2728// legal_path is the one rule for every path Koh saves, receives or restores.29pub fn legal_path(path string) bool {30	if path == '' || path.starts_with('/') || path.contains('\\') || !utf8.validate_str(path) {31		return false32	}33	if path.split('/').any(it in ['', '.', '..']) {34		return false35	}36	bytes := path.bytes()37	for i, byte in bytes {38		if byte < 0x20 || byte == 0x7f || (byte == 0xc2 && i + 1 < bytes.len39			&& bytes[i + 1] >= 0x80 && bytes[i + 1] <= 0x9f) {40			return false41		}42	}43	return true44}4546// escape_path makes unsafe names printable without letting controls affect the terminal.47pub fn escape_path(path string) string {48	mut escaped := ''49	bytes := path.bytes()50	mut i := 051	for i < bytes.len {52		byte := bytes[i]53		if byte == `\\` {54			escaped += '\\\\'55		} else if byte < 0x20 || byte == 0x7f {56			escaped += '\\x${byte.hex()}'57		} else if byte == 0xc2 && i + 1 < bytes.len && bytes[i + 1] >= 0x8058			&& bytes[i + 1] <= 0x9f {59			escaped += '\\u00${bytes[i + 1].hex()}'60			i++61		} else if byte >= 0x80 {62			// A whole valid sequence prints as itself; any other byte is escaped alone.63			n := utf8_char_len(byte)64			if n > 1 && i + n <= bytes.len && utf8.validate_str(bytes[i..i + n].bytestr()) {65				escaped += bytes[i..i + n].bytestr()66				i += n67				continue68			}69			escaped += '\\x${byte.hex()}'70		} else {71			escaped += byte.ascii_str()72		}73		i++74	}75	return escaped76}7778// Counted hears how far a long step has come; `total` is 0 when it is not known.79pub type Counted = fn (done int, total int)8081// Hashing counts the files a walk has to read and hash (a cached one costs82// nothing), and tells `on` each time, when there is an `on`.83pub struct Hashing {84pub:85	on Counted = unsafe { nil }86mut:87	count int88}8990// walk hashes every tracked file under `root` and returns them sorted by path.91// Symlinks are skipped, as Koh 2 skipped them, so migration stays lossless.92pub fn walk(store &storage.Store, root string, ig Ignore) ![]FileEntry {93	mut quiet := Hashing{}94	return walk_report(store, root, ig, mut quiet)!.files95}9697pub fn walk_report(store &storage.Store, root string, ig Ignore, mut hashing Hashing) !WalkReport {98	cache := store.load_cache()!99	mut entries := []FileEntry{}100	mut fresh := []storage.CacheRow{}101	mut unsafe_paths := []string{}102	walk_dir(root, '', ig.banning(store.stripped_paths()!), cache, mut entries, mut fresh,103		mut unsafe_paths, mut hashing)!104	// Skipped while another command writes, or inside a caller's transaction:105	// the next walk hashes those files again, which is all a missing row costs.106	store.save_cache_rows(fresh) or {}107	entries.sort(a.path < b.path)108	unsafe_paths.sort()109	return WalkReport{110		files:        entries111		unsafe_paths: unsafe_paths112	}113}114115// walk_raw hashes the same files without a store: no cache, nothing written.116// `migrate` uses it to check a working tree against a manifest before it has a117// database to check it with.118pub fn walk_raw(root string, ig Ignore) ![]FileEntry {119	mut entries := []FileEntry{}120	mut unused := []storage.CacheRow{}121	mut unsafe_paths := []string{}122	mut quiet := Hashing{}123	walk_dir(root, '', ig, map[string]storage.CacheRow{}, mut entries, mut unused, mut unsafe_paths, mut124		quiet)!125	entries.sort(a.path < b.path)126	return entries127}128129fn walk_dir(root string, rel string, ig Ignore, cache map[string]storage.CacheRow, mut out []FileEntry, mut fresh []storage.CacheRow, mut unsafe_paths []string, mut hashing Hashing) ! {130	dir := if rel == '' { root } else { os.join_path(root, rel) }131	for name in os.ls(dir)! {132		child := if rel == '' { name } else { '${rel}/${name}' }133		if !legal_path(child) {134			unsafe_paths << escape_path(child)135			continue136		}137		st := lstat(os.join_path(root, child)) or { continue }138		// The kind is known by now, so a pattern ending in `/` can be applied139		// to directories only.140		if ig.matches(child, st.kind == .dir) {141			continue142		}143		match st.kind {144			.dir {145				walk_dir(root, child, ig, cache, mut out, mut fresh, mut unsafe_paths, mut hashing)!146			}147			.file {148				if st.size > storage.max_file_size {149					return error('${child} is ${st.size} bytes; koh stores code and text, not files this large')150				}151				hash := hash_file(root, child, st, cache, mut fresh, mut hashing)!152				out << FileEntry{153					path:       child154					hash:       hash155					size:       st.size156					executable: is_executable(st.mode)157				}158			}159			else {}160		}161	}162}163164fn hash_file(root string, rel string, st Stat, cache map[string]storage.CacheRow, mut fresh []storage.CacheRow, mut hashing Hashing) !string {165	if row := cache[rel] {166		if row.size == st.size && row.mtime_ns == st.mtime_ns && row.ctime_ns == st.ctime_ns {167			return row.hash168		}169	}170	hashing.count++171	if hashing.on != unsafe { nil } {172		hashing.on(hashing.count, 0)173	}174	hash := storage.hash_hex(os.read_bytes(os.join_path(root, rel))!)175	if cacheable(st, time.now().unix_nano()) {176		fresh << storage.CacheRow{177			path:     rel178			size:     st.size179			mtime_ns: st.mtime_ns180			ctime_ns: st.ctime_ns181			hash:     hash182		}183	}184	return hash185}186187// cacheable reports whether a hash may be cached. Linux stamps files from a188// clock that ticks every few milliseconds, so a same-size rewrite in the tick189// of the hash would look unchanged; a file changed that recently is hashed190// again next time instead. `cp -p` and the like keep an old mtime while191// rewriting, so the newer of mtime and ctime decides.192fn cacheable(st Stat, now_ns i64) bool {193	changed := if st.ctime_ns > st.mtime_ns { st.ctime_ns } else { st.mtime_ns }194	return now_ns - changed >= racy_window_ns195}196197// store_objects writes the bytes of every entry the database does not have198// yet, so a save only pays for content it has never seen.199pub fn store_objects(store &storage.Store, root string, entries []FileEntry, progress Counted) ! {200	for i, entry in entries {201		if progress != unsafe { nil } {202			progress(i + 1, entries.len)203		}204		if store.has_object(entry.hash)! {205			continue206		}207		data := os.read_bytes(os.join_path(root, entry.path))!208		stored := store.put_object(data)!209		if stored != entry.hash {210			return error('${entry.path} changed while saving')211		}212	}213}214215// same_tree compares two sorted entry lists by path, hash and executable bit.216pub fn same_tree(a []FileEntry, b []FileEntry) bool {217	if a.len != b.len {218		return false219	}220	for i in 0 .. a.len {221		if a[i].path != b[i].path || a[i].hash != b[i].hash || a[i].executable != b[i].executable {222			return false223		}224	}225	return true226}