Struct Tree 

pub struct Tree { /* private fields */ }

The pruned filesystem tree produced by a walk.

Implementations

impl Tree

pub fn new(root: impl Into<PathBuf>) -> Self

An empty tree rooted at root.

pub fn insert(&mut self, hit: Hit) -> Option<NodeId>

Files a hit, creating any missing ancestors and adding its bytes to each of them.

Returns None, without changing the tree, if the hit is not under the root. The walker turns that into a reported error rather than dropping the hit silently.

pub fn price(&mut self, path: &Path, size: Size) -> Option<NodeId>

Puts a number on a claim that was filed without one, and adds it to every ancestor.

This is the other half of streaming: a claim is published as soon as it is judged and priced afterwards, so the tree has to be able to learn a size for a node it already holds. The rollup stays correct after this as it does after Tree::insert, because the ancestor chain is the same one the insert walked.

Returns None, changing nothing, when the path is not a claim in this tree or already carries a size. Both would be a caller error rather than a fact about the filesystem, and pricing one claim twice would count its bytes twice — so it is refused rather than absorbed, exactly as an out-of-root insert is.

pub fn shrink(&mut self, path: &Path, bytes: u64) -> Option<NodeId>

Takes bytes off a claim that is still there, and off every ancestor with it.

What a partial removal is, seen from here. A sweep that went into a target and came out again — a checkout inside it, an unreadable corner — leaves a directory that still exists and is smaller than it was, which is a state Tree::remove cannot express and Tree::price refuses to. Without it the reduction can only live in the front end’s per-frame progress, and progress is by definition dropped when the batch reports: the row and its ancestors would spring back to their original sizes the moment a removal finished, so a half-emptied directory would report its full weight and the headline reclaimable figure would rise after a delete. That is the one direction a tool that deletes may not be wrong in.

Clamped at the claim’s own size rather than saturating on each ancestor separately: a deduction bigger than the claim would leave every rollup above it disagreeing with the sum of what is beneath, and a rollup that cannot be re-derived from its children is the bug Tree::remove’s mtime recomputation exists to avoid.

Returns None, changing nothing, when the path is not a claim in this tree or carries no size — an unpriced claim has contributed no bytes to anything, so there are none to take back off.

pub fn remove(&mut self, path: &Path) -> Option<NodeId>

Takes a claim out of the tree, with everything it was contributing to its ancestors.

This is what a deletion is, seen from here, and it is the only way a node ever leaves. A directory that has been removed is not a row that should be marked, counted or cursored onto, and the front end learns each removal as the deleter finishes it — so the tree has to lose one claim at a time while a reader is looking at it.

An ancestor with nothing left beneath it goes too, up to but never including the root. The tree’s whole premise is that a path only appears because something reclaimable is under it; a directory that kept a row after its last claim was deleted would be the one row on screen that offers nothing.

The node is detached rather than taken out of the arena, because NodeId promises to stay valid for the life of the tree and the front end holds ids across frames — marks, the expansion set, the cursor. Compacting would silently point every one of them at a different directory. The cost is one dead Node per deleted claim, which is bounded by what the reader deleted this session.

Returns the nearest ancestor still standing, so a caller that was looking at the row has somewhere to look now. None, changing nothing, if the path is not a claim in this tree.

pub fn root(&self) -> NodeId

The root node’s id.

pub fn node(&self, id: NodeId) -> &Node

The node behind an id.

Panics

If id did not come from this tree.

pub fn children(&self, id: NodeId) -> &[NodeId]

A node’s children.

Panics

If id did not come from this tree.

pub fn find(&self, path: &Path) -> Option<NodeId>

Looks a node up by path.

pub fn is_attached(&self, id: NodeId) -> bool

Whether this id still names a directory in the tree, rather than one the deleter has taken away. See Tree::remove.

Panics

If id did not come from this tree.

pub fn root_path(&self) -> &Path

The scan root.

pub fn reclaimable(&self) -> u64

Total measured bytes reclaimable anywhere under the root.

pub fn unmeasured(&self) -> usize

How many claims in the whole tree have no size yet.

pub fn claims(&self) -> usize

How many claims the whole tree holds.

pub fn len(&self) -> usize

The number of directories in the tree, the root included.

What is still there: a claim the deleter has removed stops counting the moment it is reported, along with any ancestor it was the last thing under.

pub fn minted(&self) -> usize

How many NodeIds have ever been handed out.

Every id below this has named a directory at some point and no id above it has, so a caller holding the value from a moment ago knows exactly which nodes appeared since: they are the ids in between. That is what lets the front end light a newly found row without the tree having to report arrivals, and it works because ids are minted in order and Tree::remove detaches rather than recycles.

pub fn stamp(&self, id: NodeId) -> u64

Which change was the last one at or below id.

The question is “has anything under this directory moved since I last looked”, and the answer is this number being different — not bigger, though it always is. It is exact in both directions, which is the whole point: a summary of what is under a node (bytes, claims, how many are unpriced) is three numbers that a deletion and an arrival in the same frame put back exactly where they were, and a caller that spends a megabyte redrawing a picture is a caller that would then not redraw it.

Free to maintain, because every rollup here already walks the chain from the claim to the root — a claim’s bytes reach the root the same way this does. So it costs one store per ancestor on a write and nothing at all on a read, where asking the same question by rebuilding what the caller draws costs whatever that is.

What it deliberately does not report is Tree::sort_by, which moves children about without changing what is under anybody. A caller whose output depends on sibling order has to watch the sort itself.

Panics

If id did not come from this tree.

pub fn is_empty(&self) -> bool

Whether there is nothing left to reclaim — either the walk found nothing, or everything it found has been deleted.

pub fn sort_by(&mut self, sort: Sort)

Sorts every node’s children, deepest-first order within each level.

Per level, because a tree and a global sort are not compatible: children have to stay under their parent, so the only ordering a tree can express is a sibling ordering.

Every order breaks its ties by name and every one of them is total, which matters more here than in a batch listing: the front end re-sorts as prices land, and two rows that compare equal under a sort that stopped at the key would swap places on an unrelated arrival — a row moving under the cursor for no reason a reader can see.

Trait Implementations

impl Debug for Tree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.