pyrox.dev
1{
2 lib ? import ../.,
3}:
4let
5
6 inherit (builtins)
7 isAttrs
8 isPath
9 isString
10 nixVersion
11 pathExists
12 readDir
13 split
14 trace
15 typeOf
16 fetchGit
17 ;
18
19 inherit (lib.attrsets)
20 attrNames
21 attrValues
22 mapAttrs
23 mapAttrsToList
24 optionalAttrs
25 zipAttrsWith
26 ;
27
28 inherit (lib.filesystem)
29 pathType
30 ;
31
32 inherit (lib.lists)
33 all
34 commonPrefix
35 concatLists
36 elemAt
37 filter
38 findFirst
39 findFirstIndex
40 foldl'
41 head
42 length
43 sublist
44 tail
45 ;
46
47 inherit (lib.path)
48 append
49 splitRoot
50 hasStorePathPrefix
51 splitStorePath
52 ;
53
54 inherit (lib.path.subpath)
55 components
56 join
57 ;
58
59 inherit (lib.strings)
60 isStringLike
61 concatStringsSep
62 substring
63 stringLength
64 hasSuffix
65 versionAtLeast
66 ;
67
68 inherit (lib.trivial)
69 inPureEvalMode
70 ;
71in
72# Rare case of justified usage of rec:
73# - This file is internal, so the return value doesn't matter, no need to make things overridable
74# - The functions depend on each other
75# - We want to expose all of these functions for easy testing
76rec {
77
78 # If you change the internal representation, make sure to:
79 # - Increment this version
80 # - Add an additional migration function below
81 # - Update the description of the internal representation in ./README.md
82 _currentVersion = 3;
83
84 # Migrations between versions. The 0th element converts from v0 to v1, and so on
85 migrations = [
86 # Convert v0 into v1: Add the _internalBase{Root,Components} attributes
87 (
88 filesetV0:
89 let
90 parts = splitRoot filesetV0._internalBase;
91 in
92 filesetV0
93 // {
94 _internalVersion = 1;
95 _internalBaseRoot = parts.root;
96 _internalBaseComponents = components parts.subpath;
97 }
98 )
99
100 # Convert v1 into v2: filesetTree's can now also omit attributes to signal paths not being included
101 (
102 filesetV1:
103 # This change is backwards compatible (but not forwards compatible, so we still need a new version)
104 filesetV1
105 // {
106 _internalVersion = 2;
107 }
108 )
109
110 # Convert v2 into v3: filesetTree's now have a representation for an empty file set without a base path
111 (
112 filesetV2:
113 filesetV2
114 // {
115 # All v1 file sets are not the new empty file set
116 _internalIsEmptyWithoutBase = false;
117 _internalVersion = 3;
118 }
119 )
120 ];
121
122 _noEvalMessage = ''
123 lib.fileset: Directly evaluating a file set is not supported.
124 To turn it into a usable source, use `lib.fileset.toSource`.
125 To pretty-print the contents, use `lib.fileset.trace` or `lib.fileset.traceVal`.'';
126
127 # The empty file set without a base path
128 _emptyWithoutBase = {
129 _type = "fileset";
130
131 _internalVersion = _currentVersion;
132
133 # The one and only!
134 _internalIsEmptyWithoutBase = true;
135
136 # Due to alphabetical ordering, this is evaluated last,
137 # which makes the nix repl output nicer than if it would be ordered first.
138 # It also allows evaluating it strictly up to this error, which could be useful
139 _noEval = throw _noEvalMessage;
140 };
141
142 # Create a fileset, see ./README.md#fileset
143 # Type: path -> filesetTree -> fileset
144 _create =
145 base: tree:
146 let
147 # Decompose the base into its components
148 # See ../path/README.md for why we're not just using `toString`
149 parts = splitRoot base;
150 in
151 {
152 _type = "fileset";
153
154 _internalVersion = _currentVersion;
155
156 _internalIsEmptyWithoutBase = false;
157 _internalBase = base;
158 _internalBaseRoot = parts.root;
159 _internalBaseComponents = components parts.subpath;
160 _internalTree = tree;
161
162 # Due to alphabetical ordering, this is evaluated last,
163 # which makes the nix repl output nicer than if it would be ordered first.
164 # It also allows evaluating it strictly up to this error, which could be useful
165 _noEval = throw _noEvalMessage;
166 };
167
168 # Coerce a value to a fileset, erroring when the value cannot be coerced.
169 # The string gives the context for error messages.
170 # Type: String -> (fileset | Path) -> fileset
171 _coerce =
172 context: value:
173 if value._type or "" == "fileset" then
174 if value._internalVersion > _currentVersion then
175 throw ''
176 ${context} is a file set created from a future version of the file set library with a different internal representation:
177 - Internal version of the file set: ${toString value._internalVersion}
178 - Internal version of the library: ${toString _currentVersion}
179 Make sure to update your Nixpkgs to have a newer version of `lib.fileset`.''
180 else if value._internalVersion < _currentVersion then
181 let
182 # Get all the migration functions necessary to convert from the old to the current version
183 migrationsToApply = sublist value._internalVersion (
184 _currentVersion - value._internalVersion
185 ) migrations;
186 in
187 foldl' (value: migration: migration value) value migrationsToApply
188 else
189 value
190 else if !isPath value then
191 if value ? _isLibCleanSourceWith then
192 throw ''
193 ${context} is a `lib.sources`-based value, but it should be a file set or a path instead.
194 To convert a `lib.sources`-based value to a file set you can use `lib.fileset.fromSource`.
195 Note that this only works for sources created from paths.''
196 else if isStringLike value then
197 throw ''
198 ${context} ("${toString value}") is a string-like value, but it should be a file set or a path instead.
199 Paths represented as strings are not supported by `lib.fileset`, use `lib.sources` or derivations instead.''
200 else
201 throw ''${context} is of type ${typeOf value}, but it should be a file set or a path instead.''
202 else if !pathExists value then
203 throw ''
204 ${context} (${toString value}) is a path that does not exist.
205 To create a file set from a path that may not exist, use `lib.fileset.maybeMissing`.''
206 else
207 _singleton value;
208
209 # Coerce many values to filesets, erroring when any value cannot be coerced,
210 # or if the filesystem root of the values doesn't match.
211 # Type: String -> [ { context :: String, value :: fileset | Path } ] -> [ fileset ]
212 _coerceMany =
213 functionContext: list:
214 let
215 filesets = map ({ context, value }: _coerce "${functionContext}: ${context}" value) list;
216
217 # Find the first value with a base, there may be none!
218 firstWithBase = findFirst (fileset: !fileset._internalIsEmptyWithoutBase) null filesets;
219 # This value is only accessed if first != null
220 firstBaseRoot = firstWithBase._internalBaseRoot;
221
222 # Finds the first element with a filesystem root different than the first element, if any
223 differentIndex = findFirstIndex (
224 fileset:
225 # The empty value without a base doesn't have a base path
226 !fileset._internalIsEmptyWithoutBase && firstBaseRoot != fileset._internalBaseRoot
227 ) null filesets;
228 in
229 # Only evaluates `differentIndex` if there are any elements with a base
230 if firstWithBase != null && differentIndex != null then
231 throw ''
232 ${functionContext}: Filesystem roots are not the same:
233 ${(head list).context}: Filesystem root is "${toString firstBaseRoot}"
234 ${(elemAt list differentIndex).context}: Filesystem root is "${toString (elemAt filesets differentIndex)._internalBaseRoot}"
235 Different filesystem roots are not supported.''
236 else
237 filesets;
238
239 # Create a file set from a path.
240 # Type: Path -> fileset
241 _singleton =
242 path:
243 let
244 type = pathType path;
245 in
246 if type == "directory" then
247 _create path type
248 else
249 # This turns a file path ./default.nix into a fileset with
250 # - _internalBase: ./.
251 # - _internalTree: {
252 # "default.nix" = <type>;
253 # }
254 # See ./README.md#single-files
255 _create (dirOf path) {
256 ${baseNameOf path} = type;
257 };
258
259 # Expand a directory representation to an equivalent one in attribute set form.
260 # All directory entries are included in the result.
261 # Type: Path -> filesetTree -> { <name> = filesetTree; }
262 _directoryEntries =
263 path: value:
264 if value == "directory" then
265 readDir path
266 else
267 # Set all entries not present to null
268 mapAttrs (name: value: null) (readDir path) // value;
269
270 /**
271 A normalisation of a filesetTree suitable filtering with `builtins.path`:
272 - Replace all directories that have no files with `null`.
273 This removes directories that would be empty
274 - Replace all directories with all files with `"directory"`.
275 This speeds up the source filter function
276
277 Note that this function is strict, it evaluates the entire tree
278
279 # Inputs
280
281 `path`
282
283 : 1\. Function argument
284
285 `tree`
286
287 : 2\. Function argument
288
289 # Type
290
291 ```
292 Path -> filesetTree -> filesetTree
293 ```
294 */
295 _normaliseTreeFilter =
296 path: tree:
297 if tree == "directory" || isAttrs tree then
298 let
299 entries = _directoryEntries path tree;
300 normalisedSubtrees = mapAttrs (name: _normaliseTreeFilter (path + "/${name}")) entries;
301 subtreeValues = attrValues normalisedSubtrees;
302 in
303 # This triggers either when all files in a directory are filtered out
304 # Or when the directory doesn't contain any files at all
305 if all isNull subtreeValues then
306 null
307 # Triggers when we have the same as a `readDir path`, so we can turn it back into an equivalent "directory".
308 else if all isString subtreeValues then
309 "directory"
310 else
311 normalisedSubtrees
312 else
313 tree;
314
315 /**
316 A minimal normalisation of a filesetTree, intended for pretty-printing:
317 - If all children of a path are recursively included or empty directories, the path itself is also recursively included
318 - If all children of a path are fully excluded or empty directories, the path itself is an empty directory
319 - Other empty directories are represented with the special "emptyDir" string
320 While these could be replaced with `null`, that would take another mapAttrs
321
322 Note that this function is partially lazy.
323
324 # Inputs
325
326 `path`
327
328 : 1\. Function argument
329
330 `tree`
331
332 : 2\. Function argument
333
334 # Type
335
336 ```
337 Path -> filesetTree -> filesetTree (with "emptyDir"'s)
338 ```
339 */
340 _normaliseTreeMinimal =
341 path: tree:
342 if tree == "directory" || isAttrs tree then
343 let
344 entries = _directoryEntries path tree;
345 normalisedSubtrees = mapAttrs (name: _normaliseTreeMinimal (path + "/${name}")) entries;
346 subtreeValues = attrValues normalisedSubtrees;
347 in
348 # If there are no entries, or all entries are empty directories, return "emptyDir".
349 # After this branch we know that there's at least one file
350 if all (value: value == "emptyDir") subtreeValues then
351 "emptyDir"
352
353 # If all subtrees are fully included or empty directories
354 # (both of which are coincidentally represented as strings), return "directory".
355 # This takes advantage of the fact that empty directories can be represented as included directories.
356 # Note that the tree == "directory" check allows avoiding recursion
357 else if tree == "directory" || all (value: isString value) subtreeValues then
358 "directory"
359
360 # If all subtrees are fully excluded or empty directories, return null.
361 # This takes advantage of the fact that empty directories can be represented as excluded directories
362 else if all (value: isNull value || value == "emptyDir") subtreeValues then
363 null
364
365 # Mix of included and excluded entries
366 else
367 normalisedSubtrees
368 else
369 tree;
370
371 # Trace a filesetTree in a pretty way when the resulting value is evaluated.
372 # This can handle both normal filesetTree's, and ones returned from _normaliseTreeMinimal
373 # Type: Path -> filesetTree (with "emptyDir"'s) -> Null
374 _printMinimalTree =
375 base: tree:
376 let
377 treeSuffix =
378 tree:
379 if isAttrs tree then
380 ""
381 else if tree == "directory" then
382 " (all files in directory)"
383 else
384 # This does "leak" the file type strings of the internal representation,
385 # but this is the main reason these file type strings even are in the representation!
386 # TODO: Consider removing that information from the internal representation for performance.
387 # The file types can still be printed by querying them only during tracing
388 " (${tree})";
389
390 # Only for attribute set trees
391 traceTreeAttrs =
392 prevLine: indent: tree:
393 foldl' (
394 prevLine: name:
395 let
396 subtree = tree.${name};
397
398 # Evaluating this prints the line for this subtree
399 thisLine = trace "${indent}- ${name}${treeSuffix subtree}" prevLine;
400 in
401 if subtree == null || subtree == "emptyDir" then
402 # Don't print anything at all if this subtree is empty
403 prevLine
404 else if isAttrs subtree then
405 # A directory with explicit entries
406 # Do print this node, but also recurse
407 traceTreeAttrs thisLine "${indent} " subtree
408 else
409 # Either a file, or a recursively included directory
410 # Do print this node but no further recursion needed
411 thisLine
412 ) prevLine (attrNames tree);
413
414 # Evaluating this will print the first line
415 firstLine =
416 if tree == null || tree == "emptyDir" then
417 trace "(empty)" null
418 else
419 trace "${toString base}${treeSuffix tree}" null;
420 in
421 if isAttrs tree then traceTreeAttrs firstLine "" tree else firstLine;
422
423 # Pretty-print a file set in a pretty way when the resulting value is evaluated
424 # Type: fileset -> Null
425 _printFileset =
426 fileset:
427 if fileset._internalIsEmptyWithoutBase then
428 trace "(empty)" null
429 else
430 _printMinimalTree fileset._internalBase (
431 _normaliseTreeMinimal fileset._internalBase fileset._internalTree
432 );
433
434 # Turn a fileset into a source filter function suitable for `builtins.path`
435 # Only directories recursively containing at least one files are recursed into
436 # Type: fileset -> (String -> String -> Bool)
437 _toSourceFilter =
438 fileset:
439 let
440 # Simplify the tree, necessary to make sure all empty directories are null
441 # which has the effect that they aren't included in the result
442 tree = _normaliseTreeFilter fileset._internalBase fileset._internalTree;
443
444 # The base path as a string with a single trailing slash
445 baseString =
446 if fileset._internalBaseComponents == [ ] then
447 # Need to handle the filesystem root specially
448 "/"
449 else
450 "/" + concatStringsSep "/" fileset._internalBaseComponents + "/";
451
452 baseLength = stringLength baseString;
453
454 # Check whether a list of path components under the base path exists in the tree.
455 # This function is called often, so it should be fast.
456 # Type: [ String ] -> Bool
457 inTree =
458 components:
459 let
460 recurse =
461 index: localTree:
462 if isAttrs localTree then
463 # We have an attribute set, meaning this is a directory with at least one file
464 if index >= length components then
465 # The path may have no more components though, meaning the filter is running on the directory itself,
466 # so we always include it, again because there's at least one file in it.
467 true
468 else
469 # If we do have more components, the filter runs on some entry inside this directory, so we need to recurse
470 # We do +2 because builtins.split is an interleaved list of the inbetweens and the matches
471 recurse (index + 2) localTree.${elemAt components index}
472 else
473 # If it's not an attribute set it can only be either null (in which case it's not included)
474 # or a string ("directory" or "regular", etc.) in which case it's included
475 localTree != null;
476 in
477 recurse 0 tree;
478
479 # Filter suited when there's no files
480 empty = _: _: false;
481
482 # Filter suited when there's some files
483 # This can't be used for when there's no files, because the base directory is always included
484 nonEmpty =
485 path: type:
486 let
487 # Add a slash to the path string, turning "/foo" to "/foo/",
488 # making sure to not have any false prefix matches below.
489 # Note that this would produce "//" for "/",
490 # but builtins.path doesn't call the filter function on the `path` argument itself,
491 # meaning this function can never receive "/" as an argument
492 pathSlash = path + "/";
493 in
494 (
495 # Same as `hasPrefix pathSlash baseString`, but more efficient.
496 # With base /foo/bar we need to include /foo:
497 # hasPrefix "/foo/" "/foo/bar/"
498 if substring 0 (stringLength pathSlash) baseString == pathSlash then
499 true
500 # Same as `! hasPrefix baseString pathSlash`, but more efficient.
501 # With base /foo/bar we need to exclude /baz
502 # ! hasPrefix "/baz/" "/foo/bar/"
503 else if substring 0 baseLength pathSlash != baseString then
504 false
505 else
506 # Same as `removePrefix baseString path`, but more efficient.
507 # From the above code we know that hasPrefix baseString pathSlash holds, so this is safe.
508 # We don't use pathSlash here because we only needed the trailing slash for the prefix matching.
509 # With base /foo and path /foo/bar/baz this gives
510 # inTree (split "/" (removePrefix "/foo/" "/foo/bar/baz"))
511 # == inTree (split "/" "bar/baz")
512 # == inTree [ "bar" "baz" ]
513 inTree (split "/" (substring baseLength (-1) path))
514 )
515 # This is a way have an additional check in case the above is true without any significant performance cost
516 && (
517 # This relies on the fact that Nix only distinguishes path types "directory", "regular", "symlink" and "unknown",
518 # so everything except "unknown" is allowed, seems reasonable to rely on that
519 type != "unknown"
520 || throw ''
521 lib.fileset.toSource: `fileset` contains a file that cannot be added to the store: ${path}
522 This file is neither a regular file nor a symlink, the only file types supported by the Nix store.
523 Therefore the file set cannot be added to the Nix store as is. Make sure to not include that file to avoid this error.''
524 );
525 in
526 # Special case because the code below assumes that the _internalBase is always included in the result
527 # which shouldn't be done when we have no files at all in the base
528 # This also forces the tree before returning the filter, leads to earlier error messages
529 if fileset._internalIsEmptyWithoutBase || tree == null then empty else nonEmpty;
530
531 # Turn a builtins.filterSource-based source filter on a root path into a file set
532 # containing only files included by the filter.
533 # The filter is lazily called as necessary to determine whether paths are included
534 # Type: Path -> (String -> String -> Bool) -> fileset
535 _fromSourceFilter =
536 root: sourceFilter:
537 let
538 # During the recursion we need to track both:
539 # - The path value such that we can safely call `readDir` on it
540 # - The path string value such that we can correctly call the `filter` with it
541 #
542 # While we could just recurse with the path value,
543 # this would then require converting it to a path string for every path,
544 # which is a fairly expensive operation
545
546 # Create a file set from a directory entry
547 fromDirEntry =
548 path: pathString: type:
549 # The filter needs to run on the path as a string
550 if !sourceFilter pathString type then
551 null
552 else if type == "directory" then
553 fromDir path pathString
554 else
555 type;
556
557 # Create a file set from a directory
558 fromDir =
559 path: pathString:
560 mapAttrs
561 # This looks a bit funny, but we need both the path-based and the path string-based values
562 (name: fromDirEntry (path + "/${name}") (pathString + "/${name}"))
563 # We need to readDir on the path value, because reading on a path string
564 # would be unspecified if there are multiple filesystem roots
565 (readDir path);
566
567 rootPathType = pathType root;
568
569 # We need to convert the path to a string to imitate what builtins.path calls the filter function with.
570 # We don't want to rely on `toString` for this though because it's not very well defined, see ../path/README.md
571 # So instead we use `lib.path.splitRoot` to safely deconstruct the path into its filesystem root and subpath
572 # We don't need the filesystem root though, builtins.path doesn't expose that in any way to the filter.
573 # So we only need the components, which we then turn into a string as one would expect.
574 rootString = "/" + concatStringsSep "/" (components (splitRoot root).subpath);
575 in
576 if rootPathType == "directory" then
577 # We imitate builtins.path not calling the filter on the root path
578 _create root (fromDir root rootString)
579 else
580 # Direct files are always included by builtins.path without calling the filter
581 # But we need to lift up the base path to its parent to satisfy the base path invariant
582 _create (dirOf root) {
583 ${baseNameOf root} = rootPathType;
584 };
585
586 # Turns a file set into the list of file paths it includes.
587 # Type: fileset -> [ Path ]
588 _toList =
589 fileset:
590 let
591 recurse =
592 path: tree:
593 if isAttrs tree then
594 concatLists (mapAttrsToList (name: value: recurse (path + "/${name}") value) tree)
595 else if tree == "directory" then
596 recurse path (readDir path)
597 else if tree == null then
598 [ ]
599 else
600 [ path ];
601 in
602 if fileset._internalIsEmptyWithoutBase then
603 [ ]
604 else
605 recurse fileset._internalBase fileset._internalTree;
606
607 # Transforms the filesetTree of a file set to a shorter base path, e.g.
608 # _shortenTreeBase [ "foo" ] (_create /foo/bar null)
609 # => { bar = null; }
610 _shortenTreeBase =
611 targetBaseComponents: fileset:
612 let
613 recurse =
614 index:
615 # If we haven't reached the required depth yet
616 if index < length fileset._internalBaseComponents then
617 # Create an attribute set and recurse as the value, this can be lazily evaluated this way
618 { ${elemAt fileset._internalBaseComponents index} = recurse (index + 1); }
619 else
620 # Otherwise we reached the appropriate depth, here's the original tree
621 fileset._internalTree;
622 in
623 recurse (length targetBaseComponents);
624
625 # Transforms the filesetTree of a file set to a longer base path, e.g.
626 # _lengthenTreeBase [ "foo" "bar" ] (_create /foo { bar.baz = "regular"; })
627 # => { baz = "regular"; }
628 _lengthenTreeBase =
629 targetBaseComponents: fileset:
630 let
631 recurse =
632 index: tree:
633 # If the filesetTree is an attribute set and we haven't reached the required depth yet
634 if isAttrs tree && index < length targetBaseComponents then
635 # Recurse with the tree under the right component (which might not exist)
636 recurse (index + 1) (tree.${elemAt targetBaseComponents index} or null)
637 else
638 # For all values here we can just return the tree itself:
639 # tree == null -> the result is also null, everything is excluded
640 # tree == "directory" -> the result is also "directory",
641 # because the base path is always a directory and everything is included
642 # isAttrs tree -> the result is `tree`
643 # because we don't need to recurse any more since `index == length longestBaseComponents`
644 tree;
645 in
646 recurse (length fileset._internalBaseComponents) fileset._internalTree;
647
648 # Computes the union of a list of filesets.
649 # The filesets must already be coerced and validated to be in the same filesystem root
650 # Type: [ Fileset ] -> Fileset
651 _unionMany =
652 filesets:
653 let
654 # All filesets that have a base, aka not the ones that are the empty value without a base
655 filesetsWithBase = filter (fileset: !fileset._internalIsEmptyWithoutBase) filesets;
656
657 # The first fileset that has a base.
658 # This value is only accessed if there are at all.
659 firstWithBase = head filesetsWithBase;
660
661 # To be able to union filesetTree's together, they need to have the same base path.
662 # Base paths can be unioned by taking their common prefix,
663 # e.g. such that `union /foo/bar /foo/baz` has the base path `/foo`
664
665 # A list of path components common to all base paths.
666 # Note that commonPrefix can only be fully evaluated,
667 # so this cannot cause a stack overflow due to a build-up of unevaluated thunks.
668 commonBaseComponents =
669 foldl' (components: el: commonPrefix components el._internalBaseComponents)
670 firstWithBase._internalBaseComponents
671 # We could also not do the `tail` here to avoid a list allocation,
672 # but then we'd have to pay for a potentially expensive
673 # but unnecessary `commonPrefix` call
674 (tail filesetsWithBase);
675
676 # The common base path assembled from a filesystem root and the common components
677 commonBase = append firstWithBase._internalBaseRoot (join commonBaseComponents);
678
679 # A list of filesetTree's that all have the same base path
680 # This is achieved by nesting the trees into the components they have over the common base path
681 # E.g. `union /foo/bar /foo/baz` has the base path /foo
682 # So the tree under `/foo/bar` gets nested under `{ bar = ...; ... }`,
683 # while the tree under `/foo/baz` gets nested under `{ baz = ...; ... }`
684 # Therefore allowing combined operations over them.
685 trees = map (_shortenTreeBase commonBaseComponents) filesetsWithBase;
686
687 # Folds all trees together into a single one using _unionTree
688 # We do not use a fold here because it would cause a thunk build-up
689 # which could cause a stack overflow for a large number of trees
690 resultTree = _unionTrees trees;
691 in
692 # If there's no values with a base, we have no files
693 if filesetsWithBase == [ ] then _emptyWithoutBase else _create commonBase resultTree;
694
695 # The union of multiple filesetTree's with the same base path.
696 # Later elements are only evaluated if necessary.
697 # Type: [ filesetTree ] -> filesetTree
698 _unionTrees =
699 trees:
700 let
701 stringIndex = findFirstIndex isString null trees;
702 withoutNull = filter (tree: tree != null) trees;
703 in
704 if stringIndex != null then
705 # If there's a string, it's always a fully included tree (dir or file),
706 # no need to look at other elements
707 elemAt trees stringIndex
708 else if withoutNull == [ ] then
709 # If all trees are null, then the resulting tree is also null
710 null
711 else
712 # The non-null elements have to be attribute sets representing partial trees
713 # We need to recurse into those
714 zipAttrsWith (name: _unionTrees) withoutNull;
715
716 # Computes the intersection of a list of filesets.
717 # The filesets must already be coerced and validated to be in the same filesystem root
718 # Type: Fileset -> Fileset -> Fileset
719 _intersection =
720 fileset1: fileset2:
721 let
722 # The common base components prefix, e.g.
723 # (/foo/bar, /foo/bar/baz) -> /foo/bar
724 # (/foo/bar, /foo/baz) -> /foo
725 commonBaseComponentsLength =
726 # TODO: Have a `lib.lists.commonPrefixLength` function such that we don't need the list allocation from commonPrefix here
727 length (commonPrefix fileset1._internalBaseComponents fileset2._internalBaseComponents);
728
729 # To be able to intersect filesetTree's together, they need to have the same base path.
730 # Base paths can be intersected by taking the longest one (if any)
731
732 # The fileset with the longest base, if any, e.g.
733 # (/foo/bar, /foo/bar/baz) -> /foo/bar/baz
734 # (/foo/bar, /foo/baz) -> null
735 longestBaseFileset =
736 if commonBaseComponentsLength == length fileset1._internalBaseComponents then
737 # The common prefix is the same as the first path, so the second path is equal or longer
738 fileset2
739 else if commonBaseComponentsLength == length fileset2._internalBaseComponents then
740 # The common prefix is the same as the second path, so the first path is longer
741 fileset1
742 else
743 # The common prefix is neither the first nor the second path
744 # This means there's no overlap between the two sets
745 null;
746
747 # Whether the result should be the empty value without a base
748 resultIsEmptyWithoutBase =
749 # If either fileset is the empty fileset without a base, the intersection is too
750 fileset1._internalIsEmptyWithoutBase
751 || fileset2._internalIsEmptyWithoutBase
752 # If there is no overlap between the base paths
753 || longestBaseFileset == null;
754
755 # Lengthen each fileset's tree to the longest base prefix
756 tree1 = _lengthenTreeBase longestBaseFileset._internalBaseComponents fileset1;
757 tree2 = _lengthenTreeBase longestBaseFileset._internalBaseComponents fileset2;
758
759 # With two filesetTree's with the same base, we can compute their intersection
760 resultTree = _intersectTree tree1 tree2;
761 in
762 if resultIsEmptyWithoutBase then
763 _emptyWithoutBase
764 else
765 _create longestBaseFileset._internalBase resultTree;
766
767 # The intersection of two filesetTree's with the same base path
768 # The second element is only evaluated as much as necessary.
769 # Type: filesetTree -> filesetTree -> filesetTree
770 _intersectTree =
771 lhs: rhs:
772 if isAttrs lhs && isAttrs rhs then
773 # Both sides are attribute sets, we can recurse for the attributes existing on both sides
774 mapAttrs (name: _intersectTree lhs.${name}) (builtins.intersectAttrs lhs rhs)
775 else if lhs == null || isString rhs then
776 # If the lhs is null, the result should also be null
777 # And if the rhs is the identity element
778 # (a string, aka it includes everything), then it's also the lhs
779 lhs
780 else
781 # In all other cases it's the rhs
782 rhs;
783
784 # Compute the set difference between two file sets.
785 # The filesets must already be coerced and validated to be in the same filesystem root.
786 # Type: Fileset -> Fileset -> Fileset
787 _difference =
788 positive: negative:
789 let
790 # The common base components prefix, e.g.
791 # (/foo/bar, /foo/bar/baz) -> /foo/bar
792 # (/foo/bar, /foo/baz) -> /foo
793 commonBaseComponentsLength =
794 # TODO: Have a `lib.lists.commonPrefixLength` function such that we don't need the list allocation from commonPrefix here
795 length (commonPrefix positive._internalBaseComponents negative._internalBaseComponents);
796
797 # We need filesetTree's with the same base to be able to compute the difference between them
798 # This here is the filesetTree from the negative file set, but for a base path that matches the positive file set.
799 # Examples:
800 # For `difference /foo /foo/bar`, `negativeTreeWithPositiveBase = { bar = "directory"; }`
801 # because under the base path of `/foo`, only `bar` from the negative file set is included
802 # For `difference /foo/bar /foo`, `negativeTreeWithPositiveBase = "directory"`
803 # because under the base path of `/foo/bar`, everything from the negative file set is included
804 # For `difference /foo /bar`, `negativeTreeWithPositiveBase = null`
805 # because under the base path of `/foo`, nothing from the negative file set is included
806 negativeTreeWithPositiveBase =
807 if commonBaseComponentsLength == length positive._internalBaseComponents then
808 # The common prefix is the same as the positive base path, so the second path is equal or longer.
809 # We need to _shorten_ the negative filesetTree to the same base path as the positive one
810 # E.g. for `difference /foo /foo/bar` the common prefix is /foo, equal to the positive file set's base
811 # So we need to shorten the base of the tree for the negative argument from /foo/bar to just /foo
812 _shortenTreeBase positive._internalBaseComponents negative
813 else if commonBaseComponentsLength == length negative._internalBaseComponents then
814 # The common prefix is the same as the negative base path, so the first path is longer.
815 # We need to lengthen the negative filesetTree to the same base path as the positive one.
816 # E.g. for `difference /foo/bar /foo` the common prefix is /foo, equal to the negative file set's base
817 # So we need to lengthen the base of the tree for the negative argument from /foo to /foo/bar
818 _lengthenTreeBase positive._internalBaseComponents negative
819 else
820 # The common prefix is neither the first nor the second path.
821 # This means there's no overlap between the two file sets,
822 # and nothing from the negative argument should get removed from the positive one
823 # E.g for `difference /foo /bar`, we remove nothing to get the same as `/foo`
824 null;
825
826 resultingTree =
827 _differenceTree positive._internalBase positive._internalTree
828 negativeTreeWithPositiveBase;
829 in
830 # If the first file set is empty, we can never have any files in the result
831 if positive._internalIsEmptyWithoutBase then
832 _emptyWithoutBase
833 # If the second file set is empty, nothing gets removed, so the result is just the first file set
834 else if negative._internalIsEmptyWithoutBase then
835 positive
836 else
837 # We use the positive file set base for the result,
838 # because only files from the positive side may be included,
839 # which is what base path is for
840 _create positive._internalBase resultingTree;
841
842 # Computes the set difference of two filesetTree's
843 # Type: Path -> filesetTree -> filesetTree
844 _differenceTree =
845 path: lhs: rhs:
846 # If the lhs doesn't have any files, or the right hand side includes all files
847 if lhs == null || isString rhs then
848 # The result will always be empty
849 null
850 # If the right hand side has no files
851 else if rhs == null then
852 # The result is always the left hand side, because nothing gets removed
853 lhs
854 else
855 # Otherwise we always have two attribute sets to recurse into
856 mapAttrs (name: lhsValue: _differenceTree (path + "/${name}") lhsValue (rhs.${name} or null)) (
857 _directoryEntries path lhs
858 );
859
860 # Filters all files in a path based on a predicate
861 # Type: ({ name, type, ... } -> Bool) -> Path -> FileSet
862 _fileFilter =
863 predicate: root:
864 let
865 # Check the predicate for a single file
866 # Type: String -> String -> filesetTree
867 fromFile =
868 name: type:
869 if
870 predicate {
871 inherit name type;
872 hasExt = ext: hasSuffix ".${ext}" name;
873
874 # To ensure forwards compatibility with more arguments being added in the future,
875 # adding an attribute which can't be deconstructed :)
876 "lib.fileset.fileFilter: The predicate function passed as the first argument must be able to handle extra attributes for future compatibility. If you're using `{ name, file, hasExt }:`, use `{ name, file, hasExt, ... }:` instead." =
877 null;
878 }
879 then
880 type
881 else
882 null;
883
884 # Check the predicate for all files in a directory
885 # Type: Path -> filesetTree
886 fromDir =
887 path:
888 mapAttrs (
889 name: type: if type == "directory" then fromDir (path + "/${name}") else fromFile name type
890 ) (readDir path);
891
892 rootType = pathType root;
893 in
894 if rootType == "directory" then
895 _create root (fromDir root)
896 else
897 # Single files are turned into a directory containing that file or nothing.
898 _create (dirOf root) {
899 ${baseNameOf root} = fromFile (baseNameOf root) rootType;
900 };
901
902 # Mirrors the contents of a Nix store path relative to a local path as a file set.
903 # Some notes:
904 # - The store path is read at evaluation time.
905 # - The store path must not include files that don't exist in the respective local path.
906 #
907 # Type: Path -> String -> FileSet
908 _mirrorStorePath =
909 localPath: storePath:
910 let
911 recurse =
912 focusedStorePath:
913 mapAttrs (
914 name: type: if type == "directory" then recurse (focusedStorePath + "/${name}") else type
915 ) (builtins.readDir focusedStorePath);
916 in
917 _create localPath (recurse storePath);
918
919 # Create a file set from the files included in the result of a fetchGit call
920 # Type: String -> String -> Path -> Attrs -> FileSet
921 _fromFetchGit =
922 function: argument: path: extraFetchGitAttrs:
923 let
924 # The code path for when isStorePath is true
925 tryStorePath =
926 if pathExists (path + "/.git") then
927 # If there is a `.git` directory in the path,
928 # it means that the path was imported unfiltered into the Nix store.
929 # This function should throw in such a case, because
930 # - `fetchGit` doesn't generally work with `.git` directories in store paths
931 # - Importing the entire path could include Git-tracked files
932 throw ''
933 lib.fileset.${function}: The ${argument} (${toString path}) is a store path within a working tree of a Git repository.
934 This indicates that a source directory was imported into the store using a method such as `import "''${./.}"` or `path:.`.
935 This function currently does not support such a use case, since it currently relies on `builtins.fetchGit`.
936 You could make this work by using a fetcher such as `fetchGit` instead of copying the whole repository.
937 If you can't avoid copying the repo to the store, see https://github.com/NixOS/nix/issues/9292.''
938 else
939 # Otherwise we're going to assume that the path was a Git directory originally,
940 # but it was fetched using a method that already removed files not tracked by Git,
941 # such as `builtins.fetchGit`, `pkgs.fetchgit` or others.
942 # So we can just import the path in its entirety.
943 _singleton path;
944
945 # The code path for when isStorePath is false
946 tryFetchGit =
947 let
948 # This imports the files unnecessarily, which currently can't be avoided
949 # because `builtins.fetchGit` is the only function exposing which files are tracked by Git.
950 # With the [lazy trees PR](https://github.com/NixOS/nix/pull/6530),
951 # the unnecessarily import could be avoided.
952 # However a simpler alternative still would be [a builtins.gitLsFiles](https://github.com/NixOS/nix/issues/2944).
953 fetchResult = fetchGit (
954 {
955 url = path;
956 shallow = true;
957 }
958 // extraFetchGitAttrs
959 );
960 in
961 # We can identify local working directories by checking for .git,
962 # see https://git-scm.com/docs/gitrepository-layout#_description.
963 # Note that `builtins.fetchGit` _does_ work for bare repositories (where there's no `.git`),
964 # even though `git ls-files` wouldn't return any files in that case.
965 if !pathExists (path + "/.git") then
966 throw "lib.fileset.${function}: Expected the ${argument} (${toString path}) to point to a local working tree of a Git repository, but it's not."
967 else
968 _mirrorStorePath path fetchResult.outPath;
969
970 in
971 if !isPath path then
972 throw "lib.fileset.${function}: Expected the ${argument} to be a path, but it's a ${typeOf path} instead."
973 else if pathType path != "directory" then
974 throw "lib.fileset.${function}: Expected the ${argument} (${toString path}) to be a directory, but it's a file instead."
975 else if hasStorePathPrefix path then
976 tryStorePath
977 else
978 tryFetchGit;
979
980}