lib/path/default.nix

   1 /* Functions for working with path values. */
   2 # See ./README.md for internal docs
   3 { lib }:
   4 let
   5
   6   inherit (builtins)
   7     isString
   8     isPath
   9     split
  10     match
  11     typeOf
  12     storeDir
  13     ;
  14
  15   inherit (lib.lists)
  16     length
  17     head
  18     last
  19     genList
  20     elemAt
  21     all
  22     concatMap
  23     foldl'
  24     take
  25     drop
  26     ;
  27
  28   listHasPrefix = lib.lists.hasPrefix;
  29
  30   inherit (lib.strings)
  31     concatStringsSep
  32     substring
  33     ;
  34
  35   inherit (lib.asserts)
  36     assertMsg
  37     ;
  38
  39   inherit (lib.path.subpath)
  40     isValid
  41     ;
  42
  43   # Return the reason why a subpath is invalid, or `null` if it's valid
  44   subpathInvalidReason = value:
  45     if ! isString value then
  46       "The given value is of type ${builtins.typeOf value}, but a string was expected"
  47     else if value == "" then
  48       "The given string is empty"
  49     else if substring 0 1 value == "/" then
  50       "The given string \"${value}\" starts with a `/`, representing an absolute path"
  51     # We don't support ".." components, see ./path.md#parent-directory
  52     else if match "(.*/)?\\.\\.(/.*)?" value != null then
  53       "The given string \"${value}\" contains a `..` component, which is not allowed in subpaths"
  54     else null;
  55
  56   # Split and normalise a relative path string into its components.
  57   # Error for ".." components and doesn't include "." components
  58   splitRelPath = path:
  59     let
  60       # Split the string into its parts using regex for efficiency. This regex
  61       # matches patterns like "/", "/./", "/././", with arbitrarily many "/"s
  62       # together. These are the main special cases:
  63       # - Leading "./" gets split into a leading "." part
  64       # - Trailing "/." or "/" get split into a trailing "." or ""
  65       #   part respectively
  66       #
  67       # These are the only cases where "." and "" parts can occur
  68       parts = split "/+(\\./+)*" path;
  69
  70       # `split` creates a list of 2 * k + 1 elements, containing the k +
  71       # 1 parts, interleaved with k matches where k is the number of
  72       # (non-overlapping) matches. This calculation here gets the number of parts
  73       # back from the list length
  74       # floor( (2 * k + 1) / 2 ) + 1 == floor( k + 1/2 ) + 1 == k + 1
  75       partCount = length parts / 2 + 1;
  76
  77       # To assemble the final list of components we want to:
  78       # - Skip a potential leading ".", normalising "./foo" to "foo"
  79       # - Skip a potential trailing "." or "", normalising "foo/" and "foo/." to
  80       #   "foo". See ./path.md#trailing-slashes
  81       skipStart = if head parts == "." then 1 else 0;
  82       skipEnd = if last parts == "." || last parts == "" then 1 else 0;
  83
  84       # We can now know the length of the result by removing the number of
  85       # skipped parts from the total number
  86       componentCount = partCount - skipEnd - skipStart;
  87
  88     in
  89       # Special case of a single "." path component. Such a case leaves a
  90       # componentCount of -1 due to the skipStart/skipEnd not verifying that
  91       # they don't refer to the same character
  92       if path == "." then []
  93
  94       # Generate the result list directly. This is more efficient than a
  95       # combination of `filter`, `init` and `tail`, because here we don't
  96       # allocate any intermediate lists
  97       else genList (index:
  98         # To get to the element we need to add the number of parts we skip and
  99         # multiply by two due to the interleaved layout of `parts`
 100         elemAt parts ((skipStart + index) * 2)
 101       ) componentCount;
 102
 103   # Join relative path components together
 104   joinRelPath = components:
 105     # Always return relative paths with `./` as a prefix (./path.md#leading-dots-for-relative-paths)
 106     "./" +
 107     # An empty string is not a valid relative path, so we need to return a `.` when we have no components
 108     (if components == [] then "." else concatStringsSep "/" components);
 109
 110   # Type: Path -> { root :: Path, components :: [ String ] }
 111   #
 112   # Deconstruct a path value type into:
 113   # - root: The filesystem root of the path, generally `/`
 114   # - components: All the path's components
 115   #
 116   # This is similar to `splitString "/" (toString path)` but safer
 117   # because it can distinguish different filesystem roots
 118   deconstructPath =
 119     let
 120       recurse = components: base:
 121         # If the parent of a path is the path itself, then it's a filesystem root
 122         if base == dirOf base then { root = base; inherit components; }
 123         else recurse ([ (baseNameOf base) ] ++ components) (dirOf base);
 124     in recurse [];
 125
 126   # The components of the store directory, typically [ "nix" "store" ]
 127   storeDirComponents = splitRelPath ("./" + storeDir);
 128   # The number of store directory components, typically 2
 129   storeDirLength = length storeDirComponents;
 130
 131   # Type: [ String ] -> Bool
 132   #
 133   # Whether path components have a store path as a prefix, according to
 134   # https://nixos.org/manual/nix/stable/store/store-path.html#store-path.
 135   componentsHaveStorePathPrefix = components:
 136     # path starts with the store directory (typically /nix/store)
 137     listHasPrefix storeDirComponents components
 138     # is not the store directory itself, meaning there's at least one extra component
 139     && storeDirComponents != components
 140     # and the first component after the store directory has the expected format.
 141     # NOTE: We could change the hash regex to be [0-9a-df-np-sv-z],
 142     # because these are the actual ASCII characters used by Nix's base32 implementation,
 143     # but this is not fully specified, so let's tie this too much to the currently implemented concept of store paths.
 144     # Similar reasoning applies to the validity of the name part.
 145     # We care more about discerning store path-ness on realistic values. Making it airtight would be fragile and slow.
 146     && match ".{32}-.+" (elemAt components storeDirLength) != null;
 147
 148 in /* No rec! Add dependencies on this file at the top. */ {
 149
 150   /*
 151     Append a subpath string to a path.
 152
 153     Like `path + ("/" + string)` but safer, because it errors instead of returning potentially surprising results.
 154     More specifically, it checks that the first argument is a [path value type](https://nixos.org/manual/nix/stable/language/values.html#type-path"),
 155     and that the second argument is a [valid subpath string](#function-library-lib.path.subpath.isValid).
 156
 157     Laws:
 158
 159     - Not influenced by subpath [normalisation](#function-library-lib.path.subpath.normalise):
 160
 161           append p s == append p (subpath.normalise s)
 162
 163     Type:
 164       append :: Path -> String -> Path
 165
 166     Example:
 167       append /foo "bar/baz"
 168       => /foo/bar/baz
 169
 170       # subpaths don't need to be normalised
 171       append /foo "./bar//baz/./"
 172       => /foo/bar/baz
 173
 174       # can append to root directory
 175       append /. "foo/bar"
 176       => /foo/bar
 177
 178       # first argument needs to be a path value type
 179       append "/foo" "bar"
 180       => <error>
 181
 182       # second argument needs to be a valid subpath string
 183       append /foo /bar
 184       => <error>
 185       append /foo ""
 186       => <error>
 187       append /foo "/bar"
 188       => <error>
 189       append /foo "../bar"
 190       => <error>
 191   */
 192   append =
 193     # The absolute path to append to
 194     path:
 195     # The subpath string to append
 196     subpath:
 197     assert assertMsg (isPath path) ''
 198       lib.path.append: The first argument is of type ${builtins.typeOf path}, but a path was expected'';
 199     assert assertMsg (isValid subpath) ''
 200       lib.path.append: Second argument is not a valid subpath string:
 201           ${subpathInvalidReason subpath}'';
 202     path + ("/" + subpath);
 203
 204   /*
 205     Whether the first path is a component-wise prefix of the second path.
 206
 207     Laws:
 208
 209     - `hasPrefix p q` is only true if [`q == append p s`](#function-library-lib.path.append) for some [subpath](#function-library-lib.path.subpath.isValid) `s`.
 210
 211     - `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.
 212
 213     Type:
 214       hasPrefix :: Path -> Path -> Bool
 215
 216     Example:
 217       hasPrefix /foo /foo/bar
 218       => true
 219       hasPrefix /foo /foo
 220       => true
 221       hasPrefix /foo/bar /foo
 222       => false
 223       hasPrefix /. /foo
 224       => true
 225   */
 226   hasPrefix =
 227     path1:
 228     assert assertMsg
 229       (isPath path1)
 230       "lib.path.hasPrefix: First argument is of type ${typeOf path1}, but a path was expected";
 231     let
 232       path1Deconstructed = deconstructPath path1;
 233     in
 234       path2:
 235       assert assertMsg
 236         (isPath path2)
 237         "lib.path.hasPrefix: Second argument is of type ${typeOf path2}, but a path was expected";
 238       let
 239         path2Deconstructed = deconstructPath path2;
 240       in
 241         assert assertMsg
 242         (path1Deconstructed.root == path2Deconstructed.root) ''
 243           lib.path.hasPrefix: Filesystem roots must be the same for both paths, but paths with different roots were given:
 244               first argument: "${toString path1}" with root "${toString path1Deconstructed.root}"
 245               second argument: "${toString path2}" with root "${toString path2Deconstructed.root}"'';
 246         take (length path1Deconstructed.components) path2Deconstructed.components == path1Deconstructed.components;
 247
 248   /*
 249     Remove the first path as a component-wise prefix from the second path.
 250     The result is a [normalised subpath string](#function-library-lib.path.subpath.normalise).
 251
 252     Laws:
 253
 254     - Inverts [`append`](#function-library-lib.path.append) for [normalised subpath string](#function-library-lib.path.subpath.normalise):
 255
 256           removePrefix p (append p s) == subpath.normalise s
 257
 258     Type:
 259       removePrefix :: Path -> Path -> String
 260
 261     Example:
 262       removePrefix /foo /foo/bar/baz
 263       => "./bar/baz"
 264       removePrefix /foo /foo
 265       => "./."
 266       removePrefix /foo/bar /foo
 267       => <error>
 268       removePrefix /. /foo
 269       => "./foo"
 270   */
 271   removePrefix =
 272     path1:
 273     assert assertMsg
 274       (isPath path1)
 275       "lib.path.removePrefix: First argument is of type ${typeOf path1}, but a path was expected.";
 276     let
 277       path1Deconstructed = deconstructPath path1;
 278       path1Length = length path1Deconstructed.components;
 279     in
 280       path2:
 281       assert assertMsg
 282         (isPath path2)
 283         "lib.path.removePrefix: Second argument is of type ${typeOf path2}, but a path was expected.";
 284       let
 285         path2Deconstructed = deconstructPath path2;
 286         success = take path1Length path2Deconstructed.components == path1Deconstructed.components;
 287         components =
 288           if success then
 289             drop path1Length path2Deconstructed.components
 290           else
 291             throw ''
 292               lib.path.removePrefix: The first path argument "${toString path1}" is not a component-wise prefix of the second path argument "${toString path2}".'';
 293       in
 294         assert assertMsg
 295         (path1Deconstructed.root == path2Deconstructed.root) ''
 296           lib.path.removePrefix: Filesystem roots must be the same for both paths, but paths with different roots were given:
 297               first argument: "${toString path1}" with root "${toString path1Deconstructed.root}"
 298               second argument: "${toString path2}" with root "${toString path2Deconstructed.root}"'';
 299         joinRelPath components;
 300
 301   /*
 302     Split the filesystem root from a [path](https://nixos.org/manual/nix/stable/language/values.html#type-path).
 303     The result is an attribute set with these attributes:
 304     - `root`: The filesystem root of the path, meaning that this directory has no parent directory.
 305     - `subpath`: The [normalised subpath string](#function-library-lib.path.subpath.normalise) that when [appended](#function-library-lib.path.append) to `root` returns the original path.
 306
 307     Laws:
 308     - [Appending](#function-library-lib.path.append) the `root` and `subpath` gives the original path:
 309
 310           p ==
 311             append
 312               (splitRoot p).root
 313               (splitRoot p).subpath
 314
 315     - Trying to get the parent directory of `root` using [`readDir`](https://nixos.org/manual/nix/stable/language/builtins.html#builtins-readDir) returns `root` itself:
 316
 317           dirOf (splitRoot p).root == (splitRoot p).root
 318
 319     Type:
 320       splitRoot :: Path -> { root :: Path, subpath :: String }
 321
 322     Example:
 323       splitRoot /foo/bar
 324       => { root = /.; subpath = "./foo/bar"; }
 325
 326       splitRoot /.
 327       => { root = /.; subpath = "./."; }
 328
 329       # Nix neutralises `..` path components for all path values automatically
 330       splitRoot /foo/../bar
 331       => { root = /.; subpath = "./bar"; }
 332
 333       splitRoot "/foo/bar"
 334       => <error>
 335   */
 336   splitRoot =
 337     # The path to split the root off of
 338     path:
 339     assert assertMsg
 340       (isPath path)
 341       "lib.path.splitRoot: Argument is of type ${typeOf path}, but a path was expected";
 342     let
 343       deconstructed = deconstructPath path;
 344     in {
 345       root = deconstructed.root;
 346       subpath = joinRelPath deconstructed.components;
 347     };
 348
 349   /*
 350     Whether a [path](https://nixos.org/manual/nix/stable/language/values.html#type-path)
 351     has a [store path](https://nixos.org/manual/nix/stable/store/store-path.html#store-path)
 352     as a prefix.
 353
 354     :::{.note}
 355     As with all functions of this `lib.path` library, it does not work on paths in strings,
 356     which is how you'd typically get store paths.
 357
 358     Instead, this function only handles path values themselves,
 359     which occur when Nix files in the store use relative path expressions.
 360     :::
 361
 362     Type:
 363       hasStorePathPrefix :: Path -> Bool
 364
 365     Example:
 366       # Subpaths of derivation outputs have a store path as a prefix
 367       hasStorePathPrefix /nix/store/nvl9ic0pj1fpyln3zaqrf4cclbqdfn1j-foo/bar/baz
 368       => true
 369
 370       # The store directory itself is not a store path
 371       hasStorePathPrefix /nix/store
 372       => false
 373
 374       # Derivation outputs are store paths themselves
 375       hasStorePathPrefix /nix/store/nvl9ic0pj1fpyln3zaqrf4cclbqdfn1j-foo
 376       => true
 377
 378       # Paths outside the Nix store don't have a store path prefix
 379       hasStorePathPrefix /home/user
 380       => false
 381
 382       # Not all paths under the Nix store are store paths
 383       hasStorePathPrefix /nix/store/.links/10gg8k3rmbw8p7gszarbk7qyd9jwxhcfq9i6s5i0qikx8alkk4hq
 384       => false
 385
 386       # Store derivations are also store paths themselves
 387       hasStorePathPrefix /nix/store/nvl9ic0pj1fpyln3zaqrf4cclbqdfn1j-foo.drv
 388       => true
 389   */
 390   hasStorePathPrefix = path:
 391     let
 392       deconstructed = deconstructPath path;
 393     in
 394     assert assertMsg
 395       (isPath path)
 396       "lib.path.hasStorePathPrefix: Argument is of type ${typeOf path}, but a path was expected";
 397     assert assertMsg
 398       # This function likely breaks or needs adjustment if used with other filesystem roots, if they ever get implemented.
 399       # Let's try to error nicely in such a case, though it's unclear how an implementation would work even and whether this could be detected.
 400       # See also https://github.com/NixOS/nix/pull/6530#discussion_r1422843117
 401       (deconstructed.root == /. && toString deconstructed.root == "/")
 402       "lib.path.hasStorePathPrefix: Argument has a filesystem root (${toString deconstructed.root}) that's not /, which is currently not supported.";
 403     componentsHaveStorePathPrefix deconstructed.components;
 404
 405   /*
 406     Whether a value is a valid subpath string.
 407
 408     A subpath string points to a specific file or directory within an absolute base directory.
 409     It is a stricter form of a relative path that excludes `..` components, since those could escape the base directory.
 410
 411     - The value is a string.
 412
 413     - The string is not empty.
 414
 415     - The string doesn't start with a `/`.
 416
 417     - The string doesn't contain any `..` path components.
 418
 419     Type:
 420       subpath.isValid :: String -> Bool
 421
 422     Example:
 423       # Not a string
 424       subpath.isValid null
 425       => false
 426
 427       # Empty string
 428       subpath.isValid ""
 429       => false
 430
 431       # Absolute path
 432       subpath.isValid "/foo"
 433       => false
 434
 435       # Contains a `..` path component
 436       subpath.isValid "../foo"
 437       => false
 438
 439       # Valid subpath
 440       subpath.isValid "foo/bar"
 441       => true
 442
 443       # Doesn't need to be normalised
 444       subpath.isValid "./foo//bar/"
 445       => true
 446   */
 447   subpath.isValid =
 448     # The value to check
 449     value:
 450     subpathInvalidReason value == null;
 451
 452
 453   /*
 454     Join subpath strings together using `/`, returning a normalised subpath string.
 455
 456     Like `concatStringsSep "/"` but safer, specifically:
 457
 458     - All elements must be [valid subpath strings](#function-library-lib.path.subpath.isValid).
 459
 460     - The result gets [normalised](#function-library-lib.path.subpath.normalise).
 461
 462     - The edge case of an empty list gets properly handled by returning the neutral subpath `"./."`.
 463
 464     Laws:
 465
 466     - Associativity:
 467
 468           subpath.join [ x (subpath.join [ y z ]) ] == subpath.join [ (subpath.join [ x y ]) z ]
 469
 470     - Identity - `"./."` is the neutral element for normalised paths:
 471
 472           subpath.join [ ] == "./."
 473           subpath.join [ (subpath.normalise p) "./." ] == subpath.normalise p
 474           subpath.join [ "./." (subpath.normalise p) ] == subpath.normalise p
 475
 476     - Normalisation - the result is [normalised](#function-library-lib.path.subpath.normalise):
 477
 478           subpath.join ps == subpath.normalise (subpath.join ps)
 479
 480     - For non-empty lists, the implementation is equivalent to [normalising](#function-library-lib.path.subpath.normalise) the result of `concatStringsSep "/"`.
 481       Note that the above laws can be derived from this one:
 482
 483           ps != [] -> subpath.join ps == subpath.normalise (concatStringsSep "/" ps)
 484
 485     Type:
 486       subpath.join :: [ String ] -> String
 487
 488     Example:
 489       subpath.join [ "foo" "bar/baz" ]
 490       => "./foo/bar/baz"
 491
 492       # normalise the result
 493       subpath.join [ "./foo" "." "bar//./baz/" ]
 494       => "./foo/bar/baz"
 495
 496       # passing an empty list results in the current directory
 497       subpath.join [ ]
 498       => "./."
 499
 500       # elements must be valid subpath strings
 501       subpath.join [ /foo ]
 502       => <error>
 503       subpath.join [ "" ]
 504       => <error>
 505       subpath.join [ "/foo" ]
 506       => <error>
 507       subpath.join [ "../foo" ]
 508       => <error>
 509   */
 510   subpath.join =
 511     # The list of subpaths to join together
 512     subpaths:
 513     # Fast in case all paths are valid
 514     if all isValid subpaths
 515     then joinRelPath (concatMap splitRelPath subpaths)
 516     else
 517       # Otherwise we take our time to gather more info for a better error message
 518       # Strictly go through each path, throwing on the first invalid one
 519       # Tracks the list index in the fold accumulator
 520       foldl' (i: path:
 521         if isValid path
 522         then i + 1
 523         else throw ''
 524           lib.path.subpath.join: Element at index ${toString i} is not a valid subpath string:
 525               ${subpathInvalidReason path}''
 526       ) 0 subpaths;
 527
 528   /*
 529     Split [a subpath](#function-library-lib.path.subpath.isValid) into its path component strings.
 530     Throw an error if the subpath isn't valid.
 531     Note that the returned path components are also [valid subpath strings](#function-library-lib.path.subpath.isValid), though they are intentionally not [normalised](#function-library-lib.path.subpath.normalise).
 532
 533     Laws:
 534
 535     - Splitting a subpath into components and [joining](#function-library-lib.path.subpath.join) the components gives the same subpath but [normalised](#function-library-lib.path.subpath.normalise):
 536
 537           subpath.join (subpath.components s) == subpath.normalise s
 538
 539     Type:
 540       subpath.components :: String -> [ String ]
 541
 542     Example:
 543       subpath.components "."
 544       => [ ]
 545
 546       subpath.components "./foo//bar/./baz/"
 547       => [ "foo" "bar" "baz" ]
 548
 549       subpath.components "/foo"
 550       => <error>
 551   */
 552   subpath.components =
 553     # The subpath string to split into components
 554     subpath:
 555     assert assertMsg (isValid subpath) ''
 556       lib.path.subpath.components: Argument is not a valid subpath string:
 557           ${subpathInvalidReason subpath}'';
 558     splitRelPath subpath;
 559
 560   /*
 561     Normalise a subpath. Throw an error if the subpath isn't [valid](#function-library-lib.path.subpath.isValid).
 562
 563     - Limit repeating `/` to a single one.
 564
 565     - Remove redundant `.` components.
 566
 567     - Remove trailing `/` and `/.`.
 568
 569     - Add leading `./`.
 570
 571     Laws:
 572
 573     - Idempotency - normalising multiple times gives the same result:
 574
 575           subpath.normalise (subpath.normalise p) == subpath.normalise p
 576
 577     - Uniqueness - there's only a single normalisation for the paths that lead to the same file system node:
 578
 579           subpath.normalise p != subpath.normalise q -> $(realpath ${p}) != $(realpath ${q})
 580
 581     - Don't change the result when [appended](#function-library-lib.path.append) to a Nix path value:
 582
 583           append base p == append base (subpath.normalise p)
 584
 585     - Don't change the path according to `realpath`:
 586
 587           $(realpath ${p}) == $(realpath ${subpath.normalise p})
 588
 589     - Only error on [invalid subpaths](#function-library-lib.path.subpath.isValid):
 590
 591           builtins.tryEval (subpath.normalise p)).success == subpath.isValid p
 592
 593     Type:
 594       subpath.normalise :: String -> String
 595
 596     Example:
 597       # limit repeating `/` to a single one
 598       subpath.normalise "foo//bar"
 599       => "./foo/bar"
 600
 601       # remove redundant `.` components
 602       subpath.normalise "foo/./bar"
 603       => "./foo/bar"
 604
 605       # add leading `./`
 606       subpath.normalise "foo/bar"
 607       => "./foo/bar"
 608
 609       # remove trailing `/`
 610       subpath.normalise "foo/bar/"
 611       => "./foo/bar"
 612
 613       # remove trailing `/.`
 614       subpath.normalise "foo/bar/."
 615       => "./foo/bar"
 616
 617       # Return the current directory as `./.`
 618       subpath.normalise "."
 619       => "./."
 620
 621       # error on `..` path components
 622       subpath.normalise "foo/../bar"
 623       => <error>
 624
 625       # error on empty string
 626       subpath.normalise ""
 627       => <error>
 628
 629       # error on absolute path
 630       subpath.normalise "/foo"
 631       => <error>
 632   */
 633   subpath.normalise =
 634     # The subpath string to normalise
 635     subpath:
 636     assert assertMsg (isValid subpath) ''
 637       lib.path.subpath.normalise: Argument is not a valid subpath string:
 638           ${subpathInvalidReason subpath}'';
 639     joinRelPath (splitRelPath subpath);
 640
 641 }