#define _GNU_SOURCE
#include <stdlib.h>
#include <limits.h>
#include <errno.h>
#include <unistd.h>
#include <string.h>

static inline int at_dotdot(const char *end, size_t len)
{
	if (len<2) return 0;
	if (len>2 && end[-3]!='/') return 0;
	return end[-1]=='.' && end[-2]=='.';
}

char *realpath(const char *restrict filename, char *restrict resolved)
{
	char stack[PATH_MAX];
	char buf[resolved ? 1 : PATH_MAX];
	char *output = resolved ? resolved : buf;
	size_t p, q, l, cnt=0;

	l = strnlen(filename, sizeof stack + 1);
	if (!l) {
		errno = ENOENT;
		return 0;
	}
	if (l >= sizeof stack) goto toolong;
	p = sizeof stack - l - 1;
	q = 0;
	memcpy(stack+p, filename, l+1);

	while (stack[p]) {
		int up = 0;
		if (stack[p] == '/') {
			q=0;
			output[q++] = '/';
			p++;
			/* Initial // is special. */
			if (stack[p] == '/' && stack[p+1] != '/') {
				output[q++] = '/';
			}
			while (stack[p] == '/') p++;
			continue;
		}
		char *z = __strchrnul(stack+p, '/');
		l = z-(stack+p);
		if (l==1 && stack[p]=='.') {
			p += l;
			while (stack[p] == '/') p++;
			continue;
		}
		if (at_dotdot(stack+p+l, l)) {
			if (q && !at_dotdot(output+q, q)) {
				while(q && output[q-1]!='/') q--;
				if (q>1 && (q>2 || output[0]!='/')) q--;
				p += l;
				while (stack[p] == '/') p++;
				continue;
			}
			up = 1;
		}
		if (q && output[q-1] != '/') {
			if (!p) goto toolong;
			stack[--p] = '/';
			l++;
		}
		if (q+l >= PATH_MAX) goto toolong;
		memcpy(output+q, stack+p, l);
		output[q+l] = 0;
		p += l;
		if (up) goto notlink;
		ssize_t k = readlink(output, stack, p);
		if (k==-1) {
			if (errno == EINVAL) {
notlink:
				q += l;
				while (stack[p] == '/') p++;
				continue;
			}
			return 0;
		}
		if (k==p) goto toolong;
		if (++cnt == SYMLOOP_MAX) {
			errno = ELOOP;
			return 0;
		}
		p -= k;
		memmove(stack+p, stack, k);
	}

	output[q] = 0;

	if (output[0] != '/') {
		if (!getcwd(stack, sizeof stack)) return 0;
		l = strlen(stack);
		/* Cancel any initial .. components. */
		p = 0;
		while (q-p>=2 && at_dotdot(output+p+2, p+2)) {
			while(l>1 && stack[l-1]!='/') l--;
			if (l>1) l--;
			p += 2;
			if (p<q) p++;
		}
		if (q-p && stack[l-1]!='/') output[--p] = '/';
		if (l + (q-p) + 1 >= PATH_MAX) goto toolong;
		memmove(output + l, output + p, q - p + 1);
		memcpy(output, stack, l);
	}

	return resolved ? resolved : strdup(output);

toolong:
	errno = ENAMETOOLONG;
	return 0;
}