/*      $OpenBSD: var.c,v 1.108 2025/11/27 09:08:49 tb Exp $    */
/*      $NetBSD: var.c,v 1.18 1997/03/18 19:24:46 christos Exp $        */

/*
 * Copyright (c) 1999,2000,2007 Marc Espie.
 *
 * Extensive code modifications for the OpenBSD project.
 *
 * 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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT 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 OPENBSD
 * PROJECT 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.
 */
/*
 * Copyright (c) 1988, 1989, 1990, 1993
 *      The Regents of the University of California.  All rights reserved.
 * Copyright (c) 1989 by Berkeley Softworks
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Adam de Boor.
 *
 * 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.
 */

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ohash.h>

#include "defines.h"
#include "buf.h"
#include "cmd_exec.h"
#include "stats.h"
#include "pathnames.h"
#include "varmodifiers.h"
#include "var.h"
#include "varname.h"
#include "error.h"
#include "str.h"
#include "var_int.h"
#include "memory.h"
#include "symtable.h"
#include "gnode.h"
#include "dump.h"
#include "lowparse.h"

/*
 * This is a harmless return value for Var_Parse that can be used by Var_Subst
 * to determine if there was an error in parsing -- easier than returning
 * a flag, as things outside this module don't give a hoot.
 */
char    var_Error[] = "";

GNode *current_node = NULL;
/*
 * Similar to var_Error, but returned when the 'err' flag for Var_Parse is
 * set false. Why not just use a constant? Well, gcc likes to condense
 * identical string instances...
 */
static char     varNoError[] = "";
bool            errorIsOkay;
static bool     checkEnvFirst;  /* true if environment should be searched for
                                 * variables before the global context */
                                /* do we need to recompute varname_list */
static bool     varname_list_changed = true;

void
Var_setCheckEnvFirst(bool yes)
{
        checkEnvFirst = yes;
}

/*
 * The rules for variable look-up are complicated.
 *
 * - Dynamic variables like $@ and $* are special. They always pertain to
 * a given variable.  In this implementation of make, it is an error to
 * try to affect them manually. They are stored in a local symtable directly
 * inside the gnode.
 *
 * Global variables can be obtained:
 * - from the command line
 * - from the environment
 * - from the Makefile proper.
 * All of these are stored in a hash global_variables.
 *
 * Variables set on the command line override Makefile contents, are
 * passed to submakes (see Var_AddCmdLine), and are also exported to the
 * environment.
 *
 * Without -e (!checkEnvFirst), make will see variables set in the
 * Makefile, and default to the environment otherwise.
 *
 * With -e (checkEnvFirst), make will see the environment first, and that
 * will override anything that's set in the Makefile (but not set on
 * the command line).
 *
 * The SHELL variable is very special: it is never obtained from the
 * environment, and never passed to the environment.
 */

/* definitions pertaining to dynamic variables */

/* full names of dynamic variables */
static char *varnames[] = {
        TARGET,
        PREFIX,
        ARCHIVE,
        MEMBER,
        IMPSRC,
        OODATE,
        ALLSRC,
};

static bool xtlist[] = {
        false,  /* GLOBAL_INDEX */
        true,   /* $@ */
        false,  /* $* */
        false,  /* $! */
        true,   /* $% */
        true,   /* $< */
        false,  /* $? */
        false,  /* $> */
};

/* so that we can access tlist[-1] */
static bool *tlist = xtlist+1;

/* hashed names of dynamic variables */
#include    "varhashconsts.h"

#define GLOBAL_INDEX    -1


static struct ohash global_variables;


typedef struct Var_ {
        BUFFER val;             /* the variable value */
        unsigned int flags;     /* miscellaneous status flags */
#define VAR_IN_USE      1       /* Variable's value currently being used. */
                                /* (Used to avoid recursion) */
#define VAR_DUMMY       2       /* Variable is currently just a name */
                                /* In particular: BUFFER is invalid */
#define VAR_FROM_CMD    4       /* Special source: command line */
#define VAR_FROM_ENV    8       /* Special source: environment */
#define VAR_SEEN_ENV    16      /* No need to go look up environment again */
#define VAR_IS_SHELL    32      /* Magic behavior */
#define VAR_IS_NAMES    1024    /* Very expensive, only defined when needed */
/* XXX there are also some flag values which are part of the visible API
 * and thus defined inside var.h, don't forget to look there if you want
 * to define some new flags !
 */
#define POISONS (POISON_NORMAL | POISON_EMPTY | POISON_NOT_DEFINED)
                                /* Defined in var.h */
        char name[1];           /* the variable's name */
}  Var;

/* for GNU make compatibility */
#define VARNAME_LIST ".VARIABLES"

static struct ohash_info var_info = {
        offsetof(Var, name),
        NULL,
        hash_calloc, hash_free, element_alloc
};

static int classify_var(const char *, const char **, uint32_t *, char *);
static Var *find_global_var(const char *, const char *, uint32_t);
static Var *find_global_var_without_env(const char *, const char *, uint32_t);
static void fill_from_env(Var *);
static Var *create_var(const char *, const char *);
static void var_set_initial_value(Var *, const char *);
static void var_set_value(Var *, const char *);
static char *var_get_value(Var *);
static void var_exec_cmd(Var *);
static void varname_list_retrieve(Var *);


