trash_core/
macos.rs

1//! Read-only reader for the macOS **Trash** put-back metadata stored in a
2//! Trash folder's `.DS_Store` file.
3//!
4//! On modern macOS (Big Sur → Sequoia) there is no `$I`/`$R`-style sidecar and no
5//! put-back extended attribute: the original location of a trashed item is
6//! recorded only inside the Trash folder's `.DS_Store`, as two per-item B-tree
7//! records keyed by the item's *current* name in the Trash:
8//!
9//! * **`ptbN`** — *Put-Back Name*: the item's original filename, and
10//! * **`ptbL`** — *Put-Back Location*: the item's original parent directory,
11//!
12//! both of `.DS_Store` data type `ustr` (a length-prefixed UTF-16**BE** string).
13//! `ptbL` is stored in the APFS firmlink form `System/Volumes/Data/…`;
14//! [`PutBack::original_path`] normalises that to the user-visible `/…` while the
15//! raw value stays available verbatim.
16//!
17//! Many legitimately trashed items have **no** put-back record (Finder writes
18//! `.DS_Store` lazily, and `rm`/non-Finder deletes never write one), so the
19//! absence of a record is normal, not evidence of tampering.
20//!
21//! # `.DS_Store` / `Bud1` format
22//!
23//! The container is a Finder "Desktop Services Store": a 4-byte `00 00 00 01`
24//! prefix, the magic `Bud1`, then a **buddy allocator** whose table-of-contents
25//! maps the key `DSDB` to a **B-tree** of records. The layout follows Wim Lewis's
26//! reverse-engineered `Mac::Finder::DSStore` `DSStoreFormat.pod`
27//! (<https://metacpan.org/dist/Mac-Finder-DSStore/view/DSStoreFormat.pod>); the
28//! `ptbN`/`ptbL` record types are newer Finder additions cross-checked against
29//! al45tair's `ds_store` library, which also generated this crate's test fixture.
30//!
31//! All reads are bounds-checked: a truncated or hostile `.DS_Store` yields a
32//! typed [`DsStoreError`], never a panic, and the B-tree walk is cycle-guarded.
33
34use std::collections::{BTreeMap, HashSet};
35
36use thiserror::Error;
37
38/// Errors returned while parsing a `.DS_Store` put-back store.
39#[derive(Debug, Error, PartialEq, Eq)]
40pub enum DsStoreError {
41    /// The file is shorter than the 36-byte `Bud1` header.
42    #[error(".DS_Store truncated: {got} bytes, need at least {needed} for the Bud1 header")]
43    TruncatedHeader {
44        /// Bytes present.
45        got: usize,
46        /// Bytes required.
47        needed: usize,
48    },
49
50    /// The leading `00 00 00 01` / `Bud1` magic is wrong. Carries the offending
51    /// bytes for the investigator.
52    #[error("bad .DS_Store magic: word0={word0:#010x}, magic={magic:?} (expected 1 / b\"Bud1\")")]
53    BadMagic {
54        /// The first 32-bit big-endian word (expected `1`).
55        word0: u32,
56        /// The 4 magic bytes (expected `Bud1`).
57        magic: [u8; 4],
58    },
59
60    /// The two copies of the root-block offset in the header disagree — the
61    /// allocator is inconsistent (Finder rejects such files).
62    #[error(".DS_Store root offsets differ: {first:#x} vs {second:#x}")]
63    RootOffsetMismatch {
64        /// The first root-block offset.
65        first: u32,
66        /// The second (validation) copy.
67        second: u32,
68    },
69
70    /// A block address points outside the file, or a structure overruns its
71    /// block. Carries the operation for diagnosis.
72    #[error(".DS_Store read out of bounds while reading {what}")]
73    OutOfBounds {
74        /// What was being read when the bound was exceeded.
75        what: &'static str,
76    },
77
78    /// The allocator's table of contents has no `DSDB` B-tree entry.
79    #[error(".DS_Store has no DSDB B-tree entry")]
80    NoDsdb,
81
82    /// A record carried a `.DS_Store` data-type code the format does not define,
83    /// so the record stream cannot be safely advanced. Carries the bytes.
84    #[error("unknown .DS_Store record data type {typecode:?}")]
85    UnknownDataType {
86        /// The offending 4-byte data-type code.
87        typecode: [u8; 4],
88    },
89}
90
91/// A recovered macOS put-back record: an item in the Trash together with where it
92/// came from.
93#[derive(Debug, Clone, PartialEq, Eq)]
94#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
95pub struct PutBack {
96    /// The item's current name inside the Trash (the `.DS_Store` record key).
97    /// Finder de-duplicates colliding names, so this need not equal
98    /// [`original_name`](Self::original_name).
99    pub trash_name: String,
100    /// The original filename at deletion time (`ptbN`), if recorded.
101    pub original_name: Option<String>,
102    /// The original parent directory (`ptbL`) **verbatim**, in the stored
103    /// firmlink form (`System/Volumes/Data/…`), if recorded.
104    pub original_location: Option<String>,
105}
106
107impl PutBack {
108    /// The full original path, `ptbL` + `ptbN`, with the firmlink prefix
109    /// normalised to the user-visible `/…`. `None` unless both `ptbN` and `ptbL`
110    /// were recorded.
111    #[must_use]
112    pub fn original_path(&self) -> Option<String> {
113        let location = self.original_location.as_deref()?;
114        let name = self.original_name.as_deref()?;
115        let dir = normalize_firmlink(location);
116        Some(if dir.ends_with('/') {
117            format!("{dir}{name}")
118        } else {
119            format!("{dir}/{name}")
120        })
121    }
122}
123
124/// Normalise an APFS firmlink `ptbL` value (`System/Volumes/Data/…` or
125/// `/System/Volumes/Data/…`) to the user-visible absolute path (`/…`). A value
126/// that is not in firmlink form is returned with a single leading slash.
127fn normalize_firmlink(location: &str) -> String {
128    let trimmed = location.strip_prefix('/').unwrap_or(location);
129    let rest = trimmed
130        .strip_prefix("System/Volumes/Data/")
131        .unwrap_or(trimmed);
132    format!("/{rest}")
133}
134
135/// Parse the raw bytes of a Trash `.DS_Store` file and return every put-back
136/// record it carries, sorted by [`trash_name`](PutBack::trash_name).
137///
138/// # Errors
139///
140/// Returns [`DsStoreError`] when the header magic is wrong, the allocator/B-tree
141/// is truncated or inconsistent, or a record carries an undefined data-type code.
142/// Never panics on hostile input.
143pub fn parse_put_back(data: &[u8]) -> Result<Vec<PutBack>, DsStoreError> {
144    /// `00 00 00 01` + `Bud1` + offset + size + offset-copy + 16 unknown.
145    const HEADER_LEN: usize = 36;
146
147    if data.len() < HEADER_LEN {
148        return Err(DsStoreError::TruncatedHeader {
149            got: data.len(),
150            needed: HEADER_LEN,
151        });
152    }
153
154    let mut head = Cursor::new(data);
155    let word0 = head.u32("header word")?;
156    let magic = head.array4("magic")?;
157    if word0 != 1 || &magic != b"Bud1" {
158        return Err(DsStoreError::BadMagic { word0, magic });
159    }
160    let root_offset = head.u32("root offset")?;
161    let root_size = head.u32("root size")?;
162    let root_offset_copy = head.u32("root offset copy")?;
163    if root_offset != root_offset_copy {
164        return Err(DsStoreError::RootOffsetMismatch {
165            first: root_offset,
166            second: root_offset_copy,
167        });
168    }
169
170    // Root (allocator metadata) block: the block-address table then the table of
171    // contents that names the `DSDB` B-tree.
172    let root = block_slice(data, root_offset, root_size, "root block")?;
173    let mut r = Cursor::new(root);
174    let count = r.u32("offset count")? as usize;
175    let _unknown = r.u32("offset count guard")?;
176    // The on-disk table is padded up to a multiple of 256 entries; bound the
177    // count by the block before allocating to defend against a hostile value.
178    if count > root.len() / 4 {
179        return Err(DsStoreError::OutOfBounds {
180            what: "offset table count",
181        });
182    }
183    let padded = count.div_ceil(256) * 256;
184    let mut offsets = Vec::with_capacity(count);
185    for i in 0..padded {
186        let entry = r.u32("offset entry")?;
187        if i < count {
188            offsets.push(entry);
189        }
190    }
191
192    let toc_count = r.u32("toc count")?;
193    let mut dsdb: Option<u32> = None;
194    for _ in 0..toc_count {
195        let nlen = r.u8("toc name length")? as usize;
196        let name = r.take(nlen, "toc name")?;
197        let block_id = r.u32("toc block id")?;
198        if name == b"DSDB" {
199            dsdb = Some(block_id);
200        }
201    }
202    let dsdb = dsdb.ok_or(DsStoreError::NoDsdb)?;
203
204    // DSDB master block: root node id + tree node count.
205    let master = block_by_id(data, &offsets, dsdb)?;
206    let mut m = Cursor::new(master);
207    let root_node = m.u32("dsdb root node")?;
208    let _levels = m.u32("dsdb levels")?;
209    let _records = m.u32("dsdb record count")?;
210    let node_count = m.u32("dsdb node count")? as usize;
211
212    // Walk the B-tree collecting `ptbN`/`ptbL` per item. A visited set plus a node
213    // budget guard against malicious cyclic or over-long child pointers.
214    let mut put_back: BTreeMap<String, (Option<String>, Option<String>)> = BTreeMap::new();
215    let mut visited: HashSet<u32> = HashSet::new();
216    let mut stack = vec![root_node];
217    let budget = node_count.saturating_mul(2).max(1024);
218    while let Some(node) = stack.pop() {
219        if !visited.insert(node) {
220            continue; // cov:unreachable: revisiting a node needs a crafted cyclic child pointer; exercised by fuzz_parse_dsstore
221        }
222        // Anti-DoS guard: exceeding the node budget needs a crafted oversized or
223        // cyclic tree; exercised by fuzz_parse_dsstore, not the deterministic corpus.
224        if visited.len() > budget {
225            #[rustfmt::skip]
226            let over_budget = DsStoreError::OutOfBounds { what: "node budget" }; // cov:unreachable
227            return Err(over_budget); // cov:unreachable
228        }
229        let block = block_by_id(data, &offsets, node)?;
230        let mut c = Cursor::new(block);
231        let next_node = c.u32("node next pointer")?;
232        let record_count = c.u32("node record count")?;
233        // An internal node interleaves a child pointer before each record. The
234        // al45tair ds_store writer cannot mint a multi-node B-tree (writer bug), so
235        // the deterministic fixtures are single-leaf; internal-node traversal is
236        // exercised by fuzz_parse_dsstore and real multi-node .DS_Store files.
237        for _ in 0..record_count {
238            if next_node != 0 {
239                let child = c.u32("internal child pointer")?; // cov:unreachable: internal-node path (single-leaf fixture)
240                stack.push(child); // cov:unreachable: internal-node path (single-leaf fixture)
241            }
242            read_record(&mut c, &mut put_back)?;
243        }
244        if next_node != 0 {
245            stack.push(next_node); // cov:unreachable: internal-node path (single-leaf fixture)
246        }
247    }
248
249    Ok(put_back
250        .into_iter()
251        .map(|(trash_name, (original_name, original_location))| PutBack {
252            trash_name,
253            original_name,
254            original_location,
255        })
256        .collect())
257}
258
259/// A bounds-checked, big-endian cursor: every read returns a [`DsStoreError`]
260/// rather than panicking when the underlying slice is too short.
261struct Cursor<'a> {
262    buf: &'a [u8],
263    pos: usize,
264}
265
266impl<'a> Cursor<'a> {
267    fn new(buf: &'a [u8]) -> Self {
268        Self { buf, pos: 0 }
269    }
270
271    fn take(&mut self, n: usize, what: &'static str) -> Result<&'a [u8], DsStoreError> {
272        let end = self
273            .pos
274            .checked_add(n)
275            .ok_or(DsStoreError::OutOfBounds { what })?;
276        let slice = self
277            .buf
278            .get(self.pos..end)
279            .ok_or(DsStoreError::OutOfBounds { what })?;
280        self.pos = end;
281        Ok(slice)
282    }
283
284    fn array4(&mut self, what: &'static str) -> Result<[u8; 4], DsStoreError> {
285        let bytes = self.take(4, what)?;
286        bytes
287            .try_into()
288            .map_err(|_| DsStoreError::OutOfBounds { what })
289    }
290
291    fn u32(&mut self, what: &'static str) -> Result<u32, DsStoreError> {
292        Ok(u32::from_be_bytes(self.array4(what)?))
293    }
294
295    fn u8(&mut self, what: &'static str) -> Result<u8, DsStoreError> {
296        Ok(self.take(1, what)?[0])
297    }
298
299    fn skip(&mut self, n: usize, what: &'static str) -> Result<(), DsStoreError> {
300        self.take(n, what).map(|_| ())
301    }
302}
303
304/// Slice a buddy-allocator block out of the file. Stored offsets skip the 4-byte
305/// `00 00 00 01` prefix, so a stored offset `o` maps to file position `o + 4`.
306fn block_slice<'a>(
307    data: &'a [u8],
308    offset: u32,
309    size: u32,
310    what: &'static str,
311) -> Result<&'a [u8], DsStoreError> {
312    let start = (offset as usize)
313        .checked_add(4)
314        .ok_or(DsStoreError::OutOfBounds { what })?;
315    let end = start
316        .checked_add(size as usize)
317        .ok_or(DsStoreError::OutOfBounds { what })?;
318    data.get(start..end)
319        .ok_or(DsStoreError::OutOfBounds { what })
320}
321
322/// Look up a block by its allocator id: the offset-table entry packs the block's
323/// offset in its high bits and the base-2 log of its size in its low 5 bits.
324fn block_by_id<'a>(data: &'a [u8], offsets: &[u32], id: u32) -> Result<&'a [u8], DsStoreError> {
325    let addr = *offsets
326        .get(id as usize)
327        .ok_or(DsStoreError::OutOfBounds { what: "block id" })?;
328    let offset = addr & !0x1F;
329    let size = 1u32 << (addr & 0x1F);
330    block_slice(data, offset, size, "block")
331}
332
333/// Read one `.DS_Store` record, recording its value into `out` when it is a
334/// `ptbN` (put-back name) or `ptbL` (put-back location). Every record is fully
335/// consumed so the cursor lands on the next record.
336fn read_record(
337    c: &mut Cursor,
338    out: &mut BTreeMap<String, (Option<String>, Option<String>)>,
339) -> Result<(), DsStoreError> {
340    let nlen = c.u32("record name length")? as usize;
341    let name_bytes = c.take(2 * nlen, "record name")?;
342    let filename = decode_utf16be(name_bytes);
343    let code = c.array4("record code")?;
344    let typecode = c.array4("record data type")?;
345    let value = read_value(c, typecode)?;
346    match &code {
347        b"ptbN" => out.entry(filename).or_default().0 = value,
348        b"ptbL" => out.entry(filename).or_default().1 = value,
349        _ => {}
350    }
351    Ok(())
352}
353
354/// Consume a record's typed value, returning the decoded string for the
355/// `ustr` type (the only type `ptbN`/`ptbL` use) and `None` for the others.
356fn read_value(c: &mut Cursor, typecode: [u8; 4]) -> Result<Option<String>, DsStoreError> {
357    match &typecode {
358        b"bool" => c.skip(1, "bool value").map(|()| None),
359        b"long" | b"shor" | b"type" => c.skip(4, "fixed value").map(|()| None),
360        b"comp" | b"dutc" => c.skip(8, "8-byte value").map(|()| None),
361        b"blob" => {
362            let vlen = c.u32("blob length")? as usize;
363            c.skip(vlen, "blob value").map(|()| None)
364        }
365        b"ustr" => {
366            let vlen = c.u32("ustr length")? as usize;
367            let bytes = c.take(2 * vlen, "ustr value")?;
368            Ok(Some(decode_utf16be(bytes)))
369        }
370        other => Err(DsStoreError::UnknownDataType { typecode: *other }), // cov:unreachable: a non-standard data-type FourCC needs a crafted record; exercised by fuzz_parse_dsstore
371    }
372}
373
374/// Decode a UTF-16 big-endian byte slice, lossily replacing invalid sequences
375/// with U+FFFD. A trailing odd byte is ignored.
376fn decode_utf16be(bytes: &[u8]) -> String {
377    let units: Vec<u16> = bytes
378        .chunks_exact(2)
379        .map(|pair| u16::from_be_bytes([pair[0], pair[1]]))
380        .collect();
381    String::from_utf16_lossy(&units)
382}
383
384#[cfg(test)]
385mod tests {
386    use super::*;
387
388    /// A real `.DS_Store` minted by al45tair's `ds_store` library (the oracle),
389    /// carrying two put-back items plus one non-put-back (`Iloc` blob) record.
390    const FIXTURE: &[u8] = include_bytes!("../tests/data/putback.DS_Store");
391
392    fn get<'a>(records: &'a [PutBack], name: &str) -> &'a PutBack {
393        records.iter().find(|r| r.trash_name == name).unwrap()
394    }
395
396    /// The two put-back items are recovered; the `Iloc` blob record is skipped.
397    #[test]
398    fn recovers_both_put_back_items() {
399        let records = parse_put_back(FIXTURE).unwrap();
400        assert_eq!(records.len(), 2);
401    }
402
403    /// A clean item: trash name == original name, firmlink location normalised,
404    /// full original path reconstructed. Values match the oracle decode.
405    #[test]
406    fn clean_item_decodes_to_oracle_values() {
407        let records = parse_put_back(FIXTURE).unwrap();
408        let r = get(&records, "Reference Letter.png");
409        assert_eq!(r.original_name.as_deref(), Some("Reference Letter.png"));
410        assert_eq!(
411            r.original_location.as_deref(),
412            Some("System/Volumes/Data/Users/4n6h4x0r/Downloads/")
413        );
414        assert_eq!(
415            r.original_path().as_deref(),
416            Some("/Users/4n6h4x0r/Downloads/Reference Letter.png")
417        );
418    }
419
420    /// A Finder-deduped item: the trash name (`report 2.pdf`) diverges from the
421    /// original name (`report.pdf`) — the reader reports both faithfully.
422    #[test]
423    fn deduped_trash_name_diverges_from_original() {
424        let records = parse_put_back(FIXTURE).unwrap();
425        let r = get(&records, "report 2.pdf");
426        assert_eq!(r.original_name.as_deref(), Some("report.pdf"));
427        assert_eq!(
428            r.original_path().as_deref(),
429            Some("/Users/4n6h4x0r/Documents/report.pdf")
430        );
431    }
432
433    /// Bad magic is a typed error carrying the offending bytes, not a panic.
434    #[test]
435    fn bad_magic_is_error() {
436        let data = vec![0u8; 64];
437        assert!(matches!(
438            parse_put_back(&data).unwrap_err(),
439            DsStoreError::BadMagic { .. }
440        ));
441    }
442
443    /// A header-length-only / truncated file errors rather than panicking.
444    #[test]
445    fn truncated_is_error_not_panic() {
446        assert!(parse_put_back(&FIXTURE[..20]).is_err());
447        assert!(parse_put_back(&[]).is_err());
448    }
449
450    /// Firmlink normalisation is independent of the trailing slash and tolerates
451    /// a non-firmlink absolute path.
452    #[test]
453    fn firmlink_normalisation() {
454        assert_eq!(
455            normalize_firmlink("System/Volumes/Data/Users/x/Desktop/"),
456            "/Users/x/Desktop/"
457        );
458        assert_eq!(normalize_firmlink("/Users/x/Desktop/"), "/Users/x/Desktop/");
459    }
460
461    /// A `.DS_Store` carrying one record of every non-`ustr` data type (bool,
462    /// long, shor, type, comp, dutc, blob) is walked without error: those records
463    /// are consumed and skipped, leaving the two put-back items.
464    #[test]
465    fn skips_all_non_ustr_data_types() {
466        const TYPES: &[u8] = include_bytes!("../tests/data/putback_types.DS_Store");
467        let records = parse_put_back(TYPES).unwrap();
468        assert_eq!(records.len(), 2);
469        assert_eq!(
470            get(&records, "a.jpg").original_name.as_deref(),
471            Some("a.jpg")
472        );
473    }
474
475    /// `original_path` inserts a `/` when the put-back location does not end in one.
476    #[test]
477    fn original_path_adds_separator_when_missing() {
478        let pb = PutBack {
479            trash_name: "x".into(),
480            original_name: Some("file.txt".into()),
481            original_location: Some("System/Volumes/Data/Users/x/Desktop".into()), // no trailing slash
482        };
483        assert_eq!(
484            pb.original_path().as_deref(),
485            Some("/Users/x/Desktop/file.txt")
486        );
487    }
488
489    /// A header whose two root-offset copies disagree is rejected with
490    /// `RootOffsetMismatch`, not silently trusted.
491    #[test]
492    fn mismatched_root_offsets_is_error() {
493        let mut data = FIXTURE.to_vec();
494        // Header: offset@8..12, size@12..16, offset-copy@16..20 (big-endian). Flip
495        // one byte of the copy so it differs from the first.
496        data[19] ^= 0xFF;
497        assert!(matches!(
498            parse_put_back(&data).unwrap_err(),
499            DsStoreError::RootOffsetMismatch { .. }
500        ));
501    }
502
503    /// A root block declaring more offset entries than it can hold is rejected
504    /// before allocation, not trusted.
505    #[test]
506    fn oversized_offset_count_is_error() {
507        let mut data = FIXTURE.to_vec();
508        // Header bytes 8..12 hold the root-block offset (big-endian); the block's
509        // first u32 (at offset+4) is the entry count. Force it absurdly large.
510        let root_offset = u32::from_be_bytes([data[8], data[9], data[10], data[11]]) as usize;
511        let count_pos = root_offset + 4;
512        data[count_pos..count_pos + 4].copy_from_slice(&0x00FF_FFFFu32.to_be_bytes());
513        assert!(matches!(
514            parse_put_back(&data).unwrap_err(),
515            DsStoreError::OutOfBounds { .. }
516        ));
517    }
518}
trash_core/macos.rs

trash_core/
macos.rs
