#include <glob.h>
#include <fnmatch.h>
#include <sys/stat.h>
#include <dirent.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <stddef.h>
#include "libc.h"
#include <stdbool.h>
#include <pwd.h>
#include <unistd.h>

struct match
{
	struct match *next;
	char name[1];
};

static int is_literal(const char *p, int useesc)
{
	int bracket = 0;
	for (; *p; p++) {
		switch (*p) {
		case '\\':
			if (!useesc) break;
		case '?':
		case '*':
			return 0;
		case '[':
			bracket = 1;
			break;
		case ']':
			if (bracket) return 0;
			break;
		}
	}
	return 1;
}

static int append(struct match **tail, const char *name, size_t len, int mark)
{
	struct match *new = malloc(sizeof(struct match) + len + 1);
	if (!new) return -1;
	(*tail)->next = new;
	new->next = NULL;
	strcpy(new->name, name);
	if (mark) strcat(new->name, "/");
	*tail = new;
	return 0;
}

static int match_in_dir(const char *d, const char *p, int flags, int (*errfunc)(const char *path, int err), struct match **tail)
{
	DIR *dir;
	struct dirent de_buf, *de;
	char pat[strlen(p)+1];
	char *p2;
	size_t l = strlen(d);
	int literal;
	int fnm_flags= ((flags & GLOB_NOESCAPE) ? FNM_NOESCAPE : 0)
		| ((!(flags & GLOB_PERIOD)) ? FNM_PERIOD : 0);
	int error;

	if ((p2 = strchr(p, '/'))) {
		strcpy(pat, p);
		pat[p2-p] = 0;
		for (; *p2 == '/'; p2++);
		p = pat;
	}
	literal = is_literal(p, !(flags & GLOB_NOESCAPE));
	if (*d == '/' && !*(d+1)) l = 0;

	/* rely on opendir failing for nondirectory objects */
	dir = opendir(*d ? d : ".");
	error = errno;
	if (!dir) {
		/* this is not an error -- we let opendir call stat for us */
		if (error == ENOTDIR) return 0;
		if (error == EACCES && !*p) {
			struct stat st;
			if (!stat(d, &st) && S_ISDIR(st.st_mode)) {
				if (append(tail, d, l, l))
					return GLOB_NOSPACE;
				return 0;
			}
		}
		if (errfunc(d, error) || (flags & GLOB_ERR))
			return GLOB_ABORTED;
		return 0;
	}
	if (!*p) {
		error = append(tail, d, l, l) ? GLOB_NOSPACE : 0;
		closedir(dir);
		return error;
	}
	while (!(error = readdir_r(dir, &de_buf, &de)) && de) {
		char namebuf[l+de->d_reclen+2], *name = namebuf;
		if (!literal && fnmatch(p, de->d_name, fnm_flags))
			continue;
		if (literal && strcmp(p, de->d_name))
			continue;
		if (p2 && de->d_type && !S_ISDIR(de->d_type<<12) && !S_ISLNK(de->d_type<<12))
			continue;
		if (*d) {
			memcpy(name, d, l);
			name[l] = '/';
			strcpy(name+l+1, de->d_name);
		} else {
			name = de->d_name;
		}
		if (p2) {
			if ((error = match_in_dir(name, p2, flags, errfunc, tail))) {
				closedir(dir);
				return error;
			}
		} else {
			int mark = 0;
			if (flags & GLOB_MARK) {
				if (de->d_type && !S_ISLNK(de->d_type<<12))
					mark = S_ISDIR(de->d_type<<12);
				else {
					struct stat st;
					stat(name, &st);
					mark = S_ISDIR(st.st_mode);
				}
			}
			if (append(tail, name, l+de->d_reclen+1, mark)) {
				closedir(dir);
				return GLOB_NOSPACE;
			}
		}
	}
	closedir(dir);
	if (error && (errfunc(d, error) || (flags & GLOB_ERR)))
		return GLOB_ABORTED;
	return 0;
}

static int ignore_err(const char *path, int err)
{
	return 0;
}

static void freelist(struct match *head)
{
	struct match *match, *next;
	for (match=head->next; match; match=next) {
		next = match->next;
		free(match);
	}
}

static int sort(const void *a, const void *b)
{
	return strcmp(*(const char **)a, *(const char **)b);
}

#include <stdint.h>
#define GLOB_STRLCPY_ALIGN (sizeof(size_t)-1)
#define GLOB_STRLCPY_ONES ((size_t)-1/UCHAR_MAX)
#define GLOB_STRLCPY_HIGHS (GLOB_STRLCPY_ONES * (UCHAR_MAX/2+1))
#define GLOB_STRLCPY_HASZERO(x) ((x)-GLOB_STRLCPY_ONES & ~(x) & GLOB_STRLCPY_HIGHS)

size_t glob_strlcpy(char *d, const char *s, size_t n)
{
	char *d0 = d;
	size_t *wd;
	const size_t *ws;

	if (!n--) goto finish;
	if (((uintptr_t)s & GLOB_STRLCPY_ALIGN) == ((uintptr_t)d & GLOB_STRLCPY_ALIGN)) {
		for (; ((uintptr_t)s & GLOB_STRLCPY_ALIGN) && n && (*d=*s); n--, s++, d++);
		if (n && *s) {
			wd=(void *)d; ws=(const void *)s;
			for (; n>=sizeof(size_t) && !GLOB_STRLCPY_HASZERO(*ws);
			       n-=sizeof(size_t), ws++, wd++) *wd = *ws;
			d=(void *)wd; s=(const void *)ws;
		}
	}
	for (; n && (*d=*s); n--, s++, d++);
	*d = 0;
finish:
	return d-d0 + strlen(s);
}

