From 705868a8a96a10f70e629433cfffc2d5cd2703eb Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Mon, 4 Oct 2010 17:55:38 +0000
Subject: * Make sure that config.h is included before the system headers,  
 because it defines _FILE_OFFSET_BITS.  Without this, on   OpenSolaris the
 system headers define it to be 32, and then   the 32-bit stat() ends up being
 called with a 64-bit "struct   stat", or vice versa.

  This also ensures that we get 64-bit file sizes everywhere.

* Remove the redundant call to stat() in parseExprFromFile().
  The file cannot be a symlink because that's the exit condition
  of the loop before.
---
 src/libexpr/primops.cc | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'src/libexpr/primops.cc')

diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 68f66acc74ed..973670e68384 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -1,5 +1,5 @@
-#include "misc.hh"
 #include "eval.hh"
+#include "misc.hh"
 #include "globals.hh"
 #include "store-api.hh"
 #include "util.hh"
-- 
cgit 1.4.1


From 41c45a9b319a5578e2731505ca3de2b9c50b4988 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Fri, 22 Oct 2010 14:47:42 +0000
Subject: * Store Value nodes outside of attribute sets.  I.e., Attr now stores
   a pointer to a Value, rather than the Value directly.  This improves   the
 effectiveness of garbage collection a lot: if the Value is   stored inside
 the set directly, then any live pointer to the Value   causes all other
 attributes in the set to be live as well.

---
 src/libexpr/Makefile.am                |  2 +-
 src/libexpr/attr-path.cc               |  5 +-
 src/libexpr/attr-path.hh               |  2 +-
 src/libexpr/common-opts.cc             |  7 +--
 src/libexpr/eval.cc                    | 97 ++++++++++++++++++++--------------
 src/libexpr/eval.hh                    |  7 ++-
 src/libexpr/get-drvs.cc                | 40 +++++++-------
 src/libexpr/get-drvs.hh                |  2 +-
 src/libexpr/nixexpr.cc                 |  4 +-
 src/libexpr/nixexpr.hh                 |  1 +
 src/libexpr/primops.cc                 | 70 ++++++++++++------------
 src/libexpr/value-to-xml.cc            | 14 ++---
 src/nix-env/nix-env.cc                 |  4 +-
 src/nix-env/user-env.cc                | 23 ++++----
 src/nix-instantiate/nix-instantiate.cc |  2 +-
 15 files changed, 150 insertions(+), 130 deletions(-)

(limited to 'src/libexpr/primops.cc')

diff --git a/src/libexpr/Makefile.am b/src/libexpr/Makefile.am
index e7228e183581..6c38ecdd565f 100644
--- a/src/libexpr/Makefile.am
+++ b/src/libexpr/Makefile.am
@@ -11,7 +11,7 @@ pkginclude_HEADERS = \
  names.hh symbol-table.hh
 
 libexpr_la_LIBADD = ../libutil/libutil.la ../libstore/libstore.la \
- ../boost/format/libformat.la
+ ../boost/format/libformat.la @boehmgc_lib@
 
 BUILT_SOURCES = \
  parser-tab.hh lexer-tab.hh parser-tab.cc lexer-tab.cc
diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
index 0660ba1c1efc..365b03c0bf60 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -5,8 +5,9 @@
 namespace nix {
 
 
+// !!! Shouldn't we return a pointer to a Value?
 void findAlongAttrPath(EvalState & state, const string & attrPath,
-    const Bindings & autoArgs, Expr * e, Value & v)
+    Bindings & autoArgs, Expr * e, Value & v)
 {
     Strings tokens = tokenizeString(attrPath, ".");
 
@@ -48,7 +49,7 @@ void findAlongAttrPath(EvalState & state, const string & attrPath,
             Bindings::iterator a = v.attrs->find(state.symbols.create(attr));
             if (a == v.attrs->end())
                 throw Error(format("attribute `%1%' in selection path `%2%' not found") % attr % curPath);
-            v = a->second.value;
+            v = *a->second.value;
         }
 
         else if (apType == apIndex) {
diff --git a/src/libexpr/attr-path.hh b/src/libexpr/attr-path.hh
index b4f5c29d2ed8..b106da5ef817 100644
--- a/src/libexpr/attr-path.hh
+++ b/src/libexpr/attr-path.hh
@@ -11,7 +11,7 @@ namespace nix {
 
     
 void findAlongAttrPath(EvalState & state, const string & attrPath,
-    const Bindings & autoArgs, Expr * e, Value & v);
+    Bindings & autoArgs, Expr * e, Value & v);
 
     
 }
diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc
index 9131951e315d..6b393c07df50 100644
--- a/src/libexpr/common-opts.cc
+++ b/src/libexpr/common-opts.cc
@@ -20,12 +20,13 @@ bool parseOptionArg(const string & arg, Strings::iterator & i,
     if (i == argsEnd) throw error;
     string value = *i++;
 
-    Value & v(autoArgs[state.symbols.create(name)].value);
+    Value * v = state.allocValue();
+    autoArgs[state.symbols.create(name)].value = v;
 
     if (arg == "--arg")
-        state.mkThunk_(v, parseExprFromString(state, value, absPath(".")));
+        state.mkThunk_(*v, parseExprFromString(state, value, absPath(".")));
     else
-        mkString(v, value);
+        mkString(*v, value);
     
     return true;
 }
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index c8a031ac6d0a..ea48947258ec 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -58,7 +58,7 @@ std::ostream & operator << (std::ostream & str, const Value & v)
         typedef std::map<string, Value *> Sorted;
         Sorted sorted;
         foreach (Bindings::iterator, i, *v.attrs)
-            sorted[i->first] = &i->second.value;
+            sorted[i->first] = i->second.value;
         foreach (Sorted::iterator, i, sorted)
             str << i->first << " = " << *i->second << "; ";
         str << "}";
@@ -145,24 +145,26 @@ EvalState::~EvalState()
 
 void EvalState::addConstant(const string & name, Value & v)
 {
+    Value * v2 = allocValue();
+    *v2 = v;
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v;
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
-    (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
+    (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v2;
 }
 
 
 void EvalState::addPrimOp(const string & name,
     unsigned int arity, PrimOp primOp)
 {
-    Value v;
+    Value * v = allocValue();
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
-    v.type = tPrimOp;
-    v.primOp.arity = arity;
-    v.primOp.fun = primOp;
-    v.primOp.name = GC_STRDUP(name2.c_str());
+    v->type = tPrimOp;
+    v->primOp.arity = arity;
+    v->primOp.fun = primOp;
+    v->primOp.name = GC_STRDUP(name2.c_str());
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
-    baseEnv.values[baseEnvDispl++] = v;
+    baseEnv.values[baseEnvDispl++] = *v;
     (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
 }
 
@@ -265,7 +267,7 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
         while (1) {
             Bindings::iterator j = env->values[0].attrs->find(var.name);
             if (j != env->values[0].attrs->end())
-                return &j->second.value;
+                return j->second.value;
             if (env->prevWith == 0)
                 throwEvalError("undefined variable `%1%'", var.name);
             for (unsigned int l = env->prevWith; l; --l, env = env->up) ;
@@ -275,6 +277,13 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
 }
 
 
+Value * EvalState::allocValue()
+{
+    nrValues++;
+    return (Value *) GC_MALLOC(sizeof(Value));
+}
+
+
 Value * EvalState::allocValues(unsigned int count)
 {
     nrValues += count;
@@ -291,6 +300,14 @@ Env & EvalState::allocEnv(unsigned int size)
 }
 
 
+Value * EvalState::allocAttr(Value & vAttrs, const Symbol & name)
+{
+    Attr & a = (*vAttrs.attrs)[name];
+    a.value = allocValue();
+    return a.value;
+}
+
+    
 void EvalState::mkList(Value & v, unsigned int length)
 {
     v.type = tList;
@@ -321,11 +338,8 @@ void EvalState::mkThunk_(Value & v, Expr * expr)
 void EvalState::cloneAttrs(Value & src, Value & dst)
 {
     mkAttrs(dst);
-    foreach (Bindings::iterator, i, *src.attrs) {
-        Attr & a = (*dst.attrs)[i->first];
-        mkCopy(a.value, i->second.value);
-        a.pos = i->second.pos;
-    }
+    foreach (Bindings::iterator, i, *src.attrs)
+        (*dst.attrs)[i->first] = i->second;
 }
 
 
@@ -449,8 +463,9 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
            environment. */
         foreach (Attrs::iterator, i, attrs) {
             nix::Attr & a = (*v.attrs)[i->first];
-            mkThunk(a.value, env2, i->second.first);
-            mkCopy(env2.values[displ++], a.value);
+            a.value = state.allocValue();
+            mkThunk(*a.value, env2, i->second.first);
+            mkCopy(env2.values[displ++], *a.value);
             a.pos = &i->second.second;
         }
 
@@ -459,7 +474,7 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
         foreach (list<Inherited>::iterator, i, inherited) {
             nix::Attr & a = (*v.attrs)[i->first.name];
             Value * v2 = state.lookupVar(&env, i->first);
-            mkCopy(a.value, *v2);
+            a.value = v2;
             mkCopy(env2.values[displ++], *v2);
             a.pos = &i->second;
         }
@@ -474,10 +489,12 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
            Hence we need __overrides.) */
         Bindings::iterator overrides = v.attrs->find(state.sOverrides);
         if (overrides != v.attrs->end()) {
-            state.forceAttrs(overrides->second.value);
-            foreach (Bindings::iterator, i, *overrides->second.value.attrs) {
+            state.forceAttrs(*overrides->second.value);
+            foreach (Bindings::iterator, i, *overrides->second.value->attrs) {
                 nix::Attr & a = (*v.attrs)[i->first];
-                mkCopy(a.value, i->second.value);
+                if (a.value)
+                    mkCopy(env2.values[displs[i->first]], *i->second.value);
+                a = i->second;
             }
         }
     }
@@ -485,13 +502,14 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
     else {
         foreach (Attrs::iterator, i, attrs) {
             nix::Attr & a = (*v.attrs)[i->first];
-            mkThunk(a.value, env, i->second.first);
+            a.value = state.allocValue();
+            mkThunk(*a.value, env, i->second.first);
             a.pos = &i->second.second;
         }
 
         foreach (list<Inherited>::iterator, i, inherited) {
             nix::Attr & a = (*v.attrs)[i->first.name];
-            mkCopy(a.value, *state.lookupVar(&env, i->first));
+            a.value = state.lookupVar(&env, i->first);
             a.pos = &i->second;
         }
     }
@@ -548,13 +566,13 @@ void ExprSelect::eval(EvalState & state, Env & env, Value & v)
     if (i == v2.attrs->end())
         throwEvalError("attribute `%1%' missing", name);
     try {            
-        state.forceValue(i->second.value);
+        state.forceValue(*i->second.value);
     } catch (Error & e) {
         addErrorPrefix(e, "while evaluating the attribute `%1%' at %2%:\n",
             name, *i->second.pos);
         throw;
     }
-    v = i->second.value;
+    v = *i->second.value;
 }
 
 
@@ -578,9 +596,9 @@ void ExprApp::eval(EvalState & state, Env & env, Value & v)
 {
     Value vFun;
     state.eval(env, e1, vFun);
-    Value vArg;
-    mkThunk(vArg, env, e2); // !!! should this be on the heap?
-    state.callFunction(vFun, vArg, v);
+    Value * vArg = state.allocValue();
+    mkThunk(*vArg, env, e2);
+    state.callFunction(vFun, *vArg, v);
 }
 
 
@@ -656,7 +674,7 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
                 mkThunk(env2.values[displ++], env2, i->def);
             } else {
                 attrsUsed++;
-                mkCopy(env2.values[displ++], j->second.value);
+                mkCopy(env2.values[displ++], *j->second.value);
             }
         }
 
@@ -677,7 +695,7 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
 }
 
 
