Skip to contentSkip to conversation

Detection of directory renames

PATCH Superseded Yann Dirson 7 participants 17 messages Jun 15, 2016 Kbuild

v6 of 9 Superseded Latest is v9 →

lore
Share & tools
lore
#0 lore raw

v6 cover Detection of directory renames

Changes since v5:

* added more tests (one OK, one for suboptimal work only, one for a bug fixed)
* adjusted expected output for 'diff-index --detect-bulk-moves on a move including a subdir.', it is OK
* include a better copy_dirname based on Johnathan's code
* dropped the "Transfer special display of toplevel dir to display-time." patch posted earlier, I really think that was a bad idea.
* include 2 more patches that deal with problems with moves of deep trees, separated for easier review, but which should be squashed into the main one ultimately

Only relatively easy things are still on my immediate TODO list for this series:

* unified diff informational output
* memrchr() implementation for portability
* cleanups (free allocated structures, split long funcs a bit more, better comments, etc)
* audit remaining FIXME tags

Finishing the "--hide" feature will be next.

Yann Dirson (5):
Introduce bulk-move detection in diffcore.
Add testcases for the --detect-bulk-moves diffcore flag. [RFC] Handle the simpler case of a subdir invalidating bulk move. [RFC] Consider all parents of a file as candidates for bulk rename. [WIP] Allow hiding renames of individual files involved in a
directory rename.

 diff-lib.c                       |    6 +-
 diff.c                           |   21 ++-
 diff.h                           |    6 +
 diffcore-rename.c                |  376 +++++++++++++++++++++++++++++++++++++-
 diffcore.h                       |    2 +
 t/t4046-diff-rename-factorize.sh |  301 ++++++++++++++++++++++++++++++
 tree-diff.c                      |    4 +-
 7 files changed, 703 insertions(+), 13 deletions(-)
 create mode 100755 t/t4046-diff-rename-factorize.sh
Signature · 1 line
1.7.2.3
#1 lore raw

PATCH v6 1/5 Introduce bulk-move detection in diffcore.

This feature tries to group together files moving from and to identical directories - the most common case being directory renames.

It is activated by the new --detect-bulk-moves diffcore flag.

This is only the first step, adding the basic functionnality and adding support to raw diff output (and it is not supported in unified-diff output yet)

The output of raw diff is displayed as "Rnnn a/* b/". Those cannot be confused with renames of files named "whatever/*" with a literal star character, from the full-zero SHA1's.

Other future developements to be made on top of this include:
* extension of unified-diff format to express this
* display as such the special case of directory move/rename
* application of such new diffs: issue a conflict, or just a warning ?
* teach git-svn (and others ?) to make use of that flag
* handle new conflict type "bulk-move/add"
* detect "directory splits" as well
* use inexact dir renames to bump score of below-threshold renames from/to same locations
* add yours here

---
 diff-lib.c        |    6 +-
 diff.c            |   14 +++-
 diff.h            |    3 +
 diffcore-rename.c |  274 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 diffcore.h        |    1 +
 tree-diff.c       |    4 +-
 6 files changed, 290 insertions(+), 12 deletions(-)
diff-lib.c +4 -2
index 392ce2b..5ec3ddc 100644
@@ -208,7 +208,8 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 						    ce_option, &dirty_submodule);
 		if (!changed && !dirty_submodule) {
 			ce_mark_uptodate(ce);
-			if (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))
+			if (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&
+			    !DIFF_OPT_TST(&revs->diffopt, DETECT_BULK_MOVES))
 				continue;
 		}
 		oldmode = ce->ce_mode;
@@ -338,7 +339,8 @@ static int show_modified(struct rev_info *revs,
 
 	oldmode = old->ce_mode;
 	if (mode == oldmode && !hashcmp(sha1, old->sha1) && !dirty_submodule &&
-	    !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))
+	    !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&
+	    !DIFF_OPT_TST(&revs->diffopt, DETECT_BULK_MOVES))
 		return 0;
 
 	diff_change(&revs->diffopt, oldmode, mode,
diff.c +13 -1
index 71efa8e..4de43d6 100644
@@ -3188,6 +3188,11 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		DIFF_OPT_SET(options, REVERSE_DIFF);
 	else if (!strcmp(arg, "--find-copies-harder"))
 		DIFF_OPT_SET(options, FIND_COPIES_HARDER);
+	else if (!strcmp(arg, "--detect-bulk-moves")) {
+		DIFF_OPT_SET(options, DETECT_BULK_MOVES);
+		if (!options->detect_rename)
+			options->detect_rename = DIFF_DETECT_RENAME;
+	}
 	else if (!strcmp(arg, "--follow"))
 		DIFF_OPT_SET(options, FOLLOW_RENAMES);
 	else if (!strcmp(arg, "--color"))
@@ -3466,7 +3471,14 @@ static void diff_flush_raw(struct diff_filepair *p, struct diff_options *opt)
 	if (p->status == DIFF_STATUS_COPIED ||
 	    p->status == DIFF_STATUS_RENAMED) {
 		const char *name_a, *name_b;
-		name_a = p->one->path;
+		if (p->is_bulkmove) {
+			/* append "*" to the first dirname */
+			char buf[PATH_MAX];
+			char* next = memccpy(buf, p->one->path, '\0', PATH_MAX);
+			next[-1] = '*'; *next = '\0';
+			name_a = buf;
+		} else
+			name_a = p->one->path;
 		name_b = p->two->path;
 		strip_prefix(opt->prefix_length, &name_a, &name_b);
 		write_name_quoted(name_a, opt->file, inter_name_termination);
diff.h +3 -0
index 1fd44f5..b0d6fa6 100644
@@ -78,6 +78,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)
 #define DIFF_OPT_IGNORE_UNTRACKED_IN_SUBMODULES (1 << 25)
 #define DIFF_OPT_IGNORE_DIRTY_SUBMODULES (1 << 26)
 #define DIFF_OPT_OVERRIDE_SUBMODULE_CONFIG (1 << 27)
+#define DIFF_OPT_DETECT_BULK_MOVES  (1 << 28)
 
 #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
 #define DIFF_OPT_SET(opts, flag)    ((opts)->flags |= DIFF_OPT_##flag)
@@ -265,6 +266,8 @@ extern void diffcore_fix_diff_index(struct diff_options *);
 "  -C            detect copies.\n" \
 "  --find-copies-harder\n" \
 "                try unchanged files as candidate for copy detection.\n" \
+"  --detect-bulk-moves\n" \
+"                detect wholesale directory renames.\n" \
 "  -l<n>         limit rename attempts up to <n> paths.\n" \
 "  -O<file>      reorder diffs according to the <file>.\n" \
 "  -S<string>    find filepair whose only one side contains the string.\n" \
diffcore-rename.c +266 -8

324 lines not on this page · raw message

diffcore.h +1 -0
index b8f1fde..6dab95b 100644
@@ -69,6 +69,7 @@ struct diff_filepair {
 	unsigned broken_pair : 1;
 	unsigned renamed_pair : 1;
 	unsigned is_unmerged : 1;
+	unsigned is_bulkmove : 1;
 };
 #define DIFF_PAIR_UNMERGED(p) ((p)->is_unmerged)
 
tree-diff.c +3 -1
index cd659c6..5d9f123 100644
@@ -49,7 +49,9 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 		show_entry(opt, "+", t2, base, baselen);
 		return 1;
 	}
