Re: [PATCH 1/1] Preserve topological ordering after merges This modifies the algorithm of topopological ordering. The problem with the current algoritm is that it displays the graph below as follows

[Sergey Rudyshin <540555@gmail.com>]

Hi, Johannes,
thank you for your comment
Indeed i forgot to put an emty line. Will fix it.

On Tue, Jan 7, 2020 at 3:08 PM Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
>
> Hi Sergey,
>
> please note that the commit message's first line should not be longer than
> 76 characters per line, and it should be followed by an empty line. I
> think that you forgot the empty line, looking at
> https://github.com/gitgitgadget/git/pull/514/commits/542a02020c8578d0e004cb9c929bced8719b902a
>
> Ciao,
> Johannes
>
> On Tue, 7 Jan 2020, Sergey Rudyshin via GitGitGadget wrote:
>
> > From: Sergey Rudyshin <540555@gmail.com>
> >
> > * E
> > |\
> > | * D
> > | |\
> > | |/
> > |/|
> > * | C
> > | * B
> > |/
> > * A
> >
> > commit B is placed between A and C, which is wrong
> > because E stays that D and B comes after C
> >
> > the only correct solution here is
> >
> > * E
> > |\
> > | * D
> > | |\
> > | |/
> > |/|
> > | * B
> > * | C
> > |/
> > * A
> >
> > while it seems that it contradicts to
> > D stating that C should be between D and B
> > The new algorithm solves this issue
> >
> > Here is an example:
> > * walk to to the root via "first" parents;
> > * go E -> C -> A;
> > * print A because it has no parents;
> > * step back to C;
> > * print C because it has no other parents;
> > * then step back to E;
> > * go D -> B -> A;
> > * do not print A because A is already printed;
> > * step back to B;
> > * print B;
> > * so on.
> >
> > This change makes option "--topo-order" obsolete, because
> > there is only one way to order parents of a single commit.
> > "--date-order" and "--author-date-order" are preserved and make sense
> > only for the case when multiple commits are given
> > to be able to sort those commits.
> >
> > Signed-off-by: Sergey Rudyshin <540555@gmail.com>
> > ---
> >  Documentation/git-rev-list.txt             |   4 +-
> >  Documentation/rev-list-options.txt         |  41 +++---
> >  commit.c                                   | 149 ++++++++++++++-------
> >  commit.h                                   |   4 +-
> >  t/t4202-log.sh                             |  15 +--
> >  t/t4215-log-skewed-merges.sh               |  44 +++---
> >  t/t6003-rev-list-topo-order.sh             |  54 ++++----
> >  t/t6012-rev-list-simplify.sh               |   8 +-
> >  t/t6016-rev-list-graph-simplify-history.sh |  41 +++---
> >  t/t6600-test-reach.sh                      |   6 +-
> >  10 files changed, 214 insertions(+), 152 deletions(-)
> >
> > diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
> > index 025c911436..ad1fda7a54 100644
> > --- a/Documentation/git-rev-list.txt
> > +++ b/Documentation/git-rev-list.txt
> > @@ -3,7 +3,7 @@ git-rev-list(1)
> >
> >  NAME
> >  ----
> > -git-rev-list - Lists commit objects in reverse chronological order
> > +git-rev-list - Lists commit objects in reverse topological order
> >
> >
> >  SYNOPSIS
> > @@ -17,7 +17,7 @@ DESCRIPTION
> >  List commits that are reachable by following the `parent` links from the
> >  given commit(s), but exclude commits that are reachable from the one(s)
> >  given with a '{caret}' in front of them.  The output is given in reverse
> > -chronological order by default.
> > +topological order by default.
> >
> >  You can think of this as a set operation.  Commits given on the command
> >  line form a set of commits that are reachable from any of them, and then
> > diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> > index bfd02ade99..7ab2f451ae 100644
> > --- a/Documentation/rev-list-options.txt
> > +++ b/Documentation/rev-list-options.txt
> > @@ -643,39 +643,42 @@ ifndef::git-shortlog[]
> >  Commit Ordering
> >  ~~~~~~~~~~~~~~~
> >
> > -By default, the commits are shown in reverse chronological order.
> > +By default, the commits are shown in reverse topological order.
> > ++
> > +Meaning that no parents are shown before all of its children and
> > +merges do not change the previous order.
> > ++
> > +E.g., if commit M0 produces topologically ordered list of
> > +commits L0 then commit M1 created by merging any commit into M0
> > +produces list L1 which starts with L0
> > ++
> > +In case if multiple commits are given via the command line
> > +the following parameters determine the order among them:
> >
> >  --date-order::
> > -     Show no parents before all of its children are shown, but
> > -     otherwise show commits in the commit timestamp order.
> > +     show commits in the commit timestamp order.
> >
> >  --author-date-order::
> > -     Show no parents before all of its children are shown, but
> > -     otherwise show commits in the author timestamp order.
> > +     show commits in the author timestamp order.
> >
> >  --topo-order::
> > -     Show no parents before all of its children are shown, and
> > -     avoid showing commits on multiple lines of history
> > -     intermixed.
> > +     show commits in the commit timestamp order.
> > +     this is deprecated and will be
> > +     removed in the future.
> >  +
> >  For example, in a commit history like this:
> >  +
> >  ----------------------------------------------------------------
> > -
> > -    ---1----2----4----7
> > -     \              \
> > -      3----5----6----8---
> > -
> > +   1----2-----------5
> > +    \    \         /
> > +     -----\---3---4---6
> > +           \     /
> > +            ----
> >  ----------------------------------------------------------------
> >  +
> >  where the numbers denote the order of commit timestamps, `git
> >  rev-list` and friends with `--date-order` show the commits in the
> > -timestamp order: 8 7 6 5 4 3 2 1.
> > -+
> > -With `--topo-order`, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5
> > -3 1); some older commits are shown before newer ones in order to
> > -avoid showing the commits from two parallel development track mixed
> > -together.
> > +following order: 1 2 3 4 5 6.
> >
> >  --reverse::
> >       Output the commits chosen to be shown (see Commit Limiting
> > diff --git a/commit.c b/commit.c
> > index 434ec030d6..01e9d07db9 100644
> > --- a/commit.c
> > +++ b/commit.c
> > @@ -738,6 +738,12 @@ int compare_commits_by_author_date(const void *a_, const void *b_,
> >       return 0;
> >  }
> >
> > +static int compare_commits_by_author_date_rev(const void *a_, const void *b_,
> > +                                void *cb_data)
> > +{
> > +     return compare_commits_by_author_date(b_, a_, cb_data);
> > +}
> > +
> >  int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)
> >  {
> >       const struct commit *a = a_, *b = b_;
> > @@ -767,36 +773,83 @@ int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)
> >       return 0;
> >  }
> >
> > +static int compare_commits_by_commit_date_rev(const void *a_, const void *b_, void *unused)
> > +{
> > +     return compare_commits_by_commit_date (b_, a_, unused);
> > +}
> > +
> > +struct maze {
> > +     struct commit *ret;
> > +     struct commit *out;
> > +};
> > +
> > +define_commit_slab(maze_slab, struct maze *);
> > +
> > +/*
> > + * returns the next commit while exploring the maze
> > + * current commit has the information:
> > + *   - what was the last commit we went for (OUT)
> > + *   - from which commit we came in (RET)
> > + * trying to find a parent next to OUT
> > + * if it does not exists returns RET
> > + * otherwise returns the found parent
> > + */
> > +static struct commit *get_next(struct commit *commit, struct maze *mz, struct indegree_slab *indegree)
> > +{
> > +     struct commit_list *parents = commit->parents;
> > +     struct commit *next = NULL;
> > +     int found = 0;
> > +
> > +     while (parents) {
> > +             struct commit *parent = parents->item;
> > +
> > +             if (*indegree_slab_at(indegree, parent)) {
> > +
> > +                     if (!mz->out || found) {
> > +                             next = parent;
> > +                             break;
> > +                     } else if  (mz->out == parent) {
> > +                             found = 1;
> > +                     }
> > +             }
> > +             parents = parents->next;
> > +     }
> > +
> > +     if (!next) next = mz->ret;
> > +
> > +     return next;
> > +}
> > +
> >  /*
> >   * Performs an in-place topological sort on the list supplied.
> >   */
> >  void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)
> >  {
> >       struct commit_list *next, *orig = *list;
> > -     struct commit_list **pptr;
> > +     struct commit_list **pptr = list;
> >       struct indegree_slab indegree;
> > -     struct prio_queue queue;
> > +     struct prio_queue queue_tips;
> >       struct commit *commit;
> >       struct author_date_slab author_date;
> > +     struct maze_slab maze;
> > +     struct maze *mz;
> >
> >       if (!orig)
> >               return;
> >       *list = NULL;
> >
> >       init_indegree_slab(&indegree);
> > -     memset(&queue, '\0', sizeof(queue));
> > +     init_maze_slab(&maze);
> > +     memset(&queue_tips, '\0', sizeof(queue_tips));
> >
> >       switch (sort_order) {
> > -     default: /* REV_SORT_IN_GRAPH_ORDER */
> > -             queue.compare = NULL;
> > -             break;
> > -     case REV_SORT_BY_COMMIT_DATE:
> > -             queue.compare = compare_commits_by_commit_date;
> > +     default:
> > +             queue_tips.compare = compare_commits_by_commit_date_rev;
> >               break;
> >       case REV_SORT_BY_AUTHOR_DATE:
> >               init_author_date_slab(&author_date);
> > -             queue.compare = compare_commits_by_author_date;
> > -             queue.cb_data = &author_date;
> > +             queue_tips.compare = compare_commits_by_author_date_rev;
> > +             queue_tips.cb_data = &author_date;
> >               break;
> >       }
> >
> > @@ -804,9 +857,10 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so
> >       for (next = orig; next; next = next->next) {
> >               struct commit *commit = next->item;
> >               *(indegree_slab_at(&indegree, commit)) = 1;
> > -             /* also record the author dates, if needed */
> > -             if (sort_order == REV_SORT_BY_AUTHOR_DATE)
> > -                     record_author_date(&author_date, commit);
> > +             mz = xmalloc(sizeof(struct maze));
> > +             mz->ret = NULL;
> > +             mz->out = NULL;
> > +             *(maze_slab_at(&maze, commit)) = mz;
> >       }
> >
> >       /* update the indegree */
> > @@ -832,51 +886,56 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so
> >       for (next = orig; next; next = next->next) {
> >               struct commit *commit = next->item;
> >
> > -             if (*(indegree_slab_at(&indegree, commit)) == 1)
> > -                     prio_queue_put(&queue, commit);
> > +             if (*(indegree_slab_at(&indegree, commit)) == 1) {
> > +                     /* also record the author dates, if needed */
> > +                     if (sort_order == REV_SORT_BY_AUTHOR_DATE)
> > +                             record_author_date(&author_date, commit);
> > +                     prio_queue_put(&queue_tips, commit);
> > +             }
> >       }
> >
> > -     /*
> > -      * This is unfortunate; the initial tips need to be shown
> > -      * in the order given from the revision traversal machinery.
> > -      */
> > -     if (sort_order == REV_SORT_IN_GRAPH_ORDER)
> > -             prio_queue_reverse(&queue);
> > -
> >       /* We no longer need the commit list */
> >       free_commit_list(orig);
> >
> >       pptr = list;
> >       *list = NULL;
> > -     while ((commit = prio_queue_get(&queue)) != NULL) {
> > -             struct commit_list *parents;
> > -
> > -             for (parents = commit->parents; parents ; parents = parents->next) {
> > -                     struct commit *parent = parents->item;
> > -                     int *pi = indegree_slab_at(&indegree, parent);
> >
> > -                     if (!*pi)
> > +     while ((commit = prio_queue_get(&queue_tips)) != NULL) {
> > +             struct commit *prev_commit = NULL;
> > +             while (commit) {
> > +                     mz = *(maze_slab_at(&maze, commit));
> > +                     if (!prev_commit) {
> > +                             /* either a new tip or
> > +                              * after entering an already visited commit
> > +                              */
> > +                     }
> > +                     else if (!mz->out) {
> > +                             /* happens only once for every commit
> > +                              * note that for tips RET is set to NULL
> > +                              */
> > +                             mz->ret = prev_commit;
> > +                     }
> > +                     else if (prev_commit != mz->out) {
> > +                             /* entered an already visited commit
> > +                              * step back
> > +                              */
> > +                             commit = prev_commit;
> > +                             prev_commit = NULL;
> >                               continue;
> > -
> > -                     /*
> > -                      * parents are only enqueued for emission
> > -                      * when all their children have been emitted thereby
> > -                      * guaranteeing topological order.
> > -                      */
> > -                     if (--(*pi) == 1)
> > -                             prio_queue_put(&queue, parent);
> > +                     }
> > +                     mz->out = get_next(commit, mz, &indegree);
> > +                     if (mz->out == mz->ret) {
> > +                             /* upon leaving a commit emit it */
> > +                             *pptr = commit_list_insert(commit, pptr);
> > +                     }
> > +                     prev_commit = commit;
> > +                     commit = mz->out;
> >               }
> > -             /*
> > -              * all children of commit have already been
> > -              * emitted. we can emit it now.
> > -              */
> > -             *(indegree_slab_at(&indegree, commit)) = 0;
> > -
> > -             pptr = &commit_list_insert(commit, pptr)->next;
> >       }
> >
> >       clear_indegree_slab(&indegree);
> > -     clear_prio_queue(&queue);
> > +     clear_maze_slab(&maze);
> > +     clear_prio_queue(&queue_tips);
> >       if (sort_order == REV_SORT_BY_AUTHOR_DATE)
> >               clear_author_date_slab(&author_date);
> >  }
> > diff --git a/commit.h b/commit.h
> > index 221cdaa34b..1fe3cc240e 100644
> > --- a/commit.h
> > +++ b/commit.h
> > @@ -209,7 +209,7 @@ struct commit *pop_commit(struct commit_list **stack);
> >  void clear_commit_marks(struct commit *commit, unsigned int mark);
> >  void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark);
> >
> > -
> > +/* TODO get rid of rev_sort_order in a favour of positional parameters */
> >  enum rev_sort_order {
> >       REV_SORT_IN_GRAPH_ORDER = 0,
> >       REV_SORT_BY_COMMIT_DATE,
> > @@ -222,8 +222,6 @@ enum rev_sort_order {
> >   *   invariant of resulting list is:
> >   *      a reachable from b => ord(b) < ord(a)
> >   *   sort_order further specifies:
> > - *   REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent
> > - *                            chain together.
> >   *   REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order.
> >   */
> >  void sort_in_topological_order(struct commit_list **, enum rev_sort_order);
> > diff --git a/t/t4202-log.sh b/t/t4202-log.sh
> > index 2c9489484a..46f04b36a3 100755
> > --- a/t/t4202-log.sh
> > +++ b/t/t4202-log.sh
> > @@ -635,17 +635,16 @@ test_expect_success 'set up more tangled history' '
> >  cat > expect <<\EOF
> >  *   Merge tag 'reach'
> >  |\
> > -| \
> > +| * reach
> > +| |
> >  |  \
> >  *-. \   Merge tags 'octopus-a' and 'octopus-b'
> >  |\ \ \
> > -* | | | seventh
> >  | | * | octopus-b
> > -| |/ /
> > -|/| |
> > -| * | octopus-a
> > -|/ /
> > -| * reach
> > +| | |/
> > +| * / octopus-a
> > +| |/
> > +* / seventh
> >  |/
> >  *   Merge branch 'tangle'
> >  |\
> > @@ -673,7 +672,7 @@ cat > expect <<\EOF
> >  * initial
> >  EOF
> >
> > -test_expect_success 'log --graph with merge' '
> > +test_expect_success 'log --graph with merge tag reach' '
> >       git log --graph --date-order --pretty=tformat:%s |
> >               sed "s/ *\$//" >actual &&
> >       test_cmp expect actual
> > diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
> > index 18709a723e..91630c0cae 100755
> > --- a/t/t4215-log-skewed-merges.sh
> > +++ b/t/t4215-log-skewed-merges.sh
> > @@ -5,7 +5,7 @@ test_description='git log --graph of skewed merges'
> >  . ./test-lib.sh
> >
> >  check_graph () {
> > -     cat >expect &&
> > +     sed "s/ *$//" >expect &&
> >       git log --graph --pretty=tformat:%s "$@" >actual.raw &&
> >       sed "s/ *$//" actual.raw >actual &&
> >       test_cmp expect actual
> > @@ -185,20 +185,21 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed
> >
> >       check_graph --date-order <<-\EOF
> >       *   4_H
> > -     |\
> > +     |\
> >       | *   4_G
> > -     | |\
> > +     | |\
> > +     | | * 4_C
> >       | * | 4_F
> > -     |/| |
> > +     |/| |
> >       | * |   4_E
> > -     | |\ \
> > -     | | * | 4_D
> > -     | |/ /
> > -     |/| |
> > -     | | * 4_C
> > -     | |/
> > +     | |\ \
> > +     | | |/
> > +     | |/|
> > +     | | * 4_D
> > +     | |/
> > +     |/|
> >       | * 4_B
> > -     |/
> > +     |/
> >       * 4_A
> >       EOF
> >  '
> > @@ -221,21 +222,20 @@ test_expect_success 'log --graph with octopus merge with column joining its penu
> >
> >       check_graph <<-\EOF
> >       *   5_H
> > -     |\
> > +     |\
> >       | *-.   5_G
> > -     | |\ \
> > +     | |\ \
> >       | | | * 5_F
> >       | | * |   5_E
> > -     | |/|\ \
> > -     | |_|/ /
> > -     |/| | /
> > -     | | |/
> > -     * | | 5_D
> > +     | |/|\ \
> > +     | |_|/ /
> > +     |/| | /
> > +     | | |/
> >       | | * 5_C
> > -     | |/
> > -     |/|
> > -     | * 5_B
> > -     |/
> > +     | * | 5_B
> > +     | |/
> > +     * / 5_D
> > +     |/
> >       * 5_A
> >       EOF
> >  '
> > diff --git a/t/t6003-rev-list-topo-order.sh b/t/t6003-rev-list-topo-order.sh
> > index 24d1836f41..19cb79bc29 100755
> > --- a/t/t6003-rev-list-topo-order.sh
> > +++ b/t/t6003-rev-list-topo-order.sh
> > @@ -87,12 +87,12 @@ c3
> >  c2
> >  c1
> >  b4
> > -a3
> > -a2
> > -a1
> >  b3
> >  b2
> >  b1
> > +a3
> > +a2
> > +a1
> >  a0
> >  l2
> >  l1
> > @@ -105,15 +105,15 @@ l5
> >  l4
> >  l3
> >  a4
> > -b4
> > -a3
> > -a2
> >  c3
> >  c2
> > +c1
> > +b4
> >  b3
> >  b2
> > -c1
> >  b1
> > +a3
> > +a2
> >  a1
> >  a0
> >  l2
> > @@ -127,12 +127,12 @@ l5
> >  l4
> >  l3
> >  a4
> > -b4
> >  c3
> >  c2
> > +c1
> > +b4
> >  b3
> >  b2
> > -c1
> >  b1
> >  a3
> >  a2
> > @@ -205,12 +205,12 @@ c3
> >  c2
> >  c1
> >  b4
> > -a3
> > -a2
> > -a1
> >  b3
> >  b2
> >  b1
> > +a3
> > +a2
> > +a1
> >  a0
> >  l2
> >  EOF
> > @@ -224,12 +224,12 @@ c3
> >  c2
> >  c1
> >  b4
> > -a3
> > -a2
> > -a1
> >  b3
> >  b2
> >  b1
> > +a3
> > +a2
> > +a1
> >  a0
> >  l2
> >  EOF
> > @@ -237,10 +237,10 @@ EOF
> >  test_output_expect_success 'prune near topo' 'git rev-list --topo-order a4 ^c3' <<EOF
> >  a4
> >  b4
> > +b3
> >  a3
> >  a2
> >  a1
> > -b3
> >  EOF
> >
> >  test_output_expect_success "head has no parent" 'git rev-list --topo-order  root' <<EOF
> > @@ -297,8 +297,8 @@ c3
> >  c2
> >  c1
> >  b4
> > -a3
> > -a2
> > +b3
> > +b2
> >  EOF
> >
> >  test_output_expect_success "max-count 10 - non topo order" 'git rev-list --max-count=10 l5' <<EOF
> > @@ -376,12 +376,12 @@ c3
> >  c2
> >  c1
> >  b4
> > -a3
> > -a2
> > -a1
> >  b3
> >  b2
> >  b1
> > +a3
> > +a2
> > +a1
> >  a0
> >  l2
> >  l1
> > @@ -399,12 +399,12 @@ c3
> >  c2
> >  c1
> >  b4
> > -a3
> > -a2
> > -a1
> >  b3
> >  b2
> >  b1
> > +a3
> > +a2
> > +a1
> >  a0
> >  l2
> >  l1
> > @@ -428,12 +428,12 @@ c3
> >  c2
> >  c1
> >  b4
> > -a3
> > -a2
> > -a1
> >  b3
> >  b2
> >  b1
> > +a3
> > +a2
> > +a1
> >  a0
> >  l2
> >  l1
> > diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh
> > index a10f0df02b..9f687b6b22 100755
> > --- a/t/t6012-rev-list-simplify.sh
> > +++ b/t/t6012-rev-list-simplify.sh
> > @@ -122,16 +122,16 @@ check_result () {
> >
> >  check_result 'L K J I H F E D C G B A' --full-history --topo-order
> >  check_result 'L K I H G F E D C B J A' --full-history
> > -check_result 'L K I H G F E D C B J A' --full-history --date-order
> > -check_result 'L K I H G F E D B C J A' --full-history --author-date-order
> > +check_result 'L K J I H F E D C G B A' --full-history --date-order
> > +check_result 'L K J I H F E D C G B A' --full-history --author-date-order
> >  check_result 'K I H E C B A' --full-history -- file
> >  check_result 'K I H E C B A' --full-history --topo-order -- file
> >  check_result 'K I H E C B A' --full-history --date-order -- file
> > -check_result 'K I H E B C A' --full-history --author-date-order -- file
> > +check_result 'K I H E C B A' --full-history --author-date-order -- file
> >  check_result 'I E C B A' --simplify-merges -- file
> >  check_result 'I E C B A' --simplify-merges --topo-order -- file
> >  check_result 'I E C B A' --simplify-merges --date-order -- file
> > -check_result 'I E B C A' --simplify-merges --author-date-order -- file
> > +check_result 'I E C B A' --simplify-merges --author-date-order -- file
> >  check_result 'I B A' -- file
> >  check_result 'I B A' --topo-order -- file
> >  check_result 'I B A' --date-order -- file
> > diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
> > index f5e6e92f5b..5750c6f0fd 100755
> > --- a/t/t6016-rev-list-graph-simplify-history.sh
> > +++ b/t/t6016-rev-list-graph-simplify-history.sh
> > @@ -235,27 +235,28 @@ test_expect_success '--graph ^C3' '
> >  # I don't think the ordering of the boundary commits is really
> >  # that important, but this test depends on it.  If the ordering ever changes
> >  # in the code, we'll need to update this test.
> > -test_expect_success '--graph --boundary ^C3' '
> > +test_expect_success '--graph --boundary --all ^C3' '
> >       rm -f expected &&
> > -     echo "* $A7" >> expected &&
> > -     echo "*   $A6" >> expected &&
> > -     echo "|\\  " >> expected &&
> > -     echo "| * $C4" >> expected &&
> > -     echo "* | $A5" >> expected &&
> > -     echo "| |     " >> expected &&
> > -     echo "|  \\    " >> expected &&
> > -     echo "*-. \\   $A4" >> expected &&
> > -     echo "|\\ \\ \\  " >> expected &&
> > -     echo "| * | | $B2" >> expected &&
> > -     echo "| * | | $B1" >> expected &&
> > -     echo "* | | | $A3" >> expected &&
> > -     echo "o | | | $A2" >> expected &&
> > -     echo "|/ / /  " >> expected &&
> > -     echo "o / / $A1" >> expected &&
> > -     echo " / /  " >> expected &&
> > -     echo "| o $C3" >> expected &&
> > -     echo "|/  " >> expected &&
> > -     echo "o $C2" >> expected &&
> > +     cat >> expected <<-TESTDATA &&
> > +     * $A7
> > +     *   $A6
> > +     |\
> > +     | * $C4
> > +     * | $A5
> > +     | |
> > +     |  \
> > +     *-. \   $A4
> > +     |\ \ \
> > +     | * | | $B2
> > +     | * | | $B1
> > +     * | | | $A3
> > +     | | | o $C3
> > +     | | |/
> > +     | | o $C2
> > +     o | $A2
> > +     |/
> > +     o $A1
> > +     TESTDATA
> >       git rev-list --graph --boundary --all ^C3 > actual &&
> >       test_cmp expected actual
> >       '
> > diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> > index b24d850036..a6d389c4fd 100755
> > --- a/t/t6600-test-reach.sh
> > +++ b/t/t6600-test-reach.sh
> > @@ -339,6 +339,8 @@ test_expect_success 'rev-list: ancestry-path topo-order' '
> >       run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
> >  '
> >
> > +# TODO get rid of the "sort" below
> > +# if commitGraph is enabled then sort_in_topological_order is not envoked
> >  test_expect_success 'rev-list: symmetric difference topo-order' '
> >       git rev-parse \
> >               commit-6-6 commit-5-6 commit-4-6 \
> > @@ -349,8 +351,8 @@ test_expect_success 'rev-list: symmetric difference topo-order' '
> >               commit-6-1 commit-5-1 commit-4-1 \
> >               commit-3-8 commit-2-8 commit-1-8 \
> >               commit-3-7 commit-2-7 commit-1-7 \
> > -     >expect &&
> > -     run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
> > +     | sort >expect &&
> > +     run_three_modes git rev-list --topo-order commit-3-8...commit-6-6 | sort
> >  '
> >
> >  test_expect_success 'get_reachable_subset:all' '
> > --
> > gitgitgadget
> >
> >