-void EvalState::autoCallFunction(const Bindings & args, Value & fun, Value & res)
+void EvalState::autoCallFunction(Bindings & args, Value & fun, Value & res)
 {
     forceValue(fun);
 
@@ -690,7 +708,7 @@ void EvalState::autoCallFunction(const Bindings & args, Value & fun, Value & res
     mkAttrs(actualArgs);
 
     foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
-        Bindings::const_iterator j = args.find(i->name);
+        Bindings::iterator j = args.find(i->name);
         if (j != args.end())
             (*actualArgs.attrs)[i->name] = j->second;
         else if (!i->def)
@@ -780,11 +798,8 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
 
     state.cloneAttrs(v1, v);
 
-    foreach (Bindings::iterator, i, *v2.attrs) {
-        Attr & a = (*v.attrs)[i->first];
-        mkCopy(a.value, i->second.value);
-        a.pos = i->second.pos;
-    }
+    foreach (Bindings::iterator, i, *v2.attrs)
+        (*v.attrs)[i->first] = i->second;
 
     state.nrOpUpdateValuesCopied += v.attrs->size();
 }
@@ -866,7 +881,7 @@ void EvalState::strictForceValue(Value & v)
     
     if (v.type == tAttrs) {
         foreach (Bindings::iterator, i, *v.attrs)
-            strictForceValue(i->second.value);
+            strictForceValue(*i->second.value);
     }
     
     else if (v.type == tList) {
@@ -957,7 +972,7 @@ bool EvalState::isDerivation(Value & v)
 {
     if (v.type != tAttrs) return false;
     Bindings::iterator i = v.attrs->find(sType);
-    return i != v.attrs->end() && forceStringNoCtx(i->second.value) == "derivation";
+    return i != v.attrs->end() && forceStringNoCtx(*i->second.value) == "derivation";
 }
 
 
@@ -1001,7 +1016,7 @@ string EvalState::coerceToString(Value & v, PathSet & context,
         Bindings::iterator i = v.attrs->find(sOutPath);
         if (i == v.attrs->end())
             throwTypeError("cannot coerce an attribute set (except a derivation) to a string");
-        return coerceToString(i->second.value, context, coerceMore, copyToStore);
+        return coerceToString(*i->second.value, context, coerceMore, copyToStore);
     }
 
     if (coerceMore) {
@@ -1087,9 +1102,9 @@ bool EvalState::eqValues(Value & v1, Value & v2)
 
         case tAttrs: {
             if (v1.attrs->size() != v2.attrs->size()) return false;
-            Bindings::iterator i, j;
-            for (i = v1.attrs->begin(), j = v2.attrs->begin(); i != v1.attrs->end(); ++i, ++j)
-                if (i->first != j->first || !eqValues(i->second.value, j->second.value))
+            Bindings::iterator i = v1.attrs->begin(), j = v2.attrs->begin();
+            for ( ; i != v1.attrs->end(); ++i, ++j)
+                if (i->first != j->first || !eqValues(*i->second.value, *j->second.value))
                     return false;
             return true;
         }
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 738ca9439f6d..ee7db91a08b2 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -122,7 +122,7 @@ struct Env
 
 struct Attr
 {
-    Value value;
+    Value * value;
     Pos * pos;
     Attr() : pos(&noPos) { };
 };
@@ -294,12 +294,15 @@ public:
 
     /* Automatically call a function for which each argument has a
        default value or has a binding in the `args' map. */
-    void autoCallFunction(const Bindings & args, Value & fun, Value & res);
+    void autoCallFunction(Bindings & args, Value & fun, Value & res);
     
     /* Allocation primitives. */
+    Value * allocValue();
     Value * allocValues(unsigned int count);
     Env & allocEnv(unsigned int size);
 
+    Value * allocAttr(Value & vAttrs, const Symbol & name);
+
     void mkList(Value & v, unsigned int length);
     void mkAttrs(Value & v);
     void mkThunk_(Value & v, Expr * expr);
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 82a92416bed6..63106b87b5af 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -10,7 +10,7 @@ string DrvInfo::queryDrvPath(EvalState & state) const
     if (drvPath == "" && attrs) {
         Bindings::iterator i = attrs->find(state.sDrvPath);
         PathSet context;
-        (string &) drvPath = i != attrs->end() ? state.coerceToPath(i->second.value, context) : "";
+        (string &) drvPath = i != attrs->end() ? state.coerceToPath(*i->second.value, context) : "";
     }
     return drvPath;
 }
@@ -21,7 +21,7 @@ string DrvInfo::queryOutPath(EvalState & state) const
     if (outPath == "" && attrs) {
         Bindings::iterator i = attrs->find(state.sOutPath);
         PathSet context;
-        (string &) outPath = i != attrs->end() ? state.coerceToPath(i->second.value, context) : "";
+        (string &) outPath = i != attrs->end() ? state.coerceToPath(*i->second.value, context) : "";
     }
     return outPath;
 }
@@ -36,21 +36,21 @@ MetaInfo DrvInfo::queryMetaInfo(EvalState & state) const
     Bindings::iterator a = attrs->find(state.sMeta);
     if (a == attrs->end()) return meta; /* fine, empty meta information */
 
-    state.forceAttrs(a->second.value);
+    state.forceAttrs(*a->second.value);
 
-    foreach (Bindings::iterator, i, *a->second.value.attrs) {
+    foreach (Bindings::iterator, i, *a->second.value->attrs) {
         MetaValue value;
-        state.forceValue(i->second.value);
-        if (i->second.value.type == tString) {
+        state.forceValue(*i->second.value);
+        if (i->second.value->type == tString) {
             value.type = MetaValue::tpString;
-            value.stringValue = i->second.value.string.s;
-        } else if (i->second.value.type == tInt) {
+            value.stringValue = i->second.value->string.s;
+        } else if (i->second.value->type == tInt) {
             value.type = MetaValue::tpInt;
-            value.intValue = i->second.value.integer;
-        } else if (i->second.value.type == tList) {
+            value.intValue = i->second.value->integer;
+        } else if (i->second.value->type == tList) {
             value.type = MetaValue::tpStrings;
-            for (unsigned int j = 0; j < i->second.value.list.length; ++j)
-                value.stringValues.push_back(state.forceStringNoCtx(*i->second.value.list.elems[j]));
+            for (unsigned int j = 0; j < i->second.value->list.length; ++j)
+                value.stringValues.push_back(state.forceStringNoCtx(*i->second.value->list.elems[j]));
         } else continue;
         ((MetaInfo &) meta)[i->first] = value;
     }
@@ -99,13 +99,13 @@ static bool getDerivation(EvalState & state, Value & v,
         Bindings::iterator i = v.attrs->find(state.sName);
         /* !!! We really would like to have a decent back trace here. */
         if (i == v.attrs->end()) throw TypeError("derivation name missing");
-        drv.name = state.forceStringNoCtx(i->second.value);
+        drv.name = state.forceStringNoCtx(*i->second.value);
 
-        i = v.attrs->find(state.sSystem);
-        if (i == v.attrs->end())
+        Bindings::iterator i2 = v.attrs->find(state.sSystem);
+        if (i2 == v.attrs->end())
             drv.system = "unknown";
         else
-            drv.system = state.forceStringNoCtx(i->second.value);
+            drv.system = state.forceStringNoCtx(*i2->second.value);
 
         drv.attrs = v.attrs;
 
@@ -138,7 +138,7 @@ static string addToPath(const string & s1, const string & s2)
 
 
 static void getDerivations(EvalState & state, Value & vIn,
-    const string & pathPrefix, const Bindings & autoArgs,
+    const string & pathPrefix, Bindings & autoArgs,
     DrvInfos & drvs, Done & done)
 {
     Value v;
@@ -168,7 +168,7 @@ static void getDerivations(EvalState & state, Value & vIn,
         foreach (SortedSymbols::iterator, i, attrs) {
             startNest(nest, lvlDebug, format("evaluating attribute `%1%'") % i->first);
             string pathPrefix2 = addToPath(pathPrefix, i->first);
-            Value & v2((*v.attrs)[i->second].value);
+            Value & v2(*(*v.attrs)[i->second].value);
             if (combineChannels)
                 getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
             else if (getDerivation(state, v2, pathPrefix2, drvs, done)) {
@@ -178,7 +178,7 @@ static void getDerivations(EvalState & state, Value & vIn,
                    attribute. */
                 if (v2.type == tAttrs) {
                     Bindings::iterator j = v2.attrs->find(state.symbols.create("recurseForDerivations"));
-                    if (j != v2.attrs->end() && state.forceBool(j->second.value))
+                    if (j != v2.attrs->end() && state.forceBool(*j->second.value))
                         getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
                 }
             }
@@ -200,7 +200,7 @@ static void getDerivations(EvalState & state, Value & vIn,
 
 
 void getDerivations(EvalState & state, Value & v, const string & pathPrefix,
-    const Bindings & autoArgs, DrvInfos & drvs)
+    Bindings & autoArgs, DrvInfos & drvs)
 {
     Done done;
     getDerivations(state, v, pathPrefix, autoArgs, drvs, done);
diff --git a/src/libexpr/get-drvs.hh b/src/libexpr/get-drvs.hh
index 7b96decf4a08..7c014b7e41f2 100644
--- a/src/libexpr/get-drvs.hh
+++ b/src/libexpr/get-drvs.hh
@@ -70,7 +70,7 @@ typedef list<DrvInfo> DrvInfos;
 bool getDerivation(EvalState & state, Value & v, DrvInfo & drv);
 
 void getDerivations(EvalState & state, Value & v, const string & pathPrefix,
-    const Bindings & autoArgs, DrvInfos & drvs);
+    Bindings & autoArgs, DrvInfos & drvs);
 
  
 }
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 898fdb609417..9f2ea78831f2 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -213,10 +213,10 @@ void ExprAttrs::bindVars(const StaticEnv & env)
         unsigned int displ = 0;
 
         foreach (ExprAttrs::Attrs::iterator, i, attrs)
-            newEnv.vars[i->first] = displ++;
+            displs[i->first] = newEnv.vars[i->first] = displ++;
 
         foreach (list<Inherited>::iterator, i, inherited) {
-            newEnv.vars[i->first.name] = displ++;
+            displs[i->first.name] = newEnv.vars[i->first.name] = displ++;
             i->first.bind(env);
         }
 
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 1d03220f644a..5c0071dca2ce 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -137,6 +137,7 @@ struct ExprAttrs : Expr
     Attrs attrs;
     list<Inherited> inherited;
     std::map<Symbol, Pos> attrNames; // used during parsing
+    std::map<Symbol, unsigned int> displs;
     ExprAttrs() : recursive(false) { };
     COMMON_METHODS
 };
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 973670e68384..c7709ca9eb36 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -119,24 +119,24 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
         args[0]->attrs->find(state.symbols.create("startSet"));
     if (startSet == args[0]->attrs->end())
         throw EvalError("attribute `startSet' required");
-    state.forceList(startSet->second.value);
+    state.forceList(*startSet->second.value);
 
     list<Value *> workSet;
-    for (unsigned int n = 0; n < startSet->second.value.list.length; ++n)
-        workSet.push_back(startSet->second.value.list.elems[n]);
+    for (unsigned int n = 0; n < startSet->second.value->list.length; ++n)
+        workSet.push_back(startSet->second.value->list.elems[n]);
 
     /* Get the operator. */
     Bindings::iterator op =
         args[0]->attrs->find(state.symbols.create("operator"));
     if (op == args[0]->attrs->end())
         throw EvalError("attribute `operator' required");
-    state.forceValue(op->second.value);
+    state.forceValue(*op->second.value);
 
     /* Construct the closure by applying the operator to element of
        `workSet', adding the result to `workSet', continuing until
        no new elements are found. */
     list<Value> res;
-    set<Value, CompareValues> doneKeys;
+    set<Value, CompareValues> doneKeys; // !!! use Value *?
     while (!workSet.empty()) {
 	Value * e = *(workSet.begin());
 	workSet.pop_front();
@@ -147,15 +147,15 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
             e->attrs->find(state.symbols.create("key"));
         if (key == e->attrs->end())
             throw EvalError("attribute `key' required");
-        state.forceValue(key->second.value);
+        state.forceValue(*key->second.value);
 
-        if (doneKeys.find(key->second.value) != doneKeys.end()) continue;
-        doneKeys.insert(key->second.value);
+        if (doneKeys.find(*key->second.value) != doneKeys.end()) continue;
+        doneKeys.insert(*key->second.value);
         res.push_back(*e);
         
         /* Call the `operator' function with `e' as argument. */
         Value call;
-        mkApp(call, op->second.value, *e);
+        mkApp(call, *op->second.value, *e);
         state.forceList(call);
 
         /* Add the values returned by the operator to the work set. */
@@ -213,11 +213,13 @@ static void prim_tryEval(EvalState & state, Value * * args, Value & v)
     state.mkAttrs(v);
     try {
         state.forceValue(*args[0]);
-        (*v.attrs)[state.symbols.create("value")].value = *args[0];
-        mkBool((*v.attrs)[state.symbols.create("success")].value, true);
+        printMsg(lvlError, format("%1%") % *args[0]);
+        (*v.attrs)[state.symbols.create("value")].value = args[0];
+        mkBool(*state.allocAttr(v, state.symbols.create("success")), true);
+        printMsg(lvlError, format("%1%") % v);
     } catch (AssertionError & e) {
-        mkBool((*v.attrs)[state.symbols.create("value")].value, false);
-        mkBool((*v.attrs)[state.symbols.create("success")].value, false);
+        mkBool(*state.allocAttr(v, state.symbols.create("value")), false);
+        mkBool(*state.allocAttr(v, state.symbols.create("success")), false);
     }
 }
 
@@ -326,7 +328,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     string drvName;
     Pos & posDrvName(*attr->second.pos);
     try {        
-        drvName = state.forceStringNoCtx(attr->second.value);
+        drvName = state.forceStringNoCtx(*attr->second.value);
     } catch (Error & e) {
         e.addPrefix(format("while evaluating the derivation attribute `name' at %1%:\n") % posDrvName);
         throw;
@@ -349,9 +351,9 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
             /* The `args' attribute is special: it supplies the
                command-line arguments to the builder. */
             if (key == "args") {
-                state.forceList(i->second.value);
-                for (unsigned int n = 0; n < i->second.value.list.length; ++n) {
-                    string s = state.coerceToString(*i->second.value.list.elems[n], context, true);
+                state.forceList(*i->second.value);
+                for (unsigned int n = 0; n < i->second.value->list.length; ++n) {
+                    string s = state.coerceToString(*i->second.value->list.elems[n], context, true);
                     drv.args.push_back(s);
                 }
             }
@@ -359,7 +361,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
             /* All other attributes are passed to the builder through
                the environment. */
             else {
-                string s = state.coerceToString(i->second.value, context, true);
+                string s = state.coerceToString(*i->second.value, context, true);
                 drv.env[key] = s;
                 if (key == "builder") drv.builder = s;
                 else if (i->first == state.sSystem) drv.platform = s;
@@ -488,8 +490,8 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
 
     /* !!! assumes a single output */
     state.mkAttrs(v);
-    mkString((*v.attrs)[state.sOutPath].value, outPath, singleton<PathSet>(drvPath));
-    mkString((*v.attrs)[state.sDrvPath].value, drvPath, singleton<PathSet>("=" + drvPath));
+    mkString(*state.allocAttr(v, state.sOutPath), outPath, singleton<PathSet>(drvPath));
+    mkString(*state.allocAttr(v, state.sDrvPath), drvPath, singleton<PathSet>("=" + drvPath));
 }
 
 
@@ -713,8 +715,8 @@ static void prim_getAttr(EvalState & state, Value * * args, Value & v)
     if (i == args[1]->attrs->end())
         throw EvalError(format("attribute `%1%' missing") % attr);
     // !!! add to stack trace?
-    state.forceValue(i->second.value);
-    v = i->second.value;
+    state.forceValue(*i->second.value);
+    v = *i->second.value;
 }
 
 
@@ -766,15 +768,13 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
         Bindings::iterator j = v2.attrs->find(state.sName);
         if (j == v2.attrs->end())
             throw TypeError("`name' attribute missing in a call to `listToAttrs'");
-        string name = state.forceStringNoCtx(j->second.value);
+        string name = state.forceStringNoCtx(*j->second.value);
         
-        j = v2.attrs->find(state.symbols.create("value"));
-        if (j == v2.attrs->end())
+        Bindings::iterator j2 = v2.attrs->find(state.symbols.create("value"));
+        if (j2 == v2.attrs->end())
             throw TypeError("`value' attribute missing in a call to `listToAttrs'");
 
-        Attr & a = (*v.attrs)[state.symbols.create(name)];
-        mkCopy(a.value, j->second.value);
-        a.pos = j->second.pos;
+        (*v.attrs)[state.symbols.create(name)] = j2->second;
     }
 }
 
@@ -791,11 +791,8 @@ static void prim_intersectAttrs(EvalState & state, Value * * args, Value & v)
 
     foreach (Bindings::iterator, i, *args[0]->attrs) {
         Bindings::iterator j = args[1]->attrs->find(i->first);
-        if (j != args[1]->attrs->end()) {
-            Attr & a = (*v.attrs)[j->first];
-            mkCopy(a.value, j->second.value);
-            a.pos = j->second.pos;
-        }
+        if (j != args[1]->attrs->end())
+            (*v.attrs)[j->first] = j->second;
     }
 }
 
@@ -824,7 +821,8 @@ static void prim_functionArgs(EvalState & state, Value * * args, Value & v)
     if (!args[0]->lambda.fun->matchAttrs) return;
 
     foreach (Formals::Formals_::iterator, i, args[0]->lambda.fun->formals->formals)
-        mkBool((*v.attrs)[i->name].value, i->def);
+        // !!! should optimise booleans (allocate only once)
+        mkBool(*state.allocAttr(v, i->name), i->def);
 }
 
 
@@ -1007,8 +1005,8 @@ static void prim_parseDrvName(EvalState & state, Value * * args, Value & v)
     string name = state.forceStringNoCtx(*args[0]);
     DrvName parsed(name);
     state.mkAttrs(v);
-    mkString((*v.attrs)[state.sName].value, parsed.name);
-    mkString((*v.attrs)[state.symbols.create("version")].value, parsed.version);
+    mkString(*state.allocAttr(v, state.sName), parsed.name);
+    mkString(*state.allocAttr(v, state.symbols.create("version")), parsed.version);
 }
 
 
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index 8955a8a33931..1bb200fb858b 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -45,7 +45,7 @@ static void showAttrs(EvalState & state, bool strict, bool location,
         
         XMLOpenElement _(doc, "attr", xmlAttrs);
         printValueAsXML(state, strict, location,
-            a.value, doc, context, drvsSeen);
+            *a.value, doc, context, drvsSeen);
     }
 }
 