static void var_append_value(Var *, const char *);
static void poison_check(Var *);
static void var_set_append(const char *, const char *, const char *, int, bool);
static void set_magic_shell_variable(void);

static void delete_var(Var *);
static void print_var(Var *);


static const char *find_rparen(const char *);
static const char *find_ket(const char *);
typedef const char * (*find_t)(const char *);
static find_t find_pos(int);
static void push_used(Var *);
static void pop_used(Var *);
static char *get_expanded_value(const char *, const char *, int, uint32_t, char,
    SymTable *, bool, bool *);
static bool parse_base_variable_name(const char **, struct Name *, SymTable *);



/* Variable lookup function: return idx for dynamic variable, or
 * GLOBAL_INDEX if name is not dynamic. Set up *pk for further use.
 */
static int
classify_var(const char *name, const char **enamePtr, uint32_t *pk, char *ext)
{
        size_t len;
        uint32_t k;
        *ext = 0;


        *pk = ohash_interval(name, enamePtr);
        len = *enamePtr - name;

        /* special treatment: @D/@F and the likes */
        k = *pk;
        if (len == 2 && (name[1] == 'D' || name[1] == 'F')) {
                *ext = name[1];
                len--;
                k = name[0];
        }
            /* substitute short version for long local name */
        switch (k % MAGICSLOTS1) {      /* MAGICSLOTS should be the    */
        case K_LONGALLSRC % MAGICSLOTS1:/* smallest constant yielding  */
                                        /* distinct case values    */
                if (*pk == K_LONGALLSRC && len == strlen(LONGALLSRC) &&
                    strncmp(name, LONGALLSRC, len) == 0)
                        return ALLSRC_INDEX;
                break;
        case K_LONGARCHIVE % MAGICSLOTS1:
                if (*pk == K_LONGARCHIVE && len == strlen(LONGARCHIVE) &&
                    strncmp(name, LONGARCHIVE, len) == 0)
                        return ARCHIVE_INDEX;
                break;
        case K_LONGIMPSRC % MAGICSLOTS1:
                if (*pk == K_LONGIMPSRC && len == strlen(LONGIMPSRC) &&
                    strncmp(name, LONGIMPSRC, len) == 0)
                        return IMPSRC_INDEX;
                break;
        case K_LONGMEMBER % MAGICSLOTS1:
                if (*pk == K_LONGMEMBER && len == strlen(LONGMEMBER) &&
                    strncmp(name, LONGMEMBER, len) == 0)
                        return MEMBER_INDEX;
                break;
        case K_LONGOODATE % MAGICSLOTS1:
                if (*pk == K_LONGOODATE && len == strlen(LONGOODATE) &&
                    strncmp(name, LONGOODATE, len) == 0)
                        return OODATE_INDEX;
                break;
        case K_LONGPREFIX % MAGICSLOTS1:
                if (*pk == K_LONGPREFIX && len == strlen(LONGPREFIX) &&
                    strncmp(name, LONGPREFIX, len) == 0)
                        return PREFIX_INDEX;
                break;
        case K_LONGTARGET % MAGICSLOTS1:
                if (*pk == K_LONGTARGET && len == strlen(LONGTARGET) &&
                    strncmp(name, LONGTARGET, len) == 0)
                        return TARGET_INDEX;
                break;
        case K_TARGET % MAGICSLOTS1:
                if (name[0] == TARGET[0] && len == 1)
                        return TARGET_INDEX;
                break;
        case K_OODATE % MAGICSLOTS1:
                if (name[0] == OODATE[0] && len == 1)
                        return OODATE_INDEX;
                break;
        case K_ALLSRC % MAGICSLOTS1:
                if (name[0] == ALLSRC[0] && len == 1)
                        return ALLSRC_INDEX;
                break;
        case K_IMPSRC % MAGICSLOTS1:
                if (name[0] == IMPSRC[0] && len == 1)
                        return IMPSRC_INDEX;
                break;
        case K_PREFIX % MAGICSLOTS1:
                if (name[0] == PREFIX[0] && len == 1)
                        return PREFIX_INDEX;
                break;
        case K_ARCHIVE % MAGICSLOTS1:
                if (name[0] == ARCHIVE[0] && len == 1)
                        return ARCHIVE_INDEX;
                break;
        case K_MEMBER % MAGICSLOTS1:
                if (name[0] == MEMBER[0] && len == 1)
                        return MEMBER_INDEX;
                break;
        default:
                break;
        }
        return GLOBAL_INDEX;
}


/***
 ***    Internal handling of variables.
 ***/


/* Create a new variable, does not initialize anything except the name.
 * in particular, buffer is invalid, and flag value is invalid. Accordingly,
 * must either:
 * - set flags to VAR_DUMMY
 * - set flags to !VAR_DUMMY, and initialize buffer, for instance with
 * var_set_initial_value().
 */
static Var *
create_var(const char *name, const char *ename)
{
        return ohash_create_entry(&var_info, name, &ename);
}

