aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/libexpr/eval-test.cc5
-rw-r--r--src/libexpr/eval.cc91
-rw-r--r--src/libexpr/eval.hh16
-rw-r--r--src/libexpr/nixexpr.cc218
-rw-r--r--src/libexpr/nixexpr.hh48
-rw-r--r--src/libexpr/parser.y3
-rw-r--r--src/libexpr/primops.cc4
7 files changed, 250 insertions, 135 deletions
diff --git a/src/libexpr/eval-test.cc b/src/libexpr/eval-test.cc
index d03d3bdee..bcd3670df 100644
--- a/src/libexpr/eval-test.cc
+++ b/src/libexpr/eval-test.cc
@@ -51,11 +51,12 @@ void run(Strings args)
printMsg(lvlError, format("size of value: %1% bytes") % sizeof(Value));
printMsg(lvlError, format("size of int AST node: %1% bytes") % sizeof(ExprInt));
printMsg(lvlError, format("size of attrset AST node: %1% bytes") % sizeof(ExprAttrs));
-
+
doTest(state, "123");
doTest(state, "{ x = 1; y = 2; }");
doTest(state, "{ x = 1; y = 2; }.y");
- doTest(state, "rec { x = 1; y = x; }.y");
+ doTest(state, "let x = 1; y = 2; z = 3; in let a = 4; in y");
+ doTest(state, "rec { x = 1; y = x; }.x");
doTest(state, "(x: x) 1");
doTest(state, "(x: y: y) 1 2");
doTest(state, "x: x");
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index d8acdcb6f..9c3c869bf 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -98,7 +98,7 @@ EvalState::EvalState()
, sType(symbols.create("type"))
, sMeta(symbols.create("meta"))
, sName(symbols.create("name"))
- , baseEnv(allocEnv())
+ , baseEnv(allocEnv(128))
{
nrValues = nrEnvs = nrEvaluated = recursionDepth = maxRecursionDepth = 0;
deepestStack = (char *) -1;
@@ -117,16 +117,19 @@ EvalState::~EvalState()
void EvalState::addConstant(const string & name, Value & v)
{
+#if 0
baseEnv.bindings[symbols.create(name)] = v;
string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
(*baseEnv.bindings[symbols.create("builtins")].attrs)[symbols.create(name2)] = v;
nrValues += 2;
+#endif
}
void EvalState::addPrimOp(const string & name,
unsigned int arity, PrimOp primOp)
{
+#if 0
Value v;
v.type = tPrimOp;
v.primOp.arity = arity;
@@ -135,6 +138,7 @@ void EvalState::addPrimOp(const string & name,
string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
(*baseEnv.bindings[symbols.create("builtins")].attrs)[symbols.create(name2)] = v;
nrValues += 2;
+#endif
}
@@ -234,8 +238,8 @@ void mkPath(Value & v, const char * s)
Value * EvalState::lookupVar(Env * env, const Symbol & name)
{
+#if 0
/* First look for a regular variable binding for `name'. */
- for (Env * env2 = env; env2; env2 = env2->up) {
Bindings::iterator i = env2->bindings.find(name);
if (i != env2->bindings.end()) return &i->second;
}
@@ -250,7 +254,8 @@ Value * EvalState::lookupVar(Env * env, const Symbol & name)
if (j != i->second.attrs->end()) return &j->second;
}
- throwEvalError("undefined variable `%1%'", name);
+ throwEvalError("urgh! undefined variable `%1%'", name);
+#endif
}
@@ -261,10 +266,11 @@ Value * EvalState::allocValues(unsigned int count)
}
-Env & EvalState::allocEnv()
+Env & EvalState::allocEnv(unsigned int size)
{
nrEnvs++;
- return *(new Env);
+ Env * env = (Env *) malloc(sizeof(Env) + size * sizeof(Value));
+ return *env;
}
@@ -343,7 +349,7 @@ void EvalState::eval(Env & env, Expr * e, Value & v)
char x;
if (&x < deepestStack) deepestStack = &x;
- //debug(format("eval: %1%") % *e);
+ debug(format("eval: %1%") % *e);
checkInterrupt();
@@ -396,28 +402,33 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v)
void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
{
if (recursive) {
-
/* Create a new environment that contains the attributes in
this `rec'. */
- Env & env2(state.allocEnv());
+ Env & env2(state.allocEnv(attrs.size() + inherited.size()));
env2.up = &env;
v.type = tAttrs;
- v.attrs = &env2.bindings;
+ v.attrs = new Bindings;
+ unsigned int displ = 0;
+
/* The recursive attributes are evaluated in the new
environment. */
foreach (Attrs::iterator, i, attrs) {
- Value & v2 = env2.bindings[i->first];
- mkThunk(v2, env2, i->second);
+ Value & v2 = (*v.attrs)[i->first];
+ mkCopy(v2, env2.values[displ]);
+ mkThunk(env2.values[displ++], env2, i->second);
}
+#if 0
/* The inherited attributes, on the other hand, are
evaluated in the original environment. */
foreach (list<Symbol>::iterator, i, inherited) {
Value & v2 = env2.bindings[*i];
mkCopy(v2, *state.lookupVar(&env, *i));
}
+#endif
+
}
else {
@@ -439,22 +450,24 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
{
/* Create a new environment that contains the attributes in this
`let'. */
- Env & env2(state.allocEnv());
+ Env & env2(state.allocEnv(attrs->attrs.size() + attrs->inherited.size()));
env2.up = &env;
-
+
+ unsigned int displ = 0;
+
/* The recursive attributes are evaluated in the new
environment. */
- foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs) {
- Value & v2 = env2.bindings[i->first];
- mkThunk(v2, env2, i->second);
- }
+ foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+ mkThunk(env2.values[displ++], env2, i->second);
+#if 0
/* The inherited attributes, on the other hand, are evaluated in
the original environment. */
foreach (list<Symbol>::iterator, i, attrs->inherited) {
Value & v2 = env2.bindings[*i];
mkCopy(v2, *state.lookupVar(&env, *i));
}
+#endif
state.eval(env2, body, v);
}
@@ -470,9 +483,16 @@ void ExprList::eval(EvalState & state, Env & env, Value & v)
void ExprVar::eval(EvalState & state, Env & env, Value & v)
{
- Value * v2 = state.lookupVar(&env, name);
- state.forceValue(*v2);
- v = *v2;
+ printMsg(lvlError, format("eval var %1% %2% %3%") % fromWith % level % displ);
+
+ if (fromWith) {
+ abort();
+ } else {
+ Env * env2 = &env;
+ for (unsigned int l = level; l; --l, env2 = env2->up) ;
+ state.forceValue(env2->values[displ]);
+ v = env2->values[displ];
+ }
}
@@ -559,22 +579,22 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
throwTypeError("attempt to call something which is neither a function nor a primop (built-in operation) but %1%",
showType(fun));
- Env & env2(allocEnv());
+ unsigned int size =
+ (fun.lambda.fun->arg.empty() ? 0 : 1) +
+ (fun.lambda.fun->matchAttrs ? fun.lambda.fun->formals->formals.size() : 0);
+ Env & env2(allocEnv(size));
env2.up = fun.lambda.env;
- if (!fun.lambda.fun->matchAttrs) {
- Value & vArg = env2.bindings[fun.lambda.fun->arg];
- nrValues++;
- vArg = arg;
- }
+ unsigned int displ = 0;
+
+ if (!fun.lambda.fun->matchAttrs)
+ env2.values[displ++] = arg;
else {
forceAttrs(arg);
- if (!fun.lambda.fun->arg.empty()) {
- env2.bindings[fun.lambda.fun->arg] = arg;
- nrValues++;
- }
+ if (!fun.lambda.fun->arg.empty())
+ env2.values[displ++] = arg;
/* For each formal argument, get the actual argument. If
there is no matching actual argument but the formal
@@ -582,17 +602,13 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
unsigned int attrsUsed = 0;
foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
Bindings::iterator j = arg.attrs->find(i->name);
-
- Value & v = env2.bindings[i->name];
- nrValues++;
-
if (j == arg.attrs->end()) {
if (!i->def) throwTypeError("function at %1% called without required argument `%2%'",
fun.lambda.fun->pos, i->name);
- mkThunk(v, env2, i->def);
+ mkThunk(env2.values[displ++], env2, i->def);
} else {
attrsUsed++;
- mkCopy(v, j->second);
+ mkCopy(env2.values[displ++], j->second);
}
}
@@ -639,6 +655,8 @@ void EvalState::autoCallFunction(const Bindings & args, Value & fun, Value & res
void ExprWith::eval(EvalState & state, Env & env, Value & v)
{
+ abort();
+#if 0
Env & env2(state.allocEnv());
env2.up = &env;
@@ -647,6 +665,7 @@ void ExprWith::eval(EvalState & state, Env & env, Value & v)
state.forceAttrs(vAttrs);
state.eval(env2, body, v);
+#endif
}
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index eda081261..a24b7345e 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -18,13 +18,6 @@ struct Value;
typedef std::map<Symbol, Value> Bindings;
-struct Env
-{
- Env * up;
- Bindings bindings;
-};
-
-
typedef enum {
tInt = 1,
tBool,
@@ -109,6 +102,13 @@ struct Value
};
+struct Env
+{
+ Env * up;
+ Value values[0];
+};
+
+
static inline void mkInt(Value & v, int n)
{
v.type = tInt;
@@ -258,7 +258,7 @@ public:
/* Allocation primitives. */
Value * allocValues(unsigned int count);
- Env & allocEnv();
+ Env & allocEnv(unsigned int size);
void mkList(Value & v, unsigned int length);
void mkAttrs(Value & v);
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 4040cacc8..46cbb48ac 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -8,13 +8,14 @@
namespace nix {
+/* Displaying abstract syntax trees. */
+
std::ostream & operator << (std::ostream & str, Expr & e)
{
e.show(str);
return str;
}
-
void Expr::show(std::ostream & str)
{
abort();
@@ -135,103 +136,162 @@ std::ostream & operator << (std::ostream & str, const Pos & pos)
str << (format("`%1%:%2%:%3%'") % pos.file % pos.line % pos.column).str();
return str;
}
-
-#if 0
-static void varsBoundByPattern(ATermMap & map, Pattern pat)
-{
- ATerm name;
- ATermList formals;
- ATermBool ellipsis;
- /* Use makeRemoved() so that it can be used directly in
- substitute(). */
- if (matchVarPat(pat, name))
- map.set(name, makeRemoved());
- else if (matchAttrsPat(pat, formals, ellipsis, name)) {
- if (name != sNoAlias) map.set(name, makeRemoved());
- for (ATermIterator i(formals); i; ++i) {
- ATerm d1;
- if (!matchFormal(*i, name, d1)) abort();
- map.set(name, makeRemoved());
+
+/* Computing levels/displacements for variables. */
+
+void Expr::bindVars(const StaticEnv & env)
+{
+ abort();
+}
+
+void ExprInt::bindVars(const StaticEnv & env)
+{
+}
+
+void ExprString::bindVars(const StaticEnv & env)
+{
+}
+
+void ExprPath::bindVars(const StaticEnv & env)
+{
+}
+
+void ExprVar::bindVars(const StaticEnv & env)
+{
+ /* Check whether the variable appears in the environment. If so,
+ set its level and displacement. */
+ const StaticEnv * curEnv;
+ unsigned int level;
+ int withLevel = -1;
+ for (curEnv = &env, level = 0; curEnv; curEnv = curEnv->up, level++) {
+ if (curEnv->isWith) {
+ if (withLevel == -1) withLevel = level;
+ } else {
+ StaticEnv::Vars::const_iterator i = curEnv->vars.find(name);
+ if (i != curEnv->vars.end()) {
+ fromWith = false;
+ this->level = level;
+ displ = i->second;
+ return;
+ }
}
}
- else abort();
+
+ /* Otherwise, the variable must be obtained from the nearest
+ enclosing `with'. If there is no `with', then we can issue an
+ "undefined variable" error now. */
+ if (withLevel == -1) throw EvalError(format("undefined variable `%1%'") % name);
+
+ fromWith = true;
+ this->level = withLevel;
}
+void ExprSelect::bindVars(const StaticEnv & env)
+{
+ e->bindVars(env);
+}
-/* We use memoisation to prevent exponential complexity on heavily
- shared ATerms (remember, an ATerm is a graph, not a tree!). Note
- that using an STL set is fine here wrt to ATerm garbage collection
- since all the ATerms in the set are already reachable from
- somewhere else. */
-static void checkVarDefs2(set<Expr> & done, const ATermMap & defs, Expr e)
+void ExprOpHasAttr::bindVars(const StaticEnv & env)
{
- if (done.find(e) != done.end()) return;
- done.insert(e);
-
- ATerm name, pos, value;
- ATerm with, body;
- ATermList rbnds, nrbnds;
- Pattern pat;
-
- /* Closed terms don't have free variables, so we don't have to
- check by definition. */
- if (matchClosed(e, value)) return;
+ e->bindVars(env);
+}
+
+void ExprAttrs::bindVars(const StaticEnv & env)
+{
+ if (recursive) {
+ StaticEnv newEnv(false, &env);
- else if (matchVar(e, name)) {
- if (!defs.get(name))
- throw EvalError(format("undefined variable `%1%'")
- % aterm2String(name));
- }
+ unsigned int displ = 0;
- else if (matchFunction(e, pat, body, pos)) {
- ATermMap defs2(defs);
- varsBoundByPattern(defs2, pat);
- set<Expr> done2;
- checkVarDefs2(done2, defs2, pat);
- checkVarDefs2(done2, defs2, body);
- }
-
- else if (matchRec(e, rbnds, nrbnds)) {
- checkVarDefs2(done, defs, (ATerm) nrbnds);
- ATermMap defs2(defs);
- for (ATermIterator i(rbnds); i; ++i) {
- if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
- defs2.set(name, (ATerm) ATempty);
- }
- for (ATermIterator i(nrbnds); i; ++i) {
- if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
- defs2.set(name, (ATerm) ATempty);
- }
- set<Expr> done2;
- checkVarDefs2(done2, defs2, (ATerm) rbnds);
- }
+ foreach (ExprAttrs::Attrs::iterator, i, attrs)
+ newEnv.vars[i->first] = displ++;
- else if (matchWith(e, with, body, pos)) {
- /* We can't check the body without evaluating the definitions
- (which is an arbitrary expression), so we don't do that
- here but only when actually evaluating the `with'. */
- checkVarDefs2(done, defs, with);
+ foreach (list<Symbol>::iterator, i, inherited)
+ newEnv.vars[*i] = displ++;
+
+ foreach (ExprAttrs::Attrs::iterator, i, attrs)
+ i->second->bindVars(newEnv);
}
+
+ else
+ foreach (ExprAttrs::Attrs::iterator, i, attrs)
+ i->second->bindVars(env);
+}
+
+void ExprList::bindVars(const StaticEnv & env)
+{
+ foreach (vector<Expr *>::iterator, i, elems)
+ (*i)->bindVars(env);
+}
+
+void ExprLambda::bindVars(const StaticEnv & env)
+{
+ StaticEnv newEnv(false, &env);
+
+ unsigned int displ = 0;
- else if (ATgetType(e) == AT_APPL) {
- int arity = ATgetArity(ATgetAFun(e));
- for (int i = 0; i < arity; ++i)
- checkVarDefs2(done, defs, ATgetArgument(e, i));
+ if (!arg.empty()) newEnv.vars[arg] = displ++;
+
+ if (matchAttrs) {
+ foreach (Formals::Formals_::iterator, i, formals->formals)
+ newEnv.vars[i->name] = displ++;
+
+ foreach (Formals::Formals_::iterator, i, formals->formals)
+ if (i->def) i->def->bindVars(newEnv);
}
- else if (ATgetType(e) == AT_LIST)
- for (ATermIterator i((ATermList) e); i; ++i)
- checkVarDefs2(done, defs, *i);
+ body->bindVars(newEnv);
+}
+
+void ExprLet::bindVars(const StaticEnv & env)
+{
+ StaticEnv newEnv(false, &env);
+
+ unsigned int displ = 0;
+
+ foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+ newEnv.vars[i->first] = displ++;
+
+ foreach (list<Symbol>::iterator, i, attrs->inherited)
+ newEnv.vars[*i] = displ++;
+
+ foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+ i->second->bindVars(newEnv);
+
+ body->bindVars(newEnv);
+}
+
+void ExprWith::bindVars(const StaticEnv & env)
+{
+ attrs->bindVars(env);
+ StaticEnv newEnv(true, &env);
+ body->bindVars(newEnv);
}
+void ExprIf::bindVars(const StaticEnv & env)
+{
+ cond->bindVars(env);
+ then->bindVars(env);
+ else_->bindVars(env);
+}
+
+void ExprAssert::bindVars(const StaticEnv & env)
+{
+ cond->bindVars(env);
+ body->bindVars(env);
+}
+
+void ExprOpNot::bindVars(const StaticEnv & env)
+{
+ e->bindVars(env);
+}
-void checkVarDefs(const ATermMap & defs, Expr e)
+void ExprConcatStrings::bindVars(const StaticEnv & env)
{
- set<Expr> done;
- checkVarDefs2(done, defs, e);
+ foreach (vector<Expr *>::iterator, i, *es)
+ (*i)->bindVars(env);
}
-#endif
}
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 0e595a1b1..0422e5cf4 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -17,25 +17,29 @@ MakeError(Abort, EvalError)
MakeError(TypeError, EvalError)
+/* Position objects. */
+
struct Pos
{
string file;
unsigned int line, column;
};
-
std::ostream & operator << (std::ostream & str, const Pos & pos);
-/* Abstract syntax of Nix expressions. */
-
struct Env;
struct Value;
struct EvalState;
+struct StaticEnv;
+
+
+/* Abstract syntax of Nix expressions. */
struct Expr
{
virtual void show(std::ostream & str);
+ virtual void bindVars(const StaticEnv & env);
virtual void eval(EvalState & state, Env & env, Value & v);
};
@@ -43,7 +47,8 @@ std::ostream & operator << (std::ostream & str, Expr & e);
#define COMMON_METHODS \
void show(std::ostream & str); \
- void eval(EvalState & state, Env & env, Value & v);
+ void eval(EvalState & state, Env & env, Value & v); \
+ void bindVars(const StaticEnv & env);
struct ExprInt : Expr
{
@@ -76,6 +81,20 @@ struct ExprPath : Expr
struct ExprVar : Expr
{
Symbol name;
+
+ /* Whether the variable comes from an environment (e.g. a rec, let
+ or function argument) or from a "with". */
+ bool fromWith;
+
+ /* In the former case, the value is obtained by going `level'
+ levels up from the current environment and getting the
+ `displ'th value in that environment. In the latter case, the
+ value is obtained by getting the attribute named `name' from
+ the attribute set stored in the environment that is `level'
+ levels up from the current one.*/
+ unsigned int level;
+ unsigned int displ;
+
ExprVar(const Symbol & name) : name(name) { };
COMMON_METHODS
};
@@ -186,6 +205,10 @@ struct ExprOpNot : Expr
{ \
str << *e1 << " " s " " << *e2; \
} \
+ void bindVars(const StaticEnv & env) \
+ { \
+ e1->bindVars(env); e2->bindVars(env); \
+ } \
void eval(EvalState & state, Env & env, Value & v); \
};
@@ -206,11 +229,18 @@ struct ExprConcatStrings : Expr
};
-#if 0
-/* Check whether all variables are defined in the given expression.
- Throw an exception if this isn't the case. */
-void checkVarDefs(const ATermMap & def, Expr e);
-#endif
+/* Static environments are used to map variable names onto (level,
+ displacement) pairs used to obtain the value of the variable at
+ runtime. */
+struct StaticEnv
+{
+ bool isWith;
+ const StaticEnv * up;
+ typedef std::map<Symbol, unsigned int> Vars;
+ Vars vars;
+ StaticEnv(bool isWith, const StaticEnv * up) : isWith(isWith), up(up) { };
+};
+
}
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index b746e757e..b36244352 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -461,7 +461,8 @@ static Expr * parse(EvalState & state, const char * text,
if (res) throw ParseError(data.error);
try {
- // !!! checkVarDefs(state.primOps, data.result);
+ StaticEnv env(false, 0);
+ data.result->bindVars(env);
} catch (Error & e) {
throw ParseError(format("%1%, in `%2%'") % e.msg() % path);
}
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 257dcd2e9..83af7ada9 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -999,9 +999,11 @@ void EvalState::createBaseEnv()
{
baseEnv.up = 0;
+#if 0
Value & builtins = baseEnv.bindings[symbols.create("builtins")];
builtins.type = tAttrs;
builtins.attrs = new Bindings;
+#endif
/* Add global constants such as `true' to the base environment. */
Value v;
@@ -1023,9 +1025,11 @@ void EvalState::createBaseEnv()
/* Add a wrapper around the derivation primop that computes the
`drvPath' and `outPath' attributes lazily. */
+#if 0
string s = "attrs: let res = derivationStrict attrs; in attrs // { drvPath = res.drvPath; outPath = res.outPath; type = \"derivation\"; }";
mkThunk(v, baseEnv, parseExprFromString(*this, s, "/"));
addConstant("derivation", v);
+#endif
// Miscellaneous
addPrimOp("import", 1, prim_import);
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 04:34:36 +0000