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