From e879a0371ba7ef99da2d82547823c3f96b445fdb Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Wed, 20 Oct 2010 11:38:30 +0000
Subject: * Use the Boehm garbage collector to reclaim unused memory in the Nix
   expression evaluator.

---
 src/libexpr/Makefile.am |  3 ++-
 src/libexpr/eval.cc     | 23 ++++++++++++++---------
 src/libexpr/eval.hh     |  5 ++++-
 3 files changed, 20 insertions(+), 11 deletions(-)

(limited to 'src/libexpr')

diff --git a/src/libexpr/Makefile.am b/src/libexpr/Makefile.am
index e7228e183581..24aa2968b195 100644
--- a/src/libexpr/Makefile.am
+++ b/src/libexpr/Makefile.am
@@ -20,7 +20,8 @@ EXTRA_DIST = lexer.l parser.y
 
 AM_CXXFLAGS = \
  -I$(srcdir)/.. \
- -I$(srcdir)/../libutil -I$(srcdir)/../libstore
+ -I$(srcdir)/../libutil -I$(srcdir)/../libstore \
+ -I/home/eelco/Dev/nix/boehmgc/include
 
 
 # Parser generation.
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index e55f28822b6a..ba331749fe9c 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -8,6 +8,9 @@
 
 #include <cstring>
 
+#include <gc/gc.h>
+#include <gc/gc_cpp.h>
+
 
 #define LocalNoInline(f) static f __attribute__((noinline)); f
 #define LocalNoInlineNoReturn(f) static f __attribute__((noinline, noreturn)); f
@@ -147,7 +150,7 @@ void EvalState::addPrimOp(const string & name,
     v.type = tPrimOp;
     v.primOp.arity = arity;
     v.primOp.fun = primOp;
-    v.primOp.name = strdup(name2.c_str());
+    v.primOp.name = GC_strdup(name2.c_str());
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v;
     (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
@@ -218,7 +221,7 @@ LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2,
 void mkString(Value & v, const char * s)
 {
     v.type = tString;
-    v.string.s = strdup(s);
+    v.string.s = GC_strdup(s);
     v.string.context = 0;
 }
 
@@ -228,9 +231,10 @@ void mkString(Value & v, const string & s, const PathSet & context)
     mkString(v, s.c_str());
     if (!context.empty()) {
         unsigned int n = 0;
-        v.string.context = new const char *[context.size() + 1];
+        v.string.context = (const char * *)
+            GC_malloc((context.size() + 1) * sizeof(char *));
         foreach (PathSet::const_iterator, i, context) 
-            v.string.context[n++] = strdup(i->c_str());
+            v.string.context[n++] = GC_strdup(i->c_str());
         v.string.context[n] = 0;
     }
 }
@@ -239,7 +243,7 @@ void mkString(Value & v, const string & s, const PathSet & context)
 void mkPath(Value & v, const char * s)
 {
     v.type = tPath;
-    v.path = strdup(s);
+    v.path = GC_strdup(s);
 }
 
 
@@ -264,7 +268,7 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
 Value * EvalState::allocValues(unsigned int count)
 {
     nrValues += count;
-    return new Value[count]; // !!! check destructor
+    return (Value *) GC_MALLOC(count * sizeof(Value));
 }
 
 
@@ -272,7 +276,7 @@ Env & EvalState::allocEnv(unsigned int size)
 {
     nrEnvs++;
     nrValuesInEnvs += size;
-    Env * env = (Env *) malloc(sizeof(Env) + size * sizeof(Value));
+    Env * env = (Env *) GC_MALLOC(sizeof(Env) + size * sizeof(Value));
     return *env;
 }
 
@@ -281,7 +285,7 @@ void EvalState::mkList(Value & v, unsigned int length)
 {
     v.type = tList;
     v.list.length = length;
-    v.list.elems = new Value *[length];
+    v.list.elems = (Value * *) GC_MALLOC(length * sizeof(Value *));
     nrListElems += length;
 }
 
@@ -289,7 +293,7 @@ void EvalState::mkList(Value & v, unsigned int length)
 void EvalState::mkAttrs(Value & v)
 {
     v.type = tAttrs;
-    v.attrs = new Bindings;
+    v.attrs = new (UseGC) Bindings;
 }
 
 
@@ -1089,6 +1093,7 @@ void EvalState::printStats()
     bool showStats = getEnv("NIX_SHOW_STATS", "0") != "0";
     Verbosity v = showStats ? lvlInfo : lvlDebug;
     printMsg(v, "evaluation statistics:");
+    printMsg(v, format("  size of a value: %1%") % sizeof(Value));
     printMsg(v, format("  expressions evaluated: %1%") % nrEvaluated);
     printMsg(v, format("  stack space used: %1% bytes") % (&x - deepestStack));
     printMsg(v, format("  max eval() nesting depth: %1%") % maxRecursionDepth);
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 501ac93d016e..d74a0350624d 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -7,6 +7,8 @@
 
 #include <map>
 
+#include <gc/gc_allocator.h>
+
 
 namespace nix {
 
@@ -16,7 +18,7 @@ struct Env;
 struct Value;
 struct Attr;
 
-typedef std::map<Symbol, Attr> Bindings;
+typedef std::map<Symbol, Attr, std::less<Symbol>, gc_allocator<std::pair<const Symbol, Attr> > > Bindings;
 
 
 typedef enum {
@@ -313,6 +315,7 @@ private:
     char * deepestStack; /* for measuring stack usage */
     
     friend class RecursionCounter;
+    friend class ExprOpUpdate;
 };
 
 
-- 
cgit 1.4.1


From 76feaf016a7e9a9b019148df5ff84a63e48dbda7 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Wed, 20 Oct 2010 15:48:00 +0000
Subject: * Keep some more stats.

---
 src/libexpr/eval.cc | 9 +++++++++
 src/libexpr/eval.hh | 3 +++
 2 files changed, 12 insertions(+)

(limited to 'src/libexpr')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index ba331749fe9c..46978f6d0b81 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -119,6 +119,7 @@ EvalState::EvalState()
 {
     nrEnvs = nrValuesInEnvs = nrValues = nrListElems = 0;
     nrEvaluated = recursionDepth = maxRecursionDepth = 0;
+    nrAttrsets = nrOpUpdates = nrOpUpdateValuesCopied = 0;
     deepestStack = (char *) -1;
 
     createBaseEnv();
@@ -294,6 +295,7 @@ void EvalState::mkAttrs(Value & v)
 {
     v.type = tAttrs;
     v.attrs = new (UseGC) Bindings;
+    nrAttrsets++;
 }
 
 
@@ -758,6 +760,8 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
     state.evalAttrs(env, e1, v1);
     state.evalAttrs(env, e2, v2);
 
+    state.nrOpUpdates++;
+
     if (v1.attrs->size() == 0) { v = v2; return; }
     if (v2.attrs->size() == 0) { v = v1; return; }
 
@@ -768,6 +772,8 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
         mkCopy(a.value, i->second.value);
         a.pos = i->second.pos;
     }
+
+    state.nrOpUpdateValuesCopied += v.attrs->size();
 }
 
 
@@ -1107,6 +1113,9 @@ void EvalState::printStats()
         % nrListElems % (nrListElems * sizeof(Value *)));
     printMsg(v, format("  misc. values allocated: %1% (%2% bytes)")
         % nrValues % (nrValues * sizeof(Value)));