/* Initial version of var_set_value(), to be called after create_var().
 */
static void
var_set_initial_value(Var *v, const char *val)
{
        size_t len;

        len = strlen(val);
        Buf_Init(&(v->val), len+1);
        Buf_AddChars(&(v->val), len, val);
        varname_list_changed = true;
}

/* Normal version of var_set_value(), to be called after variable is fully
 * initialized.
 */
static void
var_set_value(Var *v, const char *val)
{
        if ((v->flags & VAR_DUMMY) == 0) {
                Buf_Reset(&(v->val));
                Buf_AddString(&(v->val), val);
        } else {
                var_set_initial_value(v, val);
                v->flags &= ~VAR_DUMMY;
        }
}

static char *
var_get_value(Var *v)
{
        if (v->flags & VAR_IS_NAMES)
                varname_list_retrieve(v);
        else if (v->flags & VAR_EXEC_LATER)
                var_exec_cmd(v);
        return Buf_Retrieve(&(v->val));
}

/* Add to a variable, insert a separating space if the variable was already
 * defined.
 */
static void
var_append_value(Var *v, const char *val)
{
        if ((v->flags & VAR_DUMMY) == 0) {
                Buf_AddSpace(&(v->val));
                Buf_AddString(&(v->val), val);
        } else {
                var_set_initial_value(v, val);
                v->flags &= ~VAR_DUMMY;
        }
}


/* Delete a variable and all the space associated with it.
 */
static void
delete_var(Var *v)
{
        if ((v->flags & VAR_DUMMY) == 0)
                Buf_Destroy(&(v->val));
        free(v);
}




/***
 ***    Dynamic variable handling.
 ***/



/* create empty symtable.
 * XXX: to save space, dynamic variables may be NULL pointers.
 */
void
SymTable_Init(SymTable *ctxt)
{
        static SymTable sym_template;
        memcpy(ctxt, &sym_template, sizeof(*ctxt));
}

/***
 ***    Global variable handling.
 ***/

/* Create a new global var if necessary, and set it up correctly.
 * Do not take environment into account.
 */
static Var *
find_global_var_without_env(const char *name, const char *ename, uint32_t k)
{
        unsigned int slot;
        Var *v;

        slot = ohash_lookup_interval(&global_variables, name, ename, k);
        v = ohash_find(&global_variables, slot);
        if (v == NULL) {
                v = create_var(name, ename);
                v->flags = VAR_DUMMY;
                ohash_insert(&global_variables, slot, v);
        }
        return v;
}

/* Helper for find_global_var(): grab environment value if needed.
 */
static void
fill_from_env(Var *v)
{
        char    *env;

        env = getenv(v->name);
        if (env == NULL)
                v->flags |= VAR_SEEN_ENV;
        else {
                var_set_value(v, env);
                v->flags |= VAR_FROM_ENV | VAR_SEEN_ENV;
        }

#ifdef STATS_VAR_LOOKUP
        STAT_VAR_FROM_ENV++;
#endif
}

/* Find global var, and obtain its value from the environment if needed.
 */
static Var *
find_global_var(const char *name, const char *ename, uint32_t k)
{
        Var *v;

        v = find_global_var_without_env(name, ename, k);

        if ((v->flags & VAR_SEEN_ENV) == 0)
                if ((checkEnvFirst && (v->flags & VAR_FROM_CMD) == 0) ||
                    (v->flags & VAR_DUMMY) != 0)
                        fill_from_env(v);

        return v;
}

/* mark variable with special flags, in a given setup.
 */
void
Var_Mark(const char *name, const char *ename, unsigned int type)
{
        Var   *v;
        uint32_t        k;
        int             idx;
        char            ext;
        idx = classify_var(name, &ename, &k, &ext);

        if (idx != GLOBAL_INDEX) {
                Parse_Error(PARSE_FATAL,
                    "Trying to poison dynamic variable $%s",
                    varnames[idx]);
                return;
        }

        v = find_global_var(name, ename, k);
        v->flags |= type;
        /* POISON_NORMAL is not lazy: if the variable already exists in
         * the Makefile, then it's a mistake.
         */
        if (v->flags & POISON_NORMAL) {
                if (v->flags & VAR_DUMMY)
                        return;
                if (v->flags & VAR_FROM_ENV)
                        return;
                Parse_Error(PARSE_FATAL,
                    "Poisoned variable %s is already set\n", v->name);
        }
}

/* Check if there's any reason not to use this variable.
 */
static void
poison_check(Var *v)
{
        if (v->flags & POISON_NORMAL) {
                Parse_Error(PARSE_FATAL,
                    "Poisoned variable %s has been referenced\n", v->name);
                return;
        }
        if (v->flags & VAR_DUMMY) {
                Parse_Error(PARSE_FATAL,
                    "Poisoned variable %s is not defined\n", v->name);
                return;
        }
        if (v->flags & POISON_EMPTY)
                if (strcmp(var_get_value(v), "") == 0)
                        Parse_Error(PARSE_FATAL,
                            "Poisoned variable %s is empty\n", v->name);
}

/* Delete global variable.
 */
