[PATCH 1/4] Implement normalize_absolute_path

[PATCH 1/4] Implement normalize_absolute_path

[David Reiss]

normalize_absolute_path removes several oddities form absolute paths,
giving nice clean paths like "/dir/sub1/sub2".  Also add a test case
for this utility, based on a new test program (in the style of test-sha1).

Signed-off-by: David Reiss <dreiss@facebook.com>
---
Junio thought it would be good to do normalization of paths in the
GIT_CEILING_DIRECTORIES patch.  This function does the normalization.

The closest thing I could find to this in the existing code base was
sanitary_path_copy, but it does not remove trailing slashes.

If this test suite takes too long to run, I'm fine with commenting
most of it out.

 .gitignore            |    1 +
 Makefile              |    2 +-
 cache.h               |    1 +
 path.c                |   50 +++++++++++++++++++++++++++++++++++++++++++++++++
 t/t0060-path-utils.sh |   40 +++++++++++++++++++++++++++++++++++++++
 test-path-utils.c     |   13 ++++++++++++
 6 files changed, 106 insertions(+), 1 deletions(-)
 create mode 100755 t/t0060-path-utils.sh
 create mode 100644 test-path-utils.c

diff --git a/.gitignore b/.gitignore
index 4ff2fec..c54c473 100644
--- a/.gitignore
+++ b/.gitignore
@@ -150,6 +150,7 @@ test-dump-cache-tree
 test-genrandom
 test-match-trees
 test-parse-options
+test-path-utils
 test-sha1
 common-cmds.h
 *.tar.gz
diff --git a/Makefile b/Makefile
index 649ee56..d76c16b 100644
--- a/Makefile
+++ b/Makefile
@@ -1182,7 +1182,7 @@ endif
 
 ### Testing rules
 
-TEST_PROGRAMS = test-chmtime$X test-genrandom$X test-date$X test-delta$X test-sha1$X test-match-trees$X test-absolute-path$X test-parse-options$X
+TEST_PROGRAMS = test-chmtime$X test-genrandom$X test-date$X test-delta$X test-sha1$X test-match-trees$X test-absolute-path$X test-parse-options$X test-path-utils$X
 
 all:: $(TEST_PROGRAMS)
 
diff --git a/cache.h b/cache.h
index 9cee9a5..5fd1e5b 100644
--- a/cache.h
+++ b/cache.h
@@ -514,6 +514,7 @@ static inline int is_absolute_path(const char *path)
 	return path[0] == '/';
 }
 const char *make_absolute_path(const char *path);
+int normalize_absolute_path(char *buf, const char *path);
 
 /* Read and unpack a sha1 file into memory, write memory to a sha1 file */
 extern int sha1_object_info(const unsigned char *, unsigned long *);
diff --git a/path.c b/path.c
index b7c24a2..17921ac 100644
--- a/path.c
+++ b/path.c
@@ -357,3 +357,53 @@ const char *make_absolute_path(const char *path)
 
 	return buf;
 }
