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/nix-env/user-env.cc | 23 ++++++++++++----------- 1 file changed, 12 insertions(+), 11 deletions(-) (limited to 'src/nix-env/user-env.cc') diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc index 0a619f698f98..07c94fe4d49a 100644 --- a/src/nix-env/user-env.cc +++ b/src/nix-env/user-env.cc @@ -25,7 +25,8 @@ DrvInfos queryInstalled(EvalState & state, const Path & userEnv) if (pathExists(manifestFile)) { Value v; state.eval(parseExprFromFile(state, manifestFile), v); - getDerivations(state, v, "", Bindings(), elems); + Bindings bindings; + getDerivations(state, v, "", bindings, elems); } else if (pathExists(oldManifestFile)) readLegacyManifest(oldManifestFile, elems); @@ -62,19 +63,19 @@ bool createUserEnv(EvalState & state, DrvInfos & elems, manifest.list.elems[n++] = &v; state.mkAttrs(v); - mkString((*v.attrs)[state.sType].value, "derivation"); - mkString((*v.attrs)[state.sName].value, i->name); - mkString((*v.attrs)[state.sSystem].value, i->system); - mkString((*v.attrs)[state.sOutPath].value, i->queryOutPath(state)); + mkString(*state.allocAttr(v, state.sType), "derivation"); + mkString(*state.allocAttr(v, state.sName), i->name); + mkString(*state.allocAttr(v, state.sSystem), i->system); + mkString(*state.allocAttr(v, state.sOutPath), i->queryOutPath(state)); if (drvPath != "") - mkString((*v.attrs)[state.sDrvPath].value, i->queryDrvPath(state)); + mkString(*state.allocAttr(v, state.sDrvPath), i->queryDrvPath(state)); - state.mkAttrs((*v.attrs)[state.sMeta].value); + state.mkAttrs(*state.allocAttr(v, state.sMeta)); MetaInfo meta = i->queryMetaInfo(state); foreach (MetaInfo::const_iterator, j, meta) { - Value & v2((*(*v.attrs)[state.sMeta].value.attrs)[state.symbols.create(j->first)].value); + Value & v2(*state.allocAttr(*(*v.attrs)[state.sMeta].value, state.symbols.create(j->first))); switch (j->second.type) { case MetaValue::tpInt: mkInt(v2, j->second.intValue); break; case MetaValue::tpString: mkString(v2, j->second.stringValue); break; @@ -114,10 +115,10 @@ bool createUserEnv(EvalState & state, DrvInfos & elems, builder with the manifest as argument. */ Value args, topLevel; state.mkAttrs(args); - mkString((*args.attrs)[state.sSystem].value, thisSystem); - mkString((*args.attrs)[state.symbols.create("manifest")].value, + mkString(*state.allocAttr(args, state.sSystem), thisSystem); + mkString(*state.allocAttr(args, state.symbols.create("manifest")), manifestFile, singleton(manifestFile)); - (*args.attrs)[state.symbols.create("derivations")].value = manifest; + (*args.attrs)[state.symbols.create("derivations")].value = &manifest; mkApp(topLevel, envBuilder, args); /* Evaluate it. */ -- cgit 1.4.1 From 3f66cfb96b6f4bbddc8bf3b15e364fd522e028bc Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Sat, 23 Oct 2010 18:18:07 +0000 Subject: * Remove allocValues(). --- src/libexpr/eval.cc | 22 +++++----------------- src/libexpr/eval.hh | 1 - src/libexpr/primops.cc | 23 +++++++---------------- src/nix-env/user-env.cc | 4 ++-- 4 files changed, 14 insertions(+), 36 deletions(-) (limited to 'src/nix-env/user-env.cc') diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index 3f2371d7957a..faf18cb7f471 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -282,13 +282,6 @@ Value * EvalState::allocValue() } -Value * EvalState::allocValues(unsigned int count) -{ - nrValues += count; - return (Value *) GC_MALLOC(count * sizeof(Value)); -} - - Env & EvalState::allocEnv(unsigned int size) { nrEnvs++; @@ -542,11 +535,8 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v) void ExprList::eval(EvalState & state, Env & env, Value & v) { state.mkList(v, elems.size()); - Value * vs = state.allocValues(v.list.length); - for (unsigned int n = 0; n < v.list.length; ++n) { - v.list.elems[n] = &vs[n]; - mkThunk(vs[n], env, elems[n]); - } + for (unsigned int n = 0; n < v.list.length; ++n) + mkThunk(*(v.list.elems[n] = state.allocValue()), env, elems[n]); } @@ -630,12 +620,10 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v) throw; } } else { - Value * v2 = allocValues(2); - v2[0] = fun; - v2[1] = arg; v.type = tPrimOpApp; - v.primOpApp.left = &v2[0]; - v.primOpApp.right = &v2[1]; + v.primOpApp.left = allocValue(); + *v.primOpApp.left = fun; + v.primOpApp.right = &arg; v.primOpApp.argsLeft = argsLeft - 1; } return; diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh index b6ec927f01fa..5f5966930f0e 100644 --- a/src/libexpr/eval.hh +++ b/src/libexpr/eval.hh @@ -290,7 +290,6 @@ public: /* Allocation primitives. */ Value * allocValue(); - Value * allocValues(unsigned int count); Env & allocEnv(unsigned int size); Value * allocAttr(Value & vAttrs, const Symbol & name); diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc index c7709ca9eb36..01cbf7a7c21a 100644 --- a/src/libexpr/primops.cc +++ b/src/libexpr/primops.cc @@ -167,13 +167,9 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v) /* Create the result list. */ state.mkList(v, res.size()); - Value * vs = state.allocValues(res.size()); - unsigned int n = 0; - foreach (list::iterator, i, res) { - v.list.elems[n] = &vs[n]; - vs[n++] = *i; - } + foreach (list::iterator, i, res) + *(v.list.elems[n++] = state.allocValue()) = *i; } @@ -691,17 +687,14 @@ static void prim_attrNames(EvalState & state, Value * * args, Value & v) state.forceAttrs(*args[0]); state.mkList(v, args[0]->attrs->size()); - Value * vs = state.allocValues(v.list.length); StringSet names; foreach (Bindings::iterator, i, *args[0]->attrs) names.insert(i->first); unsigned int n = 0; - foreach (StringSet::iterator, i, names) { - v.list.elems[n] = &vs[n]; - mkString(vs[n++], *i); - } + foreach (StringSet::iterator, i, names) + mkString(*(v.list.elems[n++] = state.allocValue()), *i); } @@ -870,12 +863,10 @@ static void prim_map(EvalState & state, Value * * args, Value & v) state.forceList(*args[1]); state.mkList(v, args[1]->list.length); - Value * vs = state.allocValues(v.list.length); - for (unsigned int n = 0; n < v.list.length; ++n) { - v.list.elems[n] = &vs[n]; - mkApp(vs[n], *args[0], *args[1]->list.elems[n]); - } + for (unsigned int n = 0; n < v.list.length; ++n) + mkApp(*(v.list.elems[n] = state.allocValue()), + *args[0], *args[1]->list.elems[n]); } diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc index 07c94fe4d49a..34e00b7c2e61 100644 --- a/src/nix-env/user-env.cc +++ b/src/nix-env/user-env.cc @@ -59,7 +59,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems, the meta attributes. */ Path drvPath = keepDerivations ? i->queryDrvPath(state) : ""; - Value & v(*state.allocValues(1)); + Value & v(*state.allocValue()); manifest.list.elems[n++] = &v; state.mkAttrs(v); @@ -83,7 +83,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems, state.mkList(v2, j->second.stringValues.size()); unsigned int m = 0; foreach (Strings::const_iterator, k, j->second.stringValues) { - v2.list.elems[m] = state.allocValues(1); + v2.list.elems[m] = state.allocValue(); mkString(*v2.list.elems[m++], *k); } break; -- cgit 1.4.1 From 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/nix-env/user-env.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 From 43535499f38acc04367eeb4dd0d9938e9f8666f8 Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Sun, 24 Oct 2010 20:09:37 +0000 Subject: * When allocating an attribute set, reserve enough space for all elements. This prevents the vector from having to resize itself. --- src/libexpr/eval.cc | 16 +++++----------- src/libexpr/eval.hh | 4 +--- src/libexpr/primops.cc | 23 ++++++++++++----------- src/nix-env/user-env.cc | 6 +++--- 4 files changed, 21 insertions(+), 28 deletions(-) (limited to 'src/nix-env/user-env.cc') diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index 4aa8fc1e44b5..919ebd4ba9b6 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -340,11 +340,12 @@ void EvalState::mkList(Value & v, unsigned int length) } -void EvalState::mkAttrs(Value & v) +void EvalState::mkAttrs(Value & v, unsigned int expected) { clearValue(v); v.type = tAttrs; v.attrs = NEW Bindings; + v.attrs->reserve(expected); nrAttrsets++; } @@ -391,13 +392,6 @@ Value * EvalState::maybeThunk(Env & env, Expr * expr) } -void EvalState::cloneAttrs(Value & src, Value & dst) -{ - mkAttrs(dst); - *dst.attrs = *src.attrs; -} - - void EvalState::evalFile(const Path & path, Value & v) { startNest(nest, lvlTalkative, format("evaluating file `%1%'") % path); @@ -504,7 +498,7 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v) void ExprAttrs::eval(EvalState & state, Env & env, Value & v) { - state.mkAttrs(v); // !!! reserve size + state.mkAttrs(v, attrs.size()); if (recursive) { /* Create a new environment that contains the attributes in @@ -758,7 +752,7 @@ void EvalState::autoCallFunction(Bindings & args, Value & fun, Value & res) } Value actualArgs; - mkAttrs(actualArgs); + mkAttrs(actualArgs, fun.lambda.fun->formals->formals.size()); foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) { Bindings::iterator j = args.find(i->name); @@ -852,7 +846,7 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v) if (v1.attrs->size() == 0) { v = v2; return; } if (v2.attrs->size() == 0) { v = v1; return; } - state.mkAttrs(v); + state.mkAttrs(v, v1.attrs->size() + v2.attrs->size()); /* Merge the attribute sets, preferring values from the second set. Make sure to keep the resulting vector in sorted diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh index 7f801d1125fb..7453ac189197 100644 --- a/src/libexpr/eval.hh +++ b/src/libexpr/eval.hh @@ -319,13 +319,11 @@ public: Value * allocAttr(Value & vAttrs, const Symbol & name); void mkList(Value & v, unsigned int length); - void mkAttrs(Value & v); + void mkAttrs(Value & v, unsigned int expected); void mkThunk_(Value & v, Expr * expr); Value * maybeThunk(Env & env, Expr * expr); - void cloneAttrs(Value & src, Value & dst); - /* Print statistics. */ void printStats(); diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc index 7c713f384f33..a4812de06519 100644 --- a/src/libexpr/primops.cc +++ b/src/libexpr/primops.cc @@ -206,7 +206,7 @@ static void prim_addErrorContext(EvalState & state, Value * * args, Value & v) * else => {success=false; value=false;} */ static void prim_tryEval(EvalState & state, Value * * args, Value & v) { - state.mkAttrs(v); + state.mkAttrs(v, 2); try { state.forceValue(*args[0]); v.attrs->push_back(Attr(state.symbols.create("value"), args[0])); @@ -484,7 +484,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v) state.drvHashes[drvPath] = hashDerivationModulo(state, drv); /* !!! assumes a single output */ - state.mkAttrs(v); + state.mkAttrs(v, 2); mkString(*state.allocAttr(v, state.sOutPath), outPath, singleton(drvPath)); mkString(*state.allocAttr(v, state.sDrvPath), drvPath, singleton("=" + drvPath)); v.attrs->sort(); @@ -745,7 +745,7 @@ static void prim_removeAttrs(EvalState & state, Value * * args, Value & v) /* Copy all attributes not in that set. Note that we don't need to sort v.attrs because it's a subset of an already sorted vector. */ - state.mkAttrs(v); + state.mkAttrs(v, args[0]->attrs->size()); foreach (Bindings::iterator, i, *args[0]->attrs) { if (names.find(i->name) == names.end()) v.attrs->push_back(*i); @@ -761,7 +761,7 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v) { state.forceList(*args[0]); - state.mkAttrs(v); + state.mkAttrs(v, args[0]->list.length); std::set seen; @@ -798,7 +798,7 @@ static void prim_intersectAttrs(EvalState & state, Value * * args, Value & v) state.forceAttrs(*args[0]); state.forceAttrs(*args[1]); - state.mkAttrs(v); + state.mkAttrs(v, std::min(args[0]->attrs->size(), args[1]->attrs->size())); foreach (Bindings::iterator, i, *args[0]->attrs) { Bindings::iterator j = args[1]->attrs->find(i->name); @@ -827,14 +827,15 @@ static void prim_functionArgs(EvalState & state, Value * * args, Value & v) if (args[0]->type != tLambda) throw TypeError("`functionArgs' requires a function"); - state.mkAttrs(v); - - if (!args[0]->lambda.fun->matchAttrs) return; + if (!args[0]->lambda.fun->matchAttrs) { + state.mkAttrs(v, 0); + return; + } + state.mkAttrs(v, args[0]->lambda.fun->formals->formals.size()); foreach (Formals::Formals_::iterator, i, args[0]->lambda.fun->formals->formals) // !!! should optimise booleans (allocate only once) mkBool(*state.allocAttr(v, i->name), i->def); - v.attrs->sort(); } @@ -1015,7 +1016,7 @@ static void prim_parseDrvName(EvalState & state, Value * * args, Value & v) { string name = state.forceStringNoCtx(*args[0]); DrvName parsed(name); - state.mkAttrs(v); + state.mkAttrs(v, 2); mkString(*state.allocAttr(v, state.sName), parsed.name); mkString(*state.allocAttr(v, state.symbols.create("version")), parsed.version); v.attrs->sort(); @@ -1043,7 +1044,7 @@ void EvalState::createBaseEnv() Value v; /* `builtins' must be first! */ - mkAttrs(v); + mkAttrs(v, 128); addConstant("builtins", v); mkBool(v, true); diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc index acd866197c7c..865d24e2f919 100644 --- a/src/nix-env/user-env.cc +++ b/src/nix-env/user-env.cc @@ -61,7 +61,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems, Value & v(*state.allocValue()); manifest.list.elems[n++] = &v; - state.mkAttrs(v); + state.mkAttrs(v, 8); mkString(*state.allocAttr(v, state.sType), "derivation"); mkString(*state.allocAttr(v, state.sName), i->name); @@ -71,7 +71,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems, mkString(*state.allocAttr(v, state.sDrvPath), i->queryDrvPath(state)); Value & vMeta = *state.allocAttr(v, state.sMeta); - state.mkAttrs(vMeta); + state.mkAttrs(vMeta, 16); MetaInfo meta = i->queryMetaInfo(state); @@ -118,7 +118,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems, /* Construct a Nix expression that calls the user environment builder with the manifest as argument. */ Value args, topLevel; - state.mkAttrs(args); + state.mkAttrs(args, 3); mkString(*state.allocAttr(args, state.sSystem), thisSystem); mkString(*state.allocAttr(args, state.symbols.create("manifest")), manifestFile, singleton(manifestFile)); -- cgit 1.4.1