gen — A Framework-Building Toolkit for Nix

An ecosystem of small, independently versioned Nix libraries for building demand-driven, graph-structured configuration frameworks.

• What gen is
• What it provides
• Using it
• What it promises
• How it's architected
• Core ideas
• Theoretical foundations
• Documentation

Each gen library owns exactly one concern — type checking, module merging, scope-graph evaluation, graph queries, selection, binding, dispatch, dataflow — names it after the literature it comes from, and ships its own test suite and CI gate. They talk to each other through accessor functions and plain attrsets rather than deep coupling, so you can take gen-graph for graph queries without gen-scope, or gen-schema for typed registries without knowing what an aspect is. This repository is the hub: it owns no concern of its own, and publishes the roster (mkGenLibs), the shared CI wrapper (mkCi), and one flake-parts module.

The primary consumer is den, a NixOS / nix-darwin / home-manager configuration framework. The libraries themselves are generic — none of them knows what NixOS is.

Twenty libraries are wired into the hub roster and reachable as mkGenLibs keys; two more are standalone and consumed directly. Each library's flake.nix description and its AGENTS.md capability sheet are the authority on its scope — the sheet also records what the library explicitly does not own, and which sibling does.

Take only the libraries you need. Every library exports exactly one .lib, and each resolves its own dependencies, so there is nothing to wire:

{
  inputs.gen-graph.url = "github:sini/gen-graph";
  inputs.gen-flake.url = "github:sini/gen-flake";

  outputs =
    { gen-graph, gen-flake, ... }:
    let
      genGraph = gen-graph.lib;
      composed = gen-flake.lib.compose { tree = ./gen-modules; };
    in
    {
      # `injectArgs` packages the resolved VALUES as a plain query module
      nixosModules.gen = gen-flake.lib.injectArgs composed;
    };
}

A consumer's ordinary nixpkgs modules then read those values as one module argument:

{ genValues, ... }:
{
  networking.hostName = genValues.hosts.igloo.name;
  # A gen type rides along as inert data — readable here, never in the options tree:
  #   genValues.schema.host.options.addr.type.name
}

The hub is optional. mkGenLibs gives you the whole roster under short keys (genLibs.graph, genLibs.merge, …) when you want it, and gen.lib.substrate / gen.lib.modules / gen.lib.aspects give you one layer of it at a time — but a consumer reading inputs.gen-X.lib directly never needs this repository at all.

Each promise below names the mechanism that enforces it. Where the enforcer is a person rather than a command, that is said outright. The full inventory — every proof, the command that re-runs it, and how it fails — is TRUST.md.

Every roster library is nixpkgs-lib-free. Enforced per repo by a source scanner, ci/tests/purity.nix (gen-types carries it as ci/tests/types-purity.nix), run by nix develop ./ci -c nix-unit --flake ./ci#tests.purity. Eighteen of the twenty roster libraries carry it. gen-prelude needs none — it declares no flake inputs at all, so nothing transitive can enter its lock, and the flake structure is the proof. gen-demand's scanner is outstanding; its purity today rests on its input list rather than on a check. gen-vars is the documented exception, and is off-roster for this reason.

Full nixpkgs enters at exactly one file. In gen-flake — the only library that consumes it — lib/terminals.nix is the single file the purity scanner excludes as the sanctioned boundary. Every other file in that lib/ is scanned, and a new file is treated as strict pure core by default, so the boundary cannot widen by accident. Everywhere the ecosystem needs lib.* alone it pulls the pinned github:nix-community/nixpkgs.lib rather than full nixpkgs — policy stated in ci/flake.nix and visible in every ci/ lock file.

One .lib export per library. Structurally enforced: mkGenLibs reads genInputs.gen-<name>.lib for nineteen of the twenty roster keys — gen-class is the exception described below, and its flake exports .lib too — so a library that renames, wraps or drops that output fails hub evaluation at its first consumer. All twenty-two library flakes declare it today.

Every library gates on its own CI. All twenty-two library repos build their ci/flake.nix on this hub's gen.lib.mkCi, which import-trees the whole ci/tests/ directory — a new test file becomes a gate the moment it lands, with no registration step. nix flake check ./ci from any repo root runs the suite, and every roster library carries a GitHub Actions workflow that runs it on push and pull request.

