* [PATCH] diff: add a config option to control orderfile @ 2013-08-31 19:44 Michael S. Tsirkin 2013-09-03 17:12 ` Junio C Hamano 0 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-08-31 19:44 UTC (permalink / raw) To: git I always want my diffs to show header files first, then .c files, then the rest. Make it possible to set orderfile though a config option to achieve this. Signed-off-by: Michael S. Tsirkin <mst@redhat.com> --- diff.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/diff.c b/diff.c index 208094f..cca0767 100644 --- a/diff.c +++ b/diff.c @@ -264,6 +264,9 @@ int git_diff_basic_config(const char *var, const char *value, void *cb) return 0; } + if (!strcmp(var, "diff.orderfile")) + return git_config_string(&default_diff_options.orderfile, var, value); + if (!prefixcmp(var, "submodule.")) return parse_submodule_config_option(var, value); -- MST ^ permalink raw reply related [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-08-31 19:44 [PATCH] diff: add a config option to control orderfile Michael S. Tsirkin @ 2013-09-03 17:12 ` Junio C Hamano 2013-09-03 21:08 ` Michael S. Tsirkin 0 siblings, 1 reply; 32+ messages in thread From: Junio C Hamano @ 2013-09-03 17:12 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: git "Michael S. Tsirkin" <mst@redhat.com> writes: > I always want my diffs to show header files first, > then .c files, then the rest. Make it possible to > set orderfile though a config option to achieve this. > > Signed-off-by: Michael S. Tsirkin <mst@redhat.com> > --- I admit that I was the guilty one who introduced the orderfile, but I think the feature was misguided (for one thing, it breaks the patch-id, I think). So I am moderately hesitant to promote its use with an addition like this. > diff.c | 3 +++ > 1 file changed, 3 insertions(+) > > diff --git a/diff.c b/diff.c > index 208094f..cca0767 100644 > --- a/diff.c > +++ b/diff.c > @@ -264,6 +264,9 @@ int git_diff_basic_config(const char *var, const char *value, void *cb) > return 0; > } > > + if (!strcmp(var, "diff.orderfile")) > + return git_config_string(&default_diff_options.orderfile, var, value); > + > if (!prefixcmp(var, "submodule.")) > return parse_submodule_config_option(var, value); ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-03 17:12 ` Junio C Hamano @ 2013-09-03 21:08 ` Michael S. Tsirkin 2013-09-15 7:49 ` Michael S. Tsirkin 0 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-03 21:08 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Tue, Sep 03, 2013 at 10:12:18AM -0700, Junio C Hamano wrote: > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > I always want my diffs to show header files first, > > then .c files, then the rest. Make it possible to > > set orderfile though a config option to achieve this. > > > > Signed-off-by: Michael S. Tsirkin <mst@redhat.com> > > --- > > I admit that I was the guilty one who introduced the orderfile, but > I think the feature was misguided (for one thing, it breaks the > patch-id, I think). This should be easy to fix - just sort before applying the ID, no? > So I am moderately hesitant to promote its use > with an addition like this. The status quo just makes people insist on using a script to generate patches for mail. Some projects put interface documentation in the header files, in that case it makes sense to put .h before .c in the patch as it makes review easier. In fact I sometimes reorder chunks in the patch manually for readability - it's probably worth finding a way to support this. > > diff.c | 3 +++ > > 1 file changed, 3 insertions(+) > > > > diff --git a/diff.c b/diff.c > > index 208094f..cca0767 100644 > > --- a/diff.c > > +++ b/diff.c > > @@ -264,6 +264,9 @@ int git_diff_basic_config(const char *var, const char *value, void *cb) > > return 0; > > } > > > > + if (!strcmp(var, "diff.orderfile")) > > + return git_config_string(&default_diff_options.orderfile, var, value); > > + > > if (!prefixcmp(var, "submodule.")) > > return parse_submodule_config_option(var, value); ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-03 21:08 ` Michael S. Tsirkin @ 2013-09-15 7:49 ` Michael S. Tsirkin 2013-09-15 8:08 ` Michael S. Tsirkin 0 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-15 7:49 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Wed, Sep 04, 2013 at 12:08:15AM +0300, Michael S. Tsirkin wrote: > On Tue, Sep 03, 2013 at 10:12:18AM -0700, Junio C Hamano wrote: > > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > > > I always want my diffs to show header files first, > > > then .c files, then the rest. Make it possible to > > > set orderfile though a config option to achieve this. > > > > > > Signed-off-by: Michael S. Tsirkin <mst@redhat.com> > > > --- > > > > I admit that I was the guilty one who introduced the orderfile, but > > I think the feature was misguided (for one thing, it breaks the > > patch-id, I think). > > This should be easy to fix - just sort before applying the ID, no? Ping. Any comment on this idea? > > So I am moderately hesitant to promote its use > > with an addition like this. > > The status quo just makes people insist on using a script to generate patches for > mail. Some projects put interface documentation in the header files, in > that case it makes sense to put .h before .c in the patch as it makes > review easier. > > In fact I sometimes reorder chunks in the patch manually for readability - > it's probably worth finding a way to support this. > > > > > diff.c | 3 +++ > > > 1 file changed, 3 insertions(+) > > > > > > diff --git a/diff.c b/diff.c > > > index 208094f..cca0767 100644 > > > --- a/diff.c > > > +++ b/diff.c > > > @@ -264,6 +264,9 @@ int git_diff_basic_config(const char *var, const char *value, void *cb) > > > return 0; > > > } > > > > > > + if (!strcmp(var, "diff.orderfile")) > > > + return git_config_string(&default_diff_options.orderfile, var, value); > > > + > > > if (!prefixcmp(var, "submodule.")) > > > return parse_submodule_config_option(var, value); ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-15 7:49 ` Michael S. Tsirkin @ 2013-09-15 8:08 ` Michael S. Tsirkin 2013-09-17 16:26 ` Junio C Hamano 0 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-15 8:08 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Sun, Sep 15, 2013 at 10:49:00AM +0300, Michael S. Tsirkin wrote: > On Wed, Sep 04, 2013 at 12:08:15AM +0300, Michael S. Tsirkin wrote: > > On Tue, Sep 03, 2013 at 10:12:18AM -0700, Junio C Hamano wrote: > > > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > > > > > I always want my diffs to show header files first, > > > > then .c files, then the rest. Make it possible to > > > > set orderfile though a config option to achieve this. > > > > > > > > Signed-off-by: Michael S. Tsirkin <mst@redhat.com> > > > > --- > > > > > > I admit that I was the guilty one who introduced the orderfile, but > > > I think the feature was misguided (for one thing, it breaks the > > > patch-id, I think). > > > > This should be easy to fix - just sort before applying the ID, no? > > Ping. Any comment on this idea? Actually, after I've looked at the code, diffcore_order is already already called for patch-id. So patch-id shouldn't be broken by specifying the orderfile. Why then is the feature misguided? > > > So I am moderately hesitant to promote its use > > > with an addition like this. > > > > The status quo just makes people insist on using a script to generate patches for > > mail. Some projects put interface documentation in the header files, in > > that case it makes sense to put .h before .c in the patch as it makes > > review easier. > > > > In fact I sometimes reorder chunks in the patch manually for readability - > > it's probably worth finding a way to support this. > > > > > > > > diff.c | 3 +++ > > > > 1 file changed, 3 insertions(+) > > > > > > > > diff --git a/diff.c b/diff.c > > > > index 208094f..cca0767 100644 > > > > --- a/diff.c > > > > +++ b/diff.c > > > > @@ -264,6 +264,9 @@ int git_diff_basic_config(const char *var, const char *value, void *cb) > > > > return 0; > > > > } > > > > > > > > + if (!strcmp(var, "diff.orderfile")) > > > > + return git_config_string(&default_diff_options.orderfile, var, value); > > > > + > > > > if (!prefixcmp(var, "submodule.")) > > > > return parse_submodule_config_option(var, value); ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-15 8:08 ` Michael S. Tsirkin @ 2013-09-17 16:26 ` Junio C Hamano 2013-09-17 16:42 ` Michael S. Tsirkin 0 siblings, 1 reply; 32+ messages in thread From: Junio C Hamano @ 2013-09-17 16:26 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: git "Michael S. Tsirkin" <mst@redhat.com> writes: > Actually, after I've looked at the code, > diffcore_order is already already called for patch-id. That was a band-aid for an ill-thought-out orderfile misfeature to hide the breakage. You somehow make sure that you pass the same orderfile to diff generating machinery used internal to patch-id generation. The standalone "git patch-id" would be reading the patch in the order you give it when you are feeding a patch somebody sent you via the mailing list using an order unknown to you, no? Before making it _easier_ to use the orderfile to generate diffs, we would need to prepare the parts that will be broken by wider use of the feature. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 16:26 ` Junio C Hamano @ 2013-09-17 16:42 ` Michael S. Tsirkin 2013-09-17 17:24 ` Junio C Hamano 0 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 16:42 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Tue, Sep 17, 2013 at 09:26:13AM -0700, Junio C Hamano wrote: > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > Actually, after I've looked at the code, > > diffcore_order is already already called for patch-id. > > That was a band-aid for an ill-thought-out orderfile misfeature to > hide the breakage. You somehow make sure that you pass the same > orderfile to diff generating machinery used internal to patch-id > generation. The standalone "git patch-id" would be reading the > patch in the order you give it when you are feeding a patch somebody > sent you via the mailing list using an order unknown to you, no? Yes but that's already the case, right? People don't have to use git to generate patches. So might it not be useful to tweak patch id to sort the diff, making it a bit more stable? This means it needs to pass twice over the file, but is this a huge issue? pass 1 - get offsets of chunks and sort them pass 2 - seek each chunk and hash what do you think? > Before making it _easier_ to use the orderfile to generate diffs, we > would need to prepare the parts that will be broken by wider use of > the feature. I'll be glad to help do this if you tell me what these parts are. anything else besides fixing besides the stand-alone patch id? -- MST ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 16:42 ` Michael S. Tsirkin @ 2013-09-17 17:24 ` Junio C Hamano 2013-09-17 17:28 ` Michael S. Tsirkin 2013-09-21 21:08 ` Michael S. Tsirkin 0 siblings, 2 replies; 32+ messages in thread From: Junio C Hamano @ 2013-09-17 17:24 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: git "Michael S. Tsirkin" <mst@redhat.com> writes: > So might it not be useful to tweak patch id to > sort the diff, making it a bit more stable? That is one thing that needs to be done, I think. But it would be unfortunate if we have to do that unconditionally, though, as we may be "buffering" many hundred kilobytes of patch text in core. If we can do so without regressing the streaming performance for the most common case of not using the orderfile on the generating side (hence not having to sort on the receiving end), it would be ideal. I am not sure offhand how much code damage we are talking about, though. > I'll be glad to help do this if you tell me what these parts are. > anything else besides fixing besides the stand-alone patch id? Off the top of my head I do not think of one (but that is not a guarantee that there isn't any). ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 17:24 ` Junio C Hamano @ 2013-09-17 17:28 ` Michael S. Tsirkin 2013-09-17 18:06 ` Junio C Hamano 2013-09-21 21:08 ` Michael S. Tsirkin 1 sibling, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 17:28 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Tue, Sep 17, 2013 at 10:24:19AM -0700, Junio C Hamano wrote: > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > So might it not be useful to tweak patch id to > > sort the diff, making it a bit more stable? > > That is one thing that needs to be done, I think. But it would be > unfortunate if we have to do that unconditionally, though, as we may > be "buffering" many hundred kilobytes of patch text in core. If we > can do so without regressing the streaming performance for the most > common case of not using the orderfile on the generating side (hence > not having to sort on the receiving end), it would be ideal. I am > not sure offhand how much code damage we are talking about, though. So make it conditional on the presence of the orderefile option? > > I'll be glad to help do this if you tell me what these parts are. > > anything else besides fixing besides the stand-alone patch id? > > Off the top of my head I do not think of one (but that is not a > guarantee that there isn't any). ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 17:28 ` Michael S. Tsirkin @ 2013-09-17 18:06 ` Junio C Hamano 2013-09-17 19:25 ` Michael S. Tsirkin 2013-09-17 20:14 ` Michael S. Tsirkin 0 siblings, 2 replies; 32+ messages in thread From: Junio C Hamano @ 2013-09-17 18:06 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: git "Michael S. Tsirkin" <mst@redhat.com> writes: > On Tue, Sep 17, 2013 at 10:24:19AM -0700, Junio C Hamano wrote: >> "Michael S. Tsirkin" <mst@redhat.com> writes: >> >> > So might it not be useful to tweak patch id to >> > sort the diff, making it a bit more stable? >> >> That is one thing that needs to be done, I think. But it would be >> unfortunate if we have to do that unconditionally, though, as we may >> be "buffering" many hundred kilobytes of patch text in core. If we >> can do so without regressing the streaming performance for the most >> common case of not using the orderfile on the generating side (hence >> not having to sort on the receiving end), it would be ideal. I am >> not sure offhand how much code damage we are talking about, though. > > So make it conditional on the presence of the orderefile option? That would mean that those who set orderfile from configuration in the future will have to always suffer, I would think. Is that acceptable? I dunno. Also, if the sender used a non-standard order, the recipient does not know what order the patch was generated, and the recipient does not use a custom orderfile, what should happen? I thought your idea was to normalize by using some canonical order that is not affected by the orderfile to make sure patch-id stays stable, so I would imagine that such a recipient who does not have orderfile specified still needs to sort before hashing, no? ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 18:06 ` Junio C Hamano @ 2013-09-17 19:25 ` Michael S. Tsirkin 2013-09-17 20:14 ` Michael S. Tsirkin 1 sibling, 0 replies; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 19:25 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Tue, Sep 17, 2013 at 11:06:07AM -0700, Junio C Hamano wrote: > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > On Tue, Sep 17, 2013 at 10:24:19AM -0700, Junio C Hamano wrote: > >> "Michael S. Tsirkin" <mst@redhat.com> writes: > >> > >> > So might it not be useful to tweak patch id to > >> > sort the diff, making it a bit more stable? > >> > >> That is one thing that needs to be done, I think. But it would be > >> unfortunate if we have to do that unconditionally, though, as we may > >> be "buffering" many hundred kilobytes of patch text in core. If we > >> can do so without regressing the streaming performance for the most > >> common case of not using the orderfile on the generating side (hence > >> not having to sort on the receiving end), it would be ideal. I am > >> not sure offhand how much code damage we are talking about, though. > > > > So make it conditional on the presence of the orderefile option? > > That would mean that those who set orderfile from configuration in > the future will have to always suffer, I would think. Is that > acceptable? I dunno. Well it's just two passes over a diff. Are we optimizing this for tape based systems or something? > Also, if the sender used a non-standard order, the recipient does > not know what order the patch was generated, and the recipient does > not use a custom orderfile, what should happen? I thought your idea > was to normalize by using some canonical order that is not affected > by the orderfile to make sure patch-id stays stable, so I would > imagine that such a recipient who does not have orderfile specified > still needs to sort before hashing, no? If you like, but I don't really care. It's fine with me to make this conditional on specifying an order file on recepient side. Or we can make it a separate option. Or we can stick some hint about the order in the patch. Tell me what you prefer :) -- MST ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 18:06 ` Junio C Hamano 2013-09-17 19:25 ` Michael S. Tsirkin @ 2013-09-17 20:14 ` Michael S. Tsirkin 2013-09-17 20:16 ` Michael S. Tsirkin 1 sibling, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 20:14 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Tue, Sep 17, 2013 at 11:06:07AM -0700, Junio C Hamano wrote: > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > On Tue, Sep 17, 2013 at 10:24:19AM -0700, Junio C Hamano wrote: > >> "Michael S. Tsirkin" <mst@redhat.com> writes: > >> > >> > So might it not be useful to tweak patch id to > >> > sort the diff, making it a bit more stable? > >> > >> That is one thing that needs to be done, I think. But it would be > >> unfortunate if we have to do that unconditionally, though, as we may > >> be "buffering" many hundred kilobytes of patch text in core. If we > >> can do so without regressing the streaming performance for the most > >> common case of not using the orderfile on the generating side (hence > >> not having to sort on the receiving end), it would be ideal. I am > >> not sure offhand how much code damage we are talking about, though. > > > > So make it conditional on the presence of the orderefile option? > > That would mean that those who set orderfile from configuration in > the future will have to always suffer, I would think. Is that > acceptable? I dunno. > > Also, if the sender used a non-standard order, the recipient does > not know what order the patch was generated, and the recipient does > not use a custom orderfile, what should happen? I thought your idea > was to normalize by using some canonical order that is not affected > by the orderfile to make sure patch-id stays stable, so I would > imagine that such a recipient who does not have orderfile specified > still needs to sort before hashing, no? Thinking about it some more, it's a best effort thing anyway, correct? So how about, instead of doing a hash over the whole input, we hash each chunk and XOR them together? This way it will be stable against chunk reordering, and no need to keep patch in memory. Hmm? -- MST ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:14 ` Michael S. Tsirkin @ 2013-09-17 20:16 ` Michael S. Tsirkin 2013-09-17 20:18 ` Jeff King 2013-09-17 20:31 ` Michael S. Tsirkin 0 siblings, 2 replies; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 20:16 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Tue, Sep 17, 2013 at 11:14:01PM +0300, Michael S. Tsirkin wrote: > On Tue, Sep 17, 2013 at 11:06:07AM -0700, Junio C Hamano wrote: > > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > > > On Tue, Sep 17, 2013 at 10:24:19AM -0700, Junio C Hamano wrote: > > >> "Michael S. Tsirkin" <mst@redhat.com> writes: > > >> > > >> > So might it not be useful to tweak patch id to > > >> > sort the diff, making it a bit more stable? > > >> > > >> That is one thing that needs to be done, I think. But it would be > > >> unfortunate if we have to do that unconditionally, though, as we may > > >> be "buffering" many hundred kilobytes of patch text in core. If we > > >> can do so without regressing the streaming performance for the most > > >> common case of not using the orderfile on the generating side (hence > > >> not having to sort on the receiving end), it would be ideal. I am > > >> not sure offhand how much code damage we are talking about, though. > > > > > > So make it conditional on the presence of the orderefile option? > > > > That would mean that those who set orderfile from configuration in > > the future will have to always suffer, I would think. Is that > > acceptable? I dunno. > > > > Also, if the sender used a non-standard order, the recipient does > > not know what order the patch was generated, and the recipient does > > not use a custom orderfile, what should happen? I thought your idea > > was to normalize by using some canonical order that is not affected > > by the orderfile to make sure patch-id stays stable, so I would > > imagine that such a recipient who does not have orderfile specified > > still needs to sort before hashing, no? > > Thinking about it some more, it's a best effort thing anyway, > correct? > > So how about, instead of doing a hash over the whole input, > we hash each chunk and XOR them together? > > This way it will be stable against chunk reordering, and > no need to keep patch in memory. > > Hmm? ENOCOFFEE That was a silly suggestion, two identical chunks aren't that unlikely :) > -- > MST ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:16 ` Michael S. Tsirkin @ 2013-09-17 20:18 ` Jeff King 2013-09-17 20:38 ` Michael S. Tsirkin 2013-09-17 20:31 ` Michael S. Tsirkin 1 sibling, 1 reply; 32+ messages in thread From: Jeff King @ 2013-09-17 20:18 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: Junio C Hamano, git On Tue, Sep 17, 2013 at 11:16:04PM +0300, Michael S. Tsirkin wrote: > > Thinking about it some more, it's a best effort thing anyway, > > correct? > > > > So how about, instead of doing a hash over the whole input, > > we hash each chunk and XOR them together? > > > > This way it will be stable against chunk reordering, and > > no need to keep patch in memory. > > > > Hmm? > > ENOCOFFEE > > That was a silly suggestion, two identical chunks aren't that unlikely :) In a single patch, they should not be, as we should be taking into account the filenames, no? You could also do it hierarchically. Hash each chunk, store only the hashes, then sort them and hash the result. That still has O(chunks) storage, but it is only one hash per chunk, not the whole data. A problem with both schemes, though, is that they are not backwards-compatible with existing git-patch-id implementations. Whereas sorting the data itself is (kind of, at least with respect to people who are not using orderfile). -Peff ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:18 ` Jeff King @ 2013-09-17 20:38 ` Michael S. Tsirkin 2013-09-17 20:41 ` Michael S. Tsirkin 2013-09-17 20:56 ` Jeff King 0 siblings, 2 replies; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 20:38 UTC (permalink / raw) To: Jeff King; +Cc: Junio C Hamano, git On Tue, Sep 17, 2013 at 04:18:28PM -0400, Jeff King wrote: > On Tue, Sep 17, 2013 at 11:16:04PM +0300, Michael S. Tsirkin wrote: > > > > Thinking about it some more, it's a best effort thing anyway, > > > correct? > > > > > > So how about, instead of doing a hash over the whole input, > > > we hash each chunk and XOR them together? > > > > > > This way it will be stable against chunk reordering, and > > > no need to keep patch in memory. > > > > > > Hmm? > > > > ENOCOFFEE > > > > That was a silly suggestion, two identical chunks aren't that unlikely :) > > In a single patch, they should not be, as we should be taking into > account the filenames, no? Right. > You could also do it hierarchically. Hash each chunk, store only the > hashes, then sort them and hash the result. That still has O(chunks) > storage, but it is only one hash per chunk, not the whole data. Could be optional too :) Or maybe just sum byte by byte instead. > A problem with both schemes, though, is that they are not > backwards-compatible with existing git-patch-id implementations. Could you clarify? We never send patch IDs on the wire - how isn't this compatible? > Whereas > sorting the data itself is (kind of, at least with respect to people who > are not using orderfile). > > -Peff ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:38 ` Michael S. Tsirkin @ 2013-09-17 20:41 ` Michael S. Tsirkin 2013-09-17 20:56 ` Jeff King 1 sibling, 0 replies; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 20:41 UTC (permalink / raw) To: Jeff King; +Cc: Junio C Hamano, git On Tue, Sep 17, 2013 at 11:38:07PM +0300, Michael S. Tsirkin wrote: > On Tue, Sep 17, 2013 at 04:18:28PM -0400, Jeff King wrote: > > On Tue, Sep 17, 2013 at 11:16:04PM +0300, Michael S. Tsirkin wrote: > > > > > > Thinking about it some more, it's a best effort thing anyway, > > > > correct? > > > > > > > > So how about, instead of doing a hash over the whole input, > > > > we hash each chunk and XOR them together? > > > > > > > > This way it will be stable against chunk reordering, and > > > > no need to keep patch in memory. > > > > > > > > Hmm? > > > > > > ENOCOFFEE > > > > > > That was a silly suggestion, two identical chunks aren't that unlikely :) > > > > In a single patch, they should not be, as we should be taking into > > account the filenames, no? > > Right. > > > You could also do it hierarchically. Hash each chunk, store only the > > hashes, then sort them and hash the result. That still has O(chunks) > > storage, but it is only one hash per chunk, not the whole data. > > Could be optional too :) > Or maybe just sum byte by byte instead. One's complement probably ... > > A problem with both schemes, though, is that they are not > > backwards-compatible with existing git-patch-id implementations. > > Could you clarify? > We never send patch IDs on the wire - how isn't this compatible? > > > Whereas > > sorting the data itself is (kind of, at least with respect to people who > > are not using orderfile). > > > > -Peff ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:38 ` Michael S. Tsirkin 2013-09-17 20:41 ` Michael S. Tsirkin @ 2013-09-17 20:56 ` Jeff King 2013-09-17 21:03 ` Michael S. Tsirkin ` (2 more replies) 1 sibling, 3 replies; 32+ messages in thread From: Jeff King @ 2013-09-17 20:56 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: Junio C Hamano, git On Tue, Sep 17, 2013 at 11:38:07PM +0300, Michael S. Tsirkin wrote: > > A problem with both schemes, though, is that they are not > > backwards-compatible with existing git-patch-id implementations. > > Could you clarify? > We never send patch IDs on the wire - how isn't this compatible? I meant that you might be comparing patch-ids generated by different implementations, or across time. There are no dedicated tools to do so, but it is very easy to do so with standard tools like "join". For example, you can do: patch_ids() { git rev-list "$1" | git diff-tree --stdin -p | git patch-id | sort } patch_ids origin..topic1 >us patch_ids origin..topic2 >them join us them | cut -d' ' -f2-3 to get a list of correlated commits between two branches. If the "them" was on another machine with a different implementation (or is saved from an earlier time), your patch-ids would not match. It may be esoteric enough not to worry about, though. By far the most common use of patch-ids is going to be in a single "rev-list --cherry-pick" situation where you are trying to omit commits during a rebase. I am mostly thinking of the problems we had with the "kup" tool, which expected stability across diffs that would be signed by both kernel.org. But as far as I know, they do not use patch-id. More details in case you are curious (including me arguing that we should not care, and it is kup's problem!) are here: http://thread.gmane.org/gmane.comp.version-control.git/192331/focus=192424 rerere is mentioned in that thread, but I believe that it does its own hash, and does not rely on patch-id. -Peff ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:56 ` Jeff King @ 2013-09-17 21:03 ` Michael S. Tsirkin 2013-09-17 21:06 ` Jeff King 2013-09-17 21:52 ` Junio C Hamano 2013-09-19 21:32 ` Michael S. Tsirkin 2 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 21:03 UTC (permalink / raw) To: Jeff King; +Cc: Junio C Hamano, git On Tue, Sep 17, 2013 at 04:56:16PM -0400, Jeff King wrote: > On Tue, Sep 17, 2013 at 11:38:07PM +0300, Michael S. Tsirkin wrote: > > > > A problem with both schemes, though, is that they are not > > > backwards-compatible with existing git-patch-id implementations. > > > > Could you clarify? > > We never send patch IDs on the wire - how isn't this compatible? > > I meant that you might be comparing patch-ids generated by different > implementations, or across time. There are no dedicated tools to do so, > but it is very easy to do so with standard tools like "join". > > For example, you can do: > > patch_ids() { > git rev-list "$1" | > git diff-tree --stdin -p | > git patch-id | > sort > } > > patch_ids origin..topic1 >us > patch_ids origin..topic2 >them > > join us them | cut -d' ' -f2-3 > > to get a list of correlated commits between two branches. If the "them" > was on another machine with a different implementation (or is saved from > an earlier time), your patch-ids would not match. > > It may be esoteric enough not to worry about, though. By far the most > common use of patch-ids is going to be in a single "rev-list > --cherry-pick" situation where you are trying to omit commits during > a rebase. > > I am mostly thinking of the problems we had with the "kup" tool, which > expected stability across diffs that would be signed by both kernel.org. > But as far as I know, they do not use patch-id. We can always do a compatibility option. --order-sensitive ? --ignore-order ? > More details in case you > are curious (including me arguing that we should not care, and it is > kup's problem!) are here: > > http://thread.gmane.org/gmane.comp.version-control.git/192331/focus=192424 > > rerere is mentioned in that thread, but I believe that it does its own > hash, and does not rely on patch-id. > > -Peff I think so too. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 21:03 ` Michael S. Tsirkin @ 2013-09-17 21:06 ` Jeff King 0 siblings, 0 replies; 32+ messages in thread From: Jeff King @ 2013-09-17 21:06 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: Junio C Hamano, git On Wed, Sep 18, 2013 at 12:03:25AM +0300, Michael S. Tsirkin wrote: > > It may be esoteric enough not to worry about, though. By far the most > > common use of patch-ids is going to be in a single "rev-list > > --cherry-pick" situation where you are trying to omit commits during > > a rebase. > > > > I am mostly thinking of the problems we had with the "kup" tool, which > > expected stability across diffs that would be signed by both kernel.org. > > But as far as I know, they do not use patch-id. > > We can always do a compatibility option. --order-sensitive ? > --ignore-order ? That may make sense as an escape hatch in case somebody has a use we didn't foresee. If it is just about "consistent order" versus "whatever is in the diff", I do not know that we need to worry as much; only the minority using orderfile is affected, and they have _always_ been affected. IOW, we are fixing a bug, and they should be happier. But if it is changing the output entirely in all cases (e.g., the 1s-complement sum), I think you would want to have a "classic" mode that tries to be compatible with the old style (with the caveat that of course it depends on patch ordering). -Peff ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:56 ` Jeff King 2013-09-17 21:03 ` Michael S. Tsirkin @ 2013-09-17 21:52 ` Junio C Hamano 2013-09-19 21:32 ` Michael S. Tsirkin 2 siblings, 0 replies; 32+ messages in thread From: Junio C Hamano @ 2013-09-17 21:52 UTC (permalink / raw) To: Jeff King; +Cc: Michael S. Tsirkin, git Jeff King <peff@peff.net> writes: > I am mostly thinking of the problems we had with the "kup" tool, which > expected stability across diffs that would be signed by both kernel.org. > But as far as I know, they do not use patch-id. More details in case you > are curious (including me arguing that we should not care, and it is > kup's problem!) are here: > > http://thread.gmane.org/gmane.comp.version-control.git/192331/focus=192424 > > rerere is mentioned in that thread, but I believe that it does its own > hash, and does not rely on patch-id. It does not. The reason rerere is relevant in that thread but is not directly relevant here is because the thread is about changing the diff algorithm, hence changing the common-sequence matches between preimage and postimage, resulting in a different shape of the conflicted section. The hash rerere does still depends on the patch text, but it is restricted to the conflicted region, so whatever we do in patch-id will not affect it. Also the rerere database is not keyed by pathname (a conflict in _any_ file as long as they have the same ours/theirs conflicted text is recognised as the same conflict we have already seen), so changing the orderfile would not affect it at all. ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:56 ` Jeff King 2013-09-17 21:03 ` Michael S. Tsirkin 2013-09-17 21:52 ` Junio C Hamano @ 2013-09-19 21:32 ` Michael S. Tsirkin 2013-09-23 21:09 ` Michael S. Tsirkin 2 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-19 21:32 UTC (permalink / raw) To: Jeff King; +Cc: Junio C Hamano, git On Tue, Sep 17, 2013 at 04:56:16PM -0400, Jeff King wrote: > On Tue, Sep 17, 2013 at 11:38:07PM +0300, Michael S. Tsirkin wrote: > > > > A problem with both schemes, though, is that they are not > > > backwards-compatible with existing git-patch-id implementations. > > > > Could you clarify? > > We never send patch IDs on the wire - how isn't this compatible? > > I meant that you might be comparing patch-ids generated by different > implementations, or across time. There are no dedicated tools to do so, > but it is very easy to do so with standard tools like "join". > > For example, you can do: > > patch_ids() { > git rev-list "$1" | > git diff-tree --stdin -p | > git patch-id | > sort > } > > patch_ids origin..topic1 >us > patch_ids origin..topic2 >them > > join us them | cut -d' ' -f2-3 > > to get a list of correlated commits between two branches. If the "them" > was on another machine with a different implementation (or is saved from > an earlier time), your patch-ids would not match. > > It may be esoteric enough not to worry about, though. By far the most > common use of patch-ids is going to be in a single "rev-list > --cherry-pick" situation where you are trying to omit commits during > a rebase. > > I am mostly thinking of the problems we had with the "kup" tool, which > expected stability across diffs that would be signed by both kernel.org. > But as far as I know, they do not use patch-id. More details in case you > are curious (including me arguing that we should not care, and it is > kup's problem!) are here: > > http://thread.gmane.org/gmane.comp.version-control.git/192331/focus=192424 > > rerere is mentioned in that thread, but I believe that it does its own > hash, and does not rely on patch-id. > > -Peff OK so far I came up with the following. Needs documentation and tests obviously. But besides that - would something like this be enough to address the issue Junio raised? ---> patch-id: make it more stable Add a new patch-id algorithm making it stable against hunk reodering: - prepend header to each hunk (if not there) - calculate SHA1 hash for each hunk separately - sum all hashes to get patch id Add --order-sensitive to get historical unstable behaviour. Signed-off-by: Michael S. Tsirkin <mst@redhat.com> --- builtin/patch-id.c | 65 +++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 50 insertions(+), 15 deletions(-) diff --git a/builtin/patch-id.c b/builtin/patch-id.c index 3cfe02d..d1902ff 100644 --- a/builtin/patch-id.c +++ b/builtin/patch-id.c @@ -1,17 +1,14 @@ #include "builtin.h" -static void flush_current_id(int patchlen, unsigned char *id, git_SHA_CTX *c) +static void flush_current_id(int patchlen, unsigned char *id, unsigned char *result) { - unsigned char result[20]; char name[50]; if (!patchlen) return; - git_SHA1_Final(result, c); memcpy(name, sha1_to_hex(id), 41); printf("%s %s\n", sha1_to_hex(result), name); - git_SHA1_Init(c); } static int remove_space(char *line) @@ -56,10 +53,30 @@ static int scan_hunk_header(const char *p, int *p_before, int *p_after) return 1; } -static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct strbuf *line_buf) +static void flush_one_hunk(unsigned char *result, git_SHA_CTX *ctx) { - int patchlen = 0, found_next = 0; + unsigned char hash[20]; + unsigned short carry = 0; + int i; + + git_SHA1_Final(hash, ctx); + git_SHA1_Init(ctx); + /* 20-byte sum, with carry */ + for (i = 0; i < 20; ++i) { + carry += result[i] + hash[i]; + result[i] = carry; + carry >>= 8; + } +} +static int get_one_patchid(unsigned char *next_sha1, unsigned char *result, + struct strbuf *line_buf, int stable) +{ + int patchlen = 0, found_next = 0, hunks = 0; int before = -1, after = -1; + git_SHA_CTX ctx, header_ctx; + + git_SHA1_Init(&ctx); + hashclr(result); while (strbuf_getwholeline(line_buf, stdin, '\n') != EOF) { char *line = line_buf->buf; @@ -99,6 +116,18 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st if (!memcmp(line, "@@ -", 4)) { /* Parse next hunk, but ignore line numbers. */ scan_hunk_header(line, &before, &after); + if (stable) { + if (hunks) { + flush_one_hunk(result, &ctx); + memcpy(&ctx, &header_ctx, + sizeof ctx); + } else { + /* Save ctx for next hunk. */ + memcpy(&header_ctx, &ctx, + sizeof ctx); + } + } + hunks++; continue; } @@ -108,6 +137,7 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st /* Else we're parsing another header. */ before = after = -1; + hunks = 0; } /* If we get here, we're inside a hunk. */ @@ -119,27 +149,27 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st /* Compute the sha without whitespace */ len = remove_space(line); patchlen += len; - git_SHA1_Update(ctx, line, len); + git_SHA1_Update(&ctx, line, len); } if (!found_next) hashclr(next_sha1); + flush_one_hunk(result, &ctx); + return patchlen; } -static void generate_id_list(void) +static void generate_id_list(int stable) { - unsigned char sha1[20], n[20]; - git_SHA_CTX ctx; + unsigned char sha1[20], n[20], result[20]; int patchlen; struct strbuf line_buf = STRBUF_INIT; - git_SHA1_Init(&ctx); hashclr(sha1); while (!feof(stdin)) { - patchlen = get_one_patchid(n, &ctx, &line_buf); - flush_current_id(patchlen, sha1, &ctx); + patchlen = get_one_patchid(n, result, &line_buf, stable); + flush_current_id(patchlen, sha1, result); hashcpy(sha1, n); } strbuf_release(&line_buf); @@ -149,9 +179,14 @@ static const char patch_id_usage[] = "git patch-id < patch"; int cmd_patch_id(int argc, const char **argv, const char *prefix) { - if (argc != 1) + int stable; + if (argc == 2 && !strcmp(argv[1], "--order-sensitive")) + stable = 0; + else if (argc == 1) + stable = 1; + else usage(patch_id_usage); - generate_id_list(); + generate_id_list(stable); return 0; } -- MST ^ permalink raw reply related [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-19 21:32 ` Michael S. Tsirkin @ 2013-09-23 21:09 ` Michael S. Tsirkin 2013-09-23 21:37 ` Jonathan Nieder 0 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-23 21:09 UTC (permalink / raw) To: Jeff King; +Cc: Junio C Hamano, git On Fri, Sep 20, 2013 at 12:32:26AM +0300, Michael S. Tsirkin wrote: > On Tue, Sep 17, 2013 at 04:56:16PM -0400, Jeff King wrote: > > On Tue, Sep 17, 2013 at 11:38:07PM +0300, Michael S. Tsirkin wrote: > > > > > > A problem with both schemes, though, is that they are not > > > > backwards-compatible with existing git-patch-id implementations. > > > > > > Could you clarify? > > > We never send patch IDs on the wire - how isn't this compatible? > > > > I meant that you might be comparing patch-ids generated by different > > implementations, or across time. There are no dedicated tools to do so, > > but it is very easy to do so with standard tools like "join". > > > > For example, you can do: > > > > patch_ids() { > > git rev-list "$1" | > > git diff-tree --stdin -p | > > git patch-id | > > sort > > } > > > > patch_ids origin..topic1 >us > > patch_ids origin..topic2 >them > > > > join us them | cut -d' ' -f2-3 > > > > to get a list of correlated commits between two branches. If the "them" > > was on another machine with a different implementation (or is saved from > > an earlier time), your patch-ids would not match. > > > > It may be esoteric enough not to worry about, though. By far the most > > common use of patch-ids is going to be in a single "rev-list > > --cherry-pick" situation where you are trying to omit commits during > > a rebase. > > > > I am mostly thinking of the problems we had with the "kup" tool, which > > expected stability across diffs that would be signed by both kernel.org. > > But as far as I know, they do not use patch-id. More details in case you > > are curious (including me arguing that we should not care, and it is > > kup's problem!) are here: > > > > http://thread.gmane.org/gmane.comp.version-control.git/192331/focus=192424 > > > > rerere is mentioned in that thread, but I believe that it does its own > > hash, and does not rely on patch-id. > > > > -Peff > > OK so far I came up with the following. > Needs documentation and tests obviously. > But besides that - > would something like this be enough to address the > issue Junio raised? Ping. Junio could you comment on this please? > ---> > > patch-id: make it more stable > > Add a new patch-id algorithm making it stable against > hunk reodering: > - prepend header to each hunk (if not there) > - calculate SHA1 hash for each hunk separately > - sum all hashes to get patch id > > Add --order-sensitive to get historical unstable behaviour. > > Signed-off-by: Michael S. Tsirkin <mst@redhat.com> > --- > builtin/patch-id.c | 65 +++++++++++++++++++++++++++++++++++++++++------------- > 1 file changed, 50 insertions(+), 15 deletions(-) > > diff --git a/builtin/patch-id.c b/builtin/patch-id.c > index 3cfe02d..d1902ff 100644 > --- a/builtin/patch-id.c > +++ b/builtin/patch-id.c > @@ -1,17 +1,14 @@ > #include "builtin.h" > > -static void flush_current_id(int patchlen, unsigned char *id, git_SHA_CTX *c) > +static void flush_current_id(int patchlen, unsigned char *id, unsigned char *result) > { > - unsigned char result[20]; > char name[50]; > > if (!patchlen) > return; > > - git_SHA1_Final(result, c); > memcpy(name, sha1_to_hex(id), 41); > printf("%s %s\n", sha1_to_hex(result), name); > - git_SHA1_Init(c); > } > > static int remove_space(char *line) > @@ -56,10 +53,30 @@ static int scan_hunk_header(const char *p, int *p_before, int *p_after) > return 1; > } > > -static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct strbuf *line_buf) > +static void flush_one_hunk(unsigned char *result, git_SHA_CTX *ctx) > { > - int patchlen = 0, found_next = 0; > + unsigned char hash[20]; > + unsigned short carry = 0; > + int i; > + > + git_SHA1_Final(hash, ctx); > + git_SHA1_Init(ctx); > + /* 20-byte sum, with carry */ > + for (i = 0; i < 20; ++i) { > + carry += result[i] + hash[i]; > + result[i] = carry; > + carry >>= 8; > + } > +} > +static int get_one_patchid(unsigned char *next_sha1, unsigned char *result, > + struct strbuf *line_buf, int stable) > +{ > + int patchlen = 0, found_next = 0, hunks = 0; > int before = -1, after = -1; > + git_SHA_CTX ctx, header_ctx; > + > + git_SHA1_Init(&ctx); > + hashclr(result); > > while (strbuf_getwholeline(line_buf, stdin, '\n') != EOF) { > char *line = line_buf->buf; > @@ -99,6 +116,18 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st > if (!memcmp(line, "@@ -", 4)) { > /* Parse next hunk, but ignore line numbers. */ > scan_hunk_header(line, &before, &after); > + if (stable) { > + if (hunks) { > + flush_one_hunk(result, &ctx); > + memcpy(&ctx, &header_ctx, > + sizeof ctx); > + } else { > + /* Save ctx for next hunk. */ > + memcpy(&header_ctx, &ctx, > + sizeof ctx); > + } > + } > + hunks++; > continue; > } > > @@ -108,6 +137,7 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st > > /* Else we're parsing another header. */ > before = after = -1; > + hunks = 0; > } > > /* If we get here, we're inside a hunk. */ > @@ -119,27 +149,27 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st > /* Compute the sha without whitespace */ > len = remove_space(line); > patchlen += len; > - git_SHA1_Update(ctx, line, len); > + git_SHA1_Update(&ctx, line, len); > } > > if (!found_next) > hashclr(next_sha1); > > + flush_one_hunk(result, &ctx); > + > return patchlen; > } > > -static void generate_id_list(void) > +static void generate_id_list(int stable) > { > - unsigned char sha1[20], n[20]; > - git_SHA_CTX ctx; > + unsigned char sha1[20], n[20], result[20]; > int patchlen; > struct strbuf line_buf = STRBUF_INIT; > > - git_SHA1_Init(&ctx); > hashclr(sha1); > while (!feof(stdin)) { > - patchlen = get_one_patchid(n, &ctx, &line_buf); > - flush_current_id(patchlen, sha1, &ctx); > + patchlen = get_one_patchid(n, result, &line_buf, stable); > + flush_current_id(patchlen, sha1, result); > hashcpy(sha1, n); > } > strbuf_release(&line_buf); > @@ -149,9 +179,14 @@ static const char patch_id_usage[] = "git patch-id < patch"; > > int cmd_patch_id(int argc, const char **argv, const char *prefix) > { > - if (argc != 1) > + int stable; > + if (argc == 2 && !strcmp(argv[1], "--order-sensitive")) > + stable = 0; > + else if (argc == 1) > + stable = 1; > + else > usage(patch_id_usage); > > - generate_id_list(); > + generate_id_list(stable); > return 0; > } > -- > MST > ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-23 21:09 ` Michael S. Tsirkin @ 2013-09-23 21:37 ` Jonathan Nieder 2013-09-24 5:45 ` Jeff King 2013-09-24 5:54 ` Michael S. Tsirkin 0 siblings, 2 replies; 32+ messages in thread From: Jonathan Nieder @ 2013-09-23 21:37 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: Jeff King, Junio C Hamano, git Hi, Michael S. Tsirkin wrote: >> On Tue, Sep 17, 2013 at 04:56:16PM -0400, Jeff King wrote: >>>>> A problem with both schemes, though, is that they are not >>>>> backwards-compatible with existing git-patch-id implementations. [...] >>> It may be esoteric enough not to worry about, though. Yeah, I think it would be okay. Details of the diff generation algorithm have changed from time to time anyway (and broken things, as you mentioned) and we make no guarantee about this. [...] >> patch-id: make it more stable >> >> Add a new patch-id algorithm making it stable against >> hunk reodering: >> - prepend header to each hunk (if not there) >> - calculate SHA1 hash for each hunk separately >> - sum all hashes to get patch id >> >> Add --order-sensitive to get historical unstable behaviour. The --order-sensitive option seems confusing. How do I use it to replicate a historical patch-id? If I record all options that might have influenced ordering (which are those?) then am I guaranteed to get a reproducible result? So I would prefer either of the following over the above: a) When asked to compute the patch-id of a seekable file, use the current streaming implementation until you notice a filename that is out of order. Then start over with sorted hunks (for example building a table of offsets within the patch for each hunk to support this). When asked to compute the patch-id of an unseekable file, stream to a temporary file under $GIT_DIR to get a seekable file. b) Unconditionally use the new patch-id definition that is stable under permutation of hunks. If and when someone complains that this invalidates their old patch-ids, they can work on adding a nice interface for getting the old-style patch-ids. I suspect it just wouldn't come up. Of course I can easily be wrong. Thanks for a clear patch that makes the choices easy to reasonable about. Thoughts? Jonathan ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-23 21:37 ` Jonathan Nieder @ 2013-09-24 5:45 ` Jeff King 2013-09-24 5:54 ` Michael S. Tsirkin 1 sibling, 0 replies; 32+ messages in thread From: Jeff King @ 2013-09-24 5:45 UTC (permalink / raw) To: Jonathan Nieder; +Cc: Michael S. Tsirkin, Junio C Hamano, git On Mon, Sep 23, 2013 at 02:37:29PM -0700, Jonathan Nieder wrote: > >> Add --order-sensitive to get historical unstable behaviour. > > The --order-sensitive option seems confusing. How do I use it to > replicate a historical patch-id? If I record all options that might > have influenced ordering (which are those?) then am I guaranteed to > get a reproducible result? Yes, I have the same complaint. I'd much rather the classic mode be given a name of some sort, and then have a "--patch-id-mode=classic" parameter (or probably some better name) that sets all of the parameters. Then you know that two implementations using "classic" should get the same output, and so forth if we have to tweak it again. > So I would prefer either of the following over the above: > > a) When asked to compute the patch-id of a seekable file, use the > current streaming implementation until you notice a filename that > is out of order. Then start over with sorted hunks (for example > building a table of offsets within the patch for each hunk to > support this). > > When asked to compute the patch-id of an unseekable file, stream > to a temporary file under $GIT_DIR to get a seekable file. This would mean that everybody, whether they care about compatibility or not, would have to pay the price to spool to $GIT_DIR, right? That's not great, as most cases would not care. > b) Unconditionally use the new patch-id definition that is stable > under permutation of hunks. If and when someone complains that > this invalidates their old patch-ids, they can work on adding a > nice interface for getting the old-style patch-ids. I suspect it > just wouldn't come up. I think I'd prefer this one. The "--patch-id-mode" above is how I would do it, and in general when we are potentially breaking compatibility, it's nice to anticipate and give an escape hatch. But I do find it reasonably unlikely that this will come up, so maybe this is a good time to practice YAGNI. -Peff ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-23 21:37 ` Jonathan Nieder 2013-09-24 5:45 ` Jeff King @ 2013-09-24 5:54 ` Michael S. Tsirkin 2013-09-24 19:36 ` Jonathan Nieder 1 sibling, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-24 5:54 UTC (permalink / raw) To: Jonathan Nieder; +Cc: Jeff King, Junio C Hamano, git On Mon, Sep 23, 2013 at 02:37:29PM -0700, Jonathan Nieder wrote: > Hi, > > Michael S. Tsirkin wrote: > >> On Tue, Sep 17, 2013 at 04:56:16PM -0400, Jeff King wrote: > > >>>>> A problem with both schemes, though, is that they are not > >>>>> backwards-compatible with existing git-patch-id implementations. > [...] > >>> It may be esoteric enough not to worry about, though. > > Yeah, I think it would be okay. Details of the diff generation > algorithm have changed from time to time anyway (and broken things, > as you mentioned) and we make no guarantee about this. > > [...] > >> patch-id: make it more stable > >> > >> Add a new patch-id algorithm making it stable against > >> hunk reodering: > >> - prepend header to each hunk (if not there) > >> - calculate SHA1 hash for each hunk separately > >> - sum all hashes to get patch id > >> > >> Add --order-sensitive to get historical unstable behaviour. > > The --order-sensitive option seems confusing. How do I use it to > replicate a historical patch-id? You supply a historical diff to it :) > If I record all options that might > have influenced ordering (which are those?) then am I guaranteed to > get a reproducible result? Maybe not. But if you have a patch on disk, you will get old hash from it with --order-sensitive. > So I would prefer either of the following over the above: > > a) When asked to compute the patch-id of a seekable file, use the > current streaming implementation until you notice a filename that > is out of order. Then start over with sorted hunks (for example > building a table of offsets within the patch for each hunk to > support this). > > When asked to compute the patch-id of an unseekable file, stream > to a temporary file under $GIT_DIR to get a seekable file. This can be computed in one pass: just keep two checksums around. But the result won't be stable: if you get same patch from two people one is ordered, the other isn't, you get two different checksums. What are we trying to achieve here? > b) Unconditionally use the new patch-id definition that is stable > under permutation of hunks. If and when someone complains that > this invalidates their old patch-ids, they can work on adding a > nice interface for getting the old-style patch-ids. I suspect it > just wouldn't come up. That's certainly easy to implement. > Of course I can easily be wrong. Thanks for a clear patch that makes > the choices easy to reasonable about. > > Thoughts? > Jonathan ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-24 5:54 ` Michael S. Tsirkin @ 2013-09-24 19:36 ` Jonathan Nieder 2013-09-24 20:15 ` Michael S. Tsirkin 0 siblings, 1 reply; 32+ messages in thread From: Jonathan Nieder @ 2013-09-24 19:36 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: Jeff King, Junio C Hamano, git Michael S. Tsirkin wrote: > On Mon, Sep 23, 2013 at 02:37:29PM -0700, Jonathan Nieder wrote: >> a) When asked to compute the patch-id of a seekable file, use the >> current streaming implementation until you notice a filename that >> is out of order. Then start over with sorted hunks (for example >> building a table of offsets within the patch for each hunk to >> support this). >> >> When asked to compute the patch-id of an unseekable file, stream >> to a temporary file under $GIT_DIR to get a seekable file. > > This can be computed in one pass: just keep two checksums around. > > But the result won't be stable: if you get same patch from two > people one is ordered, the other isn't, you get two different checksums. Sorry for the lack of clarity. In this case (a), I meant "sort the diff hunks and use the *old* patch-id definition with sorted hunks, which produces a stable result but requires random access. However: [...] >> b) Unconditionally use the new patch-id definition that is stable >> under permutation of hunks. If and when someone complains that >> this invalidates their old patch-ids, they can work on adding a >> nice interface for getting the old-style patch-ids. I suspect it >> just wouldn't come up. > > That's certainly easy to implement. Yes, (b) seems like the best option to me, for what it's worth. Thanks again, Jonathan ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-24 19:36 ` Jonathan Nieder @ 2013-09-24 20:15 ` Michael S. Tsirkin 2013-09-24 21:31 ` Jonathan Nieder 0 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-24 20:15 UTC (permalink / raw) To: Jonathan Nieder; +Cc: Jeff King, Junio C Hamano, git On Tue, Sep 24, 2013 at 12:36:10PM -0700, Jonathan Nieder wrote: > Michael S. Tsirkin wrote: > > On Mon, Sep 23, 2013 at 02:37:29PM -0700, Jonathan Nieder wrote: > > >> a) When asked to compute the patch-id of a seekable file, use the > >> current streaming implementation until you notice a filename that > >> is out of order. Then start over with sorted hunks (for example > >> building a table of offsets within the patch for each hunk to > >> support this). > >> > >> When asked to compute the patch-id of an unseekable file, stream > >> to a temporary file under $GIT_DIR to get a seekable file. > > > > This can be computed in one pass: just keep two checksums around. > > > > But the result won't be stable: if you get same patch from two > > people one is ordered, the other isn't, you get two different checksums. > > Sorry for the lack of clarity. In this case (a), I meant "sort the > diff hunks and use the *old* patch-id definition with sorted hunks, Well, then the result is not compatible with what original patch-id would produce. Basically you are either not stable or not compatible :) > which produces a stable result but requires random access. > > However: > > [...] > >> b) Unconditionally use the new patch-id definition that is stable > >> under permutation of hunks. If and when someone complains that > >> this invalidates their old patch-ids, they can work on adding a > >> nice interface for getting the old-style patch-ids. I suspect it > >> just wouldn't come up. > > > > That's certainly easy to implement. > > Yes, (b) seems like the best option to me, for what it's worth. > > Thanks again, > Jonathan OK, thanks. Just making sure: is it correct that there's no requirement to use same algorithm between patch-ids.c and builtin/patch-id.c ? ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-24 20:15 ` Michael S. Tsirkin @ 2013-09-24 21:31 ` Jonathan Nieder 2013-09-24 21:57 ` Michael S. Tsirkin 0 siblings, 1 reply; 32+ messages in thread From: Jonathan Nieder @ 2013-09-24 21:31 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: Jeff King, Junio C Hamano, git Michael S. Tsirkin wrote: >>> On Mon, Sep 23, 2013 at 02:37:29PM -0700, Jonathan Nieder wrote: >>>> Then start over with sorted hunks (for example >>>> building a table of offsets within the patch for each hunk to >>>> support this). [...] > Well, then the result is not compatible with what > original patch-id would produce. Nope, I meant sorting to produce what the original patch-id would produce for a diff with the default sorting order. The result is a patch-id that can be compared with patch-ids from earlier versions of git as long as -O<orderfile> was not used (which was already not compatible with reliable use of patch-id). [...] > Just making sure: is it correct that there's no requirement to use same > algorithm between patch-ids.c and builtin/patch-id.c ? I think so, as long as Documentation/git-cherry.txt is updated to stop pretending 'git cherry' calls 'git patch-id' and the two get comments about it, though it seems simpler to keep them roughly the same. (They already differ in handling of binary files.) Thanks, Jonathan ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-24 21:31 ` Jonathan Nieder @ 2013-09-24 21:57 ` Michael S. Tsirkin 2013-09-24 22:08 ` Jonathan Nieder 0 siblings, 1 reply; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-24 21:57 UTC (permalink / raw) To: Jonathan Nieder; +Cc: Jeff King, Junio C Hamano, git On Tue, Sep 24, 2013 at 02:31:16PM -0700, Jonathan Nieder wrote: > Michael S. Tsirkin wrote: > >>> On Mon, Sep 23, 2013 at 02:37:29PM -0700, Jonathan Nieder wrote: > > >>>> Then start over with sorted hunks (for example > >>>> building a table of offsets within the patch for each hunk to > >>>> support this). > [...] > > Well, then the result is not compatible with what > > original patch-id would produce. > > Nope, I meant sorting to produce what the original patch-id would > produce for a diff with the default sorting order. The result is a > patch-id that can be compared with patch-ids from earlier versions of > git as long as -O<orderfile> was not used (which was already not > compatible with reliable use of patch-id). > > [...] > > Just making sure: is it correct that there's no requirement to use same > > algorithm between patch-ids.c and builtin/patch-id.c ? > > I think so, as long as Documentation/git-cherry.txt is updated to stop > pretending 'git cherry' calls 'git patch-id' and the two get comments > about it, though it seems simpler to keep them roughly the same. > (They already differ in handling of binary files.) How do they differ btw? > Thanks, > Jonathan ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-24 21:57 ` Michael S. Tsirkin @ 2013-09-24 22:08 ` Jonathan Nieder 0 siblings, 0 replies; 32+ messages in thread From: Jonathan Nieder @ 2013-09-24 22:08 UTC (permalink / raw) To: Michael S. Tsirkin; +Cc: Jeff King, Junio C Hamano, git Michael S. Tsirkin wrote: > On Tue, Sep 24, 2013 at 02:31:16PM -0700, Jonathan Nieder wrote: >> Michael S. Tsirkin wrote: >>> Just making sure: is it correct that there's no requirement to use same >>> algorithm between patch-ids.c and builtin/patch-id.c ? >> >> I think so, [...] >> (They already differ in handling of binary files.) > > How do they differ btw? "git diff" without --binary writes "Binary files a/foo and b/foo differ" and there is nothing for 'git patch-id' to consume for that file. With --binary, "git diff" produces entries in 'GIT binary patch' format which patch-id also skips. 'git cherry' and friends hash in the old and new versions of a binary file to avoid accidentally dropping changes (see v1.5.3-rc6~9 "Take binary diffs into accounts for 'git rebase', 2007-08-18, and v1.7.3-rc0~27^2 "hash binary sha1 into patch id", 2010-08-15). Jonathan ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 20:16 ` Michael S. Tsirkin 2013-09-17 20:18 ` Jeff King @ 2013-09-17 20:31 ` Michael S. Tsirkin 1 sibling, 0 replies; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-17 20:31 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Tue, Sep 17, 2013 at 11:16:04PM +0300, Michael S. Tsirkin wrote: > On Tue, Sep 17, 2013 at 11:14:01PM +0300, Michael S. Tsirkin wrote: > > On Tue, Sep 17, 2013 at 11:06:07AM -0700, Junio C Hamano wrote: > > > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > > > > > On Tue, Sep 17, 2013 at 10:24:19AM -0700, Junio C Hamano wrote: > > > >> "Michael S. Tsirkin" <mst@redhat.com> writes: > > > >> > > > >> > So might it not be useful to tweak patch id to > > > >> > sort the diff, making it a bit more stable? > > > >> > > > >> That is one thing that needs to be done, I think. But it would be > > > >> unfortunate if we have to do that unconditionally, though, as we may > > > >> be "buffering" many hundred kilobytes of patch text in core. If we > > > >> can do so without regressing the streaming performance for the most > > > >> common case of not using the orderfile on the generating side (hence > > > >> not having to sort on the receiving end), it would be ideal. I am > > > >> not sure offhand how much code damage we are talking about, though. > > > > > > > > So make it conditional on the presence of the orderefile option? > > > > > > That would mean that those who set orderfile from configuration in > > > the future will have to always suffer, I would think. Is that > > > acceptable? I dunno. > > > > > > Also, if the sender used a non-standard order, the recipient does > > > not know what order the patch was generated, and the recipient does > > > not use a custom orderfile, what should happen? I thought your idea > > > was to normalize by using some canonical order that is not affected > > > by the orderfile to make sure patch-id stays stable, so I would > > > imagine that such a recipient who does not have orderfile specified > > > still needs to sort before hashing, no? > > > > Thinking about it some more, it's a best effort thing anyway, > > correct? > > > > So how about, instead of doing a hash over the whole input, > > we hash each chunk and XOR them together? > > > > This way it will be stable against chunk reordering, and > > no need to keep patch in memory. > > > > Hmm? > > ENOCOFFEE > > That was a silly suggestion, two identical chunks aren't that unlikely :) OTOH we can detect such malformed patches just by keeping the chunk hashes in memory... > > -- > > MST ^ permalink raw reply [flat|nested] 32+ messages in thread
* Re: [PATCH] diff: add a config option to control orderfile 2013-09-17 17:24 ` Junio C Hamano 2013-09-17 17:28 ` Michael S. Tsirkin @ 2013-09-21 21:08 ` Michael S. Tsirkin 1 sibling, 0 replies; 32+ messages in thread From: Michael S. Tsirkin @ 2013-09-21 21:08 UTC (permalink / raw) To: Junio C Hamano; +Cc: git On Tue, Sep 17, 2013 at 10:24:19AM -0700, Junio C Hamano wrote: > "Michael S. Tsirkin" <mst@redhat.com> writes: > > > So might it not be useful to tweak patch id to > > sort the diff, making it a bit more stable? > > That is one thing that needs to be done, I think. But it would be > unfortunate if we have to do that unconditionally, though, as we may > be "buffering" many hundred kilobytes of patch text in core. If we > can do so without regressing the streaming performance for the most > common case of not using the orderfile on the generating side (hence > not having to sort on the receiving end), it would be ideal. I am > not sure offhand how much code damage we are talking about, though. > > > I'll be glad to help do this if you tell me what these parts are. > > anything else besides fixing besides the stand-alone patch id? > > Off the top of my head I do not think of one (but that is not a > guarantee that there isn't any). Okay so I did this by reworking the internal algorithm used by the stand-alone patch-id (hope you've seen this mail). Now, a question: does it matter whether the algorithm used by diff_get_patch_id is different? Does something rely on them being the same? If yes, we'd have to change diff_get_patch_id as well. ^ permalink raw reply [flat|nested] 32+ messages in thread
end of thread, other threads:[~2013-09-24 22:08 UTC | newest] Thread overview: 32+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-08-31 19:44 [PATCH] diff: add a config option to control orderfile Michael S. Tsirkin 2013-09-03 17:12 ` Junio C Hamano 2013-09-03 21:08 ` Michael S. Tsirkin 2013-09-15 7:49 ` Michael S. Tsirkin 2013-09-15 8:08 ` Michael S. Tsirkin 2013-09-17 16:26 ` Junio C Hamano 2013-09-17 16:42 ` Michael S. Tsirkin 2013-09-17 17:24 ` Junio C Hamano 2013-09-17 17:28 ` Michael S. Tsirkin 2013-09-17 18:06 ` Junio C Hamano 2013-09-17 19:25 ` Michael S. Tsirkin 2013-09-17 20:14 ` Michael S. Tsirkin 2013-09-17 20:16 ` Michael S. Tsirkin 2013-09-17 20:18 ` Jeff King 2013-09-17 20:38 ` Michael S. Tsirkin 2013-09-17 20:41 ` Michael S. Tsirkin 2013-09-17 20:56 ` Jeff King 2013-09-17 21:03 ` Michael S. Tsirkin 2013-09-17 21:06 ` Jeff King 2013-09-17 21:52 ` Junio C Hamano 2013-09-19 21:32 ` Michael S. Tsirkin 2013-09-23 21:09 ` Michael S. Tsirkin 2013-09-23 21:37 ` Jonathan Nieder 2013-09-24 5:45 ` Jeff King 2013-09-24 5:54 ` Michael S. Tsirkin 2013-09-24 19:36 ` Jonathan Nieder 2013-09-24 20:15 ` Michael S. Tsirkin 2013-09-24 21:31 ` Jonathan Nieder 2013-09-24 21:57 ` Michael S. Tsirkin 2013-09-24 22:08 ` Jonathan Nieder 2013-09-17 20:31 ` Michael S. Tsirkin 2013-09-21 21:08 ` Michael S. Tsirkin
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.