+
+/*
+ * path = absolute path
+ * buf = buffer of at least max(2, strlen(path)+1) bytes
+ * It is okay if buf == path, but they should not overlap otherwise.
+ *
+ * Performs the following normalizations on path, storing the result in buf:
+ * - Removes trailing slashes.
+ * - Removes empty components.
+ * - Removes "." components.
+ * - Removes ".." components, and the components the precede them.
+ * "" and paths that contain only slashes are normalized to "/".
+ * Returns the length of the output.
+ *
+ * Note that this function is purely textual.  It does not follow symlinks,
+ * verify the existence of the path, or make any system calls.
+ */
+int normalize_absolute_path(char *buf, const char *path)
+{
+	const char *comp_start = path, *comp_end = path;
+	char *dst = buf;
+	int comp_len;
+	assert(buf);
+	assert(path);
+
+	while (*comp_start) {
+		while (*++comp_end && *comp_end != '/');
+		comp_len = comp_end - comp_start;
+
+		if (!strncmp("/",  comp_start, comp_len) ||
+		    !strncmp("/.", comp_start, comp_len))
+			goto next;
+
+		if (!strncmp("/..", comp_start, comp_len)) {
+			while (dst > buf && *--dst != '/');
+			goto next;
+		}
+
+		memcpy(dst, comp_start, comp_len);
+		dst += comp_len;
+	next:
+		comp_start = comp_end;
+	}
+
+	if (dst == buf)
+		*dst++ = '/';
+
+	*dst = '\0';
+	return dst - buf;
+}
diff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh
new file mode 100755
index 0000000..9076b3b
--- /dev/null
+++ b/t/t0060-path-utils.sh
@@ -0,0 +1,40 @@
+#!/bin/sh
+#
+# Copyright (c) 2008 David Reiss
+#
+
+test_description='Test various path utilities'
+
+. ./test-lib.sh
+
+norm_abs() {
+	test_expect_success "normalize absolute" \
+	"test \$(test-path-utils normalize_absolute_path '$1') = '$2'"
+}
+
+norm_abs "" /
+norm_abs / /
+norm_abs // /
+norm_abs /// /
+norm_abs /. /
+norm_abs /./ /
+norm_abs /./.. /
+norm_abs /../. /
+norm_abs /./../.// /
+norm_abs /dir/.. /
+norm_abs /dir/sub/../.. /
+norm_abs /dir /dir
+norm_abs /dir// /dir
+norm_abs /./dir /dir
+norm_abs /dir/. /dir
+norm_abs /dir///./ /dir
+norm_abs /dir//sub/.. /dir
+norm_abs /dir/sub/../ /dir
+norm_abs //dir/sub/../. /dir
+norm_abs /dir/s1/../s2/ /dir/s2
+norm_abs /d1/s1///s2/..//../s3/ /d1/s3
+norm_abs /d1/s1//../s2/../../d2 /d2
+norm_abs /d1/.../d2 /d1/.../d2
+norm_abs /d1/..././../d2 /d1/d2
+
+test_done
diff --git a/test-path-utils.c b/test-path-utils.c
new file mode 100644
index 0000000..1bd4321
--- /dev/null
+++ b/test-path-utils.c
@@ -0,0 +1,13 @@
+#include "cache.h"
+
+int main(int argc, char **argv)
+{
+	if (argc == 3 && !strcmp(argv[1], "normalize_absolute_path")) {
+		char *buf = xmalloc(strlen(argv[2])+1);
+		int rv = normalize_absolute_path(buf, argv[2]);
+		assert(strlen(buf) == rv);
+		puts(buf);
+	}
+
+	return 0;
+}
-- 
1.5.4

Re: [PATCH 1/4] Implement normalize_absolute_path

[Johannes Schindelin]

Hi,

On Mon, 19 May 2008, David Reiss wrote:

> normalize_absolute_path removes several oddities form absolute paths, 
> giving nice clean paths like "/dir/sub1/sub2".  Also add a test case for 
> this utility, based on a new test program (in the style of test-sha1).

I wonder why my advice to look at setup.c (I think I did not mention the 
function name "sanitary_path_copy()" in particular, because I figured you 
would spot it right away) went unheeded.

So I think I will not even bother to look at your patches either.

Ciao,
Dscho

Re: [PATCH 1/4] Implement normalize_absolute_path

[David Reiss]

> I wonder why my advice to look at setup.c (I think I did not mention the
> function name "sanitary_path_copy()" in particular, because I figured you
> would spot it right away) went unheeded.

I wonder why my comment in the patch went unheeded:
> The closest thing I could find to this in the existing code base was
> sanitary_path_copy, but it does not remove trailing slashes.

Honestly, I found it quite daunting to try to track down all of the
indirect callers of sanitary_path_copy and ensure that they would
continue to work if I changed the behavior of a function that does not
document what it is supposed to do.  Frankly, it would be easier for me
to just keep rebasing my patches and apply them to my local builds.

--David

Re: [PATCH 1/4] Implement normalize_absolute_path

[Alex Riesen]

David Reiss, Tue, May 20, 2008 08:48:54 +0200:
> normalize_absolute_path removes several oddities form absolute paths,
> giving nice clean paths like "/dir/sub1/sub2".  Also add a test case
> for this utility, based on a new test program (in the style of test-sha1).

Heh...
http://thread.gmane.org/gmane.comp.version-control.git/68786/focus=68812

The test of the function has these cases:

static void check(const char *cwd, const char *path, const char *good);

