mapsize/ARCHITECTURE.md

mapsize architecture

This document describes how mapsize is put together and the invariants each part relies on. It is kept in sync with the code; if they disagree, the code is wrong or this file is stale — fix one of them.

src/main.rs        CLI entry point, flag parsing
src/app.rs         mode selection: TUI, reports, snapshots, comparison
src/brand.rs       product name / file extensions (rename in one place)
src/inventory/     flat node store, aggregation, indexes, categories
src/scan.rs        bounded concurrent scanner (controller + workers)
src/cancel.rs      cancellation token shared by scans and background work
src/platform.rs    OS-specific metadata and file operations (cfg blocks)
src/treemap/       squarified layout, LOD, spatial navigation (pure geometry)
src/filter/        query lexer / parser / evaluator
src/snapshot/      versioned binary snapshot format + comparison
src/duplicate.rs   staged duplicate detection
src/export.rs      JSON / CSV / text reports
src/config.rs      settings, themes, JSON config file
src/tui/           event loop, model, canvas renderer, views, modals
src/textutil.rs    display sanitising, width-aware truncation, units
examples/treegen   synthetic test-tree generator
examples/bench     in-process benchmarks

Dependency direction is strictly downward: tui → (treemap, filter, inventory, scan, …); scan → (inventory, platform); treemap depends on nothing but the standard library. The terminal library (crossterm) is only used by tui.

Inventory representation

inventory.Tree is an append-only arena of Node records addressed by NodeId (u32). Nodes are stored in fixed-size chunks (Vec<Vec<Node>>, 65 536 nodes per chunk), so growing the arena never copies or moves existing nodes and peak memory never doubles during growth.

A node holds: parent ID, first-child / next-sibling IDs (an intrusive child list — no per-directory vectors), name (the single path component as raw bytes, not the full path), kind, flags, own logical size, own allocated size, mtime, mode, uid/gid, link count, and aggregates (total logical, total allocated, file count, directory count, error count). Directory-only data — per-category byte totals used for colouring — lives in a side table indexed by a directory index, so files do not pay for it.

Full paths are never stored; Tree.Path(id) walks parents. Extensions are interned into a small table and stored as a u16. All sizes are i64.

Node IDs are stable for the lifetime of a Tree: nodes are never removed or reordered. A rescan produces a new Tree. This is what makes selection persistence trivial (see below).

Scanner worker architecture

               +------------------ controller thread ---------------------+
               |  owns: Tree (write lock), pending FIFO of dir NodeIDs,   |
               |        hard-link table, visited-dir table               |
               +----------------------------------------------------------+
                  | jobs (bounded channel, cap = workers*2) ^ results (bounded channel)
                  v                                        |
             worker 1 .. worker N  (fixed pool, N from --workers / mode)

• Workers do I/O only: open a directory, read entries in chunks of up to 1024, lstat each entry (relative to the directory fd where the platform allows), and send a result chunk back. Workers never touch the Tree.
• The controller is the only writer of the Tree. It applies result chunks, creates child nodes, assigns IDs, propagates aggregate deltas, and decides which subdirectories become new jobs.
• Worker count: conservative = 2, balanced = min(8, 2×CPU), aggressive = min(64, 8×CPU), or an explicit number. More is not always faster — on rotational media 2–4 is often best.

Bounded directory scheduling (no deadlock under backpressure)

The classic deadlock is: workers block sending new work into a full queue while the only consumer of that queue is also blocked. mapsize avoids it by construction:

• Only the controller produces jobs. Workers only produce results.
• The controller's main loop is a single crossbeam_channel::Select that simultaneously offers the next pending job to the bounded jobs channel and receives from the bounded results channel. It never performs a blocking send without also being ready to receive. Therefore a worker blocked on results <- is always eventually served, and the controller is never blocked on jobs <- alone.
• Discovered-but-unscheduled directories wait in the controller's pending FIFO as 4-byte NodeIDs (paths are rebuilt at dispatch). Its size is bounded by the number of directory nodes already in the inventory, so it adds O(1) bytes per directory on top of memory we already spend.
• FIFO order means the scan is roughly breadth-first: every top-level directory starts growing early, which is what makes the live treemap informative.

Huge directories are streamed: a worker sends a result per 1024 entries, so a directory with 5 M entries neither balloons worker memory nor stalls the UI.

Completion: the controller tracks inflight (dispatched directories whose final chunk has not arrived). The scan is finished when pending is empty and inflight == 0. Cancellation (cancel::Cancel, which the controller also selects on) stops dispatch immediately; workers check the token between chunks, and the controller drains outstanding results and joins every worker, so no thread leaks.

Stress tests (scan::tests) run with 1 worker and job/result channel capacity 1 over trees with thousands of directories to prove progress under maximum backpressure.

Concurrent aggregation strategy

