/* See LICENSE file for copyright and license details. */
#include "common.h"
#ifndef TEST


#define FLAG_MINUS 0x01
#define FLAG_PLUS  0x02
#define FLAG_HASH  0x04
#define FLAG_ZERO  0x08
#define FLAG_SPACE 0x10


#define TYPESIZE_CHAR -2
#define TYPESIZE_SHORT -1
#define TYPESIZE_INT 0
#define TYPESIZE_LONG +1
#define TYPESIZE_LONG_LONG +2
#define TYPESIZE_SIZE 3
#define TYPESIZE_PTRDIFF 4
#define TYPESIZE_INTPTR 5
#define TYPESIZE_INTMAX 6


union anyarray_const {
	const void *v;
	const signed char *hhi;
	const signed short int  *hi;
	const signed int *i;
	const signed long int *li;
	const signed long long int *lli;
	const ssize_t *zi;
	const ptrdiff_t *ti;
	const intptr_t *pi;
	const intmax_t *ji;
	const unsigned char *hhu;
	const unsigned short int  *hu;
	const unsigned int *u;
	const unsigned long int *lu;
	const unsigned long long int *llu;
	const size_t *zu;
	const ptrdiff_t *tu;
	const uintptr_t *pu;
	const uintmax_t *ju;
	const char *c;
	const char *const *s;
};

union anyvalue {
	intmax_t i;
	uintmax_t u;
	char c[2];
	const char *s;
};

struct partial_string {
	char *s;
	size_t len;
	size_t size;
	int started;
};

struct argument_format {
	size_t array_size;
	size_t width1;
	size_t width2;
	int array_input;
	int array_null_terminated;
	int typesize;
	int has_dot;
	char typeclass;
	unsigned flags;
};

struct ignore_stack {
	char *stack;
	size_t top;
	size_t size;
	size_t active;
};


static int
resize_partial_string(struct partial_string *str, size_t req_size)
{
	void *new = realloc(str->s, req_size);
	if (!new)
		return -1;
	str->s = new;
	str->size = req_size;
	return 0;
}


static int
resize_partial_string_if_full(struct partial_string *str, size_t extra)
{
	if (str->len == str->size)
		if (resize_partial_string(str, str->len + extra))
			return -1;
	return 0;
}


static char *
make_unsigned(uintmax_t value, char fmt, const char *plus, const char *prefix, size_t minwidth)
{
#if defined(__GNUC__)
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wformat-nonliteral"
#endif

	const char *fmtstr;
	char *ret, *p;
	size_t len, zeroes, totlen;

	if (fmt == 'd' || fmt == 'i' || fmt == 'u')
		fmtstr = "%ju";
	else if (fmt == 'o')
		fmtstr = "%jo";
	else if (fmt == 'x')
		fmtstr = "%jx";
	else if (fmt == 'X')
		fmtstr = "%jX";
	else
		abort();

	len = (size_t)snprintf(NULL, 0, fmtstr, value);
	zeroes = len < minwidth ? minwidth - len : 0;

	totlen = strlen(plus) + 1;
	if (strlen(prefix) > SIZE_MAX - totlen)
		goto enomem;
	totlen += strlen(prefix);
	if (zeroes + len > SIZE_MAX - totlen)
		goto enomem;
	totlen += zeroes + len;

	ret = malloc(totlen);
	if (!ret)
		goto enomem;

	p = stpcpy(stpcpy(ret, plus), prefix);
	while (zeroes--)
		*p++ = '0';
	sprintf(p, fmtstr, value);

	return ret;

enomem:
	errno = ENOMEM;
	return NULL;

#if defined(__GNUC__)
# pragma GCC diagnostic pop
#endif
}


static char *
make_signed(intmax_t value, char fmt, const char *plus, const char *prefix, size_t minwidth)
{
	if (value < 0)
		return make_unsigned((uintmax_t)-(value + 1) + 1U, fmt, "-", prefix, minwidth);
	else
		return make_unsigned((uintmax_t)value, fmt, plus, prefix, minwidth);
}


