From 41c45a9b319a5578e2731505ca3de2b9c50b4988 Mon Sep 17 00:00:00 2001 From: Eelco Dolstra 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/get-drvs.cc | 40 ++++++++++++++++++++-------------------- 1 file changed, 20 insertions(+), 20 deletions(-) (limited to 'src/libexpr/get-drvs.cc') 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); -- cgit 1.4.1 From 0b305c534f989dbc3645ff03e070b0e4665fdeb7 Mon Sep 17 00:00:00 2001 From: Eelco Dolstra 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/get-drvs.cc') diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc index 365b03c0bf60..49c08339ae55 100644 --- a/src/libexpr/attr-path.cc +++ b/src/libexpr/attr-path.cc @@ -49,7 +49,7 @@ void findAlongAttrPath(EvalState & state, const string & attrPath, Bindings::iterator a = v.attrs->find(state.symbols.create(attr)); if (a == v.attrs->end()) throw Error(format("attribute `%1%' in selection path `%2%' not found") % attr % curPath); - v = *a->second.value; + v = *a->value; } else if (apType == apIndex) { diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index d73f99a156cf..85394b768db6 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -13,7 +13,7 @@ #include #include -#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 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::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, gc_allocator > > Bindings; +typedef std::vector > BindingsBase; #else -typedef std::map Bindings; +typedef std::vector 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 SortedSymbols; SortedSymbols attrs; foreach (Bindings::iterator, i, *v.attrs) - attrs.insert(std::pair(i->first, i->first)); + attrs.insert(std::pair(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 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 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 e0b7fb8f2710ec3012afe6b9d2096f770429a389 Mon Sep 17 00:00:00 2001 From: Eelco Dolstra 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/get-drvs.cc') diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc index 6b393c07df50..c364aa9cb599 100644 --- a/src/libexpr/common-opts.cc +++ b/src/libexpr/common-opts.cc @@ -20,14 +20,17 @@ bool parseOptionArg(const string & arg, Strings::iterator & i, if (i == argsEnd) throw error; string value = *i++; + /* !!! check for duplicates! */ Value * v = state.allocValue(); - autoArgs[state.symbols.create(name)].value = v; + autoArgs.push_back(Attr(state.symbols.create(name), v)); if (arg == "--arg") state.mkThunk_(*v, parseExprFromString(state, value, absPath("."))); else mkString(*v, value); - + + autoArgs.sort(); // !!! inefficient + return true; } diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index 124cf6498f06..4aa8fc1e44b5 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -34,18 +34,16 @@ namespace nix { Bindings::iterator Bindings::find(const Symbol & name) { - iterator i = begin(); - for ( ; i != end() && i->name != name; ++i) ; - return i; + Attr key(name, 0); + iterator i = lower_bound(begin(), end(), key); + if (i != end() && i->name == name) return i; + return end(); } -Attr & Bindings::operator [] (const Symbol & name) +void Bindings::sort() { - iterator i = find(name); - if (i != end()) return *i; - push_back(Attr(name, 0)); - return back(); + std::sort(begin(), end()); } @@ -178,12 +176,12 @@ void EvalState::addPrimOp(const string & name, { Value * v = allocValue(); string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name; - Symbol sym = symbols.create(name); + Symbol sym = symbols.create(name2); v->type = tPrimOp; v->primOp = NEW PrimOp(primOp, arity, sym); - staticBaseEnv.vars[sym] = baseEnvDispl; + staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl; baseEnv.values[baseEnvDispl++] = v; - baseEnv.values[0]->attrs->push_back(Attr(symbols.create(name2), v)); + baseEnv.values[0]->attrs->push_back(Attr(sym, v)); } @@ -506,32 +504,38 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v) void ExprAttrs::eval(EvalState & state, Env & env, Value & v) { - state.mkAttrs(v); + state.mkAttrs(v); // !!! reserve size if (recursive) { /* Create a new environment that contains the attributes in this `rec'. */ - Env & env2(state.allocEnv(attrs.size() + inherited.size())); + Env & env2(state.allocEnv(attrs.size())); env2.up = &env; + AttrDefs::iterator overrides = attrs.find(state.sOverrides); + bool hasOverrides = overrides != attrs.end(); + + /* The recursive attributes are evaluated in the new + environment, while the inherited attributes are evaluated + in the original environment. */ unsigned int displ = 0; + foreach (AttrDefs::iterator, i, attrs) + if (i->second.inherited) { + /* !!! handle overrides? */ + Value * vAttr = state.lookupVar(&env, i->second.var); + env2.values[displ++] = vAttr; + v.attrs->push_back(Attr(i->first, vAttr, &i->second.pos)); + } else { + Value * vAttr; + if (hasOverrides) { + vAttr = state.allocValue(); + mkThunk(*vAttr, env2, i->second.e); + } else + vAttr = state.maybeThunk(env2, i->second.e); + env2.values[displ++] = vAttr; + v.attrs->push_back(Attr(i->first, vAttr, &i->second.pos)); + } - /* The recursive attributes are evaluated in the new - environment. */ - foreach (Attrs::iterator, i, attrs) { - Value * vAttr = state.maybeThunk(env2, i->second.first); - env2.values[displ++] = vAttr; - v.attrs->push_back(nix::Attr(i->first, vAttr, &i->second.second)); - } - - /* The inherited attributes, on the other hand, are - evaluated in the original environment. */ - foreach (list::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::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::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::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::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::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::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::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 Attr; - typedef std::pair Inherited; - typedef std::map Attrs; - Attrs attrs; - list inherited; - std::map attrNames; // used during parsing - std::map 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 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 & attrPath, unsigned int n = 0; foreach (vector::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(j->second.first); - if (!attrs2 || n == attrPath.size()) dupAttr(attrPath, pos, j->second.second); - attrs = attrs2; + if (!j->second.inherited) { + ExprAttrs * attrs2 = dynamic_cast(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::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::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(drvPath)); mkString(*state.allocAttr(v, state.sDrvPath), drvPath, singleton("=" + 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 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(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