build tool is now blocked on file-based checksum and i am L O C K E D the fuck in
8
Replies
6
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
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
@hipsterelectron It is genuinely a shame what happened to the Zig Zag man re public trashing and his subsequent descent into madness, because to me his n-dimensional structure as a basis for relating objects in a system was always obviously far more powerful for ensuring fast access to related items. The "problem" was that it was more difficult to enforce a hierarchical relation with it, which is key to a vertical corporate application infrastructure. That's the secret history of xerox parc in a nutshell though, which I'm sure you know.
@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).