-	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
+	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) &&
+	    !DIFF_OPT_TST(opt, DETECT_BULK_MOVES) &&
+	    !hashcmp(sha1, sha2) && mode1 == mode2)
 		return 0;
 
 	/*
Signature · 1 line
1.7.2.3
#2 lore raw

PATCH v6 2/5 Add testcases for the --detect-bulk-moves diffcore flag.

This notably includes a couple of tests for cases known not to be working correctly yet.

---
 t/t4046-diff-rename-factorize.sh |  301 ++++++++++++++++++++++++++++++++++++++
 1 files changed, 301 insertions(+), 0 deletions(-)
 create mode 100755 t/t4046-diff-rename-factorize.sh
t/t4046-diff-rename-factorize.sh new file +301 -0
new file mode 100755
index 0000000..dca7cb7
@@ -0,0 +1,301 @@
+#!/bin/sh
+#
+# Copyright (c) 2008,2010 Yann Dirson
+# Copyright (c) 2005 Junio C Hamano
+#
+
+# TODO for dir renames:
+# * two dirs or more moving all their files to a single dir
+# * simultaneous bulkmove and rename
+
+test_description='Test rename factorization in diff engine.
+
+'
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/diff-lib.sh
+
+test_expect_success 'setup' '
+	git commit --allow-empty -m "original empty commit"
+
+	mkdir a &&
+	printf "Line %s\n" 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 >a/path0 &&
+	sed <a/path0 >a/path1 s/Line/Record/ &&
+	sed <a/path0 >a/path2 s/Line/Stuff/ &&
+	sed <a/path0 >a/path3 s/Line/Blurb/ &&
+
+	git update-index --add a/path* &&
+	test_tick &&
+	git commit -m "original set of files"
+
+	: rename the directory &&
+	mv a b &&
+	git update-index --add --remove a/path0 a/path1 a/path2 a/path3 b/path*
+'
+test_expect_success 'diff-index --detect-bulk-moves after directory move.' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	a/*	b/
+	:100644 100644 X X R#	a/path0	b/path0
+	:100644 100644 X X R#	a/path1	b/path1
+	:100644 100644 X X R#	a/path2	b/path2
+	:100644 100644 X X R#	a/path3	b/path3
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup non-100% rename' '
+	echo "Line 16" >>b/path0 &&
+	mv b/path2 b/2path &&
+	rm b/path3 &&
+	echo anything >b/path100 &&
+	git update-index --add --remove b/* b/path2 b/path3
+'
+test_expect_success 'diff-index --detect-bulk-moves after content changes.' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	a/*	b/
+	:100644 000000 X X D#	a/path3
+	:100644 100644 X X R#	a/path2	b/2path
+	:100644 100644 X X R#	a/path0	b/path0
+	:100644 100644 X X R#	a/path1	b/path1
+	:000000 100644 X X A#	b/path100
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup bulk move that is not directory move' '
+	git reset -q --hard &&
+
+	mkdir c &&
+	(
+		for i in 0 1 2; do
+			cp a/path$i c/apath$i || exit
+		done
+	) &&
+	git update-index --add c/apath* &&
+	test_tick &&
+	git commit -m "first set of changes" &&
+
+	mv c/* a/ &&
+	git update-index --add --remove a/* c/apath0 c/apath1 c/apath2
+'
+test_expect_success 'diff-index --detect-bulk-moves without full-dir rename.' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	c/*	a/
+	:100644 100644 X X R#	c/apath0	a/apath0
+	:100644 100644 X X R#	c/apath1	a/apath1
+	:100644 100644 X X R#	c/apath2	a/apath2
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup bulk move with new file in source dir' '
+	echo > c/anotherpath "How much wood?" &&
+	git update-index --add c/another*
+'
+test_expect_success 'diff-index --detect-bulk-moves with new file in source dir.' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	c/*	a/
+	:100644 100644 X X R#	c/apath0	a/apath0
+	:100644 100644 X X R#	c/apath1	a/apath1
+	:100644 100644 X X R#	c/apath2	a/apath2
+	:000000 100644 X X A#	c/anotherpath
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup bulk move with interfering copy' '
+	rm c/anotherpath &&
+	git update-index --remove c/anotherpath &&
+	mkdir b &&
+	cp a/apath0 b/apath9 &&
+	echo >> a/apath0 "more" &&
+	git update-index --add a/apath0 b/apath9
+'
+# scores select the "wrong" one as "moved" (only a suboptimal detection)
+test_expect_failure 'diff-index --detect-bulk-moves with interfering copy.' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	c/*	a/
+	:100644 100644 X X R#	c/apath0	a/apath0
+	:100644 100644 X X R#	c/apath1	a/apath1
+	:100644 100644 X X R#	c/apath2	a/apath2
+	:100644 100644 X X C#	c/apath0	b/apath9
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup bulk move to toplevel' '
+	git reset -q --hard &&
+	mv c/* . &&
+	git update-index --add --remove apath* c/apath0 c/apath1 c/apath2
+'
+test_expect_success 'diff-index --detect-bulk-moves bulk move to toplevel.' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	c/*	./
+	:100644 100644 X X R#	c/apath0	apath0
+	:100644 100644 X X R#	c/apath1	apath1
+	:100644 100644 X X R#	c/apath2	apath2
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup move including a subdir, with some content changes' '
+	git reset -q --hard &&
+	mv c a/ &&
+	git update-index --add --remove a/c/* c/apath0 c/apath1 c/apath2 &&
+	test_tick &&
+	git commit -m "move as subdir" &&
+
+	mv a b &&
+	echo foo >>b/c/apath0 &&
+	git update-index --add --remove a/path0 a/path1 a/path2 a/path3 \
+			a/c/apath0 a/c/apath1 a/c/apath2 b/path* b/c/apath*
+'
+test_expect_success 'diff-index --detect-bulk-moves on a move including a subdir.' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	a/*	b/
+	:040000 040000 X X R#	a/c/*	b/c/
+	:100644 100644 X X R#	a/c/apath0	b/c/apath0
+	:100644 100644 X X R#	a/c/apath1	b/c/apath1
+	:100644 100644 X X R#	a/c/apath2	b/c/apath2
+	:100644 100644 X X R#	a/path0	b/path0
+	:100644 100644 X X R#	a/path1	b/path1
+	:100644 100644 X X R#	a/path2	b/path2
+	:100644 100644 X X R#	a/path3	b/path3
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup move without a subdir' '
+	git reset -q --hard &&
+	mkdir b &&
+	mv a/path* b/ &&
+	: rename files in the directory but not subdir. &&
+	git update-index --add --remove a/path0 a/path1 a/path2 a/path3 b/path*
+'
+test_expect_success 'moving files but not subdirs is not mistaken for dir move' '
+	cat >expected <<-EOF &&
+	:100644 100644 X X R#	a/path0	b/path0
+	:100644 100644 X X R#	a/path1	b/path1
+	:100644 100644 X X R#	a/path2	b/path2
+	:100644 100644 X X R#	a/path3	b/path3
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup move of files and subdirs to different places' '
+	git reset -q --hard &&
+	mv a/c b &&
+	mv a d &&
+	git update-index --add --remove a/path0 a/path1 a/path2 a/path3 \
+		a/c/apath0 a/c/apath1 a/c/apath2 d/path* b/apath*
+'
+test_expect_success 'moving subdirs into one dir and files into another is not mistaken for dir move' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	a/c/*	b/
+	:100644 100644 X X R#	a/c/apath0	b/apath0
+	:100644 100644 X X R#	a/c/apath1	b/apath1
+	:100644 100644 X X R#	a/c/apath2	b/apath2
+	:100644 100644 X X R#	a/path0	d/path0
+	:100644 100644 X X R#	a/path1	d/path1
+	:100644 100644 X X R#	a/path2	d/path2
+	:100644 100644 X X R#	a/path3	d/path3
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+# the same with different ordering
+test_expect_success 'setup move of files and subdirs to different places' '
+	mv d 0 &&
+	git update-index --add --remove d/path0 d/path1 d/path2 d/path3 0/path*
+'
+test_expect_success 'moving subdirs into one dir and files into another is not mistaken for dir move' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	a/c/*	b/
+	:100644 100644 X X R#	a/path0	0/path0
+	:100644 100644 X X R#	a/path1	0/path1
+	:100644 100644 X X R#	a/path2	0/path2
+	:100644 100644 X X R#	a/path3	0/path3
+	:100644 100644 X X R#	a/c/apath0	b/apath0
+	:100644 100644 X X R#	a/c/apath1	b/apath1
+	:100644 100644 X X R#	a/c/apath2	b/apath2
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_expect_success 'setup move of dir with only subdirs' '
+	git reset -q --hard &&
+	mkdir a/b &&
+	mv a/path* a/b/ &&
+	git update-index --add --remove a/path0 a/path1 a/path2 a/path3 a/b/path* &&
+	test_tick &&
+	git commit -m "move all toplevel files down one level" &&
+
+	git mv a z
+'
+# TODO: only a suboptimal non-detection
+test_expect_failure 'moving a dir with no direct children files' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	a/*	z/
+	:040000 040000 X X R#	a/b/*	z/b/
+	:040000 040000 X X R#	a/c/*	z/c/
+	:100644 100644 X X R#	a/b/path0	z/b/path0
+	:100644 100644 X X R#	a/b/path1	z/b/path1
+	:100644 100644 X X R#	a/b/path2	z/b/path2
+	:100644 100644 X X R#	a/b/path3	z/b/path3
+	:100644 100644 X X R#	a/c/apath0	z/c/apath0
+	:100644 100644 X X R#	a/c/apath1	z/c/apath1
+	:100644 100644 X X R#	a/c/apath2	z/c/apath2
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+# now test moving all files from toplevel into subdir (does not hides file moves) (needs consensus on syntax)
+# Note: this is a special case of move of a dir into one of its own subdirs, which in
+# turn is a variant of new files/dirs being added into a dir after all its contents
+# are moved away
+
+test_expect_success 'setup move from toplevel to subdir' '
+	git reset -q --hard HEAD~3 &&
+	mv a/* . &&
+	git update-index --add --remove a/path0 a/path1 a/path2 a/path3 path* &&
+	test_tick &&
+	git commit -m "move all files to toplevel" &&
+
+	mkdir z &&
+	mv path* z/ &&
+	git update-index --add --remove path0 path1 path2 path3 z/path*
+'
+test_expect_success '--detect-bulk-moves everything from toplevel.' '
+	cat >expected <<-EOF &&
+	:040000 040000 X X R#	./*	z/
+	:100644 100644 X X R#	path0	z/path0
+	:100644 100644 X X R#	path1	z/path1
+	:100644 100644 X X R#	path2	z/path2
+	:100644 100644 X X R#	path3	z/path3
+	EOF
+	git diff-index --detect-bulk-moves HEAD >current &&
+	grep -v "^\[DBG\] " <current >current.filtered &&
+	compare_diff_raw expected current.filtered
+'
+
+test_done
Signature · 1 line
1.7.2.3
#3 lore raw

RFC PATCH v6 3/5 Handle the simpler case of a subdir invalidating bulk move.

Doing it so simply depends on the subdir moves being noticed later, this fixes only one of the remaining failing testcases. Doing better requires real handling of deep trees, which is addressed by next patch, but add much complexity.

---
 diffcore-rename.c |   59 ++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 45 insertions(+), 14 deletions(-)
diffcore-rename.c +45 -14
index f252da7..1be1af1 100644
@@ -596,10 +596,52 @@ static void check_one_bulk_move(struct diff_filepair *dstpair)
 	    maybe_disqualify_bulkmove(one_parent_path, one_leftover))
 		return;
 
+	fprintf(stderr, "[] %s -> %s ?\n",dstpair->one->path, dstpair->two->path);
+
+	// FIXME: loop over successive prefixes
+	unsigned needs_adding = 1;
+
 	/* already considered ? */
