/*
 * UNG's Not GNU
 *
 * Copyright (c) 2011-2022, Jakob Kaivo <jkk@ung.org>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#define _XOPEN_SOURCE 700
#include <ctype.h>
#include <errno.h>
#include <fcntl.h>	/* included because GNU only defines AT_FDCWD here */
#include <grp.h>
#include <inttypes.h>
#include <limits.h>
#include <locale.h>
#include <pwd.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/stat.h>
#include <unistd.h>
#include <dirent.h>
#include <stdlib.h>
#include <string.h>
#include <ftw.h>
#include <time.h>

#ifndef PATH_MAX
#ifdef _XOPEN_PATH_MAX
#define PATH_MAX _XOPEN_PATH_MAX
#else
#define PATH_MAX _POSIX_PATH_MAX
#endif
#endif

#define SIZEWIDTH	(8)

static enum {
	ALPHA,
	SIZE,
	DIRECTORY,
	CTIME,
	MTIME,
	ATIME,
} sort = ALPHA;

static enum { HIDE_ALL, HIDE_SOME, HIDE_NONE } ls_hidden = HIDE_ALL;
static enum { GROUP_NAME, GROUP_ID, GROUP_NONE } ls_group = GROUP_NAME;
static enum { OWNER_NAME, OWNER_ID, OWNER_NONE } ls_owner = OWNER_NAME;
static enum { MARK_NONE, MARK_DIRS, MARK_ALL } ls_mark = MARK_NONE;
static enum { BLOCKS_NONE, BLOCKS_POSIX, BLOCKS_KIBI } ls_blocks = BLOCKS_NONE;
static int ls_print_inodes = 0;
static int ls_questionable = 0;

static int reverse = 0;
static int stat_flags = AT_SYMLINK_NOFOLLOW;
static size_t nftw_dirlen = 0;

struct file_info {
	char *path;
	char link[PATH_MAX];
	struct stat st;
	struct stat lstat;
};

static void (*ls_print)(size_t n, struct file_info[static n]);

static char * ls_getmark(mode_t mode)
{
	if (ls_mark != MARK_NONE && S_ISDIR(mode)) {
		return "/";
	} else if (ls_mark == MARK_ALL) {
		if (S_ISFIFO(mode)) {
			return "|";
		} else if (S_ISLNK(mode)) {
			return "@";
		} else if (S_ISREG(mode)) {
			if ((S_IXUSR & mode) || (S_IXGRP & mode) || (S_IXOTH & mode)) {
				return "*";
			}
		}
	}

	return "";
}

static char * ls_filename(struct file_info *f)
{
	static char name[PATH_MAX + 2];
	snprintf(name, sizeof(name), "%s%s", f->path, ls_getmark(f->st.st_mode));

	if (ls_questionable) {
		for (size_t i = 0; i < strlen(name); i++) {
			if (name[i] == '\t' || !isprint(name[i])) {
				name[i] = '?';
			}
		}
	}
	return name;
}

static int ls_compare_files(const void *op_a, const void *op_b)
{
	const struct file_info *a = op_a;
	const struct file_info *b = op_b;

	int ret = 0;
	switch (sort) {
	case SIZE:
		ret = b->st.st_size - a->st.st_size;
		break;

	case CTIME:
		ret = b->st.st_ctime - a->st.st_ctime;
		break;

	case MTIME:
		ret = b->st.st_mtime - a->st.st_mtime;
		break;

	case ATIME:
		ret = b->st.st_atime - a->st.st_atime;
		break;

	case DIRECTORY:
		ret = 1;
		break;

	case ALPHA:
		/* handled below */
		break;
	}

	if (ret == 0) {
		ret = strcoll(a->path, b->path);
	}

	return (reverse ? -1 : 1) * ret;
}