void
Var_Deletei(const char *name, const char *ename)
{
        Var *v;
        uint32_t k;
        unsigned int slot;
        int idx;
        char ext;

        idx = classify_var(name, &ename, &k, &ext);
        if (idx != GLOBAL_INDEX) {
                Parse_Error(PARSE_FATAL,
                    "Trying to delete dynamic variable $%s", varnames[idx]);
                return;
        }
        slot = ohash_lookup_interval(&global_variables, name, ename, k);
        v = ohash_find(&global_variables, slot);

        if (v == NULL)
                return;

        if (checkEnvFirst && (v->flags & VAR_FROM_ENV))
                return;

        if (v->flags & VAR_FROM_CMD)
                return;

        ohash_remove(&global_variables, slot);
        delete_var(v);
        varname_list_changed = true;
}

/* Set or add a global variable, either to VAR_CMD or VAR_GLOBAL.
 */
static void
var_set_append(const char *name, const char *ename, const char *val, int ctxt,
    bool append)
{
        Var *v;
        uint32_t k;
        int idx;
        char ext;

        idx = classify_var(name, &ename, &k, &ext);
        if (idx != GLOBAL_INDEX) {
                Parse_Error(PARSE_FATAL, "Trying to %s dynamic variable $%s",
                    append ? "append to" : "set", varnames[idx]);
                return;
        }

        v = find_global_var(name, ename, k);
        if (v->flags & POISON_NORMAL)
                Parse_Error(PARSE_FATAL, "Trying to %s poisoned variable %s\n",
                    append ? "append to" : "set", v->name);
        /* so can we write to it ? */
        if (ctxt == VAR_CMD) {  /* always for command line */
                (append ? var_append_value : var_set_value)(v, val);
                v->flags |= VAR_FROM_CMD;
                if ((v->flags & VAR_IS_SHELL) == 0) {
                        /* Any variables given on the command line are
                         * automatically exported to the environment,
                         * except for SHELL (as per POSIX standard).
                         */
                        esetenv(v->name, val);
                }
                if (DEBUG(VAR))
                        printf("command:%s = %s\n", v->name, var_get_value(v));
        } else if ((v->flags & VAR_FROM_CMD) == 0 &&
             (!checkEnvFirst || (v->flags & VAR_FROM_ENV) == 0)) {
                (append ? var_append_value : var_set_value)(v, val);
                if (DEBUG(VAR))
                        printf("global:%s = %s\n", v->name, var_get_value(v));
        } else if (DEBUG(VAR))
                printf("overridden:%s = %s\n", v->name, var_get_value(v));
}

void
Var_Seti_with_ctxt(const char *name, const char *ename, const char *val,
    int ctxt)
{
        var_set_append(name, ename, val, ctxt, false);
}

void
Var_Appendi_with_ctxt(const char *name, const char *ename, const char *val,
    int ctxt)
{
        var_set_append(name, ename, val, ctxt, true);
}

static void
var_exec_cmd(Var *v)
{
        char *arg = Buf_Retrieve(&(v->val));
        char *err;
        char *res1;
        res1 = Cmd_Exec(arg, &err);
        if (err)
                Parse_Error(PARSE_WARNING, err, arg);
        var_set_value(v, res1);
        free(res1);
        v->flags &= ~VAR_EXEC_LATER;
}

static void
varname_list_retrieve(Var *v)
{
        unsigned int i;
        void *e;
        bool first = true;

        if (!varname_list_changed)
                return;
        for (e = ohash_first(&global_variables, &i); e != NULL;
            e = ohash_next(&global_variables, &i)) {
                Var *v2 = e;
                if (v2->flags & VAR_DUMMY)
                        continue;

                if (first)
                        var_set_value(v, v2->name);
                else
                        var_append_value(v, v2->name);
                first = false;
        }
        varname_list_changed = false;
}

/* XXX different semantics for Var_Valuei() and Var_Definedi():
 * references to poisoned value variables will error out in Var_Valuei(),
 * but not in Var_Definedi(), so the following construct works:
 *      .poison BINDIR
 *      BINDIR ?= /usr/bin
 */
char *
Var_Valuei(const char *name, const char *ename)
{
        Var *v;
        uint32_t k;
        int idx;
        char ext;

        idx = classify_var(name, &ename, &k, &ext);
        if (idx != GLOBAL_INDEX) {
                Parse_Error(PARSE_FATAL,
                    "Trying to get value of dynamic variable $%s",
                        varnames[idx]);
                return NULL;
        }
        v = find_global_var(name, ename, k);
        if (v->flags & POISONS)
                poison_check(v);
        if ((v->flags & VAR_DUMMY) == 0)
                return var_get_value(v);
        else
                return NULL;
}

bool
Var_Definedi(const char *name, const char *ename)
{
        Var *v;
        uint32_t k;
        int idx;
        char ext;

        idx = classify_var(name, &ename, &k, &ext);
        /* We don't bother writing an error message for dynamic variables,
         * these will be caught when getting set later, usually.
         */
        if (idx == GLOBAL_INDEX) {
                v = find_global_var(name, ename, k);
                if (v->flags & POISON_NORMAL)
                        poison_check(v);
                if ((v->flags & VAR_DUMMY) == 0)
                        return true;
        }
        return false;
}