+    printMsg(v, format("  attribute sets allocated: %1%") % nrAttrsets);
+    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());
 }
 
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index d74a0350624d..9144d99a4b38 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -310,6 +310,9 @@ private:
     unsigned long nrValues;
     unsigned long nrListElems;
     unsigned long nrEvaluated;
+    unsigned long nrAttrsets;
+    unsigned long nrOpUpdates;
+    unsigned long nrOpUpdateValuesCopied;
     unsigned int recursionDepth;
     unsigned int maxRecursionDepth;
     char * deepestStack; /* for measuring stack usage */
-- 
cgit 1.4.1


From 64c3325b0bef8c0234bf797033e129323b36ad1e Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Fri, 22 Oct 2010 13:39:15 +0000
Subject: * Make building against the Boehm GC a configure option.

---
 configure.ac                    | 13 +++++++++++++
 src/libexpr/Makefile.am         |  3 +--
 src/libexpr/eval.cc             | 23 ++++++++++++++++++-----
 src/libexpr/eval.hh             |  6 ++++++
 src/nix-env/Makefile.am         |  5 ++---
 src/nix-instantiate/Makefile.am |  6 ++----
 6 files changed, 42 insertions(+), 14 deletions(-)

(limited to 'src/libexpr')

diff --git a/configure.ac b/configure.ac
index 1caa9be5c4a6..02eebf6924b7 100644
--- a/configure.ac
+++ b/configure.ac
@@ -250,6 +250,19 @@ AC_SUBST(bzip2_bin)
 AC_SUBST(bzip2_bin_test)
 
 
