* 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.

7 files changed, 250 insertions, 135 deletions

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<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 eda081261c39..a24b7345efab 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 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<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 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<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 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);