it then shows undefined behavior

Nix doesn't have undefined behavior afaik. I think what you mean is that the output depends on details in the input that should not matter much.

Evaluating nix-instantiate nixos/release-combined.nix -A tested three times I get:

• Before this change: 220.0s (stddev 2.0s)
• After this change: 226.0s (stddev 1.3s)

So this change makes it about 2.7% slower, not too bad. For more stats, see ofborg's result here: https://github.com/NixOS/nixpkgs/pull/76857/checks?check_run_id=373281930

I'll try to optimize it a bit further though, I think there's some potential

Nope, the potential I saw turned out to be an anti-optimization. Apart from perhaps adding some more comments to the code itself, I think this is pretty much ready.

With that change I get:

• Before: 205.2s (stddev 0.7s, 3 samples)
• After: 211.2s (stddev 3.1s, 6 samples)

Not sure why this time the times are a bit faster than last time, the raw values are 210.574, 212.35, 205.356, 210.043, 214.301, 214.593. Not sure what's up with that 205.356 there either. With those means we get a decrease of 2.9%, so it's about the same. But it certainly can't hurt to use removeAttrs instead, will apply that change.

Moved loadModule to the let in scope, no need to expose this in lib

Using the faster with genericClosure now

Thanks for the review :D

After this change, I am unable to use store paths in my module imports. For example, something like:

{
  imports = [ "${sources.home-manager}/nixos" ];
  ...
}

now fails to evaluate with:

error: the string '/nix/store/an1yy60yq7p6syfxwbwljb8dmxnkk1ls-source/nixos' is not allowed to refer to a store path (such as '/nix/store/an1yy60yq7p6syfxwbwljb8dmxnkk1ls-source')

Is this intentional? If so, is there a workaround?

Oh thanks for the report. Turns out the changes in #76857 (comment) are causing this. I'll make a PR to fix it

See above PR which fixes this

As uncovered by @evanjs on IRC, this introduces a new case of infinite recursion when imports have a cycle in them, e.g. a module foo.nix with the contents

{
  imports = [ ./foo.nix ];
}

now throws

error: stack overflow (possible infinite recursion)

While I do have a fix for this, I don't think this use-case needs to be supported as I don't know of a case where something like this is needed. To fix this, just break the cycle by not importing the same module again.

So you can say that imports now have to be a DAG instead of an arbitrary graph.

Fix is here in case this is needed in the future:

diff --git a/lib/modules.nix b/lib/modules.nix
index e2315290ff0..82981dba73b 100644
--- a/lib/modules.nix
+++ b/lib/modules.nix
@@ -139,16 +139,22 @@ rec {
             disabled = concatLists (catAttrs "disabled" modules);
             inherit modules;
           };
-        in parentFile: parentKey: initialModules: args: collectResults (imap1 (n: x:
+        in parentPath: parentFile: parentKey: initialModules: args:
           let
-            module = loadModule args parentFile "${parentKey}:anon-${toString n}" x;
-            collectedImports = collectStructuredModules module._file module.key module.imports args;
+            # All modules this module imports, loaded and without modules that
+            # are anywhere on the parent path to prevent cycles
+            includedModules = filter (module: ! elem module.key parentPath) (imap1 (n:
+              loadModule args parentFile "${parentKey}:anon-${toString n}"
+            ) initialModules);
+          in collectResults (map (module:
+          let
+            collectedImports = collectStructuredModules (parentPath ++ [ module.key ]) module._file module.key module.imports args;
           in {
             key = module.key;
             module = module;
             modules = collectedImports.modules;
             disabled = module.disabledModules ++ collectedImports.disabled;
-          }) initialModules);
+          }) includedModules);
 
       # filterModules :: String -> { disabled, modules } -> [ Module ]
       #
@@ -165,7 +171,7 @@ rec {
         });
 
     in modulesPath: initialModules: args:
-      filterModules modulesPath (collectStructuredModules unknownModule "" initialModules args);
+      filterModules modulesPath (collectStructuredModules [""] unknownModule "" initialModules args);
 
   /* Massage a module into canonical form, that is, a set consisting
      of ‘options’, ‘config’ and ‘imports’ attributes. */

Just wanted to confirm that a dry build without @infinisil's patch does reproduce this issue (error: stack overflow (possible infinite recursion)), and with the patch, I am able to get a list of packages that would be built!