Skip to contentSkip to conversation

how to do directory renames in fast-import

PATCH In review David Frech 5 participants 10 messages Jun 15, 2016 Documentation

lore
Share & tools
lore
#0 lore raw

Git can track file renames implicitly. If I delete and then add (under a different name) the same content, git will figure that out.

But if a directory was renamed, I have no way to tell fast-import about it. I can't delete the directory (using a 'D' command) and then add it back (with a different name) with all its contents, because my source material (an svn dump file) doesn't tell me, at that point, about all the files involved because nothing about them has changed.

fast-import knows about the contents of the directory I want to rename, but doesn't give me a primitive to do the rename. Is this something we need to add? My frontend could keep track of this, but I would duplicating work that fast-import is already doing.

Cheers,

- David

Signature · 2 lines
If I have not seen farther, it is because I have stood in the
footsteps of giants.
#1 lore raw

PATCH 1/1 Support wholesale directory renames in fast-import

Some source material (e.g. Subversion dump files) perform directory renames without telling us exactly which files in that subdirectory were moved. This makes it hard for a frontend to convert such data formats to a fast-import stream, as all the frontend has on hand is "Rename a/ to b/" with no details about what files are in a/, unless the frontend also kept track of all files.

The new 'R' subcommand within a commit allows the frontend to rename either a file or an entire subdirectory, without needing to know the object's SHA-1 or the specific files contained within it. The rename is performed as efficiently as possible internally, making it cheaper than a 'D'/'M' pair for a file rename.

---

Quoted 9 lines · David Frech

Git can track file renames implicitly. If I delete and then add (under a different name) the same content, git will figure that out.

But if a directory was renamed, I have no way to tell fast-import about it. I can't delete the directory (using a 'D' command) and then add it back (with a different name) with all its contents, because my source material (an svn dump file) doesn't tell me, at that point, about all the files involved because nothing about them has changed.

Quoted 4 lines

fast-import knows about the contents of the directory I want to rename, but doesn't give me a primitive to do the rename. Is this something we need to add? My frontend could keep track of this, but I would duplicating work that fast-import is already doing.

Does the following do the trick for you? It is also available from my fastimport.git master branch:

git://repo.or.cz/git/fastimport.git master
http://repo.or.cz/r/git/fastimport.git master

Yes, it passes all tests...

 Documentation/git-fast-import.txt |   28 ++++++++++-
 fast-import.c                     |   91 ++++++++++++++++++++++++++++++-------
 t/t9300-fast-import.sh            |   68 +++++++++++++++++++++++++++
 3 files changed, 168 insertions(+), 19 deletions(-)
Documentation/git-fast-import.txt +25 -3
index c66af7c..80a8ee0 100644
@@ -302,7 +302,7 @@ change to the project.
 	data
 	('from' SP <committish> LF)?
 	('merge' SP <committish> LF)?
-	(filemodify | filedelete | filedeleteall)*
+	(filemodify | filedelete | filerename | filedeleteall)*
 	LF
 ....
 
@@ -325,11 +325,13 @@ commit message use a 0 length data.  Commit messages are free-form
 and are not interpreted by Git.  Currently they must be encoded in
 UTF-8, as fast-import does not permit other encodings to be specified.
 
-Zero or more `filemodify`, `filedelete` and `filedeleteall` commands
+Zero or more `filemodify`, `filedelete`, `filename` and
+`filedeleteall` commands
 may be included to update the contents of the branch prior to
 creating the commit.  These commands may be supplied in any order.
 However it is recommended that a `filedeleteall` command preceed
-all `filemodify` commands in the same commit, as `filedeleteall`
+all `filemodify` and `filerename` commands in the same commit, as
+`filedeleteall`
 wipes the branch clean (see below).
 
 `author`
@@ -495,6 +497,26 @@ here `<path>` is the complete path of the file or subdirectory to
 be removed from the branch.
 See `filemodify` above for a detailed description of `<path>`.
 
