pkgs/by-name: Introduce

This introduces the `pkgs/by-name` directory as proposed by RFC 140.
Included are:
- The implementation to add packages defined in that directory to the
  top-level package scope
- Contributer documentation on how to add packages to it
- A GitHub Actions workflow to check the structure of it on all PRs

6 files changed, 213 insertions, 1 deletions

diff --git a/.github/CODEOWNERS b/.github/CODEOWNERS
index f5679a1a142..79ba7b7c520 100644
--- a/.github/CODEOWNERS
+++ b/.github/CODEOWNERS
@@ -49,6 +49,9 @@
 
 # pkgs/by-name
 /pkgs/test/nixpkgs-check-by-name @infinisil
+/pkgs/by-name/README.md @infinisil
+/pkgs/top-level/by-name-overlay.nix @infinisil
+/.github/workflows/check-by-name.nix @infinisil
 
 # Nixpkgs build-support
 /pkgs/build-support/writers @lassulus @Profpatsch
diff --git a/.github/workflows/check-by-name.yml b/.github/workflows/check-by-name.yml
new file mode 100644
index 00000000000..9622634fcff
--- /dev/null
+++ b/.github/workflows/check-by-name.yml
@@ -0,0 +1,49 @@
+# Checks pkgs/by-name (see pkgs/by-name/README.md)
+# using the nixpkgs-check-by-name tool (see pkgs/test/nixpkgs-check-by-name)
+name: Check pkgs/by-name
+
+# The pre-built tool is fetched from a channel,
+# making it work predictable on all PRs
+on: pull_request
+
+# The tool doesn't need any permissions, it only outputs success or not based on the checkout
+permissions: {}
+
+jobs:
+  check:
+    # This is x86_64-linux, for which the tool is always prebuilt on the nixos-* channels,
+    # as specified in nixos/release-combined.nix
+    runs-on: ubuntu-latest
+    steps:
+      - uses: actions/checkout@v3
+      - uses: cachix/install-nix-action@v22
+      - name: Determining channel to use for dependencies
+        run: |
+          echo "Determining which channel to use for PR base branch $GITHUB_BASE_REF"
+          if [[ "$GITHUB_BASE_REF" =~ ^(release|staging|staging-next)-([0-9][0-9]\.[0-9][0-9])$ ]]; then
+              # Use the release channel for all PRs to release-XX.YY, staging-XX.YY and staging-next-XX.YY
+              channel=nixos-${BASH_REMATCH[2]}
+              echo "PR is for a release branch, using release channel $channel"
+          else
+              # Use the nixos-unstable channel for all other PRs
+              channel=nixos-unstable
+              echo "PR is for a non-release branch, using unstable channel $channel"
+          fi
+          echo "channel=$channel" >> "$GITHUB_ENV"
+      - name: Fetching latest version of channel
+        run: |
+          echo "Fetching latest version of channel $channel"
+          # This is probably the easiest way to get Nix to output the path to a downloaded channel!
+          nixpkgs=$(nix-instantiate --find-file nixpkgs -I nixpkgs=channel:"$channel")
+          # This file only exists in channels
+          rev=$(<"$nixpkgs"/.git-revision)
+          echo "Channel $channel is at revision $rev"
+          echo "nixpkgs=$nixpkgs" >> "$GITHUB_ENV"
+          echo "rev=$rev" >> "$GITHUB_ENV"
+      - name: Fetching pre-built nixpkgs-check-by-name from the channel
+        run: |
+          echo "Fetching pre-built nixpkgs-check-by-name from channel $channel at revision $rev"
+          # Passing --max-jobs 0 makes sure that we won't build anything
+          nix-build "$nixpkgs" -A tests.nixpkgs-check-by-name --max-jobs 0
+      - name: Running nixpkgs-check-by-name
+        run: result/bin/nixpkgs-check-by-name .
diff --git a/pkgs/by-name/README.md b/pkgs/by-name/README.md
new file mode 100644
index 00000000000..8aecc3822cc
--- /dev/null
+++ b/pkgs/by-name/README.md
@@ -0,0 +1,101 @@
+# Name-based package directories
+
+The structure of this directory maps almost directly to top-level package attributes.
+This is the recommended way to add new top-level packages to Nixpkgs [when possible](#limitations).
+
+## Example
+
+The top-level package `pkgs.some-package` may be declared by setting up this file structure:
+
+```
+pkgs
+└── by-name
+   ├── so
+   ┊  ├── some-package
+      ┊  └── package.nix
+
+```
+
+Where `some-package` is the package name and `so` is the lowercased 2-letter prefix of the package name.
+
+The `package.nix` may look like this:
+
+```nix
+# A function taking an attribute set as an argument
+{
+  # Get access to top-level attributes for use as dependencies
+  lib,
+  stdenv,
+  libbar,
+
+  # Make this derivation configurable using `.override { enableBar = true }`
+  enableBar ? false,
+}:
+
+# The return value must be a derivation
+stdenv.mkDerivation {
+  # ...
+  buildInputs =
+    lib.optional enableBar libbar;
+}
+```
+
+You can also split up the package definition into more files in the same directory if necessary.
+
+Once defined, the package can be built from the Nixpkgs root directory using:
+```
+nix-build -A some-package
+```
+
+See the [general package conventions](../README.md#conventions) for more information on package definitions.
+
+### Changing implicit attribute defaults
+
+The above expression is called using these arguments by default:
+```nix
+{
+  lib = pkgs.lib;
+  stdenv = pkgs.stdenv;
+  libbar = pkgs.libbar;
+}
+```
+
+But the package might need `pkgs.libbar_2` instead.
+While the function could be changed to take `libbar_2` directly as an argument,
+this would change the `.override` interface, breaking code like `.override { libbar = ...; }`.
+So instead it is preferable to use the same generic parameter name `libbar`
+and override its value in [`pkgs/top-level/all-packages.nix`](../top-level/all-packages.nix):
+
+```nix
+libfoo = callPackage ../by-name/so/somePackage/package.nix {
+  libbar = libbar_2;
+};
+```
+
+## Limitations
+
+There's some limitations as to which packages can be defined using this structure:
+
+- Only packages defined using `pkgs.callPackage`.
+  This excludes packages defined using `pkgs.python3Packages.callPackage ...`.
+
+  Instead use the [category hierarchy](../README.md#category-hierarchy) for such attributes.
+
+- Only top-level packages.
+  This excludes packages for other package sets like `pkgs.pythonPackages.*`.
+
+  Refer to the definition and documentation of the respective package set to figure out how such packages can be declared.
+
+## Validation
+
+CI performs [certain checks](../test/nixpkgs-check-by-name/README.md#validity-checks) on the `pkgs/by-name` structure.
+This is done using the [`nixpkgs-check-by-name` tool](../test/nixpkgs-check-by-name).
+The version of this tool used is the one that corresponds to the NixOS channel of the PR base branch.
+See [here](../../.github/workflows/check-by-name.yml) for details.
+
+The tool can be run locally using
+
+```bash
+nix-build -A tests.nixpkgs-check-by-name
+result/bin/nixpkgs-check-by-name .
+```
diff --git a/pkgs/test/nixpkgs-check-by-name/README.md b/pkgs/test/nixpkgs-check-by-name/README.md
index 754d0a2090d..4dd694acd2f 100644
--- a/pkgs/test/nixpkgs-check-by-name/README.md
+++ b/pkgs/test/nixpkgs-check-by-name/README.md
@@ -1,11 +1,12 @@
 # Nixpkgs pkgs/by-name checker
 
 This directory implements a program to check the [validity](#validity-checks) of the `pkgs/by-name` Nixpkgs directory once introduced.
+It is being used by [this GitHub Actions workflow](../../../.github/workflows/check-by-name.yml).
 This is part of the implementation of [RFC 140](https://github.com/NixOS/rfcs/pull/140).
 
 ## API
 
-This API may be changed over time if the CI making use of it is adjusted to deal with the change appropriately, see [Hydra builds](#hydra-builds).
+This API may be changed over time if the CI workflow making use of it is adjusted to deal with the change appropriately.
 
 - Command line: `nixpkgs-check-by-name <NIXPKGS>`
 - Arguments:
diff --git a/pkgs/top-level/by-name-overlay.nix b/pkgs/top-level/by-name-overlay.nix
new file mode 100644
index 00000000000..41944c4e3b0
--- /dev/null
+++ b/pkgs/top-level/by-name-overlay.nix
@@ -0,0 +1,50 @@
+# This file turns the pkgs/by-name directory (see its README.md for more info) into an overlay that adds all the defined packages.
+# No validity checks are done here,
+# instead this file is optimised for performance,
+# and validity checks are done by CI on PRs.
+
+# Type: Path -> Overlay
+baseDirectory:
+let
+  # Because of Nix's import-value cache, importing lib is free
+  lib = import ../../lib;
+
+  inherit (builtins)
+    readDir
+    ;
+
+  inherit (lib.attrsets)
+    mapAttrs
+    mapAttrsToList
+    mergeAttrsList
+    ;
+
+  # Package files for a single shard
+  # Type: String -> String -> AttrsOf Path
+  namesForShard = shard: type:
+    if type != "directory" then
+      # Ignore all non-directories. Technically only README.md is allowed as a file in the base directory, so we could alternatively:
+      # - Assume that README.md is the only file and change the condition to `shard == "README.md"` for a minor performance improvement.
+      #   This would however cause very poor error messages if there's other files.
+      # - Ensure that README.md is the only file, throwing a better error message if that's not the case.
+      #   However this would make for a poor code architecture, because one type of error would have to be duplicated in the validity checks and here.
+      # Additionally in either of those alternatives, we would have to duplicate the hardcoding of "README.md"
+      { }
+    else
+      mapAttrs
+        (name: _: baseDirectory + "/${shard}/${name}/package.nix")
+        (readDir (baseDirectory + "/${shard}"));
+
+  # The attribute set mapping names to the package files defining them
+  # This is defined up here in order to allow reuse of the value (it's kind of expensive to compute)
+  # if the overlay has to be applied multiple times
+  packageFiles = mergeAttrsList (mapAttrsToList namesForShard (readDir baseDirectory));
+in
+# TODO: Consider optimising this using `builtins.deepSeq packageFiles`,
+# which could free up the above thunks and reduce GC times.
+# Currently this would be hard to measure until we have more packages
+# and ideally https://github.com/NixOS/nix/pull/8895
+self: super:
+mapAttrs (name: file:
+  self.callPackage file { }
+) packageFiles
diff --git a/pkgs/top-level/stage.nix b/pkgs/top-level/stage.nix
index 3886ae04e49..1f37bbb70bd 100644
--- a/pkgs/top-level/stage.nix
+++ b/pkgs/top-level/stage.nix
@@ -8,6 +8,13 @@
    arguments. Normal users should not import this directly but instead
    import `pkgs/default.nix` or `default.nix`. */
 
+let
+  # An overlay to auto-call packages in ../by-name.
+  # By defining it at the top of the file,
+  # this value gets reused even if this file is imported multiple times,
+  # thanks to Nix's import-value cache.
+  autoCalledPackages = import ./by-name-overlay.nix ../by-name;
+in
 
 { ## Misc parameters kept the same for all stages
   ##
@@ -279,6 +286,7 @@ let
     stdenvAdapters
     trivialBuilders
     splice
+    autoCalledPackages
     allPackages
     otherPackageSets
     aliases