eval.c

Go to the documentation of this file.

/*
 * eval.c - gawk parse tree interpreter 
 */

/* 
 * Copyright (C) 1986, 1988, 1989, 1991-2003 the Free Software Foundation, Inc.
 * 
 * This file is part of GAWK, the GNU implementation of the
 * AWK Programming Language.
 * 
 * GAWK is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * GAWK is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA
 */

#include "awk.h"

extern double pow P((double x, double y));
extern double modf P((double x, double *yp));
extern double fmod P((double x, double y));

static int eval_condition P((NODE *tree));
static NODE *op_assign P((NODE *tree));
static NODE *func_call P((NODE *tree));
static NODE *match_op P((NODE *tree));
static void pop_forloop P((void));
static inline void pop_all_forloops P((void));
static void push_forloop P((const char *varname, NODE **elems, size_t nelems));
static void push_args P((int count, NODE *arglist, NODE **oldstack,
                        const char *func_name, char **varnames));
static inline void pop_fcall_stack P((void));
static void pop_fcall P((void));
static int comp_func P((const void *p1, const void *p2));

#if __GNUC__ < 2
NODE *_t;               /* used as a temporary in macros */
#endif
#ifdef MSDOS
double _msc51bug;       /* to get around a bug in MSC 5.1 */
#endif
NODE *ret_node;
int OFSlen;
int ORSlen;
int OFMTidx;
int CONVFMTidx;

/* Profiling stuff */
#ifdef PROFILING
#define INCREMENT(n)    n++
#else
#define INCREMENT(n)    /* nothing */
#endif

/* Macros and variables to save and restore function and loop bindings */
/*
 * the val variable allows return/continue/break-out-of-context to be
 * caught and diagnosed
 */
#define PUSH_BINDING(stack, x, val) (memcpy((char *)(stack), (const char *)(x), sizeof(jmp_buf)), val++)
#define RESTORE_BINDING(stack, x, val) (memcpy((char *)(x), (const char *)(stack), sizeof(jmp_buf)), val--)

static jmp_buf loop_tag;                /* always the current binding */
static int loop_tag_valid = FALSE;      /* nonzero when loop_tag valid */
static int func_tag_valid = FALSE;
static jmp_buf func_tag;
extern int exiting, exit_val;

/* This rather ugly macro is for VMS C */
#ifdef C
#undef C
#endif
#define C(c) ((char)c)  
/*
 * This table is used by the regexp routines to do case independant
 * matching. Basically, every ascii character maps to itself, except
 * uppercase letters map to lower case ones. This table has 256
 * entries, for ISO 8859-1. Note also that if the system this
 * is compiled on doesn't use 7-bit ascii, casetable[] should not be
 * defined to the linker, so gawk should not load.
 *
 * Do NOT make this array static, it is used in several spots, not
 * just in this file.
 */
