about summary refs log tree commit diff
path: root/src/libexpr/nixexpr.cc
diff options
context:
space:
mode:
authorEelco Dolstra <e.dolstra@tudelft.nl>2010-04-14T14·42+0000
committerEelco Dolstra <e.dolstra@tudelft.nl>2010-04-14T14·42+0000
commit9985230c00226826949473c3862c0c3afea74aaf (patch)
treed221b96649f2a134cce366efdfc5685145567aa2 /src/libexpr/nixexpr.cc
parent816dd3f0612111718c338842283c1ee6577b9f0a (diff)
* 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.

Diffstat (limited to 'src/libexpr/nixexpr.cc')
-rw-r--r--src/libexpr/nixexpr.cc218
1 files changed, 139 insertions, 79 deletions
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
 
 
 }