/***
 ***    Substitution functions, handling both global and dynamic variables.
 ***/


/* All the scanning functions needed to account for all the forms of
 * variable names that exist:
 *      $A, ${AB}, $(ABC), ${A:mod}, $(A:mod)
 */

static const char *
find_rparen(const char *p)
{
        while (*p != '$' && *p != '\0' && *p != ')' && *p != ':')
                p++;
        return p;
}

static const char *
find_ket(const char *p)
{
        while (*p != '$' && *p != '\0' && *p != '}' && *p != ':')
                p++;
        return p;
}

/* Figure out what kind of name we're looking for from a start character.
 */
static find_t
find_pos(int c)
{
        switch(c) {
        case '(':
                return find_rparen;
        case '{':
                return find_ket;
        default:
                Parse_Error(PARSE_FATAL,
                    "Wrong character in variable spec %c (can't happen)", c);
                return find_rparen;
        }
}

static bool
parse_base_variable_name(const char **pstr, struct Name *name, SymTable *ctxt)
{
        const char *str = *pstr;
        const char *tstr;
        bool has_modifier = false;

        switch(str[1]) {
        case '(':
        case '{':
                /* Find eventual modifiers in the variable */
                tstr = VarName_Get(str+2, name, ctxt, false, find_pos(str[1]));
                if (*tstr == '\0')
                         Parse_Error(PARSE_FATAL, "Unterminated variable spec in %s", *pstr);
                else if (*tstr == ':')
                        has_modifier = true;
                else
                        tstr++;
                break;
        default:
                name->s = str+1;
                name->e = str+2;
                name->tofree = false;
                tstr = str + 2;
                break;
        }
        *pstr = tstr;
        return has_modifier;
}

bool
Var_ParseSkip(const char **pstr, SymTable *ctxt)
{
        const char *str = *pstr;
        struct Name name;
        bool result;
        bool has_modifier;
        const char *tstr = str;

        if (str[1] == 0) {
                *pstr = str+1;
                return false;
        }
        has_modifier = parse_base_variable_name(&tstr, &name, ctxt);
        VarName_Free(&name);
        result = true;
        if (has_modifier) {
                bool freePtr = false;
                char *s = VarModifiers_Apply(NULL, NULL, ctxt, true, &freePtr, 
                    &tstr, str[1]);
                if (s == var_Error)
                        result = false;
                if (freePtr)
                        free(s);
        }
        *pstr = tstr;
        return result;
}

/* As of now, Var_ParseBuffer is just a wrapper around Var_Parse. For
 * speed, it may be better to revisit the implementation to do things
 * directly. */
bool
Var_ParseBuffer(Buffer buf, const char *str, SymTable *ctxt, bool err,
    size_t *lengthPtr)
{
        char *result;
        bool freeIt;

        result = Var_Parse(str, ctxt, err, lengthPtr, &freeIt);
        if (result == var_Error)
                return false;

        Buf_AddString(buf, result);
        if (freeIt)
                free(result);
        return true;
}

/* Helper function for Var_Parse: still recursive, but we tag what variables
 * we expand for better error messages.
 */
#define MAX_DEPTH 350
static Var *call_trace[MAX_DEPTH];
static int current_depth = 0;

static void
push_used(Var *v)
{
        if (v->flags & VAR_IN_USE) {
                int i;
                fprintf(stderr, "Problem with variable expansion chain: ");
                for (i = 0;
                    i < (current_depth > MAX_DEPTH ? MAX_DEPTH : current_depth);
                    i++)
                        fprintf(stderr, "%s -> ", call_trace[i]->name);
                fprintf(stderr, "%s\n", v->name);
                Fatal("\tVariable %s is recursive.", v->name);
                /*NOTREACHED*/
        }

        v->flags |= VAR_IN_USE;
        if (current_depth < MAX_DEPTH)
                call_trace[current_depth] = v;
        current_depth++;
}

static void
pop_used(Var *v)
{
        v->flags &= ~VAR_IN_USE;
        current_depth--;
}

static char *
get_expanded_value(const char *name, const char *ename, int idx, uint32_t k,
    char ext, SymTable *ctxt, bool err, bool *freePtr)
{
        char *val;

        /* Before doing any modification, we have to make sure the
         * value has been fully expanded. If it looks like recursion
         * might be necessary (there's a dollar sign somewhere in
         * the variable's value) we just call Var_Subst to do any
         * other substitutions that are necessary. Note that the
         * value returned by Var_Subst will have been dynamically
         * allocated, so it will need freeing when we return.
         */
        if (idx == GLOBAL_INDEX) {
                Var *v = find_global_var(name, ename, k);

                if (v == NULL)
                        return NULL;

                if ((v->flags & POISONS) != 0)
                        poison_check(v);
                if ((v->flags & VAR_DUMMY) != 0)
                        return NULL;

                val = var_get_value(v);
                if (strchr(val, '$') != NULL) {
                        push_used(v);
                        val = Var_Subst(val, ctxt, err);
                        pop_used(v);
                        *freePtr = true;
                }
        } else {
                if (ctxt != NULL) {
                        val = ctxt->locals[idx];
                } else
                        val = NULL;
                if (val == NULL)
                        return NULL;

                if (ext == 'F') {
                        val = Var_GetTail(val);
                        *freePtr = true;
                } else if (ext == 'D') {
                        val = Var_GetHead(val);
                        *freePtr = true;
                }
        }
        return val;
}