+# Whether to use the Boehm garbage collector.
+AC_ARG_WITH(boehm-gc, AC_HELP_STRING([--with-boehm-gc=PATH],
+  [prefix of the Boehm GC package to enable garbage collection in the Nix expression evaluator]),
+  boehmgc=$withval, boehmgc=)
+if test -n "$boehmgc"; then
+  boehmgc_lib="-L$boehmgc/lib -lgc"
+  CXXFLAGS="-I$boehmgc/include $CXXFLAGS"
+  AC_DEFINE(HAVE_BOEHMGC, 1, [Whether to use the Boehm garbage collector.])
+fi
+AC_SUBST(boehmgc_lib)
+AC_SUBST(boehmgc_include)
+  
+
 AC_ARG_ENABLE(init-state, AC_HELP_STRING([--disable-init-state],
   [do not initialise DB etc. in `make install']),
   init_state=$enableval, init_state=yes)
diff --git a/src/libexpr/Makefile.am b/src/libexpr/Makefile.am
index 24aa2968b195..e7228e183581 100644
--- a/src/libexpr/Makefile.am
+++ b/src/libexpr/Makefile.am
@@ -20,8 +20,7 @@ EXTRA_DIST = lexer.l parser.y
 
 AM_CXXFLAGS = \
  -I$(srcdir)/.. \
- -I$(srcdir)/../libutil -I$(srcdir)/../libstore \
- -I/home/eelco/Dev/nix/boehmgc/include
+ -I$(srcdir)/../libutil -I$(srcdir)/../libstore
 
 
 # Parser generation.
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 46978f6d0b81..c8a031ac6d0a 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -8,9 +8,18 @@
 
 #include <cstring>
 
+#if HAVE_BOEHMGC
+
 #include <gc/gc.h>
 #include <gc/gc_cpp.h>
 
+#else
+
+#define GC_STRDUP strdup
+#define GC_MALLOC malloc
+
+#endif
+
 
 #define LocalNoInline(f) static f __attribute__((noinline)); f
 #define LocalNoInlineNoReturn(f) static f __attribute__((noinline, noreturn)); f
@@ -151,7 +160,7 @@ void EvalState::addPrimOp(const string & name,
     v.type = tPrimOp;
     v.primOp.arity = arity;
     v.primOp.fun = primOp;
-    v.primOp.name = GC_strdup(name2.c_str());
+    v.primOp.name = GC_STRDUP(name2.c_str());
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v;
     (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
@@ -222,7 +231,7 @@ LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2,
 void mkString(Value & v, const char * s)
 {
     v.type = tString;
-    v.string.s = GC_strdup(s);
+    v.string.s = GC_STRDUP(s);
     v.string.context = 0;
 }
 
@@ -233,9 +242,9 @@ void mkString(Value & v, const string & s, const PathSet & context)
     if (!context.empty()) {
         unsigned int n = 0;
         v.string.context = (const char * *)
-            GC_malloc((context.size() + 1) * sizeof(char *));
+            GC_MALLOC((context.size() + 1) * sizeof(char *));
         foreach (PathSet::const_iterator, i, context) 
-            v.string.context[n++] = GC_strdup(i->c_str());
+            v.string.context[n++] = GC_STRDUP(i->c_str());
         v.string.context[n] = 0;
     }
 }
@@ -244,7 +253,7 @@ void mkString(Value & v, const string & s, const PathSet & context)
 void mkPath(Value & v, const char * s)
 {
     v.type = tPath;
-    v.path = GC_strdup(s);
+    v.path = GC_STRDUP(s);
 }
 
 
@@ -294,7 +303,11 @@ void EvalState::mkList(Value & v, unsigned int length)
 void EvalState::mkAttrs(Value & v)
 {
     v.type = tAttrs;
+#if HAVE_BOEHMGC
     v.attrs = new (UseGC) Bindings;
+#else
+    v.attrs = new Bindings;
+#endif
     nrAttrsets++;
 }
 
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 9144d99a4b38..738ca9439f6d 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -7,7 +7,9 @@
 
 #include <map>
 
+#if HAVE_BOEHMGC
 #include <gc/gc_allocator.h>
+#endif
 
 
 namespace nix {
@@ -18,7 +20,11 @@ struct Env;
 struct Value;
 struct Attr;
 
+#if HAVE_BOEHMGC
 typedef std::map<Symbol, Attr, std::less<Symbol>, gc_allocator<std::pair<const Symbol, Attr> > > Bindings;
+#else
+typedef std::map<Symbol, Attr> Bindings;
+#endif
 
 
 typedef enum {
diff --git a/src/nix-env/Makefile.am b/src/nix-env/Makefile.am
index 169c85fcb679..a876b3eb386d 100644
--- a/src/nix-env/Makefile.am
+++ b/src/nix-env/Makefile.am
@@ -5,7 +5,7 @@ nix_env_SOURCES = nix-env.cc profiles.cc profiles.hh user-env.cc user-env.hh hel
 nix_env_LDADD = ../libmain/libmain.la ../libexpr/libexpr.la \
  ../libstore/libstore.la ../libutil/libutil.la \
  ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@ \
- -L/home/eelco/Dev/nix/boehmgc/lib -lgc
+ @boehmgc_lib@
 
 nix-env.o: help.txt.hh
 
@@ -15,5 +15,4 @@ nix-env.o: help.txt.hh
 AM_CXXFLAGS = \
  -I$(srcdir)/.. \
  -I$(srcdir)/../libutil -I$(srcdir)/../libstore \
- -I$(srcdir)/../libexpr -I$(srcdir)/../libmain -I../libexpr \
- -I/home/eelco/Dev/nix/boehmgc/include
+ -I$(srcdir)/../libexpr -I$(srcdir)/../libmain -I../libexpr
diff --git a/src/nix-instantiate/Makefile.am b/src/nix-instantiate/Makefile.am
index c6455b116d43..bc9792818c3c 100644
--- a/src/nix-instantiate/Makefile.am
+++ b/src/nix-instantiate/Makefile.am
@@ -4,7 +4,7 @@ nix_instantiate_SOURCES = nix-instantiate.cc help.txt
 nix_instantiate_LDADD = ../libmain/libmain.la ../libexpr/libexpr.la \
  ../libstore/libstore.la ../libutil/libutil.la \
  ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@ \
- -L/home/eelco/Dev/nix/boehmgc/lib -lgc
+ @boehmgc_lib@
 
 nix-instantiate.o: help.txt.hh
 
@@ -13,6 +13,4 @@ nix-instantiate.o: help.txt.hh
 
 AM_CXXFLAGS = \
  -I$(srcdir)/.. -I$(srcdir)/../libutil -I$(srcdir)/../libstore \
- -I$(srcdir)/../libexpr -I$(srcdir)/../libmain -I../libexpr \
- -I/home/eelco/Dev/nix/boehmgc/include
-
+ -I$(srcdir)/../libexpr -I$(srcdir)/../libmain -I../libexpr
-- 
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')

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 4dee289550d11950d6d17482484061a4792b2eef Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Fri, 22 Oct 2010 15:51:52 +0000
Subject: * In environments, store pointers to values rather than values.  This
   improves GC effectiveness a bit more (because a live value doesn't   keep
 other values in the environment plus the parent environments   alive), and
 removes the need for copy nodes.

---
 src/libexpr/eval.cc | 50 ++++++++++++++++++++++++--------------------------
 src/libexpr/eval.hh | 10 +---------
 2 files changed, 25 insertions(+), 35 deletions(-)

(limited to 'src/libexpr')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index ea48947258ec..3f2371d7957a 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -72,7 +72,6 @@ std::ostream & operator << (std::ostream & str, const Value & v)
         break;
     case tThunk:
     case tApp:
-    case tCopy:
         str << "<CODE>";
         break;
     case tLambda:
@@ -104,7 +103,6 @@ string showType(const Value & v)
         case tThunk: return "a thunk";
         case tApp: return "a function application";
         case tLambda: return "a function";
-        case tCopy: return "a copy";
         case tBlackhole: return "a black hole";
         case tPrimOp: return "a built-in function";
         case tPrimOpApp: return "a partially applied built-in function";
@@ -148,9 +146,9 @@ void EvalState::addConstant(const string & name, Value & v)
     Value * v2 = allocValue();
     *v2 = v;
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
-    baseEnv.values[baseEnvDispl++] = v;
+    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)[symbols.create(name2)].value = v2;
 }
 
 
@@ -164,8 +162,8 @@ void EvalState::addPrimOp(const string & name,
     v->primOp.fun = primOp;
     v->primOp.name = GC_STRDUP(name2.c_str());
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
-    baseEnv.values[baseEnvDispl++] = *v;
-    (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
+    baseEnv.values[baseEnvDispl++] = v;
+    (*baseEnv.values[0]->attrs)[symbols.create(name2)].value = v;
 }
 
 
@@ -265,15 +263,15 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
     
     if (var.fromWith) {
         while (1) {
-            Bindings::iterator j = env->values[0].attrs->find(var.name);
-            if (j != env->values[0].attrs->end())
+            Bindings::iterator j = env->values[0]->attrs->find(var.name);
+            if (j != env->values[0]->attrs->end())
                 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) ;
         }
     } else
-        return &env->values[var.displ];
+        return env->values[var.displ];
 }
 
 
@@ -295,7 +293,7 @@ Env & EvalState::allocEnv(unsigned int size)
 {
     nrEnvs++;
     nrValuesInEnvs += size;
-    Env * env = (Env *) GC_MALLOC(sizeof(Env) + size * sizeof(Value));
+    Env * env = (Env *) GC_MALLOC(sizeof(Env) + size * sizeof(Value *));
     return *env;
 }
 
@@ -465,7 +463,7 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
             nix::Attr & a = (*v.attrs)[i->first];
             a.value = state.allocValue();
             mkThunk(*a.value, env2, i->second.first);
-            mkCopy(env2.values[displ++], *a.value);
+            env2.values[displ++] = a.value;
             a.pos = &i->second.second;
         }
 
@@ -475,7 +473,7 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
             nix::Attr & a = (*v.attrs)[i->first.name];
             Value * v2 = state.lookupVar(&env, i->first);
             a.value = v2;
-            mkCopy(env2.values[displ++], *v2);
+            env2.values[displ++] = v2;
             a.pos = &i->second;
         }
 
@@ -493,7 +491,7 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
             foreach (Bindings::iterator, i, *overrides->second.value->attrs) {
                 nix::Attr & a = (*v.attrs)[i->first];
                 if (a.value)
-                    mkCopy(env2.values[displs[i->first]], *i->second.value);
+                    env2.values[displs[i->first]] = i->second.value;
                 a = i->second;
             }
         }
@@ -527,13 +525,15 @@ 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)
-        mkThunk(env2.values[displ++], env2, i->second.first);
+    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs) {
+        env2.values[displ] = state.allocValue();
+        mkThunk(*env2.values[displ++], 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)
-        mkCopy(env2.values[displ++], *state.lookupVar(&env, i->first));
+        env2.values[displ++] = state.lookupVar(&env, i->first);
 
     state.eval(env2, body, v);
 }
@@ -654,13 +654,13 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
     unsigned int displ = 0;
 
     if (!fun.lambda.fun->matchAttrs)
-        env2.values[displ++] = arg;
+        env2.values[displ++] = &arg;
 
     else {
         forceAttrs(arg);
         
         if (!fun.lambda.fun->arg.empty())
-            env2.values[displ++] = arg;
+            env2.values[displ++] = &arg;
 
         /* For each formal argument, get the actual argument.  If
            there is no matching actual argument but the formal
@@ -670,11 +670,12 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
             Bindings::iterator j = arg.attrs->find(i->name);
             if (j == arg.attrs->end()) {
                 if (!i->def) throwTypeError("function at %1% called without required argument `%2%'",
-                    fun.lambda.fun->pos, i->name);   
-                mkThunk(env2.values[displ++], env2, i->def);
+                    fun.lambda.fun->pos, i->name);
+                env2.values[displ] = allocValue();
+                mkThunk(*env2.values[displ++], env2, i->def);
             } else {
                 attrsUsed++;
-                mkCopy(env2.values[displ++], *j->second.value);
+                env2.values[displ++] = j->second.value;
             }
         }
 