The pure module system is byte-identical to the nixpkgs one it replaced. Two parity oracles in this hub's ci/ — rehost-byte-parity over den-shaped fixtures and rehost-den-parity over den's actual registry shape — compare resolved projections down to the id_hash SHA, and carry mutation teeth. nix flake check ./ci, wired as the checks job. The reference side is pinned at frozen pre-re-host revisions, so the bar cannot drift.

Performance claims are parity-gated. nix run ./ci#perf-bench measures every cell and gates on parity, ratio and linearity together: a parity mismatch fails the run whatever the timings say, so a fast-but-wrong change cannot pass. Wired as its own CI job, alongside fleet-consistency, which re-derives every cited fleet number from committed baselines.

Every library states what it does not own. All twenty-three repositories (the hub included) carry an AGENTS.md capability sheet whose "Not this library's job" table names the owning sibling for each adjacent concern and quotes that sibling's own flake.nix description verbatim, most rows backed by a grep that localizes the seam. This is a convention with a uniform artifact, not a CI gate.

Names answer to the literature. TERMINOLOGY.md carries a per-term provenance column and a reference table of thirty-odd papers, and library sources cite their papers inline at the point of use — gen-scope/lib/resolve.nix alone cites Neron, van Antwerpen and Sloane by section. This promise is enforced by review against TERMINOLOGY.md, not by a check; no CI job verifies a citation.

The composition plane is pure and nixpkgs-lib-free: the module-system substrate (gen-types → gen-merge → { gen-schema, gen-aspects }) resolves gen module trees to values without ever touching lib.evalModules. The terminal plane is nixpkgs: gen-flake.realize folds the composed per-host projection through per-class terminals — realize is itself pure, and the nixpkgs contact lives in the terminals it is handed (terminals.mkSystemTerminal, mkFlakeTerminal). The invariant across the crossing is that gen types never leave the pure eval; only values cross — a gen type may ride along as inert data a consumer can read, but it never enters the consumer's options tree, so nixpkgs never type-walks it. This is value-injection rather than type-driving, the same one-way trade adios takes: a pure engine cannot be driven by foreign nixpkgs-module libraries.

mkGenLibs (lib/mkGenLibs.nix) is a two-stage function. Stage one captures genInputs — the gen flake inputs — and binds the roster. Stage two hands back that same value. Every member flake is self-wiring: its .lib output resolves its own dependencies internally (gen-schema owns its gen-algebra input, gen-pipe its gen-select and gen-scope), so the hub does nothing but re-export genInputs.gen-X.lib. The second argument is vestigial and kept only for call compatibility.

The roster is bound once rather than per application, so every route to it — a bucket, the flakeModule, a direct call — holds one value rather than several evaluations of the same source. Nineteen members are shared that way anyway by input memoization; class is not, because it is an import the hub applies itself, and a per-application binding re-allocated it.

gen-class is the one exception. Its flake .lib leaves the merge engine as null — every tier-1 export works without it — so the hub re-imports gen-class's ./lib with the gen-merge kernel injected as a value. That is what makes mkGenLibs.class carry the tier-2 applyCoreFixed path. gen-merge is injected rather than declared as a flake input precisely so gen-class stays a single-input Class B library.

The roster carries a strata key declaring, for every member, which layer of the stack it belongs to. The declaration is total and explicit: a member with no entry is a build error rather than a member of an implicit residue bucket, because a defaulted stratum would let a new library join the roster and land silently in whatever bucket the default happened to name. Adding a member is two lines in one commit — the binding and its stratum — and ci/mkgenlibs-eval.nix fails the gate otherwise.

Three of the five values publish a consumer path, each a selection from the flat roster rather than a re-import, so gen.lib.substrate.prelude and the flat prelude are one value and not two evaluations of the same source:

gen.lib.substrate   algebra bind dispatch graph prelude product schema scope select
gen.lib.modules     merge types
gen.lib.aspects     aspects class link

The other two publish nothing. framework (gen-settings) sits above the stack rather than in it — a configuration framework assembles with it, and no substrate vocabulary is defined in its terms. retiring (gen-demand, gen-edge, gen-flake, gen-pipe, gen-resolve) marks a member whose content is moving elsewhere: still reachable on the flat roster, deliberately not offered as something to adopt. Both keep the declaration total without inviting a consumer onto a path that is about to close.

Libraries declare their class honestly: A pure {}, B gen-prelude, C nixpkgs-lib, D nixpkgs-lib plus a gen dependency. Classes C and D are empty among the roster libraries. The graph is strictly acyclic and shallow — most libraries have one or two inputs:

gen-prelude   zero inputs (Class A)
gen-algebra   zero inputs (Class A)
gen-select    zero inputs (Class A)

gen-types     ← prelude
gen-merge     ← prelude, types
gen-schema    ← prelude, types, merge, algebra
gen-aspects   ← prelude, merge, schema
gen-scope     ← prelude
gen-graph     ← prelude
gen-bind      ← prelude
gen-dispatch  ← prelude
gen-product   ← prelude
gen-class     ← prelude (+ gen-merge injected by the hub for tier 2)
gen-edge      ← prelude, graph
gen-demand    ← prelude, graph (gen-select optional, for adapters.select)
gen-pipe      ← prelude, select, scope
gen-settings  ← prelude, algebra, bind, graph
gen-resolve   ← prelude, scope, graph, rebuild, algebra, bind
gen-link      ← prelude, scope, resolve, edge, schema, algebra, aspects

gen-flake     ← prelude, types, merge, schema, aspects, bind,
                import-tree, flake-parts, nixpkgs        (the one boundary)

Libraries never import each other's flake inputs to reach a sibling's data — gen-select does not import gen-scope, it provides an adapter that accepts gen-scope's result shape. That is what keeps the roster composable at the consumer rather than at the library.

ARCHITECTURE.md is the deep reference: composition patterns, the data-flow chain, the three fixpoint levels and who owns each, the memoization and cost model, and the full design constraints.

Nix is the evaluator. gen-scope does not build an attribute-grammar evaluator — it leverages Nix's native lazy evaluation for demand-driven computation, lib.fix for memoization, and attrset lookup for O(1) attribute access. The _eval cache co-located on each scope-graph node is just a lazy attrset.

Accessors, not data. gen-graph takes { edges = id: [...]; } — functions, not materialized maps. gen-select takes { data = id: {...}; parent = id: ...; }. Wired to gen-scope's memoized result.get, accessor calls are O(1) after first evaluation, and no computation is repeated between libraries.

Identity everywhere. Palmer's intensional functions — program-point identity with conservative equality — power dedup across the ecosystem: search continuation dedup in gen-algebra, aspect diamond dedup in gen-aspects, rule identity in gen-dispatch, selector equality in gen-select, and the content-addressed id_hash in gen-schema.

Step, loop and ordering are separate concerns. gen-dispatch is the pure relational dispatch step, a function of (rules, context) that never sorts and never iterates. Group ordering is a forward producers-first order computed by gen-graph's phaseOrder over the condensation. The convergence loop lives in gen-resolve via gen-scope.circular (Kleene ascent). Recomputing at the fixpoint makes the action set a function of the converged state, so no cross-pass bookkeeping is needed.

Actions are opaque. gen-dispatch groups actions but never interprets them; gen-edge moves content without knowing what content is; gen-demand produces pure data and constructs no modules. Libraries provide machinery, consumers provide meaning.

The ecosystem is grounded in attribute-grammar theory, scope-graph formalism, and algebraic graph construction:

• Attribute grammars — Knuth (1968), Vogt (1989, HOAG), Hedin (2000, RAG), Sloane (2010, Kiama)
• Scope graphs — Neron (2015), van Antwerpen (2016, Statix; 2018, Scopes as Types)
• Algebraic graphs — Mokhov (2017); graph products — Hammack, Imrich & Klavžar (2011)
• Intensional functions — Palmer (2024)
• Record algebra — Leijen (2005), Bracha & Cook (1990)
• Contracts — Findler (2002), Chitil (2012); refinement types — Rondon (2008)
• Rule systems — Forgy (1982, RETE), Ehrig (2006), Arntzenius (2016, Datafun)
• Dataflow and stratification — Kahn (1974, channels), Kahn (1962, toposort), Apt, Blair & Walker (1988, stratified evaluation)
• Build systems — Mokhov, Mitchell & Peyton Jones (2018, rebuilder dimension)

See TERMINOLOGY.md for the complete vocabulary with per-term provenance.

• ARCHITECTURE.md — Composition model, data flow, performance architecture, design constraints
• TERMINOLOGY.md — Unified vocabulary across the gen libraries, with academic provenance
• TRUST.md — The map: what is proven, on which axis, and where each check lives
• VALIDATION.md — The per-proof inventory: every claim, its command, and its failure mode
• BENCHMARKS.md — Evaluation-time measurements and the gates that hold them