static int ls_dir(const char *dir, int showdirname)
{
	size_t nfiles = 0;
	struct file_info *files = NULL;
	int ret = 0;
	uintmax_t blocks = 0;

	DIR *d = opendir(dir);
	if (d == NULL) {
		fprintf(stderr, "ls: %s: %s\n", dir, strerror(errno));
		return 1;
	}
	int dfd = dirfd(d);

	struct dirent *de;
	while ((de = readdir(d)) != NULL) {
		if (de->d_name[0] == '.') {
			if (ls_hidden == HIDE_ALL) {
				continue;
			}

			if (ls_hidden == HIDE_SOME && (!strcmp(".", de->d_name) || !strcmp("..", de->d_name))) {
				continue;
			}
		}

		struct file_info *tmp = realloc(files, sizeof(*tmp) * (nfiles + 1));
		if (tmp == NULL) {
			perror("ls: out of memory");
			return 1;
		}
		files = tmp;

		files[nfiles].path = strdup(de->d_name);
		if (files[nfiles].path == NULL) {
			perror("ls: out of memory");
			return 1;
		}

		/* TODO: maybe don't need stat */
		if (fstatat(dfd, de->d_name, &files[nfiles].st, stat_flags) == -1) {
			fprintf(stderr, "ls: %s: %s\n", de->d_name, strerror(errno));
			free(files[nfiles].path);
			files[nfiles].path = NULL;
			ret = 1;
		} else {
			blocks += files[nfiles].st.st_blocks;
			if (S_ISLNK(files[nfiles].st.st_mode)) {
				readlinkat(dfd, de->d_name, files[nfiles].link,
					sizeof(files[nfiles].link));
				fstatat(dfd, de->d_name, &files[nfiles].lstat, 0);
			}
			nfiles++;
		}
	}
	closedir(d);

	if (showdirname) {
		printf("%s:\n", dir);
	}

	if (ls_blocks != BLOCKS_NONE) {
		/* TODO: adjust for BLOCK_KIBI */
		printf("total %ju\n", blocks);
	}

	qsort(files, nfiles, sizeof(*files), ls_compare_files);
	ls_print(nfiles, files);

	for (size_t i = 0; i < nfiles; i++) {
		free(files[i].path);
	}
	free(files);

	return ret;
}

static size_t ls_find_widest(size_t n, struct file_info files[static n])
{
	size_t ret = 0;
	for (size_t i = 0; i < n; i++) {
		size_t len = strlen(ls_filename(files + i));
		if (len > ret) {
			ret = len;
		}
	}
	return ret + 1;
}

static char *ls_file_mode(struct stat st)
{
	mode_t m = st.st_mode;
	static char mode[] = "----------";

	if (S_ISDIR(m)) {
		mode[0] = 'd';
	} else if (S_ISBLK(m)) {
		mode[0] = 'b';
	} else if (S_ISCHR(m)) {
		mode[0] = 'c';
	} else if (S_ISLNK(m)) {
		mode[0] = 'l';
	} else if (S_ISFIFO(m)) {
		mode[0] = 'p';
	} else {
		mode[0] = '-';
	}

	mode[1] = m & S_IRUSR ? 'r' : '-';
	mode[2] = m & S_IWUSR ? 'w' : '-';
	if (m & S_ISUID) {
		mode[3] = m & S_IXUSR ? 's' : 'S';
	} else {
		mode[3] = m & S_IXUSR ? 'x' : '-';
	}

	mode[4] = m & S_IRGRP ? 'r' : '-';
	mode[5] = m & S_IWGRP ? 'w' : '-';
	if (m & S_ISGID) {
		mode[6] = m & S_IXGRP ? 's' : 'S';
	} else {
		mode[6] = m & S_IXGRP ? 'x' : '-';
	}

	mode[7] = m & S_IROTH ? 'r' : '-';
	mode[8] = m & S_IWOTH ? 'w' : '-';
	if (m & S_ISVTX) {
		mode[9] = m & S_IXOTH ? 't' : 'T';
	} else {
		mode[9] = m & S_IXOTH ? 'x' : '-';
	}

	return mode;
}

static char *ls_file_owner(uid_t uid)
{
	static char owner[32];
	if (ls_owner == OWNER_NAME) {
		struct passwd *pwd = getpwuid(uid);
		if (pwd) {
			return pwd->pw_name;
		}
	}
	snprintf(owner, sizeof(owner), "%ju", (uintmax_t)uid);
	return owner;
}

static char *ls_file_group(gid_t gid)
{
	static char group[32];
	if (ls_group == GROUP_NAME) {
		struct group *grp = getgrgid(gid);
		if (grp) {
			return grp->gr_name;
		}
	}
	snprintf(group, sizeof(group), "%ju", (uintmax_t)gid);
	return group;
}