static unsigned
get_flag(char c)
{
	return c == '-' ? FLAG_MINUS :
	       c == '+' ? FLAG_PLUS :
	       c == '#' ? FLAG_HASH :
	       c == '0' ? FLAG_ZERO :
	       c == ' ' ? FLAG_SPACE : 0U;
}


static unsigned
remove_ignored_flags(unsigned flags, char fmt)
{
	if (fmt == 's' || fmt == 'c') {
		flags &= FLAG_MINUS;
	} else if (fmt == 'i' || fmt == 'd') {
		if (flags & FLAG_PLUS)
			flags &= (unsigned)~FLAG_SPACE;
	} else {
		flags &= (unsigned)~(FLAG_PLUS | FLAG_SPACE);
	}
	return flags;
}


static const char *
read_size(size_t *out, const char *fmt, va_list args, int optional)
{
	size_t digit;

	if (*fmt == '*') {
		fmt++;
		*out = va_arg(args, size_t);
	} else if (!optional && !isdigit(*fmt)) {
		goto einval;
	} else {
		*out = 0;
		while (isdigit(*fmt)) {
			digit = (size_t)(*fmt++ - '0');
			if (*out > (SIZE_MAX - digit) / 10U)
				goto einval;
			*out = *out * 10U + digit;
		}
	}

	return fmt;

einval:
	errno = EINVAL;
	return NULL;
}


static const char *
get_typesize(int *out, const char *fmt)
{
	*out = 0;

	for (; *fmt == 'h'; fmt++)
		if (--*out < -2)
			goto einval;

	for (; *fmt == 'l'; fmt++)
		if (*out < 0 || ++*out > +2)
			goto einval;

	if (*fmt == 'z' || *fmt == 't' || *fmt == 'T' || *fmt == 'j') {
		if (*out)
			goto einval;
		*out = *fmt == 'z' ? TYPESIZE_SIZE :
		       *fmt == 't' ? TYPESIZE_PTRDIFF :
		       *fmt == 'T' ? TYPESIZE_INTPTR : /* non-standard */
		                     TYPESIZE_INTMAX;
		fmt++;
	}

	/*
	 * TODO add =N for intN_t/uintN_t (arbitrary N)
	 * TODO add =+N for int_leastN_t/uint_leastN_t (arbitrary N)
	 * TODO add =/N for int_fastN_t/uint_fastN_t (arbitrary N)
	 * non-standard
	 */

	if (*fmt == 's' || *fmt == 'c') {
		if (*out) {
			/* TODO %ls should be `const wchar_t *` */
			/* TODO %lc should be `wint_t` */
			goto einval;
		}
	}

	return fmt;

einval:
	errno = EINVAL;
	return NULL;
}


static intmax_t
get_signed_va(va_list args, int typesize)
{
	if (typesize == TYPESIZE_CHAR)
		return (intmax_t)(signed char)va_arg(args, signed int);
	else if (typesize == TYPESIZE_SHORT)
		return (intmax_t)(signed short int)va_arg(args, signed int);
	else if (typesize == TYPESIZE_INT)
		return (intmax_t)va_arg(args, signed int);
	else if (typesize == TYPESIZE_LONG)
		return (intmax_t)va_arg(args, signed long int);
	else if (typesize == TYPESIZE_LONG_LONG)
		return (intmax_t)va_arg(args, signed long long int);
	else if (typesize == TYPESIZE_SIZE) /* TODO since ssize_t may be bounded to -1, may it be bounded above INTMAX_MAX? */
		return (intmax_t)va_arg(args, ssize_t);
	else if (typesize == TYPESIZE_PTRDIFF)
		return (intmax_t)va_arg(args, ptrdiff_t);
	else if (typesize == TYPESIZE_INTPTR)
		return (intmax_t)va_arg(args, intptr_t);
	else if (typesize == TYPESIZE_INTMAX)
		return (intmax_t)va_arg(args, intmax_t);
	else
		abort();
}


static uintmax_t
get_unsigned_va(va_list args, int typesize)
{
	if (typesize == TYPESIZE_CHAR)
		return (uintmax_t)(unsigned char)va_arg(args, unsigned int);
	else if (typesize == TYPESIZE_SHORT)
		return (uintmax_t)(unsigned short int)va_arg(args, unsigned int);
	else if (typesize == TYPESIZE_INT)
		return (uintmax_t)va_arg(args, unsigned int);
	else if (typesize == TYPESIZE_LONG)
		return (uintmax_t)va_arg(args, unsigned long int);
	else if (typesize == TYPESIZE_LONG_LONG)
		return (uintmax_t)va_arg(args, unsigned long long int);
	else if (typesize == TYPESIZE_SIZE)
		return (uintmax_t)va_arg(args, size_t);
	else if (typesize == TYPESIZE_PTRDIFF)
		return (uintmax_t)va_arg(args, ptrdiff_t); /* TODO ptrdiff_t is signed */
	else if (typesize == TYPESIZE_INTPTR)
		return (uintmax_t)va_arg(args, uintptr_t);
	else if (typesize == TYPESIZE_INTMAX)
		return (uintmax_t)va_arg(args, uintmax_t);
	else
		abort();
}


static intmax_t
get_signed_array(union anyarray_const *arrayp, int typesize)
{
	if (typesize == TYPESIZE_CHAR)
		return (intmax_t)*arrayp->hhi++;
	else if (typesize == TYPESIZE_SHORT)
		return (intmax_t)*arrayp->hi++;
	else if (typesize == TYPESIZE_INT)
		return (intmax_t)*arrayp->i++;
	else if (typesize == TYPESIZE_LONG)
		return (intmax_t)*arrayp->li++;
	else if (typesize == TYPESIZE_LONG_LONG)
		return (intmax_t)*arrayp->lli++;
	else if (typesize == TYPESIZE_SIZE)
		return (intmax_t)*arrayp->zi++; /* TODO since ssize_t may be bounded to -1, may it be bounded above INTMAX_MAX? */
	else if (typesize == TYPESIZE_PTRDIFF)
		return (intmax_t)*arrayp->ti++;
	else if (typesize == TYPESIZE_INTPTR)
		return (intmax_t)*arrayp->pi++;
	else if (typesize == TYPESIZE_INTMAX)
		return (intmax_t)*arrayp->ji++;
	else
		abort();
}


static uintmax_t
get_unsigned_array(union anyarray_const *arrayp, int typesize)
{
	if (typesize == TYPESIZE_CHAR)
		return (uintmax_t)*arrayp->hhu++;
	else if (typesize == TYPESIZE_SHORT)
		return (uintmax_t)*arrayp->hu++;
	else if (typesize == TYPESIZE_INT)
		return (uintmax_t)*arrayp->u++;
	else if (typesize == TYPESIZE_LONG)
		return (uintmax_t)*arrayp->lu++;
	else if (typesize == TYPESIZE_LONG_LONG)
		return (uintmax_t)*arrayp->llu++;
	else if (typesize == TYPESIZE_SIZE)
		return (uintmax_t)*arrayp->zu++;
	else if (typesize == TYPESIZE_PTRDIFF)
		return (uintmax_t)*arrayp->tu++; /* TODO ptrdiff_t is signed */
	else if (typesize == TYPESIZE_INTPTR)
		return (uintmax_t)*arrayp->pu++;
	else if (typesize == TYPESIZE_INTMAX)
		return (uintmax_t)*arrayp->ju++;
	else
		abort();
}


static int
get_value_va(union anyvalue *out, va_list args, char fmt, int typesize)
{
	if (fmt == 'i' || fmt == 'd') {
		out->i = get_signed_va(args, typesize);

	} else if (fmt == 'u' || fmt == 'o' || fmt == 'x' || fmt == 'X') {
		out->u = get_unsigned_va(args, typesize);

	} else if (fmt == 's') {
		if (typesize)
			abort();
		out->s = va_arg(args, const char *);

	} else if (fmt == 'c') {
		if (typesize)
			abort();
		out->c[0] = (char)va_arg(args, int);
		out->c[1] = '\0';

	} else {
		errno = EINVAL;
		return -1;
	}

	return 0;
}


static int
get_value_array(union anyvalue *out, union anyarray_const *arrayp, char fmt, int typesize)
{
	if (fmt == 'i' || fmt == 'd') {
		out->i = get_signed_array(arrayp, typesize);
		return !!out->i;

	} else if (fmt == 'u' || fmt == 'o' || fmt == 'x' || fmt == 'X') {
		out->u = get_unsigned_array(arrayp, typesize);
		return !!out->u;

	} else if (fmt == 's') {
		if (typesize)
			abort();
		out->s = *arrayp->s++;
		return !!out->s;

	} else if (fmt == 'c') {
		if (typesize)
			abort();
		out->c[0] = *arrayp->c++;
		out->c[1] = '\0';
		return !!out->c[0];

	} else {
		errno = EINVAL;
		return -1;
	}
}


static char *
create_string(const union anyvalue *value, char fmt, const char *plus, const char *prefix, int has_dot, size_t width)
{
	if (fmt == 'i' || fmt == 'd') {
		return make_signed(value->i, fmt, plus, value->i ? prefix : "", width);

	} else if (fmt == 'u' || fmt == 'o' || fmt == 'x' || fmt == 'X') {
		return make_unsigned(value->u, fmt, "", value->u ? prefix : "", width);

	} else if (fmt == 's') {
		return strndup(value->s, has_dot ? width : strlen(value->s));

	} else if (fmt == 'c') {
		return strndup(value->c, has_dot ? width : 1);

	} else {
		errno = EINVAL;
		return NULL;
	}
}


static int
pad_and_insert(struct partial_string *arg, const char *substring, size_t min_width, char pad_char, unsigned pad_before)
{
	size_t pad_len, substring_len;

	substring_len = strlen(substring);
	pad_len = substring_len < min_width ? min_width - substring_len : 0;
	if (substring_len + pad_len > SIZE_MAX - arg->len) {
		errno = ENOMEM;
		return -1;
	}

	if (substring_len + pad_len + arg->len > arg->size)
		if (resize_partial_string(arg, substring_len + pad_len + arg->len))
			return -1;

	if (pad_before) {
		memset(&arg->s[arg->len], pad_char, pad_len);
		arg->len += pad_len;
	}

	memcpy(&arg->s[arg->len], substring, substring_len);
	arg->len += substring_len;

	if (!pad_before) {
		memset(&arg->s[arg->len], pad_char, pad_len);
		arg->len += pad_len;
	}

	return 0;
}


static int
insert_argument(struct partial_string *arg, const union anyvalue *value, char fmt,
                unsigned flags, size_t width1, int has_dot, size_t width2)
{
	const char *plus, *prefix;
	char *substring;

	plus = (flags & FLAG_PLUS) ? "+" : (flags & FLAG_SPACE) ? " " : "";

	prefix = !(flags & FLAG_HASH) ? "" :
	         fmt == 'o' ? "0" :
	         fmt == 'x' ? "0x" :
	         fmt == 'X' ? "0X" : "";

	if (fmt != 's' && fmt != 'c') {
		if (!has_dot) {
			width2 = width1;
			width1 = 0;
		}
	}

	substring = create_string(value, fmt, plus, prefix, has_dot, width2);
	if (!substring)
		return -1;

	if (pad_and_insert(arg, substring, width1, (flags & FLAG_ZERO) ? '0' : ' ', flags & FLAG_MINUS)) {
		free(substring);
		return -1;
	}

	free(substring);
	return 0;
}


static int
get_and_insert_arguments(struct partial_string *arg, va_list args, const struct argument_format *arg_fmt, int ignoring)
{
	union anyarray_const array;
	union anyvalue value;
	unsigned int flags;
	size_t n;
	int r;

	flags = remove_ignored_flags(arg_fmt->flags, arg_fmt->typeclass);

	if (arg_fmt->array_input) {
		array.v = va_arg(args, const void *);
		n = arg_fmt->array_size;
		while (arg_fmt->array_null_terminated || n--) {
			r = get_value_array(&value, &array, arg_fmt->typeclass, arg_fmt->typesize);
			if (r < 0)
				return -1;
			else if (!r && arg_fmt->array_null_terminated)
				break;
			if (!ignoring)
				if (insert_argument(arg, &value, arg_fmt->typeclass, flags,
				                    arg_fmt->width1, arg_fmt->has_dot, arg_fmt->width2))
					return -1;
		}

	} else {
		if (get_value_va(&value, args, arg_fmt->typeclass, arg_fmt->typesize))
			return -1;
		if (!ignoring)
			if (insert_argument(arg, &value, arg_fmt->typeclass, flags,
			                    arg_fmt->width1, arg_fmt->has_dot, arg_fmt->width2))
				return -1;
	}

	return 0;
}


