ls-remote doc: rewrite <repository> paragraph
[gitweb.git] / revision.c
index a67b615bfc7001ac28e339db1d91ea46a1b125b5..f1bb731fd71eb874344faa5376e7c375ac2fcf7f 100644 (file)
@@ -13,6 +13,7 @@
 #include "decorate.h"
 #include "log-tree.h"
 #include "string-list.h"
+#include "line-log.h"
 #include "mailmap.h"
 
 volatile show_early_output_fn_t show_early_output;
@@ -70,7 +71,8 @@ static int show_path_truncated(FILE *out, const struct name_path *path)
        return ours || emitted;
 }
 
-void show_object_with_name(FILE *out, struct object *obj, const struct name_path *path, const char *component)
+void show_object_with_name(FILE *out, struct object *obj,
+                          const struct name_path *path, const char *component)
 {
        struct name_path leaf;
        leaf.up = (struct name_path *)path;
@@ -87,7 +89,9 @@ void add_object(struct object *obj,
                struct name_path *path,
                const char *name)
 {
-       add_object_array(obj, path_name(path, name), p);
+       char *pn = path_name(path, name);
+       add_object_array(obj, pn, p);
+       free(pn);
 }
 
 static void mark_blob_uninteresting(struct blob *blob)
@@ -186,7 +190,9 @@ void mark_parents_uninteresting(struct commit *commit)
        }
 }
 
-static void add_pending_object_with_mode(struct rev_info *revs, struct object *obj, const char *name, unsigned mode)
+static void add_pending_object_with_mode(struct rev_info *revs,
+                                        struct object *obj,
+                                        const char *name, unsigned mode)
 {
        if (!obj)
                return;
@@ -209,7 +215,8 @@ static void add_pending_object_with_mode(struct rev_info *revs, struct object *o
        add_object_array_with_mode(obj, name, &revs->pending, mode);
 }
 
-void add_pending_object(struct rev_info *revs, struct object *obj, const char *name)
+void add_pending_object(struct rev_info *revs,
+                       struct object *obj, const char *name)
 {
        add_pending_object_with_mode(revs, obj, name, S_IFINVALID);
 }
@@ -226,7 +233,9 @@ void add_head_to_pending(struct rev_info *revs)
        add_pending_object(revs, obj, "HEAD");
 }
 
