* Merged the `fast-eval' branch.

1 files changed, 228 insertions, 310 deletions

diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 3675dcceaf66..898fdb609417 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -1,407 +1,325 @@
 #include "nixexpr.hh"
 #include "derivations.hh"
 #include "util.hh"
-#include "aterm.hh"
-
-#include "nixexpr-ast.hh"
-#include "nixexpr-ast.cc"
 
 #include <cstdlib>
 
 
 namespace nix {
-    
 
-string showPos(ATerm pos)
+
+/* Displaying abstract syntax trees. */
+
+std::ostream & operator << (std::ostream & str, Expr & e)
 {
-    ATerm path;
-    int line, column;
-    if (matchNoPos(pos)) return "undefined position";
-    if (!matchPos(pos, path, line, column))
-        throw badTerm("position expected", pos);
-    return (format("`%1%:%2%:%3%'") % aterm2String(path) % line % column).str();
+    e.show(str);
+    return str;
 }
-    
 
-ATerm bottomupRewrite(TermFun & f, ATerm e)
+void Expr::show(std::ostream & str)
 {
-    checkInterrupt();
-
-    if (ATgetType(e) == AT_APPL) {
-        AFun fun = ATgetAFun(e);
-        int arity = ATgetArity(fun);
-        ATerm args[arity];
-
-        for (int i = 0; i < arity; ++i)
-            args[i] = bottomupRewrite(f, ATgetArgument(e, i));
-        
-        e = (ATerm) ATmakeApplArray(fun, args);
-    }
-
-    else if (ATgetType(e) == AT_LIST) {
-        ATermList in = (ATermList) e;
-        ATermList out = ATempty;
-
-        for (ATermIterator i(in); i; ++i)
-            out = ATinsert(out, bottomupRewrite(f, *i));
-
-        e = (ATerm) ATreverse(out);
-    }
+    abort();
+}
 
-    return f(e);
+void ExprInt::show(std::ostream & str)
+{
+    str << n;
 }
 
+void ExprString::show(std::ostream & str)
+{
+    str << "\"" << s << "\""; // !!! escaping
+}
 
-void queryAllAttrs(Expr e, ATermMap & attrs, bool withPos)
+void ExprPath::show(std::ostream & str)
 {
-    ATermList bnds;
-    if (!matchAttrs(e, bnds))
-        throw TypeError(format("value is %1% while an attribute set was expected") % showType(e));
+    str << s;
+}
 
-    for (ATermIterator i(bnds); i; ++i) {
-        ATerm name;
-        Expr e;
-        ATerm pos;
-        if (!matchBind(*i, name, e, pos)) abort(); /* can't happen */
-        attrs.set(name, withPos ? makeAttrRHS(e, pos) : e);
-    }
+void ExprVar::show(std::ostream & str)
+{
+    str << info.name;
 }
 
+void ExprSelect::show(std::ostream & str)
+{
+    str << "(" << *e << ")." << name;
+}
 
-Expr queryAttr(Expr e, const string & name)
+void ExprOpHasAttr::show(std::ostream & str)
 {
-    ATerm dummy;
-    return queryAttr(e, name, dummy);
+    str << "(" << *e << ") ? " << name;
 }
 
+void ExprAttrs::show(std::ostream & str)
+{
+    if (recursive) str << "rec ";
+    str << "{ ";
+    foreach (list<Inherited>::iterator, i, inherited)
+        str << "inherit " << i->first.name << "; ";
+    foreach (Attrs::iterator, i, attrs)
+        str << i->first << " = " << *i->second.first << "; ";
+    str << "}";
+}
 
-Expr queryAttr(Expr e, const string & name, ATerm & pos)
+void ExprList::show(std::ostream & str)
 {
-    ATermList bnds;
-    if (!matchAttrs(e, bnds))
-        throw TypeError(format("value is %1% while an attribute set was expected") % showType(e));
+    str << "[ ";
+    foreach (vector<Expr *>::iterator, i, elems)
+        str << "(" << **i << ") ";
+    str << "]";
+}
 
