#include <stdio.h>

#ifdef TEST_PROGRAM
#include <stdlib.h>
#include <unistd.h>
#include <err.h>
#define _GNU_SOURCE
#define __USE_GNU
#endif
#include <string.h>

#include "canonicalize.h"

/*
 * This routine is written with the assumption that
 * the library string functions will be faster than
 * trying to do a character-by-character search.
 *
 * It also assumes that using memmove() will be
 * faster, so even if we have multiple hits on a path
 * and have to call it multiple times, overall things
 * will still be faster.
 */
void canonicalize(char * filename)
{
	char *p1, *p2, *ep = NULL;
	char c;

	/*
	 * Strip out all multiple slashes, and then we
	 * won't have to worry about them again.
	 */
	if ((p1 = strstr(filename, "//")) != NULL) {
		ep = strchr(p1, '\0') + 1;

		do {
			for (p2 = ++p1 + 1; *p2 == '/'; p2++)
				continue;
			memmove(p1, p2, ep - p2);
			ep -= (p2 - p1);
		} while ((p1 = strstr(p1, "//")) != NULL);
	}

	p1 = filename;

	/* Now we search for "." and ".." in the path. */
	for (;;) {
		if ((p1 = strstr(p1, "/.")) == NULL)
			return;

		/* Check for: "/..", "/./" and "/.\000" */
		if ((c = *(p1+2)) != '.' && c != '/') {
			if (c == '\0') {
				*p1 = '\0';
				return;
			}
			p1 += 3;
			continue;
		}

		if (c == '/') {
			if (ep == NULL)
				ep = strchr(p1 + 2, '\0') + 1;
			ep -= 2;
			memmove(p1, p1 + 2, ep - p1);
			continue;
		}

		/* At this point, p1 is pointing at "/.." */
		if ((c = *(p1+3)) != '/' && (c != '\0')) {
			p1 += 4;
			continue;
		}

		/*
		 * If the previous component is the first
		 * component, and equal to '.', don't strip
		 */
		if (p1 == filename + 1 && *filename == '.') {
			p1 += 4;
			continue;
		}

		/* Don't strip out if previous component is ".." */
		if (((p1 - filename) >= 2) &&
		    *(p1-1) == '.' &&
		    *(p1-2) == '.' &&
		    ((p1 - filename == 2) || *(p1-3) == '/')) {
			p1 +=4;
			continue;
		}

		/*
		 * Ok, strip out prev/..
		 * Back up p1 over the previous component, leaving
		 * it pointing at the slash, and backup p2 by one
		 * so that it is pointing at the slash/null.
		 */
		p2 = p1 + 3;
		while (p1 > filename && *--p1 != '/')
			continue;
		if (ep == NULL)
			ep = strchr(p2, '\0') + 1;
		memmove(p1, p2, ep - p2);
		ep -= p2 - p1;
	}
}


#ifdef TEST_PROGRAM
/*
 * This is a set of test path strings with the
 * expected result after being canonicalized.
 */
struct tests {
        char *test;
        char *ans;
} tests[] = {
	{ "./skip../../one", "./one" },
	{ "./../one/./two/./three", "./../one/two/three" },
	{ "/one/two/three", "/one/two/three" },
	{ "///one/two/three", "/one/two/three" },
	{ "/../one/two/three", "/one/two/three" },
	{ "///..///../one///skip/../two", "/one/two" },
	{ "/one/skip/../three", "/one/three" },
	{ "/one/skip1/skip2/../../two/three", "/one/two/three" },
	{ "//one/skip1//..//two/three", "/one/two/three" },
	{ "../one/two", "../one/two" },
	{ "../../one/two", "../../one/two" },
	{ "/one/./two/./three", "/one/two/three" },
	{ "./one/./two/./three", "./one/two/three" },
	{ ".././../one/./two/./three", "../../one/two/three" },
	{ "/a/b/../../../c/d", "/c/d" },
	{ "/one/two/..three/four", "/one/two/..three/four" },
	{ 0 }
};

char *input_file = NULL;
int internal_tests = 0;
int quiet_flag;

int
verify(char *strp, char *ans)
{
	int len;

	len = (int)strlen(strp) + 3;

	if (!quiet_flag)
		printf("%s -> ", strp);
	canonicalize(strp);
	if (!quiet_flag)
		printf("%s\n", strp);
	if (ans && strcmp(strp, ans) != 0) {
		if (!quiet_flag)
			printf("%*s %s\n", len, "EXPECTED ->", ans);
		return(0);
	}
	return(1);
}

void
usage()
{
	fprintf(stderr, "Usage: canonicalize [-iq] [-f input_file]\n");
	exit(1);
}

int
main(int argc, char **argv)
{
	int failed = 0;
	int parsed = 0;
	struct tests *tp;
	char tbuf[1024];
	char *test, *ans;
        int opt;
	char *ep;
	FILE *fd;

        while ((opt = getopt(argc, argv, "if:q")) != -1) {
                switch (opt) {
		case 'i':
			++internal_tests;
			break;
                case 'f':
                        input_file = optarg;
                        break;
		case 'q':
			quiet_flag++;
			break;
                default:
			usage();
                        /* NOT_REACHED */
                }
        }

	if (input_file) {
		if ((fd = fopen(input_file, "r")) == NULL) {
			err(1, "%s", input_file);
			/* NOT_REACHED */
		}
		while (fgets(tbuf, sizeof(tbuf), fd) != NULL) {
			/* Make sure it's null terminated */
			tbuf[sizeof(tbuf)-1] = '\0';
			test = tbuf;
			while (*test == ' ' || *test == '\t')
				test++;

			/* Find the (optional) expected answer */
			ans = strchrnul(test, ' ');
			if (*ans == '\0')
				ans = strchrnul(test, '\t');
			if (*ans != '\0') {
				*ans++ = '\0';
				while (*ans == ' ' || *ans == '\t')
					ans++;
				ep = strchrnul(ans, '\n');
			} else {
				ep = ans - 1;
				ans = NULL;
			}
			/* Strip off the trailing \n */
			if (*ep == '\n')
				*ep-- = '\0';
			if (*test == '\0')
				continue;
			parsed++;
			if (!verify(test, ans))
				failed++;
		}
	} else
		internal_tests++;

	if (internal_tests) {
		for (tp = tests; tp->test; tp++) {
			strncpy(tbuf, tp->test, sizeof(tbuf));
			parsed++;
			if (!verify(tbuf, tp->ans))
				failed++;
		}
	}

	printf("%d paths parsed\n", parsed);
	if (failed)
		printf("%d FAILURES\n", failed);
	exit(0);
}

#endif