From 31428c3a0675f7223470af726bc697dc7a228927 Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Mon, 29 Mar 2010 14:37:56 +0000 Subject: * Started integrating the new evaluator. --- src/libexpr/eval.cc | 564 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 545 insertions(+), 19 deletions(-) (limited to 'src/libexpr/eval.cc') diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index 1501fc0480..794e396602 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -7,6 +7,8 @@ #include "nixexpr-ast.hh" #include "globals.hh" +#include + #define LocalNoInline(f) static f __attribute__((noinline)); f #define LocalNoInlineNoReturn(f) static f __attribute__((noinline, noreturn)); f @@ -15,15 +17,77 @@ namespace nix { -EvalState::EvalState() - : normalForms(32768), primOps(128) +std::ostream & operator << (std::ostream & str, Value & v) { - nrEvaluated = nrCached = 0; + switch (v.type) { + case tInt: + str << v.integer; + break; + case tBool: + str << (v.boolean ? "true" : "false"); + break; + case tString: + str << "\"" << v.string.s << "\""; // !!! escaping + break; + case tNull: + str << "true"; + break; + case tAttrs: + str << "{ "; + foreach (Bindings::iterator, i, *v.attrs) + str << aterm2String(i->first) << " = " << i->second << "; "; + str << "}"; + break; + case tList: + str << "[ "; + for (unsigned int n = 0; n < v.list.length; ++n) + str << v.list.elems[n] << " "; + str << "]"; + break; + case tThunk: + str << ""; + break; + case tLambda: + str << ""; + break; + case tPrimOp: + str << ""; + break; + case tPrimOpApp: + str << ""; + break; + default: + throw Error("invalid value"); + } + return str; +} - initNixExprHelpers(); - addPrimOps(); +string showType(Value & v) +{ + switch (v.type) { + case tString: return "a string"; + case tPath: return "a path"; + case tNull: return "null"; + case tInt: return "an integer"; + case tBool: return "a boolean"; + case tLambda: return "a function"; + case tAttrs: return "an attribute set"; + case tList: return "a list"; + case tPrimOpApp: return "a partially applied built-in function"; + default: throw Error("unknown type"); + } +} + +EvalState::EvalState() : baseEnv(allocEnv()) +{ + nrValues = nrEnvs = nrEvaluated = 0; + + initNixExprHelpers(); + + createBaseEnv(); + allowUnsafeEquality = getEnv("NIX_NO_UNSAFE_EQ", "") == ""; } @@ -31,7 +95,11 @@ EvalState::EvalState() void EvalState::addPrimOp(const string & name, unsigned int arity, PrimOp primOp) { - primOps.set(toATerm(name), makePrimOpDef(arity, ATmakeBlob(0, (void *) primOp))); + Value & v = baseEnv.bindings[toATerm(name)]; + nrValues++; + v.type = tPrimOp; + v.primOp.arity = arity; + v.primOp.fun = primOp; } @@ -76,6 +144,471 @@ LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2, } +static void mkThunk(Value & v, Env & env, Expr expr) +{ + v.type = tThunk; + v.thunk.env = &env; + v.thunk.expr = expr; +} + + +static Value * lookupWith(Env * env, Sym name) +{ + if (!env) return 0; + Value * v = lookupWith(env->up, name); + if (v) return v; + Bindings::iterator i = env->bindings.find(sWith); + if (i == env->bindings.end()) return 0; + Bindings::iterator j = i->second.attrs->find(name); + if (j != i->second.attrs->end()) return &j->second; + return 0; +} + + +static Value * lookupVar(Env * env, Sym name) +{ + /* 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; + } + + /* Otherwise, look for a `with' attribute set containing `name'. + Outer `withs' take precedence (i.e. `with {x=1;}; with {x=2;}; + x' evaluates to 1). */ + Value * v = lookupWith(env, name); + if (v) return v; + + /* Alternative implementation where the inner `withs' take + precedence (i.e. `with {x=1;}; with {x=2;}; x' evaluates to + 2). */ +#if 0 + for (Env * env2 = env; env2; env2 = env2->up) { + Bindings::iterator i = env2->bindings.find(sWith); + if (i == env2->bindings.end()) continue; + Bindings::iterator j = i->second.attrs->find(name); + if (j != i->second.attrs->end()) return &j->second; + } +#endif + + throw Error("undefined variable"); +} + + +Value * EvalState::allocValues(unsigned int count) +{ + nrValues += count; + return new Value[count]; // !!! check destructor +} + + +Env & EvalState::allocEnv() +{ + nrEnvs++; + return *(new Env); +} + + +static char * deepestStack = (char *) -1; /* for measuring stack usage */ + + +void EvalState::eval(Env & env, Expr e, Value & v) +{ + /* When changing this function, make sure that you don't cause a + (large) increase in stack consumption! */ + + char x; + if (&x < deepestStack) deepestStack = &x; + + printMsg(lvlError, format("eval: %1%") % e); + + nrEvaluated++; + + Sym name; + if (matchVar(e, name)) { + Value * v2 = lookupVar(&env, name); + forceValue(*v2); + v = *v2; + return; + } + + int n; + if (matchInt(e, n)) { + mkInt(v, n); + return; + } + + ATerm s; ATermList context; + if (matchStr(e, s, context)) { + assert(context == ATempty); + mkString(v, ATgetName(ATgetAFun(s))); + return; + } + + ATermList es; + if (matchAttrs(e, es)) { + v.type = tAttrs; + v.attrs = new Bindings; + ATerm e2, pos; + for (ATermIterator i(es); i; ++i) { + if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */ + Value & v2 = (*v.attrs)[name]; + nrValues++; + mkThunk(v2, env, e2); + } + return; + } + + ATermList rbnds, nrbnds; + if (matchRec(e, rbnds, nrbnds)) { + Env & env2(allocEnv()); + env2.up = &env; + + v.type = tAttrs; + v.attrs = &env2.bindings; + ATerm name, e2, pos; + for (ATermIterator i(rbnds); i; ++i) { + if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */ + Value & v2 = env2.bindings[name]; + nrValues++; + mkThunk(v2, env2, e2); + } + + return; + } + + Expr e1, e2; + if (matchSelect(e, e2, name)) { + eval(env, e2, v); + forceAttrs(v); // !!! eval followed by force is slightly inefficient + Bindings::iterator i = v.attrs->find(name); + if (i == v.attrs->end()) throw TypeError("attribute not found"); + forceValue(i->second); + v = i->second; + return; + } + + Pattern pat; Expr body; Pos pos; + if (matchFunction(e, pat, body, pos)) { + v.type = tLambda; + v.lambda.env = &env; + v.lambda.pat = pat; + v.lambda.body = body; + return; + } + + Expr fun, arg; + if (matchCall(e, fun, arg)) { + eval(env, fun, v); + + if (v.type == tPrimOp || v.type == tPrimOpApp) { + unsigned int argsLeft = + v.type == tPrimOp ? v.primOp.arity : v.primOpApp.argsLeft; + if (argsLeft == 1) { + /* We have all the arguments, so call the primop. + First find the primop. */ + Value * primOp = &v; + while (primOp->type == tPrimOpApp) primOp = primOp->primOpApp.left; + assert(primOp->type == tPrimOp); + unsigned int arity = primOp->primOp.arity; + + Value vLastArg; + mkThunk(vLastArg, env, arg); + + /* Put all the arguments in an array. */ + Value * vArgs[arity]; + unsigned int n = arity - 1; + vArgs[n--] = &vLastArg; + for (Value * arg = &v; arg->type == tPrimOpApp; arg = arg->primOpApp.left) + vArgs[n--] = arg->primOpApp.right; + + /* And call the primop. */ + primOp->primOp.fun(*this, vArgs, v); + } else { + Value * v2 = allocValues(2); + v2[0] = v; + mkThunk(v2[1], env, arg); + v.type = tPrimOpApp; + v.primOpApp.left = &v2[0]; + v.primOpApp.right = &v2[1]; + v.primOpApp.argsLeft = argsLeft - 1; + } + return; + } + + if (v.type != tLambda) throw TypeError("expected function"); + + Env & env2(allocEnv()); + env2.up = &env; + + ATermList formals; ATerm ellipsis; + + if (matchVarPat(v.lambda.pat, name)) { + Value & vArg = env2.bindings[name]; + nrValues++; + mkThunk(vArg, env, arg); + } + + else if (matchAttrsPat(v.lambda.pat, formals, ellipsis, name)) { + Value * vArg; + Value vArg_; + + if (name == sNoAlias) + vArg = &vArg_; + else { + vArg = &env2.bindings[name]; + nrValues++; + } + + eval(env, arg, *vArg); + forceAttrs(*vArg); + + /* For each formal argument, get the actual argument. If + there is no matching actual argument but the formal + argument has a default, use the default. */ + unsigned int attrsUsed = 0; + for (ATermIterator i(formals); i; ++i) { + Expr def; Sym name; + DefaultValue def2; + if (!matchFormal(*i, name, def2)) abort(); /* can't happen */ + + Bindings::iterator j = vArg->attrs->find(name); + + Value & v = env2.bindings[name]; + nrValues++; + + if (j == vArg->attrs->end()) { + if (!matchDefaultValue(def2, def)) def = 0; + if (def == 0) throw TypeError(format("the argument named `%1%' required by the function is missing") + % aterm2String(name)); + mkThunk(v, env2, def); + } else { + attrsUsed++; + v.type = tCopy; + v.val = &j->second; + } + } + + /* Check that each actual argument is listed as a formal + argument (unless the attribute match specifies a + `...'). TODO: show the names of the + expected/unexpected arguments. */ + if (ellipsis == eFalse && attrsUsed != vArg->attrs->size()) + throw TypeError("function called with unexpected argument"); + } + + else abort(); + + eval(env2, v.lambda.body, v); + return; + } + + Expr attrs; + if (matchWith(e, attrs, body, pos)) { + Env & env2(allocEnv()); + env2.up = &env; + + Value & vAttrs = env2.bindings[sWith]; + nrValues++; + eval(env, attrs, vAttrs); + forceAttrs(vAttrs); + + eval(env2, body, v); + return; + } + + if (matchList(e, es)) { + v.type = tList; + v.list.length = ATgetLength(es); + v.list.elems = allocValues(v.list.length); + for (unsigned int n = 0; n < v.list.length; ++n, es = ATgetNext(es)) + mkThunk(v.list.elems[n], env, ATgetFirst(es)); + return; + } + + if (matchOpEq(e, e1, e2)) { + Value v1; eval(env, e1, v1); + Value v2; eval(env, e2, v2); + mkBool(v, eqValues(v1, v2)); + return; + } + + if (matchOpNEq(e, e1, e2)) { + Value v1; eval(env, e1, v1); + Value v2; eval(env, e2, v2); + mkBool(v, !eqValues(v1, v2)); + return; + } + + if (matchOpConcat(e, e1, e2)) { + Value v1; eval(env, e1, v1); + forceList(v1); + Value v2; eval(env, e2, v2); + forceList(v2); + v.type = tList; + v.list.length = v1.list.length + v2.list.length; + v.list.elems = allocValues(v.list.length); + /* !!! This loses sharing with the original lists. We could + use a tCopy node, but that would use more memory. */ + for (unsigned int n = 0; n < v1.list.length; ++n) + v.list.elems[n] = v1.list.elems[n]; + for (unsigned int n = 0; n < v2.list.length; ++n) + v.list.elems[n + v1.list.length] = v2.list.elems[n]; + return; + } + + if (matchConcatStrings(e, es)) { + unsigned int n = ATgetLength(es), j = 0; + Value vs[n]; + unsigned int len = 0; + for (ATermIterator i(es); i; ++i, ++j) { + eval(env, *i, vs[j]); + if (vs[j].type != tString) throw TypeError("string expected"); + len += strlen(vs[j].string.s); + } + char * s = new char[len + 1], * t = s; + for (unsigned int i = 0; i < j; ++i) { + strcpy(t, vs[i].string.s); + t += strlen(vs[i].string.s); + } + *t = 0; + mkString(v, s); + return; + } + + Expr e3; + if (matchIf(e, e1, e2, e3)) { + eval(env, evalBool(env, e1) ? e2 : e3, v); + return; + } + + if (matchOpOr(e, e1, e2)) { + mkBool(v, evalBool(env, e1) || evalBool(env, e2)); + return; + } + + throw Error("unsupported term"); +} + + +void EvalState::eval(Expr e, Value & v) +{ + eval(baseEnv, e, v); +} + + +bool EvalState::evalBool(Env & env, Expr e) +{ + Value v; + eval(env, e, v); + if (v.type != tBool) + throw TypeError(format("value is %1% while a Boolean was expected") % showType(v)); + return v.boolean; +} + + +void EvalState::strictEval(Env & env, Expr e, Value & v) +{ + eval(env, e, v); + + if (v.type == tAttrs) { + foreach (Bindings::iterator, i, *v.attrs) + forceValue(i->second); + } + + else if (v.type == tList) { + for (unsigned int n = 0; n < v.list.length; ++n) + forceValue(v.list.elems[n]); + } +} + + +void EvalState::strictEval(Expr e, Value & v) +{ + strictEval(baseEnv, e, v); +} + + +void EvalState::forceValue(Value & v) +{ + if (v.type == tThunk) { + v.type = tBlackhole; + eval(*v.thunk.env, v.thunk.expr, v); + } + else if (v.type == tCopy) { + forceValue(*v.val); + v = *v.val; + } + else if (v.type == tBlackhole) + throw EvalError("infinite recursion encountered"); +} + + +int EvalState::forceInt(Value & v) +{ + forceValue(v); + if (v.type != tInt) + throw TypeError(format("value is %1% while an integer was expected") % showType(v)); + return v.integer; +} + + +void EvalState::forceAttrs(Value & v) +{ + forceValue(v); + if (v.type != tAttrs) + throw TypeError(format("value is %1% while an attribute set was expected") % showType(v)); +} + + +void EvalState::forceList(Value & v) +{ + forceValue(v); + if (v.type != tList) + throw TypeError(format("value is %1% while a list was expected") % showType(v)); +} + + +bool EvalState::eqValues(Value & v1, Value & v2) +{ + forceValue(v1); + forceValue(v2); + + if (v1.type != v2.type) return false; + + switch (v1.type) { + + case tInt: + return v1.integer == v2.integer; + + case tBool: + return v1.boolean == v2.boolean; + + case tString: + /* !!! contexts */ + return strcmp(v1.string.s, v2.string.s) == 0; + + case tList: + if (v2.type != tList || v1.list.length != v2.list.length) return false; + for (unsigned int n = 0; n < v1.list.length; ++n) + if (!eqValues(v1.list.elems[n], v2.list.elems[n])) return false; + return true; + + case tAttrs: { + if (v2.type != tAttrs || v1.attrs->size() != v2.attrs->size()) return false; + Bindings::iterator i, j; + for (i = v1.attrs->begin(), j = v2.attrs->begin(); i != v1.attrs->end(); ++i, ++j) + if (!eqValues(i->second, j->second)) return false; + return true; + } + + default: + throw Error("cannot compare given values"); + } +} + + +#if 0 /* Pattern-match `pat' against `arg'. The result is a set of substitutions (`subs') and a set of recursive substitutions (`subsRecursive'). The latter can refer to the variables bound by @@ -683,9 +1216,6 @@ LocalNoInline(bool areEqual(EvalState & state, Expr e1, Expr e2)) } -static char * deepestStack = (char *) -1; /* for measuring stack usage */ - - Expr evalExpr2(EvalState & state, Expr e) { /* When changing this function, make sure that you don't cause a @@ -884,23 +1414,19 @@ Expr strictEvalExpr(EvalState & state, Expr e) ATermMap strictNormalForms; return strictEvalExpr(state, e, strictNormalForms); } +#endif -/* Yes, this is a really bad idea... */ -extern "C" { - unsigned long AT_calcAllocatedSize(); -} - void printEvalStats(EvalState & state) { char x; bool showStats = getEnv("NIX_SHOW_STATS", "0") != "0"; printMsg(showStats ? lvlInfo : lvlDebug, - format("evaluated %1% expressions, %2% cache hits, %3%%% efficiency, used %4% ATerm bytes, used %5% bytes of stack space") - % state.nrEvaluated % state.nrCached - % ((float) state.nrCached / (float) state.nrEvaluated * 100) - % AT_calcAllocatedSize() - % (&x - deepestStack)); + format("evaluated %1% expressions, used %2% bytes of stack space, allocated %3% values, allocated %4% environments") + % state.nrEvaluated + % (&x - deepestStack) + % state.nrValues + % state.nrEnvs); if (showStats) printATermMapStats(); } -- cgit 1.4.1