// parse.c - parser

//

// © Portions Copyright (c) Symbian Software Ltd 2007. All rights reserved.

//

/*

 * This file is part of zsh, the Z shell.

 *

 * Copyright (c) 1992-1997 Paul Falstad

 * All rights reserved.

 *

 * Permission is hereby granted, without written agreement and without

 * license or royalty fees, to use, copy, modify, and distribute this

 * software and to distribute modified versions of this software for any

 * purpose, provided that the above copyright notice and the following

 * two paragraphs appear in all copies of this software.

 *

 * In no event shall Paul Falstad or the Zsh Development Group be liable

 * to any party for direct, indirect, special, incidental, or consequential

 * damages arising out of the use of this software and its documentation,

 * even if Paul Falstad and the Zsh Development Group have been advised of

 * the possibility of such damage.

 *

 * Paul Falstad and the Zsh Development Group specifically disclaim any

 * warranties, including, but not limited to, the implied warranties of

 * merchantability and fitness for a particular purpose.  The software

 * provided hereunder is on an "as is" basis, and Paul Falstad and the

 * Zsh Development Group have no obligation to provide maintenance,

 * support, updates, enhancements, or modifications.

 *

 */

#include "zsh.mdh"

#include "parse.pro"

#ifdef __SYMBIAN32__

#ifdef __WINSCW__

#pragma warn_possunwant off

#endif//__WINSCW__

#endif//__SYMBIAN32__

/* != 0 if we are about to read a command word */

/**/

mod_export int incmdpos;

/**/

int aliasspaceflag;

/* != 0 if we are in the middle of a [[ ... ]] */

/**/

mod_export int incond;

/* != 0 if we are after a redirection (for ctxtlex only) */

/**/

mod_export int inredir;

/* != 0 if we are about to read a case pattern */

/**/

int incasepat;

/* != 0 if we just read a newline */

/**/

int isnewlin;

/* != 0 if we are after a for keyword */

/**/

int infor;

/* list of here-documents */

/**/

struct heredocs *hdocs;

#define YYERROR(O)  { tok = LEXERR; ecused = (O); return 0; }

#define YYERRORV(O) { tok = LEXERR; ecused = (O); return; }

#define COND_ERROR(X,Y) do { \

  zwarn(X,Y,0); \

  herrflush(); \

  if (noerrs != 2) \

    errflag = 1; \

  YYERROR(ecused) \

} while(0)

/* 

 * Word code.

 *

 * The parser now produces word code, reducing memory consumption compared

 * to the nested structs we had before.

 *

 * Word code layout:

 *

 *   WC_END

 *     - end of program code

 *

 *   WC_LIST

 *     - data contains type (sync, ...)

 *     - followed by code for this list

 *     - if not (type & Z_END), followed by next WC_LIST

 *

 *   WC_SUBLIST

 *     - data contains type (&&, ||, END) and flags (coprog, not)

 *     - followed by code for sublist

 *     - if not (type == END), followed by next WC_SUBLIST

 *

 *   WC_PIPE

 *     - data contains type (end, mid) and LINENO

 *     - if not (type == END), followed by offset to next WC_PIPE

 *     - followed by command

 *     - if not (type == END), followed by next WC_PIPE

 *

 *   WC_REDIR

 *     - must precede command-code (or WC_ASSIGN)

 *     - data contains type (<, >, ...)

 *     - followed by fd1 and name from struct redir

 *

 *   WC_ASSIGN

 *     - data contains type (scalar, array) and number of array-elements

 *     - followed by name and value

 *

 *   WC_SIMPLE

 *     - data contains the number of arguments (plus command)

 *     - followed by strings

 *

 *   WC_SUBSH

 *     - data unused

 *     - followed by list

 *

 *   WC_CURSH

 *     - data unused

 *     - followed by list

 *

 *   WC_TIMED

 *     - data contains type (followed by pipe or not)

 *     - if (type == PIPE), followed by pipe

 *

 *   WC_FUNCDEF

 *     - data contains offset to after body

 *     - followed by number of names

 *     - followed by names

 *     - followed by offset to first string

 *     - followed by length of string table

 *     - followed by number of patterns for body

 *     - followed by codes for body

 *     - followed by strings for body

 *

 *   WC_FOR

 *     - data contains type (list, ...) and offset to after body

 *     - if (type == COND), followed by init, cond, advance expressions

 *     - else if (type == PPARAM), followed by param name

 *     - else if (type == LIST), followed by param name, num strings, strings

 *     - followed by body

 *

 *   WC_SELECT

 *     - data contains type (list, ...) and offset to after body

 *     - if (type == PPARAM), followed by param name

 *     - else if (type == LIST), followed by param name, num strings, strings

 *     - followed by body

 *

 *   WC_WHILE

 *     - data contains type (while, until) and offset to after body

 *     - followed by condition

 *     - followed by body

 *

 *   WC_REPEAT

 *     - data contains offset to after body

 *     - followed by number-string

 *     - followed by body

 *

 *   WC_CASE

 *     - first CASE is always of type HEAD, data contains offset to esac

 *     - after that CASEs of type OR (;;) and AND (;&), data is offset to

 *       next case

 *     - each OR/AND case is followed by pattern, pattern-number, list

 *

 *   WC_IF

 *     - first IF is of type HEAD, data contains offset to fi

 *     - after that IFs of type IF, ELIF, ELSE, data is offset to next

 *     - each non-HEAD is followed by condition (only IF, ELIF) and body

 *

 *   WC_COND

 *     - data contains type

 *     - if (type == AND/OR), data contains offset to after this one,

 *       followed by two CONDs

 *     - else if (type == NOT), followed by COND

 *     - else if (type == MOD), followed by name and strings

 *     - else if (type == MODI), followed by name, left, right

 *     - else if (type == STR[N]EQ), followed by left, right, pattern-number

 *     - else if (has two args) followed by left, right

 *     - else followed by string

 *

 *   WC_ARITH

 *     - followed by string (there's only one)

 *

 *   WC_AUTOFN

 *     - only used by the autoload builtin

 *

 * Lists and sublists may also be simplified, indicated by the presence

 * of the Z_SIMPLE or WC_SUBLIST_SIMPLE flags. In this case they are only

 * followed by a slot containing the line number, not by a WC_SUBLIST or

 * WC_PIPE, respectively. The real advantage of simplified lists and

 * sublists is that they can be executed faster, see exec.c. In the

 * parser, the test if a list can be simplified is done quite simply

 * by passing a int* around which gets set to non-zero if the thing

 * just parsed is `complex', i.e. may need to be run by forking or 

 * some such.

 *

 * In each of the above, strings are encoded as one word code. For empty

 * strings this is the bit pattern 11x, the lowest bit is non-zero if the

 * string contains tokens and zero otherwise (this is true for the other

 * ways to encode strings, too). For short strings (one to three

 * characters), this is the marker 01x with the 24 bits above that

 * containing the characters. Longer strings are encoded as the offset

 * into the strs character array stored in the eprog struct shifted by

 * two and ored with the bit pattern 0x.

 * The ecstrcode() function that adds the code for a string uses a simple

 * binary tree of strings already added so that long strings are encoded

 * only once.

 *

 * Note also that in the eprog struct the pattern, code, and string

 * arrays all point to the same memory block.

 *

 *

 * To make things even faster in future versions, we could not only 

 * test if the strings contain tokens, but instead what kind of

 * expansions need to be done on strings. In the execution code we

 * could then use these flags for a specialized version of prefork()

 * to avoid a lot of string parsing and some more string duplication.

 */