-static struct object *get_reference(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags)
+static struct object *get_reference(struct rev_info *revs, const char *name,
+                                   const unsigned char *sha1,
+                                   unsigned int flags)
 {
        struct object *object;
 
@@ -247,7 +256,8 @@ void add_pending_sha1(struct rev_info *revs, const char *name,
        add_pending_object(revs, object, name);
 }
 
-static struct commit *handle_commit(struct rev_info *revs, struct object *object, const char *name)
+static struct commit *handle_commit(struct rev_info *revs,
+                                   struct object *object, const char *name)
 {
        unsigned long flags = object->flags;
 
@@ -332,6 +342,80 @@ static int everybody_uninteresting(struct commit_list *orig)
        return 1;
 }
 
+/*
+ * A definition of "relevant" commit that we can use to simplify limited graphs
+ * by eliminating side branches.
+ *
+ * A "relevant" commit is one that is !UNINTERESTING (ie we are including it
+ * in our list), or that is a specified BOTTOM commit. Then after computing
+ * a limited list, during processing we can generally ignore boundary merges
+ * coming from outside the graph, (ie from irrelevant parents), and treat
+ * those merges as if they were single-parent. TREESAME is defined to consider
+ * only relevant parents, if any. If we are TREESAME to our on-graph parents,
+ * we don't care if we were !TREESAME to non-graph parents.
+ *
+ * Treating bottom commits as relevant ensures that a limited graph's
+ * connection to the actual bottom commit is not viewed as a side branch, but
+ * treated as part of the graph. For example:
+ *
+ *   ....Z...A---X---o---o---B
+ *        .     /
+ *         W---Y
+ *
+ * When computing "A..B", the A-X connection is at least as important as
+ * Y-X, despite A being flagged UNINTERESTING.
+ *
+ * And when computing --ancestry-path "A..B", the A-X connection is more
+ * important than Y-X, despite both A and Y being flagged UNINTERESTING.
+ */
+static inline int relevant_commit(struct commit *commit)
+{
+       return (commit->object.flags & (UNINTERESTING | BOTTOM)) != UNINTERESTING;
+}
+
+/*
+ * Return a single relevant commit from a parent list. If we are a TREESAME
+ * commit, and this selects one of our parents, then we can safely simplify to
+ * that parent.
+ */
+static struct commit *one_relevant_parent(const struct rev_info *revs,
+                                         struct commit_list *orig)
+{
+       struct commit_list *list = orig;
+       struct commit *relevant = NULL;
+
+       if (!orig)
+               return NULL;
+
+       /*
+        * For 1-parent commits, or if first-parent-only, then return that
+        * first parent (even if not "relevant" by the above definition).
+        * TREESAME will have been set purely on that parent.
+        */
+       if (revs->first_parent_only || !orig->next)
+               return orig->item;
+
+       /*
+        * For multi-parent commits, identify a sole relevant parent, if any.
+        * If we have only one relevant parent, then TREESAME will be set purely
+        * with regard to that parent, and we can simplify accordingly.
+        *
+        * If we have more than one relevant parent, or no relevant parents
+        * (and multiple irrelevant ones), then we can't select a parent here
+        * and return NULL.
+        */
+       while (list) {
+               struct commit *commit = list->item;
+               list = list->next;
+               if (relevant_commit(commit)) {
+                       if (relevant)
+                               return NULL;
+                       relevant = commit;
+               }
+       }
+       return relevant;
+}
+
 /*
  * The goal is to get REV_TREE_NEW as the result only if the
  * diff consists of all '+' (and no other changes), REV_TREE_OLD
@@ -368,7 +452,8 @@ static void file_change(struct diff_options *options,
        DIFF_OPT_SET(options, HAS_CHANGES);
 }
 
-static int rev_compare_tree(struct rev_info *revs, struct commit *parent, struct commit *commit)
+static int rev_compare_tree(struct rev_info *revs,
+                           struct commit *parent, struct commit *commit)
 {
        struct tree *t1 = parent->tree;
        struct tree *t2 = commit->tree;
@@ -429,10 +514,125 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
        return retval >= 0 && (tree_difference == REV_TREE_SAME);
 }
 
+struct treesame_state {
+       unsigned int nparents;
+       unsigned char treesame[FLEX_ARRAY];
+};
+
+static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit)
+{
+       unsigned n = commit_list_count(commit->parents);
+       struct treesame_state *st = xcalloc(1, sizeof(*st) + n);
+       st->nparents = n;
+       add_decoration(&revs->treesame, &commit->object, st);
+       return st;
+}
+
+/*
+ * Must be called immediately after removing the nth_parent from a commit's
+ * parent list, if we are maintaining the per-parent treesame[] decoration.
+ * This does not recalculate the master TREESAME flag - update_treesame()
+ * should be called to update it after a sequence of treesame[] modifications
+ * that may have affected it.
+ */
+static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned nth_parent)
+{
+       struct treesame_state *st;
+       int old_same;
+
+       if (!commit->parents) {
+               /*
+                * Have just removed the only parent from a non-merge.
+                * Different handling, as we lack decoration.
+                */
+               if (nth_parent != 0)
+                       die("compact_treesame %u", nth_parent);
+               old_same = !!(commit->object.flags & TREESAME);
+               if (rev_same_tree_as_empty(revs, commit))
+                       commit->object.flags |= TREESAME;
+               else
+                       commit->object.flags &= ~TREESAME;
+               return old_same;
+       }
+
+       st = lookup_decoration(&revs->treesame, &commit->object);
+       if (!st || nth_parent >= st->nparents)
+               die("compact_treesame %u", nth_parent);
+
+       old_same = st->treesame[nth_parent];
+       memmove(st->treesame + nth_parent,
+               st->treesame + nth_parent + 1,
+               st->nparents - nth_parent - 1);
+
+       /*
+        * If we've just become a non-merge commit, update TREESAME
+        * immediately, and remove the no-longer-needed decoration.
+        * If still a merge, defer update until update_treesame().
+        */
+       if (--st->nparents == 1) {
+               if (commit->parents->next)
+                       die("compact_treesame parents mismatch");
+               if (st->treesame[0] && revs->dense)
+                       commit->object.flags |= TREESAME;
+               else
+                       commit->object.flags &= ~TREESAME;
+               free(add_decoration(&revs->treesame, &commit->object, NULL));
+       }
+
+       return old_same;
+}
+
+static unsigned update_treesame(struct rev_info *revs, struct commit *commit)
+{
+       if (commit->parents && commit->parents->next) {
+               unsigned n;
+               struct treesame_state *st;
+               struct commit_list *p;
+               unsigned relevant_parents;
+               unsigned relevant_change, irrelevant_change;
+
+               st = lookup_decoration(&revs->treesame, &commit->object);
+               if (!st)
+                       die("update_treesame %s", sha1_to_hex(commit->object.sha1));
+               relevant_parents = 0;
+               relevant_change = irrelevant_change = 0;
+               for (p = commit->parents, n = 0; p; n++, p = p->next) {
+                       if (relevant_commit(p->item)) {
+                               relevant_change |= !st->treesame[n];
+                               relevant_parents++;
+                       } else
+                               irrelevant_change |= !st->treesame[n];
+               }
+               if (relevant_parents ? relevant_change : irrelevant_change)
+                       commit->object.flags &= ~TREESAME;
+               else
+                       commit->object.flags |= TREESAME;
+       }
+
+       return commit->object.flags & TREESAME;
+}
+
+static inline int limiting_can_increase_treesame(const struct rev_info *revs)
+{
+       /*
+        * TREESAME is irrelevant unless prune && dense;
+        * if simplify_history is set, we can't have a mixture of TREESAME and
+        *    !TREESAME INTERESTING parents (and we don't have treesame[]
+        *    decoration anyway);
+        * if first_parent_only is set, then the TREESAME flag is locked
+        *    against the first parent (and again we lack treesame[] decoration).
+        */
+       return revs->prune && revs->dense &&
+              !revs->simplify_history &&
+              !revs->first_parent_only;
+}
+
 static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 {
        struct commit_list **pp, *parent;
-       int tree_changed = 0, tree_same = 0, nth_parent = 0;
+       struct treesame_state *ts = NULL;
+       int relevant_change = 0, irrelevant_change = 0;
+       int relevant_parents, nth_parent;
 
        /*
         * If we don't do pruning, everything is interesting
@@ -456,33 +656,54 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
        if (!revs->dense && !commit->parents->next)
                return;
 
-       pp = &commit->parents;
-       while ((parent = *pp) != NULL) {
+       for (pp = &commit->parents, nth_parent = 0, relevant_parents = 0;
+            (parent = *pp) != NULL;
+            pp = &parent->next, nth_parent++) {
                struct commit *p = parent->item;
+               if (relevant_commit(p))
+                       relevant_parents++;
 
-               /*
-                * Do not compare with later parents when we care only about
-                * the first parent chain, in order to avoid derailing the
-                * traversal to follow a side branch that brought everything
-                * in the path we are limited to by the pathspec.
-                */
-               if (revs->first_parent_only && nth_parent++)
-                       break;
+               if (nth_parent == 1) {
+                       /*
+                        * This our second loop iteration - so we now know
+                        * we're dealing with a merge.
+                        *
+                        * Do not compare with later parents when we care only about
+                        * the first parent chain, in order to avoid derailing the
+                        * traversal to follow a side branch that brought everything
+                        * in the path we are limited to by the pathspec.
+                        */
+                       if (revs->first_parent_only)
+                               break;
+                       /*
+                        * If this will remain a potentially-simplifiable
+                        * merge, remember per-parent treesame if needed.
+                        * Initialise the array with the comparison from our
+                        * first iteration.
+                        */
+                       if (revs->treesame.name &&
+                           !revs->simplify_history &&
+                           !(commit->object.flags & UNINTERESTING)) {
+                               ts = initialise_treesame(revs, commit);
+                               if (!(irrelevant_change || relevant_change))
+                                       ts->treesame[0] = 1;
+                       }
+               }
                if (parse_commit(p) < 0)
                        die("cannot simplify commit %s (because of %s)",
                            sha1_to_hex(commit->object.sha1),
                            sha1_to_hex(p->object.sha1));
                switch (rev_compare_tree(revs, p, commit)) {
                case REV_TREE_SAME:
-                       tree_same = 1;
-                       if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {
+                       if (!revs->simplify_history || !relevant_commit(p)) {
                                /* Even if a merge with an uninteresting
                                 * side branch brought the entire change
                                 * we are interested in, we do not want
                                 * to lose the other branches of this
                                 * merge, so we just keep going.
                                 */
-                               pp = &parent->next;
+                               if (ts)
+                                       ts->treesame[nth_parent] = 1;
                                continue;
                        }
                        parent->next = NULL;
@@ -510,15 +731,27 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
                /* fallthrough */
                case REV_TREE_OLD:
                case REV_TREE_DIFFERENT:
-                       tree_changed = 1;
-                       pp = &parent->next;
+                       if (relevant_commit(p))
+                               relevant_change = 1;
+                       else
+                               irrelevant_change = 1;
                        continue;
                }
                die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
        }
-       if (tree_changed && !tree_same)
-               return;
-       commit->object.flags |= TREESAME;
+
+       /*
+        * TREESAME is straightforward for single-parent commits. For merge
+        * commits, it is most useful to define it so that "irrelevant"
+        * parents cannot make us !TREESAME - if we have any relevant
+        * parents, then we only consider TREESAMEness with respect to them,
+        * allowing irrelevant merges from uninteresting branches to be
+        * simplified away. Only if we have only irrelevant parents do we
+        * base TREESAME on them. Note that this logic is replicated in
+        * update_treesame, which should be kept in sync.
+        */
+       if (relevant_parents ? !relevant_change : !irrelevant_change)
+               commit->object.flags |= TREESAME;
 }
 
 static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head,