@@ -725,7 +726,8 @@ void ExprWith::eval(EvalState & state, Env & env, Value & v)
     env2.up = &env;
     env2.prevWith = prevWith;
 
-    state.evalAttrs(env, attrs, env2.values[0]);
+    env2.values[0] = state.allocValue();
+    state.evalAttrs(env, attrs, *env2.values[0]);
 
     state.eval(env2, body, v);
 }
@@ -864,10 +866,6 @@ void EvalState::forceValue(Value & v)
             throw;
         }
     }
-    else if (v.type == tCopy) {
-        forceValue(*v.val);
-        v = *v.val;
-    }
     else if (v.type == tApp)
         callFunction(*v.app.left, *v.app.right, v);
     else if (v.type == tBlackhole)
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index ee7db91a08b2..b6ec927f01fa 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -38,7 +38,6 @@ typedef enum {
     tThunk,
     tApp,
     tLambda,
-    tCopy,
     tBlackhole,
     tPrimOp,
     tPrimOpApp,
@@ -116,7 +115,7 @@ struct Env
 {
     Env * up;
     unsigned int prevWith; // nr of levels up to next `with' environment
-    Value values[0];
+    Value * values[0];
 };
 
 
@@ -150,13 +149,6 @@ static inline void mkThunk(Value & v, Env & env, Expr * expr)
 }
 
 