static size_t glob_strlcat(char *d, const char *s, size_t n)
{
	size_t l = strnlen(d, n);
	if (l == n) return l + strlen(s);
	return l + glob_strlcpy(d+l, s, n-l);
}



/*"~" or "~/(...)" case*/
static bool expand_tilde_cur_user(const char *pat_after_tilde, char *new_pat, size_t new_pat_size)
{
	char *home;
	struct passwd pw_store, *pw_result;
	char pw_buf[1024];

	/*FIXME: add check for issetugid as in libc of openbsd?*/
	home = getenv("HOME");
	if(home == NULL) {
		getpwuid_r(getuid(), &pw_store, pw_buf, sizeof(pw_buf), &pw_result);
		if(pw_result == NULL) {
			return false;
		}
		home = pw_store.pw_dir;
	}

	return glob_strlcpy(new_pat, home, new_pat_size) < new_pat_size
		&& glob_strlcat(new_pat, pat_after_tilde, new_pat_size) < new_pat_size;
}

/* "~user/(...) case*/
static bool expand_tilde_named_user(const char *pat_after_tilde, char *new_pat, size_t new_pat_size)
{
	struct passwd pw_store, *pw_result;
	char pw_buf[1024], username[1024];
	const char *slash_pos = strchr(pat_after_tilde, '/');
	if(slash_pos == NULL) {
		return false;
	}

	ptrdiff_t pat_username_size = slash_pos - pat_after_tilde;
	if(pat_username_size <= 0 || pat_username_size >= sizeof(username)) {
		return false;
	}
	strncpy(username, pat_after_tilde, pat_username_size);
	username[pat_username_size] = '\0';

	getpwnam_r(username, &pw_store, pw_buf, sizeof(pw_buf), &pw_result);
	if (pw_result == NULL)
		return false;

	return glob_strlcpy(new_pat, pw_store.pw_dir, new_pat_size) < new_pat_size
		&& glob_strlcat(new_pat, slash_pos, new_pat_size) < new_pat_size;
}

/* expands:
 *  ~ into /home/user/
 *  ~/asd into /home/user/asd
 *  ~user1/asd into /home/user1/asd
 * the values for the home directory are taken from passwd
 *
 * returning true means successful expansion and that expanded_pat is valid
 */
static bool expand_tilde(const char *pat, char *new_pat, int new_pat_size)
{
	const char *pat_after_tilde = pat + 1;
	if(*pat_after_tilde == '\0' || *pat_after_tilde == '/') {
		return expand_tilde_cur_user(pat_after_tilde, new_pat, new_pat_size);
	} else {
		return expand_tilde_named_user(pat_after_tilde, new_pat, new_pat_size);
	}
}

int glob(const char *restrict pat, int flags, int (*errfunc)(const char *path, int err), glob_t *restrict g)
{
	const char *p, *d;
	char new_pat[PATH_MAX + 1];
	struct match head = { .next = NULL }, *tail = &head;
	size_t cnt, i;
	size_t offs = (flags & GLOB_DOOFFS) ? g->gl_offs : 0;
	int error = 0;

	/*even if expanding fails(e.g. expansion make pat too big)
	 * we should try to match the ~ or ~user literally*/
	bool should_expand_tilde = (flags & GLOB_TILDE) && (pat[0] == '~');
	if(should_expand_tilde && expand_tilde(pat, new_pat, sizeof(new_pat))) {
		p = new_pat;
	} else {
		p = pat;
	}
	
	if (*p == '/') {
		for (; *p == '/'; p++);
		d = "/";
	} else {
		d = "";
	}

	if (!errfunc) errfunc = ignore_err;

	if (!(flags & GLOB_APPEND)) {
		g->gl_offs = offs;
		g->gl_pathc = 0;
		g->gl_pathv = NULL;
	}

	if (strnlen(p, PATH_MAX+1) > PATH_MAX) return GLOB_NOSPACE;

	if (*p) error = match_in_dir(d, p, flags, errfunc, &tail);
	if (error == GLOB_NOSPACE) {
		freelist(&head);
		return error;
	}
	
	for (cnt=0, tail=head.next; tail; tail=tail->next, cnt++);
	if (!cnt) {
		if (flags & GLOB_NOCHECK) {
			tail = &head;
			if (append(&tail, pat, strlen(pat), 0))
				return GLOB_NOSPACE;
			cnt++;
		} else
			return GLOB_NOMATCH;
	}

	if (flags & GLOB_APPEND) {
		char **pathv = realloc(g->gl_pathv, (offs + g->gl_pathc + cnt + 1) * sizeof(char *));
		if (!pathv) {
			freelist(&head);
			return GLOB_NOSPACE;
		}
		g->gl_pathv = pathv;
		offs += g->gl_pathc;
	} else {
		g->gl_pathv = malloc((offs + cnt + 1) * sizeof(char *));
		if (!g->gl_pathv) {
			freelist(&head);
			return GLOB_NOSPACE;
		}
		for (i=0; i<offs; i++)
			g->gl_pathv[i] = NULL;
	}
	for (i=0, tail=head.next; i<cnt; tail=tail->next, i++)
		g->gl_pathv[offs + i] = tail->name;
	g->gl_pathv[offs + i] = NULL;
	g->gl_pathc += cnt;

	if (!(flags & GLOB_NOSORT))
		qsort(g->gl_pathv+offs, cnt, sizeof(char *), sort);
	
	return error;
}

void globfree(glob_t *g)
{
	size_t i;
	for (i=0; i<g->gl_pathc; i++)
		free(g->gl_pathv[g->gl_offs + i] - offsetof(struct match, name));
	free(g->gl_pathv);
	g->gl_pathc = 0;
	g->gl_pathv = NULL;
}

LFS64(glob);
LFS64(globfree);