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;
221        }
222        if visited.len() > budget {
223            return Err(DsStoreError::OutOfBounds {
224                what: "b-tree node budget",
225            });
226        }
227        let block = block_by_id(data, &offsets, node)?;
228        let mut c = Cursor::new(block);
229        let next_node = c.u32("node next pointer")?;
230        let record_count = c.u32("node record count")?;
231        for _ in 0..record_count {
232            // An internal node interleaves a child pointer before each record.
233            if next_node != 0 {
234                let child = c.u32("internal child pointer")?;
235                stack.push(child);
236            }
237            read_record(&mut c, &mut put_back)?;
238        }
239        if next_node != 0 {
240            stack.push(next_node);
241        }
242    }
243
244    Ok(put_back
245        .into_iter()
246        .map(|(trash_name, (original_name, original_location))| PutBack {
247            trash_name,
248            original_name,
249            original_location,
250        })
251        .collect())
252}
253
254/// A bounds-checked, big-endian cursor: every read returns a [`DsStoreError`]
255/// rather than panicking when the underlying slice is too short.
256struct Cursor<'a> {
257    buf: &'a [u8],
258    pos: usize,
259}
260
261impl<'a> Cursor<'a> {
262    fn new(buf: &'a [u8]) -> Self {
263        Self { buf, pos: 0 }
264    }
265
266    fn take(&mut self, n: usize, what: &'static str) -> Result<&'a [u8], DsStoreError> {
267        let end = self
268            .pos
269            .checked_add(n)
270            .ok_or(DsStoreError::OutOfBounds { what })?;
271        let slice = self
272            .buf
273            .get(self.pos..end)
274            .ok_or(DsStoreError::OutOfBounds { what })?;
275        self.pos = end;
276        Ok(slice)
277    }
278
279    fn array4(&mut self, what: &'static str) -> Result<[u8; 4], DsStoreError> {
280        let bytes = self.take(4, what)?;
281        bytes
282            .try_into()
283            .map_err(|_| DsStoreError::OutOfBounds { what })
284    }
285
286    fn u32(&mut self, what: &'static str) -> Result<u32, DsStoreError> {
287        Ok(u32::from_be_bytes(self.array4(what)?))
288    }
289
290    fn u8(&mut self, what: &'static str) -> Result<u8, DsStoreError> {
291        Ok(self.take(1, what)?[0])
292    }
293
294    fn skip(&mut self, n: usize, what: &'static str) -> Result<(), DsStoreError> {
295        self.take(n, what).map(|_| ())
296    }
297}
298
299/// Slice a buddy-allocator block out of the file. Stored offsets skip the 4-byte
300/// `00 00 00 01` prefix, so a stored offset `o` maps to file position `o + 4`.
301fn block_slice<'a>(
302    data: &'a [u8],
303    offset: u32,
304    size: u32,
305    what: &'static str,
306) -> Result<&'a [u8], DsStoreError> {
307    let start = (offset as usize)
308        .checked_add(4)
309        .ok_or(DsStoreError::OutOfBounds { what })?;
310    let end = start
311        .checked_add(size as usize)
312        .ok_or(DsStoreError::OutOfBounds { what })?;
313    data.get(start..end)
314        .ok_or(DsStoreError::OutOfBounds { what })
315}
316
317/// Look up a block by its allocator id: the offset-table entry packs the block's
318/// offset in its high bits and the base-2 log of its size in its low 5 bits.
319fn block_by_id<'a>(data: &'a [u8], offsets: &[u32], id: u32) -> Result<&'a [u8], DsStoreError> {
320    let addr = *offsets
321        .get(id as usize)
322        .ok_or(DsStoreError::OutOfBounds { what: "block id" })?;
323    let offset = addr & !0x1F;
324    let size = 1u32 << (addr & 0x1F);
325    block_slice(data, offset, size, "block")
326}
327
328/// Read one `.DS_Store` record, recording its value into `out` when it is a
329/// `ptbN` (put-back name) or `ptbL` (put-back location). Every record is fully
330/// consumed so the cursor lands on the next record.
331fn read_record(
332    c: &mut Cursor,
333    out: &mut BTreeMap<String, (Option<String>, Option<String>)>,
334) -> Result<(), DsStoreError> {
335    let nlen = c.u32("record name length")? as usize;
336    let name_bytes = c.take(2 * nlen, "record name")?;
337    let filename = decode_utf16be(name_bytes);
338    let code = c.array4("record code")?;
339    let typecode = c.array4("record data type")?;
340    let value = read_value(c, typecode)?;
341    match &code {
342        b"ptbN" => out.entry(filename).or_default().0 = value,
343        b"ptbL" => out.entry(filename).or_default().1 = value,
344        _ => {}
345    }
346    Ok(())
347}
348
349/// Consume a record's typed value, returning the decoded string for the
350/// `ustr` type (the only type `ptbN`/`ptbL` use) and `None` for the others.
351fn read_value(c: &mut Cursor, typecode: [u8; 4]) -> Result<Option<String>, DsStoreError> {
352    match &typecode {
353        b"bool" => c.skip(1, "bool value").map(|()| None),
354        b"long" | b"shor" | b"type" => c.skip(4, "fixed value").map(|()| None),
355        b"comp" | b"dutc" => c.skip(8, "8-byte value").map(|()| None),
356        b"blob" => {
357            let vlen = c.u32("blob length")? as usize;
358            c.skip(vlen, "blob value").map(|()| None)
359        }
360        b"ustr" => {
361            let vlen = c.u32("ustr length")? as usize;
362            let bytes = c.take(2 * vlen, "ustr value")?;
363            Ok(Some(decode_utf16be(bytes)))
364        }
365        other => Err(DsStoreError::UnknownDataType { typecode: *other }),
366    }
367}
368
369/// Decode a UTF-16 big-endian byte slice, lossily replacing invalid sequences
370/// with U+FFFD. A trailing odd byte is ignored.
371fn decode_utf16be(bytes: &[u8]) -> String {
372    let units: Vec<u16> = bytes
373        .chunks_exact(2)
374        .map(|pair| u16::from_be_bytes([pair[0], pair[1]]))
375        .collect();
376    String::from_utf16_lossy(&units)
377}
378
379#[cfg(test)]
380mod tests {
381    use super::*;
382
383    /// A real `.DS_Store` minted by al45tair's `ds_store` library (the oracle),
384    /// carrying two put-back items plus one non-put-back (`Iloc` blob) record.
385    const FIXTURE: &[u8] = include_bytes!("../tests/data/putback.DS_Store");
386
387    fn get<'a>(records: &'a [PutBack], name: &str) -> &'a PutBack {
388        records.iter().find(|r| r.trash_name == name).unwrap()
389    }
390
391    /// The two put-back items are recovered; the `Iloc` blob record is skipped.
392    #[test]
393    fn recovers_both_put_back_items() {
394        let records = parse_put_back(FIXTURE).unwrap();
395        assert_eq!(records.len(), 2);
396    }
397
398    /// A clean item: trash name == original name, firmlink location normalised,
399    /// full original path reconstructed. Values match the oracle decode.
400    #[test]
401    fn clean_item_decodes_to_oracle_values() {
402        let records = parse_put_back(FIXTURE).unwrap();
403        let r = get(&records, "Reference Letter.png");
404        assert_eq!(r.original_name.as_deref(), Some("Reference Letter.png"));
405        assert_eq!(
406            r.original_location.as_deref(),
407            Some("System/Volumes/Data/Users/4n6h4x0r/Downloads/")
408        );
409        assert_eq!(
410            r.original_path().as_deref(),
411            Some("/Users/4n6h4x0r/Downloads/Reference Letter.png")
412        );
413    }
414
415    /// A Finder-deduped item: the trash name (`report 2.pdf`) diverges from the
416    /// original name (`report.pdf`) — the reader reports both faithfully.
417    #[test]
418    fn deduped_trash_name_diverges_from_original() {
419        let records = parse_put_back(FIXTURE).unwrap();
420        let r = get(&records, "report 2.pdf");
421        assert_eq!(r.original_name.as_deref(), Some("report.pdf"));
422        assert_eq!(
423            r.original_path().as_deref(),
424            Some("/Users/4n6h4x0r/Documents/report.pdf")
425        );
426    }
427
428    /// Bad magic is a typed error carrying the offending bytes, not a panic.
429    #[test]
430    fn bad_magic_is_error() {
431        let data = vec![0u8; 64];
432        assert!(matches!(
433            parse_put_back(&data).unwrap_err(),
434            DsStoreError::BadMagic { .. }
435        ));
436    }
437
438    /// A header-length-only / truncated file errors rather than panicking.
439    #[test]
440    fn truncated_is_error_not_panic() {
441        assert!(parse_put_back(&FIXTURE[..20]).is_err());
442        assert!(parse_put_back(&[]).is_err());
443    }
444
445    /// Firmlink normalisation is independent of the trailing slash and tolerates
446    /// a non-firmlink absolute path.
447    #[test]
448    fn firmlink_normalisation() {
449        assert_eq!(
450            normalize_firmlink("System/Volumes/Data/Users/x/Desktop/"),
451            "/Users/x/Desktop/"
452        );
453        assert_eq!(normalize_firmlink("/Users/x/Desktop/"), "/Users/x/Desktop/");
454    }
455}
trash_core/macos.rs

trash_core/
macos.rs