-    for (ATermIterator i(bnds); i; ++i) {
-        ATerm name2, pos2;
-        Expr e;
-        if (!matchBind(*i, name2, e, pos2))
-            abort(); /* can't happen */
-        if (aterm2String(name2) == name) {
-            pos = pos2;
-            return e;
+void ExprLambda::show(std::ostream & str)
+{
+    str << "(";
+    if (matchAttrs) {
+        str << "{ ";
+        bool first = true;
+        foreach (Formals::Formals_::iterator, i, formals->formals) {
+            if (first) first = false; else str << ", ";
+            str << i->name;
+            if (i->def) str << " ? " << *i->def;
         }
+        str << " }";
+        if (!arg.empty()) str << " @ ";
     }
-
-    return 0;
+    if (!arg.empty()) str << arg;
+    str << ": " << *body << ")";
 }
 
-
-Expr makeAttrs(const ATermMap & attrs)
+void ExprLet::show(std::ostream & str)
 {
-    ATermList bnds = ATempty;
-    for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i) {
-        Expr e;
-        ATerm pos;
-        if (!matchAttrRHS(i->value, e, pos))
-            abort(); /* can't happen */
-        bnds = ATinsert(bnds, makeBind(i->key, e, pos));
-    }
-    return makeAttrs(bnds);
+    str << "let ";
+    foreach (list<ExprAttrs::Inherited>::iterator, i, attrs->inherited)
+        str << "inherit " << i->first.name << "; ";
+    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+        str << i->first << " = " << *i->second.first << "; ";
+    str << "in " << *body;
 }
 
-
-static void varsBoundByPattern(ATermMap & map, Pattern pat)
+void ExprWith::show(std::ostream & str)
 {
-    ATerm name;
-    ATermList formals;
-    Pattern pat1, pat2;
-    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)) { 
-        for (ATermIterator i(formals); i; ++i) {
-            ATerm d1;
-            if (!matchFormal(*i, name, d1)) abort();
-            map.set(name, makeRemoved());
-        }
-    }
-    else if (matchAtPat(pat, pat1, pat2)) {
-        varsBoundByPattern(map, pat1);
-        varsBoundByPattern(map, pat2);
-    }
-    else abort();
+    str << "with " << *attrs << "; " << *body;
 }
 
+void ExprIf::show(std::ostream & str)
+{
+    str << "if " << *cond << " then " << *then << " else " << *else_;
+}
 
-Expr substitute(const Substitution & subs, Expr e)
+void ExprAssert::show(std::ostream & str)
 {
-    checkInterrupt();
+    str << "assert " << *cond << "; " << *body;
+}
 
-    //if (subs.size() == 0) return e;
+void ExprOpNot::show(std::ostream & str)
+{
+    str << "! " << *e;
+}
 
-    ATerm name, pos, e2;
+void ExprConcatStrings::show(std::ostream & str)
+{
+    bool first = true;
+    foreach (vector<Expr *>::iterator, i, *es) {
+        if (first) first = false; else str << " + ";
+        str << **i;
+    }
+}
 
-    /* As an optimisation, don't substitute in subterms known to be
-       closed. */
-    if (matchClosed(e, e2)) return e;
 
-    if (matchVar(e, name)) {
-        Expr sub = subs.lookup(name);
-        if (sub == makeRemoved()) sub = 0;
-        Expr wrapped;
-        /* Add a "closed" wrapper around terms that aren't already
-           closed.  The check is necessary to prevent repeated
-           wrapping, e.g., closed(closed(closed(...))), which kills
-           caching. */
-        return sub ? (matchClosed(sub, wrapped) ? sub : makeClosed(sub)) : e;
-    }
+std::ostream & operator << (std::ostream & str, const Pos & pos)
+{
+    if (!pos.line)
+        str << "undefined position";
+    else
+        str << (format("`%1%:%2%:%3%'") % pos.file % pos.line % pos.column).str();
+    return str;
+}
 
-    /* In case of a function, filter out all variables bound by this
-       function. */
-    Pattern pat;
-    ATerm body;
-    if (matchFunction(e, pat, body, pos)) {
-        ATermMap map(16);
-        varsBoundByPattern(map, pat);
-        Substitution subs2(&subs, &map);
-        return makeFunction(
-            (Pattern) substitute(subs2, (Expr) pat),
-            substitute(subs2, body), pos);
-    }
 
-    /* Idem for a mutually recursive attribute set. */
-    ATermList rbnds, nrbnds;
-    if (matchRec(e, rbnds, nrbnds)) {
-        ATermMap map(ATgetLength(rbnds) + ATgetLength(nrbnds));
-        for (ATermIterator i(rbnds); i; ++i)
-            if (matchBind(*i, name, e2, pos)) map.set(name, makeRemoved());
-            else abort(); /* can't happen */
-        for (ATermIterator i(nrbnds); i; ++i)
-            if (matchBind(*i, name, e2, pos)) map.set(name, makeRemoved());
-            else abort(); /* can't happen */
-        return makeRec(
-            (ATermList) substitute(Substitution(&subs, &map), (ATerm) rbnds),
-            (ATermList) substitute(subs, (ATerm) nrbnds));
-    }
+Pos noPos;
 