-	for (seen=bulkmove_candidates; seen; seen = seen->next)
-		if (!strcmp(seen->one->path, one_parent_path)) break;
-	if (!seen) { /* record potential dir rename */
+	for (seen=bulkmove_candidates; seen; seen = seen->next) {
+		if (seen->discarded) {
+			/* already seen a rename from seen->one to some than ->two */
+			needs_adding = 0;
+			continue;
+		}
+		/* check exact dir */
+		if (!strcmp(seen->one->path, one_parent_path)) {
+			/* already added */
+			needs_adding = 0;
+			/* check that seen entry matches this rename */
+			if (strcmp(two_parent_path, seen->two->path)) {
+				fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
+					seen->one->path, two_parent_path, seen->two->path);
+				// FIXME: may be worth to free it instead
+				seen->discarded = 1;
+			}
+			continue;
+		}
+		if (!prefixcmp(one_parent_path, seen->one->path)) {
+			if (prefixcmp(two_parent_path, seen->two->path)) {
+				fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
+					seen->one->path, two_parent_path, seen->two->path);
+				// FIXME: may be worth to free it instead
+				seen->discarded = 1;
+				continue;
+			}
+		} else {
+			fprintf(stderr, "[DBG]  %s considered irrelevant for %s -> %s\n",
+				dstpair->one->path, seen->one->path, seen->two->path);
+			continue;
+		}
+
+		/* dstpair confirms seen */
+		fprintf(stderr, "[DBG] %s -> %s DOES NOT cause discard of %s -> %s\n",
+			dstpair->one->path, dstpair->two->path,
+			seen->one->path, seen->two->path);
+	}
+	if (needs_adding) { /* record potential dir rename */
+		/* all checks ok, we keep that entry */
 		seen = xmalloc(sizeof(*seen));
 		seen->one = alloc_filespec(one_parent_path);
 		fill_filespec(seen->one, null_sha1, S_IFDIR);
@@ -614,17 +656,6 @@ static void check_one_bulk_move(struct diff_filepair *dstpair)
 			one_parent_path, two_parent_path);
 		return;
 	}
