lib/path/default.nix

   1 # Functions for working with paths, see ./path.md
   2 { lib }:
   3 let
   4
   5   inherit (builtins)
   6     isString
   7     isPath
   8     split
   9     match
  10     typeOf
  11     ;
  12
  13   inherit (lib.lists)
  14     length
  15     head
  16     last
  17     genList
  18     elemAt
  19     all
  20     concatMap
  21     foldl'
  22     take
  23     ;
  24
  25   inherit (lib.strings)
  26     concatStringsSep
  27     substring
  28     ;
  29
  30   inherit (lib.asserts)
  31     assertMsg
  32     ;
  33
  34   inherit (lib.path.subpath)
  35     isValid
  36     ;
  37
  38   # Return the reason why a subpath is invalid, or `null` if it's valid
  39   subpathInvalidReason = value:
  40     if ! isString value then
  41       "The given value is of type ${builtins.typeOf value}, but a string was expected"
  42     else if value == "" then
  43       "The given string is empty"
  44     else if substring 0 1 value == "/" then
  45       "The given string \"${value}\" starts with a `/`, representing an absolute path"
  46     # We don't support ".." components, see ./path.md#parent-directory
  47     else if match "(.*/)?\\.\\.(/.*)?" value != null then
  48       "The given string \"${value}\" contains a `..` component, which is not allowed in subpaths"
  49     else null;
  50
  51   # Split and normalise a relative path string into its components.
  52   # Error for ".." components and doesn't include "." components
  53   splitRelPath = path:
  54     let
  55       # Split the string into its parts using regex for efficiency. This regex
  56       # matches patterns like "/", "/./", "/././", with arbitrarily many "/"s
  57       # together. These are the main special cases:
  58       # - Leading "./" gets split into a leading "." part
  59       # - Trailing "/." or "/" get split into a trailing "." or ""
  60       #   part respectively
  61       #
  62       # These are the only cases where "." and "" parts can occur
  63       parts = split "/+(\\./+)*" path;
  64
  65       # `split` creates a list of 2 * k + 1 elements, containing the k +
  66       # 1 parts, interleaved with k matches where k is the number of
  67       # (non-overlapping) matches. This calculation here gets the number of parts
  68       # back from the list length
  69       # floor( (2 * k + 1) / 2 ) + 1 == floor( k + 1/2 ) + 1 == k + 1
  70       partCount = length parts / 2 + 1;
  71
  72       # To assemble the final list of components we want to:
  73       # - Skip a potential leading ".", normalising "./foo" to "foo"
  74       # - Skip a potential trailing "." or "", normalising "foo/" and "foo/." to
  75       #   "foo". See ./path.md#trailing-slashes
  76       skipStart = if head parts == "." then 1 else 0;
  77       skipEnd = if last parts == "." || last parts == "" then 1 else 0;
  78
  79       # We can now know the length of the result by removing the number of
  80       # skipped parts from the total number
  81       componentCount = partCount - skipEnd - skipStart;
  82
  83     in
  84       # Special case of a single "." path component. Such a case leaves a
  85       # componentCount of -1 due to the skipStart/skipEnd not verifying that
  86       # they don't refer to the same character
  87       if path == "." then []
  88
  89       # Generate the result list directly. This is more efficient than a
  90       # combination of `filter`, `init` and `tail`, because here we don't
  91       # allocate any intermediate lists
  92       else genList (index:
  93         # To get to the element we need to add the number of parts we skip and
  94         # multiply by two due to the interleaved layout of `parts`
  95         elemAt parts ((skipStart + index) * 2)
  96       ) componentCount;
  97
  98   # Join relative path components together
  99   joinRelPath = components:
 100     # Always return relative paths with `./` as a prefix (./path.md#leading-dots-for-relative-paths)
 101     "./" +
 102     # An empty string is not a valid relative path, so we need to return a `.` when we have no components
 103     (if components == [] then "." else concatStringsSep "/" components);
 104
 105   # Type: Path -> { root :: Path, components :: [ String ] }
 106   #
 107   # Deconstruct a path value type into:
 108   # - root: The filesystem root of the path, generally `/`
 109   # - components: All the path's components
 110   #
 111   # This is similar to `splitString "/" (toString path)` but safer
 112   # because it can distinguish different filesystem roots
 113   deconstructPath =
 114     let
 115       recurse = components: base:
 116         # If the parent of a path is the path itself, then it's a filesystem root
 117         if base == dirOf base then { root = base; inherit components; }
 118         else recurse ([ (baseNameOf base) ] ++ components) (dirOf base);
 119     in recurse [];
 120
 121 in /* No rec! Add dependencies on this file at the top. */ {
 122
 123   /* Append a subpath string to a path.
 124
 125     Like `path + ("/" + string)` but safer, because it errors instead of returning potentially surprising results.
 126     More specifically, it checks that the first argument is a [path value type](https://nixos.org/manual/nix/stable/language/values.html#type-path"),
 127     and that the second argument is a valid subpath string (see `lib.path.subpath.isValid`).
 128
 129     Laws:
 130
 131     - Not influenced by subpath normalisation
 132
 133         append p s == append p (subpath.normalise s)
 134
 135     Type:
 136       append :: Path -> String -> Path
 137
 138     Example:
 139       append /foo "bar/baz"
 140       => /foo/bar/baz
 141
 142       # subpaths don't need to be normalised
 143       append /foo "./bar//baz/./"
 144       => /foo/bar/baz
 145
 146       # can append to root directory
 147       append /. "foo/bar"
 148       => /foo/bar
 149
 150       # first argument needs to be a path value type
 151       append "/foo" "bar"
 152       => <error>
 153
 154       # second argument needs to be a valid subpath string
 155       append /foo /bar
 156       => <error>
 157       append /foo ""
 158       => <error>
 159       append /foo "/bar"
 160       => <error>
 161       append /foo "../bar"
 162       => <error>
 163   */
 164   append =
 165     # The absolute path to append to
 166     path:
 167     # The subpath string to append
 168     subpath:
 169     assert assertMsg (isPath path) ''
 170       lib.path.append: The first argument is of type ${builtins.typeOf path}, but a path was expected'';
 171     assert assertMsg (isValid subpath) ''
 172       lib.path.append: Second argument is not a valid subpath string:
 173           ${subpathInvalidReason subpath}'';
 174     path + ("/" + subpath);
 175
 176   /*
 177   Whether the first path is a component-wise prefix of the second path.
 178
 179   Laws:
 180
 181   - `hasPrefix p q` is only true if `q == append p s` for some subpath `s`.
 182
 183   - `hasPrefix` is a [non-strict partial order](https://en.wikipedia.org/wiki/Partially_ordered_set#Non-strict_partial_order) over the set of all path values
 184
 185   Type:
 186     hasPrefix :: Path -> Path -> Bool
 187
 188   Example:
 189     hasPrefix /foo /foo/bar
 190     => true
 191     hasPrefix /foo /foo
 192     => true
 193     hasPrefix /foo/bar /foo
 194     => false
 195     hasPrefix /. /foo
 196     => true
 197   */
 198   hasPrefix =
 199     path1:
 200     assert assertMsg
 201       (isPath path1)
 202       "lib.path.hasPrefix: First argument is of type ${typeOf path1}, but a path was expected";
 203     let
 204       path1Deconstructed = deconstructPath path1;
 205     in
 206       path2:
 207       assert assertMsg
 208         (isPath path2)
 209         "lib.path.hasPrefix: Second argument is of type ${typeOf path2}, but a path was expected";
 210       let
 211         path2Deconstructed = deconstructPath path2;
 212       in
 213         assert assertMsg
 214         (path1Deconstructed.root == path2Deconstructed.root) ''
 215           lib.path.hasPrefix: Filesystem roots must be the same for both paths, but paths with different roots were given:
 216               first argument: "${toString path1}" with root "${toString path1Deconstructed.root}"
 217               second argument: "${toString path2}" with root "${toString path2Deconstructed.root}"'';
 218         take (length path1Deconstructed.components) path2Deconstructed.components == path1Deconstructed.components;
 219
 220
 221   /* Whether a value is a valid subpath string.
 222
 223   - The value is a string
 224
 225   - The string is not empty
 226
 227   - The string doesn't start with a `/`
 228
 229   - The string doesn't contain any `..` path components
 230
 231   Type:
 232     subpath.isValid :: String -> Bool
 233
 234   Example:
 235     # Not a string
 236     subpath.isValid null
 237     => false
 238
 239     # Empty string
 240     subpath.isValid ""
 241     => false
 242
 243     # Absolute path
 244     subpath.isValid "/foo"
 245     => false
 246
 247     # Contains a `..` path component
 248     subpath.isValid "../foo"
 249     => false
 250
 251     # Valid subpath
 252     subpath.isValid "foo/bar"
 253     => true
 254
 255     # Doesn't need to be normalised
 256     subpath.isValid "./foo//bar/"
 257     => true
 258   */
 259   subpath.isValid =
 260     # The value to check
 261     value:
 262     subpathInvalidReason value == null;
 263
 264
 265   /* Join subpath strings together using `/`, returning a normalised subpath string.
 266
 267     Like `concatStringsSep "/"` but safer, specifically:
 268
 269     - All elements must be valid subpath strings, see `lib.path.subpath.isValid`
 270
 271     - The result gets normalised, see `lib.path.subpath.normalise`
 272
 273     - The edge case of an empty list gets properly handled by returning the neutral subpath `"./."`
 274
 275     Laws:
 276
 277     - Associativity:
 278
 279           subpath.join [ x (subpath.join [ y z ]) ] == subpath.join [ (subpath.join [ x y ]) z ]
 280
 281     - Identity - `"./."` is the neutral element for normalised paths:
 282
 283           subpath.join [ ] == "./."
 284           subpath.join [ (subpath.normalise p) "./." ] == subpath.normalise p
 285           subpath.join [ "./." (subpath.normalise p) ] == subpath.normalise p
 286
 287     - Normalisation - the result is normalised according to `lib.path.subpath.normalise`:
 288
 289           subpath.join ps == subpath.normalise (subpath.join ps)
 290
 291     - For non-empty lists, the implementation is equivalent to normalising the result of `concatStringsSep "/"`.
 292       Note that the above laws can be derived from this one.
 293
 294           ps != [] -> subpath.join ps == subpath.normalise (concatStringsSep "/" ps)
 295
 296     Type:
 297       subpath.join :: [ String ] -> String
 298
 299     Example:
 300       subpath.join [ "foo" "bar/baz" ]
 301       => "./foo/bar/baz"
 302
 303       # normalise the result
 304       subpath.join [ "./foo" "." "bar//./baz/" ]
 305       => "./foo/bar/baz"
 306
 307       # passing an empty list results in the current directory
 308       subpath.join [ ]
 309       => "./."
 310
 311       # elements must be valid subpath strings
 312       subpath.join [ /foo ]
 313       => <error>
 314       subpath.join [ "" ]
 315       => <error>
 316       subpath.join [ "/foo" ]
 317       => <error>
 318       subpath.join [ "../foo" ]
 319       => <error>
 320   */
 321   subpath.join =
 322     # The list of subpaths to join together
 323     subpaths:
 324     # Fast in case all paths are valid
 325     if all isValid subpaths
 326     then joinRelPath (concatMap splitRelPath subpaths)
 327     else
 328       # Otherwise we take our time to gather more info for a better error message
 329       # Strictly go through each path, throwing on the first invalid one
 330       # Tracks the list index in the fold accumulator
 331       foldl' (i: path:
 332         if isValid path
 333         then i + 1
 334         else throw ''
 335           lib.path.subpath.join: Element at index ${toString i} is not a valid subpath string:
 336               ${subpathInvalidReason path}''
 337       ) 0 subpaths;
 338
 339   /* Normalise a subpath. Throw an error if the subpath isn't valid, see
 340   `lib.path.subpath.isValid`
 341
 342   - Limit repeating `/` to a single one
 343
 344   - Remove redundant `.` components
 345
 346   - Remove trailing `/` and `/.`
 347
 348   - Add leading `./`
 349
 350   Laws:
 351
 352   - Idempotency - normalising multiple times gives the same result:
 353
 354         subpath.normalise (subpath.normalise p) == subpath.normalise p
 355
 356   - Uniqueness - there's only a single normalisation for the paths that lead to the same file system node:
 357
 358         subpath.normalise p != subpath.normalise q -> $(realpath ${p}) != $(realpath ${q})
 359
 360   - Don't change the result when appended to a Nix path value:
 361
 362         base + ("/" + p) == base + ("/" + subpath.normalise p)
 363
 364   - Don't change the path according to `realpath`:
 365
 366         $(realpath ${p}) == $(realpath ${subpath.normalise p})
 367
 368   - Only error on invalid subpaths:
 369
 370         builtins.tryEval (subpath.normalise p)).success == subpath.isValid p
 371
 372   Type:
 373     subpath.normalise :: String -> String
 374
 375   Example:
 376     # limit repeating `/` to a single one
 377     subpath.normalise "foo//bar"
 378     => "./foo/bar"
 379
 380     # remove redundant `.` components
 381     subpath.normalise "foo/./bar"
 382     => "./foo/bar"
 383
 384     # add leading `./`
 385     subpath.normalise "foo/bar"
 386     => "./foo/bar"
 387
 388     # remove trailing `/`
 389     subpath.normalise "foo/bar/"
 390     => "./foo/bar"
 391
 392     # remove trailing `/.`
 393     subpath.normalise "foo/bar/."
 394     => "./foo/bar"
 395
 396     # Return the current directory as `./.`
 397     subpath.normalise "."
 398     => "./."
 399
 400     # error on `..` path components
 401     subpath.normalise "foo/../bar"
 402     => <error>
 403
 404     # error on empty string
 405     subpath.normalise ""
 406     => <error>
 407
 408     # error on absolute path
 409     subpath.normalise "/foo"
 410     => <error>
 411   */
 412   subpath.normalise =
 413     # The subpath string to normalise
 414     subpath:
 415     assert assertMsg (isValid subpath) ''
 416       lib.path.subpath.normalise: Argument is not a valid subpath string:
 417           ${subpathInvalidReason subpath}'';
 418     joinRelPath (splitRelPath subpath);
 419
 420 }