@@ -90,16 +90,16 @@ static void printValueAsXML(EvalState & state, bool strict, bool location,
                 Path drvPath;
                 a = v.attrs->find(state.sDrvPath);
                 if (a != v.attrs->end()) {
-                    if (strict) state.forceValue(a->second.value);
-                    if (a->second.value.type == tString)
-                        xmlAttrs["drvPath"] = drvPath = a->second.value.string.s;
+                    if (strict) state.forceValue(*a->second.value);
+                    if (a->second.value->type == tString)
+                        xmlAttrs["drvPath"] = drvPath = a->second.value->string.s;
                 }
         
                 a = v.attrs->find(state.sOutPath);
                 if (a != v.attrs->end()) {
-                    if (strict) state.forceValue(a->second.value);
-                    if (a->second.value.type == tString)
-                        xmlAttrs["outPath"] = a->second.value.string.s;
+                    if (strict) state.forceValue(*a->second.value);
+                    if (a->second.value->type == tString)
+                        xmlAttrs["outPath"] = a->second.value->string.s;
                 }
 
                 XMLOpenElement _(doc, "derivation", xmlAttrs);
diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc
index df32b9f603ab..4895c68e94a8 100644
--- a/src/nix-env/nix-env.cc
+++ b/src/nix-env/nix-env.cc
@@ -161,7 +161,7 @@ static Expr * loadSourceExpr(EvalState & state, const Path & path)
 
 
 static void loadDerivations(EvalState & state, Path nixExprPath,
-    string systemFilter, const Bindings & autoArgs,
+    string systemFilter, Bindings & autoArgs,
     const string & pathPrefix, DrvInfos & elems)
 {
     Value v;
@@ -321,7 +321,7 @@ static bool isPath(const string & s)
 
 
 static void queryInstSources(EvalState & state,
-    const InstallSourceInfo & instSource, const Strings & args,
+    InstallSourceInfo & instSource, const Strings & args,
     DrvInfos & elems, bool newestOnly)
 {
     InstallSourceType type = instSource.type;
diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc
index 0a619f698f98..07c94fe4d49a 100644
--- a/src/nix-env/user-env.cc
+++ b/src/nix-env/user-env.cc
@@ -25,7 +25,8 @@ DrvInfos queryInstalled(EvalState & state, const Path & userEnv)
     if (pathExists(manifestFile)) {
         Value v;
         state.eval(parseExprFromFile(state, manifestFile), v);
-        getDerivations(state, v, "", Bindings(), elems);
+        Bindings bindings;
+        getDerivations(state, v, "", bindings, elems);
     } else if (pathExists(oldManifestFile))
         readLegacyManifest(oldManifestFile, elems);
 
@@ -62,19 +63,19 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
         manifest.list.elems[n++] = &v;
         state.mkAttrs(v);
 
-        mkString((*v.attrs)[state.sType].value, "derivation");
-        mkString((*v.attrs)[state.sName].value, i->name);
-        mkString((*v.attrs)[state.sSystem].value, i->system);
-        mkString((*v.attrs)[state.sOutPath].value, i->queryOutPath(state));
+        mkString(*state.allocAttr(v, state.sType), "derivation");
+        mkString(*state.allocAttr(v, state.sName), i->name);
+        mkString(*state.allocAttr(v, state.sSystem), i->system);
+        mkString(*state.allocAttr(v, state.sOutPath), i->queryOutPath(state));
         if (drvPath != "")
-            mkString((*v.attrs)[state.sDrvPath].value, i->queryDrvPath(state));
+            mkString(*state.allocAttr(v, state.sDrvPath), i->queryDrvPath(state));
         
-        state.mkAttrs((*v.attrs)[state.sMeta].value);
+        state.mkAttrs(*state.allocAttr(v, state.sMeta));
         
         MetaInfo meta = i->queryMetaInfo(state);
 
         foreach (MetaInfo::const_iterator, j, meta) {
-            Value & v2((*(*v.attrs)[state.sMeta].value.attrs)[state.symbols.create(j->first)].value);
+            Value & v2(*state.allocAttr(*(*v.attrs)[state.sMeta].value, state.symbols.create(j->first)));
             switch (j->second.type) {
                 case MetaValue::tpInt: mkInt(v2, j->second.intValue); break;
                 case MetaValue::tpString: mkString(v2, j->second.stringValue); break;
@@ -114,10 +115,10 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
        builder with the manifest as argument. */
     Value args, topLevel;
     state.mkAttrs(args);
-    mkString((*args.attrs)[state.sSystem].value, thisSystem);
-    mkString((*args.attrs)[state.symbols.create("manifest")].value,
+    mkString(*state.allocAttr(args, state.sSystem), thisSystem);
+    mkString(*state.allocAttr(args, state.symbols.create("manifest")),
         manifestFile, singleton<PathSet>(manifestFile));
-    (*args.attrs)[state.symbols.create("derivations")].value = manifest;
+    (*args.attrs)[state.symbols.create("derivations")].value = &manifest;
     mkApp(topLevel, envBuilder, args);
         
     /* Evaluate it. */
diff --git a/src/nix-instantiate/nix-instantiate.cc b/src/nix-instantiate/nix-instantiate.cc
index 2925f9c5efb7..b330f0cf11f8 100644
--- a/src/nix-instantiate/nix-instantiate.cc
+++ b/src/nix-instantiate/nix-instantiate.cc
@@ -38,7 +38,7 @@ static bool indirectRoot = false;
 
 
 void processExpr(EvalState & state, const Strings & attrPaths,
-    bool parseOnly, bool strict, const Bindings & autoArgs,
+    bool parseOnly, bool strict, Bindings & autoArgs,
     bool evalOnly, bool xmlOutput, bool location, Expr * e)
 {
     if (parseOnly)
-- 
cgit 1.4.1


From 3f66cfb96b6f4bbddc8bf3b15e364fd522e028bc Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Sat, 23 Oct 2010 18:18:07 +0000
Subject: * Remove allocValues().

---
 src/libexpr/eval.cc     | 22 +++++-----------------
 src/libexpr/eval.hh     |  1 -
 src/libexpr/primops.cc  | 23 +++++++----------------
 src/nix-env/user-env.cc |  4 ++--
 4 files changed, 14 insertions(+), 36 deletions(-)

(limited to 'src/libexpr/primops.cc')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 3f2371d7957a..faf18cb7f471 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -282,13 +282,6 @@ Value * EvalState::allocValue()
 }
 
 
-Value * EvalState::allocValues(unsigned int count)
-{
-    nrValues += count;
-    return (Value *) GC_MALLOC(count * sizeof(Value));
-}
-
-
 Env & EvalState::allocEnv(unsigned int size)
 {
     nrEnvs++;
@@ -542,11 +535,8 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
 void ExprList::eval(EvalState & state, Env & env, Value & v)
 {
     state.mkList(v, elems.size());
-    Value * vs = state.allocValues(v.list.length);
-    for (unsigned int n = 0; n < v.list.length; ++n) {
-        v.list.elems[n] = &vs[n];
-        mkThunk(vs[n], env, elems[n]);
-    }
+    for (unsigned int n = 0; n < v.list.length; ++n)
+        mkThunk(*(v.list.elems[n] = state.allocValue()), env, elems[n]);
 }
 
 
@@ -630,12 +620,10 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
                 throw;
             }
         } else {
-            Value * v2 = allocValues(2);
-            v2[0] = fun;
-            v2[1] = arg;
             v.type = tPrimOpApp;
-            v.primOpApp.left = &v2[0];
-            v.primOpApp.right = &v2[1];
+            v.primOpApp.left = allocValue();
+            *v.primOpApp.left = fun;
+            v.primOpApp.right = &arg;
             v.primOpApp.argsLeft = argsLeft - 1;
         }
         return;
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index b6ec927f01fa..5f5966930f0e 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -290,7 +290,6 @@ public:
     
     /* Allocation primitives. */
     Value * allocValue();
-    Value * allocValues(unsigned int count);
     Env & allocEnv(unsigned int size);
 
     Value * allocAttr(Value & vAttrs, const Symbol & name);
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index c7709ca9eb36..01cbf7a7c21a 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -167,13 +167,9 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
 
     /* Create the result list. */
     state.mkList(v, res.size());
-    Value * vs = state.allocValues(res.size());
-
     unsigned int n = 0;
-    foreach (list<Value>::iterator, i, res) {
-        v.list.elems[n] = &vs[n];
-        vs[n++] = *i;
-    }
+    foreach (list<Value>::iterator, i, res)
+        *(v.list.elems[n++] = state.allocValue()) = *i;
 }
 
 
@@ -691,17 +687,14 @@ static void prim_attrNames(EvalState & state, Value * * args, Value & v)
     state.forceAttrs(*args[0]);
 
     state.mkList(v, args[0]->attrs->size());
-    Value * vs = state.allocValues(v.list.length);
 
     StringSet names;
     foreach (Bindings::iterator, i, *args[0]->attrs)
         names.insert(i->first);
 
     unsigned int n = 0;
-    foreach (StringSet::iterator, i, names) {
-        v.list.elems[n] = &vs[n];
-        mkString(vs[n++], *i);
-    }
+    foreach (StringSet::iterator, i, names)
+        mkString(*(v.list.elems[n++] = state.allocValue()), *i);
 }
 
 
@@ -870,12 +863,10 @@ static void prim_map(EvalState & state, Value * * args, Value & v)
     state.forceList(*args[1]);
 
     state.mkList(v, args[1]->list.length);
-    Value * vs = state.allocValues(v.list.length);
 
-    for (unsigned int n = 0; n < v.list.length; ++n) {
-        v.list.elems[n] = &vs[n];
-        mkApp(vs[n], *args[0], *args[1]->list.elems[n]);
-    }
+    for (unsigned int n = 0; n < v.list.length; ++n)
+        mkApp(*(v.list.elems[n] = state.allocValue()), 
+            *args[0], *args[1]->list.elems[n]);
 }
 
 
diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc
index 07c94fe4d49a..34e00b7c2e61 100644
--- a/src/nix-env/user-env.cc
+++ b/src/nix-env/user-env.cc
@@ -59,7 +59,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
            the meta attributes. */
         Path drvPath = keepDerivations ? i->queryDrvPath(state) : "";
 
-        Value & v(*state.allocValues(1));
+        Value & v(*state.allocValue());
         manifest.list.elems[n++] = &v;
         state.mkAttrs(v);
 
@@ -83,7 +83,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
                     state.mkList(v2, j->second.stringValues.size());
                     unsigned int m = 0;
                     foreach (Strings::const_iterator, k, j->second.stringValues) {
-                        v2.list.elems[m] = state.allocValues(1);
+                        v2.list.elems[m] = state.allocValue();
                         mkString(*v2.list.elems[m++], *k);
                     }
                     break;
-- 
cgit 1.4.1


From 0b305c534f989dbc3645ff03e070b0e4665fdeb7 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Sun, 24 Oct 2010 00:41:29 +0000
Subject: * Store attribute sets as a vector instead of a map (i.e. a red-black
   tree).  This saves a lot of memory.  The vector should be sorted so   that
 names can be looked up using binary search, but this is not the   case yet. 
 (Surprisingly, looking up attributes using linear search   doesn't have a big
 impact on performance.)

  Memory consumption for

    $ nix-instantiate /etc/nixos/nixos/tests -A bittorrent.test --readonly-mode

  on x86_64-linux with GC enabled is now 185 MiB (compared to 946
  MiB on the trunk).
---
 src/libexpr/attr-path.cc    |  2 +-
 src/libexpr/eval.cc         | 84 ++++++++++++++++++++++++++-------------------
 src/libexpr/eval.hh         | 18 ++++++++--
 src/libexpr/get-drvs.cc     | 34 +++++++++---------
 src/libexpr/primops.cc      | 65 ++++++++++++++++++++---------------
 src/libexpr/symbol-table.hh |  2 ++
 src/libexpr/value-to-xml.cc | 14 ++++----
 7 files changed, 129 insertions(+), 90 deletions(-)

(limited to 'src/libexpr/primops.cc')

diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
index 365b03c0bf60..49c08339ae55 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -49,7 +49,7 @@ void findAlongAttrPath(EvalState & state, const string & attrPath,
             Bindings::iterator a = v.attrs->find(state.symbols.create(attr));
             if (a == v.attrs->end())
                 throw Error(format("attribute `%1%' in selection path `%2%' not found") % attr % curPath);
-            v = *a->second.value;
+            v = *a->value;
         }
 
         else if (apType == apIndex) {
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index d73f99a156cf..85394b768db6 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -13,7 +13,7 @@
 #include <gc/gc.h>
 #include <gc/gc_cpp.h>
 
-#define NEW (UseGC)
+#define NEW new (UseGC)
 
 #else
 
@@ -30,6 +30,23 @@
 
 
 namespace nix {
+
+
+Bindings::iterator Bindings::find(const Symbol & name)
+{
+    iterator i = begin();
+    for ( ; i != end() && i->name != name; ++i) ;
+    return i;
+}
+
+
+Attr & Bindings::operator [] (const Symbol & name)
+{
+    iterator i = find(name);
+    if (i != end()) return *i;
+    push_back(Attr(name, 0));
+    return back();
+}
     
 
 std::ostream & operator << (std::ostream & str, const Value & v)
@@ -62,7 +79,7 @@ std::ostream & operator << (std::ostream & str, const Value & v)
         typedef std::map<string, Value *> Sorted;
         Sorted sorted;
         foreach (Bindings::iterator, i, *v.attrs)
-            sorted[i->first] = i->second.value;
+            sorted[i->name] = i->value;
         foreach (Sorted::iterator, i, sorted)
             str << i->first << " = " << *i->second << "; ";
         str << "}";
@@ -152,7 +169,7 @@ void EvalState::addConstant(const string & name, Value & v)
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v2;
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
-    (*baseEnv.values[0]->attrs)[symbols.create(name2)].value = v2;
+    baseEnv.values[0]->attrs->push_back(Attr(symbols.create(name2), v2));
 }
 
 
@@ -166,7 +183,7 @@ void EvalState::addPrimOp(const string & name,
     v->primOp = NEW PrimOp(primOp, arity, sym);
     staticBaseEnv.vars[sym] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v;
-    (*baseEnv.values[0]->attrs)[symbols.create(name2)].value = v;
+    baseEnv.values[0]->attrs->push_back(Attr(symbols.create(name2), v));
 }
 
 
@@ -277,7 +294,7 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
         while (1) {
             Bindings::iterator j = env->values[0]->attrs->find(var.name);
             if (j != env->values[0]->attrs->end())
-                return j->second.value;
+                return j->value;
             if (env->prevWith == 0)
                 throwEvalError("undefined variable `%1%'", var.name);
             for (unsigned int l = env->prevWith; l; --l, env = env->up) ;
@@ -305,9 +322,9 @@ Env & EvalState::allocEnv(unsigned int size)
 
 Value * EvalState::allocAttr(Value & vAttrs, const Symbol & name)
 {
-    Attr & a = (*vAttrs.attrs)[name];
-    a.value = allocValue();
-    return a.value;
+    Value * v = allocValue();
+    vAttrs.attrs->push_back(Attr(name, v));
+    return v;
 }
 
     
@@ -338,8 +355,7 @@ void EvalState::mkThunk_(Value & v, Expr * expr)
 void EvalState::cloneAttrs(Value & src, Value & dst)
 {
     mkAttrs(dst);
-    foreach (Bindings::iterator, i, *src.attrs)
-        (*dst.attrs)[i->first] = i->second;
+    *dst.attrs = *src.attrs;
 }
 
 
@@ -462,21 +478,18 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
         /* The recursive attributes are evaluated in the new
            environment. */
         foreach (Attrs::iterator, i, attrs) {
-            nix::Attr & a = (*v.attrs)[i->first];
-            a.value = state.allocValue();
-            mkThunk(*a.value, env2, i->second.first);
-            env2.values[displ++] = a.value;
-            a.pos = &i->second.second;
+            Value * vAttr = state.allocValue();
+            mkThunk(*vAttr, env2, i->second.first);
+            env2.values[displ++] = vAttr;
+            v.attrs->push_back(nix::Attr(i->first, vAttr, &i->second.second));
         }
 
         /* The inherited attributes, on the other hand, are
            evaluated in the original environment. */
         foreach (list<Inherited>::iterator, i, inherited) {
-            nix::Attr & a = (*v.attrs)[i->first.name];
-            Value * v2 = state.lookupVar(&env, i->first);
-            a.value = v2;
-            env2.values[displ++] = v2;
-            a.pos = &i->second;
+            Value * vAttr = state.lookupVar(&env, i->first);
+            env2.values[displ++] = vAttr;
+            v.attrs->push_back(nix::Attr(i->first.name, vAttr, &i->second));
         }
 
         /* If the rec contains an attribute called `__overrides', then
@@ -489,12 +502,12 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
            Hence we need __overrides.) */
         Bindings::iterator overrides = v.attrs->find(state.sOverrides);
         if (overrides != v.attrs->end()) {
-            state.forceAttrs(*overrides->second.value);
-            foreach (Bindings::iterator, i, *overrides->second.value->attrs) {
-                nix::Attr & a = (*v.attrs)[i->first];
+            state.forceAttrs(*overrides->value);
+            foreach (Bindings::iterator, i, *overrides->value->attrs) {
+                nix::Attr & a = (*v.attrs)[i->name];
                 if (a.value)
-                    env2.values[displs[i->first]] = i->second.value;
-                a = i->second;
+                    env2.values[displs[i->name]] = i->value;
+                a = *i;
             }
         }
     }
@@ -565,13 +578,13 @@ void ExprSelect::eval(EvalState & state, Env & env, Value & v)
     if (i == v2.attrs->end())
         throwEvalError("attribute `%1%' missing", name);
     try {            
-        state.forceValue(*i->second.value);
+        state.forceValue(*i->value);
     } catch (Error & e) {
         addErrorPrefix(e, "while evaluating the attribute `%1%' at %2%:\n",
-            name, *i->second.pos);
+            name, *i->pos);
         throw;
     }
-    v = *i->second.value;
+    v = *i->value;
 }
 
 
@@ -676,7 +689,7 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
                 mkThunk(*env2.values[displ++], env2, i->def);
             } else {
                 attrsUsed++;
-                env2.values[displ++] = j->second.value;
+                env2.values[displ++] = j->value;
             }
         }
 
