nova-nix 0.1.5.0 → 0.1.6.0
raw patch · 13 files changed
+581/−251 lines, 13 filesdep +primitive
Dependencies added: primitive
Files
- CHANGELOG.md +13/−1
- LICENSE +25/−17
- README.md +16/−13
- app/Main.hs +1/−0
- nova-nix.cabal +5/−2
- src/Nix/Builtins.hs +14/−11
- src/Nix/Eval.hs +196/−130
- src/Nix/Eval/IO.hs +21/−2
- src/Nix/Eval/Types.hs +113/−66
- src/Nix/Expr/Resolve.hs +156/−0
- src/Nix/Expr/Types.hs +5/−0
- src/Nix/Parser.hs +2/−1
- test/Main.hs +14/−8
CHANGELOG.md view
@@ -1,5 +1,17 @@ # Changelog +## 0.1.6.0 — 2026-02-26++### De Bruijn-Style Positional Env + SmallArray Slots++- **De Bruijn-style variable resolution** — New `Nix.Expr.Resolve` pass replaces `EVar` with `EResolvedVar level index` for lambda-bound variables. Called at parse time; all subsequent evaluation uses positional indices instead of name-based `Map` lookups.+- **Array-based Env** — `envSlots :: SmallArray Thunk` replaces `envBindings :: Map Text Thunk`. Lambda formals get O(1) positional indexing via `indexSmallArray` instead of O(log n) `Map.lookup`. Let/rec bindings and builtins remain in name-based `envLazyScope` (already zero Map.Bin overhead).+- **Scope chain** — `Env` uses parent pointer chain instead of `Map.union`. Variable lookup walks the chain: positional slots, then `envLazyScope`, then parent, then with-scopes. Avoids O(n) `Map.union` when extending large envs.+- **Inherit desugaring** — `inherit x;` is desugared to `x = x;` in the resolution pass so inherited lambda formals resolve to `EResolvedVar` (lambda slots have no names at runtime).+- **Heap savings** — Eliminates 29.9M Map.Bin nodes (1.37 GB) from lambda formals. Replaced by SmallArray (one heap object per env, O(1) index) + scope chain parent pointers.+- `primitive` dependency added for `Data.Primitive.SmallArray`+- 108 builtins, 511 tests, -Werror clean, ormolu clean, hlint clean+ ## 0.1.5.0 — 2026-02-26 ### New Builtins, Coercion Fixes, CI Cleanup@@ -57,7 +69,7 @@ - **Semi-lazy `concatMap`** — forces applications to discover list structure for concatenation, but element thunks within sub-lists stay lazy - **`@`-pattern scoping fix** — `{ system ? args.system or ..., ... }@args:` now correctly binds the `@`-name before evaluating defaults, matching real Nix. Previously, default expressions couldn't reference the `@`-binding. - **Synthetic thunk memo cell fix** — `mkSyntheticThunk` uses env bindings (not expr) for IORef uniqueness, preventing GHC's full-laziness transform from sharing one memo cell across all deferred thunks. Without this, `map f [a b c]` would return `[f(a) f(a) f(a)]`.-- `deferApply` helper: builds thunks wrapping `EApp (EVar "__fn") (EVar "__arg")` in a self-contained env, reusing existing eval + memoization machinery+- `deferApply` helper: builds thunks wrapping `EApp (EResolvedVar 0 0) (EResolvedVar 0 1)` in a self-contained env with positional slots, reusing existing eval + memoization machinery - 511 tests (3 new: map laziness, genList laziness, mapAttrs laziness) ## 0.1.1.0 — 2026-02-24
LICENSE view
@@ -1,21 +1,29 @@-MIT License- Copyright (c) 2026 Novavero AI -Permission is hereby granted, free of charge, to any person obtaining a copy-of this software and associated documentation files (the "Software"), to deal-in the Software without restriction, including without limitation the rights-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell-copies of the Software, and to permit persons to whom the Software is-furnished to do so, subject to the following conditions:+All rights reserved. -The above copyright notice and this permission notice shall be included in all-copies or substantial portions of the Software.+Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met: -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE-SOFTWARE.+1. Redistributions of source code must retain the above copyright notice,+ this list of conditions and the following disclaimer.++2. Redistributions in binary form must reproduce the above copyright notice,+ this list of conditions and the following disclaimer in the documentation+ and/or other materials provided with the distribution.++3. Neither the name of the copyright holder nor the names of its+ contributors may be used to endorse or promote products derived from+ this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE+ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE+LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR+CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF+SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)+ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF+THE POSSIBILITY OF SUCH DAMAGE.
README.md view
@@ -19,9 +19,9 @@ A pure Haskell implementation of Nix that treats Windows as a first-class target: -- **Parser** — Hand-rolled recursive descent parser for the full Nix expression language. 13 precedence levels, 17 AST constructors, all syntax forms including search paths (`<nixpkgs>`) and dynamic attribute keys (`{ ${expr} = val; }`). Direct `Text` consumption for maximum throughput.-- **Lazy Evaluator** — Thunk-based evaluation with environment closures, knot-tying for recursive bindings via Haskell laziness. All 17 AST constructors handled: literals, strings with interpolation, attribute sets (recursive and non-recursive), let bindings, lambdas with formal parameters, if/then/else, with, assert, unary/binary operators, function application, list construction, attribute selection, has-attribute checks, and search path resolution.-- **106 Built-in Functions** — Type checks, arithmetic (`min`, `max`, `mod`), bitwise, strings, lists, attribute sets, higher-order (`map`, `filter`, `foldl'`, `sort`, `genList`, `concatMap`, `mapAttrs`), JSON (`toJSON`/`fromJSON`), hashing (SHA-256/SHA-512/SHA-1/MD5), base64 (`encode`/`decode`), version parsing, `replaceStrings`, `tryEval`, `deepSeq`, `genericClosure`, `setFunctionArgs`/`functionArgs`, string context introspection (`hasContext`, `getContext`, `appendContext`), IO builtins (`import`, `readFile`, `pathExists`, `readDir`, `getEnv`, `toPath`, `toFile`, `findFile`, `scopedImport`, `fetchurl`, `fetchTarball`, `fetchGit`), `derivation`, `placeholder`, `storePath`, and more. 16 builtins available at top level without `builtins.` prefix (`toString`, `map`, `throw`, `import`, `derivation`, `abort`, `baseNameOf`, `dirOf`, `isNull`, `removeAttrs`, `placeholder`, `scopedImport`, `fetchTarball`, `fetchGit`, `fetchurl`, `toFile`) — matching the real Nix language spec.+- **Parser** — Hand-rolled recursive descent parser for the full Nix expression language. 13 precedence levels, 18 AST constructors, all syntax forms including search paths (`<nixpkgs>`) and dynamic attribute keys (`{ ${expr} = val; }`). Direct `Text` consumption for maximum throughput.+- **Lazy Evaluator** — Thunk-based evaluation with environment closures, knot-tying for recursive bindings via Haskell laziness. All 18 AST constructors handled: literals, strings with interpolation, attribute sets (recursive and non-recursive), let bindings, lambdas with formal parameters, if/then/else, with, assert, unary/binary operators, function application, list construction, attribute selection, has-attribute checks, and search path resolution.+- **108 Built-in Functions** — Type checks, arithmetic (`min`, `max`, `mod`), bitwise, strings, lists, attribute sets, higher-order (`map`, `filter`, `foldl'`, `sort`, `genList`, `concatMap`, `mapAttrs`), JSON (`toJSON`/`fromJSON`), hashing (SHA-256/SHA-512/SHA-1/MD5), base64 (`encode`/`decode`), version parsing, `replaceStrings`, `tryEval`, `deepSeq`, `genericClosure`, `setFunctionArgs`/`functionArgs`, string context introspection (`hasContext`, `getContext`, `appendContext`), IO builtins (`import`, `readFile`, `pathExists`, `readDir`, `getEnv`, `toPath`, `toFile`, `findFile`, `scopedImport`, `fetchurl`, `fetchTarball`, `fetchGit`), `derivation`, `placeholder`, `storePath`, and more. 16 builtins available at top level without `builtins.` prefix (`toString`, `map`, `throw`, `import`, `derivation`, `abort`, `baseNameOf`, `dirOf`, `isNull`, `removeAttrs`, `placeholder`, `scopedImport`, `fetchTarball`, `fetchGit`, `fetchurl`, `toFile`) — matching the real Nix language spec. - **Search Path Resolution** — `<nixpkgs>` desugars to `builtins.findFile builtins.nixPath "nixpkgs"` — matching real Nix semantics. `NIX_PATH` environment variable is parsed at startup, and `--nix-path` CLI flags merge with it. Directory imports (`import ./dir`) resolve to `dir/default.nix` automatically. - **Dynamic Attribute Keys** — `{ ${expr} = val; }` fully supported in all contexts: non-recursive attrs, recursive attrs, let bindings, attribute selection, and has-attribute checks. Key resolution is cleanly separated from value thunk construction to preserve knot-tying in recursive bindings. - **String Context Tracking** — Every string carries invisible metadata tracking which store paths it references. Context propagates through interpolation, concatenation, `replaceStrings`, and all string operations. The `derivation` builtin collects contexts into `drvInputDrvs` and `drvInputSrcs` — matching real Nix semantics.@@ -176,7 +176,9 @@ | Module | Purpose | |--------|---------|-| `Nix.Expr.Types` | Complete Nix AST — 17 expression constructors (including `ESearchPath`), atoms, formals, operators, string parts, source locations |+| `Nix.Expr` | Re-exports from `Nix.Expr.Types` |+| `Nix.Expr.Types` | Complete Nix AST — 18 expression constructors (including `ESearchPath`, `EResolvedVar`), atoms, formals, operators, string parts |+| `Nix.Expr.Resolve` | De Bruijn-style variable resolution pass — replaces `EVar` with `EResolvedVar` for lambda-bound variables at parse time | | `Nix.Parser` | Hand-rolled recursive descent parser + lexer. Direct `Text` consumption, source position tracking | | `Nix.Parser.Lexer` | Tokenizer — integers, floats, strings with interpolation, paths, URIs, search paths, all operators/keywords | | `Nix.Parser.Expr` | Expression parser — 13 precedence levels, left/right/non-associative operators, application, selection, dynamic keys |@@ -187,13 +189,13 @@ | Module | Purpose | |--------|---------|-| `Nix.Eval` | Lazy evaluator — all 17 AST constructors, thunk forcing, env operations, 106-builtin dispatch, `__functor` callable sets, search path resolution, dynamic attribute keys. Polymorphic via `MonadEval` |-| `Nix.Eval.Types` | Shared types — `NixValue` (11 constructors), `Thunk` (lazy env for knot-tying), `Env` (lexical + with-scope chain), `StringContext` (store path tracking), `MonadEval` typeclass, `PureEval` runner |+| `Nix.Eval` | Lazy evaluator — all 18 AST constructors, thunk forcing, env operations, 108-builtin dispatch, `__functor` callable sets, search path resolution, dynamic attribute keys. Polymorphic via `MonadEval` |+| `Nix.Eval.Types` | Shared types — `NixValue` (11 constructors), `Thunk` (IORef memo cell), `Env` (SmallArray positional slots + scope chain), `AttrSet` (lazy/eager), `StringContext` (store path tracking), `MonadEval` typeclass, `PureEval` runner | | `Nix.Eval.Operator` | Binary/unary operators — arithmetic with float promotion, deep structural equality, division-by-zero checks | | `Nix.Eval.StringInterp` | String interpolation — value coercion with context propagation, indented string whitespace stripping | | `Nix.Eval.Context` | String context construction, queries, extraction — pure helpers for building and inspecting store path references | | `Nix.Eval.IO` | IO evaluation monad — real filesystem access, import cache (with directory import), process execution, store writes, NIX_PATH parsing, per-thunk IORef memoization (matching real Nix in-place mutation) |-| `Nix.Builtins` | Built-in function environment — 106 builtins, search path plumbing (`parseNixPath`), top-level builtin exposure |+| `Nix.Builtins` | Built-in function environment — 108 builtins, search path plumbing (`parseNixPath`), top-level builtin exposure | ### Store + Builder @@ -218,10 +220,11 @@ | | | Parser --> Expr.Types --> Eval --> Builtins | | | | |- | Parser.Lexer Eval.Types |- | Parser.Expr Eval.Operator |- | Parser.Internal Eval.StringInterp |- | ParseError Eval.Context |+ | Expr.Resolve Eval.Types |+ | Parser.Lexer Eval.Operator |+ | Parser.Expr Eval.StringInterp |+ | Parser.Internal Eval.Context |+ | ParseError | | | | | Derivation --> Hash | | | |@@ -255,7 +258,7 @@ **Key numbers:** -- **22 modules** — all implemented+- **23 modules** — all implemented - **511 tests** — hand-rolled harness, no framework dependencies - **Zero partial functions** — total by construction, `T.uncons` over `T.head`/`T.tail` - **Strict by default** — bang patterns on all data fields (except Thunk's Env, which is lazy for knot-tying)@@ -286,7 +289,7 @@ ### Next -- [ ] **Full `import <nixpkgs> {}` performance** — nixpkgs lib layer evaluates correctly; stdenv bootstrap runs but needs memory optimization for the full 80,000+ package set (currently OOM at 2GB, investigating space leak)+- [ ] **Full `import <nixpkgs> {}` performance** — nixpkgs lib layer evaluates correctly; stdenv bootstrap runs but needs further memory optimization for the full 80,000+ package set (de Bruijn indices + SmallArray slots eliminated 1.37 GB of Map.Bin overhead; testing on 16 GB Windows machine in progress) - [ ] **`nova-nix shell`** — Enter a development shell (like `nix shell`) - [ ] **`nova-nix repl`** — Interactive evaluator
app/Main.hs view
@@ -277,6 +277,7 @@ in "{ " <> T.intercalate " " rendered <> " }" prettyValue (VLambda {}) = "«lambda»" prettyValue (VBuiltin name _) = "«builtin " <> name <> "»"+prettyValue (VCompiledRegex _) = "«compiled-regex»" prettyValue (VDerivation drv) = case drvOutputs drv of (out : _) -> "«derivation " <> T.pack (storePathToFilePath defaultStoreDir (doPath out)) <> "»"
nova-nix.cabal view
@@ -1,6 +1,6 @@ cabal-version: 3.0 name: nova-nix-version: 0.1.5.0+version: 0.1.6.0 synopsis: Windows-native Nix implementation in pure Haskell description: A pure Haskell implementation of the Nix package manager that runs natively@@ -11,7 +11,7 @@ Built on top of @nova-cache@ for NAR serialization, narinfo handling, Ed25519 signing, and binary substitution. -license: MIT+license: BSD-3-Clause license-file: LICENSE author: Devon Tomlin maintainer: devon.tomlin@novavero.ai@@ -34,6 +34,7 @@ library exposed-modules: Nix.Expr+ Nix.Expr.Resolve Nix.Expr.Types Nix.Parser Nix.Parser.Expr@@ -70,6 +71,7 @@ , memory >= 0.18 && < 1 , mtl >= 2.2 && < 2.4 , nova-cache >= 0.2.4 && < 0.3+ , primitive >= 0.7 && < 1 , process >= 1.6 && < 1.7 , regex-tdfa >= 1.3 && < 1.4 , sqlite-simple >= 0.4 && < 0.5@@ -127,6 +129,7 @@ , directory >= 1.3 && < 1.4 , filepath >= 1.4 && < 1.6 , nova-nix+ , primitive >= 0.7 && < 1 , process >= 1.6 && < 1.7 , text >= 2.0 && < 2.2
src/Nix/Builtins.hs view
@@ -36,16 +36,19 @@ builtinEnv :: Integer -> [Thunk] -> Env builtinEnv timestamp searchPaths = Env- { envBindings =- Map.fromList $- -- Values- [ ("true", evaluated (VBool True)),- ("false", evaluated (VBool False)),- ("null", evaluated VNull),- ("builtins", evaluated (builtinsAttrSet timestamp searchPaths))- ]- -- Top-level builtin functions (available without builtins. prefix)- ++ map topLevelBuiltin topLevelBuiltinNames,+ { envSlots = mempty,+ envLazyScope =+ Just $+ attrSetFromMap $+ Map.fromList $+ -- Values+ [ ("true", evaluated (VBool True)),+ ("false", evaluated (VBool False)),+ ("null", evaluated VNull),+ ("builtins", evaluated (builtinsAttrSet timestamp searchPaths))+ ]+ -- Top-level builtin functions (available without builtins. prefix)+ ++ map topLevelBuiltin topLevelBuiltinNames, envParent = Nothing, envWithScopes = [] }@@ -82,7 +85,7 @@ builtinEnvWithScope timestamp searchPaths scope = let base = builtinEnv timestamp searchPaths scopeMap = Map.fromList scope- in Env {envBindings = scopeMap, envParent = Just base, envWithScopes = []}+ in Env {envSlots = mempty, envLazyScope = Just (attrSetFromMap scopeMap), envParent = Just base, envWithScopes = []} -- | The @builtins@ attribute set, derived from the central registry. builtinsAttrSet :: Integer -> [Thunk] -> NixValue
src/Nix/Eval.hs view
@@ -13,6 +13,7 @@ module Nix.Eval ( -- * Values (re-exported from Types) NixValue (..),+ CompiledRegex (..), Thunk (..), ThunkCell (..), @@ -27,6 +28,7 @@ attrSetMember, attrSetElems, attrSetNull,+ attrSetRemoveKeys, attrSetSize, -- * String context (re-exported from Types)@@ -68,11 +70,12 @@ import qualified Data.ByteArray as BA import qualified Data.ByteString as BS import Data.Char (chr, digitToInt, isAlpha, isDigit, isHexDigit, isOctDigit, ord)+import Data.IORef (IORef, atomicModifyIORef', newIORef) import Data.List (find, foldl')-import qualified Data.Map.Lazy as MapL import Data.Map.Strict (Map) import qualified Data.Map.Strict as Map import Data.Maybe (catMaybes, fromMaybe, isJust, isNothing)+import Data.Primitive.SmallArray (smallArrayFromListN) import Data.Sequence (Seq (..)) import qualified Data.Sequence as Seq import qualified Data.Set as Set@@ -85,6 +88,7 @@ import Nix.Eval.StringInterp (coerceToString, evalIndStringParts, evalStringParts) import Nix.Eval.Types ( AttrSet (..),+ CompiledRegex (..), Env (..), LazyBinding (..), MonadEval (..),@@ -98,19 +102,19 @@ attrSetFromMap, attrSetKeys, attrSetLookup,- attrSetMapWithKey,+ attrSetMapWithKeyLazy, attrSetMember, attrSetNull,+ attrSetRemoveKeys, attrSetSize, attrSetToAscList, attrSetToMap, attrSetUnionWith, emptyContext, emptyEnv,- envInsert,- envInsertMany,- envInsertThunk,+ envFromSlots, envLookup,+ envLookupResolved, evaluated, mkStr, mkSyntheticThunk,@@ -134,6 +138,7 @@ import Nix.Store.Path (StorePath (..), defaultStoreDir, defaultStoreDirText, parseStorePath, storePathToFilePath) import qualified NovaCache.Base32 as Nix32 import qualified NovaCache.Base64 as B64+import System.IO.Unsafe (unsafePerformIO) import qualified System.Info import Text.Regex.TDFA (matchAllText) import qualified Text.Regex.TDFA as RE@@ -145,6 +150,7 @@ EStr parts -> uncurry VStr <$> evalStringParts eval force applyValue env parts EIndStr parts -> uncurry VStr <$> evalIndStringParts eval force applyValue env parts EVar name -> evalVar env name+ EResolvedVar level idx -> force (envLookupResolved level idx env) EAttrs isRec bindings -> evalAttrs env isRec bindings EList exprs -> pure (VList (map (mkThunk env) exprs)) ESelect target path defExpr -> evalSelect env target path defExpr@@ -250,33 +256,32 @@ -- Uses 'LazyAttrs' to defer thunk + IORef allocation: only keys that -- are actually accessed get materialized. For nixpkgs' 30k-entry -- package set, this avoids ~30k IORef allocations when only ~50--- packages are touched. The env uses Data.Map.Lazy to similarly--- defer thunk construction for variable lookups within the rec set.+-- packages are touched.+--+-- The env's 'envLazyScope' points to the SAME 'LazyAttrs' that backs+-- the resulting attr set — one map instead of two. Variable lookup+-- and attr set access share a single materialization cache, eliminating+-- the dual-map space leak where both a lazy Thunk map and a LazyBinding+-- map retained the entire recursive environment. evalRecAttrs :: (MonadEval m) => Env -> [Binding] -> m NixValue evalRecAttrs env bindings = do -- Resolve dynamic keys eagerly against the outer env. resolvedBindings <- resolveBindingKeys env bindings- -- Knot-tied: recEnv references recBindings which captures recEnv.- -- Lazy-valued map for env bindings — uses Data.Map.Lazy so thunks- -- are stored as unevaluated closures, deferring IORef allocation- -- until the variable is actually looked up.- -- Scope chain: recEnv has rec bindings locally, outer env as parent.- -- Avoids O(n) MapL.union on the 30k-entry nixpkgs set — parent- -- pointer means outer bindings are shared, not copied.+ -- Knot-tied: recEnv references attrSet (via envLazyScope) which+ -- references lazyBindingMap which captures recEnv lazily inside+ -- each LazyBinding. The map structure is built from resolvedBindings+ -- (already resolved), not from recEnv. let recEnv = Env- { envBindings = recBindings,+ { envSlots = mempty,+ envLazyScope = Just attrSet, envParent = Just env, envWithScopes = envWithScopes env }- -- INTENTIONALLY uses Data.Map.Lazy operations to defer thunk- -- construction. Each map value is a closure that allocates- -- a Thunk + IORef only when forced by variable lookup.- recBindings = buildResolvedBindingsMapLazy recEnv resolvedBindings- -- Build per-key lazy binding recipes for the LazyAttrs. lazyBindingMap = buildLazyBindingMap recEnv resolvedBindings cache = newLazyAttrCache lazyBindingMap- pure (VAttrs (LazyAttrs lazyBindingMap cache))+ attrSet = LazyAttrs lazyBindingMap cache+ pure (VAttrs attrSet) -- --------------------------------------------------------------------------- -- Resolved bindings (for knot-tying in rec {} and let)@@ -309,38 +314,6 @@ resolveOne (Inherit (Just fromExpr) names) = pure (Just (ResolvedInheritFrom fromExpr names)) --- | Like 'buildResolvedBindingsMap' but uses 'Data.Map.Lazy' operations--- so that thunk values are stored as unevaluated closures. This defers--- 'mkThunk' + IORef allocation until the key is actually accessed.--- Used by 'evalRecAttrs' and 'evalLet' for the env bindings.-buildResolvedBindingsMapLazy :: Env -> [ResolvedBinding] -> Map Text Thunk-buildResolvedBindingsMapLazy thunkEnv =- foldl' mergeBindingLazy MapL.empty- where- mergeBindingLazy current binding =- MapL.unionWith mergeThunks current (processResolvedLazy thunkEnv binding)---- | Like 'processResolved' but uses 'Data.Map.Lazy' operations--- to avoid forcing thunk values on map insertion.-processResolvedLazy :: Env -> ResolvedBinding -> Map Text Thunk-processResolvedLazy thunkEnv (ResolvedNamed path bodyExpr) =- buildResolvedNestedAttrLazy thunkEnv path bodyExpr-processResolvedLazy lookupEnv (ResolvedInherit names) =- MapL.fromList [(n, inheritLookup lookupEnv n) | n <- names]-processResolvedLazy thunkEnv (ResolvedInheritFrom fromExpr names) =- MapL.fromList- [ (n, mkThunk thunkEnv (ESelect fromExpr [StaticKey n] Nothing))- | n <- names- ]---- | Like 'buildResolvedNestedAttr' but uses 'Data.Map.Lazy' operations.-buildResolvedNestedAttrLazy :: Env -> [Text] -> Expr -> Map Text Thunk-buildResolvedNestedAttrLazy _thunkEnv [] _bodyExpr = Map.empty-buildResolvedNestedAttrLazy thunkEnv [key] bodyExpr =- MapL.singleton key (mkThunk thunkEnv bodyExpr)-buildResolvedNestedAttrLazy thunkEnv (key : rest) bodyExpr =- MapL.singleton key (evaluated (VAttrs (attrSetFromMap (buildResolvedNestedAttrLazy thunkEnv rest bodyExpr))))- -- | Build per-key lazy binding recipes from resolved bindings. -- Simple @key = expr@ bindings become 'LazyExpr' (deferred thunk -- construction). Nested paths and inherits fall back to 'PreBuilt'@@ -509,32 +482,36 @@ _ -> throwEvalError ("attempt to call " <> typeName funcVal <> ", which is not a function") -- | Match function formals against an argument thunk.+--+-- Builds a positional slot list matching the indices assigned by+-- 'Nix.Expr.Resolve':+--+-- * @FormalName n@ → @[argThunk]@+-- * @FormalSet [a, b, c] _@ → @[aThunk, bThunk, cThunk]@+-- * @FormalNamedSet n [a, b, c] _@ → @[argThunk, aThunk, bThunk, cThunk]@ matchFormals :: (MonadEval m) => Env -> Formals -> Thunk -> m Env-matchFormals closureEnv (FormalName name) argThunk =- pure (envInsertThunk name argThunk closureEnv)+matchFormals closureEnv (FormalName _) argThunk =+ pure (envFromSlots (smallArrayFromListN 1 [argThunk]) closureEnv) matchFormals closureEnv (FormalSet formals allowExtra) argThunk = do argVal <- force argThunk- matchFormalSet closureEnv formals allowExtra argVal-matchFormals closureEnv (FormalNamedSet name formals allowExtra) argThunk = do+ matchFormalSet closureEnv formals allowExtra argVal Nothing+matchFormals closureEnv (FormalNamedSet _ formals allowExtra) argThunk = do argVal <- force argThunk- -- Bind the @-pattern name (e.g. "args") BEFORE matching formals so that- -- default expressions like @system ? args.system or ...@ can see it.- let envWithAt = envInsertThunk name argThunk closureEnv- matchFormalSet envWithAt formals allowExtra argVal+ -- Pass the @-pattern thunk so it goes into slot 0 of the combined env.+ matchFormalSet closureEnv formals allowExtra argVal (Just argThunk) -- | Match a formal set pattern against a VAttrs argument. ----- All formals are batched into a SINGLE scope level (one Map, one Env)--- instead of creating a separate singleton Env per formal. This reduces--- Env allocations from O(N) to O(1) per function call — critical for--- nixpkgs where millions of function calls with 5–30 formals each were--- creating 7M+ Env objects and 600+ MB of Map.Bin nodes.+-- All formals are batched into a SINGLE scope level (one slot list)+-- instead of creating a separate Map per formal. This replaces+-- Map.Bin nodes (48 bytes each) with list cons cells (16 bytes each)+-- and eliminates Text key storage entirely. -- -- Default expressions use formalEnv via knot-tying, so they can -- reference other formals — matching real Nix semantics where all -- formals are mutually visible (e.g. @{ a ? b, b ? 1 }: a@ yields 1).-matchFormalSet :: (MonadEval m) => Env -> [Formal] -> Bool -> NixValue -> m Env-matchFormalSet closureEnv formals allowExtra argVal =+matchFormalSet :: (MonadEval m) => Env -> [Formal] -> Bool -> NixValue -> Maybe Thunk -> m Env+matchFormalSet closureEnv formals allowExtra argVal atThunk = case argVal of VAttrs attrs -> do checkExtraKeys formals allowExtra attrs@@ -544,12 +521,12 @@ -- Batch all formal bindings into ONE scope level. -- Knot-tying: formalEnv is used in mkThunk for defaults, -- but mkThunk captures Env lazily (Pending !Expr Env).- let formalEnv = envInsertMany formalBindings closureEnv- formalBindings =- Map.fromList- [ (fName formal, resolveOneFormal formal)- | formal <- formals- ]+ let formalEnv = envFromSlots formalSlots closureEnv+ formalSlots = case atThunk of+ Nothing ->+ smallArrayFromListN (length formals) (map resolveOneFormal formals)+ Just at ->+ smallArrayFromListN (length formals + 1) (at : map resolveOneFormal formals) resolveOneFormal (Formal name defExpr) = case attrSetLookup name attrs of Just thunk -> thunk@@ -588,20 +565,20 @@ -- Dynamic keys in let evaluate against the outer env (the let env -- is not yet available during key resolution). ----- Uses Data.Map.Lazy for env bindings to defer thunk construction.+-- Uses 'envLazyScope' to share the same 'LazyAttrs' as evalRecAttrs,+-- eliminating the dual-map space leak. evalLet :: (MonadEval m) => Env -> [Binding] -> Expr -> m NixValue evalLet env bindings body = do resolvedBindings <- resolveBindingKeys env bindings- -- Scope chain: let bindings as local scope, outer env as parent. let letEnv = Env- { envBindings = letBindings,+ { envSlots = mempty,+ envLazyScope = Just (LazyAttrs lazyBindingMap cache), envParent = Just env, envWithScopes = envWithScopes env }- -- INTENTIONALLY uses Data.Map.Lazy operations to defer thunk- -- construction, matching evalRecAttrs.- letBindings = buildResolvedBindingsMapLazy letEnv resolvedBindings+ lazyBindingMap = buildLazyBindingMap letEnv resolvedBindings+ cache = newLazyAttrCache lazyBindingMap eval letEnv body evalIf :: (MonadEval m) => Env -> Expr -> Expr -> Expr -> m NixValue@@ -876,9 +853,27 @@ let allArgs = accArgs ++ [arg] arity = builtinArity name in if length allArgs < arity- then pure (VBuiltin name allArgs)+ then pure (VBuiltin name (precompileArgs name allArgs)) else executeBuiltin name allArgs +-- | Pre-compile regex patterns at partial application time.+-- When builtins.match or builtins.split receives its first argument+-- (the pattern string), compile it immediately and store the compiled+-- RE.Regex in a VCompiledRegex, replacing the raw VStr. The compiled+-- form is carried in VBuiltin's accumulated args and reused on every+-- subsequent application — zero recompilation.+precompileArgs :: Text -> [NixValue] -> [NixValue]+precompileArgs "match" [VStr pat _] =+ let anchored = "^" <> pat <> "$"+ in case cachedCompileRegex anchored of+ Just compiled -> [VCompiledRegex (CompiledRegex pat compiled)]+ Nothing -> [VStr pat emptyContext] -- fail later at execute time+precompileArgs "split" [VStr pat _] =+ case cachedCompileRegex pat of+ Just compiled -> [VCompiledRegex (CompiledRegex pat compiled)]+ Nothing -> [VStr pat emptyContext] -- fail later at execute time+precompileArgs _ args = args+ -- | Apply a function value (lambda or builtin) to one argument. -- Used by higher-order builtins to invoke user-supplied functions. applyValue :: (MonadEval m) => NixValue -> NixValue -> m NixValue@@ -1065,6 +1060,7 @@ VLambda {} -> "lambda" VBuiltin _ _ -> "lambda" VDerivation _ -> "set"+ VCompiledRegex _ -> "lambda" isNullVal :: NixValue -> Bool isNullVal VNull = True@@ -1201,8 +1197,7 @@ builtinRemoveAttrs :: (MonadEval m) => NixValue -> NixValue -> m NixValue builtinRemoveAttrs (VAttrs attrs) (VList thunks) = do keys <- mapM forceToString thunks- let m = attrSetToMap attrs- pure (VAttrs (attrSetFromMap (foldl' (flip Map.delete) m keys)))+ pure (VAttrs (attrSetRemoveKeys keys attrs)) where forceToString thunk = do val <- force thunk@@ -1284,9 +1279,10 @@ | n < 0 = throwEvalError "builtins.genList: length must be non-negative" | otherwise = -- Lazy: each element is a deferred @f i@, forced only on demand.+ -- Slot 0 = function. let fnThunk = evaluated func- env = Env {envBindings = Map.fromList [("__fn", fnThunk)], envParent = Nothing, envWithScopes = []}- mkIndexThunk i = mkThunk env (EApp (EVar "__fn") (ELit (NixInt i)))+ env = Env {envSlots = smallArrayFromListN 1 [fnThunk], envLazyScope = Nothing, envParent = Nothing, envWithScopes = []}+ mkIndexThunk i = mkThunk env (EApp (EResolvedVar 0 0) (ELit (NixInt i))) in pure (VList (map mkIndexThunk [0 .. n - 1])) builtinGenList _ other = throwEvalError ("builtins.genList: expected an integer, got " <> typeName other)@@ -1518,21 +1514,24 @@ -- | Build a thunk that defers @f arg@ — the application only happens when -- the thunk is forced. Reuses the existing eval machinery via a synthetic--- @EApp (EVar "__fn") (EVar "__arg")@ in a self-contained env.+-- @EApp (EResolvedVar 0 0) (EResolvedVar 0 1)@ in a self-contained env.+-- Slot 0 = function, slot 1 = argument. deferApply :: NixValue -> Thunk -> Thunk deferApply func argThunk = let env = Env- { envBindings =- Map.fromList- [ ("__fn", evaluated func),- ("__arg", argThunk)- ],+ { envSlots = smallArrayFromListN 2 [evaluated func, argThunk],+ envLazyScope = Nothing, envParent = Nothing, envWithScopes = [] }- in mkSyntheticThunk env (EApp (EVar "__fn") (EVar "__arg"))+ in mkSyntheticThunk env deferApplyExpr +-- | Shared expression for 'deferApply'. Allocated once as a CAF.+deferApplyExpr :: Expr+deferApplyExpr = EApp (EResolvedVar 0 0) (EResolvedVar 0 1)+{-# NOINLINE deferApplyExpr #-}+ -- | Permissive coercion used by @builtins.toString@. -- -- Like 'coerceToString' but additionally handles lists: elements are@@ -1822,24 +1821,28 @@ builtinMapAttrs :: (MonadEval m) => NixValue -> NixValue -> m NixValue builtinMapAttrs func (VAttrs attrs) = -- Lazy: each attr value is a deferred @f key val@, forced only on demand.- pure (VAttrs (attrSetMapWithKey deferAttr attrs))+ -- Uses attrSetMapWithKeyLazy to avoid materializing all bindings in+ -- LazyAttrs — each entry stays as a PreBuilt recipe until accessed.+ -- Slot 0 = function, slot 1 = key, slot 2 = value.+ pure (VAttrs (attrSetMapWithKeyLazy deferAttr attrs)) where deferAttr key valThunk = let env = Env- { envBindings =- Map.fromList- [ ("__fn", evaluated func),- ("__key", evaluated (mkStr key)),- ("__val", valThunk)- ],+ { envSlots = smallArrayFromListN 3 [evaluated func, evaluated (mkStr key), valThunk],+ envLazyScope = Nothing, envParent = Nothing, envWithScopes = [] }- in mkSyntheticThunk env (EApp (EApp (EVar "__fn") (EVar "__key")) (EVar "__val"))+ in mkSyntheticThunk env mapAttrsExpr builtinMapAttrs _ other = throwEvalError ("builtins.mapAttrs: expected a set, got " <> typeName other) +-- | Shared expression for 'builtinMapAttrs'. Allocated once as a CAF.+mapAttrsExpr :: Expr+mapAttrsExpr = EApp (EApp (EResolvedVar 0 0) (EResolvedVar 0 1)) (EResolvedVar 0 2)+{-# NOINLINE mapAttrsExpr #-}+ builtinFunctionArgs :: (MonadEval m) => NixValue -> m NixValue builtinFunctionArgs (VLambda _ formals _) = pure (formalsToAttrs formals) builtinFunctionArgs (VBuiltin _ _) = pure (VAttrs (attrSetFromMap Map.empty))@@ -1869,9 +1872,17 @@ -- the original function. The function is captured in the closure env. builtinSetFunctionArgs :: (MonadEval m) => NixValue -> NixValue -> m NixValue builtinSetFunctionArgs func (VAttrs argSpec) =- let closureEnv = envInsert "__fn" func emptyEnv+ -- Closure env holds the function at slot 0. The __functor lambda+ -- body is EResolvedVar 1 0: level 1 (past _self's slot), index 0.+ let closureEnv =+ Env+ { envSlots = smallArrayFromListN 1 [evaluated func],+ envLazyScope = Nothing,+ envParent = Nothing,+ envWithScopes = []+ } -- __functor = self: __fn (ignores self, returns the original function)- functorLambda = VLambda closureEnv (FormalName "_self") (EVar "__fn")+ functorLambda = VLambda closureEnv (FormalName "_self") (EResolvedVar 1 0) in pure $ VAttrs $ attrSetFromMap $@@ -1961,51 +1972,100 @@ -- Builtin implementations — regex (POSIX ERE via regex-tdfa) -- --------------------------------------------------------------------------- +-- ---------------------------------------------------------------------------+-- Regex compilation cache+-- ---------------------------------------------------------------------------++-- | Global regex compilation cache. Keyed by the raw pattern string+-- (including anchoring for match). Idempotent memoization via+-- unsafePerformIO — same rationale as thunk memoization.+{-# NOINLINE regexCacheRef #-}+regexCacheRef :: IORef (Map Text RE.Regex)+regexCacheRef = unsafePerformIO (newIORef Map.empty)++-- | Compile a regex, using the global cache to avoid recompilation.+-- Returns Nothing for invalid patterns. NOINLINE prevents GHC from+-- inlining and floating the unsafePerformIO reads.+{-# NOINLINE cachedCompileRegex #-}+cachedCompileRegex :: Text -> Maybe RE.Regex+cachedCompileRegex pat =+ unsafePerformIO $ do+ cache <- atomicModifyIORef' regexCacheRef (\c -> (c, c))+ case Map.lookup pat cache of+ Just compiled -> pure (Just compiled)+ Nothing -> case RE.makeRegexM (T.unpack pat) :: Maybe RE.Regex of+ Nothing -> pure Nothing+ Just compiled -> do+ atomicModifyIORef' regexCacheRef (\c -> (Map.insert pat compiled c, ()))+ pure (Just compiled)++-- ---------------------------------------------------------------------------+-- Regex builtins+-- ---------------------------------------------------------------------------+ -- | @builtins.match regex str@: match a POSIX ERE against a string. -- The regex is implicitly anchored (must match the entire string). -- Returns @null@ if no match, or a list of capture group strings -- (empty string for unmatched optional groups). builtinMatch :: (MonadEval m) => NixValue -> NixValue -> m NixValue-builtinMatch (VStr regex _) (VStr str _) = do- let anchored = "^" <> T.unpack regex <> "$"- case RE.makeRegexM anchored :: Maybe RE.Regex of- Nothing ->- throwEvalError ("builtins.match: invalid regex: " <> regex)- Just compiled ->- let matches = matchAllText compiled (T.unpack str)- in case matches of- [] -> pure VNull- (match : _) ->- -- match is an Array of (String, (offset, len)) pairs.- -- Index 0 is the full match; indices 1.. are capture groups.- let groups = Array.elems match- -- Skip index 0 (full match) — return only capture groups.- captureGroups = drop 1 groups- toThunk (s, _) = evaluated (mkStr (T.pack s))- in pure (VList (map toThunk captureGroups))+-- Pre-compiled path: regex was compiled at partial-application time.+builtinMatch (VCompiledRegex (CompiledRegex _ compiled)) (VStr str _) =+ matchWithCompiled compiled str+-- Direct 2-arg call: use global compilation cache.+builtinMatch (VStr regex _) (VStr str _) =+ let anchored = "^" <> regex <> "$"+ in case cachedCompileRegex anchored of+ Nothing -> throwEvalError ("builtins.match: invalid regex: " <> regex)+ Just compiled -> matchWithCompiled compiled str builtinMatch (VStr _ _) other = throwEvalError ("builtins.match: expected a string, got " <> typeName other)+builtinMatch (VCompiledRegex _) other =+ throwEvalError ("builtins.match: expected a string, got " <> typeName other) builtinMatch other _ = throwEvalError ("builtins.match: expected a string (regex), got " <> typeName other) +-- | Shared match logic for pre-compiled and freshly-compiled regex paths.+matchWithCompiled :: (MonadEval m) => RE.Regex -> Text -> m NixValue+matchWithCompiled compiled str =+ let matches = matchAllText compiled (T.unpack str)+ in case matches of+ [] -> pure VNull+ (match : _) ->+ -- match is an Array of (String, (offset, len)) pairs.+ -- Index 0 is the full match; indices 1.. are capture groups.+ let groups = Array.elems match+ -- Skip index 0 (full match) — return only capture groups.+ captureGroups = drop 1 groups+ toThunk (s, _) = evaluated (mkStr (T.pack s))+ in pure (VList (map toThunk captureGroups))+ -- | @builtins.split regex str@: split a string by a POSIX ERE. -- Returns an alternating list of non-matched strings and match-group lists. -- Example: @split "(x)" "axbxc"@ → @["a" ["x"] "b" ["x"] "c"]@ builtinSplit :: (MonadEval m) => NixValue -> NixValue -> m NixValue-builtinSplit (VStr regex _) (VStr str _) = do- case RE.makeRegexM (T.unpack regex) :: Maybe RE.Regex of- Nothing ->- throwEvalError ("builtins.split: invalid regex: " <> regex)- Just compiled ->- let allMatches = matchAllText compiled (T.unpack str)- strText = T.unpack str- result = buildSplitResult strText 0 allMatches- in pure (VList result)+-- Pre-compiled path: regex was compiled at partial-application time.+builtinSplit (VCompiledRegex (CompiledRegex _ compiled)) (VStr str _) =+ splitWithCompiled compiled str+-- Direct 2-arg call: use global compilation cache.+builtinSplit (VStr regex _) (VStr str _) =+ case cachedCompileRegex regex of+ Nothing -> throwEvalError ("builtins.split: invalid regex: " <> regex)+ Just compiled -> splitWithCompiled compiled str builtinSplit (VStr _ _) other = throwEvalError ("builtins.split: expected a string, got " <> typeName other)+builtinSplit (VCompiledRegex _) other =+ throwEvalError ("builtins.split: expected a string, got " <> typeName other) builtinSplit other _ = throwEvalError ("builtins.split: expected a string (regex), got " <> typeName other) +-- | Shared split logic for pre-compiled and freshly-compiled regex paths.+splitWithCompiled :: (MonadEval m) => RE.Regex -> Text -> m NixValue+splitWithCompiled compiled str =+ let allMatches = matchAllText compiled (T.unpack str)+ strText = T.unpack str+ result = buildSplitResult strText 0 allMatches+ in pure (VList result)+ -- | Build the alternating list for builtins.split. buildSplitResult :: String -> Int -> [Array.Array Int (String, (Int, Int))] -> [Thunk] buildSplitResult remaining pos [] =@@ -2164,6 +2224,7 @@ valueToJSON (VLambda {}) = throwEvalError "builtins.toJSON: cannot convert a function to JSON" valueToJSON (VBuiltin _ _) = throwEvalError "builtins.toJSON: cannot convert a function to JSON" valueToJSON (VDerivation _) = throwEvalError "builtins.toJSON: cannot convert a derivation to JSON"+valueToJSON (VCompiledRegex _) = throwEvalError "builtins.toJSON: cannot convert a function to JSON" jsonEscapeString :: Text -> Text jsonEscapeString s = "\"" <> T.concatMap escapeChar s <> "\""@@ -2708,8 +2769,11 @@ VList thunks -> mapM forceToText thunks _ -> throwEvalError "derivation: 'args' must be a list of strings" + -- Materialize once, reuse for both env collection and result merge+ let materialized = attrSetToMap attrs+ -- Collect all string-coercible attrs into env WITH their contexts- (drvEnvPairs, envContext) <- collectDrvEnvWithContext (attrSetToMap attrs)+ (drvEnvPairs, envContext) <- collectDrvEnvWithContext materialized -- Extract input derivations and input sources from the merged context let inputDrvs = extractInputDrvs envContext@@ -2789,7 +2853,7 @@ ] ++ [(outName, evaluated (VStr outP (outPathCtx outName))) | (outName, outP) <- outPaths] -- Merge original attrs underneath so computed attrs take priority- resultAttrs = Map.union baseAttrs (attrSetToMap attrs)+ resultAttrs = Map.union baseAttrs materialized pure (VAttrs (attrSetFromMap resultAttrs)) builtinDerivation other =@@ -3446,6 +3510,8 @@ pure (indent depth <> "<function />\n") VDerivation _ -> pure (indent depth <> "<derivation />\n")+ VCompiledRegex _ ->+ pure (indent depth <> "<function />\n") where attrToXML d (name, thunk) = do v <- force thunk
src/Nix/Eval/IO.hs view
@@ -41,7 +41,7 @@ import Data.Time.Clock.POSIX (getPOSIXTime) import Nix.Builtins (builtinEnv, builtinEnvWithScope, parseNixPath) import Nix.Eval (eval)-import Nix.Eval.Types (MonadEval (..), NixValue (..), Thunk (..), ThunkCell (..))+import Nix.Eval.Types (MonadEval (..), NixValue (..), Thunk (..), ThunkCell (..), attrSetSize) import Nix.Expr.Types (AttrKey (..), Binding (..), Expr (..), Formal (..), Formals (..), NixAtom (..), StringPart (..)) import Nix.Hash (sha256Hex, truncatedBase32) import Nix.Parser (parseNix)@@ -169,7 +169,15 @@ (unEvalIO (eval (builtinEnv timestamp searchPaths) expr)) ) result <- nested- wrapIO (modifyIORef' cacheRef (Map.insert target result))+ -- Skip caching very large attr sets (e.g. all-packages.nix+ -- with 30k+ entries) so GC can reclaim them. nixpkgs only+ -- imports all-packages.nix once at the top level, so skipping+ -- the cache for it has zero performance cost.+ let shouldCache = case result of+ VAttrs attrs -> attrSetSize attrs < importCacheMaxAttrs+ _ -> True+ when shouldCache $+ wrapIO (modifyIORef' cacheRef (Map.insert target result)) pure result getEnvVar name = wrapIO $ do@@ -271,6 +279,16 @@ pure val -- ---------------------------------------------------------------------------+-- Constants+-- ---------------------------------------------------------------------------++-- | Maximum attribute set size for import caching. Results larger than this+-- are not cached, allowing GC to reclaim them. Prevents the import cache+-- from retaining huge attr sets like nixpkgs' 30k-entry all-packages.nix.+importCacheMaxAttrs :: Int+importCacheMaxAttrs = 1000++-- --------------------------------------------------------------------------- -- Helpers -- --------------------------------------------------------------------------- @@ -349,6 +367,7 @@ EStr parts -> EStr (map goPart parts) EIndStr parts -> EIndStr (map goPart parts) EVar _ -> expr+ EResolvedVar _ _ -> expr EAttrs isRec bindings -> EAttrs isRec (map goBinding bindings) EList elems -> EList (map goExpr elems) ESelect target path mDef ->
src/Nix/Eval/Types.hs view
@@ -8,6 +8,7 @@ module Nix.Eval.Types ( -- * Values NixValue (..),+ CompiledRegex (..), Thunk (..), ThunkCell (..), @@ -24,6 +25,8 @@ attrSetElems, attrSetToAscList, attrSetMapWithKey,+ attrSetMapWithKeyLazy,+ attrSetRemoveKeys, attrSetUnionWith, newLazyAttrCache, @@ -37,9 +40,8 @@ Env (..), emptyEnv, envLookup,- envInsert,- envInsertThunk,- envInsertMany,+ envLookupResolved,+ envFromSlots, pushWithScope, -- * Thunk operations@@ -59,16 +61,35 @@ import Data.ByteString (ByteString) import Data.IORef (IORef, atomicModifyIORef', newIORef, readIORef)+import Data.List (foldl') import Data.Map.Strict (Map) import qualified Data.Map.Strict as Map+import Data.Primitive.SmallArray (SmallArray, indexSmallArray, sizeofSmallArray) import Data.Set (Set) import Data.Text (Text) import Nix.Derivation (Derivation) import Nix.Expr.Types (AttrKey (..), Expr (..), Formals, StringPart (..)) import Nix.Store.Path (StorePath) import System.IO.Unsafe (unsafePerformIO)+import qualified Text.Regex.TDFA as RE -- ---------------------------------------------------------------------------+-- Compiled regex+-- ---------------------------------------------------------------------------++-- | Compiled regex with Eq/Show based on source pattern text.+-- Carries the pre-compiled 'RE.Regex' alongside the original pattern+-- so that partial application of @builtins.match@ / @builtins.split@+-- avoids recompiling the same pattern on every invocation.+data CompiledRegex = CompiledRegex !Text RE.Regex++instance Eq CompiledRegex where+ CompiledRegex a _ == CompiledRegex b _ = a == b++instance Show CompiledRegex where+ show (CompiledRegex pat _) = "CompiledRegex " <> show pat++-- --------------------------------------------------------------------------- -- String context -- --------------------------------------------------------------------------- @@ -161,6 +182,9 @@ | -- | Built-in function, dispatched by name. -- Accumulated args support curried partial application. VBuiltin !Text ![NixValue]+ | -- | Pre-compiled regex carried in a partially-applied builtin.+ -- Internal only — never exposed to Nix code directly.+ VCompiledRegex !CompiledRegex deriving (Eq, Show) -- ---------------------------------------------------------------------------@@ -317,6 +341,27 @@ attrSetMapWithKey :: (Text -> Thunk -> Thunk) -> AttrSet -> AttrSet attrSetMapWithKey f attrs = EagerAttrs (Map.mapWithKey f (attrSetToMap attrs)) +-- | Like 'attrSetMapWithKey' but preserves laziness for 'LazyAttrs'.+-- Each binding is wrapped in 'PreBuilt' so that materialization (IORef+-- allocation) only happens when a specific key is accessed. This avoids+-- ~30k IORef allocations when @mapAttrs@ is applied to a large set (e.g.+-- nixpkgs overlays) and only a few keys are actually demanded.+attrSetMapWithKeyLazy :: (Text -> Thunk -> Thunk) -> AttrSet -> AttrSet+attrSetMapWithKeyLazy f (EagerAttrs m) = EagerAttrs (Map.mapWithKey f m)+attrSetMapWithKeyLazy f (LazyAttrs bindings _cache) =+ let mapped = Map.mapWithKey (\k recipe -> PreBuilt (f k (materializeBinding k recipe))) bindings+ in LazyAttrs mapped (newLazyAttrCache mapped)++-- | Remove a list of keys from an attribute set without materializing+-- 'LazyAttrs'. For 'EagerAttrs', deletes from the map directly.+-- For 'LazyAttrs', deletes from the binding map and creates a fresh cache.+attrSetRemoveKeys :: [Text] -> AttrSet -> AttrSet+attrSetRemoveKeys keys (EagerAttrs m) =+ EagerAttrs (foldl' (flip Map.delete) m keys)+attrSetRemoveKeys keys (LazyAttrs bindings _cache) =+ let newBindings = foldl' (flip Map.delete) bindings keys+ in LazyAttrs newBindings (newLazyAttrCache newBindings)+ -- | Union two attribute sets with a combining function (materializes both). attrSetUnionWith :: (Thunk -> Thunk -> Thunk) -> AttrSet -> AttrSet -> AttrSet attrSetUnionWith f a b = EagerAttrs (Map.unionWith f (attrSetToMap a) (attrSetToMap b))@@ -332,20 +377,25 @@ newLazyAttrCache :: Map Text LazyBinding -> IORef (Map Text Thunk) newLazyAttrCache bindings = unsafePerformIO (bindings `seq` newIORef Map.empty) --- | Evaluation environment — scope chain.+-- | Evaluation environment — scope chain with positional slots. ----- Each Env holds only its LOCAL bindings and a parent pointer.--- Variable lookup walks the chain: local bindings first, then parent,--- then grandparent, etc. With-scopes are checked AFTER exhausting--- all lexical bindings in the chain (Nix: lexical always wins).+-- Lambda formals are stored in positional 'envSlots' (de Bruijn-style),+-- eliminating Map.Bin overhead. Let\/rec bindings and builtins use+-- name-based 'envLazyScope'. Variable lookup has two paths: ----- This avoids O(n) Map.union/insert when extending large envs (e.g.--- the 30k-entry nixpkgs rec set). A function application that adds--- 5 formals creates 5 singleton Maps instead of 5 copies of the--- 30k-entry map's internal Bin nodes.+-- * 'envLookupResolved': O(1) array index for 'EResolvedVar'+-- * 'envLookup': name-based walk for 'EVar' (envLazyScope + with-scopes) data Env = Env- { -- | Local lexical bindings at this scope level.- envBindings :: !(Map Text Thunk),+ { -- | Positional bindings for lambda formals.+ -- Indexed by position (0-based), filled by 'matchFormals'.+ -- O(1) lookup via 'indexSmallArray'. Empty for let/rec/builtin envs.+ envSlots :: !(SmallArray Thunk),+ -- | Lazy scope shared with a 'LazyAttrs' attr set.+ -- For rec {} and let, this points to the SAME 'LazyAttrs' that+ -- backs the resulting attr set — one map instead of two.+ -- For builtins, holds the top-level bindings (true, false, etc.).+ -- Variable lookup checks this for name-based 'EVar' lookups.+ envLazyScope :: !(Maybe AttrSet), -- | Parent scope (Nothing at the root). LAZY for knot-tying -- in rec {} where recEnv's parent is the outer env. envParent :: !(Maybe Env),@@ -354,18 +404,20 @@ envWithScopes :: ![AttrSet] } --- | Shallow comparison: checks local bindings and with-scopes only.+-- | Shallow comparison: checks slot count and with-scopes only. -- Ignores parent chain to avoid diverging on deep/recursive envs. -- Only used in tests on non-recursive structures. instance Eq Env where- Env b1 _ w1 == Env b2 _ w2 = b1 == b2 && w1 == w2+ Env s1 _ _ w1 == Env s2 _ _ w2 =+ sizeofSmallArray s1 == sizeofSmallArray s2 && w1 == w2 -- | Compact show: just the size and structure, not the full contents. instance Show Env where- show (Env bindings parent withs) =+ show (Env slots lazyScope parent withs) = "Env{"- ++ show (Map.size bindings)- ++ " local"+ ++ show (sizeofSmallArray slots)+ ++ " slots"+ ++ maybe "" (const ", lazyScope") lazyScope ++ maybe "" (const ", parent") parent ++ ", " ++ show (length withs)@@ -373,23 +425,38 @@ -- | Empty environment (no variables in scope). emptyEnv :: Env-emptyEnv = Env Map.empty Nothing []+emptyEnv = Env mempty Nothing Nothing [] --- | Look up a variable: walk the parent chain checking lexical--- bindings at each level; fall back to with-scopes (from the+-- | Look up a resolved variable by level and index. O(level) parent+-- hops, then O(1) array index via 'indexSmallArray'.+--+-- Unreachable branch: the resolution pass guarantees valid indices.+envLookupResolved :: Int -> Int -> Env -> Thunk+envLookupResolved 0 idx env = indexSmallArray (envSlots env) idx+envLookupResolved lvl idx env = case envParent env of+ Just parent -> envLookupResolved (lvl - 1) idx parent+ Nothing -> error "envLookupResolved: level exceeded (unreachable after resolution)"++-- | Name-based variable lookup: walk the parent chain checking+-- 'envLazyScope' at each level; fall back to with-scopes (from the -- starting env) only after exhausting all lexical scopes.+--+-- 'envSlots' are positional (no names) and are NOT searched here.+-- Used for 'EVar' lookups (let\/rec bindings, builtins, with-scopes). envLookup :: Text -> Env -> Maybe Thunk envLookup name env = lexicalLookup env where -- With-scopes from the STARTING env: these are the most recent -- and subsume all ancestor with-scopes (children inherit them). withs = envWithScopes env- lexicalLookup (Env bindings parent _) =- case Map.lookup name bindings of- Just val -> Just val- Nothing -> case parent of- Just p -> lexicalLookup p- Nothing -> lookupWithScopes name withs+ lexicalLookup (Env _slots lazyScope parent _) =+ case lazyScope of+ Just scope -> case attrSetLookup name scope of+ Just val -> Just val+ Nothing -> goParent parent+ Nothing -> goParent parent+ goParent (Just p) = lexicalLookup p+ goParent Nothing = lookupWithScopes name withs -- | Walk with-scopes innermost to outermost. -- Uses 'attrSetLookup' so that 'LazyAttrs' with-scopes only@@ -401,36 +468,15 @@ Just val -> Just val Nothing -> lookupWithScopes name rest --- | Insert an already-forced value as a new scope level.--- Creates a child env with a singleton Map — O(1) instead of--- O(log n) Map.insert on the parent's (potentially large) Map.-envInsert :: Text -> NixValue -> Env -> Env-envInsert name val env =- Env- { envBindings = Map.singleton name (Evaluated val),- envParent = Just env,- envWithScopes = envWithScopes env- }---- | Insert a thunk as a new scope level.-envInsertThunk :: Text -> Thunk -> Env -> Env-envInsertThunk name thunk env =- Env- { envBindings = Map.singleton name thunk,- envParent = Just env,- envWithScopes = envWithScopes env- }---- | Batch-insert multiple bindings as a single scope level.--- Creates ONE Env for all bindings instead of N singleton Envs.--- Used by formal set matching: a function with N formals creates--- one scope (one Map with N entries) instead of N scopes (N singleton Maps).-envInsertMany :: Map Text Thunk -> Env -> Env-envInsertMany bindings env =+-- | Create a child env with positional slots (for lambda formals).+-- Inherits with-scopes from the parent.+envFromSlots :: SmallArray Thunk -> Env -> Env+envFromSlots slots parent = Env- { envBindings = bindings,- envParent = Just env,- envWithScopes = envWithScopes env+ { envSlots = slots,+ envLazyScope = Nothing,+ envParent = Just parent,+ envWithScopes = envWithScopes parent } -- | Push a with-scope onto the scope chain (innermost position).@@ -453,16 +499,16 @@ ThunkRef (newMemoCell thunkExpr env) -- | Like 'mkThunk' but for synthetic thunks that reuse the same 'Expr'--- (e.g. @EApp (EVar "__fn") (EVar "__arg")@ in 'deferApply'). Uses the--- 'Env' bindings map for cell uniqueness instead of the expression, since--- GHC's full-laziness transform would otherwise float the shared expr to--- a CAF and all thunks would get the same IORef.+-- (e.g. @EApp (EResolvedVar 0 0) (EResolvedVar 0 1)@ in 'deferApply').+-- Uses the 'Env' slots list for cell uniqueness instead of the expression,+-- since GHC's full-laziness transform would otherwise float the shared+-- expr to a CAF and all thunks would get the same IORef. -- -- Must only be called with freshly-constructed envs (not knot-tied--- recursive envs), since it forces the bindings map to WHNF.+-- recursive envs), since it forces the slots list to WHNF. mkSyntheticThunk :: Env -> Expr -> Thunk mkSyntheticThunk env thunkExpr =- ThunkRef (newSyntheticCell (envBindings env) thunkExpr env)+ ThunkRef (newSyntheticCell (envSlots env) thunkExpr env) -- | Allocate a fresh memoization cell for a thunk. --@@ -478,11 +524,11 @@ newMemoCell :: Expr -> Env -> IORef ThunkCell newMemoCell expr env = unsafePerformIO (expr `seq` newIORef (Pending expr env)) --- | Like 'newMemoCell' but keyed on a bindings map instead of an expression.+-- | Like 'newMemoCell' but keyed on a SmallArray instead of an expression. -- Used by 'mkSyntheticThunk' where multiple thunks share the same expression. {-# NOINLINE newSyntheticCell #-}-newSyntheticCell :: Map Text Thunk -> Expr -> Env -> IORef ThunkCell-newSyntheticCell bindings expr env = unsafePerformIO (bindings `seq` newIORef (Pending expr env))+newSyntheticCell :: SmallArray Thunk -> Expr -> Env -> IORef ThunkCell+newSyntheticCell slots expr env = unsafePerformIO (slots `seq` newIORef (Pending expr env)) -- | Wrap an already-computed value as a thunk. evaluated :: NixValue -> Thunk@@ -510,6 +556,7 @@ VLambda {} -> "a function" VDerivation _ -> "a derivation" VBuiltin _ _ -> "a built-in function"+ VCompiledRegex _ -> "a built-in function" -- --------------------------------------------------------------------------- -- Evaluation monad
+ src/Nix/Expr/Resolve.hs view
@@ -0,0 +1,156 @@+-- | Variable resolution pass: replaces 'EVar' with 'EResolvedVar'+-- for variables bound by lambda formals.+--+-- Lambda formals get positional (de Bruijn-style) indices. Let\/rec+-- bindings act as name barriers (preventing resolution through them)+-- since they use 'envLazyScope' at runtime, which is already zero-cost.+-- With-scopes and builtins remain name-based.+--+-- Called once at parse time ('Nix.Parser.parseNix').+module Nix.Expr.Resolve+ ( resolveVars,+ )+where++import Data.List (foldl')+import Data.Map.Strict (Map)+import qualified Data.Map.Strict as Map+import Data.Set (Set)+import qualified Data.Set as Set+import Data.Text (Text)+import Nix.Expr.Types++-- | Scope entry for static variable resolution.+data ScopeEntry+ = -- | Lambda formals: name → positional index.+ LexicalScope !(Map Text Int)+ | -- | Let/rec binding names: blocks resolution (handled by name at runtime).+ NameBarrier !(Set Text)++-- | Resolve variables in an expression. Replaces 'EVar' with+-- 'EResolvedVar' where the variable is lexically bound by a lambda+-- formal. All other variables remain as 'EVar' for name-based lookup.+resolveVars :: Expr -> Expr+resolveVars = resolve []++-- | Walk the AST, maintaining a scope stack.+resolve :: [ScopeEntry] -> Expr -> Expr+resolve stack expr = case expr of+ ELit _ -> expr+ EStr parts -> EStr (map (resolvePart stack) parts)+ EIndStr parts -> EIndStr (map (resolvePart stack) parts)+ EVar name -> resolveVar stack 0 name+ EResolvedVar _ _ -> expr+ EAttrs True bindings ->+ -- Recursive: binding RHSes see their own names (as NameBarrier).+ let names = collectBindingNames bindings+ newStack = NameBarrier names : stack+ in EAttrs True (concatMap (resolveBinding newStack) bindings)+ EAttrs False bindings ->+ -- Non-recursive: bindings use the outer scope.+ EAttrs False (concatMap (resolveBinding stack) bindings)+ EList elems -> EList (map (resolve stack) elems)+ ESelect target path defExpr ->+ ESelect (resolve stack target) (map (resolveKey stack) path) (fmap (resolve stack) defExpr)+ EHasAttr target path ->+ EHasAttr (resolve stack target) (map (resolveKey stack) path)+ EApp f x -> EApp (resolve stack f) (resolve stack x)+ ELambda formals body ->+ let scope = lexicalScopeFromFormals formals+ newStack = scope : stack+ in ELambda (resolveFormalsDefaults newStack formals) (resolve newStack body)+ ELet bindings body ->+ -- Both body and binding RHSes see the let names (as NameBarrier).+ let names = collectBindingNames bindings+ newStack = NameBarrier names : stack+ in ELet (concatMap (resolveBinding newStack) bindings) (resolve newStack body)+ EIf c t f -> EIf (resolve stack c) (resolve stack t) (resolve stack f)+ EWith scope body ->+ -- with-scope names are unknown statically; no scope change.+ EWith (resolve stack scope) (resolve stack body)+ EAssert cond body ->+ EAssert (resolve stack cond) (resolve stack body)+ EUnary op operand -> EUnary op (resolve stack operand)+ EBinary op l r -> EBinary op (resolve stack l) (resolve stack r)+ ESearchPath _ -> expr++-- | Resolve a variable by walking the scope stack.+--+-- @level@ counts how many scope entries we've crossed (each corresponds+-- to one parent hop at runtime). If the name hits a 'LexicalScope',+-- we return 'EResolvedVar'. If it hits a 'NameBarrier', we stop and+-- leave it as 'EVar' (name-based lookup at runtime). If not found,+-- 'EVar' is returned unchanged (looked up via with-scopes or builtins).+resolveVar :: [ScopeEntry] -> Int -> Text -> Expr+resolveVar [] _ name = EVar name+resolveVar (LexicalScope scope : rest) level name =+ case Map.lookup name scope of+ Just idx -> EResolvedVar level idx+ Nothing -> resolveVar rest (level + 1) name+resolveVar (NameBarrier names : rest) level name =+ if Set.member name names+ then EVar name+ else resolveVar rest (level + 1) name++-- | Build a 'LexicalScope' from lambda formals.+--+-- Index assignment:+--+-- * @FormalName n@ → @[0: n]@+-- * @FormalSet [a, b, c] _@ → @[0: a, 1: b, 2: c]@ (declaration order)+-- * @FormalNamedSet n [a, b, c] _@ → @[0: n, 1: a, 2: b, 3: c]@ (\@ name first)+lexicalScopeFromFormals :: Formals -> ScopeEntry+lexicalScopeFromFormals (FormalName name) =+ LexicalScope (Map.singleton name 0)+lexicalScopeFromFormals (FormalSet formals _) =+ LexicalScope (Map.fromList (zip (map fName formals) [0 ..]))+lexicalScopeFromFormals (FormalNamedSet name formals _) =+ LexicalScope (Map.fromList ((name, 0) : zip (map fName formals) [1 ..]))++-- | Collect all top-level binding names for a 'NameBarrier'.+collectBindingNames :: [Binding] -> Set Text+collectBindingNames = foldl' addNames Set.empty+ where+ addNames acc (NamedBinding (StaticKey name : _) _) = Set.insert name acc+ addNames acc (NamedBinding _ _) = acc+ addNames acc (Inherit _ names) = foldl' (flip Set.insert) acc names++-- | Resolve variables inside string parts.+resolvePart :: [ScopeEntry] -> StringPart -> StringPart+resolvePart _ p@(StrLit _) = p+resolvePart stack (StrInterp e) = StrInterp (resolve stack e)++-- | Resolve variables inside attribute keys.+resolveKey :: [ScopeEntry] -> AttrKey -> AttrKey+resolveKey _ k@(StaticKey _) = k+resolveKey stack (DynamicKey e) = DynamicKey (resolve stack e)++-- | Resolve variables inside a binding's RHS.+--+-- 'Inherit Nothing' is desugared into 'NamedBinding' entries so that+-- each inherited name goes through normal variable resolution. This+-- is necessary because @inherit x@ does a name-based lookup at runtime,+-- but lambda formals are stored in positional 'envSlots' (no names).+-- Desugaring @inherit x@ to @x = x;@ lets the RHS 'EVar' resolve to+-- 'EResolvedVar' when @x@ is a lambda formal.+resolveBinding :: [ScopeEntry] -> Binding -> [Binding]+resolveBinding stack (NamedBinding path bodyExpr) =+ [NamedBinding (map (resolveKey stack) path) (resolve stack bodyExpr)]+resolveBinding stack (Inherit (Just fromExpr) names) =+ [Inherit (Just (resolve stack fromExpr)) names]+resolveBinding stack (Inherit Nothing names) =+ -- Desugar: inherit x y; → x = x; y = y;+ [NamedBinding [StaticKey name] (resolve stack (EVar name)) | name <- names]++-- | Resolve variables inside formal default expressions.+resolveFormalsDefaults :: [ScopeEntry] -> Formals -> Formals+resolveFormalsDefaults _ f@(FormalName _) = f+resolveFormalsDefaults stack (FormalSet formals ellipsis) =+ FormalSet (map (resolveFormal stack) formals) ellipsis+resolveFormalsDefaults stack (FormalNamedSet name formals ellipsis) =+ FormalNamedSet name (map (resolveFormal stack) formals) ellipsis++-- | Resolve variables inside a single formal's default expression.+resolveFormal :: [ScopeEntry] -> Formal -> Formal+resolveFormal stack (Formal name defExpr) =+ Formal name (fmap (resolve stack) defExpr)
src/Nix/Expr/Types.hs view
@@ -151,4 +151,9 @@ EBinary !BinaryOp !Expr !Expr | -- | Search path lookup: @\<nixpkgs\>@ is @ESearchPath "nixpkgs"@. ESearchPath !Text+ | -- | De Bruijn-style resolved variable: @(level, index)@.+ -- Produced by 'Nix.Expr.Resolve.resolveVars' for variables+ -- bound by lambda formals. @level@ counts parent-chain hops;+ -- @index@ is the positional slot within that env's 'envSlots'.+ EResolvedVar !Int !Int deriving (Eq, Show)
src/Nix/Parser.hs view
@@ -50,6 +50,7 @@ import Data.Text (Text) import qualified Data.Text as T import qualified Data.Text.IO as TIO+import Nix.Expr.Resolve (resolveVars) import Nix.Expr.Types (Expr) import Nix.Parser.Expr (parseTopLevel) import Nix.Parser.Internal (ParseState (..), runParser)@@ -66,7 +67,7 @@ tokens <- tokenize fileName (stripBOM source) let st = ParseState {psTokens = tokens, psFile = fileName} (expr, _remaining) <- runParser parseTopLevel st- pure expr+ pure (resolveVars expr) -- | Strip a leading UTF-8 byte order mark (U+FEFF) if present. stripBOM :: Text -> Text
test/Main.hs view
@@ -6,6 +6,7 @@ import Control.Monad (filterM, when) import qualified Data.ByteString as BS import qualified Data.Map.Strict as Map+import Data.Primitive.SmallArray (sizeofSmallArray) import qualified Data.Set as Set import Data.Text (Text) import qualified Data.Text as T@@ -214,7 +215,7 @@ putStrLn "eval/literals" sequence [ runTest "empty env" $- assertEqual "emptyEnv" 0 (length (envBindings emptyEnv)),+ assertEqual "emptyEnv" 0 (sizeofSmallArray (envSlots emptyEnv)), runTest "int" $ assertEval "int" "42" (VInt 42), runTest "float" $@@ -802,15 +803,18 @@ "a // b // c" (EBinary OpUpdate (EVar "a") (EBinary OpUpdate (EVar "b") (EVar "c"))), -- Lambda+ -- After variable resolution, lambda-bound vars become EResolvedVar.+ -- FormalName "x" → slot 0; FormalSet [a,b] → a=0, b=1;+ -- FormalNamedSet "args" [a] → args=0, a=1. runTest "parse simple lambda" $- assertParse "lambda" "x: x" (ELambda (FormalName "x") (EVar "x")),+ assertParse "lambda" "x: x" (ELambda (FormalName "x") (EResolvedVar 0 0)), runTest "parse set pattern lambda" $ assertParse "set pattern" "{ a, b }: a" ( ELambda (FormalSet [Formal "a" Nothing, Formal "b" Nothing] False)- (EVar "a")+ (EResolvedVar 0 0) ), runTest "parse set pattern with defaults" $ assertParse@@ -818,7 +822,7 @@ "{ a ? 1 }: a" ( ELambda (FormalSet [Formal "a" (Just (ELit (NixInt 1)))] False)- (EVar "a")+ (EResolvedVar 0 0) ), runTest "parse set pattern with ellipsis" $ assertParse@@ -826,7 +830,7 @@ "{ a, ... }: a" ( ELambda (FormalSet [Formal "a" Nothing] True)- (EVar "a")+ (EResolvedVar 0 0) ), runTest "parse named set pattern (name@{...})" $ assertParse@@ -834,7 +838,7 @@ "args@{ a }: a" ( ELambda (FormalNamedSet "args" [Formal "a" Nothing] False)- (EVar "a")+ (EResolvedVar 0 1) ), runTest "parse named set pattern ({...}@name)" $ assertParse@@ -842,7 +846,7 @@ "{ a }@args: a" ( ELambda (FormalNamedSet "args" [Formal "a" Nothing] False)- (EVar "a")+ (EResolvedVar 0 1) ), -- Application runTest "parse application" $@@ -882,11 +886,13 @@ "rec attrs" "rec { a = 1; }" (EAttrs True [NamedBinding [StaticKey "a"] (ELit (NixInt 1))]),+ -- inherit x y; is desugared to x = x; y = y; by the resolution pass+ -- (needed because lambda formals are positional, not name-based). runTest "parse inherit" $ assertParse "inherit" "{ inherit x y; }"- (EAttrs False [Inherit Nothing ["x", "y"]]),+ (EAttrs False [NamedBinding [StaticKey "x"] (EVar "x"), NamedBinding [StaticKey "y"] (EVar "y")]), runTest "parse inherit from" $ assertParse "inherit from"