evaluate inherit (from) exprs only once per directive

desugaring inherit-from to syntactic duplication of the source expr also
duplicates side effects of the source expr (such as trace calls) and
expensive computations (such as derivationStrict).

(cherry picked from commit cefd0302b55b3360dbca59cfcb4bf6a750d6cdcf)
Change-Id: Iff519f991adef2e51683ba2c552d37a3df7a179e

9 files changed, 109 insertions, 15 deletions

diff --git a/doc/manual/rl-next/inherit-from-by-need.md b/doc/manual/rl-next/inherit-from-by-need.md
new file mode 100644
index 000000000..67c2cdedf
--- /dev/null
+++ b/doc/manual/rl-next/inherit-from-by-need.md
@@ -0,0 +1,7 @@
+---
+synopsis: "`inherit (x) ...` evaluates `x` only once"
+prs: 9847
+---
+
+`inherit (x) a b ...` now evaluates the expression `x` only once for all inherited attributes rather than once for each inherited attribute.
+This does not usually have a measurable impact, but side-effects (such as `builtins.trace`) would be duplicated and expensive expressions (such as derivations) could cause a measurable slowdown.
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index e30c32d92..9fa036d6c 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -1217,6 +1217,18 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v)
 }
 
 
+Env * ExprAttrs::buildInheritFromEnv(EvalState & state, Env & up)
+{
+    Env & inheritEnv = state.allocEnv(inheritFromExprs->size());
+    inheritEnv.up = &up;
+
+    Displacement displ = 0;
+    for (auto from : *inheritFromExprs)
+        inheritEnv.values[displ++] = from->maybeThunk(state, up);
+
+    return &inheritEnv;
+}
+
 void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
 {
     v.mkAttrs(state.buildBindings(attrs.size() + dynamicAttrs.size()).finish());
@@ -1228,6 +1240,7 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
         Env & env2(state.allocEnv(attrs.size()));
         env2.up = &env;
         dynamicEnv = &env2;
+        Env * inheritEnv = inheritFromExprs ? buildInheritFromEnv(state, env2) : nullptr;
 
         AttrDefs::iterator overrides = attrs.find(state.sOverrides);
         bool hasOverrides = overrides != attrs.end();
@@ -1240,9 +1253,9 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
             Value * vAttr;
             if (hasOverrides && !i.second.inherited()) {
                 vAttr = state.allocValue();
-                mkThunk(*vAttr, *i.second.chooseByKind(&env2, &env, &env2), i.second.e);
+                mkThunk(*vAttr, *i.second.chooseByKind(&env2, &env, inheritEnv), i.second.e);
             } else
-                vAttr = i.second.e->maybeThunk(state, *i.second.chooseByKind(&env2, &env, &env2));
+                vAttr = i.second.e->maybeThunk(state, *i.second.chooseByKind(&env2, &env, inheritEnv));
             env2.values[displ++] = vAttr;
             v.attrs->push_back(Attr(i.first, vAttr, i.second.pos));
         }
@@ -1275,10 +1288,11 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
     }
 
     else {
+        Env * inheritEnv = inheritFromExprs ? buildInheritFromEnv(state, env) : nullptr;
         for (auto & i : attrs) {
             v.attrs->push_back(Attr(
                     i.first,
-                    i.second.e->maybeThunk(state, *i.second.chooseByKind(&env, &env, &env)),
+                    i.second.e->maybeThunk(state, *i.second.chooseByKind(&env, &env, inheritEnv)),
                     i.second.pos));
         }
     }
@@ -1313,6 +1327,8 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
     Env & env2(state.allocEnv(attrs->attrs.size()));
     env2.up = &env;
 
+    Env * inheritEnv = attrs->inheritFromExprs ? attrs->buildInheritFromEnv(state, env2) : nullptr;
+
     /* The recursive attributes are evaluated in the new environment,
        while the inherited attributes are evaluated in the original
        environment. */