static char *ls_file_time(struct timespec mtime)
{
	static char date[16];
	time_t now = time(NULL);
	struct tm mtm;
	struct tm ntm;

	localtime_r(&now, &ntm);
	localtime_r(&mtime.tv_sec, &mtm);

	if (mtm.tm_mon < 6) {
		mtm.tm_year += 1;
		mtm.tm_year += 6;
	}

	if (ntm.tm_year > mtm.tm_year ||
		(ntm.tm_year == mtm.tm_year && ntm.tm_mon - mtm.tm_mon > 6) ||
		(now < mtime.tv_sec)) {
		strftime(date, sizeof(date), "%b %e  %Y", &mtm);
	} else {
		strftime(date, sizeof(date), "%b %e %H:%M", &mtm);
	}

	return date;
}

static void ls_print_long(size_t n, struct file_info files[static n])
{
	for (size_t i = 0; i < n; i++) {
		struct stat st = files[i].st;

		if (ls_print_inodes) {
			printf("%*ju ", SIZEWIDTH, (uintmax_t)st.st_ino);
		}

		printf("%s ", ls_file_mode(st));

		printf("%ju ", (uintmax_t)st.st_nlink);

		if (ls_owner != OWNER_NONE) {
			printf("%*s ", - _POSIX_LOGIN_NAME_MAX,
				ls_file_owner(st.st_uid));
		}

		if (ls_group != GROUP_NONE) {
			printf("%*s ", - _POSIX_LOGIN_NAME_MAX,
				ls_file_group(st.st_gid));
		}

		if (S_ISCHR(st.st_mode) || S_ISBLK(st.st_mode)) {
			printf("%*jx ", SIZEWIDTH, (uintmax_t)st.st_rdev);
		} else {
			printf("%*ju ", SIZEWIDTH, (uintmax_t)st.st_size);
		}

		if (sort == ATIME) {
			printf("%s ", ls_file_time(st.st_atim));
		} else if (sort == CTIME) {
			printf("%s ", ls_file_time(st.st_ctim));
		} else {
			printf("%s ", ls_file_time(st.st_mtim));
		}

		char * name = ls_filename(files + i);
		if (S_ISLNK(st.st_mode)) {
			if (ls_mark == MARK_ALL) {
				name[strlen(name) - 1] = '\0';
			}
			printf("%s -> %s", name, files[i].link);
			printf("%s", ls_getmark(files[i].lstat.st_mode));
		} else {
			printf("%s", name);
		}

		printf("\n");
	}
}

static void ls_print_single(size_t n, struct file_info files[static n])
{
	for (size_t i = 0; i < n; i++) {
		if (ls_print_inodes) {
			printf("%ju ", (uintmax_t)files[i].st.st_ino);
		}
		printf("%s\n", ls_filename(files + i));
	}
}

static size_t ls_get_columns(void)
{
	static size_t columns = 0;
	if (columns == 0) {
		char *env = getenv("COLUMNS");
		if (env) {
			columns = atoi(env);
		}
		if (columns == 0) {
			columns = 80;
		}
	}
	return columns;
}

static void ls_print_serial(size_t n, struct file_info files[static n])
{
	if (n == 0) {
		return;
	}

	size_t columns = ls_get_columns();
	size_t at = 0;

	/* TODO: wrap at screen width */
	for (size_t i = 0; i < n - 1; i++) {
		char *s = ls_filename(files + i);
		if (at + strlen(s) > columns) {
			printf("\n");
			at = 0;
		}
		if (ls_print_inodes) {
			at += printf("%ju ", (uintmax_t)files[i].st.st_ino);
		}
		at += printf("%s, ", ls_filename(files + i));
	}
	if (ls_print_inodes) {
		printf("%ju ", (uintmax_t)files[n - 1].st.st_ino);
	}
	printf("%s\n", ls_filename(files + n - 1));
}