@@ -801,16 +1034,12 @@ static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *li
  * to filter the result of "A..B" further to the ones that can actually
  * reach A.
  */
-static struct commit_list *collect_bottom_commits(struct rev_info *revs)
+static struct commit_list *collect_bottom_commits(struct commit_list *list)
 {
-       struct commit_list *bottom = NULL;
-       int i;
-       for (i = 0; i < revs->cmdline.nr; i++) {
-               struct rev_cmdline_entry *elem = &revs->cmdline.rev[i];
-               if ((elem->flags & UNINTERESTING) &&
-                   elem->item->type == OBJ_COMMIT)
-                       commit_list_insert((struct commit *)elem->item, &bottom);
-       }
+       struct commit_list *elem, *bottom = NULL;
+       for (elem = list; elem; elem = elem->next)
+               if (elem->item->object.flags & BOTTOM)
+                       commit_list_insert(elem->item, &bottom);
        return bottom;
 }
 
@@ -841,7 +1070,7 @@ static int limit_list(struct rev_info *revs)
        struct commit_list *bottom = NULL;
 
        if (revs->ancestry_path) {
-               bottom = collect_bottom_commits(revs);
+               bottom = collect_bottom_commits(list);
                if (!bottom)
                        die("--ancestry-path given but there are no bottom commits");
        }
