rightkit_fs/
identity.rs

1//! Stable file identity across renames.
2//!
3//! A [`StableId`] names "this file" independent of its path. It is bound to the filesystem's own
4//! identity ([`FileKey`]: device + inode on unix, volume serial + file index on Windows), which
5//! survives `rename` and move within a volume, and falls back to a content fingerprint when the
6//! file was replaced (atomic save, editor "safe write") or copied to another volume.
7//!
8//! Resolution order, cheapest first:
9//! 1. the last known path still holds the same `FileKey` -> [`Resolution::Unchanged`];
10//! 2. a bounded walk of the caller's search roots finds the same `FileKey` -> [`Resolution::Moved`];
11//! 3. the last known path (or a search-root file) has the same size and head/tail fingerprint
12//!    but a new `FileKey` -> [`Resolution::Replaced`] (the ledger is rebound);
13//! 4. otherwise [`Resolution::Missing`].
14//!
15//! The ledger is one JSON file written atomically under a cross-process lock, so any number of
16//! processes can track and resolve concurrently. Donors: HeardRight/ScrapeRight/ViewRight file
17//! grants and clipboard delivery, which each keyed files by path.
18
19use crate::atomic::atomic_write_private;
20use crate::error::{FsError, Result};
21use crate::lock::{FileLock, LockOptions};
22use serde::{Deserialize, Serialize};
23use std::collections::BTreeMap;
24use std::fs::File;
25use std::io::{Read, Seek, SeekFrom};
26use std::path::{Path, PathBuf};
27use std::time::{Duration, SystemTime, UNIX_EPOCH};
28
29const LEDGER_FILE: &str = "identity-ledger.json";
30const LOCK_FILE: &str = "identity-ledger.lock";
31const SAMPLE: u64 = 64 * 1024;
32const LEDGER_VERSION: u32 = 1;
33
34pub type StableId = String;
35
36/// The filesystem's own identity for an open file.
37#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
38pub struct FileKey {
39    pub volume: u64,
40    pub index: u64,
41}
42
43impl FileKey {
44    pub fn of_path(path: &Path) -> Result<Self> {
45        let file = File::open(path).map_err(|e| FsError::io(path, e))?;
46        Self::of_file(&file, path)
47    }
48
49    pub fn of_file(file: &File, shown: &Path) -> Result<Self> {
50        #[cfg(unix)]
51        {
52            use std::os::unix::fs::MetadataExt;
53            let meta = file.metadata().map_err(|e| FsError::io(shown, e))?;
54            Ok(Self {
55                volume: meta.dev(),
56                index: meta.ino(),
57            })
58        }
59        #[cfg(windows)]
60        {
61            windows_key(file).map_err(|e| FsError::io(shown, e))
62        }
63        #[cfg(not(any(unix, windows)))]
64        {
65            let _ = (file, shown);
66            Err(FsError::Unavailable("file identity"))
67        }
68    }
69
70    fn of_meta(meta: &std::fs::Metadata, path: &Path) -> Option<Self> {
71        #[cfg(unix)]
72        {
73            let _ = path;
74            use std::os::unix::fs::MetadataExt;
75            Some(Self {
76                volume: meta.dev(),
77                index: meta.ino(),
78            })
79        }
80        #[cfg(not(unix))]
81        {
82            let _ = meta;
83            Self::of_path(path).ok()
84        }
85    }
86}
87
88#[cfg(windows)]
89fn windows_key(file: &File) -> std::io::Result<FileKey> {
90    use std::os::windows::io::AsRawHandle;
91    #[repr(C)]
92    struct FileTime {
93        low: u32,
94        high: u32,
95    }
96    #[repr(C)]
97    struct ByHandleFileInformation {
98        attributes: u32,
99        creation: FileTime,
100        access: FileTime,
101        write: FileTime,
102        volume_serial: u32,
103        size_high: u32,
104        size_low: u32,
105        links: u32,
106        index_high: u32,
107        index_low: u32,
108    }
109    #[link(name = "kernel32")]
110    unsafe extern "system" {
111        fn GetFileInformationByHandle(
112            handle: *mut std::ffi::c_void,
113            info: *mut ByHandleFileInformation,
114        ) -> i32;
115    }
116    let mut info = std::mem::MaybeUninit::<ByHandleFileInformation>::zeroed();
117    // SAFETY: the handle is a live file handle and `info` is a valid out-parameter.
118    let ok = unsafe { GetFileInformationByHandle(file.as_raw_handle().cast(), info.as_mut_ptr()) };
119    if ok == 0 {
120        return Err(std::io::Error::last_os_error());
121    }
122    // SAFETY: the call succeeded and filled the struct.
123    let info = unsafe { info.assume_init() };
124    Ok(FileKey {
125        volume: u64::from(info.volume_serial),
126        index: (u64::from(info.index_high) << 32) | u64::from(info.index_low),
127    })
128}
129
130/// Cheap content fingerprint: size plus FNV-1a over the first and last 64 KiB. Only ever used to
131/// shortlist a replaced or copied file; never as proof of identity on its own.
132#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
133pub struct Fingerprint {
134    pub size: u64,
135    pub sample_hash: u64,
136}
137
138impl Fingerprint {
139    pub fn of_path(path: &Path) -> Result<Self> {
140        let mut file = File::open(path).map_err(|e| FsError::io(path, e))?;
141        let size = file.metadata().map_err(|e| FsError::io(path, e))?.len();
142        let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
143        let mut feed = |bytes: &[u8]| {
144            for b in bytes {
145                hash ^= u64::from(*b);
146                hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
147            }
148        };
149        let mut buf = vec![0u8; SAMPLE as usize];
150        let head = size.min(SAMPLE) as usize;
151        file.read_exact(&mut buf[..head])
152            .map_err(|e| FsError::io(path, e))?;
153        feed(&buf[..head]);
154        if size > SAMPLE {
155            let tail = size.min(SAMPLE) as usize;
156            file.seek(SeekFrom::Start(size - tail as u64))
157                .map_err(|e| FsError::io(path, e))?;
158            file.read_exact(&mut buf[..tail])
159                .map_err(|e| FsError::io(path, e))?;
160            feed(&buf[..tail]);
161        }
162        Ok(Self {
163            size,
164            sample_hash: hash,
165        })
166    }
167}
168
169#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
170pub struct Tracked {
171    pub id: StableId,
172    pub key: FileKey,
173    pub last_path: PathBuf,
174    pub fingerprint: Fingerprint,
175    pub tracked_at_ms: u64,
176}
177
178#[derive(Clone, Debug, PartialEq, Eq)]
179pub enum Resolution {
180    /// Same file at the same path.
181    Unchanged(PathBuf),
182    /// Same file (same `FileKey`) found at a new path; the ledger now points there.
183    Moved(PathBuf),
184    /// The file's inode changed (replaced/copied) but size and fingerprint match; rebound.
185    Replaced(PathBuf),
186    Missing,
187}
188
189impl Resolution {
190    pub fn path(&self) -> Option<&Path> {
191        match self {
192            Self::Unchanged(p) | Self::Moved(p) | Self::Replaced(p) => Some(p),
193            Self::Missing => None,
194        }
195    }
196}
197
198#[derive(Clone, Debug)]
199pub struct SearchLimits {
200    pub max_entries: usize,
201    pub max_depth: usize,
202}
203
204impl Default for SearchLimits {
205    fn default() -> Self {
206        Self {
207            max_entries: 200_000,
208            max_depth: 12,
209        }
210    }
211}
212
213#[derive(Default, Serialize, Deserialize)]
214struct Ledger {
215    version: u32,
216    entries: BTreeMap<StableId, Tracked>,
217}
218
219pub struct IdentityStore {
220    dir: PathBuf,
221    limits: SearchLimits,
222}
223
224impl IdentityStore {
225    /// `dir` is the app's state directory; the ledger and its lock live inside it.
226    pub fn open(dir: &Path) -> Result<Self> {
227        crate::private::ensure_private_dir(dir)?;
228        Ok(Self {
229            dir: dir.to_path_buf(),
230            limits: SearchLimits::default(),
231        })
232    }
233
234    pub fn with_limits(mut self, limits: SearchLimits) -> Self {
235        self.limits = limits;
236        self
237    }
238
239    fn locked<T>(&self, f: impl FnOnce(&mut Ledger) -> Result<(T, bool)>) -> Result<T> {
240        let _lock = FileLock::acquire(
241            &self.dir.join(LOCK_FILE),
242            &LockOptions::wait(Duration::from_secs(10)).labeled("identity-ledger"),
243        )?;
244        let path = self.dir.join(LEDGER_FILE);
245        let mut ledger = match std::fs::read(&path) {
246            Ok(bytes) => {
247                serde_json::from_slice::<Ledger>(&bytes).map_err(|e| FsError::Corrupt {
248                    path: path.clone(),
249                    reason: e.to_string(),
250                })?
251            }
252            Err(e) if e.kind() == std::io::ErrorKind::NotFound => Ledger {
253                version: LEDGER_VERSION,
254                ..Ledger::default()
255            },
256            Err(e) => return Err(FsError::io(&path, e)),
257        };
258        let (out, dirty) = f(&mut ledger)?;
259        if dirty {
260            let bytes = serde_json::to_vec_pretty(&ledger).expect("ledger serializes");
261            atomic_write_private(&path, &bytes)?;
262        }
263        Ok(out)
264    }
265
266    /// Start tracking `path`; returns a new stable id.
267    pub fn track(&self, path: &Path) -> Result<StableId> {
268        let abs = absolute(path)?;
269        let key = FileKey::of_path(&abs)?;
270        let fingerprint = Fingerprint::of_path(&abs)?;
271        let id = new_id()?;
272        let entry = Tracked {
273            id: id.clone(),
274            key,
275            last_path: abs,
276            fingerprint,
277            tracked_at_ms: now_ms(),
278        };
279        self.locked(|ledger| {
280            ledger.entries.insert(id.clone(), entry);
281            Ok(((), true))
282        })?;
283        Ok(id)
284    }
285
286    /// Same as [`track`](Self::track), but returns the existing id when this file (by `FileKey`)
287    /// is already tracked.
288    pub fn track_or_get(&self, path: &Path) -> Result<StableId> {
289        let abs = absolute(path)?;
290        let key = FileKey::of_path(&abs)?;
291        let fingerprint = Fingerprint::of_path(&abs)?;
292        self.locked(|ledger| {
293            if let Some(existing) = ledger.entries.values().find(|t| t.key == key) {
294                return Ok((existing.id.clone(), false));
295            }
296            let id = new_id()?;
297            ledger.entries.insert(
298                id.clone(),
299                Tracked {
300                    id: id.clone(),
301                    key,
302                    last_path: abs,
303                    fingerprint,
304                    tracked_at_ms: now_ms(),
305                },
306            );
307            Ok((id, true))
308        })
309    }
310
311    pub fn lookup(&self, id: &str) -> Result<Option<Tracked>> {
312        self.locked(|ledger| Ok((ledger.entries.get(id).cloned(), false)))
313    }
314
315    pub fn forget(&self, id: &str) -> Result<bool> {
316        self.locked(|ledger| {
317            let removed = ledger.entries.remove(id).is_some();
318            Ok((removed, removed))
319        })
320    }
321
322    /// Re-record identity and fingerprint for `id` at `path` (after a deliberate rewrite).
323    pub fn rebind(&self, id: &str, path: &Path) -> Result<()> {
324        let abs = absolute(path)?;
325        let key = FileKey::of_path(&abs)?;
326        let fingerprint = Fingerprint::of_path(&abs)?;
327        self.locked(|ledger| {
328            let entry = ledger
329                .entries
330                .get_mut(id)
331                .ok_or_else(|| FsError::UnknownId(id.to_string()))?;
332            entry.key = key;
333            entry.fingerprint = fingerprint;
334            entry.last_path = abs;
335            Ok(((), true))
336        })
337    }
338
339    /// Find where `id` lives now, searching `roots` (bounded, never following symlinks) when the
340    /// last known path no longer holds the file.
341    pub fn resolve(&self, id: &str, roots: &[PathBuf]) -> Result<Resolution> {
342        let tracked = self
343            .lookup(id)?
344            .ok_or_else(|| FsError::UnknownId(id.to_string()))?;
345
346        // 1. Same file, same place.
347        if let Ok(key) = FileKey::of_path(&tracked.last_path) {
348            if key == tracked.key {
349                return Ok(Resolution::Unchanged(tracked.last_path));
350            }
351        }
352
353        // 2. Same file (by filesystem identity), new place; remember size-matching candidates.
354        let mut candidates: Vec<PathBuf> = Vec::new();
355        let mut moved: Option<PathBuf> = None;
356        let mut budget = self.limits.max_entries;
357        for root in roots {
358            walk(
359                root,
360                0,
361                self.limits.max_depth,
362                &mut budget,
363                &mut |path, meta| {
364                    if FileKey::of_meta(meta, path) == Some(tracked.key) {
365                        moved = Some(path.to_path_buf());
366                        return true;
367                    }
368                    if meta.len() == tracked.fingerprint.size && candidates.len() < 64 {
369                        candidates.push(path.to_path_buf());
370                    }
371                    false
372                },
373            );
374            if moved.is_some() {
375                break;
376            }
377        }
378        if let Some(path) = moved {
379            self.update_path(id, &path, None)?;
380            return Ok(Resolution::Moved(path));
381        }
382
383        // 3. Replaced or copied: the old path itself first, then same-size candidates.
384        let mut shortlist = Vec::new();
385        if tracked.last_path.is_file() {
386            shortlist.push(tracked.last_path.clone());
387        }
388        shortlist.extend(candidates);
389        for path in shortlist {
390            if Fingerprint::of_path(&path).ok() == Some(tracked.fingerprint) {
391                let key = FileKey::of_path(&path)?;
392                self.update_path(id, &path, Some(key))?;
393                return Ok(Resolution::Replaced(path));
394            }
395        }
396        Ok(Resolution::Missing)
397    }
398
399    fn update_path(&self, id: &str, path: &Path, new_key: Option<FileKey>) -> Result<()> {
400        self.locked(|ledger| {
401            if let Some(entry) = ledger.entries.get_mut(id) {
402                entry.last_path = path.to_path_buf();
403                if let Some(key) = new_key {
404                    entry.key = key;
405                }
406            }
407            Ok(((), true))
408        })
409    }
410}
411
412fn walk(
413    dir: &Path,
414    depth: usize,
415    max_depth: usize,
416    budget: &mut usize,
417    visit: &mut dyn FnMut(&Path, &std::fs::Metadata) -> bool,
418) -> bool {
419    let Ok(entries) = std::fs::read_dir(dir) else {
420        return false;
421    };
422    for entry in entries.flatten() {
423        if *budget == 0 {
424            return true;
425        }
426        *budget -= 1;
427        // `DirEntry::metadata` does not traverse symlinks.
428        let Ok(meta) = entry.metadata() else { continue };
429        let path = entry.path();
430        if meta.file_type().is_symlink() {
431            continue;
432        }
433        if meta.is_file() {
434            if visit(&path, &meta) {
435                return true;
436            }
437        } else if meta.is_dir()
438            && depth < max_depth
439            && walk(&path, depth + 1, max_depth, budget, visit)
440        {
441            return true;
442        }
443    }
444    false
445}
446
447fn absolute(path: &Path) -> Result<PathBuf> {
448    if path.is_absolute() {
449        Ok(path.to_path_buf())
450    } else {
451        Ok(std::env::current_dir()
452            .map_err(|e| FsError::io(path, e))?
453            .join(path))
454    }
455}
456
457fn now_ms() -> u64 {
458    SystemTime::now()
459        .duration_since(UNIX_EPOCH)
460        .map(|d| d.as_millis() as u64)
461        .unwrap_or(0)
462}
463
464fn new_id() -> Result<StableId> {
465    let mut bytes = [0u8; 16];
466    random_bytes(&mut bytes)?;
467    Ok(bytes.iter().map(|b| format!("{b:02x}")).collect())
468}
469
470fn random_bytes(buf: &mut [u8]) -> Result<()> {
471    #[cfg(unix)]
472    {
473        File::open("/dev/urandom")
474            .and_then(|mut f| f.read_exact(buf))
475            .map_err(|e| FsError::io("/dev/urandom", e))
476    }
477    #[cfg(windows)]
478    {
479        #[link(name = "bcrypt")]
480        unsafe extern "system" {
481            fn BCryptGenRandom(
482                algorithm: *mut std::ffi::c_void,
483                buffer: *mut u8,
484                length: u32,
485                flags: u32,
486            ) -> i32;
487        }
488        // SAFETY: buffer is valid for its length; flag 2 = system-preferred RNG.
489        let status =
490            unsafe { BCryptGenRandom(std::ptr::null_mut(), buf.as_mut_ptr(), buf.len() as u32, 2) };
491        if status >= 0 {
492            Ok(())
493        } else {
494            Err(FsError::io(
495                "BCryptGenRandom",
496                std::io::Error::other("RNG failure"),
497            ))
498        }
499    }
500    #[cfg(not(any(unix, windows)))]
501    {
502        let _ = buf;
503        Err(FsError::Unavailable("random bytes"))
504    }
505}
rightkit_fs/identity.rs

rightkit_fs/
identity.rs
