diff: add a config option to control orderfile
PATCH 1/1 diff: add a config option to control orderfile
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.
--- diff.c | 3 +++ 1 file changed, 3 insertions(+)
diff.c +3 -0
@@ -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);
Signature · 1 line
MST
Quoted 6 lines · Michael S. Tsirkin
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 <[email protected]>---
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.
Quoted 16 lines
diff.c | 3 +++ 1 file changed, 3 insertions(+)diff.c +3
-0@@ -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);
Quoted 6 lines · Junio C Hamano
Quoted 4 lines · Michael S. Tsirkin
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.
Quoted 6 lines
Quoted 2 lines
Signed-off-by Michael S. Tsirkin <[email protected]>---
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?
Quoted 2 lines
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.
Quoted 16 lines
Quoted 16 lines
diff.c | 3 +++ 1 file changed, 3 insertions(+)diff.c +3
-0@@ -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);
Quoted 7 lines · Michael S. Tsirkin
Quoted 6 lines · Junio C Hamano
Quoted 4 lines · Michael S. Tsirkin
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.
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
Signed-off-by Michael S. Tsirkin <[email protected]>---
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?
Quoted 28 lines
Quoted 2 lines
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.
Quoted 16 lines
Quoted 16 lines
diff.c | 3 +++ 1 file changed, 3 insertions(+)diff.c +3
-0@@ -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);
Quoted 11 lines · Michael S. Tsirkin
Quoted 10 lines · Michael S. Tsirkin
Quoted 9 lines · Junio C Hamano
Quoted 6 lines · Michael S. Tsirkin
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 <[email protected]>---
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
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?
Quoted 28 lines
Quoted 28 lines
Quoted 2 lines
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.
Quoted 16 lines
Quoted 16 lines
diff.c | 3 +++ 1 file changed, 3 insertions(+)diff.c +3
-0@@ -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);
Quoted 2 lines · Michael S. Tsirkin
Actually, after I've looked at the code,
diffcore_orderis 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.
Quoted 11 lines · Junio C Hamano
Quoted 2 lines · Michael S. Tsirkin
Actually, after I've looked at the code,
diffcore_orderis 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?
Quoted 3 lines
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?
Signature · 1 line
MST
Quoted 2 lines · Michael S. Tsirkin
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.
Quoted 2 lines
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).
Quoted 5 lines · Junio C Hamano
Quoted 2 lines · Michael S. Tsirkin
So might it not be useful to tweak patch id to
sort the diff, making it a bit more stable?
Quoted 7 lines
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?
Quoted 5 lines
Quoted 2 lines
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).
Quoted 14 lines · Michael S. Tsirkin
Quoted 5 lines · Junio C Hamano
Quoted 2 lines · Michael S. Tsirkin
So might it not be useful to tweak patch id to
sort the diff, making it a bit more stable?Quoted 7 lines
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.
Quoted 1 line
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?
Quoted 16 lines · Junio C Hamano
Quoted 14 lines · Michael S. Tsirkin
Quoted 12 lines · Junio C Hamano
Quoted 2 lines · Michael S. Tsirkin
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.
Quoted 5 lines
Quoted 1 line
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?
Quoted 7 lines
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 :)
Signature · 1 line
MST
Quoted 22 lines · Junio C Hamano
Quoted 14 lines · Michael S. Tsirkin
Quoted 5 lines · Junio C Hamano
Quoted 2 lines · Michael S. Tsirkin
So might it not be useful to tweak patch id to
sort the diff, making it a bit more stable?Quoted 7 lines
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.
Quoted 1 line
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.
Quoted 7 lines
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?
Signature · 1 line
MST
Quoted 34 lines · Michael S. Tsirkin
Quoted 22 lines · Junio C Hamano
Quoted 14 lines · Michael S. Tsirkin
Quoted 5 lines · Junio C Hamano
Quoted 2 lines · Michael S. Tsirkin
So might it not be useful to tweak patch id to
sort the diff, making it a bit more stable?Quoted 7 lines
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.
Quoted 1 line
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.
Quoted 7 lines
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?
Quoted 7 lines
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 :)
Quoted 2 lines
Signature · 1 line
MST
Quoted 6 lines · Michael S. Tsirkin
Quoted 6 lines
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?
Quoted 8 lines
Quoted 4 lines
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
Quoted 11 lines · Jeff King
Quoted 9 lines · Michael S. Tsirkin
Quoted 9 lines
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.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
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.
Quoted 3 lines
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.
Quoted 2 lines
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?
Quoted 5 lines
Whereas
sorting the data itself is (kind of, at least with respect to people who are not using orderfile).-Peff
Quoted 21 lines · Michael S. Tsirkin
Quoted 11 lines · Jeff King
Quoted 9 lines · Michael S. Tsirkin
Quoted 9 lines
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.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
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?
Quoted 8 lines
Right.
Quoted 3 lines
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 ...
Quoted 11 lines
Quoted 2 lines
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?Quoted 5 lines
Whereas
sorting the data itself is (kind of, at least with respect to people who are not using orderfile).-Peff
Quoted 5 lines · Michael S. Tsirkin
Quoted 2 lines
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
Quoted 30 lines · Jeff King
Quoted 5 lines · Michael S. Tsirkin
Quoted 2 lines
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_idsorigin..topic1 >us
patch_idsorigin..topic2 >themjoin 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.
Quoted 8 lines
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 ?
Quoted 10 lines
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.
Quoted 11 lines · Michael S. Tsirkin
Quoted 8 lines
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
Quoted 10 lines · Jeff King
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.
Quoted 41 lines · Jeff King
Quoted 5 lines · Michael S. Tsirkin
Quoted 2 lines
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_idsorigin..topic1 >us
patch_idsorigin..topic2 >themjoin 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:
Quoted 6 lines
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.
--- builtin/patch-id.c | 65 +++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 50 insertions(+), 15 deletions(-)
builtin/patch-id.c +50 -15
@@ -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 stif (!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 ; }
Signature · 1 line
MST
Quoted 47 lines · Michael S. Tsirkin
Quoted 46 lines · Jeff King
Quoted 5 lines · Michael S. Tsirkin
Quoted 2 lines
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_idsorigin..topic1 >us
patch_idsorigin..topic2 >themjoin 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.
Quoted 7 lines
Quoted 1 line
-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?
Quoted 155 lines
--->
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 idAdd --order-sensitive to get historical unstable behaviour.
Signed-off-by Michael S. Tsirkin <[email protected]>--- builtin/patch-id.c | 65 +++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 50 insertions(+), 15 deletions(-)builtin/patch-id.c +50
-15@@ -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 stif (!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 ; }Signature · 1 line
MST
Hi,
Quoted 4 lines · Michael S. Tsirkin
Quoted 4 lines · Jeff King
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
A problem with both schemes, though, is that they are not backwards-compatible with existing git-patch-id implementations.
[...]
Quoted 1 line
Quoted 1 line
Quoted 1 line
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.
[...]
Quoted 9 lines
Quoted 9 lines
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 idAdd --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
Quoted 6 lines · Jonathan Nieder
Quoted 1 line
Quoted 1 line
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.
Quoted 10 lines
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.
Quoted 5 lines
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
Quoted 23 lines · Jonathan Nieder
Hi,
Quoted 4 lines · Michael S. Tsirkin
Quoted 4 lines · Jeff King
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
A problem with both schemes, though, is that they are not backwards-compatible with existing git-patch-id implementations.
[...]
Quoted 1 line
Quoted 1 line
Quoted 1 line
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.
[...]
Quoted 8 lines
Quoted 8 lines
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
Quoted 4 lines
Quoted 1 line
Quoted 1 line
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 :)
Quoted 3 lines
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.
Quoted 10 lines
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?
Quoted 5 lines
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.
Quoted 5 lines
Of course I can easily be wrong. Thanks for a clear patch that makes the choices easy to reasonable about.
Thoughts?
Jonathan
Quoted 8 lines · Michael S. Tsirkin
Quoted 6 lines · Jonathan Nieder
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).
Quoted 7 lines
Quoted 2 lines
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:
[...]
Quoted 7 lines
Quoted 5 lines
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
Quoted 12 lines · Jonathan Nieder
Quoted 11 lines · Michael S. Tsirkin
Quoted 8 lines · Jonathan Nieder
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.
Quoted 7 lines
Quoted 4 lines
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 :)
Quoted 11 lines
which produces a stable result but requires random access.
However:
[...]
Quoted 6 lines
Quoted 5 lines
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.
Quoted 6 lines
Quoted 1 line
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 ?
Quoted 5 lines · Michael S. Tsirkin
Quoted 5 lines
Quoted 5 lines · Jonathan Nieder
Quoted 4 lines
Then start over with sorted hunks (for example
building a table of offsets within the patch for each hunk to support this).
[...]
Quoted 2 lines
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).
[...]
Quoted 2 lines
Just making sure: is it correct that there's no requirement to use same algorithm between
patch-ids.candbuiltin/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
Quoted 16 lines · Jonathan Nieder
Quoted 5 lines · Michael S. Tsirkin
Quoted 5 lines
Quoted 5 lines · Jonathan Nieder
Quoted 4 lines
Then start over with sorted hunks (for example
building a table of offsets within the patch for each hunk to support this).[...]
Quoted 2 lines
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).
Quoted 8 lines
[...]
Quoted 2 lines
Just making sure: is it correct that there's no requirement to use same algorithm between
patch-ids.candbuiltin/patch-id.c?I think so, as long as
Documentation/git-cherry.txtis 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?
Quoted 2 lines
Thanks,
Jonathan
Quoted 7 lines · Michael S. Tsirkin
Quoted 6 lines · Jonathan Nieder
Quoted 2 lines · Michael S. Tsirkin
Just making sure: is it correct that there's no requirement to use same algorithm between
patch-ids.candbuiltin/patch-id.c?I think so,
[...]
Quoted 3 lines
Quoted 1 line
(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
Quoted 38 lines · Michael S. Tsirkin
Quoted 37 lines · Michael S. Tsirkin
Quoted 22 lines · Junio C Hamano
Quoted 14 lines · Michael S. Tsirkin
Quoted 5 lines · Junio C Hamano
Quoted 2 lines · Michael S. Tsirkin
So might it not be useful to tweak patch id to
sort the diff, making it a bit more stable?Quoted 7 lines
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.
Quoted 1 line
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.
Quoted 7 lines
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?
Quoted 8 lines
Quoted 4 lines
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...
Quoted 2 lines
Quoted 2 lines
Signature · 1 line
MST
Quoted 13 lines · Junio C Hamano
Quoted 2 lines · Michael S. Tsirkin
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.
Quoted 5 lines
Quoted 2 lines
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.