gitweb: Remove --full-history from git_history

Stop pretending that gitweb is rename-aware, and remove --full-history option to git-rev-list in git_history (for "history" action):

* gitweb cannot handle renames as of yet; it uses constant original $file_name as 'f' argument in links
* at least for git 1.4.1.1 --full-history option doesn't follow renames (check 'git rev-list next -- gitweb/test/file+plus+sign' with and without --full-history option and compare to
'git rev-list next -- gitweb/test/file+plus+sign test/file+plus+sign') and is three times slower than git-rev-list without --full-history

---
This is call for better rename support in git (better than --full-history). There was such an attempt in "[RFC, PATCH] Teach revision.c about renames" by Fredrik Kuivinen
http://marc.theaimsgroup.com/?l=git&m=114772921317920
but IIRC patch was dropped in the favor of --full-history option.

What is needed by gitweb is for git-rev-list to not only follow revisions of file contents across renames, and return more revisions, but also return _how_ filename changes, without need to call git-diff-tree on each returned revision.

PROPOSAL:
---------

Implement --follow/--follow-path/--follow-contents option to git-rev-list, which would output besides revision ids also current path limit; the format could be for example:

<commit> [ -- <paths>...]

for example:

$ git rev-list --follow db58b69ba -- gitweb/test/file+plus+sign
0a8f4f0020cb35095005852c0797f0b90e9ebb74 -- gitweb/test/file+plus+sign
85852d44e48c1d1c6d815cc5fccf1b580f2f2cad -- test/file+plus+sign
cc3245b6512a01d74c0fd460d762ba8a1e8b968a -- test/file+plus+sign

There might be better format, as the proposed isn't best for copying detections support, as path limit gets larger and one cannot immediately get which element of new <paths>... correspond to which original <paths>... element. Same with splitting file vs. simply creating file.

It should be not that hard to implement, just detecting copying, renaming and filename vanishing, and updating current path limit; or putting modified path limit and revision to start modified path-limit from to the queue...

 gitweb/gitweb.perl |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

