path: root/usr.bin/make/var.c

/*	$OpenBSD: var.c,v 1.99 2015/09/27 16:58:16 guenther 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 "config.h"
#include "defines.h"
#include "buf.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 */

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,
	OODATE,
	ALLSRC,
	IMPSRC,
	FTARGET,
	DTARGET,
	FPREFIX,
	DPREFIX,
	FARCHIVE,
	DARCHIVE,
	FMEMBER,
	DMEMBER
};

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

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

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

/* extended indices for System V stuff */
#define FTARGET_INDEX	7
#define DTARGET_INDEX	8
#define FPREFIX_INDEX	9
#define DPREFIX_INDEX	10
#define FARCHIVE_INDEX	11
#define DARCHIVE_INDEX	12
#define FMEMBER_INDEX	13
#define DMEMBER_INDEX	14

#define GLOBAL_INDEX	-1

#define EXTENDED2SIMPLE(i)	(((i)-LOCAL_SIZE)/2)
#define IS_EXTENDED_F(i)	((i)%2 == 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_SHELL	32	/* Magic behavior */

#define POISONS (POISON_NORMAL | POISON_EMPTY | POISON_NOT_DEFINED)
				/* Defined in var.h */
	char name[1];		/* the variable's name */
}  Var;


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 *);
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 *);
#define var_get_value(v)	Buf_Retrieve(&((v)->val))
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,
    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)
{
	size_t len;

	*pk = ohash_interval(name, enamePtr);
	len = *enamePtr - name;
	    /* substitute short version for long local name */
	switch (*pk % 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;
	case K_FTARGET % MAGICSLOTS1:
		if (name[0] == FTARGET[0] && name[1] == FTARGET[1] && len == 2)
			return FTARGET_INDEX;
		break;
	case K_DTARGET % MAGICSLOTS1:
		if (name[0] == DTARGET[0] && name[1] == DTARGET[1] && len == 2)
			return DTARGET_INDEX;
		break;
	case K_FPREFIX % MAGICSLOTS1:
		if (name[0] == FPREFIX[0] && name[1] == FPREFIX[1] && len == 2)
			return FPREFIX_INDEX;
		break;
	case K_DPREFIX % MAGICSLOTS1:
		if (name[0] == DPREFIX[0] && name[1] == DPREFIX[1] && len == 2)
			return DPREFIX_INDEX;
		break;
	case K_FARCHIVE % MAGICSLOTS1:
		if (name[0] == FARCHIVE[0] && name[1] == FARCHIVE[1] &&
		    len == 2)
			return FARCHIVE_INDEX;
		break;
	case K_DARCHIVE % MAGICSLOTS1:
		if (name[0] == DARCHIVE[0] && name[1] == DARCHIVE[1] &&
		    len == 2)
			return DARCHIVE_INDEX;
		break;
	case K_FMEMBER % MAGICSLOTS1:
		if (name[0] == FMEMBER[0] && name[1] == FMEMBER[1] && len == 2)
			return FMEMBER_INDEX;
		break;
	case K_DMEMBER % MAGICSLOTS1:
		if (name[0] == DMEMBER[0] && name[1] == DMEMBER[1] && len == 2)
		    return DMEMBER_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);
}

/* 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;
	}
}

/* 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 as poisoned, in a given setup.
 */
void
Var_MarkPoisoned(const char *name, const char *ename, unsigned int type)
{
	Var   *v;
	uint32_t	k;
	int		idx;
	idx = classify_var(name, &ename, &k);

	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 the variable in this context.
 */
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;

	idx = classify_var(name, &ename, &k);
	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);
}

/* Set or add a global variable, in VAR_CMD or VAR_GLOBAL context.
 */
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;

	idx = classify_var(name, &ename, &k);
	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_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);
}

/* 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;

	idx = classify_var(name, &ename, &k);
	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;

	idx = classify_var(name, &ename, &k);
	/* 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,
    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) {
			if (idx < LOCAL_SIZE)
				val = ctxt->locals[idx];
			else
				val = ctxt->locals[EXTENDED2SIMPLE(idx)];
		} else
			val = NULL;
		if (val == NULL)
			return NULL;

		if (idx >= LOCAL_SIZE) {
			if (IS_EXTENDED_F(idx))
				val = Var_GetTail(val);
			else
				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);
	if (idx >= LOCAL_SIZE)
		idx = EXTENDED2SIMPLE(idx);
	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;

	*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);
	val = get_expanded_value(name.s, name.e, idx, k, 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 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;

		/* 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);
		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()
{
	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_SHELL | VAR_SEEN_ENV;
}

/*
 * Var_Init
 *	Initialize the module
 */
void
Var_Init(void)
{
	ohash_init(&global_variables, 10, &var_info);
	set_magic_shell_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);
}