static void ls_print_columns(size_t n, struct file_info files[static n])
{
	size_t widest = ls_find_widest(n, files);
	size_t columns = ls_get_columns();
	size_t ncolumns = columns / widest;
	if (ls_print_inodes) {
		ncolumns /= 2;
	}
	size_t nrows = n / ncolumns;

	/* account for partial columns */
	nrows++;

	char format[32] = "";
	snprintf(format, sizeof(format), "%%-%zds", widest);

	for (size_t i = 0; i < nrows; i++) {
		for (size_t j = 0; j < ncolumns; j++) {
			size_t fn = i + (nrows * j);
			if (fn < n) {
				if (ls_print_inodes) {
					printf("%ju ",
						(uintmax_t)files[fn].st.st_ino);
				}
				printf(format, ls_filename(files + fn));
			}
		}
		printf("\n");
	}
}

static void ls_print_rows(size_t n, struct file_info files[static n])
{
	size_t widest = ls_find_widest(n, files);
	size_t columns = ls_get_columns();
	size_t ncolumns = columns / widest;
	if (ls_print_inodes) {
		ncolumns /= 2;
	}

	char format[32] = "";
	snprintf(format, sizeof(format), "%%-%zds", widest);

	for (size_t i = 0; i < n; i++) {
		if (ls_print_inodes) {
			printf("%ju ", (uintmax_t)files[i].st.st_ino);
		}
		printf(format, ls_filename(files + i));
		if (i % ncolumns == ncolumns - 1) {
			printf("\n");
		}
	}
	printf("\n");
}

static int ls_compare_operands(const void *op_a, const void *op_b)
{
	const struct file_info *a = op_a;
	const struct file_info *b = op_b;

	if (a->path == NULL && b->path == NULL) {
		return 0;
	}

	if (a->path == NULL) {
		return 1;
	}

	if (b->path == NULL) {
		return -1;
	}

	if (S_ISDIR(a->st.st_mode) && !S_ISDIR(b->st.st_mode)) {
		return 1;
	}

	if (!S_ISDIR(a->st.st_mode) && S_ISDIR(b->st.st_mode)) {
		return -1;
	}

	return strcoll(a->path, b->path);
}

static int ls_nftw(const char *path, const struct stat *st, int type, struct FTW *ftw)
{
	(void)st;
	(void)ftw;

	if (type != FTW_D) {
		return 0;
	}

	if (ls_hidden == HIDE_ALL && path[nftw_dirlen + 1] == '.') {
		return 0;
	}

	static int firstpass = 1;
	if (firstpass) {
		firstpass = 0;
	} else {
		printf("\n");
	}

	ls_dir(path, 1);
	return 0;
}