#define ERRMSG1 "Using $< in a non-suffix rule context is a GNUmake idiom "
#define ERRMSG2  "Using undefined dynamic variable $%s "
static void
bad_dynamic_variable(int idx)
{
        Location origin;

        Parse_FillLocation(&origin);
        switch(idx) {
        case IMPSRC_INDEX:
                if (origin.fname)
                        Fatal(ERRMSG1  "(%s:%lu)", 
                            origin.fname, origin.lineno);
                else if (current_node)
                        Fatal(ERRMSG1 "(prereq of %s)", current_node->name);
                else
                        Fatal(ERRMSG1 "(?)");
                break;
        default:
                if (origin.fname)
                        Error(ERRMSG2 "(%s:%lu)", varnames[idx], 
                            origin.fname, origin.lineno);
                else if (current_node)
                        Error(ERRMSG2 "(prereq of %s)", varnames[idx], 
                            current_node->name);
                else 
                        Error(ERRMSG2 "(?)", varnames[idx]);
                break;
        }
}

char *
Var_Parse(const char *str,      /* The string to parse */
    SymTable *ctxt,             /* The context for the variable */
    bool err,                   /* true if undefined variables are an error */
    size_t *lengthPtr,          /* OUT: The length of the specification */
    bool *freePtr)              /* OUT: true if caller should free result */
{
        const char *tstr;
        struct Name name;
        char *val;
        uint32_t k;
        int idx;
        bool has_modifier;
        char ext;

        *freePtr = false;

        tstr = str;

        if (str[1] == 0) {
                *lengthPtr = 1;
                *freePtr = false;
                return err ? var_Error : varNoError;
        }

        has_modifier = parse_base_variable_name(&tstr, &name, ctxt);

        idx = classify_var(name.s, &name.e, &k, &ext);
        val = get_expanded_value(name.s, name.e, idx, k, ext, ctxt, err, 
            freePtr);
        if (has_modifier) {
                val = VarModifiers_Apply(val, &name, ctxt, err, freePtr,
                    &tstr, str[1]);
        }
        if (val == NULL) {
                val = err ? var_Error : varNoError;
                /* If it comes from a dynamic source, and it doesn't have
                 * a local context, copy the spec instead.
                 * Specifically, this make allows constructs like:
                 *      target.o: $*.c
                 * Absence of a context means "parsing". But these can't
                 * be expanded during parsing, to be consistent with the
                 * way .SUFFIXES work.
                 * .SUFFIXES may be added/reset/removed during parsing,
                 * but in the end, the final list is what's considered for
                 * handling targets.  So those dynamic variables must be
                 * handled lazily too.
                 */
                if (idx != GLOBAL_INDEX) {
                        if (ctxt == NULL) {
                                *freePtr = true;
                                val = Str_dupi(str, tstr);
                        } else {
                                bad_dynamic_variable(idx);
                        }
                }
        }
        VarName_Free(&name);
        *lengthPtr = tstr - str;
        return val;
}


char *
Var_Subst(const char *str,      /* the string in which to substitute */
    SymTable *ctxt,             /* the context wherein to find variables */
    bool undefErr)              /* true if undefineds are an error */
{
        BUFFER buf;             /* Buffer for forming things */
        static bool errorReported;

        Buf_Init(&buf, MAKE_BSIZE);
        errorReported = false;

        for (;;) {
                char *val;      /* Value to substitute for a variable */
                size_t length;  /* Length of the variable invocation */
                bool doFree;    /* Set true if val should be freed */
                const char *cp;

                /* copy uninteresting stuff */
                for (cp = str; *str != '\0' && *str != '$'; str++)
                        ;
                Buf_Addi(&buf, cp, str);
                if (*str == '\0')
                        break;
                if (str[1] == '$') {
                        /* A $ may be escaped with another $. */
                        Buf_AddChar(&buf, '$');
                        str += 2;
                        continue;
                }
                val = Var_Parse(str, ctxt, undefErr, &length, &doFree);
                /* When we come down here, val should either point to the
                 * value of this variable, suitably modified, or be NULL.
                 * Length should be the total length of the potential
                 * variable invocation (from $ to end character...) */
                if (val == var_Error || val == varNoError) {
                        /* If errors are not an issue, skip over the variable
                         * and continue with the substitution. Otherwise, store
                         * the dollar sign and advance str so we continue with
                         * the string...  */
                        if (errorIsOkay)
                                str += length;
                        else if (undefErr) {
                                /* If variable is undefined, complain and
                                 * skip the variable name. The complaint
                                 * will stop us from doing anything when
                                 * the file is parsed.  */
                                if (!errorReported)
                                        Parse_Error(PARSE_FATAL,
                                             "Undefined variable \"%.*s\"",
                                             (int)length, str);
                                str += length;
                                errorReported = true;
                        } else {
                                Buf_AddChar(&buf, *str);
                                str++;
                        }
                } else {
                        /* We've now got a variable structure to store in.
                         * But first, advance the string pointer.  */
                        str += length;

                        /* Copy all the characters from the variable value
                         * straight into the new string.  */
                        Buf_AddString(&buf, val);
                        if (doFree)
                                free(val);
                }
        }
        return  Buf_Retrieve(&buf);
}