-static inline void mkCopy(Value & v, Value & src)
-{
-    v.type = tCopy;
-    v.val = &src;
-}
-
-
 static inline void mkApp(Value & v, Value & left, Value & right)
 {
     v.type = tApp;
-- 
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')

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 8ac06726b92fff66714ceee8af89068ac876875a Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Sat, 23 Oct 2010 20:07:47 +0000
Subject: * Make Value smaller by not storing redundant PrimOp info. * Clear
 pointers in Values after overwriting them to make sure that no   objects are
 kept alive unnecessarily.

---
 src/libexpr/eval.cc | 37 +++++++++++++++++++++----------------
 src/libexpr/eval.hh | 32 +++++++++++++++++++++++---------
 2 files changed, 44 insertions(+), 25 deletions(-)

(limited to 'src/libexpr')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index faf18cb7f471..72a3bf9b9c52 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -153,15 +153,14 @@ void EvalState::addConstant(const string & name, Value & v)
 
 
 void EvalState::addPrimOp(const string & name,
-    unsigned int arity, PrimOp primOp)
+    unsigned int arity, PrimOpFun primOp)
 {
     Value * v = allocValue();
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
+    Symbol sym = symbols.create(name);
     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;
+    v->primOp = new (UseGC) PrimOp(primOp, arity, sym);
+    staticBaseEnv.vars[sym] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v;
     (*baseEnv.values[0]->attrs)[symbols.create(name2)].value = v;
 }
@@ -252,6 +251,7 @@ void mkString(Value & v, const string & s, const PathSet & context)
 
 void mkPath(Value & v, const char * s)
 {
+    clearValue(v);
     v.type = tPath;
     v.path = GC_STRDUP(s);
 }
@@ -310,6 +310,7 @@ void EvalState::mkList(Value & v, unsigned int length)
 
 void EvalState::mkAttrs(Value & v)
 {
+    clearValue(v);
     v.type = tAttrs;
 #if HAVE_BOEHMGC
     v.attrs = new (UseGC) Bindings;
@@ -595,15 +596,20 @@ void ExprApp::eval(EvalState & state, Env & env, Value & v)
 void EvalState::callFunction(Value & fun, Value & arg, Value & v)
 {
     if (fun.type == tPrimOp || fun.type == tPrimOpApp) {
-        unsigned int argsLeft =
-            fun.type == tPrimOp ? fun.primOp.arity : fun.primOpApp.argsLeft;
+
+        /* Figure out the number of arguments still needed. */
+        unsigned int argsDone = 0;
+        Value * primOp = &fun;
+        while (primOp->type == tPrimOpApp) {
+            argsDone++;
+            primOp = primOp->primOpApp.left;
+        }
+        assert(primOp->type == tPrimOp);
+        unsigned int arity = primOp->primOp->arity;
+        unsigned int argsLeft = arity - argsDone;
+        
         if (argsLeft == 1) {
-            /* We have all the arguments, so call the primop.  First
-               find the primop. */
-            Value * primOp = &fun;
-            while (primOp->type == tPrimOpApp) primOp = primOp->primOpApp.left;
-            assert(primOp->type == tPrimOp);
-            unsigned int arity = primOp->primOp.arity;
+            /* We have all the arguments, so call the primop. */
                 
             /* Put all the arguments in an array. */
             Value * vArgs[arity];
@@ -614,9 +620,9 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
 
             /* And call the primop. */
             try {
-                primOp->primOp.fun(*this, vArgs, v);
+                primOp->primOp->fun(*this, vArgs, v);
             } catch (Error & e) {
-                addErrorPrefix(e, "while evaluating the builtin function `%1%':\n", primOp->primOp.name);
+                addErrorPrefix(e, "while evaluating the builtin function `%1%':\n", primOp->primOp->name);
                 throw;
             }
         } else {
@@ -624,7 +630,6 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
             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 5f5966930f0e..ec4939442515 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -44,7 +44,17 @@ typedef enum {
 } ValueType;
 
 
-typedef void (* PrimOp) (EvalState & state, Value * * args, Value & v);
+typedef void (* PrimOpFun) (EvalState & state, Value * * args, Value & v);
+
+
+struct PrimOp
+{
+    PrimOpFun fun;
+    unsigned int arity;
+    Symbol name;
+    PrimOp(PrimOpFun fun, unsigned int arity, Symbol name)
+        : fun(fun), arity(arity), name(name) { }
+};
 
 
 struct Value
@@ -97,15 +107,9 @@ struct Value
             Env * env;
             ExprLambda * fun;
         } lambda;
-        Value * val;
-        struct {
-            PrimOp fun;
-            char * name;
-            unsigned int arity;
-        } primOp;
+        PrimOp * primOp;
         struct {
             Value * left, * right;
-            unsigned int argsLeft;
         } primOpApp;
     };
 };
@@ -127,8 +131,17 @@ struct Attr
 };
 
 
+/* After overwriting an app node, be sure to clear pointers in the
+   Value to ensure that the target isn't kept alive unnecessarily. */
+static inline void clearValue(Value & v)
+{
+    v.app.right = 0;
+}
+
+
 static inline void mkInt(Value & v, int n)
 {
+    clearValue(v);
     v.type = tInt;
     v.integer = n;
 }
@@ -136,6 +149,7 @@ static inline void mkInt(Value & v, int n)
 
 static inline void mkBool(Value & v, bool b)
 {
+    clearValue(v);
     v.type = tBool;
     v.boolean = b;
 }
@@ -268,7 +282,7 @@ private:
     void addConstant(const string & name, Value & v);
 
     void addPrimOp(const string & name,
-        unsigned int arity, PrimOp primOp);
+        unsigned int arity, PrimOpFun primOp);
 
     Value * lookupVar(Env * env, const VarRef & var);
     
-- 
cgit 1.4.1


From b2ba62170cc8359d2f8bbbd9dbacf331b98151fe Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Sat, 23 Oct 2010 21:11:59 +0000
Subject: * Optimise string constants by putting them in the symbol table.