int main(int argc, char *argv[])
{
	setlocale(LC_ALL, "");

	ls_print = isatty(STDOUT_FILENO) ? ls_print_columns : ls_print_single;
	ls_questionable = isatty(STDOUT_FILENO) ? 1 : 0;

	enum { NONE, OPERANDS, ALL } links = NONE;
	int list_dirs_separately = 1;
	int recursive = 0;

	int c;
	while ((c = getopt(argc, argv, "ACFRSacdgfiklmnopqrstux1HL")) != -1) {
		switch (c) {
		case 'A':	/** all but . and .. **/
			ls_hidden = HIDE_SOME;
			break;

		case 'C':	/** sort in columns **/
			ls_print = ls_print_columns;
			break;

		case 'F':	/** append file type characters **/
			ls_mark = MARK_ALL;
			break;

		case 'H':	/** follow symbolic links on command line **/
			links = OPERANDS;
			break;

		case 'L':	/** follow all symbolic links **/
			links = ALL;
			break;

		case 'R':	/** run recursively **/
			recursive = 1;
			break;

		case 'S':	/** sort by size **/
			sort = SIZE;
			break;

		case 'a':	/** output all files **/
			ls_hidden = HIDE_NONE;
			break;

		case 'c':	/** sort by change time **/
			sort = CTIME;
			break;

		case 'd':	/** do not enter directories **/
			list_dirs_separately = 0;
			break;

		case 'f':	/** do not sort **/
			sort = DIRECTORY;
			ls_hidden = HIDE_NONE;
			//display = ROWS;
			//format ^= BLOCKS;
			recursive = 0;
			break;

		case 'g':	/** like -l, but without owner **/
			if (ls_blocks == BLOCKS_NONE) {
				ls_blocks = BLOCKS_POSIX;
			}
			ls_print = ls_print_long;
			ls_owner = OWNER_NONE;
			break;

		case 'i':	/** include file serial numbers **/
			ls_print_inodes = 1;
			break;

		case 'k':	/** use a blocksize of 1024 **/
			ls_blocks = BLOCKS_KIBI;
			break;

		case 'l':	/** output full details **/
			if (ls_blocks == BLOCKS_NONE) {
				ls_blocks = BLOCKS_POSIX;
			}
			ls_print = ls_print_long;
			break;

		case 'm':	/** stream output separated by commas **/
			ls_print = ls_print_serial;
			break;

		case 'n':	/** like -l, but with numeric UID and GID **/
			if (ls_blocks == BLOCKS_NONE) {
				ls_blocks = BLOCKS_POSIX;
			}
			ls_print = ls_print_long;
			ls_owner = OWNER_ID;
			ls_group = GROUP_ID;
			break;

		case 'o':	/** like -l, but without group **/
			if (ls_blocks == BLOCKS_NONE) {
				ls_blocks = BLOCKS_POSIX;
			}
			ls_print = ls_print_long;
			ls_group = GROUP_NONE;
			break;

		case 'p':	/** append / after directory names **/
			ls_mark = MARK_DIRS;
			break;

		case 'q':	/** replace non-printable characters with ? **/
			ls_questionable = 1;
			break;

		case 'r':	/** reverse sort order **/
			reverse = 1;
			break;

		case 's':	/** outpu total number of blocks **/
			if (ls_blocks == BLOCKS_NONE) {
				ls_blocks = BLOCKS_POSIX;
			}
			break;

		case 't':	/** sort by modified time **/
			sort = MTIME;
			break;

		case 'u':	/** sort by access time **/
			sort = ATIME;
			break;

		case 'x':	/** sort across rows first **/
			ls_print = ls_print_rows;
			break;

		case '1':	/** output one file per line **/
			ls_print = ls_print_single;
			break;

		default:
			return 1;
		}
	}

	/* sort operands */
	/* TODO: deal with -L/-H */
	argv += optind;
	argc -= optind;

	if (links != NONE) {
		stat_flags = AT_SYMLINK_NOFOLLOW;
	}

	struct file_info operands[argc + 1];
	int ret = 0;
	for (int i = 0; i < argc; i++) {
		operands[i].path = argv[i];
		if (fstatat(AT_FDCWD, argv[i], &operands[i].st, stat_flags) == -1) {
			operands[i].path = NULL;
			fprintf(stderr, "ls: %s: %s\n", argv[i], strerror(errno));
			ret = 1;
		}
		if (S_ISLNK(operands[i].st.st_mode)) {
			readlinkat(AT_FDCWD, argv[i], operands[i].link,
				sizeof(operands[i].link));
			fstatat(AT_FDCWD, argv[i], &operands[i].lstat, 0);
		}
	}
	operands[argc].path = NULL;
	qsort(operands, argc, sizeof(operands[0]), ls_compare_operands);

	if (links != ALL) {
		stat_flags = AT_SYMLINK_NOFOLLOW;
	}

	/* list files */
	size_t nfiles = 0;
	struct file_info *op = operands;
	while (op->path != NULL) {
		if (list_dirs_separately && S_ISDIR(op->st.st_mode)) {
			break;
		}
		op++;
		nfiles++;
	}

	if (nfiles > 0) {
		qsort(operands, nfiles, sizeof(operands[0]), ls_compare_files);
		ls_print(nfiles, operands);
		if (op->path) {
			printf("\n");
		}
	}

	while (op->path != NULL) {
		if (recursive) {
			nftw_dirlen = strlen(op->path);
			nftw(op->path, ls_nftw, 10000, FTW_PHYS);
		} else {
			ls_dir(op->path, (size_t)argc > nfiles + 1);
		}
		op++;
		if (op->path) {
			printf("\n");
		}
	}

	if (argc == 0) {
		if (recursive) {
			nftw_dirlen = 1;
			nftw(".", ls_nftw, 10000, FTW_PHYS);
		} else {
			ret = ls_dir(".", 0);
		}
	}

	return ret;
}