`builtins.deepSeq` leads to nondeterministic error message

[roberth]

Describe the bug

forceValueDeep processes attributes in symbol id order instead of alphabetically. Although this is a small deficiency not observable in the "happy world" of successful evaluations, it does affect our ability to provide helpful error messages in attrsets that should never be traversed (such as pkgs or a NixOS config; both are too big and are designed to contain some errors, which would be confusing, as they don't point to the root cause, which is the traversal).

Steps To Reproduce

nix-repl> builtins.deepSeq { a = throw "a"; b = throw "b"; } true 
error: a

nix-repl> builtins.deepSeq { d = throw "d"; c = throw "c"; } true 
error: d

The latter looks innocent, because surely the first attribute goes first, but that's not how attribute sets are defined. They contain no ordering information! This behavior is an artifact of how symbols are implemented.

Expected behavior

deepSeq evaluates the lexicographically smallest attribute first.

nix-env --version output

Additional context

Priorities

Add :+1: to issues you find important.

[edolstra]

While deepSeq using lexicographical order might be okay (though it's slower), in general we don't guarantee an evaluation order. E.g. it's not guaranteed what error message throw "a" + throw "b" will produce.

[puckipedia]

The ordering in this implementation of Nix is in fact consistent (they're in order that symbols are used in the source code, with some exceptions surrounding interpolated strings in attrsets, but if you care about the semantics of this you probably know most Nix quirks already) and *is* in fact observable in non-throw Nix code with some fun magic, see #6160

[Ericson2314]

Discussed in the Nix team meeting:

• Actually a potential soundness issue
• @thufschmitt
  • abort vs throw is observable
  • (this is why catching requires IO in Haskell)
  • self-assigned

[thufschmitt]

in general we don't guarantee an evaluation order

@edolstra thinking about it, this is actually also technically unsound since we have tryEval. So maybe we should guaranty it if we want the code to be backwards-compatible.

Just to justify the unsoundness: some errors are caught by tryEval, and others not. So builtins.tryEval (throw "a" + (1*"")) will evaluate to { success = false; value = false; } if the left-hand side of the + is evaluated first (the current behaviour as of Nix 2.14.1), and throw a type error if the right-hand side is evaluated first.

[Ericson2314]

I will note another way to make tryEval more deterministic is to simply evaluate both arugments to +, etc., then we only allow the tryEval to catch the error if no possible eval order throws an unrecoverable error.

This sounds like a lot of work for useful benefit, but I will note the same sort of "do more work but not more than weak head normal form" logic is also what is needed for fix the IFD pipelining problem (keep on evaluating while we wait for imported path to be realized). So there is a chance to kill two birds with one stone here.

[edolstra]

That's why I wasn't in favor of adding tryEval to the language. It should have been called unsafeTryEval to emphasize the non-determinism.

However, Nix is not a general-purpose language so I don't think we should worry about this too much. If people actually depend on the evaluation order wrt tryEval, they're using Nix wrong.

[thufschmitt]

That's why I wasn't in favor of adding tryEval to the language. It should have been called unsafeTryEval to emphasize the non-determinism.

Indeed :)

Should we forbid it in --pure mode then? That sounds like the strictly correct™ thing, but it's also probably a very bad thing.

[nixos-discourse]

This issue has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/2023-03-10-nix-team-meeting-minutes-39/26279/1