RFC patchDocumentation: rev-list-options: clarify history simplification with paths

This is an attempt to rewrite the documentation for --full-history, --simplify-merges, and --sparse for clarity.

--prune-merges does not exist yet, but would be intended to restore the default behavior over possible earlier --full-history and --simplify-merges.

WARNING: Does not match current code behavior.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---

This is fallout from my investigation of rev-list during the filter-branch topic. I found the descriptions quite unhelpful, and investigated commit logs and empiric behavior a bit.

The problem is, rev-list behaves quite erratically if one mixes --sparse, --full-history and --parents in combinations.

With the history from the patch, i.e.

  $ git log --graph --pretty=oneline --abbrev-commit --decorate
  *-.   e0083e6... (refs/heads/master) Merge branches 'side' and 'unrelated'
  |\ \
  | | * b3127f4... (refs/heads/unrelated) d: unrelated
  | * | 984aa48... (refs/heads/side) C: dir=B
  | |/
  * | aad9982... B: dir
  |/
  * b60c459... A: dir
  * ad7052b... initial

where only commits with 'dir' touch the 'dir' subdirectory, and C=B in terms of diffs, a few unexpected things happen. (I manually applied --abbrev-commit to rev-list output to make it fit in less columns.)

As noted in the patch, I would expect the default pruning to simplify the history to 'o -- A -- B -- m' (drop parent 'd' because the entire sideline is non-touching; drop parent 'C' because it is the same as 'B'), and then have --dense decide to drop 'o' and 'm' because they are not touching. The output agrees:

  $ git rev-list --pretty=oneline HEAD -- dir
  aad9982... B: dir
  b60c459... A: dir

Also, --sparse tends to support this two-pass simplification theory:

  $ git rev-list --pretty=oneline --sparse HEAD -- dir
  e0083e6... Merge branches 'side' and 'unrelated'
  aad9982... B: dir
  b60c459... A: dir
  ad7052b... initial

Now according to current docs, --full-history should turn off removing "merges which didn't change anything at all at some child", but still "simplify away merges that didn't change anything at all into either child." How does being a merge have anything to do with it's _children_? So I read this as saying that a merge is removed iff it agrees with all _parents_. However, despite having a merge that is different relative to its third parent, it is dropped:

  $ g rev-list --pretty=oneline --full-history HEAD -- dir
  984aa48... C: dir=B
  aad9982... B: dir
  b60c459... A: dir

But --parents --full-history magically revives the merge:

  $ git rev-list --pretty=oneline --parents --full-history HEAD -- dir
  e0083e6... aad9982... 984aa48... b60c459... Merge branches 'side' and 'unrelated'
  984aa48... b60c459... C: dir=B
  aad9982... b60c459... B: dir
  b60c459... A: dir

One quickly verifies that --sparse --full-history shows everything, as it should.

More to the point, --simplify-merges actually shows the merge when --full-history does not, resulting in

  $ git rev-list --pretty=oneline --simplify-merges HEAD -- dir
  e0083e6... Merge branches 'side' and 'unrelated'
  984aa48... C: dir=B
  aad9982... B: dir
  b60c459... A: dir

despite the commit message (90818fdc) claiming that it is an additional simplification on top of --full-history, and should therefore output at most as many commits. --parents seems to agree that the simplification is working right:

  $ git rev-list --pretty=oneline --parents --simplify-merges HEAD -- dir
  e0083e6... aad9982... 984aa48... Merge branches 'side' and 'unrelated'
  984aa48... b60c459... C: dir=B
  aad9982... b60c459... B: dir
  b60c459... A: dir

(Note that it dropped the third unrelated parent.)

Furthermore, with --sparse the same turns into

  $ git rev-list --pretty=oneline --sparse --parents --simplify-merges HEAD -- dir
  e0083e6... aad9982... 984aa48... b3127f4... Merge branches 'side' and 'unrelated'
  b3127f4... b60c459... d: unrelated
  984aa48... b60c459... C: dir=B
  aad9982... b60c459... B: dir
  b60c459... ad7052b... A: dir
  ad7052b... initial