/**/

int eclen, ecused, ecnpats;

/**/

Wordcode ecbuf;

/**/

Eccstr ecstrs;

/**/

int ecsoffs, ecssub, ecnfunc;

#define EC_INIT_SIZE         256

#define EC_DOUBLE_THRESHOLD  32768

#define EC_INCREMENT         1024

/* Adjust pointers in here-doc structs. */

static void

ecadjusthere(int p, int d)

{

    struct heredocs *h;

    for (h = hdocs; h; h = h->next)

	if (h->pc >= p)

	    h->pc += d;

}

/* Insert n free code-slots at position p. */

static void

ecispace(int p, int n)

{

    int m;

    if ((eclen - ecused) < n) {

	int a = (eclen < EC_DOUBLE_THRESHOLD ? eclen : EC_INCREMENT);

	if (n > a) a = n;

	ecbuf = (Wordcode) zrealloc((char *) ecbuf, (eclen + a) * sizeof(wordcode));

	eclen += a;

    }

    if ((m = ecused - p) > 0)

	memmove(ecbuf + p + n, ecbuf + p, m * sizeof(wordcode));

    ecused += n;

    ecadjusthere(p, n);

}

/* Add one wordcode. */

static int

ecadd(wordcode c)

{

    if ((eclen - ecused) < 1) {

	int a = (eclen < EC_DOUBLE_THRESHOLD ? eclen : EC_INCREMENT);

	ecbuf = (Wordcode) zrealloc((char *) ecbuf, (eclen + a) * sizeof(wordcode));

	eclen += a;

    }

    ecbuf[ecused] = c;

    ecused++;

    return ecused - 1;

}

/* Delete a wordcode. */

static void

ecdel(int p)

{

    int n = ecused - p - 1;

    if (n > 0)

	memmove(ecbuf + p, ecbuf + p + 1, n * sizeof(wordcode));

    ecused--;

    ecadjusthere(p, -1);

}

/* Build the wordcode for a string. */

static wordcode

ecstrcode(char *s)