@@ -712,7 +725,7 @@ void EvalState::autoCallFunction(Bindings & args, Value & fun, Value & res)
     foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
         Bindings::iterator j = args.find(i->name);
         if (j != args.end())
-            (*actualArgs.attrs)[i->name] = j->second;
+            (*actualArgs.attrs)[i->name] = *j;
         else if (!i->def)
             throwTypeError("cannot auto-call a function that has an argument without a default value (`%1%')", i->name);
     }
@@ -801,8 +814,9 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
 
     state.cloneAttrs(v1, v);
 
+    /* !!! fix */
     foreach (Bindings::iterator, i, *v2.attrs)
-        (*v.attrs)[i->first] = i->second;
+        (*v.attrs)[i->name] = *i;
 
     state.nrOpUpdateValuesCopied += v.attrs->size();
 }
@@ -880,7 +894,7 @@ void EvalState::strictForceValue(Value & v)
     
     if (v.type == tAttrs) {
         foreach (Bindings::iterator, i, *v.attrs)
-            strictForceValue(*i->second.value);
+            strictForceValue(*i->value);
     }
     
     else if (v.type == tList) {
@@ -971,7 +985,7 @@ bool EvalState::isDerivation(Value & v)
 {
     if (v.type != tAttrs) return false;
     Bindings::iterator i = v.attrs->find(sType);
-    return i != v.attrs->end() && forceStringNoCtx(*i->second.value) == "derivation";
+    return i != v.attrs->end() && forceStringNoCtx(*i->value) == "derivation";
 }
 
 
@@ -1015,7 +1029,7 @@ string EvalState::coerceToString(Value & v, PathSet & context,
         Bindings::iterator i = v.attrs->find(sOutPath);
         if (i == v.attrs->end())
             throwTypeError("cannot coerce an attribute set (except a derivation) to a string");
-        return coerceToString(*i->second.value, context, coerceMore, copyToStore);
+        return coerceToString(*i->value, context, coerceMore, copyToStore);
     }
 
     if (coerceMore) {
@@ -1103,7 +1117,7 @@ bool EvalState::eqValues(Value & v1, Value & v2)
             if (v1.attrs->size() != v2.attrs->size()) return false;
             Bindings::iterator i = v1.attrs->begin(), j = v2.attrs->begin();
             for ( ; i != v1.attrs->end(); ++i, ++j)
-                if (i->first != j->first || !eqValues(*i->second.value, *j->second.value))
+                if (i->name != j->name || !eqValues(*i->value, *j->value))
                     return false;
             return true;
         }
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index ec4939442515..2f1b3fa4595e 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -20,13 +20,24 @@ struct Env;
 struct Value;
 struct Attr;
 
+
+/* Attribute sets are represented as a vector of attributes, sorted by
+   symbol (i.e. pointer to the attribute name in the symbol table). */
 #if HAVE_BOEHMGC
-typedef std::map<Symbol, Attr, std::less<Symbol>, gc_allocator<std::pair<const Symbol, Attr> > > Bindings;
+typedef std::vector<Attr, gc_allocator<Attr> > BindingsBase;
 #else
-typedef std::map<Symbol, Attr> Bindings;
+typedef std::vector<Attr> BindingsBase;
 #endif
 
 
+class Bindings : public BindingsBase
+{
+public:
+    iterator find(const Symbol & name);
+    Attr & operator [] (const Symbol & name);
+};
+
+
 typedef enum {
     tInt = 1,
     tBool,
@@ -125,8 +136,11 @@ struct Env
 
 struct Attr
 {
+    Symbol name;
     Value * value;
     Pos * pos;
+    Attr(Symbol name, Value * value, Pos * pos = &noPos)
+        : name(name), value(value), pos(pos) { };
     Attr() : pos(&noPos) { };
 };
 
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 63106b87b5af..312c2cd405e6 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -10,7 +10,7 @@ string DrvInfo::queryDrvPath(EvalState & state) const
     if (drvPath == "" && attrs) {
         Bindings::iterator i = attrs->find(state.sDrvPath);
         PathSet context;
-        (string &) drvPath = i != attrs->end() ? state.coerceToPath(*i->second.value, context) : "";
+        (string &) drvPath = i != attrs->end() ? state.coerceToPath(*i->value, context) : "";
     }
     return drvPath;
 }
@@ -21,7 +21,7 @@ string DrvInfo::queryOutPath(EvalState & state) const
     if (outPath == "" && attrs) {
         Bindings::iterator i = attrs->find(state.sOutPath);
         PathSet context;
-        (string &) outPath = i != attrs->end() ? state.coerceToPath(*i->second.value, context) : "";
+        (string &) outPath = i != attrs->end() ? state.coerceToPath(*i->value, context) : "";
     }
     return outPath;
 }
@@ -36,23 +36,23 @@ MetaInfo DrvInfo::queryMetaInfo(EvalState & state) const
     Bindings::iterator a = attrs->find(state.sMeta);
     if (a == attrs->end()) return meta; /* fine, empty meta information */
 
-    state.forceAttrs(*a->second.value);
+    state.forceAttrs(*a->value);
 
