[PATCH] diff: add a config option to control orderfile

[PATCH] diff: add a config option to control orderfile

[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 <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

Re: [PATCH] diff: add a config option to control orderfile

[Junio C Hamano]

"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);

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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);

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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);

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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);

Re: [PATCH] diff: add a config option to control orderfile

[Junio C Hamano]

"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.

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Junio C Hamano]

"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).

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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).

Re: [PATCH] diff: add a config option to control orderfile

[Junio C Hamano]

"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?

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Jeff King]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Jeff King]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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.

Re: [PATCH] diff: add a config option to control orderfile

[Jeff King]

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

Re: [PATCH] diff: add a config option to control orderfile

[Junio C Hamano]

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.

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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.

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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
> 

Re: [PATCH] diff: add a config option to control orderfile

[Jonathan Nieder]

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

Re: [PATCH] diff: add a config option to control orderfile

[Jeff King]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Jonathan Nieder]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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 ?

Re: [PATCH] diff: add a config option to control orderfile

[Jonathan Nieder]

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

Re: [PATCH] diff: add a config option to control orderfile

[Michael S. Tsirkin]

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

Re: [PATCH] diff: add a config option to control orderfile

[Jonathan Nieder]

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