@@ -894,10 +1123,26 @@ static int limit_list(struct rev_info *revs)
                free_commit_list(bottom);
        }
 
+       /*
+        * Check if any commits have become TREESAME by some of their parents
+        * becoming UNINTERESTING.
+        */
+       if (limiting_can_increase_treesame(revs))
+               for (list = newlist; list; list = list->next) {
+                       struct commit *c = list->item;
+                       if (c->object.flags & (UNINTERESTING | TREESAME))
+                               continue;
+                       update_treesame(revs, c);
+               }
+
        revs->commits = newlist;
        return 0;
 }
 
+/*
+ * Add an entry to refs->cmdline with the specified information.
+ * *name is copied.
+ */
 static void add_rev_cmdline(struct rev_info *revs,
                            struct object *item,
                            const char *name,
@@ -909,12 +1154,25 @@ static void add_rev_cmdline(struct rev_info *revs,
 
        ALLOC_GROW(info->rev, nr + 1, info->alloc);
        info->rev[nr].item = item;
-       info->rev[nr].name = name;
+       info->rev[nr].name = xstrdup(name);
        info->rev[nr].whence = whence;
        info->rev[nr].flags = flags;
        info->nr++;
 }
 
+static void add_rev_cmdline_list(struct rev_info *revs,
+                                struct commit_list *commit_list,
+                                int whence,
+                                unsigned flags)
+{
+       while (commit_list) {
+               struct object *object = &commit_list->item->object;
+               add_rev_cmdline(revs, object, sha1_to_hex(object->sha1),
+                               whence, flags);
+               commit_list = commit_list->next;
+       }
+}
+
 struct all_refs_cb {
        int all_flags;
        int warned_bad_reflog;
@@ -1000,7 +1258,7 @@ static int add_parents_only(struct rev_info *revs, const char *arg_, int flags)
        const char *arg = arg_;
 
        if (*arg == '^') {
-               flags ^= UNINTERESTING;
+               flags ^= UNINTERESTING | BOTTOM;
                arg++;
        }
        if (get_sha1_committish(arg, sha1))
@@ -1092,7 +1350,8 @@ static void prepare_show_merge(struct rev_info *revs)
        add_pending_object(revs, &head->object, "HEAD");
        add_pending_object(revs, &other->object, "MERGE_HEAD");
        bases = get_merge_bases(head, other, 1);
-       add_pending_commit_list(revs, bases, UNINTERESTING);
+       add_rev_cmdline_list(revs, bases, REV_CMD_MERGE_BASE, UNINTERESTING | BOTTOM);
+       add_pending_commit_list(revs, bases, UNINTERESTING | BOTTOM);
        free_commit_list(bases);
        head->object.flags |= SYMMETRIC_LEFT;
 
@@ -1128,13 +1387,15 @@ int handle_revision_arg(const char *arg_, struct rev_info *revs, int flags, unsi
        int cant_be_filename = revarg_opt & REVARG_CANNOT_BE_FILENAME;
        unsigned get_sha1_flags = 0;
 
+       flags = flags & UNINTERESTING ? flags | BOTTOM : flags & ~BOTTOM;
+
        dotdot = strstr(arg, "..");
        if (dotdot) {
                unsigned char from_sha1[20];
                const char *next = dotdot + 2;
                const char *this = arg;
                int symmetric = *next == '.';
-               unsigned int flags_exclude = flags ^ UNINTERESTING;
+               unsigned int flags_exclude = flags ^ (UNINTERESTING | BOTTOM);
                static const char head_by_default[] = "HEAD";
                unsigned int a_flags;
 
@@ -1179,6 +1440,9 @@ int handle_revision_arg(const char *arg_, struct rev_info *revs, int flags, unsi
 
                        if (symmetric) {
                                exclude = get_merge_bases(a, b, 1);
+                               add_rev_cmdline_list(revs, exclude,
+                                                    REV_CMD_MERGE_BASE,
+                                                    flags_exclude);
                                add_pending_commit_list(revs, exclude,
                                                        flags_exclude);
                                free_commit_list(exclude);
@@ -1207,13 +1471,13 @@ int handle_revision_arg(const char *arg_, struct rev_info *revs, int flags, unsi
        dotdot = strstr(arg, "^!");
        if (dotdot && !dotdot[2]) {
                *dotdot = 0;
-               if (!add_parents_only(revs, arg, flags ^ UNINTERESTING))
+               if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM)))
                        *dotdot = '^';
        }
 
        local_flags = 0;
        if (*arg == '^') {
-               local_flags = UNINTERESTING;
+               local_flags = UNINTERESTING | BOTTOM;
                arg++;
        }
 
@@ -1276,7 +1540,7 @@ static void read_revisions_from_stdin(struct rev_info *revs,
                        }
                        die("options not supported in --stdin mode");
                }
-               if (handle_revision_arg(xstrdup(sb.buf), revs, 0,
+               if (handle_revision_arg(sb.buf, revs, 0,
                                        REVARG_CANNOT_BE_FILENAME))
                        die("bad revision '%s'", sb.buf);
        }
@@ -1690,7 +1954,7 @@ static int handle_revision_pseudo_opt(const char *submodule,
                handle_refs(submodule, revs, *flags, for_each_branch_ref_submodule);
        } else if (!strcmp(arg, "--bisect")) {
                handle_refs(submodule, revs, *flags, for_each_bad_bisect_ref);
-               handle_refs(submodule, revs, *flags ^ UNINTERESTING, for_each_good_bisect_ref);
+               handle_refs(submodule, revs, *flags ^ (UNINTERESTING | BOTTOM), for_each_good_bisect_ref);
                revs->bisect = 1;
        } else if (!strcmp(arg, "--tags")) {
                handle_refs(submodule, revs, *flags, for_each_tag_ref_submodule);
@@ -1716,7 +1980,7 @@ static int handle_revision_pseudo_opt(const char *submodule,
        } else if (!strcmp(arg, "--reflog")) {
                handle_reflog(revs, *flags);
        } else if (!strcmp(arg, "--not")) {
-               *flags ^= UNINTERESTING;
+               *flags ^= UNINTERESTING | BOTTOM;
        } else if (!strcmp(arg, "--no-walk")) {
                revs->no_walk = REVISION_WALK_NO_WALK_SORTED;
        } else if (!prefixcmp(arg, "--no-walk=")) {
@@ -1897,6 +2161,12 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
        if (revs->combine_merges)
                revs->ignore_merges = 0;
        revs->diffopt.abbrev = revs->abbrev;
+
+       if (revs->line_level_traverse) {
+               revs->limited = 1;
+               revs->topo_order = 1;
+       }
+
        diff_setup_done(&revs->diffopt);
 
        grep_commit_pattern_type(GREP_PATTERN_TYPE_UNSPECIFIED,
@@ -1930,28 +2200,32 @@ static void add_child(struct rev_info *revs, struct commit *parent, struct commi
        l->next = add_decoration(&revs->children, &parent->object, l);
 }
 
-static int remove_duplicate_parents(struct commit *commit)
+static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit)
 {
+       struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
        struct commit_list **pp, *p;
        int surviving_parents;
 
        /* Examine existing parents while marking ones we have seen... */
        pp = &commit->parents;
+       surviving_parents = 0;
        while ((p = *pp) != NULL) {
                struct commit *parent = p->item;
                if (parent->object.flags & TMP_MARK) {
                        *pp = p->next;
+                       if (ts)
+                               compact_treesame(revs, commit, surviving_parents);
                        continue;
                }
                parent->object.flags |= TMP_MARK;
+               surviving_parents++;
                pp = &p->next;
        }
-       /* count them while clearing the temporary mark */
-       surviving_parents = 0;
+       /* clear the temporary mark */
        for (p = commit->parents; p; p = p->next) {
                p->item->object.flags &= ~TMP_MARK;
-               surviving_parents++;
        }
+       /* no update_treesame() - removing duplicates can't affect TREESAME */
        return surviving_parents;
 }
 
@@ -1971,9 +2245,157 @@ static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs,
        return st;
 }
 
+static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)
+{
+       struct commit_list *h = reduce_heads(commit->parents);
+       int i = 0, marked = 0;
+       struct commit_list *po, *pn;
+
+       /* Want these for sanity-checking only */
+       int orig_cnt = commit_list_count(commit->parents);
+       int cnt = commit_list_count(h);
+
+       /*
+        * Not ready to remove items yet, just mark them for now, based
+        * on the output of reduce_heads(). reduce_heads outputs the reduced
+        * set in its original order, so this isn't too hard.
+        */
+       po = commit->parents;
+       pn = h;
+       while (po) {
+               if (pn && po->item == pn->item) {
+                       pn = pn->next;
+                       i++;
+               } else {
+                       po->item->object.flags |= TMP_MARK;
+                       marked++;
+               }
+               po=po->next;
+       }
+
+       if (i != cnt || cnt+marked != orig_cnt)
+               die("mark_redundant_parents %d %d %d %d", orig_cnt, cnt, i, marked);
+
+       free_commit_list(h);
+
+       return marked;
+}
+
+static int mark_treesame_root_parents(struct rev_info *revs, struct commit *commit)
+{
+       struct commit_list *p;
+       int marked = 0;
+
+       for (p = commit->parents; p; p = p->next) {
+               struct commit *parent = p->item;
+               if (!parent->parents && (parent->object.flags & TREESAME)) {
+                       parent->object.flags |= TMP_MARK;
+                       marked++;
+               }
+       }
+
+       return marked;
+}
+
+/*
+ * Awkward naming - this means one parent we are TREESAME to.
+ * cf mark_treesame_root_parents: root parents that are TREESAME (to an
+ * empty tree). Better name suggestions?
+ */
+static int leave_one_treesame_to_parent(struct rev_info *revs, struct commit *commit)
+{
+       struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
+       struct commit *unmarked = NULL, *marked = NULL;
+       struct commit_list *p;
+       unsigned n;
+
+       for (p = commit->parents, n = 0; p; p = p->next, n++) {
+               if (ts->treesame[n]) {
+                       if (p->item->object.flags & TMP_MARK) {
+                               if (!marked)
+                                       marked = p->item;
+                       } else {
+                               if (!unmarked) {
+                                       unmarked = p->item;
+                                       break;
+                               }
+                       }
+               }
+       }
+
+       /*
+        * If we are TREESAME to a marked-for-deletion parent, but not to any
+        * unmarked parents, unmark the first TREESAME parent. This is the
+        * parent that the default simplify_history==1 scan would have followed,
+        * and it doesn't make sense to omit that path when asking for a
+        * simplified full history. Retaining it improves the chances of
+        * understanding odd missed merges that took an old version of a file.
+        *
+        * Example:
+        *
+        *   I--------*X       A modified the file, but mainline merge X used
+        *    \       /        "-s ours", so took the version from I. X is
+        *     `-*A--'         TREESAME to I and !TREESAME to A.
+        *
+        * Default log from X would produce "I". Without this check,
+        * --full-history --simplify-merges would produce "I-A-X", showing
+        * the merge commit X and that it changed A, but not making clear that
+        * it had just taken the I version. With this check, the topology above
+        * is retained.
+        *
+        * Note that it is possible that the simplification chooses a different
+        * TREESAME parent from the default, in which case this test doesn't
+        * activate, and we _do_ drop the default parent. Example:
+        *
+        *   I------X         A modified the file, but it was reverted in B,
+        *    \    /          meaning mainline merge X is TREESAME to both
+        *    *A-*B           parents.
+        *
+        * Default log would produce "I" by following the first parent;
+        * --full-history --simplify-merges will produce "I-A-B". But this is a
+        * reasonable result - it presents a logical full history leading from
+        * I to X, and X is not an important merge.
+        */
+       if (!unmarked && marked) {
+               marked->object.flags &= ~TMP_MARK;
+               return 1;
+       }
+
+       return 0;
+}
+
+static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
+{
+       struct commit_list **pp, *p;
+       int nth_parent, removed = 0;
+
+       pp = &commit->parents;
+       nth_parent = 0;
+       while ((p = *pp) != NULL) {
+               struct commit *parent = p->item;
+               if (parent->object.flags & TMP_MARK) {
+                       parent->object.flags &= ~TMP_MARK;
+                       *pp = p->next;
+                       free(p);
+                       removed++;
+                       compact_treesame(revs, commit, nth_parent);
+                       continue;
+               }
+               pp = &p->next;
+               nth_parent++;
+       }
+
+       /* Removing parents can only increase TREESAMEness */
+       if (removed && !(commit->object.flags & TREESAME))
+               update_treesame(revs, commit);
+
+       return nth_parent;
+}
+
 static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)
 {
        struct commit_list *p;
+       struct commit *parent;
        struct merge_simplify_state *st, *pst;
        int cnt;
 
@@ -2015,7 +2437,9 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
        }
 
        /*
-        * Rewrite our list of parents.
+        * Rewrite our list of parents. Note that this cannot
+        * affect our TREESAME flags in any way - a commit is
+        * always TREESAME to its simplification.
         */
        for (p = commit->parents; p; p = p->next) {
                pst = locate_simplify_state(revs, p->item);
@@ -2027,43 +2451,53 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
        if (revs->first_parent_only)
                cnt = 1;
        else
-               cnt = remove_duplicate_parents(commit);
+               cnt = remove_duplicate_parents(revs, commit);
 
        /*
         * It is possible that we are a merge and one side branch
         * does not have any commit that touches the given paths;
-        * in such a case, the immediate parents will be rewritten
-        * to different commits.
+        * in such a case, the immediate parent from that branch
+        * will be rewritten to be the merge base.
         *
         *      o----X          X: the commit we are looking at;
         *     /    /           o: a commit that touches the paths;
         * ---o----'
         *
-        * Further reduce the parents by removing redundant parents.
+        * Further, a merge of an independent branch that doesn't
+        * touch the path will reduce to a treesame root parent:
+        *
+        *  ----o----X          X: the commit we are looking at;
+        *          /           o: a commit that touches the paths;
+        *         r            r: a root commit not touching the paths
+        *
+        * Detect and simplify both cases.
         */
        if (1 < cnt) {
-               struct commit_list *h = reduce_heads(commit->parents);
-               cnt = commit_list_count(h);
-               free_commit_list(commit->parents);
-               commit->parents = h;
+               int marked = mark_redundant_parents(revs, commit);
+               marked += mark_treesame_root_parents(revs, commit);
+               if (marked)
+                       marked -= leave_one_treesame_to_parent(revs, commit);
+               if (marked)
+                       cnt = remove_marked_parents(revs, commit);
        }
 
        /*
         * A commit simplifies to itself if it is a root, if it is
         * UNINTERESTING, if it touches the given paths, or if it is a
-        * merge and its parents simplifies to more than one commits
+        * merge and its parents don't simplify to one relevant commit
         * (the first two cases are already handled at the beginning of
         * this function).
         *
-        * Otherwise, it simplifies to what its sole parent simplifies to.
+        * Otherwise, it simplifies to what its sole relevant parent
+        * simplifies to.
         */
        if (!cnt ||
            (commit->object.flags & UNINTERESTING) ||
            !(commit->object.flags & TREESAME) ||
-           (1 < cnt))
+           (parent = one_relevant_parent(revs, commit->parents)) == NULL)
                st->simplified = commit;
        else {
-               pst = locate_simplify_state(revs, commit->parents->item);
+               pst = locate_simplify_state(revs, parent);
                st->simplified = pst->simplified;
        }
        return tail;
@@ -2159,6 +2593,11 @@ int prepare_revision_walk(struct rev_info *revs)
        if (!revs->leak_pending)
                free(list);
 
+       /* Signal whether we need per-parent treesame decoration */
+       if (revs->simplify_merges ||
+           (revs->limited && limiting_can_increase_treesame(revs)))
+               revs->treesame.name = "treesame";
+
        if (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)
                commit_list_sort_by_date(&revs->commits);
        if (revs->no_walk)
@@ -2168,6 +2607,8 @@ int prepare_revision_walk(struct rev_info *revs)
                        return -1;
        if (revs->topo_order)
                sort_in_topological_order(&revs->commits, revs->lifo);
+       if (revs->line_level_traverse)
+               line_log_filter(revs);
        if (revs->simplify_merges)
                simplify_merges(revs);
        if (revs->children.name)
@@ -2175,12 +2616,6 @@ int prepare_revision_walk(struct rev_info *revs)
        return 0;
 }
 
-enum rewrite_result {
-       rewrite_one_ok,
-       rewrite_one_noparents,
-       rewrite_one_error
-};
-
 static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)
 {
        struct commit_list *cache = NULL;
@@ -2190,24 +2625,25 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp
                if (!revs->limited)
                        if (add_parents_to_list(revs, p, &revs->commits, &cache) < 0)
                                return rewrite_one_error;
-               if (p->parents && p->parents->next)
-                       return rewrite_one_ok;
                if (p->object.flags & UNINTERESTING)
                        return rewrite_one_ok;
                if (!(p->object.flags & TREESAME))
                        return rewrite_one_ok;
                if (!p->parents)
                        return rewrite_one_noparents;
-               *pp = p->parents->item;
+               if ((p = one_relevant_parent(revs, p->parents)) == NULL)
+                       return rewrite_one_ok;
+               *pp = p;
        }
 }
 
