Daniel Carrera <[email protected]> writes: > The reason I ask is that I want to figure out whether every patch has a > unique set of dependencies or not. If the list of dependencies is > unique, I have a potential idea for making unique hashes+signatures: > > * I'm going to define the hash H which I hope will be uniquely > defined for any patch. If H is unique, we can sign H. > > Definition: Given a patch U... > > 1. If U has no dependencies, let H_u = SHA1(U') where U' is U applied to > the empty repository. > > 2. If U has dependencies, find the minimal set of patches needed for U. > In other words, commute away everything that can be commuted. This > leaves us with something like this: ABCDU'. This is not uniquely > defined. For example, A and B might commute, so that B'A'CDU' is equally > acceptable. But in either case, U' will look the same (right?). Now we > can define H_u: > > H_u = SHA1( join(sort(H_a,H_b,H_c,H_d)) ++ SHA1(U')) > > In other words, take the H hashes for A-D, sort them alphabetically, > concatenate them, concatenate that with SHA1(U'). > > In this way, the hash H for any patch depends on that patch's > dependencies. But you can see that this is only well defined if the > concept of "that patch's dependencies" is well defined, and it isn't if > we can replace patch A by patch X.
Correct me if i'm saying rubbish, but: I think that the problem with that approach is that hash verification is exponential: in order to check that your hash is good, i have to put U in the same context as you in order to get U', that is, put A B C and D in the same order. As I have no way to know in what order you saw them, I have to try them all… Maybe there is a way to normalise that, for example by requiring that ABCD is "pseudo-sorted": every pair of adjacent patches is either dependent on each-other or in hash-alphabetical-order. This still makes computing and checking hashes quadratic in the length of ABCD. Florent _______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