/* Very quick version of the variable scanner that just looks for target
 * variables, and never ever errors out
 */
bool
Var_Check_for_target(const char *str)
{
        bool seen_target = false;

        for (;;) {
                const char *tstr;
                uint32_t k;
                int idx;
                bool has_modifier;
                struct Name name;
                char ext;

                /* skip over uninteresting stuff */
                for (; *str != '\0' && *str != '$'; str++)
                        ;
                if (*str == '\0')
                        break;
                if (str[1] == '$') {
                        /* A $ may be escaped with another $. */
                        str += 2;
                        continue;
                }

                tstr = str;

                has_modifier = parse_base_variable_name(&tstr, &name, NULL);
                idx = classify_var(name.s, &name.e, &k, &ext);
                if (has_modifier) {
                        bool doFree = false;
                        char *val = VarModifiers_Apply(NULL, NULL, NULL, false, 
                            &doFree, &tstr, str[1]);
                        if (doFree)
                                free(val);
                }
                if (tlist[idx])
                        seen_target = true;
                VarName_Free(&name);
                str = tstr;
        }
        return seen_target;
}

static BUFFER subst_buffer;

/* we would like to subst on intervals, but it's complicated, so we cheat
 * by storing the interval in a static buffer.
 */
char *
Var_Substi(const char *str, const char *estr, SymTable *ctxt, bool undefErr)
{
        /* delimited string: no need to copy */
        if (estr == NULL || *estr == '\0')
                return Var_Subst(str, ctxt, undefErr);

        Buf_Reset(&subst_buffer);
        Buf_Addi(&subst_buffer, str, estr);
        return Var_Subst(Buf_Retrieve(&subst_buffer), ctxt, undefErr);
}

/***
 ***    Supplementary support for .for loops.
 ***/



struct LoopVar
{
        Var old;        /* keep old variable value (before the loop) */
        Var *me;        /* the variable we're dealing with */
};


struct LoopVar *
Var_NewLoopVar(const char *name, const char *ename)
{
        struct LoopVar *l;
        uint32_t k;

        l = emalloc(sizeof(struct LoopVar));

        /* we obtain a new variable quickly, make a snapshot of its old
         * value, and make sure the environment cannot touch us.
         */
        /* XXX: should we avoid dynamic variables ? */
        k = ohash_interval(name, &ename);

        l->me = find_global_var_without_env(name, ename, k);
        l->old = *(l->me);
        l->me->flags = VAR_SEEN_ENV | VAR_DUMMY;
        return l;
}

char *
Var_LoopVarName(struct LoopVar *v)
{
        return v->me->name;
}

void
Var_DeleteLoopVar(struct LoopVar *l)
{
        if ((l->me->flags & VAR_DUMMY) == 0)
                Buf_Destroy(&(l->me->val));
        *(l->me) = l->old;
        free(l);
}

void
Var_SubstVar(Buffer buf,        /* To store result */
    const char *str,            /* The string in which to substitute */
    struct LoopVar *l,          /* Handle */
    const char *val)            /* Its value */
{
        const char *var = l->me->name;

        var_set_value(l->me, val);

        for (;;) {
                const char *start;
                /* Copy uninteresting stuff */
                for (start = str; *str != '\0' && *str != '$'; str++)
                        ;
                Buf_Addi(buf, start, str);

                start = str;
                if (*str++ == '\0')
                        break;
                str++;
                /* and escaped dollars */
                if (start[1] == '$') {
                        Buf_Addi(buf, start, start+2);
                        continue;
                }
                /* Simple variable, if it's not us, copy.  */
                if (start[1] != '(' && start[1] != '{') {
                        if (start[1] != *var || var[1] != '\0') {
                                Buf_AddChars(buf, 2, start);
                                continue;
                    }
                } else {
                        const char *p;
                        char paren = start[1];


                        /* Find the end of the variable specification.  */
                        p = find_pos(paren)(str);
                        /* A variable inside the variable. We don't know how to
                         * expand the external variable at this point, so we
                         * try  again with the nested variable. */
                        if (*p == '$') {
                                Buf_Addi(buf, start, p);
                                str = p;
                                continue;
                        }

                        if (strncmp(var, str, p - str) != 0 ||
                                var[p - str] != '\0') {
                                /* Not the variable we want to expand.  */
                                Buf_Addi(buf, start, p);
                                str = p;
                                continue;
                        }
                        if (*p == ':') {
                                bool doFree;    /* should val be freed ? */
                                char *newval;
                                struct Name name;

                                doFree = false;
                                name.s = var;
                                name.e = var + (p-str);

                                /* val won't be freed since !doFree, but
                                 * VarModifiers_Apply doesn't know that,
                                 * hence the cast. */
                                newval = VarModifiers_Apply((char *)val,
                                    &name, NULL, false, &doFree, &p, paren);
                                Buf_AddString(buf, newval);
                                if (doFree)
                                        free(newval);
                                str = p;
                                continue;
                        } else
                                str = p+1;
                }
                Buf_AddString(buf, val);
        }
}