int main(int argc, char **argv)
{
	/* 1 */ check("/onelevel", "aa", "onelevel/aa");
	/* 2 */ check("/", "..", "");
	/* 3 */ check("/", "../..", "");
	/* 4 */ check("/one", "aa/../bb", "one/bb");
	/* 5 */ check("/one/two", "aa//bb", "one/two/aa/bb");
	/* 6 */ check("", "/aa//bb", "aa/bb");
	/* 7 */ check("/one/two", "", "one/two");
	/* 8 */ check("/one/two", "aa/..bb/x/../cc/", "one/two/aa/..bb/cc");
	/* 9 */ check("/one/two", "aa/x/././cc////", "one/two/aa/x/cc");
	/* 10 */ check("/one/two", "../../../../aa", "aa");
	/* 11 */ check("one/", "../one/two", "one/two");
	/* 12 */ check("", "../../two", "two");
	/* 13 */ check("a/b/c", "../../two", "a/two");
	/* 14 */ check("a/b/", "../two", "a/two");
	/* 15 */ check("///", "../two", "two");
	return 0;
}

static void check(const char *cwd, const char *path, const char *good)
{
	static int n = 0;
	printf("%-2d: %10s$ cd %s", ++n, cwd, path);
	char *t = pathexpand(cwd, path);
	if ( strcmp(t, good) )
		printf(" ____________________failed(%s)\n", t);
	else
		printf(" \033[32m%s\033[0m\n", t);
	free(t);
}

Re: [PATCH 1/4] Implement normalize_absolute_path

[David Reiss]

This is close enough to what I want that I could definitely use it if it
were in the main tree.  I read through most of that thread, but I
couldn't figure out what ever happened to your patch.  (I couldn't find
a clear rejection, but I also don't see it in master.)

--David

Alex Riesen wrote:
> David Reiss, Tue, May 20, 2008 08:48:54 +0200:
>> normalize_absolute_path removes several oddities form absolute paths,
>> giving nice clean paths like "/dir/sub1/sub2".  Also add a test case
>> for this utility, based on a new test program (in the style of test-sha1).
> 
> Heh...
> http://thread.gmane.org/gmane.comp.version-control.git/68786/focus=68812
> 
> The test of the function has these cases:
> 
> static void check(const char *cwd, const char *path, const char *good);
> 
> int main(int argc, char **argv)
> {
>         /* 1 */ check("/onelevel", "aa", "onelevel/aa");
>         /* 2 */ check("/", "..", "");
>         /* 3 */ check("/", "../..", "");
>         /* 4 */ check("/one", "aa/../bb", "one/bb");
>         /* 5 */ check("/one/two", "aa//bb", "one/two/aa/bb");
>         /* 6 */ check("", "/aa//bb", "aa/bb");
>         /* 7 */ check("/one/two", "", "one/two");
>         /* 8 */ check("/one/two", "aa/..bb/x/../cc/", "one/two/aa/..bb/cc");
>         /* 9 */ check("/one/two", "aa/x/././cc////", "one/two/aa/x/cc");
>         /* 10 */ check("/one/two", "../../../../aa", "aa");
>         /* 11 */ check("one/", "../one/two", "one/two");
>         /* 12 */ check("", "../../two", "two");
>         /* 13 */ check("a/b/c", "../../two", "a/two");
>         /* 14 */ check("a/b/", "../two", "a/two");
>         /* 15 */ check("///", "../two", "two");
>         return 0;
> }
> 
> static void check(const char *cwd, const char *path, const char *good)
> {
>         static int n = 0;
>         printf("%-2d: %10s$ cd %s", ++n, cwd, path);
>         char *t = pathexpand(cwd, path);
>         if ( strcmp(t, good) )
>                 printf(" ____________________failed(%s)\n", t);
>         else
>                 printf(" \033[32m%s\033[0m\n", t);
>         free(t);
> }
> 
> 

Re: [PATCH 1/4] Implement normalize_absolute_path

[Alex Riesen]

David Reiss, Wed, May 21, 2008 10:34:17 +0200:
> This is close enough to what I want that I could definitely use it if it
> were in the main tree.  I read through most of that thread, but I
> couldn't figure out what ever happened to your patch.  (I couldn't find
> a clear rejection, but I also don't see it in master.)

Me too. OTOH, it was not a clear proposal for inclusion.