So it didn't simplify away the parent 'd' after all, even though 90818fdc (in the second * bullet) does not mention any criterion that would make 'd' its own replacement. (I would actually expect it to replace 'd' with 'initial' on that ancestor line, and subsequently prune that parent because it is redundant.)

So if anyone read this mail up to this point: Which of these are actual bugs? Which of them are a misunderstanding on my part?

Thanks for your time,

Thomas

 Documentation/rev-list-options.txt |   97 ++++++++++++++++++++++++++++-------
 1 files changed, 77 insertions(+), 20 deletions(-)

Thomas Rast <trast@student.ethz.ch> writes:

Personally I do not think --full-history without --parents is of much usefulness (I'd let Linus or somebody else defend this usage, or make it imply revs.rewrite_parents otherwise). If you remove that case from your set of experiments in the equation, do the rest of the results make sense?

One thing I forgot to mention (but the code of course does not forget to do) in the series is that --simplify-merges implies revs.rewrite_parents which roughly translates to your experiments from the command line to always have --parents option.

I am not sure what one should expect from combination between these two options. --sparse says do not drop commits that are of no interest with respect to the paths specified, while --simplify-merges tells it to simplify merges so that the remaining graph shows only the ones that have relevance to !TREESAME (iow "has some changes") nodes.

On Sun, 10 Aug 2008, Junio C Hamano wrote:

Oh, it's _very_ useful.

The most common case is "git whatchanged". It's useful to find a commit that did some change _without_ any graphical front-end.

And then the merges and parenthood are totally pointless - no human can try to tie things together in their head _anyway_, so why show them? You just want to find the change.

			Linus

Linus Torvalds <torvalds@linux-foundation.org> writes:

Oh, I was not talking about revs.print_parents part, but about revs.rewrite_parents part. What got Thomas puzzled about was exactly how the set of commits _shown_ are different with and without --parents, which sets both of these internal flags. Your "pointless" argument applies to "print_parents" part, but "rewrite_parents" affects the resulting set.

On Sun, 10 Aug 2008, Junio C Hamano wrote:

Umm. Since --parents sets both, I don't see the point of that statement.

The fact is, --parents makes us show parenthood. That means that we need the merges to show up, otherwise the parenthood is meaningless.

So without "--parents", there is absolutely no point in showing the merges that don't have any other reason to be shown. And _with_ --parents, we need to show them because they matter for parenthood.

What's so confusing or hard to understand?

And yes, we now have split that "parents" flag into two separate flags internally, but that has absolutely _zero_ meaning for "--parents" itself, and it is totally irrelevant and meaningless to bring up that internal implementation issue and mentioning "print_parents" and "rewrite_parents".

They are immaterial to the actual argument, and the split-up happened because of the "--graph" flag, where we actually *do* show parents too, but we show them through the graph, not by printing the SHA1 of the parent. So the reason "rewrite_parents" is the one that affects the set of commits that get output is a small _internal_ implementation detail, and I really don't see what it has to do with anything at all.

So the fact is:

 - "rewrite_parents" is the flag that says that we are interested in 
   parenthood and keeping the graph consistent and dense.

   This very much implies showing merges that would otherwise not be 
   relevant.

 - "print_parents" is just a flag whether we should print the parent SHA1 
   or not. Nothing less, nothing more.

   This one has absolutely no relevance to whether a merge should be shown 
   or not, since it only affects the output _format_. It's related to 
   pretty-printing, not to anything else!

I really don't see what the confusion is all about. It's very straightforward and obvious.

			Linus

Junio C Hamano wrote:

Well,

  --parents::
          Print the parents of the commit.

does not mention any change in behaviour. I find it very surprising that a simple commit formatting option changes the way commits are _selected_.

Then it makes sense of course.

[...]

It makes sense assuming a one-pass (plus simplify-merges) model. It did not fit into my two-pass model that I tried to come up with for an easier explanation.

So in my current (ahem, new) understanding, that means (assuming the side effect of --parents):

The simplification follows commits backwards into history according to the following rules:

--dense:
	Non-merges are included if TREESAME[1], otherwise they are
	skipped.
--sparse:
	Non-merges are always included.

default:
	Merges are included unless they are TREESAME with a parent, in
	which case they are skipped and only that parent is followed.
--full-history:
	Merges are always included.

Conceptually, that builds a subset of the history, although it is not kept in memory unless absolutely required. Then:

--simplify-commits:
	Implies --full-history, then applies your algorithm on the
	resulting subset.

Which probably means that --sparse --simplify-commits makes no sense, but explains the results.

Note that --full-history makes no exceptions, not even for merges that are TREESAME w.r.t. all parents, unlike current docs state. (This is empirically correct.) If the above is correct, and you think that has some merit, I'll rewrite my patch to reflect this (with examples) to update the docs.

- Thomas

[1] I still think "touching" was a pretty neat idea ;-)