-	if (seen->discarded)
-		/* already seen a rename from seen->one to some than ->two */
-		return;
-	/* check that seen entry matches this rename */
-	if (strcmp(two_parent_path, seen->two->path)) {
-		fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
-			one_parent_path, two_parent_path, seen->two->path);
-		seen->discarded = 1;
-	}
-
-	/* all checks ok, we keep that entry */
 }
 
 /*
Signature · 1 line
1.7.2.3
#4 lore raw

RFC PATCH v6 4/5 Consider all parents of a file as candidates for bulk rename.

We previously only looked at the immediate parents of a file involved in a move. Now consider upper ones as candidates too.

The way it is done here is somewhat inefficient, but at least it handles all previously-known cases of incorrectness.

Note this patch largely puts existing code in a look, and is a bit easier to read with -w.

---
 diffcore-rename.c |  118 ++++++++++++++++++++++++++++-------------------------
 1 files changed, 63 insertions(+), 55 deletions(-)
diffcore-rename.c +63 -55
index 1be1af1..ff69201 100644
@@ -542,7 +542,7 @@ static int maybe_disqualify_bulkmove(const char* one_parent_path,
 		if (strncmp(rename_dst[j].two->path,
 			    one_parent_path, onep_len))
 			break; /* exhausted directory in this direction */