#if 'a' == 97   /* it's ascii */
const char casetable[] = {
        '\000', '\001', '\002', '\003', '\004', '\005', '\006', '\007',
        '\010', '\011', '\012', '\013', '\014', '\015', '\016', '\017',
        '\020', '\021', '\022', '\023', '\024', '\025', '\026', '\027',
        '\030', '\031', '\032', '\033', '\034', '\035', '\036', '\037',
        /* ' '     '!'     '"'     '#'     '$'     '%'     '&'     ''' */
        '\040', '\041', '\042', '\043', '\044', '\045', '\046', '\047',
        /* '('     ')'     '*'     '+'     ','     '-'     '.'     '/' */
        '\050', '\051', '\052', '\053', '\054', '\055', '\056', '\057',
        /* '0'     '1'     '2'     '3'     '4'     '5'     '6'     '7' */
        '\060', '\061', '\062', '\063', '\064', '\065', '\066', '\067',
        /* '8'     '9'     ':'     ';'     '<'     '='     '>'     '?' */
        '\070', '\071', '\072', '\073', '\074', '\075', '\076', '\077',
        /* '@'     'A'     'B'     'C'     'D'     'E'     'F'     'G' */
        '\100', '\141', '\142', '\143', '\144', '\145', '\146', '\147',
        /* 'H'     'I'     'J'     'K'     'L'     'M'     'N'     'O' */
        '\150', '\151', '\152', '\153', '\154', '\155', '\156', '\157',
        /* 'P'     'Q'     'R'     'S'     'T'     'U'     'V'     'W' */
        '\160', '\161', '\162', '\163', '\164', '\165', '\166', '\167',
        /* 'X'     'Y'     'Z'     '['     '\'     ']'     '^'     '_' */
        '\170', '\171', '\172', '\133', '\134', '\135', '\136', '\137',
        /* '`'     'a'     'b'     'c'     'd'     'e'     'f'     'g' */
        '\140', '\141', '\142', '\143', '\144', '\145', '\146', '\147',
        /* 'h'     'i'     'j'     'k'     'l'     'm'     'n'     'o' */
        '\150', '\151', '\152', '\153', '\154', '\155', '\156', '\157',
        /* 'p'     'q'     'r'     's'     't'     'u'     'v'     'w' */
        '\160', '\161', '\162', '\163', '\164', '\165', '\166', '\167',
        /* 'x'     'y'     'z'     '{'     '|'     '}'     '~' */
        '\170', '\171', '\172', '\173', '\174', '\175', '\176', '\177',

        /* Latin 1: */
        C('\200'), C('\201'), C('\202'), C('\203'), C('\204'), C('\205'), C('\206'), C('\207'),
        C('\210'), C('\211'), C('\212'), C('\213'), C('\214'), C('\215'), C('\216'), C('\217'),
        C('\220'), C('\221'), C('\222'), C('\223'), C('\224'), C('\225'), C('\226'), C('\227'),
        C('\230'), C('\231'), C('\232'), C('\233'), C('\234'), C('\235'), C('\236'), C('\237'),
        C('\240'), C('\241'), C('\242'), C('\243'), C('\244'), C('\245'), C('\246'), C('\247'),
        C('\250'), C('\251'), C('\252'), C('\253'), C('\254'), C('\255'), C('\256'), C('\257'),
        C('\260'), C('\261'), C('\262'), C('\263'), C('\264'), C('\265'), C('\266'), C('\267'),
        C('\270'), C('\271'), C('\272'), C('\273'), C('\274'), C('\275'), C('\276'), C('\277'),
        C('\340'), C('\341'), C('\342'), C('\343'), C('\344'), C('\345'), C('\346'), C('\347'),
        C('\350'), C('\351'), C('\352'), C('\353'), C('\354'), C('\355'), C('\356'), C('\357'),
        C('\360'), C('\361'), C('\362'), C('\363'), C('\364'), C('\365'), C('\366'), C('\327'),
        C('\370'), C('\371'), C('\372'), C('\373'), C('\374'), C('\375'), C('\376'), C('\337'),
        C('\340'), C('\341'), C('\342'), C('\343'), C('\344'), C('\345'), C('\346'), C('\347'),
        C('\350'), C('\351'), C('\352'), C('\353'), C('\354'), C('\355'), C('\356'), C('\357'),
        C('\360'), C('\361'), C('\362'), C('\363'), C('\364'), C('\365'), C('\366'), C('\367'),
        C('\370'), C('\371'), C('\372'), C('\373'), C('\374'), C('\375'), C('\376'), C('\377'),
};
#else
#include "You lose. You will need a translation table for your character set."
#endif

#undef C

/*
 * This table maps node types to strings for debugging.
 * KEEP IN SYNC WITH awk.h!!!!
 */