-    if (ATgetType(e) == AT_APPL) {
-        AFun fun = ATgetAFun(e);
-        int arity = ATgetArity(fun);
-        ATerm args[arity];
-        bool changed = false;
 
-        for (int i = 0; i < arity; ++i) {
-            ATerm arg = ATgetArgument(e, i);
-            args[i] = substitute(subs, arg);
-            if (args[i] != arg) changed = true;
-        }
-        
-        return changed ? (ATerm) ATmakeApplArray(fun, args) : e;
-    }
+/* Computing levels/displacements for variables. */
 
-    if (ATgetType(e) == AT_LIST) {
-        unsigned int len = ATgetLength((ATermList) e);
-        ATerm es[len];
-        ATermIterator i((ATermList) e);
-        for (unsigned int j = 0; i; ++i, ++j)
-            es[j] = substitute(subs, *i);
-        ATermList out = ATempty;
-        for (unsigned int j = len; j; --j)
-            out = ATinsert(out, es[j - 1]);
-        return (ATerm) out;
-    }
+void Expr::bindVars(const StaticEnv & env)
+{
+    abort();
+}
 
-    return e;
+void ExprInt::bindVars(const StaticEnv & env)
+{
 }
 
+void ExprString::bindVars(const StaticEnv & 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 ExprPath::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;
-    
-    else if (matchVar(e, name)) {
-        if (!defs.get(name))
-            throw EvalError(format("undefined variable `%1%'")
-                % aterm2String(name));
-    }
+}
 
-    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);
+void VarRef::bind(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;
+            }
         }
-        set<Expr> done2;
-        checkVarDefs2(done2, defs2, (ATerm) rbnds);
     }
 
-    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);
-    }
-    
-    else if (ATgetType(e) == AT_APPL) {
-        int arity = ATgetArity(ATgetAFun(e));
-        for (int i = 0; i < arity; ++i)
-            checkVarDefs2(done, defs, ATgetArgument(e, i));
-    }
+    /* 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);
 
-    else if (ATgetType(e) == AT_LIST)
-        for (ATermIterator i((ATermList) e); i; ++i)
-            checkVarDefs2(done, defs, *i);
+    fromWith = true;
+    this->level = withLevel;
 }
 
-
-void checkVarDefs(const ATermMap & defs, Expr e)
+void ExprVar::bindVars(const StaticEnv & env)
 {
-    set<Expr> done;
-    checkVarDefs2(done, defs, e);
+    info.bind(env);
 }
 
+void ExprSelect::bindVars(const StaticEnv & env)
+{
+    e->bindVars(env);
+}
 
-struct Canonicalise : TermFun
+void ExprOpHasAttr::bindVars(const StaticEnv & env)
 {
-    ATerm operator () (ATerm e)
-    {
-        /* Remove position info. */
-        ATerm path;
-        int line, column;
-        if (matchPos(e, path, line, column))
-            return makeNoPos();
+    e->bindVars(env);
+}
 
-        /* Sort attribute sets. */
-        ATermList _;
-        if (matchAttrs(e, _)) {
-            ATermMap attrs;
-            queryAllAttrs(e, attrs);
-            StringSet names;
-            for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i)
-                names.insert(aterm2String(i->key));
+void ExprAttrs::bindVars(const StaticEnv & env)
+{
+    if (recursive) {
+        StaticEnv newEnv(false, &env);
+    
+        unsigned int displ = 0;
 
-            ATermList attrs2 = ATempty;
-            for (StringSet::reverse_iterator i = names.rbegin(); i != names.rend(); ++i)
-                attrs2 = ATinsert(attrs2,
-                    makeBind(toATerm(*i), attrs.get(toATerm(*i)), makeNoPos()));
+        foreach (ExprAttrs::Attrs::iterator, i, attrs)
+            newEnv.vars[i->first] = displ++;
 
-            return makeAttrs(attrs2);
+        foreach (list<Inherited>::iterator, i, inherited) {
+            newEnv.vars[i->first.name] = displ++;
+            i->first.bind(env);
         }
-        
-        return e;
+
+        foreach (ExprAttrs::Attrs::iterator, i, attrs)
+            i->second.first->bindVars(newEnv);
     }
-};
 
