build tool is now blocked on file-based checksum and i am L O C K E D the fuck in
15
Replies
4
Boosts
directory checksum is otherwise solved, for simple trees as well as arbitrary cyclic directed graphs. hashing a cyclic graph is much less difficult than everyone makes it out to be
the reason cycles are difficult is because it breaks a hidden invariant of every single tree that is deeply nonobvious yet extraordinarily simple to prove: in a tree, every vertex is the root
@hipsterelectron You're cooking, but to be perfectly honest I genuinely thought that was supremely obvious. That's pretty much what every elegant algorithm on trees relies on, it's why you can implement such algorithms trivially with a stack (and even collapse the tree away by making it implicit from some generating data).
this is not novel, that's a well-known fun fact. jeremy spinrad was clearly delighted to mention it in lecture
what "every vertex is the root" means is that the path from the root (any vertex) to any other vertex (leaf or otherwise) is unique. and this uniqueness makes hashing more or less obvious (i might venture to say a little too obvious)
so if you have a cycle, that definitionally means you have more than one path universally across the graph. so you have to make a Decision
importantly, directory trees are incredibly highly structured. so not only do we have a fixed root, we have a strict requirement that all edge directions point downwards.
what is downwards? in fact, this is yet another distinction obscured by the "parent" vs "child" terminology, which describes absolutely nothing useful about the data structure
the definition of "downwards" is determined specifically by the ordering of vertices within the undirected paths generated by a breadth-first search from the fixed root (the root we were given at the start of the problem)
recall that in a tree, all paths are unique (and the converse is also true--paths are unique if and only if the graph is a tree. isn't that cute?).
as a result, the directionality between any two vertices is always fixed--hence the desire to refer to it with hierarchical terminology like "parent" and "child"
but note that this "parent"/"child" terminology is a relative distinction, and says nothing about the identity of each vertex.
in fact, in every filesystem, this is what an "inode" designates--a unique vertex identifier. but this isn't exposed in any useful way at all
i have crashed out about the inode deception many times
anyway, the problem statement that gives you a "root" (i.e. a specific inode to start your paths from--that's all the / directory is, in a virtualized/sandboxed scenario) makes this problem fully deterministic. this requires another small but important inference, which is that directory cycles must necessarily occur as the result of a depth-first traversal
(i said "breadth-first" earlier, which was actually wrong, but only because the distinction didn't matter at all there)
this is to say: directory traversals from a fixed root do not consider arbitrary "back edges" (not yet). and a cycle therefore only arises if you can keep going "downwards" and find a vertex you've seen before
in fact i was boasting earlier. i totally don't know how directory cycles should work yet
but instead of going downwards, what happens if we went upwards from the leaves?
importantly, leaves are definitionally files and not directories. so we're not repeating ourselves the same way.
and more importantly, we have no choice about how we pick the upward path from a leaf!