Because the controller is the single writer, aggregation needs no atomics. For each result chunk it sums the chunk's file sizes, allocated sizes, counts and per-category bytes once, then walks the ancestor chain adding that one delta. Cost is O(depth) per 1024-entry chunk rather than O(depth) per file — for a 1 M-file tree at depth 20 that is ~20 K ancestor updates instead of ~20 M. There is no reconciliation pass: totals are exact at every moment for the data seen so far.

The tree is shared as Arc<RwLock<Tree>>. The UI reads it under the read lock; the controller applies batches of results under the write lock, holding it for at most a few milliseconds (it releases the lock between batches). This is the only lock in the data path.

Concurrency invariants

1. Only the scan controller (or a snapshot loader before publication) mutates a Tree.
2. Every read of Tree node data from another thread holds the read lock.
3. Nodes are never deleted; a NodeID once observed stays valid.
4. Workers share nothing mutable except the bounded channels and atomic progress counters.
5. No thread ever takes the read lock while already holding it. The standard RwLock may block new readers once a writer waits, so a recursive read lock can deadlock against the scan controller. The TUI takes the lock once per entry point (render, key and mouse handlers) and passes &Tree to the helpers it calls. Background tasks (filter, duplicates, snapshot save) take their own lock on their own thread.
6. After a scan finishes, the UI thread may become the writer (move to trash updates aggregates under the write lock). Trash is refused while scanning.

Hard links and sizes

• Logical size = st_size. Allocated size = st_blocks × 512 on Unix. On Windows allocated size is reported as unknown (equal to logical, flagged) because getting it costs an extra handle-open per file.
• For regular files with link count > 1, the controller keys (dev, inode). The first path seen contributes to directory aggregates; later paths are flagged HardlinkDup and contribute zero to aggregates (their own size is still shown). Which path is "first" depends on scan order and is not deterministic. This matches du's default semantics.
• Windows does not expose link counts from directory enumeration, so hard links are not deduplicated there. This is documented, not hidden.

Symlinks, mount points, exclusions

• --follow-symlinks=none (default): symlinks are leaf nodes counted at their own (tiny) size. same-filesystem / all follow directory symlinks; every descended directory's (dev, inode) is recorded and a directory already visited is never descended twice — loops terminate and nothing is counted twice. On platforms without inode identity (Windows, other portable fallbacks) loop detection is impossible, so symlinks are never followed there and scan info says so.
• A directory whose device differs from its parent is flagged MountPoint. With --one-file-system it is not descended. On Linux, virtual filesystems (proc, sysfs, cgroup, debugfs, …) are never descended — /proc/kcore would otherwise dominate any scan of / — and are reported in scan info.
• --exclude PATTERN: patterns containing a path separator match full paths; others match the entry name with glob semantics. Excluded entries are counted and the UI shows that exclusions are active.

TUI event flow

scan controller ──(applies under write lock)──> Tree
       │ atomic progress counters
       ▼
tick (10 Hz while scanning) ─────┐
crossterm events (input thread) ─┼─> select ─> Model::update ─> state change ─> frame dirty
background task results ─────────┘
render: if dirty → read-lock tree → layout (if layout dirty) → paint canvas → write changed lines

tui::run puts the terminal in raw mode on the alternate screen and selects over three crossbeam channels: terminal events from a dedicated input thread, a timer tick, and messages from background tasks (filter, duplicates, snapshot save, scan done). There is never one message per file: the scanner does not talk to the UI at all except for the scan-done notification. The UI polls its progress counters at a fixed rate.

The model caches the rendered frame and only repaints when something visible changed; several updates in a row cost at most one render.

Expensive per-directory work (sorting children by size) is cached per data version. During a scan the version advances at most every 400 ms, so the layout does not jitter at frame rate even though labels and counters update at the 10 Hz refresh.

A panic hook restores the terminal (leaves the alternate screen, disables raw mode and mouse reporting) before the panic is reported; SIGTERM quits cleanly.

Rendering: the canvas

All drawing goes to an in-memory Canvas of cells (grapheme, fg, bg, attrs). Views and modals paint into the canvas; the canvas is serialised with minimal SGR changes, converted to the detected colour profile (truecolour / 256 / 16 / none), and only the changed span of each changed line is written, inside a synchronized-output block where the terminal supports it. The drawing code uses RGB throughout. For 256-colour terminals the canvas quantizes colours itself (redmean distance over the 6×6×6 cube and grey ramp, never the palette-dependent first 16 entries): the stock conversion maps dark tints to saturated olive/navy and destroys the shading. For 16 colours, dark shades map to black, greys to the grey entries, and saturated colours keep their hue, so shadows stay quiet and categories stay distinguishable. --color overrides detection (useful over SSH, where COLORTERM is often not forwarded). NO_COLOR selects the mono theme, which relies on attributes and glyphs only. Selection never relies on colour alone: the selected rectangle uses a double-line border, bold reversed title and a status-line description.

Treemap algorithm

treemap.Squarify implements Bruls, Huizing & van Wijk's squarified layout on float rectangles: items sorted by size descending are added to the current row while the worst aspect ratio improves; then the row is laid out along the shorter side. Float rectangles are snapped to the cell grid by rounding the edges (not the widths), so neighbouring rectangles share edges exactly — no gaps, no overlaps. Layout is deterministic (stable sort by size, then ID).