---
 src/libexpr/eval.cc    | 10 ++++++-
 src/libexpr/lexer.l    |  8 +++---
 src/libexpr/nixexpr.hh |  4 +--
 src/libexpr/parser.y   | 72 ++++++++++++++++++++++++++++----------------------
 4 files changed, 55 insertions(+), 39 deletions(-)

(limited to 'src/libexpr')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 72a3bf9b9c52..8c33fd22486c 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -249,6 +249,14 @@ void mkString(Value & v, const string & s, const PathSet & context)
 }
 
 
+void mkString(Value & v, const Symbol & s)
+{
+    v.type = tString;
+    v.string.s = ((string) s).c_str();
+    v.string.context = 0;
+}
+
+
 void mkPath(Value & v, const char * s)
 {
     clearValue(v);
@@ -429,7 +437,7 @@ void ExprInt::eval(EvalState & state, Env & env, Value & v)
 
 void ExprString::eval(EvalState & state, Env & env, Value & v)
 {
-    mkString(v, s.c_str());
+    mkString(v, s);
 }
 
 
diff --git a/src/libexpr/lexer.l b/src/libexpr/lexer.l
index f29f9b684332..5b27e2582d2b 100644
--- a/src/libexpr/lexer.l
+++ b/src/libexpr/lexer.l
@@ -46,7 +46,7 @@ static void adjustLoc(YYLTYPE * loc, const char * s, size_t len)
 }
 
 
-static Expr * unescapeStr(const char * s)
+static Expr * unescapeStr(SymbolTable & symbols, const char * s)
 {
     string t;
     char c;
@@ -66,7 +66,7 @@ static Expr * unescapeStr(const char * s)
         }
         else t += c;
     }
-    return new ExprString(t);
+    return new ExprString(symbols.create(t));
 }
 
  
@@ -119,7 +119,7 @@ inherit     { return INHERIT; }
                  "$\"" will be consumed as part of a string, rather
                  than a "$" followed by the string terminator.
                  Disallow "$\"" for now. */
-              yylval->e = unescapeStr(yytext);
+              yylval->e = unescapeStr(data->symbols, yytext);
               return STR;
             }
 <STRING>\$\{  { BEGIN(INITIAL); return DOLLAR_CURLY; }
@@ -140,7 +140,7 @@ inherit     { return INHERIT; }
                    return IND_STR;
                  }
 <IND_STRING>\'\'\\. {