+    else {
+        foreach (ExprAttrs::Attrs::iterator, i, attrs)
+            i->second.first->bindVars(env);
 
-Expr canonicaliseExpr(Expr e)
-{
-    Canonicalise canonicalise;
-    return bottomupRewrite(canonicalise, e);
+        foreach (list<Inherited>::iterator, i, inherited)
+            i->first.bind(env);
+    }
 }
 
-
-Expr makeBool(bool b)
+void ExprList::bindVars(const StaticEnv & env)
 {
-    return b ? eTrue : eFalse;
+    foreach (vector<Expr *>::iterator, i, elems)
+        (*i)->bindVars(env);
 }
 
-
-bool matchStr(Expr e, string & s, PathSet & context)
+void ExprLambda::bindVars(const StaticEnv & env)
 {
-    ATermList l;
-    ATerm s_;
-
-    if (!matchStr(e, s_, l)) return false;
+    StaticEnv newEnv(false, &env);
+    
+    unsigned int displ = 0;
+    
+    if (!arg.empty()) newEnv.vars[arg] = displ++;
 
-    s = aterm2String(s_);
+    if (matchAttrs) {
+        foreach (Formals::Formals_::iterator, i, formals->formals)
+            newEnv.vars[i->name] = displ++;
 
-    for (ATermIterator i(l); i; ++i)
-        context.insert(aterm2String(*i));
+        foreach (Formals::Formals_::iterator, i, formals->formals)
+            if (i->def) i->def->bindVars(newEnv);
+    }
 
-    return true;
+    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<ExprAttrs::Inherited>::iterator, i, attrs->inherited) {
+        newEnv.vars[i->first.name] = displ++;
+        i->first.bind(env);
+    }
 
-Expr makeStr(const string & s, const PathSet & context)
+    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+        i->second.first->bindVars(newEnv);
+    
+    body->bindVars(newEnv);
+}
+
+void ExprWith::bindVars(const StaticEnv & env)
 {
-    return makeStr(toATerm(s), toATermList(context));
+    /* Does this `with' have an enclosing `with'?  If so, record its
+       level so that `lookupVar' can look up variables in the previous
+       `with' if this one doesn't contain the desired attribute. */
+    const StaticEnv * curEnv;
+    unsigned int level;
+    prevWith = 0;
+    for (curEnv = &env, level = 1; curEnv; curEnv = curEnv->up, level++)
+        if (curEnv->isWith) {
+            prevWith = level;
+            break;
+        }
+    
+    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);
+}
 
-string showType(Expr e)
+void ExprAssert::bindVars(const StaticEnv & env)
 {
-    ATerm t1, t2;
-    ATermList l1;
-    ATermBlob b1;
-    int i1;
-    Pattern p1;
-    if (matchStr(e, t1, l1)) return "a string";
-    if (matchPath(e, t1)) return "a path";
-    if (matchNull(e)) return "null";
-    if (matchInt(e, i1)) return "an integer";
-    if (matchBool(e, t1)) return "a boolean";
-    if (matchFunction(e, p1, t1, t2)) return "a function";
-    if (matchAttrs(e, l1)) return "an attribute set";
-    if (matchList(e, l1)) return "a list";
-    if (matchPrimOp(e, i1, b1, l1)) return "a partially applied built-in function";
-    return "an unknown type";
+    cond->bindVars(env);
+    body->bindVars(env);
 }
 
+void ExprOpNot::bindVars(const StaticEnv & env)
+{
+    e->bindVars(env);
+}
 
-string showValue(Expr e)
+void ExprConcatStrings::bindVars(const StaticEnv & env)
 {
-    PathSet context;
-    string s;
-    ATerm s2;
-    int i;
-    if (matchStr(e, s, context)) {
-        string u;
-        for (string::iterator i = s.begin(); i != s.end(); ++i)
-            if (*i == '\"' || *i == '\\') u += "\\" + *i;
-            else if (*i == '\n') u += "\\n";
-            else if (*i == '\r') u += "\\r";
-            else if (*i == '\t') u += "\\t";
-            else u += *i;
-        return "\"" + u + "\"";
-    }
-    if (matchPath(e, s2)) return aterm2String(s2);
-    if (matchNull(e)) return "null";
-    if (matchInt(e, i)) return (format("%1%") % i).str();
-    if (e == eTrue) return "true";
-    if (e == eFalse) return "false";
-    /* !!! incomplete */
-    return "<unknown>";
+    foreach (vector<Expr *>::iterator, i, *es)
+        (*i)->bindVars(env);
 }
 
- 
+
 }