build tool is now blocked on file-based checksum and i am L O C K E D the fuck in
5
Replies
3
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)
