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/nixexpr.cc | 218 +++++++++++++++++++++++++++++++------------------ 1 file changed, 139 insertions(+), 79 deletions(-) (limited to 'src/libexpr/nixexpr.cc') diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc index 4040cacc81..46cbb48ac5 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 } -- cgit 1.4.1