about summary refs log tree commit diff
path: root/nix/yants
diff options
context:
space:
mode:
Diffstat (limited to 'nix/yants')
-rw-r--r--nix/yants/README.md88
-rw-r--r--nix/yants/default.nix368
-rw-r--r--nix/yants/screenshots/enums.pngbin0 -> 41305 bytes
-rw-r--r--nix/yants/screenshots/functions.pngbin0 -> 32907 bytes
-rw-r--r--nix/yants/screenshots/nested-structs.pngbin0 -> 70264 bytes
-rw-r--r--nix/yants/screenshots/simple.pngbin0 -> 43010 bytes
-rw-r--r--nix/yants/screenshots/structs.pngbin0 -> 69499 bytes
-rw-r--r--nix/yants/tests/default.nix158
8 files changed, 614 insertions, 0 deletions
diff --git a/nix/yants/README.md b/nix/yants/README.md
new file mode 100644
index 000000000000..98e6642e2dd8
--- /dev/null
+++ b/nix/yants/README.md
@@ -0,0 +1,88 @@
+yants
+=====
+
+This is a tiny type-checker for data in Nix, written in Nix.
+
+# Features
+
+* Checking of primitive types (`int`, `string` etc.)
+* Checking polymorphic types (`option`, `list`, `either`)
+* Defining & checking struct/record types
+* Defining & matching enum types
+* Defining & matching sum types
+* Defining function signatures (including curried functions)
+* Types are composable! `option string`! `list (either int (option float))`!
+* Type errors also compose!
+
+Currently lacking:
+
+* Any kind of inference
+* Convenient syntax for attribute-set function signatures
+
+## Primitives & simple polymorphism
+
+![simple](/about/nix/yants/screenshots/simple.png)
+
+## Structs
+
+![structs](/about/nix/yants/screenshots/structs.png)
+
+## Nested structs!
+
+![nested structs](/about/nix/yants/screenshots/nested-structs.png)
+
+## Enums!
+
+![enums](/about/nix/yants/screenshots/enums.png)
+
+## Functions!
+
+![functions](/about/nix/yants/screenshots/functions.png)
+
+# Usage
+
+Yants can be imported from its `default.nix`. A single attribute (`lib`) can be
+passed, which will otherwise be imported from `<nixpkgs>`.
+
+TIP: You do not need to clone the entire TVL repository to use Yants!
+You can clone just this project through josh: `git clone
+https://code.tvl.fyi/depot.git:/nix/yants.git`
+
+Examples for the most common import methods would be:
+
+1. Import into scope with `with`:
+    ```nix
+    with (import ./default.nix {});
+    # ... Nix code that uses yants ...
+    ```
+
+2. Import as a named variable:
+    ```nix
+    let yants = import ./default.nix {};
+    in yants.string "foo" # or other uses ...
+    ````
+
+3. Overlay into `pkgs.lib`:
+    ```nix
+    # wherever you import your package set (e.g. from <nixpkgs>):
+    import <nixpkgs> {
+      overlays = [
+        (self: super: {
+          lib = super.lib // { yants = import ./default.nix { inherit (super) lib; }; };
+        })
+      ];
+    }
+
+    # yants now lives at lib.yants, besides the other library functions!
+    ```
+
+Please see my [Nix one-pager](https://github.com/tazjin/nix-1p) for more generic
+information about the Nix language and what the above constructs mean.
+
+# Stability
+
+The current API of Yants is **not yet** considered stable, but it works fine and
+should continue to do so even if used at an older version.
+
+Yants' tests use Nix versions above 2.2 - compatibility with older versions is
+not guaranteed.
diff --git a/nix/yants/default.nix b/nix/yants/default.nix
new file mode 100644
index 000000000000..cb9fc08287fb
--- /dev/null
+++ b/nix/yants/default.nix
@@ -0,0 +1,368 @@
+# Copyright 2019 Google LLC
+# SPDX-License-Identifier: Apache-2.0
+#
+# Provides a "type-system" for Nix that provides various primitive &
+# polymorphic types as well as the ability to define & check records.
+#
+# All types (should) compose as expected.
+
+{ lib ? (import <nixpkgs> { }).lib, ... }:
+
+with builtins; let
+  prettyPrint = lib.generators.toPretty { };
+
+  # typedef' :: struct {
+  #   name = string;
+  #   checkType = function; (a -> result)
+  #   checkToBool = option function; (result -> bool)
+  #   toError = option function; (a -> result -> string)
+  #   def = option any;
+  #   match = option function;
+  # } -> type
+  #           -> (a -> b)
+  #           -> (b -> bool)
+  #           -> (a -> b -> string)
+  #           -> type
+  #
+  # This function creates an attribute set that acts as a type.
+  #
+  # It receives a type name, a function that is used to perform a
+  # check on an arbitrary value, a function that can translate the
+  # return of that check to a boolean that informs whether the value
+  # is type-conformant, and a function that can construct error
+  # messages from the check result.
+  #
+  # This function is the low-level primitive used to create types. For
+  # many cases the higher-level 'typedef' function is more appropriate.
+  typedef' =
+    { name
+    , checkType
+    , checkToBool ? (result: result.ok)
+    , toError ? (_: result: result.err)
+    , def ? null
+    , match ? null
+    }: {
+      inherit name checkToBool toError;
+
+      # check :: a -> bool
+      #
+      # This function is used to determine whether a given type is
+      # conformant.
+      check = value: checkToBool (checkType value);
+
+      # checkType :: a -> struct { ok = bool; err = option string; }
+      #
+      # This function checks whether the passed value is type conformant
+      # and returns an optional type error string otherwise.
+      inherit checkType;
+
+      # __functor :: a -> a
+      #
+      # This function checks whether the passed value is type conformant
+      # and throws an error if it is not.
+      #
+      # The name of this function is a special attribute in Nix that
+      # makes it possible to execute a type attribute set like a normal
+      # function.
+      __functor = self: value:
+        let result = self.checkType value;
+        in if checkToBool result then value
+        else throw (toError value result);
+    };
+
+  typeError = type: val:
+    "expected type '${type}', but value '${prettyPrint val}' is of type '${typeOf val}'";
+
+  # typedef :: string -> (a -> bool) -> type
+  #
+  # typedef is the simplified version of typedef' which uses a default
+  # error message constructor.
+  typedef = name: check: typedef' {
+    inherit name;
+    checkType = v:
+      let res = check v;
+      in {
+        ok = res;
+      } // (lib.optionalAttrs (!res) {
+        err = typeError name v;
+      });
+  };
+
+  checkEach = name: t: l: foldl'
+    (acc: e:
+      let
+        res = t.checkType e;
+        isT = t.checkToBool res;
+      in
+      {
+        ok = acc.ok && isT;
+        err =
+          if isT
+          then acc.err
+          else acc.err + "${prettyPrint e}: ${t.toError e res}\n";
+      })
+    { ok = true; err = "expected type ${name}, but found:\n"; }
+    l;
+in
+lib.fix (self: {
+  # Primitive types
+  any = typedef "any" (_: true);
+  unit = typedef "unit" (v: v == { });
+  int = typedef "int" isInt;
+  bool = typedef "bool" isBool;
+  float = typedef "float" isFloat;
+  string = typedef "string" isString;
+  path = typedef "path" (x: typeOf x == "path");
+  drv = typedef "derivation" (x: isAttrs x && x ? "type" && x.type == "derivation");
+  function = typedef "function" (x: isFunction x || (isAttrs x && x ? "__functor"
+    && isFunction x.__functor));
+
+  # Type for types themselves. Useful when defining polymorphic types.
+  type = typedef "type" (x:
+    isAttrs x
+    && hasAttr "name" x && self.string.check x.name
+    && hasAttr "checkType" x && self.function.check x.checkType
+    && hasAttr "checkToBool" x && self.function.check x.checkToBool
+    && hasAttr "toError" x && self.function.check x.toError
+  );
+
+  # Polymorphic types
+  option = t: typedef' rec {
+    name = "option<${t.name}>";
+    checkType = v:
+      let res = t.checkType v;
+      in {
+        ok = isNull v || (self.type t).checkToBool res;
+        err = "expected type ${name}, but value does not conform to '${t.name}': "
+          + t.toError v res;
+      };
+  };
+
+  eitherN = tn: typedef "either<${concatStringsSep ", " (map (x: x.name) tn)}>"
+    (x: any (t: (self.type t).check x) tn);
+
+  either = t1: t2: self.eitherN [ t1 t2 ];
+
+  list = t: typedef' rec {
+    name = "list<${t.name}>";
+
+    checkType = v:
+      if isList v
+      then checkEach name (self.type t) v
+      else {
+        ok = false;
+        err = typeError name v;
+      };
+  };
+
+  attrs = t: typedef' rec {
+    name = "attrs<${t.name}>";
+
+    checkType = v:
+      if isAttrs v
+      then checkEach name (self.type t) (attrValues v)
+      else {
+        ok = false;
+        err = typeError name v;
+      };
+  };
+
+  # Structs / record types
+  #
+  # Checks that all fields match their declared types, no optional
+  # fields are missing and no unexpected fields occur in the struct.
+  #
+  # Anonymous structs are supported (e.g. for nesting) by omitting the
+  # name.
+  #
+  # TODO: Support open records?
+  struct =
+    # Struct checking is more involved than the simpler types above.
+    # To make the actual type definition more readable, several
+    # helpers are defined below.
+    let
+      # checkField checks an individual field of the struct against
+      # its definition and creates a typecheck result. These results
+      # are aggregated during the actual checking.
+      checkField = def: name: value:
+        let result = def.checkType value; in rec {
+          ok = def.checkToBool result;
+          err =
+            if !ok && isNull value
+            then "missing required ${def.name} field '${name}'\n"
+            else "field '${name}': ${def.toError value result}\n";
+        };
+
+      # checkExtraneous determines whether a (closed) struct contains
+      # any fields that are not part of the definition.
+      checkExtraneous = def: has: acc:
+        if (length has) == 0 then acc
+        else if (hasAttr (head has) def)
+        then checkExtraneous def (tail has) acc
+        else
+          checkExtraneous def (tail has) {
+            ok = false;
+            err = acc.err + "unexpected struct field '${head has}'\n";
+          };
+
+      # checkStruct combines all structure checks and creates one
+      # typecheck result from them
+      checkStruct = def: value:
+        let
+          init = { ok = true; err = ""; };
+          extraneous = checkExtraneous def (attrNames value) init;
+
+          checkedFields = map
+            (n:
+              let v = if hasAttr n value then value."${n}" else null;
+              in checkField def."${n}" n v)
+            (attrNames def);
+
+          combined = foldl'
+            (acc: res: {
+              ok = acc.ok && res.ok;
+              err = if !res.ok then acc.err + res.err else acc.err;
+            })
+            init
+            checkedFields;
+        in
+        {
+          ok = combined.ok && extraneous.ok;
+          err = combined.err + extraneous.err;
+        };
+
+      struct' = name: def: typedef' {
+        inherit name def;
+        checkType = value:
+          if isAttrs value
+          then (checkStruct (self.attrs self.type def) value)
+          else { ok = false; err = typeError name value; };
+
+        toError = _: result: "expected '${name}'-struct, but found:\n" + result.err;
+      };
+    in
+    arg: if isString arg then (struct' arg) else (struct' "anon" arg);
+
+  # Enums & pattern matching
+  enum =
+    let
+      plain = name: def: typedef' {
+        inherit name def;
+
+        checkType = (x: isString x && elem x def);
+        checkToBool = x: x;
+        toError = value: _: "'${prettyPrint value} is not a member of enum ${name}";
+      };
+      enum' = name: def: lib.fix (e: (plain name def) // {
+        match = x: actions: deepSeq (map e (attrNames actions)) (
+          let
+            actionKeys = attrNames actions;
+            missing = foldl' (m: k: if (elem k actionKeys) then m else m ++ [ k ]) [ ] def;
+          in
+          if (length missing) > 0
+          then throw "Missing match action for members: ${prettyPrint missing}"
+          else actions."${e x}"
+        );
+      });
+    in
+    arg: if isString arg then (enum' arg) else (enum' "anon" arg);
+
+  # Sum types
+  #
+  # The representation of a sum type is an attribute set with only one
+  # value, where the key of the value denotes the variant of the type.
+  sum =
+    let
+      plain = name: def: typedef' {
+        inherit name def;
+        checkType = (x:
+          let variant = elemAt (attrNames x) 0;
+          in if isAttrs x && length (attrNames x) == 1 && hasAttr variant def
+          then
+            let
+              t = def."${variant}";
+              v = x."${variant}";
+              res = t.checkType v;
+            in
+            if t.checkToBool res
+            then { ok = true; }
+            else {
+              ok = false;
+              err = "while checking '${name}' variant '${variant}': "
+                + t.toError v res;
+            }
+          else { ok = false; err = typeError name x; }
+        );
+      };
+      sum' = name: def: lib.fix (s: (plain name def) // {
+        match = x: actions:
+          let
+            variant = deepSeq (s x) (elemAt (attrNames x) 0);
+            actionKeys = attrNames actions;
+            defKeys = attrNames def;
+            missing = foldl' (m: k: if (elem k actionKeys) then m else m ++ [ k ]) [ ] defKeys;
+          in
+          if (length missing) > 0
+          then throw "Missing match action for variants: ${prettyPrint missing}"
+          else actions."${variant}" x."${variant}";
+      });
+    in
+    arg: if isString arg then (sum' arg) else (sum' "anon" arg);
+
+  # Typed function definitions
+  #
+  # These definitions wrap the supplied function in type-checking
+  # forms that are evaluated when the function is called.
+  #
+  # Note that typed functions themselves are not types and can not be
+  # used to check values for conformity.
+  defun =
+    let
+      mkFunc = sig: f: {
+        inherit sig;
+        __toString = self: foldl' (s: t: "${s} -> ${t.name}")
+          "λ :: ${(head self.sig).name}"
+          (tail self.sig);
+        __functor = _: f;
+      };
+
+      defun' = sig: func:
+        if length sig > 2
+        then mkFunc sig (x: defun' (tail sig) (func ((head sig) x)))
+        else mkFunc sig (x: ((head (tail sig)) (func ((head sig) x))));
+
+    in
+    sig: func:
+      if length sig < 2
+      then (throw "Signature must at least have two types (a -> b)")
+      else defun' sig func;
+
+  # Restricting types
+  #
+  # `restrict` wraps a type `t`, and uses a predicate `pred` to further
+  # restrict the values, giving the restriction a descriptive `name`.
+  #
+  # First, the wrapped type definition is checked (e.g. int) and then the
+  # value is checked with the predicate, so the predicate can already
+  # depend on the value being of the wrapped type.
+  restrict = name: pred: t:
+    let restriction = "${t.name}[${name}]"; in typedef' {
+      name = restriction;
+      checkType = v:
+        let res = t.checkType v;
+        in
+        if !(t.checkToBool res)
+        then res
+        else
+          let
+            iok = pred v;
+          in
+          if isBool iok then {
+            ok = iok;
+            err = "${prettyPrint v} does not conform to restriction '${restriction}'";
+          } else
+          # use throw here to avoid spamming the build log
+            throw "restriction '${restriction}' predicate returned unexpected value '${prettyPrint iok}' instead of boolean";
+    };
+
+})
diff --git a/nix/yants/screenshots/enums.png b/nix/yants/screenshots/enums.png
new file mode 100644
index 000000000000..71673e7ab63c
--- /dev/null
+++ b/nix/yants/screenshots/enums.png
Binary files differdiff --git a/nix/yants/screenshots/functions.png b/nix/yants/screenshots/functions.png
new file mode 100644
index 000000000000..30ed50f8327b
--- /dev/null
+++ b/nix/yants/screenshots/functions.png
Binary files differdiff --git a/nix/yants/screenshots/nested-structs.png b/nix/yants/screenshots/nested-structs.png
new file mode 100644
index 000000000000..6b03ed65ceb7
--- /dev/null
+++ b/nix/yants/screenshots/nested-structs.png
Binary files differdiff --git a/nix/yants/screenshots/simple.png b/nix/yants/screenshots/simple.png
new file mode 100644
index 000000000000..05a302cc6b9d
--- /dev/null
+++ b/nix/yants/screenshots/simple.png
Binary files differdiff --git a/nix/yants/screenshots/structs.png b/nix/yants/screenshots/structs.png
new file mode 100644
index 000000000000..fcbcf6415fad
--- /dev/null
+++ b/nix/yants/screenshots/structs.png
Binary files differdiff --git a/nix/yants/tests/default.nix b/nix/yants/tests/default.nix
new file mode 100644
index 000000000000..0c7ec2418802
--- /dev/null
+++ b/nix/yants/tests/default.nix
@@ -0,0 +1,158 @@
+{ depot, pkgs, ... }:
+
+with depot.nix.yants;
+
+# Note: Derivations are not included in the tests below as they cause
+# issues with deepSeq.
+
+let
+
+  inherit (depot.nix.runTestsuite)
+    runTestsuite
+    it
+    assertEq
+    assertThrows
+    assertDoesNotThrow
+    ;
+
+  # this derivation won't throw if evaluated with deepSeq
+  # unlike most things even remotely related with nixpkgs
+  trivialDerivation = derivation {
+    name = "trivial-derivation";
+    inherit (pkgs.stdenv) system;
+    builder = "/bin/sh";
+    args = [ "-c" "echo hello > $out" ];
+  };
+
+  testPrimitives = it "checks that all primitive types match" [
+    (assertDoesNotThrow "unit type" (unit { }))
+    (assertDoesNotThrow "int type" (int 15))
+    (assertDoesNotThrow "bool type" (bool false))
+    (assertDoesNotThrow "float type" (float 13.37))
+    (assertDoesNotThrow "string type" (string "Hello!"))
+    (assertDoesNotThrow "function type" (function (x: x * 2)))
+    (assertDoesNotThrow "path type" (path /nix))
+    (assertDoesNotThrow "derivation type" (drv trivialDerivation))
+  ];
+
+  testPoly = it "checks that polymorphic types work as intended" [
+    (assertDoesNotThrow "option type" (option int null))
+    (assertDoesNotThrow "list type" (list string [ "foo" "bar" ]))
+    (assertDoesNotThrow "either type" (either int float 42))
+  ];
+
+  # Test that structures work as planned.
+  person = struct "person" {
+    name = string;
+    age = int;
+
+    contact = option (struct {
+      email = string;
+      phone = option string;
+    });
+  };
+
+  testStruct = it "checks that structures work as intended" [
+    (assertDoesNotThrow "person struct" (person {
+      name = "Brynhjulf";
+      age = 42;
+      contact.email = "brynhjulf@yants.nix";
+    }))
+  ];
+
+  # Test enum definitions & matching
+  colour = enum "colour" [ "red" "blue" "green" ];
+  colourMatcher = {
+    red = "It is in fact red!";
+    blue = "It should not be blue!";
+    green = "It should not be green!";
+  };
+
+  testEnum = it "checks enum definitions and matching" [
+    (assertEq "enum is matched correctly"
+      "It is in fact red!"
+      (colour.match "red" colourMatcher))
+    (assertThrows "out of bounds enum fails"
+      (colour.match "alpha" (colourMatcher // {
+        alpha = "This should never happen";
+      }))
+    )
+  ];
+
+  # Test sum type definitions
+  creature = sum "creature" {
+    human = struct {
+      name = string;
+      age = option int;
+    };
+
+    pet = enum "pet" [ "dog" "lizard" "cat" ];
+  };
+  some-human = creature {
+    human = {
+      name = "Brynhjulf";
+      age = 42;
+    };
+  };
+
+  testSum = it "checks sum types definitions and matching" [
+    (assertDoesNotThrow "creature sum type" some-human)
+    (assertEq "sum type is matched correctly"
+      "It's a human named Brynhjulf"
+      (creature.match some-human {
+        human = v: "It's a human named ${v.name}";
+        pet = v: "It's not supposed to be a pet!";
+      })
+    )
+  ];
+
+  # Test curried function definitions
+  func = defun [ string int string ]
+    (name: age: "${name} is ${toString age} years old");
+
+  testFunctions = it "checks function definitions" [
+    (assertDoesNotThrow "function application" (func "Brynhjulf" 42))
+  ];
+
+  # Test that all types are types.
+  assertIsType = name: t:
+    assertDoesNotThrow "${name} is a type" (type t);
+  testTypes = it "checks that all types are types" [
+    (assertIsType "any" any)
+    (assertIsType "bool" bool)
+    (assertIsType "drv" drv)
+    (assertIsType "float" float)
+    (assertIsType "int" int)
+    (assertIsType "string" string)
+    (assertIsType "path" path)
+
+    (assertIsType "attrs int" (attrs int))
+    (assertIsType "eitherN [ ... ]" (eitherN [ int string bool ]))
+    (assertIsType "either int string" (either int string))
+    (assertIsType "enum [ ... ]" (enum [ "foo" "bar" ]))
+    (assertIsType "list string" (list string))
+    (assertIsType "option int" (option int))
+    (assertIsType "option (list string)" (option (list string)))
+    (assertIsType "struct { ... }" (struct { a = int; b = option string; }))
+    (assertIsType "sum { ... }" (sum { a = int; b = option string; }))
+  ];
+
+  testRestrict = it "checks restrict types" [
+    (assertDoesNotThrow "< 42" ((restrict "< 42" (i: i < 42) int) 25))
+    (assertDoesNotThrow "list length < 3"
+      ((restrict "not too long" (l: builtins.length l < 3) (list int)) [ 1 2 ]))
+    (assertDoesNotThrow "list eq 5"
+      (list (restrict "eq 5" (v: v == 5) any) [ 5 5 5 ]))
+  ];
+
+in
+runTestsuite "yants" [
+  testPrimitives
+  testPoly
+  testStruct
+  testEnum
+  testSum
+  testFunctions
+  testTypes
+  testRestrict
+]