diff options
Diffstat (limited to 'users/sterni/nix')
-rw-r--r-- | users/sterni/nix/char/all-chars.bin | 2 | ||||
-rw-r--r-- | users/sterni/nix/char/default.nix | 99 | ||||
-rw-r--r-- | users/sterni/nix/char/tests/default.nix | 31 | ||||
-rw-r--r-- | users/sterni/nix/flow/default.nix | 83 | ||||
-rw-r--r-- | users/sterni/nix/flow/tests/default.nix | 39 | ||||
-rw-r--r-- | users/sterni/nix/fun/default.nix | 257 | ||||
-rw-r--r-- | users/sterni/nix/fun/tests/default.nix | 82 | ||||
-rw-r--r-- | users/sterni/nix/html/README.md | 148 | ||||
-rw-r--r-- | users/sterni/nix/html/default.nix | 122 | ||||
-rw-r--r-- | users/sterni/nix/html/tests/default.nix | 93 | ||||
-rw-r--r-- | users/sterni/nix/int/default.nix | 126 | ||||
-rw-r--r-- | users/sterni/nix/int/tests/default.nix | 459 | ||||
-rw-r--r-- | users/sterni/nix/string/default.nix | 122 | ||||
-rw-r--r-- | users/sterni/nix/string/tests/default.nix | 72 | ||||
-rw-r--r-- | users/sterni/nix/url/default.nix | 100 | ||||
-rw-r--r-- | users/sterni/nix/url/tests/default.nix | 58 | ||||
-rw-r--r-- | users/sterni/nix/utf8/default.nix | 325 | ||||
-rw-r--r-- | users/sterni/nix/utf8/tests/default.nix | 148 |
18 files changed, 2366 insertions, 0 deletions
diff --git a/users/sterni/nix/char/all-chars.bin b/users/sterni/nix/char/all-chars.bin new file mode 100644 index 000000000000..017b909e8e8e --- /dev/null +++ b/users/sterni/nix/char/all-chars.bin @@ -0,0 +1,2 @@ + + !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ \ No newline at end of file diff --git a/users/sterni/nix/char/default.nix b/users/sterni/nix/char/default.nix new file mode 100644 index 000000000000..9c6ce2fb250b --- /dev/null +++ b/users/sterni/nix/char/default.nix @@ -0,0 +1,99 @@ +{ depot, lib, pkgs, ... }: + +let + + inherit (depot.users.sterni.nix.flow) + cond + ; + + inherit (depot.nix) + yants + ; + + inherit (depot.users.sterni.nix) + string + ; + + # A char is the atomic element of a nix string + # which is essentially an array of arbitrary bytes + # as long as they are not a NUL byte. + # + # A char is neither a byte nor a unicode codepoint! + char = yants.restrict "char" (s: builtins.stringLength s == 1) yants.string; + + # integer representation of char + charval = yants.restrict "charval" (i: i >= 1 && i < 256) yants.int; + + allChars = builtins.readFile ./all-chars.bin; + + # Originally I searched a list for this, but came to the + # conclusion that this can never be fast enough in Nix. + # We therefore use a solution similar to infinisil's. + ordMap = builtins.listToAttrs + (lib.imap1 (i: v: { name = v; value = i; }) + (string.toChars allChars)); + + # Note on performance: + # chr and ord have been benchmarked using the following cases: + # + # builtins.map ord (lib.stringToCharacters allChars) + # builtins.map chr (builtins.genList (int.add 1) 255 + # + # The findings are as follows: + # 1. Searching through either strings using recursion is + # unbearably slow in Nix, leading to evaluation times + # of up to 3s for the following very small test case. + # This is why we use the trusty attribute set for ord. + # 2. String indexing is much faster than list indexing which + # is why we use the former for chr. + ord = c: ordMap."${c}"; + + chr = i: string.charAt (i - 1) allChars; + + asciiAlpha = c: + let + v = ord c; + in + (v >= 65 && v <= 90) + || (v >= 97 && v <= 122); + + asciiNum = c: + let + v = ord c; + in + v >= 48 && v <= 57; + + asciiAlphaNum = c: asciiAlpha c || asciiNum c; + +in +{ + inherit + allChars + char + charval + ord + chr + asciiAlpha + asciiNum + asciiAlphaNum + ; + + # originally I generated a nix file containing a list of + # characters, but infinisil uses a better way which I adapt + # which is using builtins.readFile instead of import. + __generateAllChars = pkgs.runCommandCC "generate-all-chars" + { + source = '' + #include <stdio.h> + + int main(void) { + for(int i = 1; i <= 0xff; i++) { + putchar(i); + } + } + ''; + passAsFile = [ "source" ]; + } '' + $CC -o "$out" -x c "$sourcePath" + ''; +} diff --git a/users/sterni/nix/char/tests/default.nix b/users/sterni/nix/char/tests/default.nix new file mode 100644 index 000000000000..313df474514c --- /dev/null +++ b/users/sterni/nix/char/tests/default.nix @@ -0,0 +1,31 @@ +{ depot, ... }: + +let + inherit (depot.nix.runTestsuite) + it + assertEq + runTestsuite + ; + + inherit (depot.users.sterni.nix) + char + string + int + fun + ; + + charList = string.toChars char.allChars; + + testAllCharConversion = it "tests conversion of all chars" [ + (assertEq "char.chr converts to char.allChars" + (builtins.genList (fun.rl char.chr (int.add 1)) 255) + charList) + (assertEq "char.ord converts from char.allChars" + (builtins.genList (int.add 1) 255) + (builtins.map char.ord charList)) + ]; + +in +runTestsuite "char" [ + testAllCharConversion +] diff --git a/users/sterni/nix/flow/default.nix b/users/sterni/nix/flow/default.nix new file mode 100644 index 000000000000..4bef0abb91e9 --- /dev/null +++ b/users/sterni/nix/flow/default.nix @@ -0,0 +1,83 @@ +{ depot, ... }: + +let + + inherit (depot.nix) + yants + ; + + inherit (depot.users.sterni.nix) + fun + ; + + # we must avoid evaluating any of the sublists + # as they may contain conditions that throw + condition = yants.restrict "condition" + (ls: builtins.length ls == 2) + (yants.list yants.any); + + /* Like the common lisp macro: takes a list + of two elemented lists whose first element + is a boolean. The second element of the + first list that has true as its first + element is returned. + + Type: [ [ bool a ] ] -> a + + Example: + + cond [ + [ (builtins.isString true) 12 ] + [ (3 == 2) 13 ] + [ true 42 ] + ] + + => 42 + */ + cond = conds: switch true conds; + + /* Generic pattern match-ish construct for nix. + Takes a bunch of lists which are of length + two and checks the first element for either + a predicate or a value. The second value of + the first list which either has a value equal + to or a function that evaluates to true for + the given value. + + Type: a -> [ [ (function | a) b ] ] -> b + + Example: + + switch "foo" [ + [ "smol" "SMOL!!!" ] + [ (x: builtins.stringLength x <= 3) "smol-ish" ] + [ (fun.const true) "not smol" ] + ] + + => "smol-ish" + */ + switch = x: conds: + if builtins.length conds == 0 + then builtins.throw "exhausted all conditions" + else + let + c = condition (builtins.head conds); + s = builtins.head c; + b = + if builtins.isFunction s + then s x + else x == s; + in + if b + then builtins.elemAt c 1 + else switch x (builtins.tail conds); + + + +in +{ + inherit + cond + switch + ; +} diff --git a/users/sterni/nix/flow/tests/default.nix b/users/sterni/nix/flow/tests/default.nix new file mode 100644 index 000000000000..9f974a61c7b2 --- /dev/null +++ b/users/sterni/nix/flow/tests/default.nix @@ -0,0 +1,39 @@ +{ depot, ... }: + +let + + inherit (depot.nix.runTestsuite) + runTestsuite + it + assertEq + assertThrows + ; + + inherit (depot.users.sterni.nix.flow) + cond + match + ; + + dontEval = builtins.throw "this should not get evaluated"; + + testCond = it "tests cond" [ + (assertThrows "malformed cond list" + (cond [ [ true 1 2 ] [ false 1 ] ])) + (assertEq "last is true" "last" + (cond [ + [ false dontEval ] + [ false dontEval ] + [ true "last" ] + ])) + (assertEq "first is true" 1 + (cond [ + [ true 1 ] + [ true dontEval ] + [ true dontEval ] + ])) + ]; + +in +runTestsuite "nix.flow" [ + testCond +] diff --git a/users/sterni/nix/fun/default.nix b/users/sterni/nix/fun/default.nix new file mode 100644 index 000000000000..bb10f9e6c1bf --- /dev/null +++ b/users/sterni/nix/fun/default.nix @@ -0,0 +1,257 @@ +{ depot, lib, ... }: + +let + + inherit (lib) + id + ; + + # Simple function composition, + # application is right to left. + rl = f1: f2: + (x: f1 (f2 x)); + + # Compose a list of functions, + # application is right to left. + rls = fs: + builtins.foldl' (fOut: f: lr f fOut) id fs; + + # Simple function composition, + # application is left to right. + lr = f1: f2: + (x: f2 (f1 x)); + + # Compose a list of functions, + # application is left to right + lrs = x: fs: + builtins.foldl' (v: f: f v) x fs; + + # Warning: cursed function + # + # Check if a function has an attribute + # set pattern with an ellipsis as its argument. + # + # s/o to puck for discovering that you could use + # builtins.toXML to introspect functions more than + # you should be able to in Nix. + hasEllipsis = f: + builtins.isFunction f && + builtins.match ".*<attrspat ellipsis=\"1\">.*" + (builtins.toXML f) != null; + + /* Return the number of arguments the given function accepts or 0 if the value + is not a function. + + Example: + + argCount argCount + => 1 + + argCount builtins.add + => 2 + + argCount pkgs.stdenv.mkDerivation + => 1 + */ + argCount = f: + let + # N.B. since we are only interested if the result of calling is a function + # as opposed to a normal value or evaluation failure, we never need to + # check success, as value will be false (i.e. not a function) in the + # failure case. + called = builtins.tryEval ( + f (builtins.throw "You should never see this error message") + ); + in + if !(builtins.isFunction f || builtins.isFunction (f.__functor or null)) + then 0 + else 1 + argCount called.value; + + /* Call a given function with a given list of arguments. + + Example: + + apply builtins.sub [ 20 10 ] + => 10 + */ + apply = f: args: + builtins.foldl' (f: x: f x) f args; + + # TODO(sterni): think of a better name for unapply + /* Collect n arguments into a list and pass them to the given function. + Allows calling a function that expects a list by feeding it the list + elements individually as function arguments - the limitation is + that the list must be of constant length. + + This is mainly useful for functions that wrap other, arbitrary functions + in conjunction with argCount and apply, since lists of arguments are + easier to deal with usually. + + Example: + + (unapply 3 lib.id) 1 2 3 + => [ 1 2 3 ] + + (unapply 5 lib.reverse) 1 2 null 4 5 + => [ 5 4 null 2 1 ] + + # unapply and apply compose the identity relation together + + unapply (argCount f) (apply f) + # is equivalent to f (if the function has a constant number of arguments) + + (unapply 2 (apply builtins.sub)) 20 10 + => 10 + */ + unapply = + let + unapply' = acc: n: f: x: + if n == 1 + then f (acc ++ [ x ]) + else unapply' (acc ++ [ x ]) (n - 1) f; + in + unapply' [ ]; + + /* Optimize a tail recursive Nix function by intercepting the recursive + function application and expressing it in terms of builtins.genericClosure + instead. The main benefit of this optimization is that even a naively + written recursive algorithm won't overflow the stack. + + For this to work the following things prerequisites are necessary: + + - The passed function needs to be a fix point for its self reference, + i. e. the argument to tailCallOpt needs to be of the form + `self: # function body that uses self to call itself`. + This is because tailCallOpt needs to manipulate the call to self + which otherwise wouldn't be possible due to Nix's lexical scoping. + + - The passed function may only call itself as a tail call, all other + forms of recursions will fail evaluation. + + This function was mainly written to prove that builtins.genericClosure + can be used to express any (tail) recursive algorithm. It can be used + to avoid stack overflows for deeply recursive, but naively written + functions (in the context of Nix this mainly means using recursion + instead of (ab)using more performant and less limited builtins). + A better alternative to using this function is probably translating + the algorithm to builtins.genericClosure manually. Also note that + using tailCallOpt doesn't mean that the stack won't ever overflow: + Data structures, especially lazy ones, can still cause all the + available stack space to be consumed. + + The optimization also only concerns avoiding stack overflows, + tailCallOpt will make functions slower if anything. + + Type: (F -> F) -> F where F is any tail recursive function. + + Example: + + let + label' = self: acc: n: + if n == 0 + then "This is " + acc + "cursed." + else self (acc + "very ") (n - 1); + + # Equivalent to a naive recursive implementation in Nix + label = (lib.fix label') ""; + + labelOpt = (tailCallOpt label') ""; + in + + label 5 + => "This is very very very very very cursed." + + labelOpt 5 + => "This is very very very very very cursed." + + label 10000 + => error: stack overflow (possible infinite recursion) + + labelOpt 10000 + => "This is very very very very very very very very very… + */ + tailCallOpt = f: + let + argc = argCount (lib.fix f); + + # This function simulates being f for f's self reference. Instead of + # recursing, it will just return the arguments received as a specially + # tagged set, so the recursion step can be performed later. + fakef = unapply argc (args: { + __tailCall = true; + inherit args; + }); + # Pass fakef to f so that it'll be called instead of recursing, ensuring + # only one recursion step is performed at a time. + encodedf = f fakef; + + opt = args: + let + steps = builtins.genericClosure { + # This is how we encode a (tail) call: A set with final == false + # and the list of arguments to pass to be found in args. + startSet = [ + { + key = "0"; + id = 0; + final = false; + inherit args; + } + ]; + + operator = + { id, final, ... }@state: + let + # Plumbing to make genericClosure happy + newIds = { + key = toString (id + 1); + id = id + 1; + }; + + # Perform recursion step + call = apply encodedf state.args; + + # If call encodes a new call, return the new encoded call, + # otherwise signal that we're done. + newState = + if builtins.isAttrs call && call.__tailCall or false + then newIds // { + final = false; + inherit (call) args; + } else newIds // { + final = true; + value = call; + }; + in + + if final + then [ ] # end condition for genericClosure + else [ newState ]; + }; + in + # The returned list contains intermediate steps we ignore. + (builtins.head (builtins.filter (x: x.final) steps)).value; + in + unapply argc opt; +in + +{ + inherit (lib) + fix + flip + const + ; + + inherit + id + rl + rls + lr + lrs + hasEllipsis + argCount + tailCallOpt + apply + unapply + ; +} diff --git a/users/sterni/nix/fun/tests/default.nix b/users/sterni/nix/fun/tests/default.nix new file mode 100644 index 000000000000..6b1e6fcc7b0b --- /dev/null +++ b/users/sterni/nix/fun/tests/default.nix @@ -0,0 +1,82 @@ +{ depot, ... }: + +let + inherit (depot.nix.runTestsuite) + runTestsuite + it + assertEq + ; + + inherit (depot.nix) escapeExecline; + + inherit (depot.users.sterni.nix) + fun + ; + + hasEllipsisTests = it "checks fun.hasEllipsis" [ + (assertEq "Malicious string" false + (fun.hasEllipsis (builtins.toXML ({ foo, ... }: 12)))) + (assertEq "No function" false + (fun.hasEllipsis 23)) + (assertEq "No attribute set pattern" false + (fun.hasEllipsis (a: a + 2))) + (assertEq "No ellipsis" false + (fun.hasEllipsis ({ foo, bar }: foo + bar))) + (assertEq "Ellipsis" true + (fun.hasEllipsis ({ depot, pkgs, ... }: 42))) + ]; + + argCountTests = it "checks fun.argCount" [ + (assertEq "builtins.sub has two arguments" 2 + (fun.argCount builtins.sub)) + (assertEq "fun.argCount has one argument" 1 + (fun.argCount fun.argCount)) + (assertEq "runTestsuite has two arguments" 2 + (fun.argCount runTestsuite)) + ]; + + applyTests = it "checks that fun.apply is equivalent to calling" [ + (assertEq "fun.apply builtins.sub" (builtins.sub 23 42) + (fun.apply builtins.sub [ 23 42 ])) + (assertEq "fun.apply escapeExecline" (escapeExecline [ "foo" [ "bar" ] ]) + (fun.apply escapeExecline [ [ "foo" [ "bar" ] ] ])) + ]; + + unapplyTests = it "checks fun.unapply" [ + (assertEq "fun.unapply 3 accepts 3 args" 3 + (fun.argCount (fun.unapply 3 fun.id))) + (assertEq "fun.unapply 73 accepts 73 args" 73 + (fun.argCount (fun.unapply 73 fun.id))) + (assertEq "fun.unapply 1 accepts 73 args" 1 + (fun.argCount (fun.unapply 1 fun.id))) + (assertEq "fun.unapply collects arguments correctly" + (fun.unapply 5 fun.id 1 2 3 4 5) + [ 1 2 3 4 5 ]) + (assertEq "fun.unapply calls the given function correctly" 1 + (fun.unapply 1 builtins.head 1)) + ]; + + fac' = self: acc: n: if n == 0 then acc else self (n * acc) (n - 1); + + facPlain = fun.fix fac' 1; + facOpt = fun.tailCallOpt fac' 1; + + tailCallOptTests = it "checks fun.tailCallOpt" [ + (assertEq "optimized and unoptimized factorial have the same base case" + (facPlain 0) + (facOpt 0)) + (assertEq "optimized and unoptimized factorial have same value for 1" + (facPlain 1) + (facOpt 1)) + (assertEq "optimized and unoptimized factorial have same value for 100" + (facPlain 100) + (facOpt 100)) + ]; +in +runTestsuite "nix.fun" [ + hasEllipsisTests + argCountTests + applyTests + unapplyTests + tailCallOptTests +] diff --git a/users/sterni/nix/html/README.md b/users/sterni/nix/html/README.md new file mode 100644 index 000000000000..0349e466a166 --- /dev/null +++ b/users/sterni/nix/html/README.md @@ -0,0 +1,148 @@ +# html.nix — _the_ most cursed Nix HTML DSL + +A quick example to show you what it looks like: + +```nix +# Note: this example is for standalone usage out of depot +{ pkgs ? import <nixpkgs> {} }: + +let + # zero dependency, one file implementation + htmlNix = import ./path/to/html.nix { }; + + # make the magic work + inherit (htmlNix) __findFile esc withDoctype; +in + +pkgs.writeText "example.html" (withDoctype (<html> {} [ + (<head> {} [ + (<meta> { charset = "utf-8"; } null) + (<title> {} (esc "hello world")) + ]) + (<body> {} [ + (<h1> {} (esc "hello world")) + (<p> { class = "intro"; } (esc '' + welcome to the land of sillyness! + '')) + (<ul> {} [ + (<li> {} [ + (esc "check out ") + (<a> { href = "https://code.tvl.fyi"; } "depot") + ]) + (<li> {} [ + (esc "find ") + (<a> { href = "https://cl.tvl.fyi/q/hashtag:cursed"; } "cursed things") + ]) + ]) + ]) +])) +``` + +Convince yourself it works: + +```console +$ $BROWSER $(nix-build example.nix) +``` + +Alternatively, in depot: + +```console +$ $BROWSER $(nix-build -A users.sterni.nix.html.tests) +``` + +## Creating tags + +An empty tag is passed `null` as its content argument: + +```nix +<link> { + rel = "stylesheet"; + href = "/main.css"; + type = "text/css"; +} null + +# => "<link href=\"/main.css\" rel=\"stylesheet\" type=\"text/css\"/>" +``` + +Content is expected to be HTML: + +```nix +<div> { class = "foo"; } "<strong>hi</strong>" + +# => "<div class=\"foo\"><strong>hi</strong></div>" +``` + +If it's not, be sure to escape it: + +```nix +<p> {} (esc "A => B") + +# => "<p>A => B</p>" +``` + +Nesting tags works of course: + +```nix +<div> {} (<strong> {} (<em> {} "hi")) + +# => "<div><strong><em>hi</em></strong></div>" +``` + +If the content of a tag is a list, it's concatenated: + +```nix +<h1> {} [ + (esc "The ") + (<strong> {} "Nix") + (esc " ") + (<em> {} "Expression") + (esc " Language") +] + +# => "<h1>The <strong>Nix</strong> <em>Expression</em> Language</h1>" +``` + +More detailed documentation can be found in `nixdoc`-compatible +comments in the source file (`default.nix` in this directory). + +## How does this work? + +*Theoretically* expressions like `<nixpkgs>` are just ordinary paths — +their actual value is determined from `NIX_PATH`. `html.nix` works +because of how this is actually implemented: At [parse time][spath-parsing] +Nix transparently translates an expression like `<foo>` into +`__findFile __nixPath "foo"`: + +``` +nix-repl> <nixpkgs> +/nix/var/nix/profiles/per-user/root/channels/vuizvui/nixpkgs + +nix-repl> __findFile __nixPath "nixpkgs" +/nix/var/nix/profiles/per-user/root/channels/vuizvui/nixpkgs +``` + +This translation doesn't take any scoping issues into account -- +so we can just shadow `__findFile` and make it return anything, +even a function: + +``` +nix-repl> __findFile = nixPath: str: + /**/ if str == "double" then x: x * 2 + else if str == "triple" then x: x * 3 + else throw "what?" + +nix-repl> <double> 2 +4 + +nix-repl> <triple> 3 +9 + +nix-repl> <quadruple> 4 +error: what? +``` + +Exactly this is what we are doing in `html.nix`: +Using `let inherit (htmlNix) __findFile; in` we shadow the builtin `__findFile` +with a function which returns a function rendering a particular HTML tag. + +[spath-parsing]: https://github.com/NixOS/nix/blob/293220bed5a75efc963e33c183787e87e55e28d9/src/libexpr/parser.y#L410-L416 diff --git a/users/sterni/nix/html/default.nix b/users/sterni/nix/html/default.nix new file mode 100644 index 000000000000..d25a7ab8dac0 --- /dev/null +++ b/users/sterni/nix/html/default.nix @@ -0,0 +1,122 @@ +# Copyright © 2021 sterni +# SPDX-License-Identifier: MIT +# +# This file provides a cursed HTML DSL for nix which works by overloading +# the NIX_PATH lookup operation via angle bracket operations, e. g. `<nixpkgs>`. + +{ ... }: + +let + /* Escape everything we have to escape in an HTML document if either + in a normal context or an attribute string (`<>&"'`). + + A shorthand for this function called `esc` is also provided. + + Type: string -> string + + Example: + + escapeMinimal "<hello>" + => "<hello>" + */ + escapeMinimal = builtins.replaceStrings + [ "<" ">" "&" "\"" "'" ] + [ "<" ">" "&" """ "'" ]; + + /* Return a string with a correctly rendered tag of the given name, + with the given attributes which are automatically escaped. + + If the content argument is `null`, the tag will have no children nor a + closing element. If the content argument is a string it is used as the + content as is (unescaped). If the content argument is a list, its + elements are concatenated. + + `renderTag` is only an internal function which is reexposed as `__findFile` + to allow for much neater syntax than calling `renderTag` everywhere: + + ```nix + { depot, ... }: + let + inherit (depot.users.sterni.nix.html) __findFile esc; + in + + <html> {} [ + (<head> {} (<title> {} (esc "hello world"))) + (<body> {} [ + (<h1> {} (esc "hello world")) + (<p> {} (esc "foo bar")) + ]) + ] + + ``` + + As you can see, the need to call a function disappears, instead the + `NIX_PATH` lookup operation via `<foo>` is overloaded, so it becomes + `renderTag "foo"` automatically. + + Since the content argument may contain the result of other `renderTag` + calls, we can't escape it automatically. Instead this must be done manually + using `esc`. + + Type: string -> attrs<string> -> (list<string> | string | null) -> string + + Example: + + <link> { + rel = "stylesheet"; + href = "/css/main.css"; + type = "text/css"; + } null + + renderTag "link" { + rel = "stylesheet"; + href = "/css/main.css"; + type = "text/css"; + } null + + => "<link href=\"/css/main.css\" rel=\"stylesheet\" type=\"text/css\"/>" + + <p> {} [ + "foo " + (<strong> {} "bar") + ] + + renderTag "p" {} "foo <strong>bar</strong>" + => "<p>foo <strong>bar</strong></p>" + */ + renderTag = tag: attrs: content: + let + attrs' = builtins.concatStringsSep "" ( + builtins.map + (n: + " ${escapeMinimal n}=\"${escapeMinimal (toString attrs.${n})}\"" + ) + (builtins.attrNames attrs) + ); + content' = + if builtins.isList content + then builtins.concatStringsSep "" content + else content; + in + if content == null + then "<${tag}${attrs'}/>" + else "<${tag}${attrs'}>${content'}</${tag}>"; + + /* Prepend "<!DOCTYPE html>" to a string. + + Type: string -> string + + Example: + + withDoctype (<body> {} (esc "hello")) + => "<!DOCTYPE html><body>hello</body>" + */ + withDoctype = doc: "<!DOCTYPE html>" + doc; + +in +{ + inherit escapeMinimal renderTag withDoctype; + + __findFile = _: renderTag; + esc = escapeMinimal; +} diff --git a/users/sterni/nix/html/tests/default.nix b/users/sterni/nix/html/tests/default.nix new file mode 100644 index 000000000000..0d80f2f1cd70 --- /dev/null +++ b/users/sterni/nix/html/tests/default.nix @@ -0,0 +1,93 @@ +{ depot, pkgs, ... }: + +let + inherit (depot.users.sterni.nix.html) + __findFile + esc + withDoctype + ; + + exampleDocument = withDoctype (<html> { lang = "en"; } [ + (<head> { } [ + (<meta> { charset = "utf-8"; } null) + (<title> { } "html.nix example document") + (<link> + { + rel = "license"; + href = "https://code.tvl.fyi/about/LICENSE"; + type = "text/html"; + } + null) + (<style> { } (esc '' + hgroup h2 { + font-weight: normal; + } + + dd { + margin: 0; + } + '')) + ]) + (<body> { } [ + (<main> { } [ + (<hgroup> { } [ + (<h1> { } (esc "html.nix")) + (<h2> { } [ + (<em> { } "the") + (esc " most cursed HTML DSL ever!") + ]) + ]) + (<dl> { } [ + (<dt> { } [ + (esc "Q: Wait, it's all ") + (<a> + { + href = "https://cl.tvl.fyi/q/hashtag:cursed"; + } + (esc "cursed")) + (esc " nix hacks?") + ]) + (<dd> { } (esc "A: Always has been. 🔫")) + (<dt> { } (esc "Q: Why does this work?")) + (<dd> { } [ + (esc "Because nix ") + (<a> + { + href = "https://github.com/NixOS/nix/blob/293220bed5a75efc963e33c183787e87e55e28d9/src/libexpr/parser.y#L410-L416"; + } + (esc "translates ")) + (<a> + { + href = "https://github.com/NixOS/nix/blob/293220bed5a75efc963e33c183787e87e55e28d9/src/libexpr/lexer.l#L100"; + } + (esc "SPATH tokens")) + (esc " like ") + (<code> { } (esc "<nixpkgs>")) + (esc " into calls to ") + (<code> { } (esc "__findFile")) + (esc " in the ") + (<em> { } (esc "current")) + (esc " scope.") + ]) + ]) + ]) + ]) + ]); +in + +pkgs.runCommandNoCC "html.nix.html" +{ + passAsFile = [ "exampleDocument" ]; + inherit exampleDocument; + nativeBuildInputs = [ pkgs.html5validator ]; +} '' + set -x + test "${esc "<> && \" \'"}" = "<> && " '" + + # slow as hell unfortunately + html5validator "$exampleDocumentPath" + + mv "$exampleDocumentPath" "$out" + + set +x +'' diff --git a/users/sterni/nix/int/default.nix b/users/sterni/nix/int/default.nix new file mode 100644 index 000000000000..54b55964722d --- /dev/null +++ b/users/sterni/nix/int/default.nix @@ -0,0 +1,126 @@ +{ depot, lib, ... }: + +let + + # TODO(sterni): implement nix.float and figure out which of these + # functions can be split out into a common nix.num + # library. + + inherit (depot.users.sterni.nix) + string + ; + + inherit (builtins) + bitOr + bitAnd + bitXor + mul + div + add + sub + ; + + abs = i: if i < 0 then -i else i; + + exp = base: pow: + if pow > 0 + then base * (exp base (pow - 1)) + else if pow < 0 + then 1.0 / exp base (abs pow) + else 1; + + bitShiftR = bit: count: + if count == 0 + then bit + else div (bitShiftR bit (count - 1)) 2; + + bitShiftL = bit: count: + if count == 0 + then bit + else 2 * (bitShiftL bit (count - 1)); + + hexdigits = "0123456789ABCDEF"; + + toHex = int: + let + go = i: + if i == 0 + then "" + else go (bitShiftR i 4) + + string.charAt (bitAnd i 15) hexdigits; + sign = lib.optionalString (int < 0) "-"; + in + if int == 0 + then "0" + else "${sign}${go (abs int)}"; + + fromHexMap = builtins.listToAttrs + (lib.imap0 (i: c: { name = c; value = i; }) + (lib.stringToCharacters hexdigits)); + + fromHex = literal: + let + negative = string.charAt 0 literal == "-"; + start = if negative then 1 else 0; + len = builtins.stringLength literal; + # reversed list of all digits + digits = builtins.genList + (i: string.charAt (len - 1 - i) literal) + (len - start); + parsed = builtins.foldl' + (v: d: { + val = v.val + (fromHexMap."${d}" * v.mul); + mul = v.mul * 16; + }) + { val = 0; mul = 1; } + digits; + in + if negative + then -parsed.val + else parsed.val; + + # A nix integer is a 64bit signed integer + maxBound = 9223372036854775807; + + # fun fact: -9223372036854775808 is the lower bound + # for a nix integer (as you would expect), but you can't + # use it as an integer literal or you'll be greeted with: + # error: invalid integer '9223372036854775808' + # This is because all int literals when parsing are + # positive, negative "literals" are positive literals + # which are preceded by the arithmetric negation operator. + minBound = -9223372036854775807 - 1; + + odd = x: bitAnd x 1 == 1; + even = x: bitAnd x 1 == 0; + + # div and mod behave like quot and rem in Haskell, + # i. e. they truncate towards 0 + mod = a: b: let res = a / b; in a - (res * b); + + inRange = a: b: x: x >= a && x <= b; + +in +{ + inherit + maxBound + minBound + abs + exp + odd + even + add + sub + mul + div + mod + bitShiftR + bitShiftL + bitOr + bitAnd + bitXor + toHex + fromHex + inRange + ; +} diff --git a/users/sterni/nix/int/tests/default.nix b/users/sterni/nix/int/tests/default.nix new file mode 100644 index 000000000000..8d2263b42117 --- /dev/null +++ b/users/sterni/nix/int/tests/default.nix @@ -0,0 +1,459 @@ +{ depot, lib, ... }: + +let + + inherit (depot.nix.runTestsuite) + runTestsuite + it + assertEq + ; + + inherit (depot.users.sterni.nix) + int + string + fun + ; + + testBounds = it "checks minBound and maxBound" [ + # this is gonna blow up in my face because + # integer overflow is undefined behavior in + # C++, so most likely anything could happen? + (assertEq "maxBound is the maxBound" true + (int.maxBound + 1 < int.maxBound)) + (assertEq "minBound is the minBound" true + (int.minBound - 1 > int.minBound)) + (assertEq "maxBound overflows to minBound" + (int.maxBound + 1) + int.minBound) + (assertEq "minBound overflows to maxBound" + (int.minBound - 1) + int.maxBound) + ]; + + expectedBytes = [ + "00" + "01" + "02" + "03" + "04" + "05" + "06" + "07" + "08" + "09" + "0A" + "0B" + "0C" + "0D" + "0E" + "0F" + "10" + "11" + "12" + "13" + "14" + "15" + "16" + "17" + "18" + "19" + "1A" + "1B" + "1C" + "1D" + "1E" + "1F" + "20" + "21" + "22" + "23" + "24" + "25" + "26" + "27" + "28" + "29" + "2A" + "2B" + "2C" + "2D" + "2E" + "2F" + "30" + "31" + "32" + "33" + "34" + "35" + "36" + "37" + "38" + "39" + "3A" + "3B" + "3C" + "3D" + "3E" + "3F" + "40" + "41" + "42" + "43" + "44" + "45" + "46" + "47" + "48" + "49" + "4A" + "4B" + "4C" + "4D" + "4E" + "4F" + "50" + "51" + "52" + "53" + "54" + "55" + "56" + "57" + "58" + "59" + "5A" + "5B" + "5C" + "5D" + "5E" + "5F" + "60" + "61" + "62" + "63" + "64" + "65" + "66" + "67" + "68" + "69" + "6A" + "6B" + "6C" + "6D" + "6E" + "6F" + "70" + "71" + "72" + "73" + "74" + "75" + "76" + "77" + "78" + "79" + "7A" + "7B" + "7C" + "7D" + "7E" + "7F" + "80" + "81" + "82" + "83" + "84" + "85" + "86" + "87" + "88" + "89" + "8A" + "8B" + "8C" + "8D" + "8E" + "8F" + "90" + "91" + "92" + "93" + "94" + "95" + "96" + "97" + "98" + "99" + "9A" + "9B" + "9C" + "9D" + "9E" + "9F" + "A0" + "A1" + "A2" + "A3" + "A4" + "A5" + "A6" + "A7" + "A8" + "A9" + "AA" + "AB" + "AC" + "AD" + "AE" + "AF" + "B0" + "B1" + "B2" + "B3" + "B4" + "B5" + "B6" + "B7" + "B8" + "B9" + "BA" + "BB" + "BC" + "BD" + "BE" + "BF" + "C0" + "C1" + "C2" + "C3" + "C4" + "C5" + "C6" + "C7" + "C8" + "C9" + "CA" + "CB" + "CC" + "CD" + "CE" + "CF" + "D0" + "D1" + "D2" + "D3" + "D4" + "D5" + "D6" + "D7" + "D8" + "D9" + "DA" + "DB" + "DC" + "DD" + "DE" + "DF" + "E0" + "E1" + "E2" + "E3" + "E4" + "E5" + "E6" + "E7" + "E8" + "E9" + "EA" + "EB" + "EC" + "ED" + "EE" + "EF" + "F0" + "F1" + "F2" + "F3" + "F4" + "F5" + "F6" + "F7" + "F8" + "F9" + "FA" + "FB" + "FC" + "FD" + "FE" + "FF" + ]; + + hexByte = i: string.fit { width = 2; char = "0"; } (int.toHex i); + + hexInts = [ + { left = 0; right = "0"; } + { left = 1; right = "1"; } + { left = 11; right = "B"; } + { left = 123; right = "7B"; } + { left = 9000; right = "2328"; } + { left = 2323; right = "913"; } + { left = 4096; right = "1000"; } + { left = int.maxBound; right = "7FFFFFFFFFFFFFFF"; } + { left = int.minBound; right = "-8000000000000000"; } + ]; + + testHex = it "checks conversion to hex" (lib.flatten [ + (lib.imap0 + (i: hex: [ + (assertEq "hexByte ${toString i} == ${hex}" (hexByte i) hex) + (assertEq "${toString i} == fromHex ${hex}" i (int.fromHex hex)) + ]) + expectedBytes) + (builtins.map + ({ left, right }: [ + (assertEq "toHex ${toString left} == ${right}" (int.toHex left) right) + (assertEq "${toString left} == fromHex ${right}" left (int.fromHex right)) + ]) + hexInts) + ]); + + testBasic = it "checks basic int operations" [ + (assertEq "122 is even" (int.even 122 && !(int.odd 122)) true) + (assertEq "123 is odd" (int.odd 123 && !(int.even 123)) true) + (assertEq "abs -4959" (int.abs (-4959)) 4959) + ]; + + expNumbers = [ + { left = -3; right = 0.125; } + { left = -2; right = 0.25; } + { left = -1; right = 0.5; } + { left = 0; right = 1; } + { left = 1; right = 2; } + { left = 2; right = 4; } + { left = 3; right = 8; } + { left = 4; right = 16; } + { left = 5; right = 32; } + { left = 16; right = 65536; } + ]; + + testExp = it "checks exponentiation" + (builtins.map + ({ left, right }: + assertEq + "2 ^ ${toString left} == ${toString right}" + (int.exp 2 left) + right) + expNumbers); + + shifts = [ + { a = 2; b = 5; c = 64; op = "<<"; } + { a = -2; b = 5; c = -64; op = "<<"; } + { a = 123; b = 4; c = 1968; op = "<<"; } + { a = 1; b = 8; c = 256; op = "<<"; } + { a = 256; b = 8; c = 1; op = ">>"; } + { a = 374; b = 2; c = 93; op = ">>"; } + { a = 2; b = 2; c = 0; op = ">>"; } + { a = 99; b = 9; c = 0; op = ">>"; } + ]; + + checkShift = { a, b, c, op }@args: + let + f = string.match op { + "<<" = int.bitShiftL; + ">>" = int.bitShiftR; + }; + in + assertEq "${toString a} ${op} ${toString b} == ${toString c}" (f a b) c; + + checkShiftRDivExp = n: + assertEq "${toString n} >> 5 == ${toString n} / 2 ^ 5" + (int.bitShiftR n 5) + (int.div n (int.exp 2 5)); + + checkShiftLMulExp = n: + assertEq "${toString n} >> 6 == ${toString n} * 2 ^ 6" + (int.bitShiftL n 5) + (int.mul n (int.exp 2 5)); + + testBit = it "checks bitwise operations" (lib.flatten [ + (builtins.map checkShift shifts) + (builtins.map checkShiftRDivExp [ + 1 + 2 + 3 + 5 + 7 + 23 + 1623 + 238 + 34 + 348 + 2834 + 834 + 348 + ]) + (builtins.map checkShiftLMulExp [ + 1 + 2 + 3 + 5 + 7 + 23 + 384 + 3 + 2 + 5991 + 85109 + 38 + ]) + ]); + + divisions = [ + { a = 2; b = 1; c = 2; mod = 0; } + { a = 2; b = 2; c = 1; mod = 0; } + { a = 20; b = 10; c = 2; mod = 0; } + { a = 12; b = 5; c = 2; mod = 2; } + { a = 23; b = 4; c = 5; mod = 3; } + ]; + + checkDiv = n: { a, b, c, mod }: [ + (assertEq "${n}: div result" (int.div a b) c) + (assertEq "${n}: mod result" (int.mod a b) mod) + (assertEq "${n}: divMod law" ((int.div a b) * b + (int.mod a b)) a) + ]; + + testDivMod = it "checks integer division and modulo" + (lib.flatten [ + (builtins.map (checkDiv "+a / +b") divisions) + (builtins.map + (fun.rl (checkDiv "-a / +b") (x: x // { + a = -x.a; + c = -x.c; + mod = -x.mod; + })) + divisions) + (builtins.map + (fun.rl (checkDiv "+a / -b") (x: x // { + b = -x.b; + c = -x.c; + })) + divisions) + (builtins.map + (fun.rl (checkDiv "-a / -b") (x: x // { + a = -x.a; + b = -x.b; + mod = -x.mod; + })) + divisions) + ]); + +in +runTestsuite "nix.int" [ + testBounds + testHex + testBasic + testExp + testBit + testDivMod +] diff --git a/users/sterni/nix/string/default.nix b/users/sterni/nix/string/default.nix new file mode 100644 index 000000000000..852ef2538fdc --- /dev/null +++ b/users/sterni/nix/string/default.nix @@ -0,0 +1,122 @@ +{ depot, lib, ... }: + +let + + inherit (depot.users.sterni.nix.char) + chr + ord + ; + + inherit (depot.users.sterni.nix) + int + flow + ; + + take = n: s: + builtins.substring 0 n s; + + drop = n: s: + builtins.substring n int.maxBound s; + + charAt = i: s: + let + r = builtins.substring i 1 s; + in + if r == "" then null else r; + + charIndex = char: s: + let + len = builtins.stringLength s; + go = i: + flow.cond [ + [ (i >= len) null ] + [ (charAt i s == char) i ] + [ true (go (i + 1)) ] + ]; + in + go 0; + + toChars = lib.stringToCharacters; + fromChars = lib.concatStrings; + + toBytes = str: + builtins.map ord (toChars str); + + fromBytes = is: lib.concatMapStrings chr is; + + pad = { left ? 0, right ? 0, char ? " " }: s: + let + leftS = fromChars (builtins.genList (_: char) left); + rightS = fromChars (builtins.genList (_: char) right); + in + "${leftS}${s}${rightS}"; + + fit = { char ? " ", width, side ? "left" }: s: + let + diff = width - builtins.stringLength s; + in + if diff <= 0 + then s + else pad { inherit char; "${side}" = diff; } s; + + # pattern matching for strings only + match = val: matcher: matcher."${val}"; + + /* Bare-bones printf implementation. Supported format specifiers: + + * `%%` escapes `%` + * `%s` is substituted by a string + + As expected, the first argument is a format string and the values + for its format specifiers need to provided as the next arguments + in order. + + Type: string -> (printfVal : either string (a -> printfVal)) + */ + printf = formatString: + let + specifierWithArg = token: builtins.elem token [ + "%s" + ]; + isSpecifier = lib.hasPrefix "%"; + + tokens = lib.flatten (builtins.split "(%.)" formatString); + argsNeeded = builtins.length (builtins.filter specifierWithArg tokens); + + format = args: (builtins.foldl' + ({ out ? "", argIndex ? 0 }: token: { + argIndex = argIndex + (if specifierWithArg token then 1 else 0); + out = + /**/ + if token == "%s" then out + builtins.elemAt args argIndex + else if token == "%%" then out + "%" + else if isSpecifier token then throw "Unsupported format specifier ${token}" + else out + token; + }) + { } + tokens).out; + + accumulateArgs = argCount: args: + if argCount > 0 + then arg: accumulateArgs (argCount - 1) (args ++ [ arg ]) + else format args; + in + accumulateArgs argsNeeded [ ]; + +in +{ + inherit + take + drop + charAt + charIndex + toBytes + fromBytes + toChars + fromChars + pad + fit + match + printf + ; +} diff --git a/users/sterni/nix/string/tests/default.nix b/users/sterni/nix/string/tests/default.nix new file mode 100644 index 000000000000..e9015e95dca4 --- /dev/null +++ b/users/sterni/nix/string/tests/default.nix @@ -0,0 +1,72 @@ +{ depot, ... }: + +let + + inherit (depot.users.sterni.nix) + string + ; + + inherit (depot.nix.runTestsuite) + it + assertEq + runTestsuite + ; + + testTakeDrop = it "tests take and drop" [ + (assertEq "take" + (string.take 5 "five and more") + "five ") + (assertEq "drop" + (string.drop 2 "coin") + "in") + (assertEq "take out of bounds" + (string.take 100 "foo") + "foo") + (assertEq "drop out of bounds" + (string.drop 42 "lol") + "") + ]; + + testIndexing = it "tests string indexing" [ + (assertEq "normal charAt" + (string.charAt 3 "helo") + "o") + (assertEq "out of bounds charAt" + (string.charAt 5 "helo") + null) + ]; + + testFinding = it "tests finding in strings" [ + (assertEq "normal charIndex" + (string.charIndex "d" "abcdefghijkl") + 3) + (assertEq "charIndex no match" + (string.charIndex "w" "zZzZzzzZZZ") + null) + ]; + + dontEval = builtins.throw "this should not get evaluated"; + + testMatch = it "tests match" [ + (assertEq "basic match usage" 42 + (string.match "answer" { + "answer" = 42; + "banana" = dontEval; + "maleur" = dontEval; + })) + ]; + + f = "f"; + testPrintf = it "prints f" [ + (assertEq "basic %s usage" "print ${f}" (string.printf "print %s" f)) + (assertEq "% escaping" "100%" (string.printf "100%%")) + ]; + +in +runTestsuite "nix.string" [ + testTakeDrop + testIndexing + testFinding + testMatch + testPrintf +] diff --git a/users/sterni/nix/url/default.nix b/users/sterni/nix/url/default.nix new file mode 100644 index 000000000000..4a401873a1f2 --- /dev/null +++ b/users/sterni/nix/url/default.nix @@ -0,0 +1,100 @@ +{ depot, lib, ... }: + +let + + inherit (depot.users.sterni.nix) + char + int + string + flow + ; + + reserved = c: builtins.elem c [ + "!" + "#" + "$" + "&" + "'" + "(" + ")" + "*" + "+" + "," + "/" + ":" + ";" + "=" + "?" + "@" + "[" + "]" + ]; + + unreserved = c: char.asciiAlphaNum c + || builtins.elem c [ "-" "_" "." "~" ]; + + percentEncode = c: + if unreserved c + then c + else "%" + (string.fit + { + width = 2; + char = "0"; + side = "left"; + } + (int.toHex (char.ord c))); + + encode = { leaveReserved ? false }: s: + let + chars = lib.stringToCharacters s; + tr = c: + if leaveReserved && reserved c + then c + else percentEncode c; + in + lib.concatStrings (builtins.map tr chars); + + decode = s: + let + tokens = builtins.split "%" s; + decodeStep = + { result ? "" + , inPercent ? false + }: s: + flow.cond [ + [ + (builtins.isList s) + { + inherit result; + inPercent = true; + } + ] + [ + inPercent + { + inPercent = false; + # first two characters came after an % + # the rest is the string until the next % + result = result + + char.chr (int.fromHex (string.take 2 s)) + + (string.drop 2 s); + } + ] + [ + (!inPercent) + { + result = result + s; + } + ] + ]; + + in + (builtins.foldl' decodeStep { } tokens).result; + +in +{ + inherit + encode + decode + ; +} diff --git a/users/sterni/nix/url/tests/default.nix b/users/sterni/nix/url/tests/default.nix new file mode 100644 index 000000000000..4eb6f95ccd07 --- /dev/null +++ b/users/sterni/nix/url/tests/default.nix @@ -0,0 +1,58 @@ +{ depot, ... }: + +let + + inherit (depot.nix.runTestsuite) + it + assertEq + runTestsuite + ; + + inherit (depot.users.sterni.nix) + url + ; + + checkEncoding = args: { left, right }: + assertEq "encode ${builtins.toJSON left} == ${builtins.toJSON right}" + (url.encode args left) + right; + + checkDecoding = { left, right }: + assertEq "${builtins.toJSON left} == decode ${builtins.toJSON right}" + (url.decode left) + right; + + unreserved = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.-_~"; + + encodeExpected = [ + { left = "Laguna Beach"; right = "Laguna%20Beach"; } + { left = "👾 Exterminate!"; right = "%F0%9F%91%BE%20Exterminate%21"; } + { left = unreserved; right = unreserved; } + { + left = "`!@#$%^&*()+={}[]:;'\\|<>,?/ \""; + right = "%60%21%40%23%24%25%5E%26%2A%28%29%2B%3D%7B%7D%5B%5D%3A%3B%27%5C%7C%3C%3E%2C%3F%2F%20%22"; + } + ]; + + testEncode = it "checks url.encode" + (builtins.map (checkEncoding { }) encodeExpected); + + testDecode = it "checks url.decode" + (builtins.map checkDecoding encodeExpected); + + testLeaveReserved = it "checks that leaveReserved is like id for valid URLs" + (builtins.map (x: checkEncoding { leaveReserved = true; } { left = x; right = x; }) [ + "ftp://ftp.is.co.za/rfc/rfc1808.txt" + "http://www.ietf.org/rfc/rfc2396.txt" + "ldap://[2001:db8::7]/c=GB?objectClass?one" + "mailto:John.Doe@example.com" + "news:comp.infosystems.www.servers.unix" + "tel:+1-816-555-1212" + "telnet://192.0.2.16:80/" + "urn:oasis:names:specification:docbook:dtd:xml:4.1.2" + ]); +in +runTestsuite "nix.url" [ + testEncode + testLeaveReserved +] diff --git a/users/sterni/nix/utf8/default.nix b/users/sterni/nix/utf8/default.nix new file mode 100644 index 000000000000..71c846c0421e --- /dev/null +++ b/users/sterni/nix/utf8/default.nix @@ -0,0 +1,325 @@ +{ depot, lib, ... }: + +let + + inherit (depot.users.sterni.nix) + char + flow + fun + int + string + util + ; + + /* (Internal) function to determine the amount + bytes left in a UTF-8 byte sequence from the + first byte. + + This function will throw if the given first + byte is ill-formed, but will not detect all + cases of ill-formed-ness. + + Based on table 3-6. from The Unicode Standard, + Version 13.0, section 3.9. + + Type: integer -> integer + */ + byteCount = i: flow.cond [ + [ (int.bitAnd i 128 == 0) 1 ] + [ (int.bitAnd i 224 == 192) 2 ] + [ (int.bitAnd i 240 == 224) 3 ] + [ (int.bitAnd i 248 == 240) 4 ] + [ true (builtins.throw "Ill-formed first byte ${int.toHex i}") ] + ]; + + /* (Internal) function to check if a given byte in + an UTF-8 byte sequence is well-formed. + + Based on table 3-7. from The Unicode Standard, + Version 13.0, section 3.9. + + Type: integer -> integer -> integer -> bool + */ + wellFormedByte = + # first byte's integer value + first: + # byte position as an index starting with 0 + pos: + let + defaultRange = int.inRange 128 191; + + secondBytePredicate = flow.switch first [ + [ (int.inRange 194 223) defaultRange ] # C2..DF + [ 224 (int.inRange 160 191) ] # E0 + [ (int.inRange 225 236) defaultRange ] # E1..EC + [ 237 (int.inRange 128 159) ] # ED + [ (int.inRange 238 239) defaultRange ] # EE..EF + [ 240 (int.inRange 144 191) ] # F0 + [ (int.inRange 241 243) defaultRange ] # F1..F3 + [ 244 (int.inRange 128 143) ] # F4 + [ (fun.const true) null ] + ]; + + firstBytePredicate = byte: assert first == byte; + first < 128 || secondBytePredicate != null; + in + # Either ASCII or in one of the byte ranges of Table 3-6. + if pos == 0 then firstBytePredicate + # return predicate according to Table 3-6. + else if pos == 1 then assert secondBytePredicate != null; secondBytePredicate + # 3rd and 4th byte have only one validity rule + else defaultRange; + + /* Iteration step for decoding an UTF-8 byte sequence. + It decodes incrementally, i. e. it has to be fed + one byte at a time and then returns either a + new state or a final result. + + If the resulting attribute set contains the attribute + result, it is finished and the decoded codepoint is + contained in that attribute. In all other cases, + pass the returned set to step again along with + a new byte. The initial state to pass is the empty + set. + + Extra attributes are always passed through, so you + can pass extra state. Be sure not to use result, + pos, code, first or count. + + This function will throw with a fairly detailed + message if it encounters ill-formed bytes. + + The implementation is based on The Unicode Standard, + Version 13.0, section 3.9, especially table 3-6. + + Type: { ... } -> string -> ({ result :: integer, ... } | { ... }) + + Example: utf8.step {} "f" + => { result = 102; } + */ + step = { pos ? 0, code ? 0, ... }@args: byte: + let + value = char.ord byte; + # first byte is context for well-formed-ness + first = args.first or value; + count = args.count or (byteCount first); + newCode = + if count == 1 + then int.bitAnd 127 first # ascii character + else # multi byte UTF-8 sequence + let + # Calculate the bitmask for extracting the + # codepoint data in the current byte. + # If the codepoint is not ASCII, the bits + # used for codepoint data differ depending + # on the byte position and overall byte + # count. The first byte always ignores + # the (count + 1) most significant bits. + # For all subsequent bytes, the 2 most + # significant bits need to be ignored. + # See also table 3-6. + mask = + if pos == 0 + then int.exp 2 (8 - (count + 1)) - 1 + else 63; + # UTF-8 uses the 6 least significant bits in all + # subsequent bytes after the first one. Therefore + # We can determine the amount we need to shift + # the current value by the amount of bytes left. + offset = (count - (pos + 1)) * 6; + in + code + (int.bitShiftL (int.bitAnd mask value) offset); + illFormedMsg = + "Ill-formed byte ${int.toHex value} at position ${toString pos} in ${toString count} byte UTF-8 sequence"; + in + if !(wellFormedByte first pos value) then builtins.throw illFormedMsg + else if pos + 1 == count + then (builtins.removeAttrs args [ + # allow extra state being passed through + "count" + "code" + "pos" + "first" + ]) // { result = newCode; } + else (builtins.removeAttrs args [ "result" ]) // { + inherit count first; + code = newCode; + pos = pos + 1; + }; + + /* Decode an UTF-8 string into a list of codepoints. + + Throws if the string is ill-formed UTF-8. + + Type: string -> [ integer ] + */ + # TODO(sterni): option to fallback to replacement char instead of failure + decode = s: + let + stringLength = builtins.stringLength s; + iterResult = builtins.genericClosure { + startSet = [ + { + key = "start"; + stringIndex = -1; + state = { }; + codepoint = null; + } + ]; + operator = { state, stringIndex, ... }: + let + # updated values for current iteration step + newIndex = stringIndex + 1; + newState = step state (builtins.substring newIndex 1 s); + in + lib.optional (newIndex < stringLength) { + # unique keys to make genericClosure happy + key = toString newIndex; + # carryover state for the next step + stringIndex = newIndex; + state = newState; + # actual payload for later, steps with value null are filtered out + codepoint = newState.result or null; + }; + }; + in + # extract all steps that yield a code point into a list + builtins.map (v: v.codepoint) ( + builtins.filter + ( + { codepoint, stringIndex, state, ... }: + + let + # error message in case we are missing bytes at the end of input + earlyEndMsg = + if state ? count && state ? pos + then "Missing ${toString (with state; count - pos)} bytes at end of input" + else "Unexpected end of input"; + in + + # filter out all iteration steps without a codepoint value + codepoint != null + # if we are at the iteration step of a non-empty input string, throw + # an error if no codepoint was returned, as it indicates an incomplete + # UTF-8 sequence. + || (stringLength > 0 && stringIndex == stringLength - 1 && throw earlyEndMsg) + + ) + iterResult + ); + + /* Pretty prints a Unicode codepoint in the U+<HEX> notation. + + Type: integer -> string + */ + formatCodepoint = cp: "U+" + string.fit + { + width = 4; + char = "0"; + } + (int.toHex cp); + + encodeCodepoint = cp: + let + # Find the amount of bytes needed to encode the given codepoint. + # Note that this doesn't check if the Unicode codepoint is allowed, + # but rather allows all theoretically UTF-8-encodeable ones. + count = flow.switch cp [ + [ (int.inRange 0 127) 1 ] # 00000000 0xxxxxxx + [ (int.inRange 128 2047) 2 ] # 00000yyy yyxxxxxx + [ (int.inRange 2048 65535) 3 ] # zzzzyyyy yyxxxxxx + [ (int.inRange 65536 1114111) 4 ] # 000uuuuu zzzzyyyy yyxxxxxx, + # capped at U+10FFFF + + [ (fun.const true) (builtins.throw invalidCodepointMsg) ] + ]; + + invalidCodepointMsg = "${formatCodepoint cp} is not a Unicode codepoint"; + + # Extract the bit ranges x, y, z and u from the given codepoint + # according to Table 3-6. from The Unicode Standard, Version 13.0, + # section 3.9. u is split into uh and ul since they are used in + # different bytes in the end. + components = lib.mapAttrs + (_: { mask, offset }: + int.bitAnd (int.bitShiftR cp offset) mask + ) + { + x = { + mask = if count > 1 then 63 else 127; + offset = 0; + }; + y = { + mask = if count > 2 then 63 else 31; + offset = 6; + }; + z = { + mask = 15; + offset = 12; + }; + # u which belongs into the second byte + ul = { + mask = 3; + offset = 16; + }; + # u which belongs into the first byte + uh = { + mask = 7; + offset = 18; + }; + }; + inherit (components) x y z ul uh; + + # Finally construct the byte sequence for the given codepoint. This is + # usually done by using the component and adding a few bits as a prefix + # which depends on the length of the sequence. The longer the sequence, + # the further back each component is pushed. To simplify this, we + # always construct a 4 element list and take the last `count` elements. + # Thanks to laziness the bogus values created by this are never evaluated. + # + # Based on table 3-6. from The Unicode Standard, + # Version 13.0, section 3.9. + bytes = lib.sublist (4 - count) count [ + # 11110uuu + (uh + 240) + # 10uuzzzz or 1110zzzz + (z + (if count > 3 then 128 + int.bitShiftL ul 4 else 224)) + # 10yyyyyy or 110yyyyy + (y + (if count > 2 then 128 else 192)) + # 10xxxxxx or 0xxxxxxx + (x + (if count > 1 then 128 else 0)) + ]; + + firstByte = builtins.head bytes; + + unableToEncodeMessage = "Can't encode ${formatCodepoint cp} as UTF-8"; + + in + string.fromBytes ( + builtins.genList + (i: + let + byte = builtins.elemAt bytes i; + in + if wellFormedByte firstByte i byte + then byte + else builtins.throw unableToEncodeMessage + ) + count + ); + + /* Encode a list of Unicode codepoints into an UTF-8 string. + + Type: [ integer ] -> string + */ + encode = lib.concatMapStrings encodeCodepoint; + +in +{ + inherit + encode + decode + step + formatCodepoint + ; +} diff --git a/users/sterni/nix/utf8/tests/default.nix b/users/sterni/nix/utf8/tests/default.nix new file mode 100644 index 000000000000..40783eab2421 --- /dev/null +++ b/users/sterni/nix/utf8/tests/default.nix @@ -0,0 +1,148 @@ +{ depot, pkgs, lib, ... }: + +let + + inherit (pkgs) + runCommandLocal + ; + + inherit (depot.nix.runTestsuite) + runTestsuite + it + assertEq + assertThrows + assertDoesNotThrow + ; + + inherit (depot.nix.writers) + rustSimple + ; + + inherit (depot.users.sterni.nix) + int + utf8 + string + char + ; + + rustDecoder = rustSimple + { + name = "utf8-decode"; + } '' + use std::io::{self, Read}; + fn main() -> std::io::Result<()> { + let mut buffer = String::new(); + io::stdin().read_to_string(&mut buffer)?; + + print!("[ "); + + for c in buffer.chars() { + print!("{} ", u32::from(c)); + } + + print!("]"); + + Ok(()) + } + ''; + + rustDecode = s: + let + expr = runCommandLocal "${s}-decoded" { } '' + printf '%s' ${lib.escapeShellArg s} | ${rustDecoder} > $out + ''; + in + import expr; + + hexDecode = l: + utf8.decode (string.fromBytes (builtins.map int.fromHex l)); + + hexEncode = l: utf8.encode (builtins.map int.fromHex l); + + testFailures = it "checks UTF-8 decoding failures" ([ + (assertThrows "truncated UTF-8 string throws" (hexDecode [ "F0" "9F" ])) + # examples from The Unicode Standard + (assertThrows "ill-formed: C0 AF" (hexDecode [ "C0" "AF" ])) + (assertThrows "ill-formed: E0 9F 80" (hexDecode [ "E0" "9F" "80" ])) + (assertEq "well-formed: F4 80 83 92" (hexDecode [ "F4" "80" "83" "92" ]) [ 1048786 ]) + (assertThrows "Codepoint out of range: 0xFFFFFF" (hexEncode [ "FFFFFF" ])) + (assertThrows "Codepoint out of range: -0x02" (hexEncode [ "-02" ])) + ] ++ builtins.genList + (i: + let + cp = i + int.fromHex "D800"; + in + assertThrows "Can't encode UTF-16 reserved characters: ${utf8.formatCodepoint cp}" + (utf8.encode [ cp ]) + ) + (int.fromHex "07FF")); + + testAscii = it "checks decoding of ascii strings" + (builtins.map + (s: assertEq "ASCII decoding is equal to UTF-8 decoding for \"${s}\"" + (string.toBytes s) + (utf8.decode s)) [ + "foo bar" + "hello\nworld" + "carriage\r\nreturn" + "1238398494829304 []<><>({})[]!!)" + (string.take 127 char.allChars) + ]); + + randomUnicode = [ + "" # empty string should yield empty list + "🥰👨👨👧👦🐈⬛👩🏽🦰" + # https://kermitproject.org/utf8.html + "ᚠᛇᚻ᛫ᛒᛦᚦ᛫ᚠᚱᚩᚠᚢᚱ᛫ᚠᛁᚱᚪ᛫ᚷᛖᚻᚹᛦᛚᚳᚢᛗ" + "An preost wes on leoden, Laȝamon was ihoten" + "Sîne klâwen durh die wolken sint geslagen," + "Τὴ γλῶσσα μοῦ ἔδωσαν ἑλληνικὴ" + "На берегу пустынных волн" + "ვეპხის ტყაოსანი შოთა რუსთაველი" + "யாமறிந்த மொழிகளிலே தமிழ்மொழி போல் இனிதாவது எங்கும் காணோம், " + "ಬಾ ಇಲ್ಲಿ ಸಂಭವಿಸು " + ]; + + # https://kermitproject.org/utf8.html + glassSentences = [ + "Euro Symbol: €." + "Greek: Μπορώ να φάω σπασμένα γυαλιά χωρίς να πάθω τίποτα." + "Íslenska / Icelandic: Ég get etið gler án þess að meiða mig." + "Polish: Mogę jeść szkło, i mi nie szkodzi." + "Romanian: Pot să mănânc sticlă și ea nu mă rănește." + "Ukrainian: Я можу їсти шкло, й воно мені не пошкодить." + "Armenian: Կրնամ ապակի ուտել և ինծի անհանգիստ չըներ։" + "Georgian: მინას ვჭამ და არა მტკივა." + "Hindi: मैं काँच खा सकता हूँ, मुझे उस से कोई पीडा नहीं होती." + "Hebrew(2): אני יכול לאכול זכוכית וזה לא מזיק לי." + "Yiddish(2): איך קען עסן גלאָז און עס טוט מיר נישט װײ." + "Arabic(2): أنا قادر على أكل الزجاج و هذا لا يؤلمني." + "Japanese: 私はガラスを食べられます。それは私を傷つけません。" + "Thai: ฉันกินกระจกได้ แต่มันไม่ทำให้ฉันเจ็บ " + ]; + + testDecoding = it "checks decoding of UTF-8 strings against Rust's String" + (builtins.map + (s: assertEq "Decoding of “${s}” is correct" (utf8.decode s) (rustDecode s)) + (lib.flatten [ + glassSentences + randomUnicode + ])); + + testDecodingEncoding = it "checks that decoding and then encoding forms an identity" + (builtins.map + (s: assertEq "Decoding and then encoding “${s}” yields itself" + (utf8.encode (utf8.decode s)) + s) + (lib.flatten [ + glassSentences + randomUnicode + ])); + +in +runTestsuite "nix.utf8" [ + testFailures + testAscii + testDecoding + testDecodingEncoding +] |