-    foreach (Bindings::iterator, i, *a->second.value->attrs) {
+    foreach (Bindings::iterator, i, *a->value->attrs) {
         MetaValue value;
-        state.forceValue(*i->second.value);
-        if (i->second.value->type == tString) {
+        state.forceValue(*i->value);
+        if (i->value->type == tString) {
             value.type = MetaValue::tpString;
-            value.stringValue = i->second.value->string.s;
-        } else if (i->second.value->type == tInt) {
+            value.stringValue = i->value->string.s;
+        } else if (i->value->type == tInt) {
             value.type = MetaValue::tpInt;
-            value.intValue = i->second.value->integer;
-        } else if (i->second.value->type == tList) {
+            value.intValue = i->value->integer;
+        } else if (i->value->type == tList) {
             value.type = MetaValue::tpStrings;
-            for (unsigned int j = 0; j < i->second.value->list.length; ++j)
-                value.stringValues.push_back(state.forceStringNoCtx(*i->second.value->list.elems[j]));
+            for (unsigned int j = 0; j < i->value->list.length; ++j)
+                value.stringValues.push_back(state.forceStringNoCtx(*i->value->list.elems[j]));
         } else continue;
-        ((MetaInfo &) meta)[i->first] = value;
+        ((MetaInfo &) meta)[i->name] = value;
     }
 
     return meta;
@@ -99,13 +99,13 @@ static bool getDerivation(EvalState & state, Value & v,
         Bindings::iterator i = v.attrs->find(state.sName);
         /* !!! We really would like to have a decent back trace here. */
         if (i == v.attrs->end()) throw TypeError("derivation name missing");
-        drv.name = state.forceStringNoCtx(*i->second.value);
+        drv.name = state.forceStringNoCtx(*i->value);
 
         Bindings::iterator i2 = v.attrs->find(state.sSystem);
         if (i2 == v.attrs->end())
             drv.system = "unknown";
         else
-            drv.system = state.forceStringNoCtx(*i2->second.value);
+            drv.system = state.forceStringNoCtx(*i2->value);
 
         drv.attrs = v.attrs;
 
@@ -163,7 +163,7 @@ static void getDerivations(EvalState & state, Value & vIn,
         typedef std::map<string, Symbol> SortedSymbols;
         SortedSymbols attrs;
         foreach (Bindings::iterator, i, *v.attrs)
-            attrs.insert(std::pair<string, Symbol>(i->first, i->first));
+            attrs.insert(std::pair<string, Symbol>(i->name, i->name));
 
         foreach (SortedSymbols::iterator, i, attrs) {
             startNest(nest, lvlDebug, format("evaluating attribute `%1%'") % i->first);
@@ -178,7 +178,7 @@ static void getDerivations(EvalState & state, Value & vIn,
                    attribute. */
                 if (v2.type == tAttrs) {
                     Bindings::iterator j = v2.attrs->find(state.symbols.create("recurseForDerivations"));
-                    if (j != v2.attrs->end() && state.forceBool(*j->second.value))
+                    if (j != v2.attrs->end() && state.forceBool(*j->value))
                         getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
                 }
             }
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 01cbf7a7c21a..20b8395088d7 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -119,18 +119,18 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
         args[0]->attrs->find(state.symbols.create("startSet"));
     if (startSet == args[0]->attrs->end())
         throw EvalError("attribute `startSet' required");
-    state.forceList(*startSet->second.value);
+    state.forceList(*startSet->value);
 
     list<Value *> workSet;
-    for (unsigned int n = 0; n < startSet->second.value->list.length; ++n)
-        workSet.push_back(startSet->second.value->list.elems[n]);
+    for (unsigned int n = 0; n < startSet->value->list.length; ++n)
+        workSet.push_back(startSet->value->list.elems[n]);
 
     /* Get the operator. */
     Bindings::iterator op =
         args[0]->attrs->find(state.symbols.create("operator"));
     if (op == args[0]->attrs->end())
         throw EvalError("attribute `operator' required");
-    state.forceValue(*op->second.value);
+    state.forceValue(*op->value);
 
     /* Construct the closure by applying the operator to element of
        `workSet', adding the result to `workSet', continuing until
@@ -147,15 +147,15 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
             e->attrs->find(state.symbols.create("key"));
         if (key == e->attrs->end())
             throw EvalError("attribute `key' required");
-        state.forceValue(*key->second.value);
+        state.forceValue(*key->value);
 
-        if (doneKeys.find(*key->second.value) != doneKeys.end()) continue;
-        doneKeys.insert(*key->second.value);
+        if (doneKeys.find(*key->value) != doneKeys.end()) continue;
+        doneKeys.insert(*key->value);
         res.push_back(*e);
         
         /* Call the `operator' function with `e' as argument. */
         Value call;
-        mkApp(call, *op->second.value, *e);
+        mkApp(call, *op->value, *e);
         state.forceList(call);
 
         /* Add the values returned by the operator to the work set. */
@@ -322,9 +322,9 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     if (attr == args[0]->attrs->end())
         throw EvalError("required attribute `name' missing");
     string drvName;
-    Pos & posDrvName(*attr->second.pos);
+    Pos & posDrvName(*attr->pos);
     try {        
-        drvName = state.forceStringNoCtx(*attr->second.value);
+        drvName = state.forceStringNoCtx(*attr->value);
     } catch (Error & e) {
         e.addPrefix(format("while evaluating the derivation attribute `name' at %1%:\n") % posDrvName);
         throw;
@@ -339,7 +339,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     bool outputHashRecursive = false;
 
     foreach (Bindings::iterator, i, *args[0]->attrs) {
-        string key = i->first;
+        string key = i->name;
         startNest(nest, lvlVomit, format("processing attribute `%1%'") % key);
 
         try {
@@ -347,9 +347,9 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
             /* The `args' attribute is special: it supplies the
                command-line arguments to the builder. */
             if (key == "args") {
-                state.forceList(*i->second.value);
-                for (unsigned int n = 0; n < i->second.value->list.length; ++n) {
-                    string s = state.coerceToString(*i->second.value->list.elems[n], context, true);
+                state.forceList(*i->value);
+                for (unsigned int n = 0; n < i->value->list.length; ++n) {
+                    string s = state.coerceToString(*i->value->list.elems[n], context, true);
                     drv.args.push_back(s);
                 }
             }
@@ -357,11 +357,11 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
             /* All other attributes are passed to the builder through
                the environment. */
             else {
-                string s = state.coerceToString(*i->second.value, context, true);
+                string s = state.coerceToString(*i->value, context, true);
                 drv.env[key] = s;
                 if (key == "builder") drv.builder = s;
-                else if (i->first == state.sSystem) drv.platform = s;
-                else if (i->first == state.sName) drvName = s;
+                else if (i->name == state.sSystem) drv.platform = s;
+                else if (i->name == state.sName) drvName = s;
                 else if (key == "outputHash") outputHash = s;
                 else if (key == "outputHashAlgo") outputHashAlgo = s;
                 else if (key == "outputHashMode") {
@@ -373,7 +373,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
 
         } catch (Error & e) {
             e.addPrefix(format("while evaluating the derivation attribute `%1%' at %2%:\n")
-                % key % *i->second.pos);
+                % key % *i->pos);
             e.addPrefix(format("while instantiating the derivation named `%1%' at %2%:\n")
                 % drvName % posDrvName);
             throw;
@@ -690,7 +690,7 @@ static void prim_attrNames(EvalState & state, Value * * args, Value & v)
 
     StringSet names;
     foreach (Bindings::iterator, i, *args[0]->attrs)
-        names.insert(i->first);
+        names.insert(i->name);
 
     unsigned int n = 0;
     foreach (StringSet::iterator, i, names)
@@ -708,8 +708,8 @@ static void prim_getAttr(EvalState & state, Value * * args, Value & v)
     if (i == args[1]->attrs->end())
         throw EvalError(format("attribute `%1%' missing") % attr);
     // !!! add to stack trace?
-    state.forceValue(*i->second.value);
-    v = *i->second.value;
+    state.forceValue(*i->value);
+    v = *i->value;
 }
 
 
@@ -735,11 +735,18 @@ static void prim_removeAttrs(EvalState & state, Value * * args, Value & v)
     state.forceAttrs(*args[0]);
     state.forceList(*args[1]);
 
-    state.cloneAttrs(*args[0], v);
-
+    /* Get the attribute names to be removed. */
+    std::set<Symbol> names;
     for (unsigned int i = 0; i < args[1]->list.length; ++i) {
         state.forceStringNoCtx(*args[1]->list.elems[i]);
-        v.attrs->erase(state.symbols.create(args[1]->list.elems[i]->string.s));
+        names.insert(state.symbols.create(args[1]->list.elems[i]->string.s));
+    }
+
+    /* Copy all attributes not in that set. */
+    state.mkAttrs(v);
+    foreach (Bindings::iterator, i, *args[0]->attrs) {
+        if (names.find(i->name) == names.end())
+            v.attrs->push_back(*i);
     }
 }
 
@@ -761,13 +768,15 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
         Bindings::iterator j = v2.attrs->find(state.sName);
         if (j == v2.attrs->end())
             throw TypeError("`name' attribute missing in a call to `listToAttrs'");
-        string name = state.forceStringNoCtx(*j->second.value);
+        string name = state.forceStringNoCtx(*j->value);
         
         Bindings::iterator j2 = v2.attrs->find(state.symbols.create("value"));
         if (j2 == v2.attrs->end())
             throw TypeError("`value' attribute missing in a call to `listToAttrs'");
 
-        (*v.attrs)[state.symbols.create(name)] = j2->second;
+        Attr & a = (*v.attrs)[state.symbols.create(name)];
+        a.value = j2->value;
+        a.pos = j2->pos;
     }
 }
 
@@ -783,9 +792,9 @@ static void prim_intersectAttrs(EvalState & state, Value * * args, Value & v)
     state.mkAttrs(v);
 
     foreach (Bindings::iterator, i, *args[0]->attrs) {
-        Bindings::iterator j = args[1]->attrs->find(i->first);
+        Bindings::iterator j = args[1]->attrs->find(i->name);
         if (j != args[1]->attrs->end())
-            (*v.attrs)[j->first] = j->second;
+            v.attrs->push_back(*j);
     }
 }
 
diff --git a/src/libexpr/symbol-table.hh b/src/libexpr/symbol-table.hh
index 20ebe5fedbf6..976117a20a46 100644
--- a/src/libexpr/symbol-table.hh
+++ b/src/libexpr/symbol-table.hh
@@ -28,6 +28,8 @@ private:
     friend class SymbolTable;
 
 public:
+    Symbol() : s(0) { };
+    
     bool operator == (const Symbol & s2) const
     {
         return s == s2.s;
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index 1bb200fb858b..4f9b62d5f15e 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -34,7 +34,7 @@ static void showAttrs(EvalState & state, bool strict, bool location,
     StringSet names;
     
     foreach (Bindings::iterator, i, attrs)
-        names.insert(i->first);
+        names.insert(i->name);
     
     foreach (StringSet::iterator, i, names) {
         Attr & a(attrs[state.symbols.create(*i)]);
@@ -90,16 +90,16 @@ static void printValueAsXML(EvalState & state, bool strict, bool location,
                 Path drvPath;
                 a = v.attrs->find(state.sDrvPath);
                 if (a != v.attrs->end()) {
-                    if (strict) state.forceValue(*a->second.value);
-                    if (a->second.value->type == tString)
-                        xmlAttrs["drvPath"] = drvPath = a->second.value->string.s;
+                    if (strict) state.forceValue(*a->value);
+                    if (a->value->type == tString)
+                        xmlAttrs["drvPath"] = drvPath = a->value->string.s;
                 }
         
                 a = v.attrs->find(state.sOutPath);
                 if (a != v.attrs->end()) {
-                    if (strict) state.forceValue(*a->second.value);
-                    if (a->second.value->type == tString)
-                        xmlAttrs["outPath"] = a->second.value->string.s;
+                    if (strict) state.forceValue(*a->value);
+                    if (a->value->type == tString)
+                        xmlAttrs["outPath"] = a->value->string.s;
                 }
 
                 XMLOpenElement _(doc, "derivation", xmlAttrs);
-- 
cgit 1.4.1


From 2dc6d5094183edee523a48d449eab1a376e839a2 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Sun, 24 Oct 2010 14:20:02 +0000
Subject: * Don't create thunks for variable lookups (if possible).  This  
 significantly reduces the number of values allocated (e.g. from 8.7m   to
 4.9m for the Bittorrent test).

---
 src/libexpr/eval.cc    | 71 ++++++++++++++++++++++++++++++++++++++++----------
 src/libexpr/eval.hh    | 10 ++-----
 src/libexpr/primops.cc |  2 +-
 3 files changed, 60 insertions(+), 23 deletions(-)

(limited to 'src/libexpr/primops.cc')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 85394b768db6..124cf6498f06 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -316,6 +316,11 @@ Env & EvalState::allocEnv(unsigned int size)
     nrEnvs++;
     nrValuesInEnvs += size;
     Env * env = (Env *) GC_MALLOC(sizeof(Env) + size * sizeof(Value *));
+
+    /* Clear the values because maybeThunk() expects this. */
+    for (unsigned i = 0; i < size; ++i)
+        env->values[i] = 0;
+    
     return *env;
 }
 
@@ -346,12 +351,48 @@ void EvalState::mkAttrs(Value & v)
 }
 
 
+unsigned long nrThunks = 0;
+
+static inline void mkThunk(Value & v, Env & env, Expr * expr)
+{
+    v.type = tThunk;
+    v.thunk.env = &env;
+    v.thunk.expr = expr;
+    nrThunks++;
+}
+
+
 void EvalState::mkThunk_(Value & v, Expr * expr)
 {
     mkThunk(v, baseEnv, expr);
 }
 
 
+unsigned long nrAvoided = 0;
+
+/* Create a thunk for the delayed computation of the given expression
+   in the given environment.  But if the expression is a variable,
+   then look it up right away.  This significantly reduces the number
+   of thunks allocated. */
+Value * EvalState::maybeThunk(Env & env, Expr * expr)
+{
+    ExprVar * var;
+    /* Ignore variables from `withs' because they can throw an
+       exception. */
+    if ((var = dynamic_cast<ExprVar *>(expr))) {
+        Value * v = lookupVar(&env, var->info);
+        /* The value might not be initialised in the environment yet.
+           In that case, ignore it. */
+        if (v) { nrAvoided++; return v; }
+    }
+
+    Value * v = allocValue();
+    mkThunk(*v, env, expr);
+
+    return v;
+}
+
+
 void EvalState::cloneAttrs(Value & src, Value & dst)
 {
     mkAttrs(dst);
@@ -478,8 +519,7 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
         /* The recursive attributes are evaluated in the new
            environment. */
         foreach (Attrs::iterator, i, attrs) {
-            Value * vAttr = state.allocValue();
-            mkThunk(*vAttr, env2, i->second.first);
+            Value * vAttr = state.maybeThunk(env2, i->second.first);
             env2.values[displ++] = vAttr;
             v.attrs->push_back(nix::Attr(i->first, vAttr, &i->second.second));
         }
@@ -515,8 +555,7 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
     else {
         foreach (Attrs::iterator, i, attrs) {
             nix::Attr & a = (*v.attrs)[i->first];
-            a.value = state.allocValue();
-            mkThunk(*a.value, env, i->second.first);
+            a.value = state.maybeThunk(env, i->second.first);
             a.pos = &i->second.second;
         }
 
@@ -540,10 +579,8 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
 
     /* The recursive attributes are evaluated in the new
        environment. */
-    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs) {
-        env2.values[displ] = state.allocValue();
-        mkThunk(*env2.values[displ++], env2, i->second.first);
-    }
+    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
+        env2.values[displ++] = state.maybeThunk(env2, i->second.first);
 
     /* The inherited attributes, on the other hand, are evaluated in
        the original environment. */
@@ -558,7 +595,7 @@ void ExprList::eval(EvalState & state, Env & env, Value & v)
 {
     state.mkList(v, elems.size());
     for (unsigned int n = 0; n < v.list.length; ++n)
-        mkThunk(*(v.list.elems[n] = state.allocValue()), env, elems[n]);
+        v.list.elems[n] = state.maybeThunk(env, elems[n]);
 }
 
 
@@ -570,10 +607,15 @@ void ExprVar::eval(EvalState & state, Env & env, Value & v)
 }
 
 
+unsigned long nrLookups = 0;
+unsigned long nrLookupSize = 0;
+
 void ExprSelect::eval(EvalState & state, Env & env, Value & v)
 {
+    nrLookups++;
     Value v2;
     state.evalAttrs(env, e, v2);
+    nrLookupSize += v2.attrs->size();
     Bindings::iterator i = v2.attrs->find(name);
     if (i == v2.attrs->end())
         throwEvalError("attribute `%1%' missing", name);
@@ -608,9 +650,7 @@ void ExprApp::eval(EvalState & state, Env & env, Value & v)
 {
     Value vFun;
     state.eval(env, e1, vFun);
-    Value * vArg = state.allocValue();
-    mkThunk(*vArg, env, e2);
-    state.callFunction(vFun, *vArg, v);
+    state.callFunction(vFun, *state.maybeThunk(env, e2), v);
 }
 
 
@@ -685,8 +725,7 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
             if (j == arg.attrs->end()) {
                 if (!i->def) throwTypeError("function at %1% called without required argument `%2%'",
                     fun.lambda.fun->pos, i->name);
-                env2.values[displ] = allocValue();
-                mkThunk(*env2.values[displ++], env2, i->def);
+                env2.values[displ++] = maybeThunk(env2, i->def);
             } else {
                 attrsUsed++;
                 env2.values[displ++] = j->value;
@@ -1156,6 +1195,10 @@ void EvalState::printStats()
     printMsg(v, format("  right-biased unions: %1%") % nrOpUpdates);
     printMsg(v, format("  values copied in right-biased unions: %1%") % nrOpUpdateValuesCopied);
     printMsg(v, format("  symbols in symbol table: %1%") % symbols.size());
+    printMsg(v, format("  number of thunks: %1%") % nrThunks);
+    printMsg(v, format("  number of thunks avoided: %1%") % nrAvoided);
+    printMsg(v, format("  number of attr lookups: %1%") % nrLookups);
+    printMsg(v, format("  attr lookup size: %1%") % nrLookupSize);
 }
 
 
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 2f1b3fa4595e..e1aa69dd38d2 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -169,14 +169,6 @@ static inline void mkBool(Value & v, bool b)
 }
 
 
-static inline void mkThunk(Value & v, Env & env, Expr * expr)
-{
-    v.type = tThunk;
-    v.thunk.env = &env;
-    v.thunk.expr = expr;
-}
-
-
 static inline void mkApp(Value & v, Value & left, Value & right)
 {
     v.type = tApp;
@@ -325,6 +317,8 @@ public:
     void mkList(Value & v, unsigned int length);
     void mkAttrs(Value & v);
     void mkThunk_(Value & v, Expr * expr);
+
+    Value * maybeThunk(Env & env, Expr * expr);
     
     void cloneAttrs(Value & src, Value & dst);
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 20b8395088d7..3e32dd3ffc0e 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -1070,7 +1070,7 @@ void EvalState::createBaseEnv()
     /* Add a wrapper around the derivation primop that computes the
        `drvPath' and `outPath' attributes lazily. */
     string s = "attrs: let res = derivationStrict attrs; in attrs // { drvPath = res.drvPath; outPath = res.outPath; type = \"derivation\"; }";
-    mkThunk(v, baseEnv, parseExprFromString(*this, s, "/"));
+    mkThunk_(v, parseExprFromString(*this, s, "/"));
     addConstant("derivation", v);
 
     // Paths
-- 
cgit 1.4.1


From e0b7fb8f2710ec3012afe6b9d2096f770429a389 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Sun, 24 Oct 2010 19:52:33 +0000
Subject: * Keep attribute sets in sorted order to speed up attribute lookups.
 * Simplify the representation of attributes in the AST. * Change the
 behaviour of listToAttrs() in case of duplicate names.

---
 src/libexpr/common-opts.cc           |   7 +-
 src/libexpr/eval.cc                  | 147 +++++++++++++++++++----------------
 src/libexpr/eval.hh                  |   6 +-
 src/libexpr/get-drvs.cc              |   2 +-
 src/libexpr/nixexpr.cc               |  63 +++++++--------
 src/libexpr/nixexpr.hh               |  20 +++--
 src/libexpr/parser.y                 |  32 ++++----
 src/libexpr/primops.cc               |  32 ++++++--
 src/libexpr/value-to-xml.cc          |   2 +-
 src/nix-env/nix-env.cc               |   4 +-
 src/nix-env/user-env.cc              |  15 ++--
 tests/lang/eval-okay-listtoattrs.nix |   2 +-
 12 files changed, 185 insertions(+), 147 deletions(-)

(limited to 'src/libexpr/primops.cc')

diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc
index 6b393c07df50..c364aa9cb599 100644
--- a/src/libexpr/common-opts.cc
+++ b/src/libexpr/common-opts.cc
@@ -20,14 +20,17 @@ bool parseOptionArg(const string & arg, Strings::iterator & i,
     if (i == argsEnd) throw error;
     string value = *i++;
 
+    /* !!! check for duplicates! */
     Value * v = state.allocValue();
-    autoArgs[state.symbols.create(name)].value = v;
+    autoArgs.push_back(Attr(state.symbols.create(name), v));
 
     if (arg == "--arg")
         state.mkThunk_(*v, parseExprFromString(state, value, absPath(".")));
     else
         mkString(*v, value);
-    
+
+    autoArgs.sort(); // !!! inefficient
+
     return true;
 }
 
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 124cf6498f06..4aa8fc1e44b5 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -34,18 +34,16 @@ namespace nix {
 
 Bindings::iterator Bindings::find(const Symbol & name)
 {
-    iterator i = begin();
-    for ( ; i != end() && i->name != name; ++i) ;
-    return i;
+    Attr key(name, 0);
+    iterator i = lower_bound(begin(), end(), key);
+    if (i != end() && i->name == name) return i;
+    return end();
 }
 
 
-Attr & Bindings::operator [] (const Symbol & name)
+void Bindings::sort()
 {
-    iterator i = find(name);
-    if (i != end()) return *i;
-    push_back(Attr(name, 0));
-    return back();
+    std::sort(begin(), end());
 }
     
 
@@ -178,12 +176,12 @@ void EvalState::addPrimOp(const string & name,
 {
     Value * v = allocValue();
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
-    Symbol sym = symbols.create(name);
+    Symbol sym = symbols.create(name2);
     v->type = tPrimOp;
     v->primOp = NEW PrimOp(primOp, arity, sym);
-    staticBaseEnv.vars[sym] = baseEnvDispl;
+    staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v;
-    baseEnv.values[0]->attrs->push_back(Attr(symbols.create(name2), v));
+    baseEnv.values[0]->attrs->push_back(Attr(sym, v));
 }
 
 
@@ -506,32 +504,38 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v)
 
 void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
 {
-    state.mkAttrs(v);
+    state.mkAttrs(v); // !!! reserve size
 
     if (recursive) {
         /* Create a new environment that contains the attributes in
            this `rec'. */
-        Env & env2(state.allocEnv(attrs.size() + inherited.size()));
+        Env & env2(state.allocEnv(attrs.size()));
         env2.up = &env;
 
+        AttrDefs::iterator overrides = attrs.find(state.sOverrides);
+        bool hasOverrides = overrides != attrs.end();
+
+        /* The recursive attributes are evaluated in the new
+           environment, while the inherited attributes are evaluated
+           in the original environment. */
         unsigned int displ = 0;
+        foreach (AttrDefs::iterator, i, attrs)
+            if (i->second.inherited) {
+                /* !!! handle overrides? */
+                Value * vAttr = state.lookupVar(&env, i->second.var);
+                env2.values[displ++] = vAttr;
+                v.attrs->push_back(Attr(i->first, vAttr, &i->second.pos));
+            } else {
+                Value * vAttr;
+                if (hasOverrides) {
+                    vAttr = state.allocValue();
+                    mkThunk(*vAttr, env2, i->second.e);
+                } else
+                    vAttr = state.maybeThunk(env2, i->second.e);
+                env2.values[displ++] = vAttr;
+                v.attrs->push_back(Attr(i->first, vAttr, &i->second.pos));
+            }
         
-        /* The recursive attributes are evaluated in the new
-           environment. */
-        foreach (Attrs::iterator, i, attrs) {
-            Value * vAttr = state.maybeThunk(env2, i->second.first);
-            env2.values[displ++] = vAttr;
-            v.attrs->push_back(nix::Attr(i->first, vAttr, &i->second.second));
-        }
-
-        /* The inherited attributes, on the other hand, are
-           evaluated in the original environment. */
-        foreach (list<Inherited>::iterator, i, inherited) {
-            Value * vAttr = state.lookupVar(&env, i->first);
-            env2.values[displ++] = vAttr;
-            v.attrs->push_back(nix::Attr(i->first.name, vAttr, &i->second));
-        }
-
         /* If the rec contains an attribute called `__overrides', then
            evaluate it, and add the attributes in that set to the rec.
            This allows overriding of recursive attributes, which is
@@ -540,30 +544,27 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
            still reference the original value, because that value has
            been substituted into the bodies of the other attributes.
            Hence we need __overrides.) */
-        Bindings::iterator overrides = v.attrs->find(state.sOverrides);
-        if (overrides != v.attrs->end()) {
-            state.forceAttrs(*overrides->value);
-            foreach (Bindings::iterator, i, *overrides->value->attrs) {
-                nix::Attr & a = (*v.attrs)[i->name];
-                if (a.value)
-                    env2.values[displs[i->name]] = i->value;
-                a = *i;
+        if (hasOverrides) {
+            Value * vOverrides = (*v.attrs)[overrides->second.displ].value;
+            state.forceAttrs(*vOverrides);
+            foreach (Bindings::iterator, i, *vOverrides->attrs) {
+                AttrDefs::iterator j = attrs.find(i->name);
+                if (j != attrs.end()) {
+                    (*v.attrs)[j->second.displ] = *i;
+                    env2.values[j->second.displ] = i->value;
+                } else
+                    v.attrs->push_back(*i);
             }
+            v.attrs->sort();
         }
     }
 
     else {
-        foreach (Attrs::iterator, i, attrs) {
-            nix::Attr & a = (*v.attrs)[i->first];
-            a.value = state.maybeThunk(env, i->second.first);
-            a.pos = &i->second.second;
-        }
-
-        foreach (list<Inherited>::iterator, i, inherited) {
-            nix::Attr & a = (*v.attrs)[i->first.name];
-            a.value = state.lookupVar(&env, i->first);
-            a.pos = &i->second;
-        }
+        foreach (AttrDefs::iterator, i, attrs)
+            if (i->second.inherited)
+                v.attrs->push_back(Attr(i->first, state.lookupVar(&env, i->second.var), &i->second.pos));
+            else
+                v.attrs->push_back(Attr(i->first, state.maybeThunk(env, i->second.e), &i->second.pos));
     }
 }
 
@@ -572,20 +573,18 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
 {
     /* Create a new environment that contains the attributes in this
        `let'. */
-    Env & env2(state.allocEnv(attrs->attrs.size() + attrs->inherited.size()));
+    Env & env2(state.allocEnv(attrs->attrs.size()));
     env2.up = &env;
 
-    unsigned int displ = 0;
-
-    /* The recursive attributes are evaluated in the new
+    /* The recursive attributes are evaluated in the new environment,
+       while the inherited attributes are evaluated in the original
        environment. */
-    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
-        env2.values[displ++] = state.maybeThunk(env2, i->second.first);
-
-    /* The inherited attributes, on the other hand, are evaluated in
-       the original environment. */
-    foreach (list<ExprAttrs::Inherited>::iterator, i, attrs->inherited)
-        env2.values[displ++] = state.lookupVar(&env, i->first);
+    unsigned int displ = 0;
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        if (i->second.inherited)
+            env2.values[displ++] = state.lookupVar(&env, i->second.var);
+        else
+            env2.values[displ++] = state.maybeThunk(env2, i->second.e);
 
     state.eval(env2, body, v);
 }
@@ -736,7 +735,7 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
            argument (unless the attribute match specifies a `...').
            TODO: show the names of the expected/unexpected
            arguments. */
-        if (!fun.lambda.fun->formals->ellipsis && attrsUsed != arg.attrs->size())
+        if (!fun.lambda.fun->formals->ellipsis && attrsUsed != arg.attrs->size()) 
             throwTypeError("function at %1% called with unexpected argument", fun.lambda.fun->pos);
     }
 
@@ -764,11 +763,13 @@ void EvalState::autoCallFunction(Bindings & args, Value & fun, Value & res)
     foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
         Bindings::iterator j = args.find(i->name);
         if (j != args.end())
-            (*actualArgs.attrs)[i->name] = *j;
+            actualArgs.attrs->push_back(*j);
         else if (!i->def)
             throwTypeError("cannot auto-call a function that has an argument without a default value (`%1%')", i->name);
     }
 
+    actualArgs.attrs->sort();
+
     callFunction(fun, actualArgs, res);
 }
 
@@ -851,12 +852,28 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
     if (v1.attrs->size() == 0) { v = v2; return; }
     if (v2.attrs->size() == 0) { v = v1; return; }
 
-    state.cloneAttrs(v1, v);
+    state.mkAttrs(v);
+
+    /* Merge the attribute sets, preferring values from the second
+       set.  Make sure to keep the resulting vector in sorted
+       order. */
+    Bindings::iterator i = v1.attrs->begin();
+    Bindings::iterator j = v2.attrs->begin();
 
-    /* !!! fix */
-    foreach (Bindings::iterator, i, *v2.attrs)
-        (*v.attrs)[i->name] = *i;
+    while (i != v1.attrs->end() && j != v2.attrs->end()) {
+        if (i->name == j->name) {
+            v.attrs->push_back(*j);
+            ++i; ++j;
+        }
+        else if (i->name < j->name)
+            v.attrs->push_back(*i++);
+        else
+            v.attrs->push_back(*j++);
+    }
 
+    while (i != v1.attrs->end()) v.attrs->push_back(*i++);
+    while (j != v2.attrs->end()) v.attrs->push_back(*j++);
+    
     state.nrOpUpdateValuesCopied += v.attrs->size();
 }
 
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index e1aa69dd38d2..7f801d1125fb 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -34,7 +34,7 @@ class Bindings : public BindingsBase
 {
 public:
     iterator find(const Symbol & name);
-    Attr & operator [] (const Symbol & name);
+    void sort();
 };
 
 
@@ -142,6 +142,10 @@ struct Attr
     Attr(Symbol name, Value * value, Pos * pos = &noPos)
         : name(name), value(value), pos(pos) { };
     Attr() : pos(&noPos) { };
+    bool operator < (const Attr & a) const
+    {
+        return name < a.name;
+    }
 };
 
 
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 312c2cd405e6..a28a705d22d1 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -168,7 +168,7 @@ static void getDerivations(EvalState & state, Value & vIn,
         foreach (SortedSymbols::iterator, i, attrs) {
             startNest(nest, lvlDebug, format("evaluating attribute `%1%'") % i->first);
             string pathPrefix2 = addToPath(pathPrefix, i->first);
-            Value & v2(*(*v.attrs)[i->second].value);
+            Value & v2(*v.attrs->find(i->second)->value);
             if (combineChannels)
                 getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
             else if (getDerivation(state, v2, pathPrefix2, drvs, done)) {
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 9f2ea78831f2..147f50853e9d 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -55,10 +55,11 @@ 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 << "; ";
+    foreach (AttrDefs::iterator, i, attrs)
+        if (i->second.inherited)
+            str << "inherit " << i->first << " " << "; ";
+        else
+            str << i->first << " = " << *i->second.e << "; ";
     str << "}";
 }
 
@@ -91,10 +92,11 @@ void ExprLambda::show(std::ostream & str)
 void ExprLet::show(std::ostream & str)
 {
     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 << "; ";
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        if (i->second.inherited)
+            str << "inherit " << i->first << "; ";
+        else
+            str << i->first << " = " << *i->second.e << "; ";
     str << "in " << *body;
 }
 
@@ -211,26 +213,18 @@ void ExprAttrs::bindVars(const StaticEnv & env)
         StaticEnv newEnv(false, &env);
     
         unsigned int displ = 0;
-
-        foreach (ExprAttrs::Attrs::iterator, i, attrs)
-            displs[i->first] = newEnv.vars[i->first] = displ++;
-
-        foreach (list<Inherited>::iterator, i, inherited) {
-            displs[i->first.name] = newEnv.vars[i->first.name] = displ++;
-            i->first.bind(env);
-        }
-
-        foreach (ExprAttrs::Attrs::iterator, i, attrs)
-            i->second.first->bindVars(newEnv);
+        foreach (AttrDefs::iterator, i, attrs)
+            newEnv.vars[i->first] = i->second.displ = displ++;
+        
+        foreach (AttrDefs::iterator, i, attrs)
+            if (i->second.inherited) i->second.var.bind(env);
+            else i->second.e->bindVars(newEnv);
     }
 
-    else {
-        foreach (ExprAttrs::Attrs::iterator, i, attrs)
-            i->second.first->bindVars(env);
-
-        foreach (list<Inherited>::iterator, i, inherited)
-            i->first.bind(env);
-    }
+    else
+        foreach (AttrDefs::iterator, i, attrs)
+            if (i->second.inherited) i->second.var.bind(env);
+            else i->second.e->bindVars(env);
 }
 
 void ExprList::bindVars(const StaticEnv & env)
@@ -263,17 +257,12 @@ 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);
-    }
-
-    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
-        i->second.first->bindVars(newEnv);
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        newEnv.vars[i->first] = i->second.displ = displ++;
+    
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        if (i->second.inherited) i->second.var.bind(env);
+        else i->second.e->bindVars(newEnv);
     
     body->bindVars(newEnv);
 }
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 1aa3df3689a6..8f976f1de8f9 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -101,6 +101,7 @@ struct VarRef
     unsigned int level;
     unsigned int displ;
 
+    VarRef() { };
     VarRef(const Symbol & name) : name(name) { };
     void bind(const StaticEnv & env);
 };
@@ -131,13 +132,18 @@ struct ExprOpHasAttr : Expr
 struct ExprAttrs : Expr
 {
     bool recursive;
-    typedef std::pair<Expr *, Pos> Attr;
-    typedef std::pair<VarRef, Pos> Inherited;
-    typedef std::map<Symbol, Attr> Attrs;
-    Attrs attrs;
-    list<Inherited> inherited;
-    std::map<Symbol, Pos> attrNames; // used during parsing
-    std::map<Symbol, unsigned int> displs;
+    struct AttrDef {
+        bool inherited;
+        Expr * e; // if not inherited
+        VarRef var; // if inherited
+        Pos pos;
+        unsigned int displ; // displacement
+        AttrDef(Expr * e, const Pos & pos) : inherited(false), e(e), pos(pos) { };
+        AttrDef(const Symbol & name, const Pos & pos) : inherited(true), var(name), pos(pos) { };
+        AttrDef() { };
+    };
+    typedef std::map<Symbol, AttrDef> AttrDefs;
+    AttrDefs attrs;
     ExprAttrs() : recursive(false) { };
     COMMON_METHODS
 };
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index 3a72a4ade257..c6d29b6ca8bd 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -93,20 +93,20 @@ static void addAttr(ExprAttrs * attrs, const vector<Symbol> & attrPath,
     unsigned int n = 0;
     foreach (vector<Symbol>::const_iterator, i, attrPath) {
         n++;
-        ExprAttrs::Attrs::iterator j = attrs->attrs.find(*i);
+        ExprAttrs::AttrDefs::iterator j = attrs->attrs.find(*i);
         if (j != attrs->attrs.end()) {
-            ExprAttrs * attrs2 = dynamic_cast<ExprAttrs *>(j->second.first);
-            if (!attrs2 || n == attrPath.size()) dupAttr(attrPath, pos, j->second.second);
-            attrs = attrs2;
+            if (!j->second.inherited) {
+                ExprAttrs * attrs2 = dynamic_cast<ExprAttrs *>(j->second.e);
+                if (!attrs2 || n == attrPath.size()) dupAttr(attrPath, pos, j->second.pos);
+                attrs = attrs2;
+            } else
+                dupAttr(attrPath, pos, j->second.pos);
         } else {
-            if (attrs->attrNames.find(*i) != attrs->attrNames.end())
-                dupAttr(attrPath, pos, attrs->attrNames[*i]);
-            attrs->attrNames[*i] = pos;
             if (n == attrPath.size())
-                attrs->attrs[*i] = ExprAttrs::Attr(e, pos);
+                attrs->attrs[*i] = ExprAttrs::AttrDef(e, pos);
             else {
                 ExprAttrs * nested = new ExprAttrs;
-                attrs->attrs[*i] = ExprAttrs::Attr(nested, pos);
+                attrs->attrs[*i] = ExprAttrs::AttrDef(nested, pos);
                 attrs = nested;
             }
         }
@@ -383,21 +383,19 @@ binds
   | binds INHERIT ids ';'
     { $$ = $1;
       foreach (vector<Symbol>::iterator, i, *$3) {
-          if ($$->attrNames.find(*i) != $$->attrNames.end())
-              dupAttr(*i, makeCurPos(@3, data), $$->attrNames[*i]);
+          if ($$->attrs.find(*i) != $$->attrs.end())
+              dupAttr(*i, makeCurPos(@3, data), $$->attrs[*i].pos);
           Pos pos = makeCurPos(@3, data);
-          $$->inherited.push_back(ExprAttrs::Inherited(*i, pos));
-          $$->attrNames[*i] = pos;
+          $$->attrs[*i] = ExprAttrs::AttrDef(*i, pos);
       }
     }
   | binds INHERIT '(' expr ')' ids ';'
     { $$ = $1;
       /* !!! Should ensure sharing of the expression in $4. */
       foreach (vector<Symbol>::iterator, i, *$6) {
-          if ($$->attrNames.find(*i) != $$->attrNames.end())
-              dupAttr(*i, makeCurPos(@6, data), $$->attrNames[*i]);
-          $$->attrs[*i] = ExprAttrs::Attr(new ExprSelect($4, *i), makeCurPos(@6, data));
-          $$->attrNames[*i] = makeCurPos(@6, data);
+          if ($$->attrs.find(*i) != $$->attrs.end())
+              dupAttr(*i, makeCurPos(@6, data), $$->attrs[*i].pos);
+          $$->attrs[*i] = ExprAttrs::AttrDef(new ExprSelect($4, *i), makeCurPos(@6, data));
       }}
 
   | { $$ = new ExprAttrs; }
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 3e32dd3ffc0e..7c713f384f33 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -209,14 +209,13 @@ static void prim_tryEval(EvalState & state, Value * * args, Value & v)
     state.mkAttrs(v);
     try {
         state.forceValue(*args[0]);
-        printMsg(lvlError, format("%1%") % *args[0]);
-        (*v.attrs)[state.symbols.create("value")].value = args[0];
+        v.attrs->push_back(Attr(state.symbols.create("value"), args[0]));
         mkBool(*state.allocAttr(v, state.symbols.create("success")), true);
-        printMsg(lvlError, format("%1%") % v);
     } catch (AssertionError & e) {
         mkBool(*state.allocAttr(v, state.symbols.create("value")), false);
         mkBool(*state.allocAttr(v, state.symbols.create("success")), false);
     }
+    v.attrs->sort();
 }
 
 
@@ -488,6 +487,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     state.mkAttrs(v);
     mkString(*state.allocAttr(v, state.sOutPath), outPath, singleton<PathSet>(drvPath));
     mkString(*state.allocAttr(v, state.sDrvPath), drvPath, singleton<PathSet>("=" + drvPath));
+    v.attrs->sort();
 }
 
 
@@ -742,7 +742,9 @@ static void prim_removeAttrs(EvalState & state, Value * * args, Value & v)
         names.insert(state.symbols.create(args[1]->list.elems[i]->string.s));
     }
 
-    /* Copy all attributes not in that set. */
+    /* Copy all attributes not in that set.  Note that we don't need
+       to sort v.attrs because it's a subset of an already sorted
+       vector. */
     state.mkAttrs(v);
     foreach (Bindings::iterator, i, *args[0]->attrs) {
         if (names.find(i->name) == names.end())
@@ -761,6 +763,8 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
 
     state.mkAttrs(v);
 
+    std::set<Symbol> seen;
+
     for (unsigned int i = 0; i < args[0]->list.length; ++i) {
         Value & v2(*args[0]->list.elems[i]);
         state.forceAttrs(v2);
@@ -774,10 +778,15 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
         if (j2 == v2.attrs->end())
             throw TypeError("`value' attribute missing in a call to `listToAttrs'");
 
-        Attr & a = (*v.attrs)[state.symbols.create(name)];
-        a.value = j2->value;
-        a.pos = j2->pos;
+        Symbol sym = state.symbols.create(name);
+        if (seen.find(sym) == seen.end()) {
+            v.attrs->push_back(Attr(sym, j2->value, j2->pos));
+            seen.insert(sym);
+        }
+        /* !!! Throw an error if `name' already exists? */
     }
+
+    v.attrs->sort();
 }
 
 
@@ -825,6 +834,8 @@ static void prim_functionArgs(EvalState & state, Value * * args, Value & v)
     foreach (Formals::Formals_::iterator, i, args[0]->lambda.fun->formals->formals)
         // !!! should optimise booleans (allocate only once)
         mkBool(*state.allocAttr(v, i->name), i->def);
+
+    v.attrs->sort();
 }
 
 
@@ -1007,6 +1018,7 @@ static void prim_parseDrvName(EvalState & state, Value * * args, Value & v)
     state.mkAttrs(v);
     mkString(*state.allocAttr(v, state.sName), parsed.name);
     mkString(*state.allocAttr(v, state.symbols.create("version")), parsed.version);
+    v.attrs->sort();
 }
 
 
@@ -1119,7 +1131,11 @@ void EvalState::createBaseEnv()
 
     // Versions
     addPrimOp("__parseDrvName", 1, prim_parseDrvName);
-    addPrimOp("__compareVersions", 2, prim_compareVersions);    
+    addPrimOp("__compareVersions", 2, prim_compareVersions);
+
+    /* Now that we've added all primops, sort the `builtins' attribute
+       set, because attribute lookups expect it to be sorted. */
+    baseEnv.values[0]->attrs->sort();
 }
 
 
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index 4f9b62d5f15e..bc63f776269c 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -37,7 +37,7 @@ static void showAttrs(EvalState & state, bool strict, bool location,
         names.insert(i->name);
     
     foreach (StringSet::iterator, i, names) {
-        Attr & a(attrs[state.symbols.create(*i)]);
+        Attr & a(*attrs.find(state.symbols.create(*i)));
         
         XMLAttrs xmlAttrs;
         xmlAttrs["name"] = *i;
diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc
index 4895c68e94a8..58bc9af12598 100644
--- a/src/nix-env/nix-env.cc
+++ b/src/nix-env/nix-env.cc
@@ -132,7 +132,7 @@ static void getAllExprs(EvalState & state,
             if (hasSuffix(attrName, ".nix"))
                 attrName = string(attrName, 0, attrName.size() - 4);
             attrs.attrs[state.symbols.create(attrName)] =
-                ExprAttrs::Attr(parseExprFromFile(state, absPath(path2)), noPos);
+                ExprAttrs::AttrDef(parseExprFromFile(state, absPath(path2)), noPos);
         }
         else
             /* `path2' is a directory (with no default.nix in it);
@@ -154,7 +154,7 @@ static Expr * loadSourceExpr(EvalState & state, const Path & path)
        some system-wide directory). */
     ExprAttrs * attrs = new ExprAttrs;
     attrs->attrs[state.symbols.create("_combineChannels")] =
-        ExprAttrs::Attr(new ExprList(), noPos);
+        ExprAttrs::AttrDef(new ExprList(), noPos);
     getAllExprs(state, path, *attrs);
     return attrs;
 }
diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc
index 34e00b7c2e61..acd866197c7c 100644
--- a/src/nix-env/user-env.cc
+++ b/src/nix-env/user-env.cc
@@ -69,13 +69,14 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
         mkString(*state.allocAttr(v, state.sOutPath), i->queryOutPath(state));
         if (drvPath != "")
             mkString(*state.allocAttr(v, state.sDrvPath), i->queryDrvPath(state));
-        
-        state.mkAttrs(*state.allocAttr(v, state.sMeta));
-        
+
+        Value & vMeta = *state.allocAttr(v, state.sMeta);
+        state.mkAttrs(vMeta);
+
         MetaInfo meta = i->queryMetaInfo(state);
 
         foreach (MetaInfo::const_iterator, j, meta) {
-            Value & v2(*state.allocAttr(*(*v.attrs)[state.sMeta].value, state.symbols.create(j->first)));
+            Value & v2(*state.allocAttr(vMeta, state.symbols.create(j->first)));
             switch (j->second.type) {
                 case MetaValue::tpInt: mkInt(v2, j->second.intValue); break;
                 case MetaValue::tpString: mkString(v2, j->second.stringValue); break;
@@ -92,6 +93,9 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
             }
         }
     
+        vMeta.attrs->sort();
+        v.attrs->sort();
+        
         /* This is only necessary when installing store paths, e.g.,
            `nix-env -i /nix/store/abcd...-foo'. */
         store->addTempRoot(i->queryOutPath(state));
@@ -118,7 +122,8 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
     mkString(*state.allocAttr(args, state.sSystem), thisSystem);
     mkString(*state.allocAttr(args, state.symbols.create("manifest")),
         manifestFile, singleton<PathSet>(manifestFile));
-    (*args.attrs)[state.symbols.create("derivations")].value = &manifest;
+    args.attrs->push_back(Attr(state.symbols.create("derivations"), &manifest));
+    args.attrs->sort();
     mkApp(topLevel, envBuilder, args);
         
     /* Evaluate it. */
diff --git a/tests/lang/eval-okay-listtoattrs.nix b/tests/lang/eval-okay-listtoattrs.nix
index 023c1d84e573..4186e029b538 100644
--- a/tests/lang/eval-okay-listtoattrs.nix
+++ b/tests/lang/eval-okay-listtoattrs.nix
@@ -7,5 +7,5 @@ let
   a = builtins.listToAttrs list;
   b = builtins.listToAttrs ( list ++ list );
   r = builtins.listToAttrs [ (asi "result" [ a b ]) ( asi "throw" (throw "this should not be thrown")) ];
-  x = builtins.listToAttrs [ (asi "foo" "bla") (asi "foo" "bar") ];
+  x = builtins.listToAttrs [ (asi "foo" "bar") (asi "foo" "bla") ];
 in concat (map (x: x.a) r.result) + x.foo
-- 
cgit 1.4.1


From 43535499f38acc04367eeb4dd0d9938e9f8666f8 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Sun, 24 Oct 2010 20:09:37 +0000
Subject: * When allocating an attribute set, reserve enough space for all  
 elements.  This prevents the vector from having to resize itself.

---
 src/libexpr/eval.cc     | 16 +++++-----------
 src/libexpr/eval.hh     |  4 +---
 src/libexpr/primops.cc  | 23 ++++++++++++-----------
 src/nix-env/user-env.cc |  6 +++---
 4 files changed, 21 insertions(+), 28 deletions(-)

(limited to 'src/libexpr/primops.cc')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 4aa8fc1e44b5..919ebd4ba9b6 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -340,11 +340,12 @@ void EvalState::mkList(Value & v, unsigned int length)
 }
 
 