index ae13e3e..59222c2 100755
@@ -2284,7 +2284,7 @@ sub git_history {
 	git_print_page_path($file_name, $ftype);
 
 	open my $fd, "-|",
-		$GIT, "rev-list", "--full-history", $hash_base, "--", $file_name;
+		$GIT, "rev-list", $hash_base, "--", $file_name;
 	print "<table cellspacing=\"0\">\n";
 	my $alternate = 0;
 	while (my $line = <$fd>) {

1.4.1.1

I don't think it was dropped in favor --full-history. Anyway, I did some more work on that patch back then. Compared to the one posted in the mail referenced above a couple of bugs have been fixed and a few tests have been added. If anyone wants to play with it see the patch in the end of this mail. It is on top of ed90cbf5f681c0144909457be3f4792b47604a5b, so it's quite old and will most probably not apply cleanly on the current master branch. I just noticed that it makes t/t6003-rev-list-topo-order.sh fail too.

Note that it is not enough to only return more revisions.

For example, consider the commits (newest commit first)
A: Rename "bar" to "foo"
B: No changes to "bar"
C: No changes to "bar", delete "foo"
<more commits here>

Then you want "git-rev-list --renames A -- foo" to return A,... not A,C,...

This is currently not done by the patch. Should be straight forward to add though.

- Fredrik

---
 Documentation/git-rev-list.txt |    6 
 Makefile                       |    2 
 log-tree.c                     |    9 
 revision.c                     |  636 ++++++++++++++++++++++++++++++++++++++++-
 revision.h                     |   38 ++
 t/t6004-rev-list-rename.sh     |  100 ++++++
 6 files changed, 780 insertions(+), 11 deletions(-)

index ad6d14c..f7ecf8e 100644
@@ -103,6 +103,12 @@ OPTIONS
 	topological order (i.e. descendant commits are shown
 	before their parents).
 
+--renames::
+	When optional paths are given together with '--renames' the
+	paths are tracked, and any renames detected by Git are
+	followed. This is useful for tracking the history of files
+	across renames.
+
 Author
 ------
 Written by Linus Torvalds <[email protected]>

index dbf19c6..4212a05 100644
@@ -85,7 +85,7 @@ uname_P := $(shell sh -c 'uname -p 2>/de
 
 # CFLAGS and LDFLAGS are for the users to override from the command line.
 
-CFLAGS = -g -O2 -Wall
+CFLAGS = -g3 -O0 -Wall
 LDFLAGS =
 ALL_CFLAGS = $(CFLAGS)
 ALL_LDFLAGS = $(LDFLAGS)

index 58b0163..e53dd19 100644
@@ -133,11 +133,12 @@ int log_tree_diff_flush(struct rev_info 
 }
 
 static int diff_root_tree(struct rev_info *opt,
-			  const unsigned char *new, const char *base)
+			  struct commit* commit, const char *base)
 {
 	int retval;
 	void *tree;
 	struct tree_desc empty, real;
+	const unsigned char* new = commit->object.sha1;
 
 	tree = read_object_with_reference(new, tree_type, &real.size, NULL);
 	if (!tree)

@@ -146,9 +147,11 @@ static int diff_root_tree(struct rev_inf
 
 	empty.buf = "";
 	empty.size = 0;
+	rev_setup_diffopt_paths(opt, commit, NULL);
 	retval = diff_tree(&empty, &real, base, &opt->diffopt);
 	free(tree);
 	log_tree_diff_flush(opt);
+	rev_free_diffopt_paths(opt, commit);
 	return retval;
 }
 

@@ -178,7 +181,7 @@ static int log_tree_diff(struct rev_info
 	parents = commit->parents;
 	if (!parents) {
 		if (opt->show_root_diff)
-			diff_root_tree(opt, sha1, "");
+			diff_root_tree(opt, commit, "");
 		return !opt->loginfo;
 	}
 

@@ -197,8 +200,10 @@ static int log_tree_diff(struct rev_info
 	for (;;) {
 		struct commit *parent = parents->item;
 
+		rev_setup_diffopt_paths(opt, commit, parent);
 		diff_tree_sha1(parent->object.sha1, sha1, "", &opt->diffopt);
 		log_tree_diff_flush(opt);
+		rev_free_diffopt_paths(opt, commit);
 
 		showed_log |= !opt->loginfo;
 

index bdbdd23..a2d9666 100644
@@ -9,15 +9,19 @@ #define TMP_MARK	(1u<<4) /* for isolated
 #define BOUNDARY	(1u<<5)
 #define BOUNDARY_SHOW	(1u<<6)
 #define ADDED		(1u<<7)	/* Parents already parsed and added? */
+#define DUPLICATE	(1u<<8)
 
 struct rev_info;
 struct log_info;
+struct path_list;
 
 typedef void (prune_fn_t)(struct rev_info *revs, struct commit *commit);
 
 struct rev_info {
 	/* Starting list */
 	struct commit_list *commits;
+	  /* the last entry in the 'commits' list */
+	struct commit_list *last_commit;
 	struct object_list *pending_objects;
 
 	/* Basic information */

@@ -39,7 +43,8 @@ struct rev_info {
 			limited:1,
 			unpacked:1,
 			boundary:1,
-			parents:1;
+			parents:1,
+			follow_renames:1;
 
 	/* Diff flags */
 	unsigned int	diff:1,

@@ -70,6 +75,11 @@ struct rev_info {
 	struct diff_options diffopt;
 	struct diff_options pruning;
 
+	/* Rename following */
+	struct path_list* initial_paths;
+	struct mem_pool* string_pool;
+	struct mem_pool* list_pool;
+
 	topo_sort_set_fn_t topo_setter;
 	topo_sort_get_fn_t topo_getter;
 };

@@ -84,6 +94,7 @@ extern int rev_compare_tree(struct rev_i
 
 extern void init_revisions(struct rev_info *revs);
 extern int setup_revisions(int argc, const char **argv, struct rev_info *revs, const char *def);
+extern void free_revisions(struct rev_info *revs);
 extern void prepare_revision_walk(struct rev_info *revs);
 extern struct commit *get_revision(struct rev_info *revs);
 

@@ -101,4 +112,29 @@ extern struct object_list **add_object(s
 				       struct name_path *path,
 				       const char *name);
 
+struct path_list {
+	char* item;
+	struct path_list *next;
+};
+
+struct rev_commit_info {
+	struct path_list* paths;
+	void* topo_data;
+};
+
+extern const struct path_list* path_list_find(const struct path_list* list,
+					      const char* path);
+extern struct path_list* path_list_insert(char *item,
+					  struct path_list **list_p);
+extern void path_list_print(FILE*, struct path_list* list);
+extern void free_path_list(struct path_list *list);
+extern const char** convert_to_pathspec(struct path_list* l1,
+					struct path_list* l2);
+
+extern void rev_setup_diffopt_paths(struct rev_info* revs,
+				    struct commit* commit,
+				    struct commit* parent);
+extern void rev_free_diffopt_paths(struct rev_info* revs,
+				   struct commit* commit);
+
 #endif

Correct.

The --full-history option is about merge simplification and has nothing to do with renames.

The thing is, your patch, while I very much liked the direction it was taking us, was so intrusive that it scared the h*ck out of me ;-).

Yes. For this "following renames for a single file" example, we should not extend the pathspec which originally starts out as "foo" to _include_ "bar"; instead it should _replace_, and after that point we should not care about "foo".

This was another reason I shied away from your patch back then. We would need to think about interactions between this pathspec for a single file (which should be switched) and pathspecs for directories ("more useful form of usage than single file", as Linus would put it).

I have this vague feeling, without revisiting the code to make an informed argument, that it might be cleaner and with less impact (read: smaller chance to break the "directories" usage) if we special case "follow a single file" case. I dunno.

Also I was not sure how well your pathspec switching worked across forks and merges.

                            M bar
           .----------------4------5
          /                         \

A bar / R bar->foo M foo \ M foo
0------1-----2-----------3-----------6----7-------8

Suppose we are at 8 and start digging for the history of "foo". Our pathspec starts out as "foo" at 8 and stays so until we hit
6. If the lower branch renamed bar->foo while the upper didn't, and merge-recursive merged them correctly at 6, we would use "foo" as pathspec while on the lower branch while traversing 6, 3 and 2 (at that point we switch to "bar"). On the upper branch, we switch pathspec to "bar" while traversing 6, 5, 4. When we hit 1, pathspec of both of its children (2 and 4) happen to match in this example. But what would we do if for some reason they didn't? Do we care? Is that die("an internal error")? I did not have a good anser to that question, and I still don't.

I kind of suspected that :) It certainly is intrusive and it changes revision.c which is at the very core of git.

I mentioned a couple of different strategies for handling the directory case in the original mail.

Yes, it most certainly is. We actually already have the "follow a single file from a single commit" case implemented already, in blame.c. But it is much cooler to be able to track multiple files from several different starting points ("git-rev-list --renames A B C --
foo bar") :) It also makes the git-rev-list interface more
consistent. No special cases such as "if you use --renames then you can only specify one pathspec (which has to be a filename)".

I _think_ that the patch as it currently is would track both files from 1 and onwards. That is, if the upper branch tracks "foobar" when we hit 1 and the lower branch tracks "bar" then we would track both "foobar" and "bar" at 1 and 0.

- Fredrik

By the way, --full-history option is not documented: neither in Documentation/git-rev-list.txt, nor in git-rev-list --usage

Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Hi,

your struct path_list and find_renames() is so similar to what is already in merge-recursive.c that it is not even funny.

Furthermore, the struct path_list from path-list.[ch] implements a sorted list, so that lookups are way cheaper than with linked lists.

IMHO this whole renaming stuff should go into a new file, renames.c, and be reused as often as possible.

Ciao,
Dscho

Where did you get the idea that --full-history has anything to do with renames?

Message-ID: <[email protected]>
Message-ID: <[email protected]>

http://marc.theaimsgroup.com/?l=git&m=115171557714437

http://marc.theaimsgroup.com/?l=git&m=115171683714119

Ooops, sorry, my mistake. Still, even if the patch is to be dropped, the proposal about rename detection is still valid.

I wonder which version is faster: --full-history, or filter using diff-tree?

ab -n 10 "http://localhost/cgi-bin/gitweb/gitweb.cgi?p=git.git;a=history;hb=next;f=gitweb/gitweb.perl" (ApacheBench, Version 2.0.41-dev <$Revision: 1.141 $> apache-2.0) says

  Requests per second:    0.09 [#/sec] (mean)
  Time per request:       10918.552 [ms] (mean)
  Time per request:       10918.552 [ms] (mean, across all concurrent requests)
  Transfer rate:          2.13 [Kbytes/sec] received

Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.0 0 0
Processing: 8851 10917 2776.1 9284 16420
Waiting: 407 457 95.1 428 721
Total: 8851 10917 2776.1 9284 16420

for --full-history version, and

  Requests per second:    0.11 [#/sec] (mean)
  Time per request:       9076.865 [ms] (mean)
  Time per request:       9076.865 [ms] (mean, across all concurrent requests)
  Transfer rate:          2.57 [Kbytes/sec] received

Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.0 0 0
Processing: 8741 9076 271.7 9100 9581
Waiting: 299 405 49.5 404 507
Total: 8741 9076 271.7 9100 9581

for the pipe through git-diff-tree version, both with very similar times (check out median column), although --full-history version seems slightly slower...

Still, it is ab on workstation, not separate server, an only average over 10 requests.

And
1025:jnareb@roke:~/git> time git rev-list next -- gitweb/gitweb.perl
[...]

  real    0m2.623s
  user    0m2.536s
  sys     0m0.016s
1024:jnareb@roke:~/git> time git rev-list next | git diff-tree -r --stdin -- gitweb/gitweb.perl
  [...]
  real    0m6.857s
  user    0m6.024s
  sys     0m0.068s

Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Adding "--remove-empty" (would this change output for git_history much?) changes this to:

  Requests per second:    0.75 [#/sec] (mean)
  Time per request:       1341.702 [ms] (mean)
  Time per request:       1341.702 [ms] (mean, across all concurrent requests)
  Transfer rate:          17.37 [Kbytes/sec] received

Connection Times (ms)
min mean[+/-sd] median max
Connect: 0 0 0.0 0 0
Processing: 1208 1340 206.6 1241 1729
Waiting: 386 408 36.6 403 510
Total: 1208 1340 206.6 1241 1729

Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

format

And of course git-diff-tree --stdin should accept not only list of revisions or list of tree pairs, but also path limits.

Jakub Narebski
Warsaw, Poland
ShadeHawk on #git