+`filerename`
+^^^^^^^^^^^^
+Renames an existing file or subdirectory to a different location
+within the branch.  The existing file or directory must exist. If
+the destination exists it will be replaced by the source directory.
+
+....
+	'R' SP <path> SP <path> LF
+....
+
+here the first `<path>` is the source location and the second
+`<path>` is the destination.  See `filemodify` above for a detailed
+description of what `<path>` may look like.  To use a source path
+that contains SP the path must be quoted.
+
+A `filerename` command takes effect immediately.  Once the source
+location has been renamed to the destination any future commands
+applied to the source location will create new files there and not
+impact the destination of the rename.
+
 `filedeleteall`
 ^^^^^^^^^^^^^^^
 Included in a `commit` command to remove all files (and also all
fast-import.c +75 -16

180 lines not on this page · raw message

t/t9300-fast-import.sh +68 -0

72 lines not on this page · raw message

Signature · 1 line
1.5.3.rc0.879.g64b8
#2 lore raw

Re: [PATCH] Support wholesale directory renames in fast-import

Documentation/git-fast-import.txt commit message use a 0 length data. Commit messages are free-form · line 328

Quoted 2 lines · Shawn O. Pearce
Documentation/git-fast-import.txt +1 -1
-Zero or more `filemodify`, `filedelete` and `filedeleteall` commands
+Zero or more `filemodify`, `filedelete`, `filename` and

^^ filerename

Rogan

#3 lore raw

Re: [PATCH] Support wholesale directory renames in fast-import

Quoted 4 lines · Rogan Dawes

Documentation/git-fast-import.txt commit message use a 0 length data. Commit messages are free-form · line 328

Quoted 2 lines · Shawn O. Pearce
Documentation/git-fast-import.txt +1 -1
-Zero or more `filemodify`, `filedelete` and `filedeleteall` commands
+Zero or more `filemodify`, `filedelete`, `filename` and

^^ filerename

Ugh. Thanks. I just pushed out a corrected version.

Signature · 1 line
Shawn.
#4 lore raw

Re: [PATCH] Support wholesale directory renames in fast-import

In reply to Shawn O. Pearce

This should do nicely! Thank you!

Now my challenge is that the svn dump doesn't *actually* say "rename a/ to b/"; it says "copy a/ to b/; delete a/", so I have to infer the rename.

But your patch makes my import possible, and it wasn't before!

Cheers,

- David

Quoted 31 lines · Shawn O. Pearce

Some source material (e.g. Subversion dump files) perform directory renames without telling us exactly which files in that subdirectory were moved. This makes it hard for a frontend to convert such data formats to a fast-import stream, as all the frontend has on hand is "Rename a/ to b/" with no details about what files are in a/, unless the frontend also kept track of all files.

The new 'R' subcommand within a commit allows the frontend to rename either a file or an entire subdirectory, without needing to know the object's SHA-1 or the specific files contained within it. The rename is performed as efficiently as possible internally, making it cheaper than a 'D'/'M' pair for a file rename.

---

Quoted 9 lines · David Frech

Git can track file renames implicitly. If I delete and then add (under a different name) the same content, git will figure that out.

But if a directory was renamed, I have no way to tell fast-import about it. I can't delete the directory (using a 'D' command) and then add it back (with a different name) with all its contents, because my source material (an svn dump file) doesn't tell me, at that point, about all the files involved because nothing about them has changed.

Quoted 4 lines

fast-import knows about the contents of the directory I want to rename, but doesn't give me a primitive to do the rename. Is this something we need to add? My frontend could keep track of this, but I would duplicating work that fast-import is already doing.

Quoted 8 lines

Does the following do the trick for you? It is also available from my fastimport.git master branch:

git://repo.or.cz/git/fastimport.git master
http://repo.or.cz/r/git/fastimport.git master

Yes, it passes all tests...

[patch elided]

#5 lore raw

Re: [PATCH] Support wholesale directory renames in fast-import

Hallo David,

Quoted 3 lines · David Frech

Now my challenge is that the svn dump doesn't *actually* say "rename a/ to b/"; it says "copy a/ to b/; delete a/", so I have to infer the rename.

I don't know fast-import very well, but why not doing exactly what the dump file suggests: copy a b; delete a ?

Best regards
Uwe

Signature · 3 lines
Uwe Kleine-König

http://www.google.com/search?q=12+divided+by+3
#6 lore raw

Re: [PATCH] Support wholesale directory renames in fast-import

Quoted 7 lines · Uwe Kleine-K??nig
Quoted 3 lines · David Frech

Now my challenge is that the svn dump doesn't *actually* say "rename a/ to b/"; it says "copy a/ to b/; delete a/", so I have to infer the rename.

I don't know fast-import very well, but why not doing exactly what the dump file suggests: copy a b; delete a ?

Because there is no copy operator in fast-import. So you cannot do "copy a b". Apparently that's what I should have implemented, as rename in Git really is as simple as the copy/delete pair. Ugh.

Copy isn't really that hard, it just can't be nearly as efficient as rename, as copying a subtree will force me to either duplicate data in memory or reload trees from disk to duplicate data in memory. But its a copy, so data duplication is expected. ;-)

I'll implement a copy opertor soon. Shouldn't be too difficult. Maybe someone else would like to take a shot at implementing it...

Signature · 1 line
Shawn.
#7 lore raw

Re: [PATCH] Support wholesale directory renames in fast-import

Hmm. I think Uwe is right. Copy is probably the "right" primitive, and rename can always be synthesized from copy+delete.

