diff options
37 files changed, 722 insertions, 444 deletions
diff --git a/Makefile.am b/Makefile.am index 2f39f90d6ce3..cb1a321dddf2 100644 --- a/Makefile.am +++ b/Makefile.am @@ -2,6 +2,8 @@ SUBDIRS = externals src scripts corepkgs doc misc tests EXTRA_DIST = substitute.mk nix.spec nix.spec.in bootstrap.sh \ nix.conf.example NEWS version +pkginclude_HEADERS = config.h + include ./substitute.mk nix.spec: nix.spec.in diff --git a/configure.ac b/configure.ac index 81c008a84de3..c2599a75f1ba 100644 --- a/configure.ac +++ b/configure.ac @@ -132,11 +132,18 @@ AC_LANG_POP(C++) AC_CHECK_HEADER([err.h], [], [bsddiff_compat_include="-Icompat-include"]) AC_SUBST([bsddiff_compat_include]) + # Check whether we have the personality() syscall, which allows us to # do i686-linux builds on x86_64-linux machines. AC_CHECK_HEADERS([sys/personality.h]) +# Check for tr1/unordered_set. +AC_LANG_PUSH(C++) +AC_CHECK_HEADERS([tr1/unordered_set], [], [], []) +AC_LANG_POP(C++) + + AC_DEFUN([NEED_PROG], [ AC_PATH_PROG($1, $2) @@ -255,6 +262,18 @@ AC_SUBST(sqlite_lib) AC_SUBST(sqlite_include) AC_SUBST(sqlite_bin) +# Whether to use the Boehm garbage collector. +AC_ARG_ENABLE(gc, AC_HELP_STRING([--enable-gc], + [enable garbage collection in the Nix expression evaluator (requires Boehm GC)]), + gc=$enableval, gc=) +if test -n "$gc"; then + PKG_CHECK_MODULES([BDW_GC], [bdw-gc]) + boehmgc_lib="-L$boehmgc/lib -lgc" + CXXFLAGS="$BDW_GC_CFLAGS $CXXFLAGS" + AC_DEFINE(HAVE_BOEHMGC, 1, [Whether to use the Boehm garbage collector.]) +fi +AC_SUBST(boehmgc_lib) + AC_ARG_ENABLE(init-state, AC_HELP_STRING([--disable-init-state], [do not initialise DB etc. in `make install']), diff --git a/doc/manual/env-common.xml b/doc/manual/env-common.xml index d67ef714d0f9..99acc5949044 100644 --- a/doc/manual/env-common.xml +++ b/doc/manual/env-common.xml @@ -271,6 +271,17 @@ $ mount -o bind /mnt/otherdisk/nix /nix</screen> </varlistentry> + +<varlistentry><term><envar>GC_INITIAL_HEAP_SIZE</envar></term> + + <listitem><para>If Nix has been configured to use the Boehm garbage + collector, this variable sets the initial size of the heap in bytes. + It defaults to 384 MiB. Setting it to a low value reduces memory + consumption, but will increase runtime due to the overhead of + garbage collection.</para></listitem> + +</varlistentry> + </variablelist> diff --git a/doc/manual/installation.xml b/doc/manual/installation.xml index bc5e21f0d39a..87a6c446a2d5 100644 --- a/doc/manual/installation.xml +++ b/doc/manual/installation.xml @@ -105,6 +105,13 @@ this packages. Alternatively, if you already have it installed, you can use <command>configure</command>'s <option>--with-bzip2</option> options to point to their respective locations.</para> +<para>Nix can optionally use the <link +xlink:href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Boehm +garbage collector</link> to reduce the evaluator’s memory consumption. +To enable it, install <literal>pkgconfig</literal> and the Boehm +garbage collector, and pass the flag <option>--enable-gc</option> to +<command>configure</command>.</para> + </section> diff --git a/doc/manual/introduction.xml b/doc/manual/introduction.xml index 0cf57fd855ff..bdd71e5c3e7b 100644 --- a/doc/manual/introduction.xml +++ b/doc/manual/introduction.xml @@ -113,7 +113,7 @@ $ nix-env --rollback <simplesect><title>Garbage collection</title> -<para>When you install a package like this… +<para>When you uninstall a package like this… <screen> $ nix-env --uninstall firefox diff --git a/doc/manual/release-notes.xml b/doc/manual/release-notes.xml index 5b1c30bf8292..1e579a37b017 100644 --- a/doc/manual/release-notes.xml +++ b/doc/manual/release-notes.xml @@ -8,6 +8,27 @@ <!--==================================================================--> +<section xml:id="ssec-relnotes-1.0"><title>Release 1.0 (TBA)</title> + +<para>This release has the following improvements:</para> + +<itemizedlist> + + <listitem> + <para>Nix can now optionally use the Boehm garbage collector. + This significantly reduces the Nix evaluator’s memory footprint, + especially when evaluating large NixOS system configurations. It + can be enabled using the <option>--enable-gc</option> configure + option.</para> + </listitem> + +</itemizedlist> + +</section> + + +<!--==================================================================--> + <section xml:id="ssec-relnotes-0.16"><title>Release 0.16 (August 17, 2010)</title> <para>This release has the following improvements:</para> diff --git a/release.nix b/release.nix index 589d0f035e5d..1fc9405bdb28 100644 --- a/release.nix +++ b/release.nix @@ -18,8 +18,8 @@ let inherit officialRelease; buildInputs = - [ curl bison flex2533 perl libxml2 libxslt w3m bzip2 - tetex dblatex nukeReferences + [ curl bison24 flex2535 perl libxml2 libxslt w3m bzip2 + tetex dblatex nukeReferences pkgconfig ]; configureFlags = '' @@ -70,11 +70,12 @@ let name = "nix"; src = tarball; - buildInputs = [ curl perl bzip2 openssl ]; + buildInputs = [ curl perl bzip2 openssl pkgconfig boehmgc ]; configureFlags = '' --disable-init-state --with-bzip2=${bzip2} --with-sqlite=${sqlite} + --enable-gc ''; }; 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..49c08339ae55 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->value; } else if (apType == apIndex) { diff --git a/src/libexpr/attr-path.hh b/src/libexpr/attr-path.hh index 33587e5edee1..b106da5ef817 100644 --- a/src/libexpr/attr-path.hh +++ b/src/libexpr/attr-path.hh @@ -1,17 +1,17 @@ #ifndef __ATTR_PATH_H #define __ATTR_PATH_H +#include "eval.hh" + #include <string> #include <map> -#include "eval.hh" - 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..c364aa9cb599 100644 --- a/src/libexpr/common-opts.cc +++ b/src/libexpr/common-opts.cc @@ -20,13 +20,17 @@ bool parseOptionArg(const string & arg, Strings::iterator & i, if (i == argsEnd) throw error; string value = *i++; - Value & v(autoArgs[state.symbols.create(name)].value); + /* !!! check for duplicates! */ + Value * v = state.allocValue(); + autoArgs.push_back(Attr(state.symbols.create(name), 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); + + autoArgs.sort(); // !!! inefficient + return true; } diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index e55f28822b6a..3ef17c36a287 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -8,12 +8,43 @@ #include <cstring> +#if HAVE_BOEHMGC + +#include <gc/gc.h> +#include <gc/gc_cpp.h> + +#define NEW new (UseGC) + +#else + +#define GC_STRDUP strdup +#define GC_MALLOC malloc + +#define NEW new + +#endif + #define LocalNoInline(f) static f __attribute__((noinline)); f #define LocalNoInlineNoReturn(f) static f __attribute__((noinline, noreturn)); f namespace nix { + + +Bindings::iterator Bindings::find(const Symbol & name) +{ + Attr key(name, 0); + iterator i = lower_bound(begin(), end(), key); + if (i != end() && i->name == name) return i; + return end(); +} + + +void Bindings::sort() +{ + std::sort(begin(), end()); +} std::ostream & operator << (std::ostream & str, const Value & v) @@ -46,7 +77,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 << "}"; @@ -60,7 +91,6 @@ std::ostream & operator << (std::ostream & str, const Value & v) break; case tThunk: case tApp: - case tCopy: str << "<CODE>"; break; case tLambda: @@ -92,7 +122,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"; @@ -116,6 +145,7 @@ EvalState::EvalState() { nrEnvs = nrValuesInEnvs = nrValues = nrListElems = 0; nrEvaluated = recursionDepth = maxRecursionDepth = 0; + nrAttrsets = nrOpUpdates = nrOpUpdateValuesCopied = 0; deepestStack = (char *) -1; createBaseEnv(); @@ -132,25 +162,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; + baseEnv.values[baseEnvDispl++] = v2; string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name; - (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v; + baseEnv.values[0]->attrs->push_back(Attr(symbols.create(name2), v2)); } void EvalState::addPrimOp(const string & name, - unsigned int arity, PrimOp primOp) + unsigned int arity, PrimOpFun 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 = strdup(name2.c_str()); + Symbol sym = symbols.create(name2); + v->type = tPrimOp; + v->primOp = NEW PrimOp(primOp, arity, sym); staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl; baseEnv.values[baseEnvDispl++] = v; - (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v; + baseEnv.values[0]->attrs->push_back(Attr(sym, v)); } @@ -218,7 +249,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,18 +259,28 @@ 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]; - foreach (PathSet::const_iterator, i, context) - v.string.context[n++] = strdup(i->c_str()); + 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; } } +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); v.type = tPath; - v.path = strdup(s); + v.path = GC_STRDUP(s); } @@ -249,22 +290,22 @@ 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()) - return &j->second.value; + Bindings::iterator j = env->values[0]->attrs->find(var.name); + if (j != env->values[0]->attrs->end()) + return j->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]; } -Value * EvalState::allocValues(unsigned int count) +Value * EvalState::allocValue() { - nrValues += count; - return new Value[count]; // !!! check destructor + nrValues++; + return (Value *) GC_MALLOC(sizeof(Value)); } @@ -272,24 +313,51 @@ 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 *)); + + /* Clear the values because maybeThunk() expects this. */ + for (unsigned i = 0; i < size; ++i) + env->values[i] = 0; + return *env; } +Value * EvalState::allocAttr(Value & vAttrs, const Symbol & name) +{ + Value * v = allocValue(); + vAttrs.attrs->push_back(Attr(name, v)); + return v; +} + + 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; } -void EvalState::mkAttrs(Value & v) +void EvalState::mkAttrs(Value & v, unsigned int expected) { + clearValue(v); v.type = tAttrs; - v.attrs = new Bindings; + v.attrs = NEW Bindings; + v.attrs->reserve(expected); + nrAttrsets++; +} + + +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++; } @@ -299,14 +367,28 @@ void EvalState::mkThunk_(Value & v, Expr * expr) } -void EvalState::cloneAttrs(Value & src, Value & dst) +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) { - 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; + 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; } @@ -404,7 +486,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); } @@ -416,35 +498,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, attrs.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) { - nix::Attr & a = (*v.attrs)[i->first]; - mkThunk(a.value, env2, i->second.first); - mkCopy(env2.values[displ++], a.value); - a.pos = &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); - mkCopy(a.value, *v2); - mkCopy(env2.values[displ++], *v2); - a.pos = &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 @@ -453,28 +538,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->second.value); - foreach (Bindings::iterator, i, *overrides->second.value.attrs) { - nix::Attr & a = (*v.attrs)[i->first]; - mkCopy(a.value, i->second.value); + 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]; - 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.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)); } } @@ -483,20 +567,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) - 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)); + 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); } @@ -505,11 +587,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) + v.list.elems[n] = state.maybeThunk(env, elems[n]); } @@ -521,21 +600,26 @@ 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); 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; } @@ -559,24 +643,27 @@ 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); + state.callFunction(vFun, *state.maybeThunk(env, e2), 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]; @@ -587,19 +674,16 @@ 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 { - 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.argsLeft = argsLeft - 1; + v.primOpApp.left = allocValue(); + *v.primOpApp.left = fun; + v.primOpApp.right = &arg; } return; } @@ -617,13 +701,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 @@ -633,11 +717,11 @@ 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++] = maybeThunk(env2, i->def); } else { attrsUsed++; - mkCopy(env2.values[displ++], j->second.value); + env2.values[displ++] = j->value; } } @@ -645,7 +729,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); } @@ -658,7 +742,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); @@ -668,16 +752,18 @@ void EvalState::autoCallFunction(const 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::const_iterator j = args.find(i->name); + Bindings::iterator j = args.find(i->name); if (j != args.end()) - (*actualArgs.attrs)[i->name] = j->second; + 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); } @@ -688,7 +774,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); } @@ -754,16 +841,34 @@ 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; } - state.cloneAttrs(v1, 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 + order. */ + Bindings::iterator i = v1.attrs->begin(); + Bindings::iterator j = v2.attrs->begin(); - foreach (Bindings::iterator, i, *v2.attrs) { - Attr & a = (*v.attrs)[i->first]; - mkCopy(a.value, i->second.value); - a.pos = i->second.pos; + 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(); } @@ -826,10 +931,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) @@ -843,7 +944,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) { @@ -934,7 +1035,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"; } @@ -978,7 +1079,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) { @@ -1064,9 +1165,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->name != j->name || !eqValues(*i->value, *j->value)) return false; return true; } @@ -1089,20 +1190,26 @@ 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); 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); + 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 c7533479aa67..7453ac189197 100644 --- a/src/libexpr/eval.hh +++ b/src/libexpr/eval.hh @@ -1,13 +1,15 @@ #ifndef __EVAL_H #define __EVAL_H -#include <map> - #include "nixexpr.hh" #include "symbol-table.hh" #include "hash.hh" -typedef union _ATermList * ATermList; +#include <map> + +#if HAVE_BOEHMGC +#include <gc/gc_allocator.h> +#endif namespace nix { @@ -18,7 +20,22 @@ struct Env; struct Value; struct Attr; -typedef std::map<Symbol, Attr> Bindings; + +/* 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::vector<Attr, gc_allocator<Attr> > BindingsBase; +#else +typedef std::vector<Attr> BindingsBase; +#endif + + +class Bindings : public BindingsBase +{ +public: + iterator find(const Symbol & name); + void sort(); +}; typedef enum { @@ -32,14 +49,23 @@ typedef enum { tThunk, tApp, tLambda, - tCopy, tBlackhole, tPrimOp, tPrimOpApp, } 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 @@ -92,15 +118,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; }; }; @@ -110,20 +130,36 @@ struct Env { Env * up; unsigned int prevWith; // nr of levels up to next `with' environment - Value values[0]; + Value * values[0]; }; struct Attr { - Value value; + Symbol name; + Value * value; Pos * pos; + 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; + } }; +/* 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; } @@ -131,26 +167,12 @@ static inline void mkInt(Value & v, int n) static inline void mkBool(Value & v, bool b) { + clearValue(v); v.type = tBool; v.boolean = 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 mkCopy(Value & v, Value & src) -{ - v.type = tCopy; - v.val = &src; -} - - static inline void mkApp(Value & v, Value & left, Value & right) { v.type = tApp; @@ -270,7 +292,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); @@ -288,18 +310,20 @@ 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 * allocValues(unsigned int count); + Value * allocValue(); Env & allocEnv(unsigned int size); + 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); - - void cloneAttrs(Value & src, Value & dst); + Value * maybeThunk(Env & env, Expr * expr); + /* Print statistics. */ void printStats(); @@ -310,11 +334,15 @@ 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 */ friend class RecursionCounter; + friend class ExprOpUpdate; }; diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc index 82a92416bed6..a28a705d22d1 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); - 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->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; @@ -163,12 +163,12 @@ 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); 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)) { @@ -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); } } @@ -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 ca7d980027e4..7c014b7e41f2 100644 --- a/src/libexpr/get-drvs.hh +++ b/src/libexpr/get-drvs.hh @@ -1,13 +1,13 @@ #ifndef __GET_DRVS_H #define __GET_DRVS_H +#include "eval.hh" + #include <string> #include <map> #include <boost/shared_ptr.hpp> -#include "eval.hh" - namespace nix { @@ -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/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.cc b/src/libexpr/nixexpr.cc index 898fdb609417..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) - newEnv.vars[i->first] = displ++; - - foreach (list<Inherited>::iterator, i, inherited) { - 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 b1043a32684e..8f976f1de8f9 100644 --- a/src/libexpr/nixexpr.hh +++ b/src/libexpr/nixexpr.hh @@ -1,10 +1,10 @@ #ifndef __NIXEXPR_H #define __NIXEXPR_H -#include <map> - #include "symbol-table.hh" +#include <map> + namespace nix { @@ -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 }; @@ -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,12 +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 + 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 7236bab19ce5..c6d29b6ca8bd 100644 --- a/src/libexpr/parser.y +++ b/src/libexpr/parser.y @@ -7,48 +7,59 @@ %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 <stdio.h> -#include <stdlib.h> -#include <string.h> - #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 +#include <stdio.h> +#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) { @@ -82,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; } } @@ -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'. */ @@ -375,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; } @@ -480,8 +486,6 @@ Expr * parseExprFromFile(EvalState & state, Path path) } /* If `path' refers to a directory, append `/default.nix'. */ - if (stat(path.c_str(), &st)) - throw SysError(format("getting status of `%1%'") % path); if (S_ISDIR(st.st_mode)) path = canonPath(path + "/default.nix"); diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc index 68f66acc74ed..a4812de06519 100644 --- a/src/libexpr/primops.cc +++ b/src/libexpr/primops.cc @@ -1,5 +1,5 @@ -#include "misc.hh" #include "eval.hh" +#include "misc.hh" #include "globals.hh" #include "store-api.hh" #include "util.hh" @@ -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->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 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->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. */ @@ -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; } @@ -210,15 +206,16 @@ 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)[state.symbols.create("value")].value = *args[0]; - mkBool((*v.attrs)[state.symbols.create("success")].value, true); + v.attrs->push_back(Attr(state.symbols.create("value"), args[0])); + mkBool(*state.allocAttr(v, state.symbols.create("success")), true); } 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); } + v.attrs->sort(); } @@ -324,9 +321,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; @@ -341,7 +338,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 { @@ -349,9 +346,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); } } @@ -359,11 +356,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") { @@ -375,7 +372,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; @@ -487,9 +484,10 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v) state.drvHashes[drvPath] = hashDerivationModulo(state, drv); /* !!! 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)); + 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(); } @@ -689,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); + names.insert(i->name); 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); } @@ -713,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; } @@ -740,11 +735,20 @@ 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. Note that we don't need + to sort v.attrs because it's a subset of an already sorted + vector. */ + 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); } } @@ -757,7 +761,9 @@ 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; for (unsigned int i = 0; i < args[0]->list.length; ++i) { Value & v2(*args[0]->list.elems[i]); @@ -766,16 +772,21 @@ 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); - 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; + 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(); } @@ -787,15 +798,12 @@ 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->first); - if (j != args[1]->attrs->end()) { - Attr & a = (*v.attrs)[j->first]; - mkCopy(a.value, j->second.value); - a.pos = j->second.pos; - } + Bindings::iterator j = args[1]->attrs->find(i->name); + if (j != args[1]->attrs->end()) + v.attrs->push_back(*j); } } @@ -819,12 +827,16 @@ 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) - mkBool((*v.attrs)[i->name].value, i->def); + // !!! should optimise booleans (allocate only once) + mkBool(*state.allocAttr(v, i->name), i->def); + v.attrs->sort(); } @@ -872,12 +884,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]); } @@ -1006,9 +1016,10 @@ 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); + 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(); } @@ -1033,7 +1044,7 @@ void EvalState::createBaseEnv() Value v; /* `builtins' must be first! */ - mkAttrs(v); + mkAttrs(v, 128); addConstant("builtins", v); mkBool(v, true); @@ -1072,7 +1083,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 @@ -1121,7 +1132,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/symbol-table.hh b/src/libexpr/symbol-table.hh index 424c2353899e..976117a20a46 100644 --- a/src/libexpr/symbol-table.hh +++ b/src/libexpr/symbol-table.hh @@ -1,8 +1,13 @@ #ifndef __SYMBOL_TABLE_H #define __SYMBOL_TABLE_H +#include "config.h" + #include <map> + +#if HAVE_TR1_UNORDERED_SET #include <tr1/unordered_set> +#endif #include "types.hh" @@ -23,6 +28,8 @@ private: friend class SymbolTable; public: + Symbol() : s(0) { }; + bool operator == (const Symbol & s2) const { return s == s2.s; @@ -60,7 +67,11 @@ inline std::ostream & operator << (std::ostream & str, const Symbol & sym) class SymbolTable { private: +#if HAVE_TR1_UNORDERED_SET typedef std::tr1::unordered_set<string> Symbols; +#else + typedef std::set<string> Symbols; +#endif Symbols symbols; public: diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc index 8955a8a33931..bc63f776269c 100644 --- a/src/libexpr/value-to-xml.cc +++ b/src/libexpr/value-to-xml.cc @@ -34,10 +34,10 @@ 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)]); + Attr & a(*attrs.find(state.symbols.create(*i))); XMLAttrs xmlAttrs; xmlAttrs["name"] = *i; @@ -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->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); diff --git a/src/libexpr/value-to-xml.hh b/src/libexpr/value-to-xml.hh index 0c6de3a8b2e6..3ebc989ffa26 100644 --- a/src/libexpr/value-to-xml.hh +++ b/src/libexpr/value-to-xml.hh @@ -1,12 +1,12 @@ #ifndef __VALUE_TO_XML_H #define __VALUE_TO_XML_H -#include <string> -#include <map> - #include "nixexpr.hh" #include "eval.hh" +#include <string> +#include <map> + namespace nix { void printValueAsXML(EvalState & state, bool strict, bool location, 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 f58def403e82..d7879f035607 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 { @@ -316,6 +320,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(); +} + + } @@ -337,6 +349,26 @@ 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; + + /* Set the initial heap size to something fairly big (384 MiB) so + that in most cases we don't need to garbage collect at all. + (Collection has a fairly significant overhead, some.) The heap + size can be overriden through libgc's GC_INITIAL_HEAP_SIZE + environment variable. We should probably also provide a + nix.conf setting for this. Note that GC_expand_hp() causes a + lot of virtual, but not physical (resident) memory to be + allocated. This might be a problem on systems that don't + overcommit. */ + if (!getenv("GC_INITIAL_HEAP_SIZE")) + GC_expand_hp(384 * 1024 * 1024); +#endif + try { try { initAndRun(argc, argv); diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh index 3b81bfa39438..082a9edc44c1 100644 --- a/src/libstore/store-api.hh +++ b/src/libstore/store-api.hh @@ -1,14 +1,14 @@ #ifndef __STOREAPI_H #define __STOREAPI_H +#include "hash.hh" +#include "serialise.hh" + #include <string> #include <map> #include <boost/shared_ptr.hpp> -#include "hash.hh" -#include "serialise.hh" - namespace nix { diff --git a/src/libutil/types.hh b/src/libutil/types.hh index 86801342fefb..854a0f689a14 100644 --- a/src/libutil/types.hh +++ b/src/libutil/types.hh @@ -1,6 +1,8 @@ #ifndef __TYPES_H #define __TYPES_H +#include "config.h" + #include <string> #include <list> #include <set> diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc index 47dab0457ab9..bfcc25872715 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,14 +154,14 @@ 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; } 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..865d24e2f919 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); @@ -58,23 +59,24 @@ 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); + state.mkAttrs(v, 8); - 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)); - - state.mkAttrs((*v.attrs)[state.sMeta].value); - + mkString(*state.allocAttr(v, state.sDrvPath), i->queryDrvPath(state)); + + Value & vMeta = *state.allocAttr(v, state.sMeta); + state.mkAttrs(vMeta, 16); + 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(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; @@ -82,7 +84,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; @@ -91,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)); @@ -113,11 +118,12 @@ 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); - mkString((*args.attrs)[state.sSystem].value, thisSystem); - mkString((*args.attrs)[state.symbols.create("manifest")].value, + state.mkAttrs(args, 3); + 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/src/nix-hash/nix-hash.cc b/src/nix-hash/nix-hash.cc index a70f59e0c2d0..8a66554033b3 100644 --- a/src/nix-hash/nix-hash.cc +++ b/src/nix-hash/nix-hash.cc @@ -1,9 +1,9 @@ -#include <iostream> - #include "hash.hh" #include "shared.hh" #include "help.txt.hh" +#include <iostream> + using namespace nix; diff --git a/src/nix-instantiate/nix-instantiate.cc b/src/nix-instantiate/nix-instantiate.cc index 38c62880b88f..3d3b643cfd6e 100644 --- a/src/nix-instantiate/nix-instantiate.cc +++ b/src/nix-instantiate/nix-instantiate.cc @@ -1,6 +1,3 @@ -#include <map> -#include <iostream> - #include "globals.hh" #include "shared.hh" #include "eval.hh" @@ -13,6 +10,9 @@ #include "common-opts.hh" #include "help.txt.hh" +#include <map> +#include <iostream> + using namespace nix; @@ -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) diff --git a/src/nix-store/nix-store.cc b/src/nix-store/nix-store.cc index b6ece30ce0b8..695eb10dcec1 100644 --- a/src/nix-store/nix-store.cc +++ b/src/nix-store/nix-store.cc @@ -1,6 +1,3 @@ -#include <iostream> -#include <algorithm> - #include "globals.hh" #include "misc.hh" #include "archive.hh" @@ -11,6 +8,9 @@ #include "util.hh" #include "help.txt.hh" +#include <iostream> +#include <algorithm> + using namespace nix; using std::cin; diff --git a/substitute.mk b/substitute.mk index e99b1c615cf9..d83399cfde78 100644 --- a/substitute.mk +++ b/substitute.mk @@ -26,6 +26,6 @@ -e "s^@xsltproc\@^$(xsltproc)^g" \ -e "s^@sqlite_bin\@^$(sqlite_bin)^g" \ -e "s^@version\@^$(VERSION)^g" \ - -e "s^@testPath\@^$(coreutils):$$(dirname $$(type -P expr))^g" \ + -e "s^@testPath\@^$(coreutils):$$(dirname $$(type -p expr))^g" \ < $< > $@ || rm $@ if test -x $<; then chmod +x $@; fi diff --git a/tests/lang/eval-okay-listtoattrs.exp b/tests/lang/eval-okay-listtoattrs.exp index 11d29b588ac1..74abef7bc6ed 100644 --- a/tests/lang/eval-okay-listtoattrs.exp +++ b/tests/lang/eval-okay-listtoattrs.exp @@ -1 +1 @@ -"AA" +"AAbar" diff --git a/tests/lang/eval-okay-listtoattrs.nix b/tests/lang/eval-okay-listtoattrs.nix index d5cd726b0c64..4186e029b538 100644 --- a/tests/lang/eval-okay-listtoattrs.nix +++ b/tests/lang/eval-okay-listtoattrs.nix @@ -7,4 +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")) ]; -in concat (map (x: x.a) r.result) + x = builtins.listToAttrs [ (asi "foo" "bar") (asi "foo" "bla") ]; +in concat (map (x: x.a) r.result) + x.foo diff --git a/tests/lang/eval-okay-overrides.exp b/tests/lang/eval-okay-overrides.exp new file mode 100644 index 000000000000..0cfbf08886fc --- /dev/null +++ b/tests/lang/eval-okay-overrides.exp @@ -0,0 +1 @@ +2 diff --git a/tests/lang/eval-okay-overrides.nix b/tests/lang/eval-okay-overrides.nix new file mode 100644 index 000000000000..358742b36e22 --- /dev/null +++ b/tests/lang/eval-okay-overrides.nix @@ -0,0 +1,9 @@ +let + + overrides = { a = 2; }; + +in (rec { + __overrides = overrides; + x = a; + a = 1; +}).x |