-void EvalState::mkAttrs(Value & v)
+void EvalState::mkAttrs(Value & v, unsigned int expected)
 {
     clearValue(v);
     v.type = tAttrs;
     v.attrs = NEW Bindings;
+    v.attrs->reserve(expected);
     nrAttrsets++;
 }
 
@@ -391,13 +392,6 @@ Value * EvalState::maybeThunk(Env & env, Expr * expr)
 }
 
 
-void EvalState::cloneAttrs(Value & src, Value & dst)
-{
-    mkAttrs(dst);
-    *dst.attrs = *src.attrs;
-}
-
-
 void EvalState::evalFile(const Path & path, Value & v)
 {
     startNest(nest, lvlTalkative, format("evaluating file `%1%'") % path);
@@ -504,7 +498,7 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v)
 
 void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
 {
-    state.mkAttrs(v); // !!! reserve size
+    state.mkAttrs(v, attrs.size());
 
     if (recursive) {
         /* Create a new environment that contains the attributes in
@@ -758,7 +752,7 @@ void EvalState::autoCallFunction(Bindings & args, Value & fun, Value & res)
     }
 
     Value actualArgs;
-    mkAttrs(actualArgs);
+    mkAttrs(actualArgs, fun.lambda.fun->formals->formals.size());
 
     foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
         Bindings::iterator j = args.find(i->name);
@@ -852,7 +846,7 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
     if (v1.attrs->size() == 0) { v = v2; return; }
     if (v2.attrs->size() == 0) { v = v1; return; }
 
-    state.mkAttrs(v);
+    state.mkAttrs(v, v1.attrs->size() + v2.attrs->size());
 
     /* Merge the attribute sets, preferring values from the second
        set.  Make sure to keep the resulting vector in sorted
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 7f801d1125fb..7453ac189197 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -319,13 +319,11 @@ public:
     Value * allocAttr(Value & vAttrs, const Symbol & name);
 
     void mkList(Value & v, unsigned int length);
-    void mkAttrs(Value & v);
+    void mkAttrs(Value & v, unsigned int expected);
     void mkThunk_(Value & v, Expr * expr);
 
     Value * maybeThunk(Env & env, Expr * expr);
     
-    void cloneAttrs(Value & src, Value & dst);
-
     /* Print statistics. */
     void printStats();
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 7c713f384f33..a4812de06519 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -206,7 +206,7 @@ static void prim_addErrorContext(EvalState & state, Value * * args, Value & v)
  * else => {success=false; value=false;} */
 static void prim_tryEval(EvalState & state, Value * * args, Value & v)
 {
-    state.mkAttrs(v);
+    state.mkAttrs(v, 2);
     try {
         state.forceValue(*args[0]);
         v.attrs->push_back(Attr(state.symbols.create("value"), args[0]));
@@ -484,7 +484,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     state.drvHashes[drvPath] = hashDerivationModulo(state, drv);
 
     /* !!! assumes a single output */
-    state.mkAttrs(v);
+    state.mkAttrs(v, 2);
     mkString(*state.allocAttr(v, state.sOutPath), outPath, singleton<PathSet>(drvPath));
     mkString(*state.allocAttr(v, state.sDrvPath), drvPath, singleton<PathSet>("=" + drvPath));
     v.attrs->sort();
@@ -745,7 +745,7 @@ static void prim_removeAttrs(EvalState & state, Value * * args, Value & v)
     /* Copy all attributes not in that set.  Note that we don't need
        to sort v.attrs because it's a subset of an already sorted
        vector. */
-    state.mkAttrs(v);
+    state.mkAttrs(v, args[0]->attrs->size());
     foreach (Bindings::iterator, i, *args[0]->attrs) {
         if (names.find(i->name) == names.end())
             v.attrs->push_back(*i);
@@ -761,7 +761,7 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
 {
     state.forceList(*args[0]);
 
-    state.mkAttrs(v);
+    state.mkAttrs(v, args[0]->list.length);
 
     std::set<Symbol> seen;
 
@@ -798,7 +798,7 @@ static void prim_intersectAttrs(EvalState & state, Value * * args, Value & v)
     state.forceAttrs(*args[0]);
     state.forceAttrs(*args[1]);
         
-    state.mkAttrs(v);
+    state.mkAttrs(v, std::min(args[0]->attrs->size(), args[1]->attrs->size()));
 
     foreach (Bindings::iterator, i, *args[0]->attrs) {
         Bindings::iterator j = args[1]->attrs->find(i->name);
@@ -827,14 +827,15 @@ static void prim_functionArgs(EvalState & state, Value * * args, Value & v)
     if (args[0]->type != tLambda)
         throw TypeError("`functionArgs' requires a function");
 
-    state.mkAttrs(v);
-
-    if (!args[0]->lambda.fun->matchAttrs) return;
+    if (!args[0]->lambda.fun->matchAttrs) {
+        state.mkAttrs(v, 0);
+        return;
+    }
 
+    state.mkAttrs(v, args[0]->lambda.fun->formals->formals.size());
     foreach (Formals::Formals_::iterator, i, args[0]->lambda.fun->formals->formals)
         // !!! should optimise booleans (allocate only once)
         mkBool(*state.allocAttr(v, i->name), i->def);
-
     v.attrs->sort();
 }
 
@@ -1015,7 +1016,7 @@ static void prim_parseDrvName(EvalState & state, Value * * args, Value & v)
 {
     string name = state.forceStringNoCtx(*args[0]);
     DrvName parsed(name);
-    state.mkAttrs(v);
+    state.mkAttrs(v, 2);
     mkString(*state.allocAttr(v, state.sName), parsed.name);
     mkString(*state.allocAttr(v, state.symbols.create("version")), parsed.version);
     v.attrs->sort();
@@ -1043,7 +1044,7 @@ void EvalState::createBaseEnv()
     Value v;
 
     /* `builtins' must be first! */
-    mkAttrs(v);
+    mkAttrs(v, 128);
     addConstant("builtins", v);
 
     mkBool(v, true);
diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc
index acd866197c7c..865d24e2f919 100644
--- a/src/nix-env/user-env.cc
+++ b/src/nix-env/user-env.cc
@@ -61,7 +61,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
 
         Value & v(*state.allocValue());
         manifest.list.elems[n++] = &v;
-        state.mkAttrs(v);
+        state.mkAttrs(v, 8);
 
         mkString(*state.allocAttr(v, state.sType), "derivation");
         mkString(*state.allocAttr(v, state.sName), i->name);
@@ -71,7 +71,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
             mkString(*state.allocAttr(v, state.sDrvPath), i->queryDrvPath(state));
 
         Value & vMeta = *state.allocAttr(v, state.sMeta);
-        state.mkAttrs(vMeta);
+        state.mkAttrs(vMeta, 16);
 
         MetaInfo meta = i->queryMetaInfo(state);
 
@@ -118,7 +118,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
     /* Construct a Nix expression that calls the user environment
        builder with the manifest as argument. */
     Value args, topLevel;
-    state.mkAttrs(args);
+    state.mkAttrs(args, 3);
     mkString(*state.allocAttr(args, state.sSystem), thisSystem);
     mkString(*state.allocAttr(args, state.symbols.create("manifest")),
         manifestFile, singleton<PathSet>(manifestFile));
-- 
cgit 1.4.1