Something went wrong. Try again.
A simple DAV sync application / cli
Something went wrong. Try again.
TypeScript
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307import type { Change, LastSeen, MoveEvidence, Side, SideChanges, Snapshot, States } from "./types.ts";import { depth, isBelow, mapLimit, nameOf, parentOf, rebase } from "./paths.ts";
/** How much of a file the `head` hash covers. */export const HEAD_SIZE = 4096;
/** * A local file whose mtime lies this close before the moment its last-seen record * was written may have changed again within the same timestamp tick, so an * unchanged stat proves nothing about it. It is re-hashed once (git's "racy" rule). */export const RACY_MS = 2000;
/** * The I/O detection may need. Each call answers one question as cheaply as it can, * and detection only asks when cheaper evidence ran out. Results are cached on the * snapshot (`head`, `sha256`) so execution never reads the same bytes twice. */export interface Probe { /** SHA-256 of the first HEAD_SIZE bytes of a local file. */ headLocal(snapshot: Snapshot): Promise<string>; /** SHA-256 of a whole local file (and its head, from the same read). */ hashLocal(snapshot: Snapshot): Promise<{ sha256: string; head: string }>; /** SHA-256 of the first HEAD_SIZE bytes of a remote file (a Range request), or null if the server can't say. */ headRemote(snapshot: Snapshot): Promise<string | null>;}
type Verdict = "same" | "refresh" | "modified";
/** How one side tells whether an entry still holds what was last seen. */interface Rules { side: Side; /** The entry is still at its last-seen path: did its content change? */ compare(base: LastSeen, now: Snapshot): Promise<Verdict>; /** A new path appeared and a last-seen path vanished: is it the same content, and how do we know? */ sameContent(base: LastSeen, now: Snapshot): Promise<MoveEvidence | null>; /** * The entry at a new path has the vanished one's identity: is it plausibly that * file, moved? (File systems hand a deleted file's inode to the next new one.) */ sameObject(base: LastSeen, now: Snapshot): Promise<boolean>;}
const HASH_CONCURRENCY = 8;
/** * Compares the last-seen state with what each side holds now, and reports per side * what happened to every entry: unchanged, modified, deleted, added, or moved. * * Detection never decides what to do about a change (that is the planner's job) and * never writes anything. It reads as little as it can: * * - local files whose size, mtime, ctime and inode are as last seen are trusted * without reading them, unless their timestamp is racy; * - otherwise the 4 KiB head settles most cases, and only an equal head with an * equal size makes it read the whole file; * - remote files are judged by etag (and a SHA-256 checksum, where the server * keeps one), and are never downloaded here. * * Moves are recognised, in order of confidence, by identity (inode / oc:fileid), * by a parent directory having moved, by content (SHA-256 locally; etag, checksum * or, for small files, the head remotely), and finally a directory counts as moved * when everything that was below it turned up below one new directory. */export async function detect(states: States, probe: Probe): Promise<{ local: SideChanges; remote: SideChanges }> { const [local, remote] = await Promise.all([ detectSide(states.base, states.local, localRules(probe)), detectSide(states.base, states.remote, remoteRules(probe)), ]); return { local, remote };}
function localRules(probe: Probe): Rules { const head = async (now: Snapshot) => (now.head ??= await probe.headLocal(now)); const sha256 = async (now: Snapshot) => { if (now.sha256 === null) Object.assign(now, await probe.hashLocal(now)); return now.sha256!; }; return { side: "local", async compare(base, now) { const racy = base.syncedAt - base.local.mtime < RACY_MS; // The inode is left out on purpose: some file systems (FAT, network mounts) // number files afresh on every mount, which would re-hash everything. A file // replaced by another one has a new ctime anyway. const statSame = now.size === base.size && now.mtime === base.local.mtime && now.ctime === base.local.ctime; if (statSame && !racy) { now.sha256 ??= base.sha256; now.head ??= base.head; return "same"; } // Something about the file changed, or might have. Find out from as few bytes as possible. if (now.size !== base.size) return "modified"; try { if (base.head !== null && (await head(now)) !== base.head) return "modified"; if ((await sha256(now)) !== base.sha256) return "modified"; } catch { // Unreadable right now (vanished, locked): let execution try, and report what fails. return "modified"; } if (!statSame) return "refresh"; // Racy but unchanged. Recording it again only helps once the record would no // longer be racy; until then, it is simply re-hashed. return Date.now() - now.mtime >= RACY_MS ? "refresh" : "same"; }, async sameObject(base, now) { // A rename keeps a file's mtime; a file that merely got a recycled inode was // just written. Changed since the move is fine, as long as it starts the same. if (now.mtime === base.local.mtime) return true; try { return base.head !== null && (await head(now)) === base.head; } catch { return false; } }, async sameContent(base, now) { if (now.size !== base.size || base.sha256 === null) return null; if (base.head !== null && (await head(now)) !== base.head) return null; return (await sha256(now)) === base.sha256 ? "sha256" : null; }, };}
function remoteRules(probe: Probe): Rules { return { side: "remote", async compare(base, now) { if (now.etag !== null && base.remote.etag !== null) { if (now.etag === base.remote.etag && now.size === base.size) { now.sha256 ??= base.sha256; now.head ??= base.head; return "same"; } } else if (now.size === base.size && now.mtime === base.remote.mtime) { // No etags to go by: size and modification time are all there is. now.sha256 ??= base.sha256; now.head ??= base.head; return "same"; } // The etag moved on. A server-side checksum can still prove the bytes didn't; // without one, the content is unknown until it is downloaded. if (now.sha256 !== null && now.sha256 === base.sha256) return "refresh"; return "modified"; }, // A server's file id names one file for good; it is not handed on. sameObject: async () => true, async sameContent(base, now) { if (now.size !== base.size) return null; if (now.etag !== null && now.etag === base.remote.etag) return "etag"; if (now.sha256 !== null && now.sha256 === base.sha256) return "sha256"; // A head that covers the whole file is the whole file. if (now.size <= HEAD_SIZE && base.head !== null) { now.head ??= await probe.headRemote(now).catch(() => null); if (now.head === base.head) return "head"; } return null; }, };}
async function detectSide(base: Map<string, LastSeen>, current: Map<string, Snapshot>, rules: Rules): Promise<SideChanges> { const known = new Map<string, Change>(); const added = new Map<string, Change>(); /** Last-seen entries that are no longer at their path on this side. */ const vanished = new Map<string, LastSeen>(); /** Entries at paths that have no last-seen record. */ const appeared = new Map<string, Snapshot>();
// ---- Entries still where they were ---------------------------------------- const stayed: [LastSeen, Snapshot][] = []; for (const [path, entry] of base) { const now = current.get(path); if (!now || now.kind !== entry.kind) vanished.set(path, entry); else stayed.push([entry, now]); } for (const [path, now] of current) { const entry = base.get(path); if (!entry || entry.kind !== now.kind) appeared.set(path, now); } const verdicts = await mapLimit(stayed, HASH_CONCURRENCY, ([entry, now]) => entry.kind === "dir" ? Promise.resolve<Verdict>("same") : rules.compare(entry, now), ); stayed.forEach(([entry], index) => { const verdict = verdicts[index]!; known.set( entry.path, verdict === "modified" ? { type: "modified", path: entry.path } : { type: "unchanged", path: entry.path, refresh: verdict === "refresh" }, ); });
// ---- Moves ------------------------------------------------------------------ const moved = (from: string, to: string, modified: boolean, via: MoveEvidence) => { known.set(from, { type: "moved", path: to, from, modified, via }); vanished.delete(from); appeared.delete(to); }; const byId = (kind: LastSeen["kind"]) => { const index = new Map<string, LastSeen>(); for (const entry of vanished.values()) { const id = entry[rules.side].id; if (entry.kind === kind && id !== null && !index.has(id)) index.set(id, entry); } return index; }; const sorted = <T>(map: Map<string, T>) => [...map.keys()].sort((a, b) => depth(a) - depth(b) || a.localeCompare(b));
// 1. Directories by identity, outermost first, each taking everything below it along. const dirsById = byId("dir"); for (const path of sorted(appeared)) { const now = appeared.get(path); if (!now || now.kind !== "dir" || now.id === null) continue; const entry = dirsById.get(now.id); if (!entry || !vanished.has(entry.path)) continue; moved(entry.path, path, false, "id"); for (const below of sorted(vanished)) { if (!isBelow(below, entry.path)) continue; const target = rebase(below, entry.path, path); const there = appeared.get(target); const was = vanished.get(below)!; if (!there || there.kind !== was.kind) continue; const verdict = was.kind === "dir" ? "same" : await rules.compare(was, there); moved(below, target, verdict === "modified", "dir"); } }
// 2. Files by identity. The content may have changed along the way. const filesById = byId("file"); for (const path of sorted(appeared)) { const now = appeared.get(path)!; if (now.kind !== "file" || now.id === null) continue; const entry = filesById.get(now.id); if (!entry || !vanished.has(entry.path)) continue; if (!(await rules.sameObject(entry, now))) continue; const verdict = await rules.compare(entry, now); moved(entry.path, path, verdict === "modified", "id"); }
// 3. Files by content. Only sizes that match some vanished file are worth a look, // and among equal candidates the one with the same name wins, then the same folder. const bySize = new Map<number, LastSeen[]>(); for (const entry of vanished.values()) { if (entry.kind !== "file") continue; if (!bySize.has(entry.size)) bySize.set(entry.size, []); bySize.get(entry.size)!.push(entry); } for (const path of sorted(appeared)) { const now = appeared.get(path)!; if (now.kind !== "file") continue; const candidates = (bySize.get(now.size) ?? []) .filter((entry) => vanished.has(entry.path)) .sort((a, b) => affinity(b.path, path) - affinity(a.path, path)); for (const entry of candidates) { let evidence: MoveEvidence | null; try { evidence = await rules.sameContent(entry, now); } catch { evidence = null; } if (evidence) { moved(entry.path, path, false, evidence); break; } } }
// 4. Directories whose whole content moved, innermost first so nested ones compose. for (const path of sorted(vanished).reverse()) { const entry = vanished.get(path)!; if (entry.kind !== "dir") continue; const target = movedDirTarget(path, base, known); const there = target === null ? undefined : appeared.get(target); if (there?.kind === "dir") moved(path, target!, false, "dir"); }
// ---- Whatever is left --------------------------------------------------------- for (const path of vanished.keys()) known.set(path, { type: "deleted", path }); for (const path of appeared.keys()) added.set(path, { type: "added", path }); return { side: rules.side, known, added };}
/** * Where directory `dir` went, if every last-seen entry below it moved to the same * relative place below one new directory. Null when there is nothing below it, or * anything stayed, vanished or went elsewhere. */function movedDirTarget(dir: string, base: Map<string, LastSeen>, known: Map<string, Change>): string | null { let target: string | null = null; for (const path of base.keys()) { if (!isBelow(path, dir)) continue; const change = known.get(path); if (change?.type !== "moved") return null; const relative = path.slice(dir.length); if (!change.path.endsWith(relative)) return null; const candidate = change.path.slice(0, change.path.length - relative.length); if (target !== null && candidate !== target) return null; target = candidate; } return target;}
/** Tie-break for equal-content candidates: same name beats same folder beats neither. */function affinity(from: string, to: string): number { return (nameOf(from) === nameOf(to) ? 2 : 0) + (parentOf(from) === parentOf(to) ? 1 : 0);}