Since Subversion is built around the idea of "cheap copies" there is no incentive for them to represent renames other than as "copy, then delete".

But isn't the same true in a way of git? If I copy a directory (a tree), then the new tree is the same tree - it has the same SHA-1 hash, so I can simply refer to the existing object. Same for file blobs.

Subversion dump files have *lots* of copies. Might be nice to be able to feed these directly into fast-import and have it DTRT, esp if it was smart about sharing identical data structures.

- David

Quoted 24 lines · Shawn O. Pearce
Quoted 7 lines · Uwe Kleine-K??nig
Quoted 3 lines · David Frech

Now my challenge is that the svn dump doesn't *actually* say "rename a/ to b/"; it says "copy a/ to b/; delete a/", so I have to infer the rename.

I don't know fast-import very well, but why not doing exactly what the dump file suggests: copy a b; delete a ?

Because there is no copy operator in fast-import. So you cannot do "copy a b". Apparently that's what I should have implemented, as rename in Git really is as simple as the copy/delete pair. Ugh.

Copy isn't really that hard, it just can't be nearly as efficient as rename, as copying a subtree will force me to either duplicate data in memory or reload trees from disk to duplicate data in memory. But its a copy, so data duplication is expected. ;-)

I'll implement a copy opertor soon. Shouldn't be too difficult. Maybe someone else would like to take a shot at implementing it...

--
Shawn.

Signature · 2 lines
If I have not seen farther, it is because I have stood in the
footsteps of giants.
#8 lore raw

Re: [PATCH] Support wholesale directory renames in fast-import

Quoted 7 lines · David Frech

Hmm. I think Uwe is right. Copy is probably the "right" primitive, and rename can always be synthesized from copy+delete.

Since Subversion is built around the idea of "cheap copies" there is no incentive for them to represent renames other than as "copy, then delete".

Quoted 8 lines

But isn't the same true in a way of git? If I copy a directory (a tree), then the new tree is the same tree - it has the same SHA-1 hash, so I can simply refer to the existing object. Same for file blobs.

Subversion dump files have *lots* of copies. Might be nice to be able to feed these directly into fast-import and have it DTRT, esp if it was smart about sharing identical data structures.

Yes. All of that is true. ;-)

I'm tired. I just worked an 18 hour day. I need to go do it all over again in about 4 hours. So I'm going to head off to bed. But I did manage to implement this (I think). Its totally untested. But feel free to poke at it:

git://repo.or.cz/git/fastimport.git copy-wip

I'll write documentation and unit tests tomorrow. And fix any bugs, if any get identified.

The implementation should copy as little memory as possible to do the actual copy. This should make a C/D pair about as efficient as an R command if the directory being copied has not yet been modified as part of the current commit (this is probably typical for an SVN dump file). The only difference should be a slight increase in running time for the C/D pair, as directory entry lookup in fast-import is O(n).

Oh, and as always, C works with both files and directories...

Hmm. Quickly reading this diff I can actually do it shorter with a bit of refactoring. I'll clean that up tomorrow night. I blame it on the lack of sleep that I'm suffering from right now. ;-)

-->8--
WIP Teach fast import how to copy

---
 fast-import.c |  121 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 120 insertions(+), 1 deletions(-)
fast-import.c +120 -1
index a1cb13f..41c0352 100644
@@ -26,10 +26,16 @@ Format of STDIN stream:
     lf;
   commit_msg ::= data;
 
-  file_change ::= file_clr | file_del | file_rnm | file_obm | file_inm;
+  file_change ::= file_clr
+    | file_del
+    | file_rnm
+    | file_cpy
+    | file_obm
+    | file_inm;
   file_clr ::= 'deleteall' lf;
   file_del ::= 'D' sp path_str lf;
   file_rnm ::= 'R' sp path_str sp path_str lf;
+  file_cpy ::= 'C' sp path_str sp path_str lf;
   file_obm ::= 'M' sp mode sp (hexsha1 | idnum) sp path_str lf;
   file_inm ::= 'M' sp mode sp 'inline' sp path_str lf
     data;
@@ -623,6 +629,33 @@ static void release_tree_entry(struct tree_entry *e)
 	avail_tree_entry = e;
 }
 
+static struct tree_content *dup_tree_content(struct tree_content *s)
+{
+	struct tree_content *d;
+	struct tree_entry *a, *b;
+	unsigned int i, j;
+
+	if (!s)
+		return NULL;
+	d = new_tree_content(s->entry_count);
+	for (i = 0, j = 0; i < s->entry_count; i++) {
+		a = s->entries[i];
+		if (a->versions[1].mode) {
+			b = new_tree_entry();
+			memcpy(b, a, sizeof(*a));
+			if (is_null_sha1(b->versions[1].sha1))
+				b->tree = dup_tree_content(b->tree);
+			else
+				b->tree = NULL;
+			d->entries[j++] = a;
+		}
+	}
+	d->entry_count = j;
+	d->delta_depth = s->delta_depth;
+
+	return d;
+}
+
 static void start_packfile(void)
 {
 	static char tmpfile[PATH_MAX];
@@ -1273,6 +1306,43 @@ del_entry:
 	return 1;
 }
 