Nested levels are laid out recursively inside each block's interior (inside its border) while the interior is large enough to be useful.

Level-of-detail model

A 160×50 terminal has 8 000 cells; the tree may have millions of entries. For each directory being laid out, children are reduced to the top K by size using a bounded heap (O(n log K)). Children whose proportional area would be smaller than a minimum useful block (a few cells), or beyond K, are merged into one synthetic group block ("312 smaller items, 8.4 GiB"). Zooming into a directory gives its children the whole screen, so they become individually visible. Groups are selectable and inspectable.

Spatial navigation algorithm

treemap::neighbour(blocks, selected, dir) is pure geometry:

1. Candidates must lie in the requested half-plane: for RIGHT, c.X ≥ sel.X + sel.W − tolerance (with the candidate's centre to the right of the selected centre).
2. Each candidate is scored by the primary-axis gap (edge to edge) plus a penalty for the orthogonal offset. Candidates overlapping the selected rectangle's orthogonal span get the offset term set to zero and are preferred over any non-overlapping candidate.
3. Among overlapping candidates, the one whose overlap is largest relative to the source, then nearest to the source's centre line, wins.
4. Ties are broken by top-left position, then NodeID — fully deterministic.

Terminal resize architecture

A resize event only records the new size and marks layout dirty. The next render recomputes panel geometry for the new size class (large / medium / small / too-small), reruns the treemap layout for the new treemap rectangle (never stretches old coordinates), and repaints. Because work happens only at render time and the frame cache absorbs repeated calls, a storm of resize events costs at most one layout per rendered frame. Modal geometry is derived from the current size every frame, clamped to the screen, and becomes scrollable when content does not fit.

Selection persistence

Selection is a NodeId (or, for the synthetic LOD group, -1 - parent). Until the user moves the selection it follows the largest block, which changes while a scan runs; after that it is sticky. After any relayout the renderer looks the ID up in the new rectangle list. If it is absent (filtered out, collapsed into a group, zoom changed) selection falls back to: the group containing it, then its nearest visible ancestor, then the largest block.

Modal architecture

A modal is a small trait: title(), content(width), footer(), and key. A generic frame renders any modal centred, clamped to the screen (min 1-cell margin), with a scrollable viewport when content exceeds height. The base screen is dimmed before the modal is painted. While a modal is open it receives all keys; Esc always closes it.

OS abstraction

platform exposes read_dir(path, chunk, |entries| …), stat/lstat, Meta, trash, delete, reveal and name lookups. platform/unix.rs and platform/windows.rs hold the implementations:

• Linux — readdir on an O_DIRECTORY descriptor + statx (via the raw system call, so static musl builds work) relative to that descriptor: one system call per entry, birth time included; fstatat if the kernel lacks statx. Virtual filesystems are detected with statfs. freedesktop.org trash; xdg-open reveals.
• macOS, FreeBSD, NetBSD — the same descriptor-relative walk with fstatat. macOS moves items to ~/.Trash (or the volume's .Trashes) and reveals with open -R; the BSDs have no trash or reveal, so d is only offered as a permanent delete when headless.
• Windows — std::fs::read_dir and metadata. Allocated size is reported as unknown and there is no inode identity, so hard links are not deduplicated and symlinks and junctions are never followed. The Recycle Bin (SHFileOperationW) and explorer /select, reveal; permanent delete is not offered.

The terminal code has the only other cfg blocks (signals and writing the restore sequence).

Security handling for hostile filenames

Filenames and snapshot contents are untrusted.

• Every string that reaches the terminal passes through textutil::sanitize, which replaces C0/C1 control characters (including ESC, CSI, BEL, DEL) with visible escapes (\x1b), replaces invalid UTF-8 with U+FFFD, and neutralises bidi override characters. The canvas also refuses control characters as a second line of defence. Internal names keep the raw bytes.
• Text is clipped by display width (grapheme clusters, East-Asian wide characters) so labels never overflow their rectangle.
• Snapshot decoding validates magic, version, every length, every parent reference (a parent must precede its child, so cycles are impossible), depth (≤ 4096 levels, bounding recursion in exporters), per-node sizes (≤ 1 EiB) and node count (at most one node per byte of snapshot file, 1 Mi floor); caps the decompressed body at 64× the file size (decompression bombs fail fast); and verifies a SHA-256 trailer. Aggregates are recomputed with saturating arithmetic rather than trusted.
• No shell is ever invoked. "Open/reveal" and trash use std::process::Command with argument vectors or native APIs; paths are passed as single arguments.
• Permanent delete (headless only) checks the item's owner and type against the scan and removes it through descriptors opened from the parent directory without following symlinks (openat/unlinkat with O_NOFOLLOW), so a symlink swapped in since the scan cannot redirect it.
• --read-only disables every mutating action in the UI.