-static int rewrite_parents(struct rev_info *revs, struct commit *commit)
+int rewrite_parents(struct rev_info *revs, struct commit *commit,
+       rewrite_parent_fn_t rewrite_parent)
 {
        struct commit_list **pp = &commit->parents;
        while (*pp) {
                struct commit_list *parent = *pp;
-               switch (rewrite_one(revs, &parent->item)) {
+               switch (rewrite_parent(revs, &parent->item)) {
                case rewrite_one_ok:
                        break;
                case rewrite_one_noparents:
@@ -2218,7 +2654,7 @@ static int rewrite_parents(struct rev_info *revs, struct commit *commit)
                }
                pp = &parent->next;
        }
-       remove_duplicate_parents(commit);
+       remove_duplicate_parents(revs, commit);
        return 0;
 }
 
@@ -2342,10 +2778,7 @@ enum commit_action get_commit_action(struct rev_info *revs, struct commit *commi
        if (revs->min_age != -1 && (commit->date > revs->min_age))
                return commit_ignore;
        if (revs->min_parents || (revs->max_parents >= 0)) {
-               int n = 0;
-               struct commit_list *p;
-               for (p = commit->parents; p; p = p->next)
-                       n++;
+               int n = commit_list_count(commit->parents);
                if ((n < revs->min_parents) ||
                    ((revs->max_parents >= 0) && (n > revs->max_parents)))
                        return commit_ignore;
@@ -2355,12 +2788,23 @@ enum commit_action get_commit_action(struct rev_info *revs, struct commit *commi
        if (revs->prune && revs->dense) {
                /* Commit without changes? */
                if (commit->object.flags & TREESAME) {
+                       int n;
+                       struct commit_list *p;
                        /* drop merges unless we want parenthood */
                        if (!want_ancestry(revs))
                                return commit_ignore;
-                       /* non-merge - always ignore it */
-                       if (!commit->parents || !commit->parents->next)
-                               return commit_ignore;
+                       /*
+                        * If we want ancestry, then need to keep any merges
+                        * between relevant commits to tie together topology.
+                        * For consistency with TREESAME and simplification
+                        * use "relevant" here rather than just INTERESTING,
+                        * to treat bottom commit(s) as part of the topology.
+                        */
+                       for (n = 0, p = commit->parents; p; p = p->next)
+                               if (relevant_commit(p->item))
+                                       if (++n >= 2)
+                                               return commit_show;
+                       return commit_ignore;
                }
        }
        return commit_show;
@@ -2373,7 +2817,7 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)
        if (action == commit_show &&
            !revs->show_all &&
            revs->prune && revs->dense && want_ancestry(revs)) {
-               if (rewrite_parents(revs, commit) < 0)
+               if (rewrite_parents(revs, commit, rewrite_one) < 0)
                        return commit_error;
        }
        return action;
@@ -2423,25 +2867,23 @@ static struct commit *get_revision_1(struct rev_info *revs)
        return NULL;
 }
 
-static void gc_boundary(struct object_array *array)
+/*
+ * Return true for entries that have not yet been shown.  (This is an
+ * object_array_each_func_t.)
+ */
+static int entry_unshown(struct object_array_entry *entry, void *cb_data_unused)
 {
-       unsigned nr = array->nr;
-       unsigned alloc = array->alloc;
-       struct object_array_entry *objects = array->objects;
+       return !(entry->item->flags & SHOWN);
+}
 
-       if (alloc <= nr) {
-               unsigned i, j;
-               for (i = j = 0; i < nr; i++) {
-                       if (objects[i].item->flags & SHOWN)
-                               continue;
-                       if (i != j)
-                               objects[j] = objects[i];
-                       j++;
-               }
-               for (i = j; i < nr; i++)
-                       objects[i].item = NULL;
-               array->nr = j;
-       }
+/*
+ * If array is on the verge of a realloc, garbage-collect any entries
+ * that have already been shown to try to free up some space.
+ */
+static void gc_boundary(struct object_array *array)
+{
+       if (array->nr == array->alloc)
+               object_array_filter(array, entry_unshown, NULL);
 }
 
 static void create_boundary_commit_list(struct rev_info *revs)