{

    int l, t = has_token(s);

    if ((l = strlen(s) + 1) && l <= 4) {

	wordcode c = (t ? 3 : 2);

	switch (l) {

	case 4: c |= ((wordcode) STOUC(s[2])) << 19;

	case 3: c |= ((wordcode) STOUC(s[1])) << 11;

	case 2: c |= ((wordcode) STOUC(s[0])) <<  3; break;

	case 1: c = (t ? 7 : 6); break;

	}

	return c;

    } else {

	Eccstr p, *pp;

	int cmp;

	for (pp = &ecstrs; (p = *pp); ) {

	    if (!(cmp = p->nfunc - ecnfunc) && !(cmp = strcmp(p->str, s)))

		return p->offs;

	    pp = (cmp < 0 ? &(p->left) : &(p->right));

	}

	p = *pp = (Eccstr) zhalloc(sizeof(*p));

	p->left = p->right = 0;

	p->offs = ((ecsoffs - ecssub) << 2) | (t ? 1 : 0);

	p->aoffs = ecsoffs;

	p->str = s;

	p->nfunc = ecnfunc;

	ecsoffs += l;

	return p->offs;

    }

}

#define ecstr(S) ecadd(ecstrcode(S))

#define par_save_list(C) \

    do { \

        int eu = ecused; \

        par_list(C); \

        if (eu == ecused) ecadd(WCB_END()); \

    } while (0)

#define par_save_list1(C) \

    do { \

        int eu = ecused; \

        par_list1(C); \

        if (eu == ecused) ecadd(WCB_END()); \

    } while (0)

/* Initialise wordcode buffer. */

static void

init_parse(void)

{

    if (ecbuf) zfree(ecbuf, eclen);

    ecbuf = (Wordcode) zalloc((eclen = EC_INIT_SIZE) * sizeof(wordcode));

    ecused = 0;

    ecstrs = NULL;

    ecsoffs = ecnpats = 0;

    ecssub = 0;

    ecnfunc = 0;

}

/* Build eprog. */

static void

copy_ecstr(Eccstr s, char *p)

{

    while (s) {

	memcpy(p + s->aoffs, s->str, strlen(s->str) + 1);

	copy_ecstr(s->left, p);

	s = s->right;

    }

}

static Eprog

bld_eprog(void)

{

    Eprog ret;

    int l;

    ecadd(WCB_END());

    ret = (Eprog) zhalloc(sizeof(*ret));

    ret->len = ((ecnpats * sizeof(Patprog)) +

		(ecused * sizeof(wordcode)) +

		ecsoffs);

    ret->npats = ecnpats;

    ret->nref = -1;		/* Eprog is on the heap */

    ret->pats = (Patprog *) zhalloc(ret->len);

    ret->prog = (Wordcode) (ret->pats + ecnpats);

    ret->strs = (char *) (ret->prog + ecused);

    ret->shf = NULL;

    ret->flags = EF_HEAP;

    ret->dump = NULL;

    for (l = 0; l < ecnpats; l++)

	ret->pats[l] = dummy_patprog1;

    memcpy(ret->prog, ecbuf, ecused * sizeof(wordcode));

    copy_ecstr(ecstrs, ret->strs);

    zfree(ecbuf, eclen);

    ecbuf = NULL;

    return ret;

}

/**/

mod_export int

empty_eprog(Eprog p)

{

    return (!p || !p->prog || *p->prog == WCB_END());

}

static void

clear_hdocs()

{

    struct heredocs *p, *n;

    for (p = hdocs; p; p = n) {

        n = p->next;

        zfree(p, sizeof(struct heredocs));

    }

    hdocs = NULL;

}

/*

 * event	: ENDINPUT

 *			| SEPER

 *			| sublist [ SEPER | AMPER | AMPERBANG ]

 */

/**/

Eprog

parse_event(void)

{

    tok = ENDINPUT;

    incmdpos = 1;

    aliasspaceflag = 0;

    yylex();

    init_parse();

    if (!par_event()) {

        clear_hdocs();

        return NULL;

    }

    return bld_eprog();

}

/**/

static int

par_event(void)

{

    int r = 0, p, c = 0;

    while (tok == SEPER) {

	if (isnewlin > 0)

	    return 0;

	yylex();

    }

    if (tok == ENDINPUT)

	return 0;

    p = ecadd(0);

    if (par_sublist(&c)) {

	if (tok == ENDINPUT) {

	    set_list_code(p, Z_SYNC, c);

	    r = 1;

	} else if (tok == SEPER) {

	    set_list_code(p, Z_SYNC, c);

	    if (isnewlin <= 0)

		yylex();

	    r = 1;

	} else if (tok == AMPER) {

	    set_list_code(p, Z_ASYNC, c);

	    yylex();

	    r = 1;

	} else if (tok == AMPERBANG) {

	    set_list_code(p, (Z_ASYNC | Z_DISOWN), c);

	    yylex();

	    r = 1;

	}

    }

    if (!r) {

	tok = LEXERR;

	if (errflag) {

	    yyerror(0);

	    ecused--;

	    return 0;

	}

	yyerror(1);

	herrflush();

	if (noerrs != 2)

	    errflag = 1;

	ecused--;

	return 0;

    } else {

	int oec = ecused;

	if (!par_event()) {

	    ecused = oec;

	    ecbuf[p] |= wc_bdata(Z_END);

	}

    }

    return 1;

}

/**/

mod_export Eprog

parse_list(void)