-                   yylval->e = unescapeStr(yytext + 2);
+                   yylval->e = unescapeStr(data->symbols, yytext + 2);
                    return IND_STR;
                  }
 <IND_STRING>\$\{ { BEGIN(INITIAL); return DOLLAR_CURLY; }
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 5c0071dca2ce..1aa3df3689a6 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -65,8 +65,8 @@ struct ExprInt : Expr
 
 struct ExprString : Expr
 {
-    string s;
-    ExprString(const string & s) : s(s) { };
+    Symbol s;
+    ExprString(const Symbol & s) : s(s) { };
     COMMON_METHODS
 };
 
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index b0c54339b051..3a72a4ade257 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -7,19 +7,44 @@
 %parse-param { yyscan_t scanner }
 %parse-param { ParseData * data }
 %lex-param { yyscan_t scanner }
+%lex-param { ParseData * data }
 
-
-%{
-/* Newer versions of Bison copy the declarations below to
-   parser-tab.hh, which sucks bigtime since lexer.l doesn't want that
-   stuff.  So allow it to be excluded. */
-#ifndef BISON_HEADER_HACK
-#define BISON_HEADER_HACK
-
+%code requires {
+    
+#ifndef BISON_HEADER
+#define BISON_HEADER
+    
 #include "util.hh"
     
 #include "nixexpr.hh"
 
+namespace nix {
+
+    struct ParseData 
+    {
+        SymbolTable & symbols;
+        Expr * result;
+        Path basePath;
+        Path path;
+        string error;
+        Symbol sLetBody;
+        ParseData(SymbolTable & symbols)
+            : symbols(symbols)
+            , sLetBody(symbols.create("<let-body>"))
+            { };
+    };
+    
+}
+
+#define YY_DECL int yylex \
+    (YYSTYPE * yylval_param, YYLTYPE * yylloc_param, yyscan_t yyscanner, nix::ParseData * data)
+
+#endif
+
+}
+
+%{
+
 #include "parser-tab.hh"
 #include "lexer-tab.hh"
 #define YYSTYPE YYSTYPE // workaround a bug in Bison 2.4
@@ -28,27 +53,13 @@
 #include <stdlib.h>
 #include <string.h>
 
+YY_DECL;
 
 using namespace nix;
 
 
 namespace nix {
-
     
-struct ParseData 
-{
-    SymbolTable & symbols;
-    Expr * result;
-    Path basePath;
-    Path path;
-    string error;
-    Symbol sLetBody;
-    ParseData(SymbolTable & symbols)
-        : symbols(symbols)
-        , sLetBody(symbols.create("<let-body>"))
-    { };
-};
-
 
 static string showAttrPath(const vector<Symbol> & attrPath)
 {
@@ -113,9 +124,9 @@ static void addFormal(const Pos & pos, Formals * formals, const Formal & formal)
 }
 
 
-static Expr * stripIndentation(vector<Expr *> & es)
+static Expr * stripIndentation(SymbolTable & symbols, vector<Expr *> & es)
 {
-    if (es.empty()) return new ExprString("");
+    if (es.empty()) return new ExprString(symbols.create(""));
     
     /* Figure out the minimum indentation.  Note that by design
        whitespace-only final lines are not taken into account.  (So
@@ -195,7 +206,7 @@ static Expr * stripIndentation(vector<Expr *> & es)
                 s2 = string(s2, 0, p + 1);
         }
 
-        es2->push_back(new ExprString(s2));
+        es2->push_back(new ExprString(symbols.create(s2)));
     }
 
     return new ExprConcatStrings(es2);
@@ -224,9 +235,6 @@ void yyerror(YYLTYPE * loc, yyscan_t scanner, ParseData * data, const char * err
 }
 
 
-#endif
-
-
 %}
 
 %union {
@@ -337,15 +345,15 @@ expr_simple
   | INT { $$ = new ExprInt($1); }
   | '"' string_parts '"' {
       /* For efficiency, and to simplify parse trees a bit. */
-      if ($2->empty()) $$ = new ExprString("");
+      if ($2->empty()) $$ = new ExprString(data->symbols.create(""));
       else if ($2->size() == 1) $$ = $2->front();
       else $$ = new ExprConcatStrings($2);
   }
   | IND_STRING_OPEN ind_string_parts IND_STRING_CLOSE {
-      $$ = stripIndentation(*$2);
+      $$ = stripIndentation(data->symbols, *$2);
   }
   | PATH { $$ = new ExprPath(absPath($1, data->basePath)); }
-  | URI { $$ = new ExprString($1); }
+  | URI { $$ = new ExprString(data->symbols.create($1)); }
   | '(' expr ')' { $$ = $2; }
   /* Let expressions `let {..., body = ...}' are just desugared
      into `(rec {..., body = ...}).body'. */
-- 
cgit 1.4.1


From a247d20604a97ff6e84b87f66e3338714e7964f0 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Sat, 23 Oct 2010 22:58:24 +0000
Subject: * Fix compiling without Boehm. * Fix the stats.

---
 src/libexpr/eval.cc | 18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

(limited to 'src/libexpr')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 8c33fd22486c..d73f99a156cf 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -13,11 +13,15 @@
 #include <gc/gc.h>
 #include <gc/gc_cpp.h>
 
+#define NEW (UseGC)
+
 #else
 
 #define GC_STRDUP strdup
 #define GC_MALLOC malloc
 
+#define NEW new
+
 #endif
 
 
@@ -159,7 +163,7 @@ void EvalState::addPrimOp(const string & name,
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
     Symbol sym = symbols.create(name);
     v->type = tPrimOp;
-    v->primOp = new (UseGC) PrimOp(primOp, arity, sym);
+    v->primOp = NEW PrimOp(primOp, arity, sym);
     staticBaseEnv.vars[sym] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v;
     (*baseEnv.values[0]->attrs)[symbols.create(name2)].value = v;
@@ -320,11 +324,7 @@ void EvalState::mkAttrs(Value & v)
 {
     clearValue(v);
     v.type = tAttrs;
-#if HAVE_BOEHMGC
-    v.attrs = new (UseGC) Bindings;
-#else
-    v.attrs = new Bindings;
-#endif
+    v.attrs = NEW Bindings;
     nrAttrsets++;
 }
 
@@ -1133,12 +1133,10 @@ void EvalState::printStats()
     printMsg(v, format("  stack space per eval() level: %1% bytes")
         % ((&x - deepestStack) / (float) maxRecursionDepth));
     printMsg(v, format("  environments allocated: %1% (%2% bytes)")
-        % nrEnvs % (nrEnvs * sizeof(Env)));
-    printMsg(v, format("  values allocated in environments: %1% (%2% bytes)")
-        % nrValuesInEnvs % (nrValuesInEnvs * sizeof(Value)));
+        % nrEnvs % (nrEnvs * sizeof(Env) + nrValuesInEnvs * sizeof(Value *)));
     printMsg(v, format("  list elements: %1% (%2% bytes)")
         % nrListElems % (nrListElems * sizeof(Value *)));
-    printMsg(v, format("  misc. values allocated: %1% (%2% bytes)")
+    printMsg(v, format("  values allocated: %1% (%2% bytes)")
         % nrValues % (nrValues * sizeof(Value)));
     printMsg(v, format("  attribute sets allocated: %1%") % nrAttrsets);
     printMsg(v, format("  right-biased unions: %1%") % nrOpUpdates);
-- 
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')

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')

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')

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')

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


From e11e6fb1c6709ca3f0e596a7b1fb988df2fbd9b1 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Thu, 28 Oct 2010 12:29:40 +0000
Subject: * Handle out of memory condition.

---
 src/libexpr/eval.cc             | 10 +++++-----
 src/libmain/Makefile.am         |  2 +-
 src/libmain/shared.cc           | 20 ++++++++++++++++++++
 src/nix-env/Makefile.am         |  3 +--
 src/nix-instantiate/Makefile.am |  3 +--
 5 files changed, 28 insertions(+), 10 deletions(-)

(limited to 'src/libexpr')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 919ebd4ba9b6..c36a679d350d 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -259,9 +259,8 @@ void mkString(Value & v, const string & s, const PathSet & context)
     mkString(v, s.c_str());
     if (!context.empty()) {
         unsigned int n = 0;
-        v.string.context = (const char * *)
-            GC_MALLOC((context.size() + 1) * sizeof(char *));
-        foreach (PathSet::const_iterator, i, context) 
+        v.string.context = NEW const char *[context.size() + 1];
+        foreach (PathSet::const_iterator, i, context)  
             v.string.context[n++] = GC_STRDUP(i->c_str());
         v.string.context[n] = 0;
     }
@@ -305,7 +304,7 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
 Value * EvalState::allocValue()
 {
     nrValues++;
-    return (Value *) GC_MALLOC(sizeof(Value));
+    return NEW Value;
 }
 
 
@@ -314,6 +313,7 @@ Env & EvalState::allocEnv(unsigned int size)
     nrEnvs++;
     nrValuesInEnvs += size;
     Env * env = (Env *) GC_MALLOC(sizeof(Env) + size * sizeof(Value *));
+    if (!env) throw std::bad_alloc();
 
     /* Clear the values because maybeThunk() expects this. */
     for (unsigned i = 0; i < size; ++i)
@@ -335,7 +335,7 @@ void EvalState::mkList(Value & v, unsigned int length)
 {
     v.type = tList;
     v.list.length = length;
-    v.list.elems = (Value * *) GC_MALLOC(length * sizeof(Value *));
+    v.list.elems = NEW Value *[length];
     nrListElems += length;
 }
 
diff --git a/src/libmain/Makefile.am b/src/libmain/Makefile.am
index a9ee6604255e..1a2146e0448f 100644
--- a/src/libmain/Makefile.am
+++ b/src/libmain/Makefile.am
@@ -2,7 +2,7 @@ pkglib_LTLIBRARIES = libmain.la
 
 libmain_la_SOURCES = shared.cc
 
-libmain_la_LIBADD = ../libstore/libstore.la
+libmain_la_LIBADD = ../libstore/libstore.la @boehmgc_lib@
 
 pkginclude_HEADERS = shared.hh
 
diff --git a/src/libmain/shared.cc b/src/libmain/shared.cc
index eddc4e64b3d7..440949bd2a0a 100644
--- a/src/libmain/shared.cc
+++ b/src/libmain/shared.cc
@@ -13,6 +13,10 @@
 #include <sys/stat.h>
 #include <unistd.h>
 
+#if HAVE_BOEHMGC
+#include <gc/gc.h>
+#endif
+
 
 namespace nix {
 
@@ -314,6 +318,14 @@ static void setuidInit()
 }
 
 
+/* Called when the Boehm GC runs out of memory. */
+static void * oomHandler(size_t requested)
+{
+    /* Convert this to a proper C++ exception. */
+    throw std::bad_alloc();
+}
+
+
 }
 
 
@@ -335,6 +347,14 @@ int main(int argc, char * * argv)
 
     std::ios::sync_with_stdio(false);
 
+#if HAVE_BOEHMGC
+    /* Initialise the Boehm garbage collector.  This isn't necessary
+       on most platforms, but for portability we do it anyway. */
+    GC_INIT();
+
+    GC_oom_fn = oomHandler;
+#endif
+
     try {
         try {
             initAndRun(argc, argv);
diff --git a/src/nix-env/Makefile.am b/src/nix-env/Makefile.am
index a876b3eb386d..7dfa7425a062 100644
--- a/src/nix-env/Makefile.am
+++ b/src/nix-env/Makefile.am
@@ -4,8 +4,7 @@ nix_env_SOURCES = nix-env.cc profiles.cc profiles.hh user-env.cc user-env.hh hel
 
 nix_env_LDADD = ../libmain/libmain.la ../libexpr/libexpr.la \
  ../libstore/libstore.la ../libutil/libutil.la \
- ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@ \
- @boehmgc_lib@
+ ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@
 
 nix-env.o: help.txt.hh
 
diff --git a/src/nix-instantiate/Makefile.am b/src/nix-instantiate/Makefile.am
index bc9792818c3c..a65907a8d40a 100644
--- a/src/nix-instantiate/Makefile.am
+++ b/src/nix-instantiate/Makefile.am
@@ -3,8 +3,7 @@ bin_PROGRAMS = nix-instantiate
 nix_instantiate_SOURCES = nix-instantiate.cc help.txt
 nix_instantiate_LDADD = ../libmain/libmain.la ../libexpr/libexpr.la \
  ../libstore/libstore.la ../libutil/libutil.la \
- ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@ \
- @boehmgc_lib@
+ ../boost/format/libformat.la @ADDITIONAL_NETWORK_LIBS@
 
 nix-instantiate.o: help.txt.hh
 
-- 
cgit 1.4.1


From 0c4828ea05798b9e070e233884739736115a830d Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <e.dolstra@tudelft.nl>
Date: Thu, 28 Oct 2010 12:50:01 +0000
Subject: * new(UseGC) is inexplicably slower than GC_MALLOC, so prefer the  
 latter.

---
 src/libexpr/eval.cc | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'src/libexpr')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index c36a679d350d..3ef17c36a287 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -259,7 +259,8 @@ void mkString(Value & v, const string & s, const PathSet & context)
     mkString(v, s.c_str());
     if (!context.empty()) {
         unsigned int n = 0;
-        v.string.context = NEW const char *[context.size() + 1];
+        v.string.context = (const char * *)
+            GC_MALLOC((context.size() + 1) * sizeof(char *));
         foreach (PathSet::const_iterator, i, context)  
             v.string.context[n++] = GC_STRDUP(i->c_str());
         v.string.context[n] = 0;
@@ -304,7 +305,7 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
 Value * EvalState::allocValue()
 {
     nrValues++;
-    return NEW Value;
+    return (Value *) GC_MALLOC(sizeof(Value));
 }
 
 
@@ -313,7 +314,6 @@ Env & EvalState::allocEnv(unsigned int size)
     nrEnvs++;
     nrValuesInEnvs += size;
     Env * env = (Env *) GC_MALLOC(sizeof(Env) + size * sizeof(Value *));
-    if (!env) throw std::bad_alloc();
 
     /* Clear the values because maybeThunk() expects this. */
     for (unsigned i = 0; i < size; ++i)
@@ -335,7 +335,7 @@ void EvalState::mkList(Value & v, unsigned int length)
 {
     v.type = tList;
     v.list.length = length;
-    v.list.elems = NEW Value *[length];
+    v.list.elems = (Value * *) GC_MALLOC(length * sizeof(Value *));
     nrListElems += length;
 }
 
-- 
cgit 1.4.1