* [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
From: Sergey Rudyshin via GitGitGadget @ 2020-01-07 10:30 UTC (permalink / raw)
To: git; +Cc: Sergey Rudyshin, Junio C Hamano, Sergey Rudyshin
In-Reply-To: <pull.514.git.1578393057.gitgitgadget@gmail.com>
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
^ permalink raw reply related
* Re: [PATCH 1/1] add: use advise function to display hints
From: Heba Waly @ 2020-01-07 10:54 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List, Heba Waly via GitGitGadget
In-Reply-To: <xmqqzhf5cw69.fsf@gitster-ct.c.googlers.com>
On Fri, Jan 3, 2020 at 11:48 AM Junio C Hamano <gitster@pobox.com> wrote:
>
> Junio C Hamano <gitster@pobox.com> writes:
>
> A side note.
>
> Right now, the advise() API is a bit awkweard to use correctly.
> When introducing a new advice message, you would
>
> * come up with advice.frotz configuration variable
>
> * define and declare advice_frotz global variable that defaults to
> true
>
> * sprinkle calls like this:
>
> if (advice_frotz)
> advise(_("helpful message about frotz"));
>
> I am wondering about two things:
>
> (1) if we can update the API so that the above can be reduced to
> just adding calls like:
>
> advise_ng("frotz", _("helpful message about frotz"));
>
> (2) if such a simplified advise_ng API is a good idea to begin
> with.
>
That's a valid suggestion, I can investigate that in a new patch, I'd rather
keep this one as simple as calling the existing advise function.
Thanks,
Heba
^ permalink raw reply
* Re: [PATCH] run-command: avoid undefined behavior in exists_in_PATH
From: Jeff King @ 2020-01-07 11:01 UTC (permalink / raw)
To: brian m. carlson; +Cc: git, Junio C Hamano, Miriam R.
In-Reply-To: <20200107013640.1821227-1-sandals@crustytoothpaste.net>
On Tue, Jan 07, 2020 at 01:36:40AM +0000, brian m. carlson wrote:
> In this function, we free the pointer we get from locate_in_PATH and
> then check whether it's NULL. However, this is undefined behavior if
> the pointer is non-NULL, since the C standard no longer permits us to
> use a valid pointer after freeing it.
>
> The only case in which the C standard would permit this to be defined
> behavior is if r were NULL, since it states that in such a case "no
> action occurs" as a result of calling free.
>
> It's easy to suggest that this is not likely to be a problem, but we
> know that GCC does aggressively exploit the fact that undefined
> behavior can never occur to optimize and rewrite code, even when that's
> contrary to the expectations of the programmer. It is, in fact, very
> common for it to omit NULL pointer checks, just as we have here.
OK, I agree it makes sense to be on the safe side here (and the patch is
obviously the right fix).
> Noticed-by: Miriam R. <mirucam@gmail.com>
> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
I think Miriam actually posted the same patch in her initial email:
https://lore.kernel.org/git/CAN7CjDDBA0ZoCG9aaQf5rg3gxqny=EjR6v6jE1mnxvUJQSF_0Q@mail.gmail.com/
I don't know how we want to handle authorship.
-Peff
^ permalink raw reply
* Re: [PATCH] run-command: avoid undefined behavior in exists_in_PATH
From: Jeff King @ 2020-01-07 11:08 UTC (permalink / raw)
To: Jonathan Nieder; +Cc: brian m. carlson, git, Junio C Hamano, Miriam R.
In-Reply-To: <20200107020425.GG92456@google.com>
On Mon, Jan 06, 2020 at 06:04:25PM -0800, Jonathan Nieder wrote:
> -- >8 --
> Subject: run-command: let caller pass in buffer to locate_in_PATH
>
> Instead of returning a buffer that the caller is responsible for
> freeing, use a strbuf output parameter to record the path to the
> searched-for program.
>
> This makes ownership a little easier to reason about, since the owning
> code declares the buffer. It's a good habit to follow because it
> allows buffer reuse when calling such a function in a loop.
>
> It also allows the caller exists_in_PATH that does not care about the
> path to the command to be slightly simplified, by allowing a NULL
> output parameter that means that locate_in_PATH should take care of
> allocating and freeing its temporary buffer.
>
> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
> ---
> run-command.c | 51 +++++++++++++++++++++++++++++----------------------
> 1 file changed, 29 insertions(+), 22 deletions(-)
I dunno. Now the rules inside locate_in_PATH() are more complicated, and
we have an unusual boolean return from the function.
I admit I don't overly care either way, as there are literally two
callers (and not likely to be more). So I'd probably just leave it
alone, but I'm not opposed to the patch if people think it's a good
idea.
-Peff
^ permalink raw reply
* Re: [PATCH 0/1] sequencer: comment out the 'squash!' line
From: Jeff King @ 2020-01-07 11:15 UTC (permalink / raw)
To: Jonathan Nieder
Cc: Mike Rappazzo, Junio C Hamano, Michael Rappazzo via GitGitGadget,
Git List
In-Reply-To: <20200107033639.GH92456@google.com>
On Mon, Jan 06, 2020 at 07:36:39PM -0800, Jonathan Nieder wrote:
> Jeff King wrote:
>
> > But I thought that was the point of "squash" versus "fixup"? One
> > includes the commit message, and the other does not.
> >
> > I do think "commit --squash" is mostly useless for that reason, and I
> > suspect we could do a better job in the documentation about pushing
> > people to "--fixup".
> >
> > But --squash _can_ be useful with other options to populate the commit
> > message (e.g., "--edit", which just pre-populates the subject with the
> > right "squash!" line but lets you otherwise write a normal commit
> > message). If that's the workflow you're using, then I'm sympathetic to
> > auto-removing just a "squash!" line, as it's automated garbage that is
> > only meant as a signal for --autosquash.
>
> It's a signal for --autosquash and it gives a visual signal to humans
> of where the squashed commit came from.
True, but I think any proposal here would continue to include that text
in the human-readable output (I was sloppy to say "auto-remove"; it is
really "auto-comment").
Or do you mean that it's useful in the final, squashed commit? I'd argue
that a normal subject line might be so, but the "squash!" line doesn't
saying anything that's not in the main subject already. It tells you
that there _was_ a squash, but isn't erasing that origin kind of the
point of a squash?
> --squash already implies --edit, supporting this kind of workflow.
Ah, that makes sense. I don't use it myself, so I did a quick test
earlier. But I jumped too quickly to assuming I needed "--edit" (the
"--squash" entry in git-commit(1) talks about being able to use "-m",
which I read too much into).
> If we could turn back time and start over, would we want something
> like the following?
>
> 1. if someone leaves the squash! message as is, include it as is in
> the commit message without commenting out
>
> 2. if someone edits the squash! commit message to include a body
> describing what is being squashed in, include the squash! line as
> part of the commented marker
>
> 3. if someone leaves the (uncommented) squash! message in after being
> presented with an editor at --autosquash time, reopen the editor
> with some text verifying they really meant to do that
>
> It's rare that concatenated commit messages make sense to be used as
> is, especially when trailers (sign-offs, Fixes, etc) are involved. I
> suspect that (3) is more important than (2) here --- we're using the
> same space in the editor for input and output, and the result is a
> kind of error-prone process of getting the output right.
>
> Since we can't turn back time, one possibility would be to make tools
> like "git show --check" notice the squash! lines. Would that be
> useful?
What if (3) issued a warning to stderr insted of re-invoking the editor?
Then "git commit --amend" could be used to fix it, with no change in
behavior.
-Peff
^ permalink raw reply
* Re: [PATCH v2 1/1] branch: advise the user to checkout a different branch before deleting
From: Eric Sunshine @ 2020-01-07 11:16 UTC (permalink / raw)
To: Heba Waly via GitGitGadget; +Cc: Git List, Heba Waly, Junio C Hamano
In-Reply-To: <19a7cc1889d6094e4f8a94c19c43ad554662e8d8.1578370226.git.gitgitgadget@gmail.com>
On Mon, Jan 6, 2020 at 11:10 PM Heba Waly via GitGitGadget
<gitgitgadget@gmail.com> wrote:
> branch: advise the user to checkout a different branch before deleting
>
> Display a hint to the user when attempting to delete a checked out
> branch.
>
> Currently the user gets an error message saying: "error: Cannot delete
> branch <branch> checked out at <path>". The hint will be displayed
> after the error message.
A couple comments...
The second paragraph doesn't say anything beyond what the patch/code
itself already says clearly (plus, there's no need to state the
obvious), so the paragraph adds no value (yet eats up reviewer time).
Therefore, it can be dropped.
To convince readers that the change made by the patch is indeed
warranted, it's always important to explain _why_ this change is being
made.
Both points can be addressed with a short and sweet commit message,
perhaps like this:
branch: advise how to delete checked-out branch
Teach newcomers how to deal with Git refusing to delete a
checked-out branch (whether in the current worktree or some
other).
By the way, did you actually run across a real-world case in which
someone was confused about how to resolve this situation? I ask
because this almost seems like too much hand-holding, and it would be
nice to avoid polluting Git with unnecessary advice.
> Signed-off-by: Heba Waly <heba.waly@gmail.com>
> ---
> diff --git a/advice.c b/advice.c
> @@ -31,6 +31,7 @@ int advice_graft_file_deprecated = 1;
> @@ -91,7 +92,8 @@ static struct {
> { "submoduleAlternateErrorStrategyDie", &advice_submodule_alternate_error_strategy_die },
> -
> + { "deleteCheckedoutBranch", &advice_delete_checkedout_branch },
> +
When you see an odd-looking diff like this in which you wouldn't
expect any diff markers on the blank line (that is, the blank line got
deleted and re-added), it's a good indication that there's unwanted
trailing whitespace on one of the lines. In this case, you (or more
likely your editor automatically) added trailing whitespace to the
blank line which doesn't belong there. Unwanted whitespace changes
like this make the patch noisier and more difficult for a reviewer to
read.
> diff --git a/advice.h b/advice.h
> @@ -31,6 +31,7 @@ extern int advice_graft_file_deprecated;
> +extern int advice_delete_checkedout_branch;
Is there precedent elsewhere for spelling this "checkedout" rather
than the more natural "checked_out"?
> diff --git a/builtin/branch.c b/builtin/branch.c
> @@ -240,6 +240,20 @@ static int delete_branches(int argc, const char **argv, int force, int kinds,
> + if (advice_delete_checkedout_branch) {
> + if (wt->is_current) {
> + advise(_("The branch you are trying to delete is already "
> + "checked out, run the following command to "
> + "checkout a different branch then try again:\n"
> + "git switch <branch>"));
This advice unnecessarily repeats what the error message just above it
already says about the branch being checked out (thus adds no value),
and then jumps directly into showing the user an opaque command to
resolve the situation without explaining _how_ or _why_ the command is
supposed to help.
Advice messages elsewhere typically indent the example command to make
it stand out from the explanatory prose (and often separated it from
the text by a blank line).
A rewrite which addresses both these issues might be something like:
Switch to a different branch before trying to delete it. For
example:
git switch <different-branch>
git branch -%c <this-branch>
(and fill in %c with either "-d" or "-D" depending upon the value of 'force')
> + }
> + else {
> + advise(_("The branch you are trying to delete is checked "
> + "out on another worktree, run the following command "
> + "to checkout a different branch then try again:\n"
> + "git -C %s switch <branch>"), wt->path);
I like the use of -C here because it makes the command self-contained,
however, I also worry because wt->path is an absolute path, thus
likely to be quite lengthy, which means that the important part of the
example command (the "switch <branch>") can get pushed quite far away,
thus is more easily overlooked by the reader. I wonder if it would
make more sense to show the 'cd' command explicitly, although doing so
ties the example to a particular shell, which may be a downside.
cd %s
git switch <different-branch>
cd -
git branch -%c <this-branch>
(It is rather verbose and ugly, though.)
> diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
> @@ -807,8 +807,10 @@ test_expect_success 'test deleting branch without config' '
> test_expect_success 'deleting currently checked out branch fails' '
> git worktree add -b my7 my7 &&
> - test_must_fail git -C my7 branch -d my7 &&
> - test_must_fail git branch -d my7 &&
> + test_must_fail git -C my7 branch -d my7 2>output1.err &&
> + test_must_fail git branch -d my7 2>output2.err &&
> + test_i18ngrep "hint: The branch you are trying to delete is already checked out" output1.err &&
> + test_i18ngrep "hint: The branch you are trying to delete is checked out on another worktree" output2.err &&
Nit: Separating the 'grep' from the command which generated the error
output makes it harder for a reader to see at a glance what is being
tested and to reason about it since it demands that the reader keep
two distinct cases in mind rather than merely focusing on one at a
time. Also, doing it this way forces you to invent distinct filenames
(by appending a number, for instance), which further leads the reader
to wonder if there is some significance (later in the test) to keeping
these outputs in separate files. So, a better organization (with more
natural filenames) would be:
test_must_fail git -C my7 branch -d my7 2>output.err &&
test_i18ngrep "hint: ..." output.err &&
test_must_fail git branch -d my7 2>output.err &&
test_i18ngrep "hint: ..." output.err &&
^ permalink raw reply
* Re: [PATCH v2] sha1-file: remove OBJECT_INFO_SKIP_CACHED
From: Jeff King @ 2020-01-07 11:22 UTC (permalink / raw)
To: Jonathan Nieder; +Cc: Jonathan Tan, git, gitster
In-Reply-To: <20200106234753.GB92456@google.com>
On Mon, Jan 06, 2020 at 03:47:53PM -0800, Jonathan Nieder wrote:
> >> + * Callers are responsible for calling write_object_file to record the
> >> + * object in persistent storage before writing any other new objects
> >> + * that reference it.
> >> + */
> >> int pretend_object_file(void *, unsigned long, enum object_type,
> >> struct object_id *oid);
> >
> > I think this is an improvement over the status quo, but it's still a
> > potential trap for code which happens to run in the same process (see my
> > other email in the thread).
> >
> > Should the message perhaps be even more scary?
>
> A pet peeve of mine is warning volume escalation: if it becomes common
> for us to say
>
> * Warning: callers are reponsible for [...]
>
> then new warnings trying to stand out might say
>
> * WARNING: callers are responsible for [...]
>
> and then after we are desensitized to that, we may switch to
>
> * WARNING WARNING WARNING, not the usual blah-blah: callers are
>
> and so on. The main way I have found to counteract that is to make
> the "dangerous curve" markers context-specific enough that people
> don't learn to ignore them. After all, sometimes a concurrency
> warning is important to me, at other times warnings about clarity may
> be what attract my interest, and so on.
I meant less about the number of capital letters, and more that we
should be saying "this interface is dangerous; don't use it". Because
it's not just "callers are responsible". It's "this can cause subtle
and hard-to-debug issues because it's writing to global state".
My preferred solution would actually be to rip it out entirely, but we'd
need some solution for git-blame, the sole caller. Possibly it could
insert the value straight into the diff_filespec. But according to the
thread that I linked earlier, I poked at that last year but it didn't
look trivial.
> I don't have a good suggestion here. Perhaps "Callers are responsible
> for" is too slow and something more terse would help?
>
> /*
> * Adds an object to the in-memory object store, without writing it
> * to disk.
> *
> * Use with caution! Unless you call write_object_file to record the
> * in-memory object to persistent storage, any other new objects that
> * reference it will point to a missing (in memory only) object,
> * resulting in a corrupt repository.
> */
Yeah, that's more what I had in mind.
> It would be even better if we have some automated way to catch this
> kind of issue. Should tests run "git fsck" after each test? Should
> write_object_file have a paranoid mode that checks integrity?
>
> I don't know an efficient way to do that. Ultimately I am comfortable
> counting on reviewers to be aware of this kind of pitfall. While
> nonlocal invariants are always hard to maintain, this pitfall is
> inherent in the semantics of the function, so I am not too worried
> that reviewers will overlook it.
Yeah, given the scope of the problem (we have a single caller, and this
mechanism is over a decade old) I'm fine with review as the enforcement
mechanism, too.
> A less error-prone interface would tie the result of
> pretend_object_file to a short-lived overlay on the_repository without
> affecting global state. We could even enforce read-only access in
> that overlay. I don't think the "struct repository" interface and
> callers are ready for that yet, though.
I agree that would be better, though it's still kind-of global (in that
the repository object is effectively a global for most processes).
-Peff
^ permalink raw reply
* Assertion in git log graphing
From: Bradley Smith @ 2020-01-07 11:24 UTC (permalink / raw)
To: git
Hi,
The following git repository (https://github.com/brads55/git-testcase)
causes an assertion when running:
$ git log --oneline --graph --all
git-log: graph.c:1228: graph_output_collapsing_line: Assertion
`graph->mapping[i - 3] == target' failed.
The assertion seems to be caused by commit
0f0f389f12029b1c3745f8ed7aacfe6b2fc7a6cc. The graph structure of the
above repository is as follows (as produced by v2.24.1):
* a0a130c Merge commit '8f076d8' into HEAD
|\
| | * f0f3be5 Merge commit '1b4b8d0' into HEAD
| | |\
| | | * 1b4b8d0 6
| | * | 2c44f1b 2
| | | | * dd068b4 Merge commit '8f076d8' into HEAD
| | | | |\
| |_|_|/ /
|/| | | /
| | |_|/
| |/| |
| * | | 8f076d8 5
| | |/
| |/|
* | | a261135 4
| |/
|/|
* | a267dd6 1
|/
* 68f4772 0
Regards,
Bradley Smith
^ permalink raw reply
* Re: [PATCH 1/1] doc: fix a typo in gitcore-tutorial.txt
From: Eric Sunshine @ 2020-01-07 11:35 UTC (permalink / raw)
To: Heba Waly via GitGitGadget; +Cc: Git List, Heba Waly, Junio C Hamano
In-Reply-To: <ee8636e0ed40888b2a132cff2dacc97754550ba1.1578391553.git.gitgitgadget@gmail.com>
On Tue, Jan 7, 2020 at 5:06 AM Heba Waly via GitGitGadget
<gitgitgadget@gmail.com> wrote:
> doc: fix a typo in gitcore-tutorial.txt
>
> Signed-off-by: Heba Waly <heba.waly@gmail.com>
> ---
> diff --git a/Documentation/gitcore-tutorial.txt b/Documentation/gitcore-tutorial.txt
> @@ -751,7 +751,7 @@ to it.
> ================================================
> If you make the decision to start your new branch at some
> other point in the history than the current `HEAD`, you can do so by
> -just telling 'git checkout' what the base of the checkout would be.
> +just telling 'git switch' what the base of the checkout would be.
Calling this change a "typo fix" confuses reviewers since it's clearly
not a mere typographical error. It looks instead as if you are
recommending git-switch over git-checkout, so a reader would expect
the commit message to justify that change rather than merely calling
it a "typo fix". However, digging deeper, one finds that this is
actually fixing an oversight from an earlier change which already
updated this file to prefer git-switch over git-checkout.
To save reviewers the time and effort of having to figure all this
out, use the commit message to explain the situation. For example, you
might say:
doc/gitcore-tutorial: fix prose to match example command
In 328c6cb853 (doc: promote "git switch", 2019-03-29), an example
was changed to use "git switch" rather than "git checkout" but an
instance of "git checkout" in the explanatory text preceding the
example was overlooked. Fix this oversight.
^ permalink raw reply
* Re: Assertion in git log graphing [regression in v2.25]
From: Jeff King @ 2020-01-07 11:48 UTC (permalink / raw)
To: Bradley Smith; +Cc: Junio C Hamano, James Coglan, git
In-Reply-To: <CAHt=fUXTHc4JPsapvHKnw5vHhp2cBOYRNfdaSDWBUnKt8fWfeA@mail.gmail.com>
On Tue, Jan 07, 2020 at 11:24:50AM +0000, Bradley Smith wrote:
> The following git repository (https://github.com/brads55/git-testcase)
> causes an assertion when running:
>
> $ git log --oneline --graph --all
>
> git-log: graph.c:1228: graph_output_collapsing_line: Assertion
> `graph->mapping[i - 3] == target' failed.
Thanks for the report, and especially for providing a reproduction case!
The problem is new in the v2.25 release candidates, so we should try to
deal with it before the release.
> The assertion seems to be caused by commit
> 0f0f389f12029b1c3745f8ed7aacfe6b2fc7a6cc. The graph structure of the
> above repository is as follows (as produced by v2.24.1):
Yeah, I can confirm that this introduces the problem. I admit to not
following the recent graph changes too closely, so I'll add James to the
cc for attention.
The assertion itself is quite old, so I wondered if it was even still
relevant. Removing it does produce a reasonable-looking graph:
* a0a130c Merge commit '8f076d8' into HEAD
|\
| | * f0f3be5 Merge commit '1b4b8d0' into HEAD
| | |\
| | | * 1b4b8d0 6
| | * | 2c44f1b 2
| | | | * dd068b4 Merge commit '8f076d8' into HEAD
| |_|_|/|
|/| | |/
| | |/|
| |/| |
| * | | 8f076d8 5
| | |/
| |/|
* | | a261135 4
| |/
|/|
* | a267dd6 1
|/
* 68f4772 0
but the colors aren't quite right. In particular, in this segment:
| | | | * dd068b4 Merge commit '8f076d8' into HEAD
| |_|_|/|
|/| | |/
the first-parent line coming from dd068b4 is red in the slashes, but
uncolored in the underscores.
So much for naive fix. :)
-Peff
^ permalink raw reply
* 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
From: Johannes Schindelin @ 2020-01-07 12:08 UTC (permalink / raw)
To: Sergey Rudyshin via GitGitGadget
Cc: git, Sergey Rudyshin, Junio C Hamano, Sergey Rudyshin
In-Reply-To: <542a02020c8578d0e004cb9c929bced8719b902a.1578393057.git.gitgitgadget@gmail.com>
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
>
>
^ permalink raw reply
* Re: [PATCH 0/1] Preserve topological ordering after merges
From: Johannes Schindelin @ 2020-01-07 12:11 UTC (permalink / raw)
To: Sergey Rudyshin via GitGitGadget; +Cc: git, Sergey Rudyshin, Junio C Hamano
In-Reply-To: <pull.514.git.1578393057.gitgitgadget@gmail.com>
Hi Sergey,
On Tue, 7 Jan 2020, Sergey Rudyshin via GitGitGadget wrote:
> This modifies the algoritm of topopological ordering. The problem with the
> current algoritm is that it displays the graph below as following
>
> * 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 staiting that C shoud 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 becase A is
> already printed step back to B print B so on
>
> This change makes option "--topo-order" obsolete, because for a single
> commit there is only one way to order parents. "--date-order" and
> "--author-date-order" are preserved and make sence only for the case when
> multiple commits are given to be able to sort those commits.
I have to admit that I am not a fan of this change, as I find that there
are legitimate use cases where I want to order the commits by commit
topology, and other use cases where I want to order them by date.
Maybe other reviewers agree with your reasoning, though, in that case you
still will need to address the test failures in t4202, t4215 and t6012:
https://dev.azure.com/gitgitgadget/git/_build/results?buildId=25867&view=ms.vss-test-web.build-test-results-tab
Ciao,
Johannes
>
> Sergey Rudyshin (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
>
> 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(-)
>
>
> base-commit: 8679ef24ed64018bb62170c43ce73e0261c0600a
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-514%2FSergeyRudyshin%2Ftopo_order_fix-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-514/SergeyRudyshin/topo_order_fix-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/514
> --
> gitgitgadget
>
^ permalink raw reply
* 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
From: Derrick Stolee @ 2020-01-07 12:14 UTC (permalink / raw)
To: Sergey Rudyshin via GitGitGadget, git; +Cc: Sergey Rudyshin, Junio C Hamano
In-Reply-To: <542a02020c8578d0e004cb9c929bced8719b902a.1578393057.git.gitgitgadget@gmail.com>
On 1/7/2020 5:30 AM, 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
This ordering concern makes sense _somewhat_, because D is the
second parent of D and that wants to say "Show everything in C..D
before showing C". The issues is that since C is the second parent
of D, the topo-ordering says "Show everything in B..C before showing
things reachable from B". It is unfortunate that these constraints
collide.
Perhaps your description could do a better job clarifying this
issue and how your algorithm change fixes the problem.
However, I'm not sure we even want to make the change, as this
is still a valid topological order (parents appear after children).
When we have an ambiguous pair (like B and C) the order can differ.
The --topo-order option tries to group commits by when they were
introduced, and that's the reason for presenting the commits reachable
from the later parents before presenting the commits from earlier
parents.
The only documentation we have is from [1]:
"Show no parents before all of its children are shown, and avoid
showing commits on multiple lines of history intermixed."
The first part of the sentence is still true, and the second part
is ambiguous of how to do that.
[1] https://git-scm.com/docs/git-log#Documentation/git-log.txt---topo-order
> 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.
This part of the change needs to be removed. The default sort does
not preserve topological orderings (like --date-order does), and
so is much faster to output, especially without a commit-graph file.
> void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)
Since you are only editing this code, and not the incremental topo-order code, your
test changes will likely break when run with GIT_TEST_COMMIT_GRAPH=1. When the commit-graph
exists and generation numbers are calculated, we use a different algorithm for topo-order.
I've been meaning to clean up this "duplicated" logic by deleting this method in favor of
the incremental algorithm in all cases. It needs some perf testing to make sure that
refactor doesn't have too large of a perf hit in the case of no commit-graph.
> /* 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);
> + }
Your code change looks rather large for what I expected to be a much simpler change.
Likely the only thing we need is to avoid adding to the priority queue if we already
have the commit in the queue (maybe using a hashset storing the commits that we've
added to the queue). I believe the reason C appears before B in your example is that
it was added to the queue a second time, and the queue behaves like a stack in the
topo-order case.
Thanks,
-Stolee
^ permalink raw reply
* Re: [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS
From: Jakub Narebski @ 2020-01-07 12:19 UTC (permalink / raw)
To: Garima Singh via GitGitGadget
Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
Junio C Hamano, Garima Singh
In-Reply-To: <a15f87fdcbea1a37a20a05135832b42f36f682f1.1576879520.git.gitgitgadget@gmail.com>
"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:
> From: Garima Singh <garima.singh@microsoft.com>
>
> This is a minor cleanup to make it easier to change the
> number of chunks being written to the commit-graph in the future.
Very minor nit: in the whole commit message it is not stated explicitly
what MAX_NUM_CHUNKS is for, though it is very easy to guess (from the
name itself).
>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> ---
> commit-graph.c | 5 +++--
> 1 file changed, 3 insertions(+), 2 deletions(-)
>
> diff --git a/commit-graph.c b/commit-graph.c
> index 61e60ff98a..8c4941eeaa 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -24,6 +24,7 @@
> #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
> #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
> #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
> +#define MAX_NUM_CHUNKS 5
Minor nit: MAX_NUM_CHUNKS or MAX_CHUNKS?
>
> #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
>
> @@ -1381,8 +1382,8 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
> int fd;
> struct hashfile *f;
> struct lock_file lk = LOCK_INIT;
> - uint32_t chunk_ids[6];
> - uint64_t chunk_offsets[6];
> + uint32_t chunk_ids[MAX_NUM_CHUNKS + 1];
> + uint64_t chunk_offsets[MAX_NUM_CHUNKS + 1];
Looks good. I guess we won't ever have more chunks than 5:
OIDF, OIDL, CDAT, EDGE, BASE (and they cannot repeat, and last two are
optional).
> const unsigned hashsz = the_hash_algo->rawsz;
> struct strbuf progress_title = STRBUF_INIT;
> int num_chunks = 3;
Good.
Looks good to me.
--
Jakub Narębski
^ permalink raw reply
* Re: [PATCH 0/1] Update imap-send.c, fix incompatibilities with OpenSSL 1.1.x
From: Johannes Schindelin @ 2020-01-07 12:19 UTC (permalink / raw)
To: Liam Huang via GitGitGadget, Liam Huang; +Cc: git, Junio C Hamano
In-Reply-To: <pull.516.git.1578391376.gitgitgadget@gmail.com>
Hi Liam,
On Tue, 7 Jan 2020, Liam Huang via GitGitGadget wrote:
> Some APIs have been changed since OpenSSL 1.1.0, so fix incompatibilities
> with OpenSSL 1.1.x.
In your PR, the "Checks" tab shows that this breaks the build for all
non-32-bit Linux builds and for Windows. Here is an excerpt of the failed
`linux-clang` build:
-- snip --
[...]
imap-send.c:253:43: error: incompatible pointer types passing 'struct stack_st_GENERAL_NAME *' to parameter of type 'const OPENSSL_STACK *' (aka 'const struct stack_st *') [-Werror,-Wincompatible-pointer-types]
int num_subj_alt_names = OPENSSL_sk_num(subj_alt_names);
^~~~~~~~~~~~~~
/usr/include/openssl/stack.h:23:41: note: passing argument to parameter here
int OPENSSL_sk_num(const OPENSSL_STACK *);
^
imap-send.c:260:51: error: incompatible pointer types passing 'struct stack_st_GENERAL_NAME *' to parameter of type 'const OPENSSL_STACK *' (aka 'const struct stack_st *') [-Werror,-Wincompatible-pointer-types]
GENERAL_NAME *subj_alt_name = OPENSSL_sk_value(subj_alt_names, i);
^~~~~~~~~~~~~~
/usr/include/openssl/stack.h:24:45: note: passing argument to parameter here
void *OPENSSL_sk_value(const OPENSSL_STACK *, int);
^
imap-send.c:270:23: error: incompatible pointer types passing 'struct stack_st_GENERAL_NAME *' to parameter of type 'OPENSSL_STACK *' (aka 'struct stack_st *') [-Werror,-Wincompatible-pointer-types]
OPENSSL_sk_pop_free(subj_alt_names, GENERAL_NAME_free);
^~~~~~~~~~~~~~
/usr/include/openssl/stack.h:33:41: note: passing argument to parameter 'st' here
void OPENSSL_sk_pop_free(OPENSSL_STACK *st, void (*func) (void *));
^
imap-send.c:270:39: error: incompatible pointer types passing 'void (GENERAL_NAME *)' (aka 'void (struct GENERAL_NAME_st *)') to parameter of type 'void (*)(void *)' [-Werror,-Wincompatible-pointer-types]
OPENSSL_sk_pop_free(subj_alt_names, GENERAL_NAME_free);
^~~~~~~~~~~~~~~~~
/usr/include/openssl/stack.h:33:52: note: passing argument to parameter 'func' here
void OPENSSL_sk_pop_free(OPENSSL_STACK *st, void (*func) (void *));
^
4 errors generated.
Makefile:2382: recipe for target 'imap-send.o' failed
-- snap --
For the full build logs, please have a look at
https://dev.azure.com/gitgitgadget/git/_build/results?buildId=25858&view=logs&j=8f20da19-31b7-5cef-4813-95b8788bd086&t=56027f08-fde3-50ad-0c9a-5ec7df432ed0
Could you fix those compile errors, please?
While at it, please also fix your author email: it should match your
_real_ email address, i.e. "liamhuang0205@gmail.com", not
"Liam0205@users.noreply.github.com".
Thank you,
Johannes
^ permalink raw reply
* Re: Assertion in git log graphing [regression in v2.25]
From: Derrick Stolee @ 2020-01-07 12:22 UTC (permalink / raw)
To: Jeff King, Bradley Smith; +Cc: Junio C Hamano, James Coglan, git
In-Reply-To: <20200107114812.GE1073219@coredump.intra.peff.net>
On 1/7/2020 6:48 AM, Jeff King wrote:
> On Tue, Jan 07, 2020 at 11:24:50AM +0000, Bradley Smith wrote:
>
>> The following git repository (https://github.com/brads55/git-testcase)
>> causes an assertion when running:
>>
>> $ git log --oneline --graph --all
>>
>> git-log: graph.c:1228: graph_output_collapsing_line: Assertion
>> `graph->mapping[i - 3] == target' failed.
>
> Thanks for the report, and especially for providing a reproduction case!
>
> The problem is new in the v2.25 release candidates, so we should try to
> deal with it before the release.
>
>> The assertion seems to be caused by commit
>> 0f0f389f12029b1c3745f8ed7aacfe6b2fc7a6cc. The graph structure of the
>> above repository is as follows (as produced by v2.24.1):
>
> Yeah, I can confirm that this introduces the problem. I admit to not
> following the recent graph changes too closely, so I'll add James to the
> cc for attention.
I'm also going to take a look this morning, starting by creating a test.
I reviewed what I could of James' patch series, but I was also unfamiliar
with graph.c and relied on his very substantial test cases to verify the
correctness. Looks like a corner case got missed.
Thanks,
-Stolee
^ permalink raw reply
* Re: Assertion in git log graphing [regression in v2.25]
From: Derrick Stolee @ 2020-01-07 12:42 UTC (permalink / raw)
To: Jeff King, Bradley Smith; +Cc: Junio C Hamano, James Coglan, git
In-Reply-To: <d694a5b5-9c88-0a34-b9fd-050e5e02c312@gmail.com>
On 1/7/2020 7:22 AM, Derrick Stolee wrote:
> I'm also going to take a look this morning, starting by creating a test.
Here is a a patch that reproduces the test failure. It hits the
assert, so it definitely fails.
NOTE: The test may not actually pass after this bug is fixed, as
the output expectation may not match exactly. Thus, the test will
likely still fail after fixing the bug, but for a different reason.
I could use the output from v2.24.1, but the point of these changes
in graph.c was to have a compressed output in exactly these cases
of multiple edges moving to the left. In particular, the edges out
of 6_F will likely need updating.
If I manage to do the "right" fix, then I'll update this test
accordingly.
-Stolee
-->8--
From: Derrick Stolee <dstolee@microsoft.com>
Date: Tue, 7 Jan 2020 07:35:56 -0500
Subject: [PATCH] graph: add failing test that hits assert()
A failure was reported in "git log --graph --all" with the new
graph-rendering logic. Create a test case that matches the
topology of that example and uses an explicit ref ordering instead
of the "--all" option. The test fails with the following error:
graph.c:1228: graph_output_collapsing_line: Assertion
`graph->mapping[i - 3] == target' failed.
Reported-by: Bradley Smith <brad@brad-smith.co.uk>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
t/t4215-log-skewed-merges.sh | 43 ++++++++++++++++++++++++++++++++++++
1 file changed, 43 insertions(+)
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 18709a723e..bab8a7ed56 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -240,4 +240,47 @@ test_expect_success 'log --graph with octopus merge with column joining its penu
EOF
'
+test_expect_failure 'log --graph with multiple tips' '
+ git checkout --orphan 6_1 &&
+ test_commit 6_A &&
+ git branch 6_2 &&
+ git branch 6_4 &&
+ test_commit 6_B &&
+ git branch 6_3 &&
+ test_commit 6_C &&
+ git checkout 6_2 && test_commit 6_D &&
+ git checkout 6_3 && test_commit 6_E &&
+ git checkout -b 6_5 6_1 &&
+ git merge --no-ff 6_2 -m 6_F &&
+ git checkout 6_4 && test_commit 6_G &&
+ git checkout 6_3 &&
+ git merge --no-ff 6_4 -m 6_H &&
+ git checkout 6_1 &&
+ git merge --no-ff 6_2 -m 6_I &&
+
+ check_graph 6_1 6_3 6_5 <<-\EOF
+ * 6_I
+ |\
+ | | * 6_H
+ | | |\
+ | | | * 6_G
+ | | * | 6_E
+ | | | | * 6_F
+ | | | | |\
+ | |_|_|/ /
+ |/| | | /
+ | | |_|/
+ | |/| |
+ | * | | 6_D
+ | | |/
+ | |/|
+ * | | 6_C
+ | |/
+ |/|
+ * | 6_B
+ |/
+ * 6_A
+ EOF
+'
+
test_done
--
2.24.1.vfs.1.1.12.gccc87aa318
^ permalink raw reply related
* Re: Assertion in git log graphing [regression in v2.25]
From: Eric Sunshine @ 2020-01-07 12:50 UTC (permalink / raw)
To: Derrick Stolee
Cc: Jeff King, Bradley Smith, Junio C Hamano, James Coglan, Git List
In-Reply-To: <fe1cd838-d390-96ab-d3b4-72df5aa61947@gmail.com>
On Tue, Jan 7, 2020 at 7:42 AM Derrick Stolee <stolee@gmail.com> wrote:
> Here is a a patch that reproduces the test failure. It hits the
> assert, so it definitely fails.
What happens if someone builds the project with NDEBUG? Then the test
won't fail as expected. Perhaps this patch ought to also change those
asserts() to `if (...) BUG(...)` to ensure consistent behavior.
^ permalink raw reply
* Broken branch after git commit - tracked files in staging area can't be removed with restore --staged, or commit or stash
From: Torsten Krah @ 2020-01-07 12:55 UTC (permalink / raw)
To: git
Hi,
as written here https://git-scm.com/community I should sent reports to
this list - if I am mistaken please tell me where to direct this
question / problem I've encountered.
I've got a problem with a git branch and as this is the second time now
(I never hit that problem before I've started using the "new" git
restore --staged command - but since I am using it its the second time
now - maybe by accident, maybe related - I don't know).
Maybe someone can help me with this matter.
I am using 2.24.1 git and my starting point was a local branch and I
wanted to removed some files from the last commit I made.
So I did this:
1. git reset --soft HEAD~1
Now I had all my files from the last commit in the staging area and to
remove some of them I did:
2. git restore --staged $my-files
This worked too - now those files were moved to the working tree in git
status and were untracked and the rest looked still fine in the staging
area.
3. git commit
Now I made my commit - had a look on that with git show and it looks
fine.
But now I've hit the problem - looking with "git status" I was left now
with 6 files in the staging area all marked as deleted - still they are
in the working tree.
But I did never deleted them and the most annoying part now - I can't
fix that.
I tried:
1. git restore --staged
Does not change anything, still deleted in the staging area.
2. git stash
Does create a stash entry (did not look at the content though yet) but
staging area still unchanged.
3. git commit
Does create a commit but the whole commit is empty - nothing from the
tracked staging area is there and "git status" is unchanged - still 6
tracked deleted files.
I don't know what went wrong and I am unable to fix it - help
appreciated.
I can't share the whole git repository but I can try whatever git
command or other tool output may help here to shed some light on this -
as written I don't have a clear reproducer, I just have my branch with
a borked staging area.
thx and kind regards
Torsten
PS: Of cause I can delete the whole repo and clone it again or remove
the branch and start from a fresh new one ;) but I want to analyse
this.
^ permalink raw reply
* Re: Assertion in git log graphing [regression in v2.25]
From: Derrick Stolee @ 2020-01-07 12:56 UTC (permalink / raw)
To: Eric Sunshine
Cc: Jeff King, Bradley Smith, Junio C Hamano, James Coglan, Git List
In-Reply-To: <CAPig+cRH-yeHmeikf=cbTTMDom+7SLtT2dmya=WP7fsy8tTY3g@mail.gmail.com>
On 1/7/2020 7:50 AM, Eric Sunshine wrote:
> On Tue, Jan 7, 2020 at 7:42 AM Derrick Stolee <stolee@gmail.com> wrote:
>> Here is a a patch that reproduces the test failure. It hits the
>> assert, so it definitely fails.
>
> What happens if someone builds the project with NDEBUG? Then the test
> won't fail as expected. Perhaps this patch ought to also change those
> asserts() to `if (...) BUG(...)` to ensure consistent behavior.
A final version of the patch would probably fix the bug and not use
test_expect_failure. The other option would be to replace every
assert() with a macro that did the "if (...) BUG(...);" conversion,
but maybe that's not necessary in general.
-Stolee
^ permalink raw reply
* Re: Assertion in git log graphing [regression in v2.25]
From: Eric Sunshine @ 2020-01-07 13:14 UTC (permalink / raw)
To: Derrick Stolee
Cc: Jeff King, Bradley Smith, Junio C Hamano, James Coglan, Git List
In-Reply-To: <3fd8d52c-622e-29a6-442c-66797a3ae1f9@gmail.com>
On Tue, Jan 7, 2020 at 7:56 AM Derrick Stolee <stolee@gmail.com> wrote:
> On 1/7/2020 7:50 AM, Eric Sunshine wrote:
> > On Tue, Jan 7, 2020 at 7:42 AM Derrick Stolee <stolee@gmail.com> wrote:
> >> Here is a a patch that reproduces the test failure. It hits the
> >> assert, so it definitely fails.
> >
> > What happens if someone builds the project with NDEBUG? Then the test
> > won't fail as expected. Perhaps this patch ought to also change those
> > asserts() to `if (...) BUG(...)` to ensure consistent behavior.
>
> A final version of the patch would probably fix the bug and not use
> test_expect_failure.
Indeed, I understood that when I made the suggestion, but you still
want to be able to catch the problem if the code ever regresses and
reintroduces the bug. And, to do so, you'd want to ensure consistent
behavior which you get with BUG() but not with assert().
^ permalink raw reply
* Re: Assertion in git log graphing [regression in v2.25]
From: Derrick Stolee @ 2020-01-07 13:25 UTC (permalink / raw)
To: Jeff King, Bradley Smith; +Cc: Junio C Hamano, James Coglan, git
In-Reply-To: <20200107114812.GE1073219@coredump.intra.peff.net>
On 1/7/2020 6:48 AM, Jeff King wrote:
> The assertion itself is quite old, so I wondered if it was even still
> relevant. Removing it does produce a reasonable-looking graph:
As I'm digging into this case, and finding when the assertion is hit,
I see that the issue is in the line further below your coloring issue:
> | | | | * dd068b4 Merge commit '8f076d8' into HEAD
> | |_|_|/|
> |/| | |/
> | | |/|
> | |/| |
> | * | | 8f076d8 5
What is output is actually this, above. But the logic that includes the
assert is checking where the underscores end, and the shown underscores
actually pass the check. The issue is that it seems like it really wants
to show this:
> | | | | * dd068b4 Merge commit '8f076d8' into HEAD
> | |_|_|/|
> |/| |_|/
> | |/| |
> | * | | 8f076d8 5
Note that I dropped a line and compressed a slash into an underscore. It's
on that line that this condition is being hit.
Now, is this really the intended behavior? Maybe. Looking at the previous
tests in 54125-log-skewed-merges.sh, I don't see any where we have two
skewed merges in the same merge.
Thanks,
-Stolee
^ permalink raw reply
* Re: Broken branch after git commit - tracked files in staging area can't be removed with restore --staged, or commit or stash
From: Torsten Krah @ 2020-01-07 13:43 UTC (permalink / raw)
To: git
In-Reply-To: <07c84224bb0b093ab3770be9b5ab2ec23ce2d31a.camel@gmail.com>
Am Dienstag, den 07.01.2020, 13:55 +0100 schrieb Torsten Krah:
> 3. git commit
>
> Now I made my commit - had a look on that with git show and it looks
> fine.
I had a second look on this step and the result it wrong.
Although restore --staged moved my unwanted files away from the staging
area and "git status" told me that they are not "in" the commit the
commit itself did still include them.
So they are listed as unversioned now but are in the commit although
git status told me otherwise - weird.
kind regards
Torsten
^ permalink raw reply
* Re: Assertion in git log graphing [regression in v2.25]
From: Jeff King @ 2020-01-07 14:04 UTC (permalink / raw)
To: Derrick Stolee; +Cc: Bradley Smith, Junio C Hamano, James Coglan, git
In-Reply-To: <5f956281-e861-f274-be43-95d99a625abb@gmail.com>
On Tue, Jan 07, 2020 at 08:25:59AM -0500, Derrick Stolee wrote:
> On 1/7/2020 6:48 AM, Jeff King wrote:
> > The assertion itself is quite old, so I wondered if it was even still
> > relevant. Removing it does produce a reasonable-looking graph:
>
> As I'm digging into this case, and finding when the assertion is hit,
> I see that the issue is in the line further below your coloring issue:
Oh, you're right. I totally missed that.
So perhaps we have two bugs, or perhaps they have the same root cause.
> > | | | | * dd068b4 Merge commit '8f076d8' into HEAD
> > | |_|_|/|
> > |/| | |/
> > | | |/|
> > | |/| |
> > | * | | 8f076d8 5
>
> What is output is actually this, above. But the logic that includes the
> assert is checking where the underscores end, and the shown underscores
> actually pass the check. The issue is that it seems like it really wants
> to show this:
>
> > | | | | * dd068b4 Merge commit '8f076d8' into HEAD
> > | |_|_|/|
> > |/| |_|/
> > | |/| |
> > | * | | 8f076d8 5
>
> Note that I dropped a line and compressed a slash into an underscore. It's
> on that line that this condition is being hit.
Hrm. I could see either being acceptable, but I do think the second one
is a bit easier to read. I'm not sure which was intended for this case.
-Peff
^ permalink raw reply
* Re: Assertion in git log graphing [regression in v2.25]
From: Derrick Stolee @ 2020-01-07 14:22 UTC (permalink / raw)
To: Jeff King; +Cc: Bradley Smith, Junio C Hamano, James Coglan, git
In-Reply-To: <20200107140417.GA12242@coredump.intra.peff.net>
On 1/7/2020 9:04 AM, Jeff King wrote:
> On Tue, Jan 07, 2020 at 08:25:59AM -0500, Derrick Stolee wrote:
>
>> On 1/7/2020 6:48 AM, Jeff King wrote:
>>> The assertion itself is quite old, so I wondered if it was even still
>>> relevant. Removing it does produce a reasonable-looking graph:
>>
>> As I'm digging into this case, and finding when the assertion is hit,
>> I see that the issue is in the line further below your coloring issue:
>
> Oh, you're right. I totally missed that.
>
> So perhaps we have two bugs, or perhaps they have the same root cause.
>
>>> | | | | * dd068b4 Merge commit '8f076d8' into HEAD
>>> | |_|_|/|
>>> |/| | |/
>>> | | |/|
>>> | |/| |
>>> | * | | 8f076d8 5
>>
>> What is output is actually this, above. But the logic that includes the
>> assert is checking where the underscores end, and the shown underscores
>> actually pass the check. The issue is that it seems like it really wants
>> to show this:
>>
>>> | | | | * dd068b4 Merge commit '8f076d8' into HEAD
>>> | |_|_|/|
>>> |/| |_|/
>>> | |/| |
>>> | * | | 8f076d8 5
>>
>> Note that I dropped a line and compressed a slash into an underscore. It's
>> on that line that this condition is being hit.
>
> Hrm. I could see either being acceptable, but I do think the second one
> is a bit easier to read. I'm not sure which was intended for this case.
Somewhat expanding the situation to test more of these collapses, I can get
the following graph:
* 6_M1
|\
| | * 6_M2
| | |\
| | | * 6_H
| | | | * 6_M3
| | | | |\
| | | | | * 6_J
| | | | * | 6_I
| | | | | | * 6_M4
| |_|_|_|_|/|\
|/| | | | |/ /
| | | | |/| /
| | | |/| |/
| | |/| |/|
| |/| |/| |
| | |/| | |
| | * | | | 6_G
| | | |_|/
| | |/| |
| | * | | 6_F
| * | | | 6_E
| | |/ /
| |/| |
| * | | 6_D
| | |/
| |/|
* | | 6_C
| |/
|/|
* | 6_B
|/
* 6_A
Note how 6_M4 has three parents, and the first parent has a horizontal
edge. Even giving an extra padding line between horizontal edges, we
_could_ output the following instead:
| | | | | | * 6_M4
| |_|_|_|_|/|\
|/| | | | |/ /
| | |_|_|/| /
| |/| | | |/
| | | |_|/|
| | |/| | |
| | * | | | 6_G
However, I'll stick with the fix for the coloring issue. I think it
was a previous bug that just wasn't hit until now.
Thanks,
-Stolee
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox