/*
 * This file was generated by the mknodes program.
 */

/*-
 * Copyright (c) 1991, 1993
 *	The Regents of the University of California.  All rights reserved.
 * Copyright (c) 1997-2005
 *	Herbert Xu <herbert@gondor.apana.org.au>.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Kenneth Almquist.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)nodes.c.pat	8.2 (Berkeley) 5/4/95
 */

#include <zircon/syscalls.h>
#include <stdlib.h>

/*
 * Routine for dealing with parsed shell commands.
 */

#include "shell.h"
#include "nodes.h"
#include "memalloc.h"
#include "machdep.h"
#include "mystring.h"
#include "system.h"
#include "error.h"
#include "var.h"


int     funcblocksize;		/* size of structures in function */
int     funcstringsize;		/* size of strings in node */
pointer funcblock;		/* block to allocate function from */
char   *funcstring;		/* block to allocate strings from */

static const short nodesize[26] = {
      SHELL_ALIGN(sizeof (struct ncmd)),
      SHELL_ALIGN(sizeof (struct npipe)),
      SHELL_ALIGN(sizeof (struct nredir)),
      SHELL_ALIGN(sizeof (struct nredir)),
      SHELL_ALIGN(sizeof (struct nredir)),
      SHELL_ALIGN(sizeof (struct nbinary)),
      SHELL_ALIGN(sizeof (struct nbinary)),
      SHELL_ALIGN(sizeof (struct nbinary)),
      SHELL_ALIGN(sizeof (struct nif)),
      SHELL_ALIGN(sizeof (struct nbinary)),
      SHELL_ALIGN(sizeof (struct nbinary)),
      SHELL_ALIGN(sizeof (struct nfor)),
      SHELL_ALIGN(sizeof (struct ncase)),
      SHELL_ALIGN(sizeof (struct nclist)),
      SHELL_ALIGN(sizeof (struct ndefun)),
      SHELL_ALIGN(sizeof (struct narg)),
      SHELL_ALIGN(sizeof (struct nfile)),
      SHELL_ALIGN(sizeof (struct nfile)),
      SHELL_ALIGN(sizeof (struct nfile)),
      SHELL_ALIGN(sizeof (struct nfile)),
      SHELL_ALIGN(sizeof (struct nfile)),
      SHELL_ALIGN(sizeof (struct ndup)),
      SHELL_ALIGN(sizeof (struct ndup)),
      SHELL_ALIGN(sizeof (struct nhere)),
      SHELL_ALIGN(sizeof (struct nhere)),
      SHELL_ALIGN(sizeof (struct nnot)),
};


STATIC void calcsize(union node *);
STATIC void sizenodelist(struct nodelist *);
STATIC union node *copynode(union node *);
STATIC struct nodelist *copynodelist(struct nodelist *);
STATIC char *nodesavestr(char *);

STATIC void writenode(union node *n, size_t node_size, size_t block_size);
STATIC void encodenode(union node *);
STATIC void encodenodelist(struct nodelist *);
STATIC void encodestring(const char *);

STATIC void decodenode(union node **);
STATIC void decodenodelist(struct nodelist **);
STATIC char *decodestring();

/*
 * Make a copy of a parse tree.
 */

struct funcnode *
copyfunc(union node *n)
{
	struct funcnode *f;
	size_t blocksize;

	funcblocksize = offsetof(struct funcnode, n);
	funcstringsize = 0;
	calcsize(n);
	blocksize = funcblocksize;
	f = ckmalloc(blocksize + funcstringsize);
	funcblock = (char *) f + offsetof(struct funcnode, n);
	funcstring = (char *) f + blocksize;
	copynode(n);
	f->count = 0;
	return f;
}



STATIC void
calcsize(n)
	union node *n;
{
	if (n == NULL)
		return;
	funcblocksize += nodesize[n->type];
	switch (n->type) {
	case NCMD:
		calcsize(n->ncmd.redirect);
		calcsize(n->ncmd.args);
		calcsize(n->ncmd.assign);
		break;
	case NPIPE:
		sizenodelist(n->npipe.cmdlist);
		break;
	case NREDIR:
	case NBACKGND:
	case NSUBSHELL:
		calcsize(n->nredir.redirect);
		calcsize(n->nredir.n);
		break;
	case NAND:
	case NOR:
	case NSEMI:
	case NWHILE:
	case NUNTIL:
		calcsize(n->nbinary.ch2);
		calcsize(n->nbinary.ch1);
		break;
	case NIF:
		calcsize(n->nif.elsepart);
		calcsize(n->nif.ifpart);
		calcsize(n->nif.test);
		break;
	case NFOR:
		funcstringsize += strlen(n->nfor.var) + 1;
		calcsize(n->nfor.body);
		calcsize(n->nfor.args);
		break;
	case NCASE:
		calcsize(n->ncase.cases);
		calcsize(n->ncase.expr);
		break;
	case NCLIST:
		calcsize(n->nclist.body);
		calcsize(n->nclist.pattern);
		calcsize(n->nclist.next);
		break;
	case NDEFUN:
		calcsize(n->ndefun.body);
		funcstringsize += strlen(n->ndefun.text) + 1;
		break;
	case NARG:
		sizenodelist(n->narg.backquote);
		funcstringsize += strlen(n->narg.text) + 1;
		calcsize(n->narg.next);
		break;
	case NTO:
	case NCLOBBER:
	case NFROM:
	case NFROMTO:
	case NAPPEND:
		calcsize(n->nfile.fname);
		calcsize(n->nfile.next);
		break;
	case NTOFD:
	case NFROMFD:
		calcsize(n->ndup.vname);
		calcsize(n->ndup.next);
		break;
	case NHERE:
	case NXHERE:
		calcsize(n->nhere.doc);
		calcsize(n->nhere.next);
		break;
	case NNOT:
		calcsize(n->nnot.com);
		break;
	};
}



STATIC void
sizenodelist(lp)
	struct nodelist *lp;
{
	while (lp) {
		funcblocksize += SHELL_ALIGN(sizeof(struct nodelist));
		calcsize(lp->n);
		lp = lp->next;
	}
}



STATIC union node *
copynode(n)
	union node *n;
{
	union node *new;

	if (n == NULL)
		return NULL;
	new = funcblock;
	funcblock = (char *) funcblock + nodesize[n->type];
	switch (n->type) {
	case NCMD:
		new->ncmd.redirect = copynode(n->ncmd.redirect);
		new->ncmd.args = copynode(n->ncmd.args);
		new->ncmd.assign = copynode(n->ncmd.assign);
		new->ncmd.linno = n->ncmd.linno;
		break;
	case NPIPE:
		new->npipe.cmdlist = copynodelist(n->npipe.cmdlist);
		new->npipe.backgnd = n->npipe.backgnd;
		break;
	case NREDIR:
	case NBACKGND:
	case NSUBSHELL:
		new->nredir.redirect = copynode(n->nredir.redirect);
		new->nredir.n = copynode(n->nredir.n);
		new->nredir.linno = n->nredir.linno;
		break;
	case NAND:
	case NOR:
	case NSEMI:
	case NWHILE:
	case NUNTIL:
		new->nbinary.ch2 = copynode(n->nbinary.ch2);
		new->nbinary.ch1 = copynode(n->nbinary.ch1);
		break;
	case NIF:
		new->nif.elsepart = copynode(n->nif.elsepart);
		new->nif.ifpart = copynode(n->nif.ifpart);
		new->nif.test = copynode(n->nif.test);
		break;
	case NFOR:
		new->nfor.var = nodesavestr(n->nfor.var);
		new->nfor.body = copynode(n->nfor.body);
		new->nfor.args = copynode(n->nfor.args);
		new->nfor.linno = n->nfor.linno;
		break;
	case NCASE:
		new->ncase.cases = copynode(n->ncase.cases);
		new->ncase.expr = copynode(n->ncase.expr);
		new->ncase.linno = n->ncase.linno;
		break;
	case NCLIST:
		new->nclist.body = copynode(n->nclist.body);
		new->nclist.pattern = copynode(n->nclist.pattern);
		new->nclist.next = copynode(n->nclist.next);
		break;
	case NDEFUN:
		new->ndefun.body = copynode(n->ndefun.body);
		new->ndefun.text = nodesavestr(n->ndefun.text);
		new->ndefun.linno = n->ndefun.linno;
		break;
	case NARG:
		new->narg.backquote = copynodelist(n->narg.backquote);
		new->narg.text = nodesavestr(n->narg.text);
		new->narg.next = copynode(n->narg.next);
		break;
	case NTO:
	case NCLOBBER:
	case NFROM:
	case NFROMTO:
	case NAPPEND:
		new->nfile.fname = copynode(n->nfile.fname);
		new->nfile.fd = n->nfile.fd;
		new->nfile.next = copynode(n->nfile.next);
		break;
	case NTOFD:
	case NFROMFD:
		new->ndup.vname = copynode(n->ndup.vname);
		new->ndup.dupfd = n->ndup.dupfd;
		new->ndup.fd = n->ndup.fd;
		new->ndup.next = copynode(n->ndup.next);
		break;
	case NHERE:
	case NXHERE:
		new->nhere.doc = copynode(n->nhere.doc);
		new->nhere.fd = n->nhere.fd;
		new->nhere.next = copynode(n->nhere.next);
		break;
	case NNOT:
		new->nnot.com = copynode(n->nnot.com);
		break;
	};
	new->type = n->type;
	return new;
}


STATIC struct nodelist *
copynodelist(lp)
	struct nodelist *lp;
{
	struct nodelist *start;
	struct nodelist **lpp;

	lpp = &start;
	while (lp) {
		*lpp = funcblock;
		funcblock = (char *) funcblock +
		    SHELL_ALIGN(sizeof(struct nodelist));
		(*lpp)->n = copynode(lp->n);
		lp = lp->next;
		lpp = &(*lpp)->next;
	}
	*lpp = NULL;
	return start;
}



STATIC char *
nodesavestr(s)
	char   *s;
{
	char   *rtn = funcstring;

	funcstring = stpcpy(funcstring, s) + 1;
	return rtn;
}

STATIC void writenode(union node *n, size_t node_size, size_t block_size)
{
	if (block_size > funcblocksize) {
		sh_error("Unable to encode AST");
		exraise(-1);
	}
	memcpy(funcblock, n, node_size);
	funcblock = (char *) funcblock + block_size;
	funcblocksize -= block_size;
}

STATIC void
encodenode(union node *n)
{
	if (n == NULL)
		return;
	switch (n->type) {
	case NCMD:
		writenode(n, sizeof(struct ncmd), nodesize[n->type]);
		encodenode(n->ncmd.redirect);
		encodenode(n->ncmd.args);
		encodenode(n->ncmd.assign);
		break;
	case NPIPE:
		writenode(n, sizeof(struct npipe), nodesize[n->type]);
		encodenodelist(n->npipe.cmdlist);
		break;
	case NREDIR:
	case NBACKGND:
	case NSUBSHELL:
		writenode(n, sizeof(struct nredir), nodesize[n->type]);
		encodenode(n->nredir.redirect);
		encodenode(n->nredir.n);
		break;
	case NAND:
	case NOR:
	case NSEMI:
	case NWHILE:
	case NUNTIL:
		writenode(n, sizeof(struct nbinary), nodesize[n->type]);
		encodenode(n->nbinary.ch2);
		encodenode(n->nbinary.ch1);
		break;
	case NIF:
		writenode(n, sizeof(struct nif), nodesize[n->type]);
		encodenode(n->nif.elsepart);
		encodenode(n->nif.ifpart);
		encodenode(n->nif.test);
		break;
	case NFOR:
		writenode(n, sizeof(struct nfor), nodesize[n->type]);
		encodestring(n->nfor.var);
		encodenode(n->nfor.body);
		encodenode(n->nfor.args);
		break;
	case NCASE:
		writenode(n, sizeof(struct ncase), nodesize[n->type]);
		encodenode(n->ncase.cases);
		encodenode(n->ncase.expr);
		break;
	case NCLIST:
		writenode(n, sizeof(struct nclist), nodesize[n->type]);
		encodenode(n->nclist.body);
		encodenode(n->nclist.pattern);
		encodenode(n->nclist.next);
		break;
	case NDEFUN:
		writenode(n, sizeof(struct ndefun), nodesize[n->type]);
		encodenode(n->ndefun.body);
		encodestring(n->ndefun.text);
		break;
	case NARG:
		writenode(n, sizeof(struct narg), nodesize[n->type]);
		encodenodelist(n->narg.backquote);
		encodestring(n->narg.text);
		encodenode(n->narg.next);
		break;
	case NTO:
	case NCLOBBER:
	case NFROM:
	case NFROMTO:
	case NAPPEND:
		writenode(n, sizeof(struct nfile), nodesize[n->type]);
		encodenode(n->nfile.fname);
		encodenode(n->nfile.next);
		break;
	case NTOFD:
	case NFROMFD:
		writenode(n, sizeof(struct ndup), nodesize[n->type]);
		encodenode(n->ndup.vname);
		encodenode(n->ndup.next);
		break;
	case NHERE:
	case NXHERE:
		writenode(n, sizeof(struct nhere), nodesize[n->type]);
		encodenode(n->nhere.doc);
		encodenode(n->nhere.next);
		break;
	case NNOT:
		writenode(n, sizeof(struct nnot), nodesize[n->type]);
		encodenode(n->nnot.com);
		break;
	};
}

STATIC void
encodenodelist(struct nodelist *lp)
{
	while (lp) {
		memcpy(funcblock, lp, sizeof(struct nodelist));
		funcblock = (char *) funcblock + SHELL_ALIGN(sizeof(struct nodelist));
		encodenode(lp->n);
		lp = lp->next;
	}
}

STATIC void
encodestring(const char *s)
{
	funcstring = stpcpy(funcstring, s) + 1;
}


STATIC void
decodenode(union node **npp)
{
	if (*npp == NULL)
		return;
	*npp = funcblock;
	union node *n = *npp;
	funcblock = (char *) funcblock + nodesize[n->type];
	switch (n->type) {
	case NCMD:
		decodenode(&n->ncmd.redirect);
		decodenode(&n->ncmd.args);
		decodenode(&n->ncmd.assign);
		break;
	case NPIPE:
		decodenodelist(&n->npipe.cmdlist);
		break;
	case NREDIR:
	case NBACKGND:
	case NSUBSHELL:
		decodenode(&n->nredir.redirect);
		decodenode(&n->nredir.n);
		break;
	case NAND:
	case NOR:
	case NSEMI:
	case NWHILE:
	case NUNTIL:
		decodenode(&n->nbinary.ch2);
		decodenode(&n->nbinary.ch1);
		break;
	case NIF:
		decodenode(&n->nif.elsepart);
		decodenode(&n->nif.ifpart);
		decodenode(&n->nif.test);
		break;
	case NFOR:
		n->nfor.var = decodestring();
		decodenode(&n->nfor.body);
		decodenode(&n->nfor.args);
		break;
	case NCASE:
		decodenode(&n->ncase.cases);
		decodenode(&n->ncase.expr);
		break;
	case NCLIST:
		decodenode(&n->nclist.body);
		decodenode(&n->nclist.pattern);
		decodenode(&n->nclist.next);
		break;
	case NDEFUN:
		decodenode(&n->ndefun.body);
		n->ndefun.text = decodestring();
		break;
	case NARG:
		decodenodelist(&n->narg.backquote);
		n->narg.text = decodestring();
		decodenode(&n->narg.next);
		break;
	case NTO:
	case NCLOBBER:
	case NFROM:
	case NFROMTO:
	case NAPPEND:
		decodenode(&n->nfile.fname);
		decodenode(&n->nfile.next);
		break;
	case NTOFD:
	case NFROMFD:
		decodenode(&n->ndup.vname);
		decodenode(&n->ndup.next);
		break;
	case NHERE:
	case NXHERE:
		decodenode(&n->nhere.doc);
		decodenode(&n->nhere.next);
		break;
	case NNOT:
		decodenode(&n->nnot.com);
		break;
	};
}

STATIC void
decodenodelist(struct nodelist **lpp)
{
	while (*lpp) {
		*lpp = funcblock;
		funcblock = (char *) funcblock + SHELL_ALIGN(sizeof(struct nodelist));
		struct nodelist *lp = *lpp;
		decodenode(&lp->n);
		lpp = &lp->next;
	}
}

STATIC char *
decodestring()
{
	char *result = funcstring;
	funcstring += strlen(result) + 1;
	return result;
}

/*
 * Free a parse tree.
 */

void
freefunc(struct funcnode *f)
{
	if (f && --f->count < 0)
		ckfree(f);
}

// Fuchsia-specific:
// This is the definition of the header of the VMO used for transferring initialization
// information to a subshell.  This information would be automatically inherited if we
// were able to invoke the subshell using a fork().
// For now, we pass symbol table information (non-exported symbols, those are passed in
// the environment) and a list of operations to be performed by the subshell.
struct state_header
{
	size_t total_size;
	size_t num_symbols;
	size_t symtab_offset;
	size_t cmd_offset;
	size_t string_offset;
};
static const size_t kHeaderSize = SHELL_ALIGN(sizeof(struct state_header));

static char *ignored_syms[] = { "_", "PPID", "PWD" };

static bool
ignore_sym(char *name)
{
	for (size_t sym_ndx = 0;
	     sym_ndx < sizeof(ignored_syms) / sizeof(char *);
	     sym_ndx++) {
		if (!strcmp(ignored_syms[sym_ndx], name)) {
			return true;
		}
	}
	return false;
}

// Determine the space needed to represent the NULL-terminated symbol table
// 'vars'. Also sets 'num_vars' to the number of symbol table entries.
static size_t
calc_symtab_size(char **vars, size_t *num_vars)
{
	size_t total_len = 0;
	*num_vars = 0;
	while (*vars) {
		if (! ignore_sym(*vars)) {
			// + 2 for NULL symbol flags
			total_len += strlen(*vars) + 2;
			(*num_vars)++;
		}
		vars++;
	}
	return total_len;
}

// Write symbols into 'buffer'. If 'is_readonly' is set, all variables are
// marked as such.
static size_t
output_symtab(char *buffer, char **vars, bool is_readonly)
{
	char *orig_buffer = buffer;
	while (*vars) {
		if (! ignore_sym(*vars)) {
			*buffer++ = is_readonly ? 1 : 0;
			size_t len = strlen(*vars);
			buffer = mempcpy(buffer, *vars, len + 1);
		}
		vars++;
	}
	return buffer - orig_buffer;
}

// Read in symbols from the encoded table 'buffer'. We currently only support
// two variants of variables: readonly (flags == 1) and writable (flags == 0).
static void
restore_symtab(char *buffer, size_t num_syms)
{
	while(num_syms--) {
		bool is_readonly = (*buffer++ == 1);
		setvareq(buffer, is_readonly ? VREADONLY : 0);
		buffer += (strlen(buffer) + 1);
	}
}

// The encoded format contains four segments:
//
// * A header that specifies the number of symbols, and offsets of each of
//   the three segments (see "struct state_header").
// * A symbol table. Each entry in the symbol table is a single-byte of flags
//   (1 = read-only, 0 = writable) followed by a NULL-terminted NAME=VALUE
//   string.
// * A sequence of nodes in a pre-order traversal of the node tree.
//   - The encoded size of each node is determined by its type.
//   - Pointer fields in each node contain zero if that pointer should decode
//     a NULL. Otherwise, if the pointer should decode as non-NULL, the field
//     contains an arbitrary non-zero value. (These values are the address of
//     the node or the string in the encoding process, which isn't meaningful to
//     the decoding progress).
// * A sequence of null-terminated strings, in the order the strings are
//   encountered in a pre-order traversal of the node tree.

zx_status_t
codec_encode(struct nodelist *nlist, zx_handle_t *vmo)
{
	funcblocksize = 0;
	funcstringsize = 0;
	char **writable_vars = listvars(0, VEXPORT | VREADONLY, 0);
	char **readonly_vars = listvars(VREADONLY, VEXPORT, 0);

	// Calculate the size of the components
	size_t num_writable_vars;
	size_t num_readonly_vars;
	size_t total_symtab_size = calc_symtab_size(writable_vars, &num_writable_vars) +
				   calc_symtab_size(readonly_vars, &num_readonly_vars);
	total_symtab_size = SHELL_ALIGN(total_symtab_size);
	sizenodelist(nlist);
	struct state_header header;

	// Fill in the header
	header.num_symbols = num_writable_vars + num_readonly_vars;
	header.symtab_offset = kHeaderSize;
	header.cmd_offset = header.symtab_offset + total_symtab_size;
	header.string_offset = header.cmd_offset + funcblocksize;

	char buffer[header.string_offset + funcstringsize];
	header.total_size = sizeof(buffer);

	// Output the symbol tables
	memcpy(buffer, &header, sizeof(header));
	size_t symtab_offset = header.symtab_offset;
	char* symtab = &buffer[symtab_offset];
	symtab_offset += output_symtab(symtab, writable_vars, 0);
	output_symtab(symtab, readonly_vars, 1);

	// Output the command nodes
	funcblock = buffer + header.cmd_offset;
	funcstring = buffer + header.string_offset;
	encodenodelist(nlist);

	// And VMO-ify the whole thing
	zx_status_t status = zx_vmo_create(sizeof(buffer), 0, vmo);
	if (status != ZX_OK)
		return status;
	return zx_vmo_write(*vmo, buffer, 0, sizeof(buffer));
}

struct nodelist *codec_decode(char *buffer, size_t length)
{
	struct state_header header;
	if (length < sizeof(header)) {
		return NULL;
	}
	memcpy(&header, buffer, sizeof(header));
	if (length < header.total_size) {
		return NULL;
	}

	restore_symtab(buffer + header.symtab_offset, header.num_symbols);
	funcblock = buffer + header.cmd_offset;
	funcstring = buffer + header.string_offset;
	struct nodelist dummy;
	// The decodenodelist API is very... unique. It needs the
	// argument to point to something non-NULL, even though the
	// argument is otherwise ignored and used as an output parameter.
	struct nodelist *nlist = &dummy;
	decodenodelist(&nlist);
	return nlist;
}