static const char *const nodetypes[] = {
        "Node_illegal",
        "Node_times",
        "Node_quotient",
        "Node_mod",
        "Node_plus",
        "Node_minus",
        "Node_cond_pair",
        "Node_subscript",
        "Node_concat",
        "Node_exp",
        "Node_preincrement",
        "Node_predecrement",
        "Node_postincrement",
        "Node_postdecrement",
        "Node_unary_minus",
        "Node_field_spec",
        "Node_assign",
        "Node_assign_times",
        "Node_assign_quotient",
        "Node_assign_mod",
        "Node_assign_plus",
        "Node_assign_minus",
        "Node_assign_exp",
        "Node_and",
        "Node_or",
        "Node_equal",
        "Node_notequal",
        "Node_less",
        "Node_greater",
        "Node_leq",
        "Node_geq",
        "Node_match",
        "Node_nomatch",
        "Node_not",
        "Node_rule_list",
        "Node_rule_node",
        "Node_statement_list",
        "Node_switch_body",
        "Node_case_list",
        "Node_if_branches",
        "Node_expression_list",
        "Node_param_list",
        "Node_K_if",
        "Node_K_switch",
        "Node_K_case",
        "Node_K_default",
        "Node_K_while", 
        "Node_K_for",
        "Node_K_arrayfor",
        "Node_K_break",
        "Node_K_continue",
        "Node_K_print",
        "Node_K_print_rec",
        "Node_K_printf",
        "Node_K_next",
        "Node_K_exit",
        "Node_K_do",
        "Node_K_return",
        "Node_K_delete",
        "Node_K_delete_loop",
        "Node_K_getline",
        "Node_K_function",
        "Node_K_nextfile",
        "Node_redirect_output",
        "Node_redirect_append",
        "Node_redirect_pipe",
        "Node_redirect_pipein",
        "Node_redirect_input",
        "Node_redirect_twoway",
        "Node_var_new",
        "Node_var",
        "Node_var_array",
        "Node_val",
        "Node_builtin",
        "Node_line_range",
        "Node_in_array",
        "Node_func",
        "Node_func_call",
        "Node_cond_exp",
        "Node_regex",
        "Node_dynregex",
        "Node_hashnode",
        "Node_ahash",
        "Node_array_ref",
        "Node_BINMODE",
        "Node_CONVFMT",
        "Node_FIELDWIDTHS",
        "Node_FNR",
        "Node_FS",
        "Node_IGNORECASE",
        "Node_LINT",
        "Node_NF",
        "Node_NR",
        "Node_OFMT",
        "Node_OFS",
        "Node_ORS",
        "Node_RS",
        "Node_TEXTDOMAIN",
        "Node_final --- this should never appear",
        NULL
};

/* nodetype2str --- convert a node type into a printable value */

const char *
nodetype2str(NODETYPE type)
{
        static char buf[40];

        if (type >= Node_illegal && type <= Node_final)
                return nodetypes[(int) type];

        sprintf(buf, _("unknown nodetype %d"), (int) type);
        return buf;
}

/* flags2str --- make a flags value readable */

const char *
flags2str(int flagval)
{
        static const struct flagtab values[] = {
                { MALLOC, "MALLOC" },
                { TEMP, "TEMP" },
                { PERM, "PERM" },
                { STRING, "STRING" },
                { STRCUR, "STRCUR" },
                { NUMCUR, "NUMCUR" },
                { NUMBER, "NUMBER" },
                { MAYBE_NUM, "MAYBE_NUM" },
                { ARRAYMAXED, "ARRAYMAXED" },
                { FUNC, "FUNC" },
                { FIELD, "FIELD" },
                { INTLSTR, "INTLSTR" },
                { 0,    NULL },
        };

        return genflags2str(flagval, values);
}

/* genflags2str --- general routine to convert a flag value to a string */

const char *
genflags2str(int flagval, const struct flagtab *tab)
{
        static char buffer[BUFSIZ];
        char *sp;
        int i, space_left, space_needed;

        sp = buffer;
        space_left = BUFSIZ;
        for (i = 0; tab[i].name != NULL; i++) {
                /*
                 * note the trick, we want 1 or 0 for whether we need
                 * the '|' character.
                 */
                space_needed = (strlen(tab[i].name) + (sp != buffer));
                if (space_left < space_needed)
                        fatal(_("buffer overflow in genflags2str"));

                if ((flagval & tab[i].val) != 0) {
                        if (sp != buffer) {
                                *sp++ = '|';
                                space_left--;
                        }
                        strcpy(sp, tab[i].name);
                        /* note ordering! */
                        space_left -= strlen(sp);
                        sp += strlen(sp);
                }
        }

        return buffer;
}

/*
 * interpret:
 * Tree is a bunch of rules to run. Returns zero if it hit an exit()
 * statement 
 */
