fix(tvix/eval): `getContext` merges underlying values r/7403

Previously, we were assembling very naively an attribute set composed of context we saw.

But it was forgetting that `"${drv}${drv.drvPath}"` would contain 2 contexts with the same key, but
with different values, one with `outputs = [ "out" ];` and `allOutputs = true;`.

Following this reasoning and comparing with what Nix does, we ought to merge underlying values systematically.

Hence, I bring `itertools` to perform a group by on the key and merge everything on the fly, it's not
beautiful but it's the best I could find, notice that I don't use
`group_by` but I talk about group by, that is, because `group_by` is a
`group_by_consecutive`, see
https://github.com/rust-itertools/itertools/issues/374.

Initially, I tried to do it without a `into_grouping_map_by`, it was akin to assemble the final `NixAttrs` directly,
it was less readable and harder to pull out because we don't have a lot of in-place mutable functions on
our data structures.

Change-Id: I9933c9bd88ffe04de50dda14f21879b60d8b8cd4
Reviewed-on: https://cl.tvl.fyi/c/depot/+/10620
Tested-by: BuildkiteCI
Reviewed-by: tazjin <tazjin@tvl.su>

2 files changed, 66 insertions, 17 deletions

diff --git a/tvix/eval/Cargo.toml b/tvix/eval/Cargo.toml
index d1bb48a7c512..d347d0ea687a 100644
--- a/tvix/eval/Cargo.toml
+++ b/tvix/eval/Cargo.toml
@@ -16,6 +16,7 @@ codemap-diagnostic = "0.1.1"
 dirs = "4.0.0"
 genawaiter = { version = "0.99.1", default_features = false }
 imbl = { version = "2.0", features = [ "serde" ] }
+itertools = "0.12.0"
 lazy_static = "1.4.0"
 lexical-core = { version = "0.8.5", features = ["format", "parse-floats"] }
 path-clean = "0.1"
diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index 03e485cb56dc..2070f6591e47 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -76,6 +76,9 @@ pub async fn coerce_value_to_path(
 
 #[builtins]
 mod pure_builtins {
+    use imbl::Vector;
+    use itertools::Itertools;
+
     use crate::{value::PointerEquality, NixContext, NixContextElement};
 
     use super::*;
@@ -705,25 +708,70 @@ mod pure_builtins {
             .await?;
         let s = v.to_contextful_str()?;
 
-        let elements = s
+        let groups = s
             .iter_context()
             .flat_map(|context| context.iter())
-            .map(|ctx_element| match ctx_element {
-                NixContextElement::Plain(spath) => (
-                    spath.clone(),
-                    Value::attrs(NixAttrs::from_iter([("path", true)])),
-                ),
-                NixContextElement::Single { name, derivation } => (
-                    derivation.clone(),
-                    Value::attrs(NixAttrs::from_iter([(
-                        "outputs",
-                        Value::List(NixList::construct(1, vec![name.clone().into()])),
-                    )])),
-                ),
-                NixContextElement::Derivation(drv_path) => (
-                    drv_path.clone(),
-                    Value::attrs(NixAttrs::from_iter([("allOutputs", true)])),
-                ),
+            // Do not think `group_by` works here.
+            // `group_by` works on consecutive elements of the iterator.
+            // Due to how `HashSet` works (ordering is not guaranteed),
+            // this can become a source of non-determinism if you `group_by` naively.
+            // I know I did.
+            .into_grouping_map_by(|ctx_element| match ctx_element {
+                NixContextElement::Plain(spath) => spath,
+                NixContextElement::Single { derivation, .. } => derivation,
+                NixContextElement::Derivation(drv_path) => drv_path,
+            })
+            .collect::<Vec<_>>();
+
+        let elements = groups
+            .into_iter()
+            .map(|(key, group)| {
+                let mut outputs: Vector<NixString> = Vector::new();
+                let mut is_path = false;
+                let mut all_outputs = false;
+
+                for ctx_element in group {
+                    match ctx_element {
+                        NixContextElement::Plain(spath) => {
+                            debug_assert!(spath == key, "Unexpected group containing mixed keys, expected: {:?}, encountered {:?}", key, spath);
+                            is_path = true;
+                        }
+
+                        NixContextElement::Single { name, derivation } => {
+                            debug_assert!(derivation == key, "Unexpected group containing mixed keys, expected: {:?}, encountered {:?}", key, derivation);
+                            outputs.push_back(name.clone().into());
+                        }
+
+                        NixContextElement::Derivation(drv_path) => {
+                            debug_assert!(drv_path == key, "Unexpected group containing mixed keys, expected: {:?}, encountered {:?}", key, drv_path);
+                            all_outputs = true;
+                        }
+                    }
+                }
+
+                // FIXME(raitobezarius): is there a better way to construct an attribute set
+                // conditionally?
+                let mut vec_attrs: Vec<(&str, Value)> = Vec::new();
+
+                if is_path {
+                    vec_attrs.push(("path", true.into()));
+                }
+
+                if all_outputs {
+                    vec_attrs.push(("allOutputs", true.into()));
+                }
+
+                if !outputs.is_empty() {
+                    outputs.sort();
+                    vec_attrs.push(("outputs", Value::List(outputs
+                                .into_iter()
+                                .map(|s| s.into())
+                                .collect::<Vector<Value>>()
+                                .into()
+                    )));
+                }
+
+                (key.clone(), Value::attrs(NixAttrs::from_iter(vec_attrs.into_iter())))
             });
 
         Ok(Value::attrs(NixAttrs::from_iter(elements)))