From 9985230c00226826949473c3862c0c3afea74aaf Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Wed, 14 Apr 2010 14:42:32 +0000 Subject: * After parsing, compute level/displacement pairs for each variable use site, allowing environments to be stores as vectors of values rather than maps. This should speed up evaluation and reduce the number of allocations. --- src/libexpr/eval-test.cc | 5 +- src/libexpr/eval.cc | 91 ++++++++++++-------- src/libexpr/eval.hh | 16 ++-- src/libexpr/nixexpr.cc | 218 ++++++++++++++++++++++++++++++----------------- src/libexpr/nixexpr.hh | 48 +++++++++-- src/libexpr/parser.y | 3 +- src/libexpr/primops.cc | 4 + 7 files changed, 250 insertions(+), 135 deletions(-) (limited to 'src') diff --git a/src/libexpr/eval-test.cc b/src/libexpr/eval-test.cc index d03d3bdeed1b..bcd3670dfedc 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 d8acdcb6f6e3..9c3c869bf3f2 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::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::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 eda081261c39..a24b7345efab 100644 --- a/src/libexpr/eval.hh +++ b/src/libexpr/eval.hh @@ -18,13 +18,6 @@ struct Value; typedef std::map 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 4040cacc813e..46cbb48ac5e5 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 & 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 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 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::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::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::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 done; - checkVarDefs2(done, defs, e); + foreach (vector::iterator, i, *es) + (*i)->bindVars(env); } -#endif } diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh index 0e595a1b168d..0422e5cf4638 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 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 b746e757eb88..b3624435231f 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 257dcd2e9b79..83af7ada9315 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); -- cgit 1.4.1