static const char *
get_argument_format(struct argument_format *out, const char *fmt, va_list args)
{
	unsigned flag;

	memset(out, 0, sizeof(*out));

	if (*fmt == '[') {
		fmt++;
		out->array_input = 1;
		if (*fmt == ']') {
			out->array_null_terminated = 1;
		} else {
			fmt = read_size(&out->array_size, fmt, args, 1);
			if (!fmt)
				goto fail;
		}
		if (*fmt != ']')
			goto einval;
		fmt++;
	}

	while ((flag = get_flag(*fmt))) {
		out->flags |= flag;
		fmt++;
	}

	fmt = read_size(&out->width1, fmt, args, 0);
	if (!fmt)
		goto fail;
	if (*fmt == '.') {
		out->has_dot = 1;
		out->flags &= (unsigned)~FLAG_ZERO;
		fmt++;
		fmt = read_size(&out->width2, fmt, args, 0);
		if (!fmt)
			goto fail;
	}

	fmt = get_typesize(&out->typesize, fmt);
	if (!fmt)
		goto fail;

	out->typeclass = *fmt++;

	return fmt;

einval:
	errno = EINVAL;
fail:
	return NULL;
}


static void
destroy_ignore_stack(struct ignore_stack *stack)
{
	free(stack->stack);
	stack->stack = NULL;
}


static int
push_ignore_stack(struct ignore_stack *stack, va_list args)
{
	int show;
	void *new;
	size_t new_size;

	if (stack->top == stack->size) {
		new_size = stack->size + 8;
		new = realloc(stack->stack, new_size * sizeof(*stack->stack));
		if (!new)
			return -1;
		stack->stack = new;
		stack->size = new_size;
	}

	show = va_arg(args, int);
	stack->stack[stack->top++] = (char)!show;
	stack->active += (size_t)!show;
	return 0;
}


static int
pop_ignore_stack(struct ignore_stack *stack)
{
	if (!stack->top) {
		errno = EINVAL;
		return -1;
	}
	if (stack->stack[--stack->top])
		stack->active -= 1;
	return 0;
}


static int
is_ignoring(struct ignore_stack *stack)
{
	return stack->active > 0;
}


static const char *
format(const char *fmt, struct partial_string *arg, struct ignore_stack *ignore_stack, va_list args)
{
	
	struct argument_format arg_fmt;

	/* TODO $< should work as <(), * or number before < to select fd (default: STDOUT_FILENO) */
	/* TODO $> should work as >(), * or number before > to select fd (default: STDIN_FILENO) */
	/* TODO add support for embedding via %S and %C (do not set arg->started) */
	/* TODO add support for floating point values */

	if (*fmt == '$' || *fmt == '\'' || *fmt == '"' || *fmt == '_') {
		if (!is_ignoring(ignore_stack)) {
			if (arg->len == arg->size)
				if (resize_partial_string(arg, arg->size + 32))
					goto fail;
			arg->s[arg->len++] = *fmt == '_' ? ' ' : *fmt;
			arg->started = 1;
		}
		fmt++;

	} else if (*fmt == '(') {
		fmt++;
		if (push_ignore_stack(ignore_stack, args))
			goto fail;

	} else if (*fmt == ')') {
		fmt++;
		if (pop_ignore_stack(ignore_stack))
			goto fail;

	} else {
		fmt = get_argument_format(&arg_fmt, fmt, args);
		if (!fmt)
			goto fail;
		if (get_and_insert_arguments(arg, args, &arg_fmt, is_ignoring(ignore_stack)))
			goto fail;
		arg->started = 1;
	}

	return fmt;

fail:
	return NULL;
}