Thomas Rast <trast@student.ethz.ch> writes:

Actually, I felt it was a horrible wording, because the first association I got from the word was with "emotionally moved", and not about !TREESAME which is "Does the commit modify the specified paths?" at all.

Thomas Rast <trast@student.ethz.ch> writes:

What was the meaning of the double-dash at the beginning of line in AsciiDoc markup? I forgot.

Please draw it a bit more consistently with pictures in other existing documentation, perhaps like this:

              d---.  
             /     \
        o---A---B---m
             \     /
              C---.

I'd rather make this the part of the base text. In other words, remove the "--prune-merges" header, dedent the description and start the sentence with "By default, parents of a merge is rewritten with the following rules:".

Then before listing the options, say something like "You can influence how simplification works using the following options".

Also this option implies --full-history's true meaning "do not cull side branches even when they led to the same conclusion", with --parent's meaning "do not drop merges that are necessary to keep the rewritten history still connected".

Same comment on the way the picture is drawn.

With clarification from Linus yesterday, this would need rewording. It is not about "simplifying merges", but its main focus is "do not cull side branches". When --parents is in effect, merges need to be shown because otherwise the resulting list of commits won't be connected, but otherwise you are getting a flat list of commits and useless merges won't be shown.

Junio C Hamano <gitster@pobox.com> wrote:

Thanks for taking the time to look into this!

I wish I knew. I simply copied that from elsewhere in the docs to make it shut up about an error. It would seem that it is required to end the list before a title, except if there's already an 'if' doing the split, unless on a full moon, except if it's wednesday. I've tried to make the patches compile with asciidoc (8.2.5 here), but that's about as far as it goes.

I haven't found any mention of the magic features of '^--' in the user manual, though the cheat sheet

  http://powerman.name/doc/asciidoc

has nice examples how to interrupt lists, which I used for the upcoming patch contents.

Hmm. I've tried to give the new examples a more compact and round appearance, like in your example. Tell me if that works for you.

I dropped the "--prune-merges" since it would be a new option. However, I would like to keep some sort of "Default mode" header (not necessarily as a list header, if you have better ideas). Otherwise, upon encountering "--full-history ... differs from the default", the reader would have to (tediously) scan several paragraph breaks to discover where the default begins.

I completely rewrote it along the outlines given in my own followup. I also devised a better example that shows the differences between all-TREESAME merges, one-TREESAME merges, and (!)TREESAME commits. I am open for further suggestions of course. (I'm also violating the "no patches after midnight" rule, so feel free to point out obvious mistakes too.)

I furthermore split the patch into two halves:

* 2/3 applies on top of master, so that it is independent of
  --simplify-merges.

* 3/3 replaces the docs coming with --simplify-merges with an extra
  paragraph in 'History Simplification'.

I hope that's the right way to proceed. This does mean you will get a merge conflict when merging jc/post-simplify, but it's a fairly obvious one.

1/3 is just a one-character typo that I discovered along the way.

Finally, I'm attaching a script that generates a repository with the history used in the example.

- Thomas

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 Documentation/rev-list-options.txt |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

This completely rewrites the documentation of --full-history with lots of examples.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 Documentation/rev-list-options.txt |  153 ++++++++++++++++++++++++++++++++----
 1 files changed, 136 insertions(+), 17 deletions(-)

Fits --simplify-merges documentation into the 'History Simplification' section, including example.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 Documentation/rev-list-options.txt |   48 +++++++++++++++++++++++++++++++----
 1 files changed, 42 insertions(+), 6 deletions(-)