diff options
| -rw-r--r-- | src/libexpr/attr-path.cc | 2 | ||||
| -rw-r--r-- | src/libexpr/eval-test.cc | 662 | ||||
| -rw-r--r-- | src/libexpr/eval.cc | 564 | ||||
| -rw-r--r-- | src/libexpr/eval.hh | 152 | ||||
| -rw-r--r-- | src/libexpr/get-drvs.cc | 2 | ||||
| -rw-r--r-- | src/libexpr/parser.y | 4 | ||||
| -rw-r--r-- | src/libexpr/primops.cc | 58 | ||||
| -rw-r--r-- | src/nix-instantiate/nix-instantiate.cc | 10 |
8 files changed, 745 insertions, 709 deletions
diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc index e8e4c050cc84..5d81303fe3d0 100644 --- a/src/libexpr/attr-path.cc +++ b/src/libexpr/attr-path.cc @@ -6,6 +6,7 @@ namespace nix { +#if 0 bool isAttrs(EvalState & state, Expr e, ATermMap & attrs) { e = evalExpr(state, e); @@ -77,6 +78,7 @@ Expr findAlongAttrPath(EvalState & state, const string & attrPath, return e; } +#endif } diff --git a/src/libexpr/eval-test.cc b/src/libexpr/eval-test.cc index 543a9cf85298..d37014a731ca 100644 --- a/src/libexpr/eval-test.cc +++ b/src/libexpr/eval-test.cc @@ -10,668 +10,13 @@ using namespace nix; -struct Env; -struct Value; - -typedef ATerm Sym; - -typedef std::map<Sym, Value> Bindings; - - -struct Env -{ - Env * up; - Bindings bindings; -}; - - -typedef enum { - tInt = 1, - tBool, - tString, - tPath, - tNull, - tAttrs, - tList, - tThunk, - tLambda, - tCopy, - tBlackhole, - tPrimOp, - tPrimOpApp, -} ValueType; - - -typedef void (* PrimOp_) (Value * * args, Value & v); - - -struct Value -{ - ValueType type; - union - { - int integer; - bool boolean; - struct { - const char * s; - const char * * context; - } string; - Bindings * attrs; - struct { - unsigned int length; - Value * elems; - } list; - struct { - Env * env; - Expr expr; - } thunk; - struct { - Env * env; - Pattern pat; - Expr body; - } lambda; - Value * val; - struct { - PrimOp_ fun; - unsigned int arity; - } primOp; - struct { - Value * left, * right; - unsigned int argsLeft; - } primOpApp; - }; -}; - - -static void mkThunk(Value & v, Env & env, Expr expr) -{ - v.type = tThunk; - v.thunk.env = &env; - v.thunk.expr = expr; -} - - -static void mkInt(Value & v, int n) -{ - v.type = tInt; - v.integer = n; -} - - -static void mkBool(Value & v, bool b) -{ - v.type = tBool; - v.boolean = b; -} - - -static void mkString(Value & v, const char * s) -{ - v.type = tString; - v.string.s = s; - v.string.context = 0; -} - - -std::ostream & operator << (std::ostream & str, Value & v) -{ - 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 << "<CODE>"; - break; - case tLambda: - str << "<LAMBDA>"; - break; - case tPrimOp: - str << "<PRIMOP>"; - break; - case tPrimOpApp: - str << "<PRIMOP-APP>"; - break; - default: - abort(); - } - return str; -} - - -static void eval(Env & env, Expr e, Value & v); - - -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"); - } -} - - -static void 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"); -} - - -static void forceInt(Value & v) -{ - forceValue(v); - if (v.type != tInt) - throw TypeError(format("value is %1% while an integer was expected") % showType(v)); -} - - -static void forceAttrs(Value & v) -{ - forceValue(v); - if (v.type != tAttrs) - throw TypeError(format("value is %1% while an attribute set was expected") % showType(v)); -} - - -static void forceList(Value & v) -{ - forceValue(v); - if (v.type != tList) - throw TypeError(format("value is %1% while a list was expected") % showType(v)); -} - - -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"); -} - - -static bool eqValues(Value & v1, Value & v2) -{ - forceValue(v1); - forceValue(v2); - switch (v1.type) { - - case tInt: - return v2.type == tInt && v1.integer == v2.integer; - - case tBool: - return v2.type == tBool && v1.boolean == v2.boolean; - - 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"); - } -} - - -unsigned long nrValues = 0, nrEnvs = 0, nrEvaluated = 0; - -static Value * allocValues(unsigned int count) -{ - nrValues += count; - return new Value[count]; // !!! check destructor -} - -static Env & allocEnv() -{ - nrEnvs++; - return *(new Env); -} - - -char * p1 = 0, * p2 = 0; - - -static bool 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; -} - - -static void eval(Env & env, Expr e, Value & v) -{ - char c; - if (!p1) p1 = &c; else if (!p2) p2 = &c; - - 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(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"); -} - - -static void 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]); - } -} - - -static void prim_head(Value * * args, Value & v) -{ - forceList(*args[0]); - if (args[0]->list.length == 0) - throw Error("`head' called on an empty list"); - forceValue(args[0]->list.elems[0]); - v = args[0]->list.elems[0]; -} - - -static void prim_add(Value * * args, Value & v) -{ - forceInt(*args[0]); - forceInt(*args[1]); - mkInt(v, args[0]->integer + args[1]->integer); -} - - -static void addPrimOp(Env & env, const string & name, unsigned int arity, PrimOp_ fun) -{ - Value & v = env.bindings[toATerm(name)]; - nrValues++; - v.type = tPrimOp; - v.primOp.arity = arity; - v.primOp.fun = fun; -} - - void doTest(string s) { - Env baseEnv; - baseEnv.up = 0; - - /* Add global constants such as `true' to the base environment. */ - { - Value & v = baseEnv.bindings[toATerm("true")]; - v.type = tBool; - v.boolean = true; - } - { - Value & v = baseEnv.bindings[toATerm("false")]; - v.type = tBool; - v.boolean = false; - } - { - Value & v = baseEnv.bindings[toATerm("null")]; - v.type = tNull; - } - - /* Add primops to the base environment. */ - addPrimOp(baseEnv, "__head", 1, prim_head); - addPrimOp(baseEnv, "__add", 2, prim_add); - - p1 = p2 = 0; EvalState state; Expr e = parseExprFromString(state, s, "/"); printMsg(lvlError, format(">>>>> %1%") % e); Value v; - strictEval(baseEnv, e, v); + state.strictEval(e, v); printMsg(lvlError, format("result: %1%") % v); } @@ -721,11 +66,6 @@ void run(Strings args) doTest("if false then 1 else 2"); doTest("if false || true then 1 else 2"); doTest("let x = x; in if true || x then 1 else 2"); - - printMsg(lvlError, format("alloced %1% values") % nrValues); - printMsg(lvlError, format("alloced %1% environments") % nrEnvs); - printMsg(lvlError, format("evaluated %1% expressions") % nrEvaluated); - printMsg(lvlError, format("each eval() uses %1% bytes of stack space") % (p1 - p2)); } diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index 1501fc0480b2..794e3966029f 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -7,6 +7,8 @@ #include "nixexpr-ast.hh" #include "globals.hh" +#include <cstring> + #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 << "<CODE>"; + break; + case tLambda: + str << "<LAMBDA>"; + break; + case tPrimOp: + str << "<PRIMOP>"; + break; + case tPrimOpApp: + str << "<PRIMOP-APP>"; + 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(); } diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh index fed6d347266b..8ca997f1404b 100644 --- a/src/libexpr/eval.hh +++ b/src/libexpr/eval.hh @@ -11,7 +11,101 @@ namespace nix { class Hash; - +class EvalState; +struct Env; +struct Value; + +typedef ATerm Sym; + +typedef std::map<Sym, Value> Bindings; + + +struct Env +{ + Env * up; + Bindings bindings; +}; + + +typedef enum { + tInt = 1, + tBool, + tString, + tPath, + tNull, + tAttrs, + tList, + tThunk, + tLambda, + tCopy, + tBlackhole, + tPrimOp, + tPrimOpApp, +} ValueType; + + +typedef void (* PrimOp) (EvalState & state, Value * * args, Value & v); + + +struct Value +{ + ValueType type; + union + { + int integer; + bool boolean; + struct { + const char * s; + const char * * context; + } string; + Bindings * attrs; + struct { + unsigned int length; + Value * elems; + } list; + struct { + Env * env; + Expr expr; + } thunk; + struct { + Env * env; + Pattern pat; + Expr body; + } lambda; + Value * val; + struct { + PrimOp fun; + unsigned int arity; + } primOp; + struct { + Value * left, * right; + unsigned int argsLeft; + } primOpApp; + }; +}; + + +static inline void mkInt(Value & v, int n) +{ + v.type = tInt; + v.integer = n; +} + + +static inline void mkBool(Value & v, bool b) +{ + v.type = tBool; + v.boolean = b; +} + + +static inline void mkString(Value & v, const char * s) +{ + v.type = tString; + v.string.s = s; + v.string.context = 0; +} + typedef std::map<Path, PathSet> DrvRoots; typedef std::map<Path, Hash> DrvHashes; @@ -22,32 +116,69 @@ typedef std::map<Path, Path> SrcToStore; struct EvalState; -/* Note: using a ATermVector is safe here, since when we call a primop - we also have an ATermList on the stack. */ -typedef Expr (* PrimOp) (EvalState &, const ATermVector & args); + +std::ostream & operator << (std::ostream & str, Value & v); struct EvalState { - ATermMap normalForms; - ATermMap primOps; DrvRoots drvRoots; DrvHashes drvHashes; /* normalised derivation hashes */ SrcToStore srcToStore; - unsigned int nrEvaluated; - unsigned int nrCached; + unsigned long nrValues; + unsigned long nrEnvs; + unsigned long nrEvaluated; bool allowUnsafeEquality; EvalState(); - void addPrimOps(); + /* Evaluate an expression to normal form, storing the result in + value `v'. */ + void eval(Expr e, Value & v); + void eval(Env & env, Expr e, Value & v); + + /* Evaluation the expression, then verify that it has the expected + type. */ + bool evalBool(Env & env, Expr e); + + /* Evaluate an expression, and recursively evaluate list elements + and attributes. */ + void strictEval(Expr e, Value & v); + void strictEval(Env & env, Expr e, Value & v); + + /* If `v' is a thunk, enter it and overwrite `v' with the result + of the evaluation of the thunk. Otherwise, this is a no-op. */ + void forceValue(Value & v); + + /* Force `v', and then verify that it has the expected type. */ + int forceInt(Value & v); + void forceAttrs(Value & v); + void forceList(Value & v); + +private: + + /* The base environment, containing the builtin functions and + values. */ + Env & baseEnv; + + void createBaseEnv(); + void addPrimOp(const string & name, unsigned int arity, PrimOp primOp); + + /* Do a deep equality test between two values. That is, list + elements and attributes are compared recursively. */ + bool eqValues(Value & v1, Value & v2); + + /* Allocation primitives. */ + Value * allocValues(unsigned int count); + Env & allocEnv(); }; +#if 0 /* Evaluate an expression to normal form. */ Expr evalExpr(EvalState & state, Expr e); @@ -86,11 +217,12 @@ Path coerceToPath(EvalState & state, Expr e, PathSet & context); value or has a binding in the `args' map. Note: result is a call, not a normal form; it should be evaluated by calling evalExpr(). */ Expr autoCallFunction(Expr e, const ATermMap & args); +#endif /* Print statistics. */ void printEvalStats(EvalState & state); - + } diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc index 1442d7988b8b..26ce6e71cf74 100644 --- a/src/libexpr/get-drvs.cc +++ b/src/libexpr/get-drvs.cc @@ -6,6 +6,7 @@ namespace nix { +#if 0 string DrvInfo::queryDrvPath(EvalState & state) const { if (drvPath == "") { @@ -256,6 +257,7 @@ void getDerivations(EvalState & state, Expr e, const string & pathPrefix, Exprs doneExprs; getDerivations(state, e, pathPrefix, autoArgs, drvs, doneExprs); } +#endif } diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y index e55dfd76f591..2f0c9db3f33e 100644 --- a/src/libexpr/parser.y +++ b/src/libexpr/parser.y @@ -375,7 +375,7 @@ expr_op | expr_op UPDATE expr_op { $$ = makeOpUpdate($1, $3); } | expr_op '~' expr_op { $$ = makeSubPath($1, $3); } | expr_op '?' ID { $$ = makeOpHasAttr($1, $3); } - | expr_op '+' expr_op { $$ = makeOpPlus($1, $3); } + | expr_op '+' expr_op { $$ = makeConcatStrings(ATmakeList2($1, $3)); } | expr_op CONCAT expr_op { $$ = makeOpConcat($1, $3); } | expr_app ; @@ -513,7 +513,7 @@ static Expr parse(EvalState & state, if (res) throw ParseError(data.error); try { - checkVarDefs(state.primOps, data.result); + // !!! checkVarDefs(state.primOps, data.result); } 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 52292f3f8461..a24f40be67e0 100644 --- a/src/libexpr/primops.cc +++ b/src/libexpr/primops.cc @@ -19,6 +19,7 @@ namespace nix { +#if 0 /************************************************************* * Constants *************************************************************/ @@ -895,18 +896,21 @@ static Expr prim_isList(EvalState & state, const ATermVector & args) ATermList list; return makeBool(matchList(evalExpr(state, args[0]), list)); } +#endif /* Return the first element of a list. */ -static Expr prim_head(EvalState & state, const ATermVector & args) +static void prim_head(EvalState & state, Value * * args, Value & v) { - ATermList list = evalList(state, args[0]); - if (ATisEmpty(list)) + state.forceList(*args[0]); + if (args[0]->list.length == 0) throw Error("`head' called on an empty list"); - return evalExpr(state, ATgetFirst(list)); + state.forceValue(args[0]->list.elems[0]); + v = args[0]->list.elems[0]; } +#if 0 /* Return a list consisting of everything but the the first element of a list. */ static Expr prim_tail(EvalState & state, const ATermVector & args) @@ -938,6 +942,7 @@ static Expr prim_length(EvalState & state, const ATermVector & args) ATermList list = evalList(state, args[0]); return makeInt(ATgetLength(list)); } +#endif /************************************************************* @@ -945,14 +950,13 @@ static Expr prim_length(EvalState & state, const ATermVector & args) *************************************************************/ -static Expr prim_add(EvalState & state, const ATermVector & args) +static void prim_add(EvalState & state, Value * * args, Value & v) { - int i1 = evalInt(state, args[0]); - int i2 = evalInt(state, args[1]); - return makeInt(i1 + i2); + mkInt(v, state.forceInt(*args[0]) + state.forceInt(*args[1])); } +#if 0 static Expr prim_sub(EvalState & state, const ATermVector & args) { int i1 = evalInt(state, args[0]); @@ -1102,6 +1106,7 @@ static Expr prim_compareVersions(EvalState & state, const ATermVector & args) int d = compareVersions(version1, version2); return makeInt(d); } +#endif /************************************************************* @@ -1109,14 +1114,31 @@ static Expr prim_compareVersions(EvalState & state, const ATermVector & args) *************************************************************/ -void EvalState::addPrimOps() +void EvalState::createBaseEnv() { - addPrimOp("builtins", 0, prim_builtins); - + baseEnv.up = 0; + + { Value & v = baseEnv.bindings[toATerm("builtins")]; + v.type = tAttrs; + v.attrs = new Bindings; + } + + /* Add global constants such as `true' to the base environment. */ + { Value & v = baseEnv.bindings[toATerm("true")]; + mkBool(v, true); + } + { Value & v = baseEnv.bindings[toATerm("false")]; + mkBool(v, false); + } + { Value & v = baseEnv.bindings[toATerm("null")]; + v.type = tNull; + } + { Value & v = (*baseEnv.bindings[toATerm("builtins")].attrs)[toATerm("currentSystem")]; + mkString(v, thisSystem.c_str()); // !!! copy string + } + +#if 0 // Constants - addPrimOp("true", 0, prim_true); - addPrimOp("false", 0, prim_false); - addPrimOp("null", 0, prim_null); addPrimOp("__currentSystem", 0, prim_currentSystem); addPrimOp("__currentTime", 0, prim_currentTime); @@ -1134,7 +1156,6 @@ void EvalState::addPrimOps() addPrimOp("__tryEval", 1, prim_tryEval); addPrimOp("__getEnv", 1, prim_getEnv); addPrimOp("__trace", 2, prim_trace); - // Expr <-> String addPrimOp("__exprToString", 1, prim_exprToString); @@ -1169,13 +1190,17 @@ void EvalState::addPrimOps() // Lists addPrimOp("__isList", 1, prim_isList); +#endif addPrimOp("__head", 1, prim_head); +#if 0 addPrimOp("__tail", 1, prim_tail); addPrimOp("map", 2, prim_map); addPrimOp("__length", 1, prim_length); - +#endif + // Integer arithmetic addPrimOp("__add", 2, prim_add); +#if 0 addPrimOp("__sub", 2, prim_sub); addPrimOp("__mul", 2, prim_mul); addPrimOp("__div", 2, prim_div); @@ -1191,6 +1216,7 @@ void EvalState::addPrimOps() // Versions addPrimOp("__parseDrvName", 1, prim_parseDrvName); addPrimOp("__compareVersions", 2, prim_compareVersions); +#endif } diff --git a/src/nix-instantiate/nix-instantiate.cc b/src/nix-instantiate/nix-instantiate.cc index 3822de5c6289..5473db4ac928 100644 --- a/src/nix-instantiate/nix-instantiate.cc +++ b/src/nix-instantiate/nix-instantiate.cc @@ -37,6 +37,7 @@ static int rootNr = 0; static bool indirectRoot = false; +#if 0 static void printResult(EvalState & state, Expr e, bool evalOnly, bool xmlOutput, const ATermMap & autoArgs) { @@ -63,21 +64,28 @@ static void printResult(EvalState & state, Expr e, } } } +#endif void processExpr(EvalState & state, const Strings & attrPaths, bool parseOnly, bool strict, const ATermMap & autoArgs, bool evalOnly, bool xmlOutput, Expr e) { + Value v; + state.strictEval(e, v); + std::cout << v << std::endl; + +#if 0 for (Strings::const_iterator i = attrPaths.begin(); i != attrPaths.end(); ++i) { Expr e2 = findAlongAttrPath(state, *i, autoArgs, e); if (!parseOnly) if (strict) - e2 = strictEvalExpr(state, e2); + e2 = state.strictEval(e2); else e2 = evalExpr(state, e2); printResult(state, e2, evalOnly, xmlOutput, autoArgs); } +#endif } |