static char **
format_command(const char *fmt, va_list args, size_t *narguments_out)
{
	size_t command_size = 0;
	char **command = NULL;
	struct ignore_stack ignore_stack;
	struct partial_string arg;
	void *new;

	*narguments_out = 0;

	memset(&ignore_stack, 0, sizeof(ignore_stack));
	ignore_stack.stack = NULL;

	memset(&arg, 0, sizeof(arg));
	arg.s = NULL;

next_arg:
	arg.started = 0;
	arg.len = 0;
	while (*fmt) {
		if (*fmt == '$') {
			fmt++;
			fmt = format(fmt, &arg, &ignore_stack, args);
			if (!fmt)
				goto fail;

		} else if (isspace(*fmt)) {
			fmt++;
			if (!arg.started || is_ignoring(&ignore_stack))
				continue;
			new = realloc(command, (command_size + 1) * sizeof(*command));
			if (!new)
				goto fail;
			command = new;
			if (resize_partial_string_if_full(&arg, 32))
				goto fail;
			arg.s[arg.len] = '\0';
			command[command_size] = strdup(arg.s);
			if (!command[command_size])
				goto fail;
			command_size++;
			goto next_arg;

		} else if (*fmt == '\'' || *fmt == '"') {
			arg.started = 1;
			/* TODO add support for quotes */
			errno = EINVAL;
			goto fail;

		} else {
			if (!is_ignoring(&ignore_stack)) {
				if (resize_partial_string_if_full(&arg, 32))
					goto fail;
				arg.s[arg.len++] = *fmt;
				arg.started = 1;
			}
			fmt++;
		}
	}

	new = realloc(command, (command_size + 2) * sizeof(*command));
	if (!new)
		goto fail;
	command = new;
	if (arg.started) {
		if (resize_partial_string_if_full(&arg, 1))
			goto fail;
		arg.s[arg.len] = '\0';
		command[command_size++] = arg.s;
	} else {
		free(arg.s);
	}
	command[command_size] = NULL;
	destroy_ignore_stack(&ignore_stack);

	*narguments_out = command_size;
	return command;

fail:
	free(arg.s);
	destroy_ignore_stack(&ignore_stack);
	while (command_size)
		free(command[--command_size]);
	free(command);
	return NULL;
}


static int
append_arguments(struct libexec_command *cmd, va_list args)
{
	size_t n = 0, i;
	va_list args2;
	void *new;

	va_copy(args2, args);
	while (va_arg(args2, const char *))
		n += 1;
	va_end(args2);

	new = realloc(cmd->arguments, (cmd->narguments + n + 1) * sizeof(*cmd->arguments));
	if (!new)
		return -1;
	cmd->arguments = new;

	for (i = 0; i < n; i++) {
		cmd->arguments[cmd->narguments + i] = strdup(va_arg(args, const char *));
		if (!cmd->arguments[cmd->narguments + i]) {
			while (i)
				free(cmd->arguments[cmd->narguments + --i]);
			if (!cmd->narguments) {
				free(cmd->arguments);
				cmd->arguments = NULL;
			}
			return -1;
		}
	}

	cmd->arguments[cmd->narguments + n] = va_arg(args, char *); /* that's a NULL */
	cmd->narguments += n;

	return 0;
}


int
libexec_vconstruct_command(struct libexec_command *cmd, const char *fmt, va_list args)
{
	size_t n;
	char **command = NULL;
	void *new;

	if (!cmd) {
		errno = EINVAL;
		return -1;
	}

	if (!fmt) {
		return append_arguments(cmd, args);

	} else {
		command = format_command(fmt, args, &n);
		if (!command)
			return -1;
		if (!cmd->narguments) {
			cmd->arguments = command;
			cmd->narguments = n;
		} else {
			new = realloc(cmd->arguments, (cmd->narguments + n + 1) * sizeof(*cmd->arguments));
			if (!new) {
				while (n)
					free(command[--n]);
				free(command);
				return -1;
			}
			cmd->arguments = new;
			memcpy(&cmd->arguments[cmd->narguments], command, (n + 1) * sizeof(*command));
			cmd->narguments += n;
			free(command);
		}
		return 0;
	}
}


#else
TESTED_ELSEWHERE /* libexec_construct_command.c */
#endif