Merge branch 'jc/rev-list-ancestry-path'

* jc/rev-list-ancestry-path:
revision: Turn off history simplification in --ancestry-path mode
revision: Fix typo in --ancestry-path error message
Documentation/rev-list-options.txt: Explain --ancestry-path
Documentation/rev-list-options.txt: Fix missing line in example history graph
revision: --ancestry-path

diff --combined revision.c
index b209d493e169ae58130a998f7dc1239f5a385c44,96d7fa7f143b8680fe638e1ea69f4ec172fcedad..7847921658c0f0b13c51650057b907ee431b1378
--- 1/revision.c
--- 2/revision.c
+++ b/revision.c
@@@ -646,6 -646,93 +646,93 @@@ static int still_interesting(struct com
        return slop-1;
  }
  
+ /*
+  * "rev-list --ancestry-path A..B" computes commits that are ancestors
+  * of B but not ancestors of A but further limits the result to those
+  * that are descendants of A.  This takes the list of bottom commits and
+  * the result of "A..B" without --ancestry-path, and limits the latter
+  * further to the ones that can reach one of the commits in "bottom".
+  */
+ static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *list)
+ {
+       struct commit_list *p;
+       struct commit_list *rlist = NULL;
+       int made_progress;
+ 
+       /*
+        * Reverse the list so that it will be likely that we would
+        * process parents before children.
+        */
+       for (p = list; p; p = p->next)
+               commit_list_insert(p->item, &rlist);
+ 
+       for (p = bottom; p; p = p->next)
+               p->item->object.flags |= TMP_MARK;
+ 
+       /*
+        * Mark the ones that can reach bottom commits in "list",
+        * in a bottom-up fashion.
+        */
+       do {
+               made_progress = 0;
+               for (p = rlist; p; p = p->next) {
+                       struct commit *c = p->item;
+                       struct commit_list *parents;
+                       if (c->object.flags & (TMP_MARK | UNINTERESTING))
+                               continue;
+                       for (parents = c->parents;
+                            parents;
+                            parents = parents->next) {
+                               if (!(parents->item->object.flags & TMP_MARK))
+                                       continue;
+                               c->object.flags |= TMP_MARK;
+                               made_progress = 1;
+                               break;
+                       }
+               }
+       } while (made_progress);
+ 
+       /*
+        * NEEDSWORK: decide if we want to remove parents that are
+        * not marked with TMP_MARK from commit->parents for commits
+        * in the resulting list.  We may not want to do that, though.
+        */
+ 
+       /*
+        * The ones that are not marked with TMP_MARK are uninteresting
+        */
+       for (p = list; p; p = p->next) {
+               struct commit *c = p->item;
+               if (c->object.flags & TMP_MARK)
+                       continue;
+               c->object.flags |= UNINTERESTING;
+       }
+ 
+       /* We are done with the TMP_MARK */
+       for (p = list; p; p = p->next)
+               p->item->object.flags &= ~TMP_MARK;
+       for (p = bottom; p; p = p->next)
+               p->item->object.flags &= ~TMP_MARK;
+       free_commit_list(rlist);
+ }
+ 
+ /*
+  * Before walking the history, keep the set of "negative" refs the
+  * caller has asked to exclude.
+  *
+  * This is used to compute "rev-list --ancestry-path A..B", as we need
+  * to filter the result of "A..B" further to the ones that can actually
+  * reach A.
+  */
+ static struct commit_list *collect_bottom_commits(struct commit_list *list)
+ {
+       struct commit_list *elem, *bottom = NULL;
+       for (elem = list; elem; elem = elem->next)
+               if (elem->item->object.flags & UNINTERESTING)
+                       commit_list_insert(elem->item, &bottom);
+       return bottom;
+ }
+ 
  static int limit_list(struct rev_info *revs)
  {
        int slop = SLOP;
@@@ -653,6 -740,13 +740,13 @@@
        struct commit_list *list = revs->commits;
        struct commit_list *newlist = NULL;
        struct commit_list **p = &newlist;
+       struct commit_list *bottom = NULL;
+ 
+       if (revs->ancestry_path) {
+               bottom = collect_bottom_commits(list);
+               if (!bottom)
+                       die("--ancestry-path given but there are no bottom commits");
+       }
  
        while (list) {
                struct commit_list *entry = list;
@@@ -694,6 -788,11 +788,11 @@@
        if (revs->cherry_pick)
                cherry_pick_list(newlist, revs);
  
+       if (bottom) {
+               limit_to_ancestry(bottom, newlist);
+               free_commit_list(bottom);
+       }
+ 
        revs->commits = newlist;
        return 0;
  }
@@@ -1089,6 -1188,10 +1188,10 @@@ static int handle_revision_opt(struct r
                revs->min_age = approxidate(arg + 8);
        } else if (!strcmp(arg, "--first-parent")) {
                revs->first_parent_only = 1;
+       } else if (!strcmp(arg, "--ancestry-path")) {
+               revs->ancestry_path = 1;
+               revs->simplify_history = 0;
+               revs->limited = 1;
        } else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) {
                init_reflog_walk(&revs->reflog_info);
        } else if (!strcmp(arg, "--default")) {
@@@ -1781,7 -1884,7 +1884,7 @@@ int prepare_revision_walk(struct rev_in
  enum rewrite_result {
        rewrite_one_ok,
        rewrite_one_noparents,
 -      rewrite_one_error,
 +      rewrite_one_error
  };
  
  static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)