@@ -1320,7 +1336,7 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
     for (auto & i : attrs->attrs) {
         env2.values[displ++] = i.second.e->maybeThunk(
             state,
-            *i.second.chooseByKind(&env2, &env, &env2));
+            *i.second.chooseByKind(&env2, &env, inheritEnv));
     }
 
     auto dts = state.debugRepl
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index c9d42cea5..3bcd35fef 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -78,7 +78,7 @@ void ExprAttrs::showBindings(const SymbolTable & symbols, std::ostream & str) co
         return sa < sb;
     });
     std::vector<Symbol> inherits;
-    std::map<Expr *, std::vector<Symbol>> inheritsFrom;
+    std::map<ExprInheritFrom *, std::vector<Symbol>> inheritsFrom;
     for (auto & i : sorted) {
         switch (i->second.kind) {
         case AttrDef::Kind::Plain:
@@ -88,7 +88,8 @@ void ExprAttrs::showBindings(const SymbolTable & symbols, std::ostream & str) co
             break;
         case AttrDef::Kind::InheritedFrom: {
             auto & select = dynamic_cast<ExprSelect &>(*i->second.e);
-            inheritsFrom[select.e].push_back(i->first);
+            auto & from = dynamic_cast<ExprInheritFrom &>(*select.e);
+            inheritsFrom[&from].push_back(i->first);
             break;
         }
         }
@@ -100,7 +101,7 @@ void ExprAttrs::showBindings(const SymbolTable & symbols, std::ostream & str) co
     }
     for (const auto & [from, syms] : inheritsFrom) {
         str << "inherit (";
-        from->show(symbols, str);
+        (*inheritFromExprs)[from->displ]->show(symbols, str);
         str << ")";
         for (auto sym : syms) str << " " << symbols[sym];
         str << "; ";
@@ -326,6 +327,12 @@ void ExprVar::bindVars(EvalState & es, const std::shared_ptr<const StaticEnv> &
     this->level = withLevel;
 }
 
+void ExprInheritFrom::bindVars(EvalState & es, const std::shared_ptr<const StaticEnv> & env)
+{
+    if (es.debugRepl)
+        es.exprEnvs.insert(std::make_pair(this, env));
+}
+
 void ExprSelect::bindVars(EvalState & es, const std::shared_ptr<const StaticEnv> & env)
 {
     if (es.debugRepl)
@@ -349,6 +356,27 @@ void ExprOpHasAttr::bindVars(EvalState & es, const std::shared_ptr<const StaticE
             i.expr->bindVars(es, env);
 }
 
+std::shared_ptr<const StaticEnv> ExprAttrs::bindInheritSources(
+    EvalState & es, const std::shared_ptr<const StaticEnv> & env)
+{
+    if (!inheritFromExprs)
+        return nullptr;
+
+    // the inherit (from) source values are inserted into an env of its own, which
+    // does not introduce any variable names.
+    // analysis must see an empty env, or an env that contains only entries with
+    // otherwise unused names to not interfere with regular names. the parser
+    // has already filled all exprs that access this env with appropriate level
+    // and displacement, and nothing else is allowed to access it. ideally we'd
+    // not even *have* an expr that grabs anything from this env since it's fully
+    // invisible, but the evaluator does not allow for this yet.
+    auto inner = std::make_shared<StaticEnv>(nullptr, env.get(), 0);
+    for (auto from : *inheritFromExprs)
+        from->bindVars(es, env);
+
+    return inner;
+}
+
 void ExprAttrs::bindVars(EvalState & es, const std::shared_ptr<const StaticEnv> & env)
 {
     if (es.debugRepl)
@@ -366,8 +394,9 @@ void ExprAttrs::bindVars(EvalState & es, const std::shared_ptr<const StaticEnv>
 
         // No need to sort newEnv since attrs is in sorted order.
 
+        auto inheritFromEnv = bindInheritSources(es, newEnv);
         for (auto & i : attrs)
-            i.second.e->bindVars(es, i.second.chooseByKind(newEnv, env, newEnv));
+            i.second.e->bindVars(es, i.second.chooseByKind(newEnv, env, inheritFromEnv));
 
         for (auto & i : dynamicAttrs) {
             i.nameExpr->bindVars(es, newEnv);
@@ -375,8 +404,10 @@ void ExprAttrs::bindVars(EvalState & es, const std::shared_ptr<const StaticEnv>
         }
     }
     else {
+        auto inheritFromEnv = bindInheritSources(es, env);
+
         for (auto & i : attrs)
-            i.second.e->bindVars(es, i.second.chooseByKind(env, env, env));
+            i.second.e->bindVars(es, i.second.chooseByKind(env, env, inheritFromEnv));
 
         for (auto & i : dynamicAttrs) {
             i.nameExpr->bindVars(es, env);
@@ -444,8 +475,9 @@ void ExprLet::bindVars(EvalState & es, const std::shared_ptr<const StaticEnv> &
 
     // No need to sort newEnv since attrs->attrs is in sorted order.
 
+    auto inheritFromEnv = attrs->bindInheritSources(es, newEnv);
     for (auto & i : attrs->attrs)
-        i.second.e->bindVars(es, i.second.chooseByKind(newEnv, env, newEnv));
+        i.second.e->bindVars(es, i.second.chooseByKind(newEnv, env, inheritFromEnv));
 
     if (es.debugRepl)
         es.exprEnvs.insert(std::make_pair(this, newEnv));
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 793e1a707..cb630d201 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -129,6 +129,18 @@ struct ExprVar : Expr
     COMMON_METHODS
 };
 
+struct ExprInheritFrom : ExprVar
+{
+    ExprInheritFrom(PosIdx pos, Displacement displ): ExprVar(pos, {})
+    {
+        this->level = 0;
+        this->displ = displ;
+        this->fromWith = nullptr;
+    }
+
+    void bindVars(EvalState & es, const std::shared_ptr<const StaticEnv> & env);
+};
+
 struct ExprSelect : Expr
 {
     PosIdx pos;
@@ -189,6 +201,7 @@ struct ExprAttrs : Expr
     };
     typedef std::map<Symbol, AttrDef> AttrDefs;
     AttrDefs attrs;
+    std::unique_ptr<std::vector<Expr *>> inheritFromExprs;
     struct DynamicAttrDef {
         Expr * nameExpr, * valueExpr;
         PosIdx pos;
@@ -202,6 +215,9 @@ struct ExprAttrs : Expr
     PosIdx getPos() const override { return pos; }
     COMMON_METHODS
 
+    std::shared_ptr<const StaticEnv> bindInheritSources(
+        EvalState & es, const std::shared_ptr<const StaticEnv> & env);
+    Env * buildInheritFromEnv(EvalState & state, Env & up);
     void showBindings(const SymbolTable & symbols, std::ostream & str) const;
 };
 
diff --git a/src/libexpr/parser-state.hh b/src/libexpr/parser-state.hh
index fa417b0be..d10188f52 100644
--- a/src/libexpr/parser-state.hh
+++ b/src/libexpr/parser-state.hh
@@ -117,13 +117,24 @@ inline void ParserState::addAttr(ExprAttrs * attrs, AttrPath && attrPath, Expr *
             auto ae = dynamic_cast<ExprAttrs *>(e);
             auto jAttrs = dynamic_cast<ExprAttrs *>(j->second.e);
             if (jAttrs && ae) {
+                if (ae->inheritFromExprs && !jAttrs->inheritFromExprs)
+                    jAttrs->inheritFromExprs = std::make_unique<std::vector<Expr *>>();
                 for (auto & ad : ae->attrs) {
                     auto j2 = jAttrs->attrs.find(ad.first);
                     if (j2 != jAttrs->attrs.end()) // Attr already defined in iAttrs, error.
                         dupAttr(ad.first, j2->second.pos, ad.second.pos);
                     jAttrs->attrs.emplace(ad.first, ad.second);
+                    if (ad.second.kind == ExprAttrs::AttrDef::Kind::InheritedFrom) {
+                        auto & sel = dynamic_cast<ExprSelect &>(*ad.second.e);
+                        auto & from = dynamic_cast<ExprInheritFrom &>(*sel.e);
+                        from.displ += jAttrs->inheritFromExprs->size();
+                    }
                 }
                 jAttrs->dynamicAttrs.insert(jAttrs->dynamicAttrs.end(), ae->dynamicAttrs.begin(), ae->dynamicAttrs.end());
+                if (ae->inheritFromExprs) {
+                    jAttrs->inheritFromExprs->insert(jAttrs->inheritFromExprs->end(),
+                        ae->inheritFromExprs->begin(), ae->inheritFromExprs->end());
+                }
             } else {
                 dupAttr(attrPath, pos, j->second.pos);
             }
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index ae5723a6f..ee44a6d7a 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -319,14 +319,17 @@ binds
     }
   | binds INHERIT '(' expr ')' attrs ';'
     { $$ = $1;
-      /* !!! Should ensure sharing of the expression in $4. */
+      if (!$$->inheritFromExprs)
+          $$->inheritFromExprs = std::make_unique<std::vector<Expr *>>();
+      $$->inheritFromExprs->push_back($4);
+      auto from = new nix::ExprInheritFrom(state->at(@4), $$->inheritFromExprs->size() - 1);
       for (auto & i : *$6) {
           if ($$->attrs.find(i.symbol) != $$->attrs.end())
               state->dupAttr(i.symbol, state->at(@6), $$->attrs[i.symbol].pos);
           $$->attrs.emplace(
               i.symbol,
               ExprAttrs::AttrDef(
-                  new ExprSelect(CUR_POS, $4, i.symbol),
+                  new ExprSelect(CUR_POS, from, i.symbol),
                   state->at(@6),
                   ExprAttrs::AttrDef::Kind::InheritedFrom));
       }
diff --git a/tests/functional/lang/eval-okay-inherit-from.err.exp b/tests/functional/lang/eval-okay-inherit-from.err.exp
index 51881205b..3227501f2 100644
--- a/tests/functional/lang/eval-okay-inherit-from.err.exp
+++ b/tests/functional/lang/eval-okay-inherit-from.err.exp
@@ -1,2 +1 @@
 trace: used
-trace: used
diff --git a/tests/functional/lang/eval-okay-inherit-from.exp b/tests/functional/lang/eval-okay-inherit-from.exp
index 43bd0e899..024daff6b 100644
--- a/tests/functional/lang/eval-okay-inherit-from.exp
+++ b/tests/functional/lang/eval-okay-inherit-from.exp
@@ -1 +1 @@
-[ 1 2 { __overrides = { y = { d = [ ]; }; }; c = [ ]; d = 4; x = { c = [ ]; }; y = «repeated»; } ]
+[ 1 2 { __overrides = { y = { d = [ ]; }; }; c = [ ]; d = 4; x = { c = [ ]; }; y = «repeated»; } { inner = { c = 3; d = 4; }; } ]
diff --git a/tests/functional/lang/eval-okay-inherit-from.nix b/tests/functional/lang/eval-okay-inherit-from.nix
index d1fad7d69..b72a1c639 100644
--- a/tests/functional/lang/eval-okay-inherit-from.nix
+++ b/tests/functional/lang/eval-okay-inherit-from.nix
@@ -2,5 +2,15 @@ let
   inherit (builtins.trace "used" { a = 1; b = 2; }) a b;
   x.c = 3;
   y.d = 4;
+
+  merged = {
+    inner = {
+      inherit (y) d;
+    };
+
+    inner = {
+      inherit (x) c;
+    };
+  };
 in
-  [ a b rec { x.c = []; inherit (x) c; inherit (y) d; __overrides.y.d = []; } ]
+  [ a b rec { x.c = []; inherit (x) c; inherit (y) d; __overrides.y.d = []; } merged ]