int
interpret(register NODE *volatile tree)
{
        jmp_buf volatile loop_tag_stack; /* shallow binding stack for loop_tag */
        static jmp_buf rule_tag; /* tag the rule currently being run, for NEXT
                                  * and EXIT statements.  It is static because
                                  * there are no nested rules */
        register NODE *volatile t = NULL;       /* temporary */
        NODE **volatile lhs;    /* lhs == Left Hand Side for assigns, etc */
        NODE *volatile stable_tree;
        int volatile traverse = TRUE;   /* True => loop thru tree (Node_rule_list) */

        /* avoid false source indications */
        source = NULL;
        sourceline = 0;

        if (tree == NULL)
                return 1;
        sourceline = tree->source_line;
        source = tree->source_file;
        switch (tree->type) {
        case Node_rule_node:
                traverse = FALSE;  /* False => one for-loop iteration only */
                /* FALL THROUGH */
        case Node_rule_list:
                for (t = tree; t != NULL; t = t->rnode) {
                        if (traverse)
                                tree = t->lnode;
                        sourceline = tree->source_line;
                        source = tree->source_file;
                        INCREMENT(tree->exec_count);
                        switch (setjmp(rule_tag)) {
                        case 0: /* normal non-jump */
                                /* test pattern, if any */
                                if (tree->lnode == NULL ||
                                    eval_condition(tree->lnode)) {
                                        /* using the lnode exec_count is kludgey */
                                        if (tree->lnode != NULL)
                                                INCREMENT(tree->lnode->exec_count);
                                        (void) interpret(tree->rnode);
                                }
                                break;
                        case TAG_CONTINUE:      /* NEXT statement */
                                pop_all_forloops();
                                pop_fcall_stack();
                                return 1;
                        case TAG_BREAK:         /* EXIT statement */
                                pop_all_forloops();
                                pop_fcall_stack();
                                return 0;
                        default:
                                cant_happen();
                        }
                        if (! traverse)         /* case Node_rule_node */
                                break;          /* don't loop */
                }
                break;

        case Node_statement_list:
                for (t = tree; t != NULL; t = t->rnode)
                        (void) interpret(t->lnode);
                break;

        case Node_K_if:
                INCREMENT(tree->exec_count);
                if (eval_condition(tree->lnode)) {
                        INCREMENT(tree->rnode->exec_count);
                        (void) interpret(tree->rnode->lnode);
                } else {
                        (void) interpret(tree->rnode->rnode);
                }
                break;

        case Node_K_switch:
                {
                NODE *switch_value;
                NODE *switch_body;
                NODE *case_list;
                NODE *default_list;
                NODE *case_stmt;

                int match_found = FALSE;

                PUSH_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                INCREMENT(tree->exec_count);
                stable_tree = tree;

                switch_value = tree_eval(stable_tree->lnode);
                switch_body = stable_tree->rnode;
                case_list = switch_body->lnode;
                default_list  = switch_body->rnode;

                for (; case_list != NULL; case_list = case_list->rnode) {
                        case_stmt = case_list->lnode;

                        /*
                         * Once a match is found, all cases will be processed as they fall through,
                         * so continue to execute statements until a break is reached.
                         */
                        if (! match_found) {
                                if (case_stmt->type == Node_K_default)
                                        ;       /* do nothing */
                                else if (case_stmt->lnode->type == Node_regex) {
                                        NODE *t1;
                                        Regexp *rp;

                                        t1 = force_string(switch_value);
                                        rp = re_update(case_stmt->lnode);

                                        match_found = (research(rp, t1->stptr, 0, t1->stlen, FALSE) >= 0);
                                        if (t1 != switch_value)
                                                free_temp(t1);
                                } else {
                                        match_found = (cmp_nodes(switch_value, case_stmt->lnode) == 0);
                                }
                        }

                        /* If a match was found, execute the statements associated with the case. */
                        if (match_found) {
                                INCREMENT(case_stmt->exec_count);
                                switch (setjmp(loop_tag)) {
                                case 0:                /* Normal non-jump    */
                                        (void) interpret(case_stmt->rnode);
                                        break;
                                case TAG_CONTINUE:     /* continue statement */
                                        free_temp(switch_value);
                                        RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                                        longjmp(loop_tag, TAG_CONTINUE);
                                        break;
                                case TAG_BREAK:        /* break statement    */
                                        free_temp(switch_value);
                                        RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                                        return 1;
                                default:
                                        cant_happen();
                                }
                        }

                }

                free_temp(switch_value);

                /*
                 * If a default section was found, execute the statements associated with it
                 * and execute any trailing case statements if the default falls through.
                 */
                if (! match_found && default_list != NULL) {
                        for (case_list = default_list;
                                        case_list != NULL; case_list = case_list->rnode) {
                                case_stmt = case_list->lnode;

                                INCREMENT(case_stmt->exec_count);
                                switch (setjmp(loop_tag)) {
                                case 0:                /* Normal non-jump    */
                                        (void) interpret(case_stmt->rnode);
                                        break;
                                case TAG_CONTINUE:     /* continue statement */
                                        RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                                        longjmp(loop_tag, TAG_CONTINUE);
                                        break;
                                case TAG_BREAK:        /* break statement    */
                                        RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                                        return 1;
                                default:
                                        cant_happen();
                                }
                        }
                }

                RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                }
                break;

        case Node_K_while:
                PUSH_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);

                stable_tree = tree;
                while (eval_condition(stable_tree->lnode)) {
                        INCREMENT(stable_tree->exec_count);
                        switch (setjmp(loop_tag)) {
                        case 0: /* normal non-jump */
                                (void) interpret(stable_tree->rnode);
                                break;
                        case TAG_CONTINUE:      /* continue statement */
                                break;
                        case TAG_BREAK: /* break statement */
                                RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                                return 1;
                        default:
                                cant_happen();
                        }
                }
                RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                break;

        case Node_K_do:
                PUSH_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                stable_tree = tree;
                do {
                        INCREMENT(stable_tree->exec_count);
                        switch (setjmp(loop_tag)) {
                        case 0: /* normal non-jump */
                                (void) interpret(stable_tree->rnode);
                                break;
                        case TAG_CONTINUE:      /* continue statement */
                                break;
                        case TAG_BREAK: /* break statement */
                                RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                                return 1;
                        default:
                                cant_happen();
                        }
                } while (eval_condition(stable_tree->lnode));
                RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                break;

        case Node_K_for:
                PUSH_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                (void) interpret(tree->forloop->init);
                stable_tree = tree;
                while (eval_condition(stable_tree->forloop->cond)) {
                        INCREMENT(stable_tree->exec_count);
                        switch (setjmp(loop_tag)) {
                        case 0: /* normal non-jump */
                                (void) interpret(stable_tree->lnode);
                                /* fall through */
                        case TAG_CONTINUE:      /* continue statement */
                                (void) interpret(stable_tree->forloop->incr);
                                break;
                        case TAG_BREAK: /* break statement */
                                RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                                return 1;
                        default:
                                cant_happen();
                        }
                }
                RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                break;

        case Node_K_arrayfor:
                {
                Func_ptr after_assign = NULL;
                NODE **list = NULL;
                NODE *volatile array;
                NODE *volatile save_array;
                volatile size_t i, num_elems;
                size_t j;
                volatile int retval = 0;
                int sort_indices = whiny_users;

#define hakvar forloop->init
#define arrvar forloop->incr
                /* get the array */
                save_array = tree->arrvar;
                array = get_array(save_array);

                /* sanity: do nothing if empty */
                if (array->var_array == NULL || array->table_size == 0)
                        break;  /* from switch */

                /* allocate space for array */
                num_elems = array->table_size;
                emalloc(list, NODE **, num_elems * sizeof(NODE *), "for_loop");

                /* populate it */
                for (i = j = 0; i < array->array_size; i++) {
                        NODE *t = array->var_array[i];

                        if (t == NULL)
                                continue;

                        for (; t != NULL; t = t->ahnext) {
                                list[j++] = dupnode(t);
                                assert(list[j-1] == t);
                        }
                }


                if (sort_indices)
                        qsort(list, num_elems, sizeof(NODE *), comp_func); /* shazzam! */

                /* now we can run the loop */
                push_forloop(array->vname, list, num_elems);
                PUSH_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);

                lhs = get_lhs(tree->hakvar, &after_assign, FALSE);
                stable_tree = tree;
                for (i = 0; i < num_elems; i++) {
                        INCREMENT(stable_tree->exec_count);
                        unref(*((NODE **) lhs));
                        *lhs = make_string(list[i]->ahname_str, list[i]->ahname_len);
                        if (after_assign)
                                (*after_assign)();
                        switch (setjmp(loop_tag)) {
                        case 0:
                                (void) interpret(stable_tree->lnode);
                        case TAG_CONTINUE:
                                break;

                        case TAG_BREAK:
                                retval = 1;
                                goto done;

                        default:
                                cant_happen();
                        }
                }

        done:
                RESTORE_BINDING(loop_tag_stack, loop_tag, loop_tag_valid);
                pop_forloop();

                if (do_lint && num_elems != array->table_size)
                        lintwarn(_("for loop: array `%s' changed size from %ld to %ld during loop execution"),
                                array_vname(save_array), (long) num_elems, (long) array->table_size);
                
                if (retval == 1)
                        return 1;
                break;
                }