+static int tree_content_get(
+	struct tree_entry *root,
+	const char *p,
+	struct tree_entry *leaf)
+{
+	struct tree_content *t = root->tree;
+	const char *slash1;
+	unsigned int i, n;
+	struct tree_entry *e;
+
+	slash1 = strchr(p, '/');
+	if (slash1)
+		n = slash1 - p;
+	else
+		n = strlen(p);
+
+	for (i = 0; i < t->entry_count; i++) {
+		e = t->entries[i];
+		if (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {
+			if (!slash1) {
+				memcpy(leaf, e, sizeof(*leaf));
+				if (is_null_sha1(e->versions[1].sha1))
+					leaf->tree = dup_tree_content(leaf->tree);
+				else
+					leaf->tree = NULL;
+				return 1;
+			}
+			if (!S_ISDIR(e->versions[1].mode))
+				return 0;
+			if (!e->tree)
+				load_tree(e);
+			return tree_content_get(e, slash1 + 1, leaf);
+		}
+	}
+	return 0;
+}
+
 static int update_branch(struct branch *b)
 {
 	static const char *msg = "fast-import";
@@ -1706,6 +1776,53 @@ static void file_change_r(struct branch *b)
 	free(d_uq);
 }
 
+static void file_change_c(struct branch *b)
+{
+	const char *s, *d;
+	char *s_uq, *d_uq;
+	const char *endp;
+	struct tree_entry leaf;
+
+	s = command_buf.buf + 2;
+	s_uq = unquote_c_style(s, &endp);
+	if (s_uq) {
+		if (*endp != ' ')
+			die("Missing space after source: %s", command_buf.buf);
+	}
+	else {
+		endp = strchr(s, ' ');
+		if (!endp)
+			die("Missing space after source: %s", command_buf.buf);
+		s_uq = xmalloc(endp - s + 1);
+		memcpy(s_uq, s, endp - s);
+		s_uq[endp - s] = 0;
+	}
+	s = s_uq;
+
+	endp++;
+	if (!*endp)
+		die("Missing dest: %s", command_buf.buf);
+
+	d = endp;
+	d_uq = unquote_c_style(d, &endp);
+	if (d_uq) {
+		if (*endp)
+			die("Garbage after dest in: %s", command_buf.buf);
+		d = d_uq;
+	}
+
+	memset(&leaf, 0, sizeof(leaf));
+	if (!tree_content_get(&b->branch_tree, s, &leaf))
+		die("Path %s not in branch", s);
+	tree_content_set(&b->branch_tree, d,
+		leaf.versions[1].sha1,
+		leaf.versions[1].mode,
+		leaf.tree);
+
+	free(s_uq);
+	free(d_uq);
+}
+
 static void file_change_deleteall(struct branch *b)
 {
 	release_tree_content_recursive(b->branch_tree.tree);
@@ -1875,6 +1992,8 @@ static void cmd_new_commit(void)
 			file_change_d(b);
 		else if (!prefixcmp(command_buf.buf, "R "))
 			file_change_r(b);
+		else if (!prefixcmp(command_buf.buf, "C "))
+			file_change_c(b);
 		else if (!strcmp("deleteall", command_buf.buf))
 			file_change_deleteall(b);
 		else
Signature · 5 lines
1.5.3.rc0.879.g64b8


-- 
Shawn.
#9 lore raw

Re: [PATCH] Support wholesale directory renames in fast-import

Quoted 9 lines · Shawn O. Pearce

I'm tired. I just worked an 18 hour day. I need to go do it all over again in about 4 hours. So I'm going to head off to bed. But I did manage to implement this (I think). Its totally untested. But feel free to poke at it:

git://repo.or.cz/git/fastimport.git copy-wip

I'll write documentation and unit tests tomorrow. And fix any bugs, if any get identified.

Shawn, don't knock yourself out. ;-)

I think getting the semantics right (of the command set in fast-import) is important, but it doesn't have to be right *yesterday*. I won't need to point my command stream at fast-import for at least another day or two. ;-) I have some subtle code to write first that'll take me a bit to get right...

Thanks for your enthusiasm though!

Cheers,

- David

Quoted 3 lines

--
Shawn.

Signature · 2 lines
If I have not seen farther, it is because I have stood in the
footsteps of giants.