#include <sys/stat.h>
#include <linux/limits.h>
#include <sys/types.h>
#include <dirent.h>
#include <fcntl.h>
#include <unistd.h>

#include <errno.h>
#include <string.h>
#include <stdio.h>
#include <stdbool.h>

static bool show_hidden = false;

static void glob_r(int fd, char *buf, size_t off, size_t cap, const char *pat);

static bool
append(char *path, const char *component, size_t *len, size_t cap, size_t off, bool final)
{
	if (*len + !final + 1 > cap - off) {
		fprintf(stderr, "glob: len > PATH_MAX\n");
		return false;
	}
	strncpy(path + off, component, *len);
	while (*len > 0 && path[off+*len-1] == '/')
		(*len)--;
	if (!final) path[off+(*len)++] = '/';
	path[off+*len] = '\0';
	return true;
}

static int
opendirat(int pfd, const char *full, const char *child)
{
	int fd = openat(pfd, child, O_DIRECTORY);
	if (fd < 0) {
		fprintf(stderr, "glob: openat '%s': %s\n",
			full, strerror(errno));
		return -1;
	}
	return fd;
}

static bool
esc_strcmp(const char **esc, const char **str, const char *except)
{
	const char *e, *s;

	for (e = *esc, s = *str; *s && *e; s++, e++) {
		if (*e == '\\') e++;
		else if (strchr(except, *e)) return true;
		if (*s != *e) return false;
	}
	*esc = e;
	*str = s;

	return (!*s && !*e) || strchr(except, *e);
}

static bool
esc_strstr(const char **esc, const char **str, const char *except)
{
	for (; **str; (*str)++) {
		if (esc_strcmp(esc, str, except))
			return true;
	}

	return false;
}

static bool
match(const char *pat, const char *str)
{
	const char *p;

	p = pat;
	while (1) {
		if (p == pat) {
			if (!esc_strcmp(&p, &str, "*/"))
				return false;
		} else {
			if (!esc_strstr(&p, &str, "*/"))
				return false;
		}
		if (*p == '/' || !*p)
			break;
		p += 1;
	}

	return true;
}

static bool
addprefix(char *buf, const char *pat, size_t cap,
	size_t off, size_t *consumed, size_t *added)
{
	const char *slash;
	const char *star;
	const char *tok;
	size_t len;

	*added = *consumed = 0;

	star = strchr(pat, '*');
	if (!star) {
		*consumed = *added = strlen(pat);
		return append(buf, pat, added, cap, off, true);
	}

	slash = strchr(pat, '/');
	if (!slash || slash > star)
		return true;

	tok = pat;
	do {
		len = (size_t) (slash + 1 - tok);
		*consumed += len;
		if (slash == pat || len > 1) {
			if (!append(buf, tok, &len, cap, off + *added, !slash))
				return false;
			*added += len;
		}
		tok = slash + 1;
		slash = strchr(slash + 1, '/');
	} while (slash && slash < star);

	return true;
}

static void
glob_r_match(int fd, char *buf, size_t off, size_t cap, const char *pat)
{
	const char *slash;
	struct dirent *ent;
	DIR *d;
	size_t len;
	int sfd;

	if (!(d = fdopendir(fd))) {
		fprintf(stderr, "glob: opendir '%s': %s\n",
			*buf ? buf : ".", strerror(errno));
		return;
	}

	slash = strchr(pat, '/');
	while ((ent = readdir(d))) {
		if (!strcmp(ent->d_name, ".")) continue;
		if (!strcmp(ent->d_name, "..")) continue;

		if (*ent->d_name == '.' && !show_hidden) continue;

		if (!match(pat, ent->d_name)) continue;

		if (slash && ent->d_type == DT_DIR) {
			len = strlen(ent->d_name);
			if (!append(buf, ent->d_name, &len, cap, off, false))
				continue;
			if ((sfd = opendirat(fd, buf, ent->d_name)) < 0)
				continue;
			glob_r(sfd, buf, off + len, cap, slash + 1);
			close(sfd);
		} else if (!slash) {
			len = strlen(ent->d_name);
			if (!append(buf, ent->d_name, &len, cap, off, true))
				continue;
			puts(buf);
		}
	}

	closedir(d);
}

static void
glob_r(int fd, char *buf, size_t off, size_t cap, const char *pat)
{
	struct stat stat;
	size_t plen;
	size_t len;
	int sfd;

	if (!addprefix(buf, pat, cap, off, &plen, &len))
		return;

	if (len) {
		if (!pat[plen]) {
			if (!fstatat(fd, buf + off, &stat, 0)) {
				puts(buf);
			}
		} else {
			if ((sfd = opendirat(fd, buf, buf + off)) < 0)
				return;
			glob_r_match(sfd, buf, off + len, cap, pat + plen);
			close(sfd);
		}
	} else {
		glob_r_match(fd, buf, off, cap, pat + plen);
	}
}

static void
glob(char *pat)
{
	char buf[PATH_MAX];
	char *end;

	buf[0] = '\0';

	end = pat + strlen(pat);
	while (end > pat && end[-1] == '/')
		end--;
	*end = '\0';

	glob_r(AT_FDCWD, buf, 0, PATH_MAX, pat);
}

int
main(int argc, char **argv)
{
	char **arg;

	if (!argc) return 1;

	for (arg = argv + 1; *arg; arg++) {
		if (!strcmp(*arg, "-h")) {
			printf("Usage: glob [-h] [-a]\n");
			return 0;
		} else if (!strcmp(*arg, "-a")) {
			show_hidden = true;
		} else {
			if (!strcmp(*arg, "--")) arg++;
			break;
		}
	}

	for (; *arg; arg++) glob(*arg);
}