#undef hakvar
#undef arrvar

        case Node_K_break:
                INCREMENT(tree->exec_count);
                if (! loop_tag_valid) {
                        /*
                         * Old AT&T nawk treats break outside of loops like
                         * next. New ones catch it at parse time. Allow it if
                         * do_traditional is on, and complain if lint.
                         */
                        static int warned = FALSE;

                        if (do_lint && ! warned) {
                                lintwarn(_("`break' outside a loop is not portable"));
                                warned = TRUE;
                        }
                        if (! do_traditional || do_posix)
                                fatal(_("`break' outside a loop is not allowed"));
                        longjmp(rule_tag, TAG_CONTINUE);
                } else
                        longjmp(loop_tag, TAG_BREAK);
                break;

        case Node_K_continue:
                INCREMENT(tree->exec_count);
                if (! loop_tag_valid) {
                        /*
                         * Old AT&T nawk treats continue outside of loops like
                         * next. New ones catch it at parse time. Allow it if
                         * do_traditional is on, and complain if lint.
                         */
                        static int warned = FALSE;

                        if (do_lint && ! warned) {
                                lintwarn(_("`continue' outside a loop is not portable"));
                                warned = TRUE;
                        }
                        if (! do_traditional || do_posix)
                                fatal(_("`continue' outside a loop is not allowed"));
                        longjmp(rule_tag, TAG_CONTINUE);
                } else
                        longjmp(loop_tag, TAG_CONTINUE);
                break;

        case Node_K_print:
                INCREMENT(tree->exec_count);
                do_print(tree);
                break;

        case Node_K_print_rec:
                INCREMENT(tree->exec_count);
                do_print_rec(tree);
                break;

        case Node_K_printf:
                INCREMENT(tree->exec_count);
                do_printf(tree);
                break;

        case Node_K_delete:
                INCREMENT(tree->exec_count);
                do_delete(tree->lnode, tree->rnode);
                break;

        case Node_K_delete_loop:
                INCREMENT(tree->exec_count);
                do_delete_loop(tree->lnode, tree->rnode);
                break;

        case Node_K_next:
                INCREMENT(tree->exec_count);
                if (in_begin_rule)
                        fatal(_("`next' cannot be called from a BEGIN rule"));
                else if (in_end_rule)
                        fatal(_("`next' cannot be called from an END rule"));

                /* could add a lint check here for in a loop or function */
                longjmp(rule_tag, TAG_CONTINUE);
                break;

        case Node_K_nextfile:
                INCREMENT(tree->exec_count);
                if (in_begin_rule)
                        fatal(_("`nextfile' cannot be called from a BEGIN rule"));
                else if (in_end_rule)
                        fatal(_("`nextfile' cannot be called from an END rule"));

                /* could add a lint check here for in a loop or function */
                /*
                 * Have to do this cleanup here, since we don't longjump
                 * back to the main awk rule loop (rule_tag).
                 */
                pop_all_forloops();
                pop_fcall_stack();

                do_nextfile();
                break;

        case Node_K_exit:
                INCREMENT(tree->exec_count);
                /*
                 * In A,K,&W, p. 49, it says that an exit statement "...
                 * causes the program to behave as if the end of input had
                 * occurred; no more input is read, and the END actions, if
                 * any are executed." This implies that the rest of the rules
                 * are not done. So we immediately break out of the main loop.
                 */
                exiting = TRUE;
                if (tree->lnode != NULL) {
                        t = tree_eval(tree->lnode);
                        exit_val = (int) force_number(t);
                        free_temp(t);
                }
                longjmp(rule_tag, TAG_BREAK);
                break;

        case Node_K_return:
                INCREMENT(tree->exec_count);
                t = tree_eval(tree->lnode);
                ret_node = dupnode(t);
                free_temp(t);
                longjmp(func_tag, TAG_RETURN);
                break;

        default:
                /*
                 * Appears to be an expression statement.  Throw away the
                 * value. 
                 */
                if (do_lint && (tree->type == Node_var || tree->type == Node_var_new))
                        lintwarn(_("statement has no effect"));
                INCREMENT(tree->exec_count);
                t = tree_eval(tree);
                if (t)  /* stopme() returns NULL */
                        free_temp(t);
                break;
        }
        return 1;
}