-		fprintf(stderr, "[DBG] leftover file %s in %s\n",
+		fprintf(stderr, "[DBG] leftover file %s in '%s'\n",
 			rename_dst[j].two->path, one_parent_path);
 		if (rename_dst[j].i_am_not_single || /* those were already here */
 		    (rename_dst[j].pair &&
@@ -596,66 +596,74 @@ static void check_one_bulk_move(struct diff_filepair *dstpair)
 	    maybe_disqualify_bulkmove(one_parent_path, one_leftover))
 		return;
 
-	fprintf(stderr, "[] %s -> %s ?\n",dstpair->one->path, dstpair->two->path);
+	fprintf(stderr, "[] %s -> %s ?\n", dstpair->one->path, dstpair->two->path);
 
-	// FIXME: loop over successive prefixes
-	unsigned needs_adding = 1;
+	// loop over successive prefixes
+	// FIXME: also loop over two_parent_path prefixes ?
+	do {
+		unsigned needs_adding = 1;
 
-	/* already considered ? */
-	for (seen=bulkmove_candidates; seen; seen = seen->next) {
-		if (seen->discarded) {
-			/* already seen a rename from seen->one to some than ->two */
-			needs_adding = 0;
-			continue;
-		}
-		/* check exact dir */
-		if (!strcmp(seen->one->path, one_parent_path)) {
-			/* already added */
-			needs_adding = 0;
-			/* check that seen entry matches this rename */
-			if (strcmp(two_parent_path, seen->two->path)) {
-				fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
-					seen->one->path, two_parent_path, seen->two->path);
-				// FIXME: may be worth to free it instead
-				seen->discarded = 1;
-			}
-			continue;
-		}
-		if (!prefixcmp(one_parent_path, seen->one->path)) {
-			if (prefixcmp(two_parent_path, seen->two->path)) {
-				fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
-					seen->one->path, two_parent_path, seen->two->path);
-				// FIXME: may be worth to free it instead
-				seen->discarded = 1;
+		fprintf(stderr, "[[]] %s ...\n", one_parent_path);
+
+		/* already considered ? */
+		for (seen=bulkmove_candidates; seen; seen = seen->next) {
+			if (seen->discarded) {
+				/* already seen a rename from seen->one to some than ->two */
+				needs_adding = 0;
 				continue;
 			}
-		} else {
-			fprintf(stderr, "[DBG]  %s considered irrelevant for %s -> %s\n",
-				dstpair->one->path, seen->one->path, seen->two->path);
-			continue;
+			fprintf(stderr, "[DBG]  ? %s -> %s\n", seen->one->path, seen->two->path);
+			/* subdir of "seen" source dir ? */
+			if (!prefixcmp(one_parent_path, seen->one->path)) {
+				/* subdir of "seen" dest dir ? */
+				if (!prefixcmp(two_parent_path, seen->two->path)) {
+					if (!strcmp(seen->one->path, one_parent_path) &&
+					    !strcmp(seen->two->path, two_parent_path)) {
+						/* already added */
+						fprintf(stderr, "[DBG] already added\n");
+						needs_adding = 0;
+					} else // confirms
+						fprintf(stderr, "[DBG]  'dstpair' conforts 'seen'\n");
+				} else {
+					fprintf(stderr, "[DBG] discarding %s -> %s from bulk moves (split into %s and %s)\n",
+						seen->one->path, seen->two->path,
+						two_parent_path, seen->two->path);
+					// FIXME: may be worth to free it instead
+					seen->discarded = 1;
+					if (!strcmp(seen->one->path, one_parent_path) &&
+					    prefixcmp(seen->two->path, two_parent_path)) {
+						fprintf(stderr, "[DBG] ... and not adding self\n");
+						needs_adding = 0;
+					}
+					continue;
+				}
+			}
+			else fprintf(stderr, "[DBG]  'dstpair' unrelated to 'seen'\n");
+
+			/* dstpair confirms seen, or does not infirm */
+			fprintf(stderr, "[DBG] %s -> %s DOES NOT cause discard of %s -> %s\n",
+				dstpair->one->path, dstpair->two->path,
+				seen->one->path, seen->two->path);
+		}
+		if (needs_adding) { /* record potential dir rename */
+			/* all checks ok, we keep that entry */
+			seen = xmalloc(sizeof(*seen));
+			seen->one = alloc_filespec(one_parent_path);
+			fill_filespec(seen->one, null_sha1, S_IFDIR);
+			seen->two = alloc_filespec(two_parent_path);
+			fill_filespec(seen->two, null_sha1, S_IFDIR);
+			seen->discarded = 0;
+			seen->next = bulkmove_candidates;
+			bulkmove_candidates = seen;
+			fprintf(stderr, "[DBG] %s -> %s suggests possible bulk move from %s to %s\n",
+				dstpair->one->path,
+				dstpair->two->path,
+				one_parent_path, two_parent_path);
 		}
 
-		/* dstpair confirms seen */
-		fprintf(stderr, "[DBG] %s -> %s DOES NOT cause discard of %s -> %s\n",
-			dstpair->one->path, dstpair->two->path,
-			seen->one->path, seen->two->path);
-	}
-	if (needs_adding) { /* record potential dir rename */
-		/* all checks ok, we keep that entry */
-		seen = xmalloc(sizeof(*seen));
-		seen->one = alloc_filespec(one_parent_path);
-		fill_filespec(seen->one, null_sha1, S_IFDIR);
-		seen->two = alloc_filespec(two_parent_path);
-		fill_filespec(seen->two, null_sha1, S_IFDIR);
-		seen->discarded = 0;
-		seen->next = bulkmove_candidates;
-		bulkmove_candidates = seen;
-		fprintf(stderr, "[DBG] %s -> %s suggests possible bulk move from %s to %s\n",
-			dstpair->one->path,
-			dstpair->two->path,
-			one_parent_path, two_parent_path);
-		return;
-	}
+		/* next parent if any */
+		copy_dirname(one_parent_path, one_parent_path);
+	} while (*one_parent_path);
 }
 
 /*
Signature · 1 line
1.7.2.3
#5 lore raw

PATCH v6 5/5 Allow hiding renames of individual files involved in a directory rename.

Once has identified groups of bulk-moved files, and then
the --hide-bulk-move-details flag hides those of the individual renames which carry no other information (further name change, or content changes).

This makes it much easier to a human reader to spot content changes in a commit that also moves a whole subtree.

Important note: unified diff output is not currently useful, since the "bulk move" headers are not yet added by --detect-bulk-moves, but the redundant renames are really removed.

---
 diff.c            |    7 +++++
 diff.h            |    3 ++
 diffcore-rename.c |   67 ++++++++++++++++++++++++++++++++++++++++++++++++++--
 diffcore.h        |    1 +
 4 files changed, 75 insertions(+), 3 deletions(-)
diff.c +7 -0
index 4de43d6..81282bf 100644
@@ -3193,6 +3193,13 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		if (!options->detect_rename)
 			options->detect_rename = DIFF_DETECT_RENAME;
 	}
+	else if (!strcmp(arg, "--hide-bulk-move-details")) {
+		DIFF_OPT_SET(options, HIDE_DIR_RENAME_DETAILS);
+		if (!DIFF_OPT_TST(options, DETECT_BULK_MOVES))
+			DIFF_OPT_SET(options, DETECT_BULK_MOVES);
+		if (!options->detect_rename)
+			options->detect_rename = DIFF_DETECT_RENAME;
+	}
 	else if (!strcmp(arg, "--follow"))
 		DIFF_OPT_SET(options, FOLLOW_RENAMES);
 	else if (!strcmp(arg, "--color"))
diff.h +3 -0
index b0d6fa6..7f132d0 100644
@@ -79,6 +79,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)
 #define DIFF_OPT_IGNORE_DIRTY_SUBMODULES (1 << 26)
 #define DIFF_OPT_OVERRIDE_SUBMODULE_CONFIG (1 << 27)
 #define DIFF_OPT_DETECT_BULK_MOVES  (1 << 28)
+#define DIFF_OPT_HIDE_DIR_RENAME_DETAILS (1 << 29)
 
 #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
 #define DIFF_OPT_SET(opts, flag)    ((opts)->flags |= DIFF_OPT_##flag)
@@ -268,6 +269,8 @@ extern void diffcore_fix_diff_index(struct diff_options *);
 "                try unchanged files as candidate for copy detection.\n" \
 "  --detect-bulk-moves\n" \
 "                detect wholesale directory renames.\n" \
+"  --hide-bulk-move-details\n" \
+"                hide renames of individual files in a directory rename.\n" \
 "  -l<n>         limit rename attempts up to <n> paths.\n" \
 "  -O<file>      reorder diffs according to the <file>.\n" \
 "  -S<string>    find filepair whose only one side contains the string.\n" \
diffcore-rename.c +64 -3

95 lines not on this page · raw message

diffcore.h +1 -0
index 6dab95b..a4eb8e1 100644
@@ -69,6 +69,7 @@ struct diff_filepair {
 	unsigned broken_pair : 1;
 	unsigned renamed_pair : 1;
 	unsigned is_unmerged : 1;
+	unsigned uninteresting_rename : 1;
 	unsigned is_bulkmove : 1;
 };
 #define DIFF_PAIR_UNMERGED(p) ((p)->is_unmerged)
Signature · 1 line
1.7.2.3
#6 lore raw

RFC PATCH 1/1 Consider all parents of a file as candidates for bulk rename.

In reply to Yann Dirson

We previously only looked at the immediate parents of a file involved in a move. Now consider upper ones as candidates too.

The way it is done here is somewhat inefficient, but at least it handles all previously-known cases of incorrectness.

---
 diffcore-rename.c |  120 ++++++++++++++++++++++++++++-------------------------
 1 files changed, 63 insertions(+), 57 deletions(-)

There was a major flaw in the first iteration of this patch (never looking again at discarded renames). This iteration also adds more explicit comments about why this piece of code should work, despite having been written late at night and having already shown one problem which demonstrated that a testsuite is no replacement for a good night of sleep :)

I'm still not happy with the thing, though - the loops can surely be made shorter by using the discarded flags previously set, and more importantly we need to consider moves to parents of the file's destination too, which will add a loop of its own which will have to be made as short as possible. All of this seems to require to sort bulkmove_candidates so we can binary-search into it and rapidly access related paths.

Other opinions on the spirit of this patch still gladly welcome :)

diffcore-rename.c +63 -57
index 1be1af1..a8f3a8b 100644
@@ -542,7 +542,7 @@ static int maybe_disqualify_bulkmove(const char* one_parent_path,
 		if (strncmp(rename_dst[j].two->path,
 			    one_parent_path, onep_len))
 			break; /* exhausted directory in this direction */
-		fprintf(stderr, "[DBG] leftover file %s in %s\n",
+		fprintf(stderr, "[DBG] leftover file %s in '%s'\n",
 			rename_dst[j].two->path, one_parent_path);
 		if (rename_dst[j].i_am_not_single || /* those were already here */
 		    (rename_dst[j].pair &&
@@ -596,66 +596,72 @@ static void check_one_bulk_move(struct diff_filepair *dstpair)
 	    maybe_disqualify_bulkmove(one_parent_path, one_leftover))
 		return;
 
-	fprintf(stderr, "[] %s -> %s ?\n",dstpair->one->path, dstpair->two->path);
-
-	// FIXME: loop over successive prefixes
-	unsigned needs_adding = 1;
+	fprintf(stderr, "[] %s -> %s ?\n", dstpair->one->path, dstpair->two->path);
 
-	/* already considered ? */
-	for (seen=bulkmove_candidates; seen; seen = seen->next) {
-		if (seen->discarded) {
-			/* already seen a rename from seen->one to some than ->two */
-			needs_adding = 0;
-			continue;
-		}
-		/* check exact dir */
-		if (!strcmp(seen->one->path, one_parent_path)) {
-			/* already added */
-			needs_adding = 0;
-			/* check that seen entry matches this rename */
-			if (strcmp(two_parent_path, seen->two->path)) {
-				fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
-					seen->one->path, two_parent_path, seen->two->path);
-				// FIXME: may be worth to free it instead
-				seen->discarded = 1;
+	/* loop up one_parent_path over successive parents */
+	// FIXME: also loop over two_parent_path prefixes ?
+	// FIXME: use a more informative prefixcmp to avoid strcmp calls
+	do {
+		unsigned needs_adding = 1;
+
+		fprintf(stderr, "[[]] %s ...\n", one_parent_path);
+
+		/* already considered ? */
+		for (seen=bulkmove_candidates; seen; seen = seen->next) {
+			fprintf(stderr, "[DBG]  ? %s -> %s\n", seen->one->path, seen->two->path);
+			/* subdir of "seen" source dir ? */
+			if (!prefixcmp(one_parent_path, seen->one->path)) {
+				/* subdir of "seen" dest dir ? */
+				if (!prefixcmp(two_parent_path, seen->two->path)) {
+					if (!strcmp(seen->one->path, one_parent_path) &&
+					    !strcmp(seen->two->path, two_parent_path)) {
+						/* already added */
+						fprintf(stderr, "[DBG]  already added\n");
+						needs_adding = 0;
+					} else /* is in a subdir: confirms but still
+						* may need adding */
+						fprintf(stderr, "[DBG]  'dstpair' conforts 'seen'\n");
+				} else {
+					fprintf(stderr, "[DBG] discarding %s -> %s from bulk moves (split into %s and %s)\n",
+						seen->one->path, seen->two->path,
+						two_parent_path, seen->two->path);
+					seen->discarded = 1;
+					/* Need to discard dstpair as well, unless moving
+					 * from a strict subdir of seen->one or to a
+					 * strict subdir of seen->two */
+					if (!strcmp(seen->one->path, one_parent_path) &&
+					    prefixcmp(seen->two->path, two_parent_path)) {
+						fprintf(stderr, "[DBG] ... and not adding self\n");
+						needs_adding = 0;
+					}
+					continue;
+				}
 			}
-			continue;
+			else fprintf(stderr, "[DBG]  %s outside of %s\n",
+				     one_parent_path, seen->one->path);
+
+			/* dstpair confirms seen, or does not infirm */
+			fprintf(stderr, "[DBG] %s -> %s DOES NOT cause discard of %s -> %s\n",
+				dstpair->one->path, dstpair->two->path,
+				seen->one->path, seen->two->path);
 		}
-		if (!prefixcmp(one_parent_path, seen->one->path)) {
-			if (prefixcmp(two_parent_path, seen->two->path)) {
-				fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
-					seen->one->path, two_parent_path, seen->two->path);
-				// FIXME: may be worth to free it instead
-				seen->discarded = 1;
-				continue;
-			}
-		} else {
-			fprintf(stderr, "[DBG]  %s considered irrelevant for %s -> %s\n",
-				dstpair->one->path, seen->one->path, seen->two->path);
-			continue;
+		if (needs_adding) { /* record potential dir rename */
+			seen = xmalloc(sizeof(*seen));
+			seen->one = alloc_filespec(one_parent_path);
+			fill_filespec(seen->one, null_sha1, S_IFDIR);
+			seen->two = alloc_filespec(two_parent_path);
+			fill_filespec(seen->two, null_sha1, S_IFDIR);
+			seen->discarded = 0;
+			seen->next = bulkmove_candidates;
+			bulkmove_candidates = seen;
+			fprintf(stderr, "[DBG] %s -> %s suggests possible bulk move from %s to %s\n",
+				dstpair->one->path,
+				dstpair->two->path,
+				one_parent_path, two_parent_path);
 		}
-
-		/* dstpair confirms seen */
-		fprintf(stderr, "[DBG] %s -> %s DOES NOT cause discard of %s -> %s\n",
-			dstpair->one->path, dstpair->two->path,
-			seen->one->path, seen->two->path);
-	}
-	if (needs_adding) { /* record potential dir rename */
-		/* all checks ok, we keep that entry */
-		seen = xmalloc(sizeof(*seen));
-		seen->one = alloc_filespec(one_parent_path);
-		fill_filespec(seen->one, null_sha1, S_IFDIR);
-		seen->two = alloc_filespec(two_parent_path);
-		fill_filespec(seen->two, null_sha1, S_IFDIR);
-		seen->discarded = 0;
-		seen->next = bulkmove_candidates;
-		bulkmove_candidates = seen;
-		fprintf(stderr, "[DBG] %s -> %s suggests possible bulk move from %s to %s\n",
-			dstpair->one->path,
-			dstpair->two->path,
-			one_parent_path, two_parent_path);
-		return;
-	}
+		/* next parent if any */
+		copy_dirname(one_parent_path, one_parent_path);
+	} while (*one_parent_path);
 }
 
 /*
Signature · 1 line
1.7.2.3
#7 lore raw

PATCH 1/1 compat: add memrchr()

In reply to Yann Dirson

Reimplement another handy convenience function from glibc. memrchr() searches from the end of a memory area for a particular character. It is similar to strrchr() but takes a length argument and is binary-safe.

The whole-directory rename detection patch could use this to find the last directory separator in a (possibly truncated) pathname.

---

Quoted 1 line · Yann Dirson

* memrchr() implementation for portability

Something like this? Untested.

 git-compat-util.h |   16 ++++++++++++++++
 1 files changed, 16 insertions(+), 0 deletions(-)
git-compat-util.h +16 -0
index 2af8d3e..6f1020e 100644
@@ -366,6 +366,9 @@ extern int git_vsnprintf(char *str, size_t maxsize,
 #define HAVE_STRCHRNUL
 #define HAVE_MEMPCPY
 #endif
+#if __GLIBC_PREREQ(2, 2)
+#define HAVE_MEMRCHR
+#endif
 #endif
 
 #ifndef HAVE_STRCHRNUL
@@ -386,6 +389,19 @@ static inline void *gitmempcpy(void *dest, const void *src, size_t n)
 }
 #endif
 
+#ifndef HAVE_MEMRCHR
+#define memrchr gitmemrchr
+static inline void *gitmemrchr(const void *s, int c, size_t n)
+{
+	const char *p = s;
+	p += n;
+	while (p != s)
+		if (*--p == c)
+			return p;
+	return NULL;
+}
+#endif
+
 extern void release_pack_memory(size_t, int);
 
 typedef void (*try_to_free_t)(size_t);
Signature · 1 line
1.7.2.3
#8 lore raw

Re: [PATCH] compat: add memrchr()

Quoted 8 lines · Jonathan Nieder

Reimplement another handy convenience function from glibc.  memrchr() searches from the end of a memory area for a particular character.  It is similar to strrchr() but takes a length argument and is binary-safe.

The whole-directory rename detection patch could use this to find the last directory separator in a (possibly truncated) pathname.

Are you sure this would work on Windows where both '/' and '\' are valid directory separators?

#9 lore raw

Re: [PATCH] compat: add memrchr()

Am 10/15/2010 10:56, schrieb Erik Faye-Lund:

Quoted 6 lines · Jonathan Nieder
Quoted 5 lines

Reimplement another handy convenience function from glibc. memrchr() searches from the end of a memory area for a particular character. It is similar to strrchr() but takes a length argument and is binary-safe.

Quoted 6 lines
Quoted 3 lines

The whole-directory rename detection patch could use this to find the last directory separator in a (possibly truncated) pathname.

Are you sure this would work on Windows where both '/' and '\' are valid directory separators?

I'm sure this would be used only on paths that were constructed from index or repository contents; there, the directory separator is '/' by definition.

-- Hannes

#10 lore raw

Re: [PATCH] compat: add memrchr()

In reply to Jonathan Nieder
Quoted 7 lines · Jonathan Nieder

Reimplement another handy convenience function from glibc.  memrchr() searches from the end of a memory area for a particular character.  It is similar to strrchr() but takes a length argument and is binary-safe.

The whole-directory rename detection patch could use this to find the last directory separator in a (possibly truncated) pathname.

Maybe something like this for configure.ac:

    AC_CHECK_LIB([c], [memchr],
    [HAVE_MEMRCHR=YesPlease],
    [HAVE_MEMRCHR=])
    AC_SUBST(HAVE_MEMRCHR)

And documentation with the other HAVE_* variables at the top of the Makefile?

#11 lore raw

Re: [PATCH] compat: add memrchr()

Quoted 9 lines · Ævar Arnfjörð Bjarmason

Maybe something like this for configure.ac:

    AC_CHECK_LIB([c], [memchr],
    [HAVE_MEMRCHR=YesPlease],
    [HAVE_MEMRCHR=])
    AC_SUBST(HAVE_MEMRCHR)

And documentation with the other HAVE_* variables at the top of the Makefile?

Hmm, the BSDs and plan 9 have an memrchr() apparently. Any idea for
taking advantage of that (the makefile support part) that's less ugly than this?

If we miss a platform, that's no big deal. The 1-char-at-a-time loop is not so slow, and the "#define memrchr gitmemrchr" ensures that it would not conflict with the libc version.
---

Makefile +5 -0
index 1f1ce04..fa91530 100644
@@ -211,6 +211,8 @@ all::
 #
 # Define NO_REGEX if you have no or inferior regex support in your C library.
 #
+# Define HAVE_MEMRCHR if you have memrchr() in your C library.
+#
 # Define JSMIN to point to JavaScript minifier that functions as
 # a filter to have gitweb.js minified.
 #
@@ -1388,6 +1390,9 @@ endif
 ifdef NO_UINTMAX_T
 	BASIC_CFLAGS += -Duintmax_t=uint32_t
 endif
+ifdef HAVE_MEMRCHR
+	BASIC_CFLAGS += -DHAVE_MEMRCHR
+endif
 ifdef NO_SOCKADDR_STORAGE
 ifdef NO_IPV6
 	BASIC_CFLAGS += -Dsockaddr_storage=sockaddr_in
git-compat-util.h +1 -1
index 6f1020e..45aaebc 100644
@@ -366,7 +366,7 @@ extern int git_vsnprintf(char *str, size_t maxsize,
 #define HAVE_STRCHRNUL
 #define HAVE_MEMPCPY
 #endif
-#if __GLIBC_PREREQ(2, 2)
+#if __GLIBC_PREREQ(2, 2) && !defined(HAVE_MEMRCHR)
 #define HAVE_MEMRCHR
 #endif
 #endif
#12 lore raw

Re: [PATCH] compat: add memrchr()

Quoted 9 lines · Jonathan Nieder
Quoted 7 lines · Ævar Arnfjörð Bjarmason

Maybe something like this for configure.ac:

    AC_CHECK_LIB([c], [memchr],
    [HAVE_MEMRCHR=YesPlease],
    [HAVE_MEMRCHR=])
    AC_SUBST(HAVE_MEMRCHR)

Quoted 6 lines
Quoted 2 lines

And documentation with the other HAVE_* variables at the top of the Makefile?

Hmm, the BSDs and plan 9 have an memrchr() apparently.   Any idea for taking advantage of that (the makefile support part) that's less ugly than this?

Check out my "Makefile & configure: add a NO_FNMATCH flag" and "Makefile & configure: add a NO_FNMATCH_CASEFOLD flag" patches already in pu.

Maybe it should be a NO_* flag since that's what we use when we expect sanity, e.g. we have NO_REGEXP=, NO_CURL and NO_GETTEXT.

Then you just need NO_MEMRCHR=UnfortunatelyYes entries in the big if/else block for those platforms that don't have it.

But memrchr() is a GNU extension so it should probably be a HAVE_*. I don't know.

Quoted 3 lines

If we miss a platform, that's no big deal.  The 1-char-at-a-time loop is not so slow, and the "#define memrchr gitmemrchr" ensures that it would not conflict with the libc version.

Yup, probably best as a HAVE_*. In any case the autoconf probe I added should work when memrchr is spelled properly.

#13 lore raw

Re: [PATCH] compat: add memrchr()

Quoted 5 lines · Ævar Arnfjörð Bjarmason

Maybe it should be a NO_* flag since that's what we use when we expect sanity, e.g. we have NO_REGEXP=, NO_CURL and NO_GETTEXT.

Then you just need NO_MEMRCHR=UnfortunatelyYes entries in the big if/else block for those platforms that don't have it.

Hmmm, perhaps our naming convention have deteriorated over time.

I think one of the oldest one is NO_CURL, which started out as a way to say "I do not have to go over http and dumb http transport is of no use to me. I _might_ have curl library installed on this system, but it does not matter. No thanks, please do not build git with curl support". For some people, it also meant "Unfortunately I do not have a working curl library here, so I'll live with a git without http support".

On the other hand, NO_REGEX means "regrettably the platform implementation is not good enough for our codebase, and we do need to use a replacement implementation from compat/".

The difference is that it is not an option to build a less capable git that lacks features that depend on REGEX. But somehow we ended up using the same NO_ prefix, conflating the two. In that sense NO_GETTEXT is named correctly, I think, as we fall back on implementation (i.e. less capable git) that does not do i18n/l10n.

Quoted 2 lines

But memrchr() is a GNU extension so it should probably be a HAVE_*. I don't know.

Yes, if we want to express that we positively rely on the existence of an extension, HAVE_* does sound more correct. It also is how the world with autoconf/configure works.

We might want to clean up the names of variables at some point, but from a quick glance things do not look very good.

Most NO_FOO are misnamed and should be !HAVE_FOO, but because our codebase tend to use more common features, switching from the way we currently do, i.e. assuming we have FOO and defining NO_FOO for oddball platforms, to the other way around of defining HAVE_FOO for platforms where we do have FOO and omit it for the ones that lack, may make the Makefile more cluttered.

But as I already said, switching to HAVE_FOO has one definite advantage; it is more conventional and would mesh a lot better with the way autoconf/configure would do things.

Here is a quick break-down of the current set I found from the 'master' branch.

* You decline to build, or are unable to build, git with...

NO_CURL transport based on libcurl e.g. HTTP.
NO_ICONV charset re-encoding support.
NO_IPV6 IPV6
NO_NSEC nanosecond resolution file timestamps
NO_POSIX_ONLY_PROGRAMS
NO_PYTHON anything that depends on Python
NO_SYMLINK_HEAD support for original layout where .git/HEAD was a symlink
NO_SVN_TESTS test that spends too much time on git-svn

* We work around the lack of the platform feature FOO without loss of features from git (i.e. should be !HAVE_FOO):

NO_C99_FORMAT SZ_FMT and friends
NO_D_INO_IN_DIRENT (struct dirent)d.d_ino
NO_D_TYPE_IN_DIRENT (struct dirent)d.d_type
NO_HSTRERROR
NO_INET_NTOP
NO_INET_PTON
NO_LIBGEN_H
NO_MEMMEM
NO_MKDTEMP
NO_MKSTEMPS
NO_MMAP
HAVE_PATHS_H #include <paths.h>
NO_PERL_MAKEMAKER
NO_PREAD
NO_REGEX
NO_R_TO_GCC_LINKER
NO_SETENV
NO_SOCKADDR_STORAGE
NO_ST_BLOCKS_IN_STRUCT_STAT
NO_STRCASESTR
NO_STRLCPY
NO_STRTOK_R
NO_STRTOULL
NO_STRTOUMAX
NO_SYS_SELECT_H
NO_TRUSTABLE_FILEMODE
NO_UINTMAX_T
NO_UNSETENV

Unfortunately the world is not so black-and-white. There is another class

* Depending on platform features, we use different implementation with almost no observable difference in behaviour (perhaps except for performance)

NO_PTHREADS
Use of threads for better machine utilization

NO_FAST_WORKING_DIRECTORY
Reading from object database is faster than opening a file in the working directory and reading from it on this platform, so we do the former when we know the file in the working directory is clean. Perhaps !HAVE_FAST_WORKING_DIRECTORY.

And yet another that is completely unrelated:

NO_SUBDIR

#14 lore raw

Re: [PATCH] compat: add memrchr()

In reply to Ævar Arnfjörð Bjarmason

Am 10/15/2010 7:31, schrieb Ævar Arnfjörð Bjarmason:

Quoted 3 lines

Maybe something like this for configure.ac:

    AC_CHECK_LIB([c], [memchr],

Don't forget to change this to [memrchr] before you submit a patch.

Quoted 3 lines
    [HAVE_MEMRCHR=YesPlease],
    [HAVE_MEMRCHR=])
    AC_SUBST(HAVE_MEMRCHR)

-- Hannes

#15 lore raw

Re: [PATCH] compat: add memrchr()

In reply to Jonathan Nieder
Quoted 5 lines · Jonathan Nieder <jrnieder <at> gmail.com> writes:

Reimplement another handy convenience function from glibc. memrchr() searches from the end of a memory area for a particular character. It is similar to strrchr() but takes a length argument and is binary-safe.

System memrchr uses a byte comparison rather than an int comparison.

"The memchr() function scans the first n bytes of the memory area pointed to by s for the character c. The first byte to match c (interpreted as an unsigned character) stops the operation. "

See: http://linux.die.net/man/3/memrchr

It's a good idea to do the same thing for compatibility reasons.

/Ludde

#16 lore raw

PATCH v2 1/1 compat: add memrchr()

Reimplement another handy convenience function from glibc. memrchr() searches from the end of a memory area for a particular character. It is similar to strrchr() but takes a length argument and is binary-safe.

The whole-directory rename detection patch could use this to find the last '/' in a (possibly truncated) pathname.

The system memrchr() is used on glibc systems to provide a sanity check that our code works with a non-custom implementation. Yes, the various BSDs have their own highly optimized memrchr(), too. The planned use of memrchr in git is for clarity, not speed, so it is not obvious that the makefile+autoconf magic to use libc's implementation on a wide variety of operating systems would be worth the time.

---

Quoted 5 lines · Ludvig Strigeus

System memrchr uses a byte comparison rather than an int comparison.

"The memchr() function scans the first n bytes of the memory area pointed to by s for the character c. The first byte to match c (interpreted as an unsigned character) stops the operation. "

Oh, right. (strchr() uses char, memchr() uses unsigned char.)

 git-compat-util.h |   16 ++++++++++++++++
 1 files changed, 16 insertions(+), 0 deletions(-)
git-compat-util.h +16 -0
index 2af8d3e..6de9dee 100644
@@ -366,6 +366,9 @@ extern int git_vsnprintf(char *str, size_t maxsize,
 #define HAVE_STRCHRNUL
 #define HAVE_MEMPCPY
 #endif
+#if __GLIBC_PREREQ(2, 2)
+#define HAVE_MEMRCHR
+#endif
 #endif
 
 #ifndef HAVE_STRCHRNUL
@@ -386,6 +389,19 @@ static inline void *gitmempcpy(void *dest, const void *src, size_t n)
 }
 #endif
 
+#ifndef HAVE_MEMRCHR
+#define memrchr gitmemrchr
+static inline void *gitmemrchr(const void *s, int c, size_t n)
+{
+	const unsigned char *p = s;
+	p += n;
+	while (p != s)
+		if (*--p == (unsigned char) c)
+			return p;
+	return NULL;
+}
+#endif
+
 extern void release_pack_memory(size_t, int);
 
 typedef void (*try_to_free_t)(size_t);
Signature · 1 line
1.7.2.3