/***
 ***    Odds and ends
 ***/

static void
set_magic_shell_variable(void)
{
        const char *name = "SHELL";
        const char *ename = NULL;
        uint32_t k;
        Var *v;

        k = ohash_interval(name, &ename);
        v = find_global_var_without_env(name, ename, k);
        var_set_value(v, _PATH_BSHELL);
        /* XXX the environment shall never affect it */
        v->flags = VAR_IS_SHELL | VAR_SEEN_ENV;
}

static void
set_magic_name_list_variable(void)
{
        const char *name = VARNAME_LIST;
        const char *ename = NULL;
        uint32_t k;
        Var *v;

        k = ohash_interval(name, &ename);
        v = find_global_var_without_env(name, ename, k);
        /* XXX We need to set a "dummy" value because that variable can't be
         * VAR_DUMMY, since we wouldn't hit var_get_value otherwise.
         */
        var_set_initial_value(v, "");
        v->flags = VAR_IS_NAMES;
}
/*
 * Var_Init
 *      Initialize the module
 */
void
Var_Init(void)
{
        ohash_init(&global_variables, 10, &var_info);
        set_magic_shell_variable();
        set_magic_name_list_variable();

        errorIsOkay = true;
        Var_setCheckEnvFirst(false);
        VarModifiers_Init();
        Buf_Init(&subst_buffer, MAKE_BSIZE);
}


static const char *interpret(int);

static const char *
interpret(int f)
{
        if (f & VAR_DUMMY)
                return "(D)";
        return "";
}


static void
print_var(Var *v)
{
        printf("%-16s%s = %s\n", v->name, interpret(v->flags),
            (v->flags & VAR_DUMMY) == 0 ? var_get_value(v) : "(none)");
}


void
Var_Dump(void)
{
        Var **t;

        unsigned int i;
        const char *banner;
        bool first = true;

        t = sort_ohash_by_name(&global_variables);
/* somewhat dirty, but does the trick */

#define LOOP(mask, value, do_stuff) \
        for (i = 0; t[i] != NULL; i++) \
                if ((t[i]->flags & (mask)) == (value)) { \
                        if (banner) { \
                                if (first) \
                                        first = false; \
                                else \
                                        putchar('\n'); \
                                fputs(banner, stdout); \
                                banner = NULL; \
                        } \
                    do_stuff; \
                }

        banner = "#variables from command line:\n";
        LOOP(VAR_FROM_CMD | VAR_DUMMY, VAR_FROM_CMD, print_var(t[i]));

        banner = "#global variables:\n";
        LOOP(VAR_FROM_ENV| VAR_FROM_CMD | VAR_DUMMY, 0, print_var(t[i]));

        banner = "#variables from env:\n";
        LOOP(VAR_FROM_ENV|VAR_DUMMY, VAR_FROM_ENV, print_var(t[i]));

        banner = "#variable name seen, but not defined:";
        LOOP(VAR_DUMMY|POISONS, VAR_DUMMY, printf(" %s", t[i]->name));

#undef LOOP

        printf("\n\n");

        for (i = 0; t[i] != NULL; i++)
                switch(t[i]->flags & POISONS) {
                case POISON_NORMAL:
                        printf(".poison %s\n", t[i]->name);
                        break;
                case POISON_EMPTY:
                        printf(".poison empty(%s)\n", t[i]->name);
                        break;
                case POISON_NOT_DEFINED:
                        printf(".poison !defined(%s)\n", t[i]->name);
                        break;
                default:
                        break;
                }
        free(t);
        printf("\n");
}

static const char *quotable = " \t\n\\'\"";

/* POSIX says that variable assignments passed on the command line should be
 * propagated to sub makes through MAKEFLAGS.
 */
void
Var_AddCmdline(const char *name)
{
        Var *v;
        unsigned int i;
        BUFFER buf;
        char *s;

        Buf_Init(&buf, MAKE_BSIZE);

        for (v = ohash_first(&global_variables, &i); v != NULL;
            v = ohash_next(&global_variables, &i)) {
                /* This is not as expensive as it looks: this function is
                 * called before parsing Makefiles, so there are just a
                 * few non cmdling variables in there.
                 */
                if (!(v->flags & VAR_FROM_CMD)) {
                        continue;
                }
                /* We assume variable names don't need quoting */
                Buf_AddString(&buf, v->name);
                Buf_AddChar(&buf, '=');
                for (s = var_get_value(v); *s != '\0'; s++) {
                        if (strchr(quotable, *s))
                                Buf_AddChar(&buf, '\\');
                        Buf_AddChar(&buf, *s);
                }
                Buf_AddSpace(&buf);
        }
        Var_Append(name, Buf_Retrieve(&buf));
        Buf_Destroy(&buf);
}