/* r_tree_eval --- evaluate a subtree */

NODE *
r_tree_eval(register NODE *tree, int iscond)
{
        register NODE *r, *t1, *t2;     /* return value & temporary subtrees */
        register NODE **lhs;
        register int di;
        AWKNUM x, x1, x2;
        long lx;
#ifdef _CRAY
        long lx2;
#endif

#ifndef TREE_EVAL_MACRO
        if (tree == NULL)
                return Nnull_string;
        else if (tree->type == Node_val) {
                if (tree->stref <= 0)
                        cant_happen();
                return ((tree->flags & INTLSTR) != 0
                        ? r_force_string(tree)
                        : tree);
        } else if (tree->type == Node_var) {
                if (tree->var_value->stref <= 0)
                        cant_happen();
                if (! var_uninitialized(tree))
                        return tree->var_value;
        }
#endif

        if (tree->type == Node_param_list) {
                if ((tree->flags & FUNC) != 0)
                        fatal(_("can't use function name `%s' as variable or array"),
                                        tree->vname);

                tree = stack_ptr[tree->param_cnt];

                if (tree == NULL) {
                        if (do_lint)
                                lintwarn(_("reference to uninitialized argument `%s'"),
                                                tree->vname);
                        return Nnull_string;
                }

                if (do_lint && var_uninitialized(tree))
                        lintwarn(_("reference to uninitialized argument `%s'"),
                              tree->vname);
        }

        switch (tree->type) {
        case Node_array_ref:
                if (tree->orig_array->type == Node_var_array)
                        fatal(_("attempt to use array `%s' in a scalar context"),
                                array_vname(tree));
                tree->orig_array->type = Node_var;
                /* fall through */
        case Node_var_new:
                tree->type = Node_var;
                tree->var_value = Nnull_string;
                /* fall through */
        case Node_var:
                if (do_lint && var_uninitialized(tree))
                        lintwarn(_("reference to uninitialized variable `%s'"),
                              tree->vname);
                return tree->var_value;

        case Node_and:
                return tmp_number((AWKNUM) (eval_condition(tree->lnode)
                                            && eval_condition(tree->rnode)));

        case Node_or:
                return tmp_number((AWKNUM) (eval_condition(tree->lnode)
                                            || eval_condition(tree->rnode)));

        case Node_not:
                return tmp_number((AWKNUM) ! eval_condition(tree->lnode));

                /* Builtins */
        case Node_builtin:
                return (*tree->builtin)(tree->subnode);

        case Node_K_getline:
                return (do_getline(tree));

        case Node_in_array:
                return tmp_number((AWKNUM) (in_array(tree->lnode, tree->rnode) != NULL));

        case Node_func_call:
                return func_call(tree);

                /* unary operations */
        case Node_NR:
        case Node_FNR:
        case Node_NF:
        case Node_FIELDWIDTHS:
        case Node_FS:
        case Node_RS:
        case Node_field_spec:
        case Node_subscript:
        case Node_IGNORECASE:
        case Node_OFS:
        case Node_ORS:
        case Node_OFMT:
        case Node_CONVFMT:
        case Node_BINMODE:
        case Node_LINT:
        case Node_TEXTDOMAIN:
                lhs = get_lhs(tree, (Func_ptr *) NULL, TRUE);
                return *lhs;

        case Node_var_array:
                fatal(_("attempt to use array `%s' in a scalar context"),
                        array_vname(tree));

        case Node_unary_minus:
                t1 = tree_eval(tree->subnode);
                x = -force_number(t1);
                free_temp(t1);
                return tmp_number(x);

        case Node_cond_exp:
                if (eval_condition(tree->lnode))
                        return tree_eval(tree->rnode->lnode);
                return tree_eval(tree->rnode->rnode);

        case Node_match:
        case Node_nomatch:
        case Node_regex:
        case Node_dynregex:
                return match_op(tree);

        case Node_concat:
                {
                NODE **treelist;
                NODE **strlist;
                NODE *save_tree;
                register NODE **treep;
                register NODE **strp;
                register size_t len;
                register size_t supposed_len;
                char *str;
                register char *dest;
                int alloc_count, str_count;
                int i;

                /*
                 * This is an efficiency hack for multiple adjacent string
                 * concatenations, to avoid recursion and string copies.
                 *
                 * Node_concat trees grow downward to the left, so
                 * descend to lowest (first) node, accumulating nodes
                 * to evaluate to strings as we go.
                 */

                /*
                 * But first, no arbitrary limits. Count the number of
                 * nodes and malloc the treelist and strlist arrays.
                 * There will be alloc_count + 1 items to concatenate. We
                 * also leave room for an extra pointer at the end to
                 * use as a sentinel.  Thus, start alloc_count at 2.
                 */
                save_tree = tree;
                for (alloc_count = 2; tree != NULL && tree->type == Node_concat;
                                tree = tree->lnode)
                        alloc_count++;
                tree = save_tree;
                emalloc(treelist, NODE **, sizeof(NODE *) * alloc_count, "tree_eval");
                emalloc(strlist, NODE **, sizeof(NODE *) * alloc_count, "tree_eval");

                /* Now, here we go. */
                treep = treelist;
                while (tree != NULL && tree->type == Node_concat) {
                        *treep++ = tree->rnode;
                        tree = tree->lnode;
                }
                *treep = tree;
                /*
                 * Now, evaluate to strings in LIFO order, accumulating
                 * the string length, so we can do a single malloc at the
                 * end.
                 *
                 * Evaluate the expressions first, then get their
                 * lengthes, in case one of the expressions has a
                 * side effect that changes one of the others.
                 * See test/nasty.awk.
                 *
                 * dupnode the results a la do_print, to give us
                 * more predicable behavior; compare gawk 3.0.6 to
                 * nawk/mawk on test/nasty.awk.
                 */
                strp = strlist;
                supposed_len = len = 0;
                while (treep >= treelist) {
                        NODE *n;

                        /* Here lies the wumpus's brother. R.I.P. */
                        n = force_string(tree_eval(*treep--));
                        *strp = dupnode(n);
                        free_temp(n);
                        supposed_len += (*strp)->stlen;
                        strp++;
                }
                *strp = NULL;

                str_count = strp - strlist;
                strp = strlist;
                for (i = 0; i < str_count; i++) {
                        len += (*strp)->stlen;
                        strp++;
                }
                if (do_lint && supposed_len != len)
                        lintwarn(_("concatenation: side effects in one expression have changed the length of another!"));
                emalloc(str, char *, len+2, "tree_eval");
                str[len] = str[len+1] = '\0';   /* for good measure */
                dest = str;
                strp = strlist;
                while (*strp != NULL) {
                        memcpy(dest, (*strp)->stptr, (*strp)->stlen);
                        dest += (*strp)->stlen;
                        unref(*strp);
                        strp++;
                }
                r = make_str_node(str, len, ALREADY_MALLOCED);
                r->flags |= TEMP;

                free(strlist);
                free(treelist);
                }
                return r;

        /* assignments */
        case Node_assign:
                {
                Func_ptr after_assign = NULL;

                if (do_lint && iscond)
                        lintwarn(_("assignment used in conditional context"));
                r = tree_eval(tree->rnode);
                lhs = get_lhs(tree->lnode, &after_assign, FALSE);

                assign_val(lhs, r);
                if (after_assign)
                        (*after_assign)();
                return *lhs;
                }

        /* other assignment types are easier because they are numeric */
        case Node_preincrement:
        case Node_predecrement:
        case Node_postincrement:
        case Node_postdecrement:
        case Node_assign_exp:
        case Node_assign_times:
        case Node_assign_quotient:
        case Node_assign_mod:
        case Node_assign_plus:
        case Node_assign_minus:
                return op_assign(tree);
        default:
                break;  /* handled below */
        }

        /*
         * Evaluate subtrees in order to do binary operation, then keep going.
         * Use dupnode to make sure that these values don't disappear out
         * from under us during recursive subexpression evaluation.
         */
        t1 = dupnode(tree_eval(tree->lnode));
        t2 = dupnode(tree_eval(tree->rnode));

        switch (tree->type) {
        case Node_geq:
        case Node_leq:
        case Node_greater:
        case Node_less:
        case Node_notequal:
        case Node_equal:
                di = cmp_nodes(t1, t2);
                unref(t1);
                unref(t2);
                switch (tree->type) {
                case Node_equal:
                        return tmp_number((AWKNUM) (di == 0));
                case Node_notequal:
                        return tmp_number((AWKNUM) (di != 0));
                case