| blob | 7f002216bc7ff816ab7485d26ce5fcef852b6279 |
1 {
2 lib ? import ../.,
3 }:
4 let
6 inherit (builtins)
7 isAttrs
8 isPath
9 isString
10 nixVersion
11 pathExists
12 readDir
13 split
14 trace
15 typeOf
16 fetchGit
17 ;
19 inherit (lib.attrsets)
20 attrNames
21 attrValues
22 mapAttrs
23 mapAttrsToList
24 optionalAttrs
25 zipAttrsWith
26 ;
28 inherit (lib.filesystem)
29 pathType
30 ;
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 ;
47 inherit (lib.path)
48 append
49 splitRoot
50 hasStorePathPrefix
51 splitStorePath
52 ;
54 inherit (lib.path.subpath)
55 components
56 join
57 ;
59 inherit (lib.strings)
60 isStringLike
61 concatStringsSep
62 substring
63 stringLength
64 hasSuffix
65 versionAtLeast
66 ;
68 inherit (lib.trivial)
69 inPureEvalMode
70 ;
71 in
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
76 rec {
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;
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 )
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 )
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 ];
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`.'';
127 # The empty file set without a base path
128 _emptyWithoutBase = {
129 _type = "fileset";
131 _internalVersion = _currentVersion;
133 # The one and only!
134 _internalIsEmptyWithoutBase = true;
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 };
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";
154 _internalVersion = _currentVersion;
156 _internalIsEmptyWithoutBase = false;
157 _internalBase = base;
158 _internalBaseRoot = parts.root;
159 _internalBaseComponents = components parts.subpath;
160 _internalTree = tree;
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 };
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;
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;
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;
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;
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 };
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;
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
277 Note that this function is strict, it evaluates the entire tree
279 Type: Path -> filesetTree -> filesetTree
280 */
281 _normaliseTreeFilter =
282 path: tree:
283 if tree == "directory" || isAttrs tree then
284 let
285 entries = _directoryEntries path tree;
286 normalisedSubtrees = mapAttrs (name: _normaliseTreeFilter (path + "/${name}")) entries;
287 subtreeValues = attrValues normalisedSubtrees;
288 in
289 # This triggers either when all files in a directory are filtered out
290 # Or when the directory doesn't contain any files at all
291 if all isNull subtreeValues then
292 null
293 # Triggers when we have the same as a `readDir path`, so we can turn it back into an equivalent "directory".
294 else if all isString subtreeValues then
295 "directory"
296 else
297 normalisedSubtrees
298 else
299 tree;
301 /*
302 A minimal normalisation of a filesetTree, intended for pretty-printing:
303 - If all children of a path are recursively included or empty directories, the path itself is also recursively included
304 - If all children of a path are fully excluded or empty directories, the path itself is an empty directory
305 - Other empty directories are represented with the special "emptyDir" string
306 While these could be replaced with `null`, that would take another mapAttrs
308 Note that this function is partially lazy.
310 Type: Path -> filesetTree -> filesetTree (with "emptyDir"'s)
311 */
312 _normaliseTreeMinimal =
313 path: tree:
314 if tree == "directory" || isAttrs tree then
315 let
316 entries = _directoryEntries path tree;
317 normalisedSubtrees = mapAttrs (name: _normaliseTreeMinimal (path + "/${name}")) entries;
318 subtreeValues = attrValues normalisedSubtrees;
319 in
320 # If there are no entries, or all entries are empty directories, return "emptyDir".
321 # After this branch we know that there's at least one file
322 if all (value: value == "emptyDir") subtreeValues then
323 "emptyDir"
325 # If all subtrees are fully included or empty directories
326 # (both of which are coincidentally represented as strings), return "directory".
327 # This takes advantage of the fact that empty directories can be represented as included directories.
328 # Note that the tree == "directory" check allows avoiding recursion
329 else if tree == "directory" || all (value: isString value) subtreeValues then
330 "directory"
332 # If all subtrees are fully excluded or empty directories, return null.
333 # This takes advantage of the fact that empty directories can be represented as excluded directories
334 else if all (value: isNull value || value == "emptyDir") subtreeValues then
335 null
337 # Mix of included and excluded entries
338 else
339 normalisedSubtrees
340 else
341 tree;
343 # Trace a filesetTree in a pretty way when the resulting value is evaluated.
344 # This can handle both normal filesetTree's, and ones returned from _normaliseTreeMinimal
345 # Type: Path -> filesetTree (with "emptyDir"'s) -> Null
346 _printMinimalTree =
347 base: tree:
348 let
349 treeSuffix =
350 tree:
351 if isAttrs tree then
352 ""
353 else if tree == "directory" then
354 " (all files in directory)"
355 else
356 # This does "leak" the file type strings of the internal representation,
357 # but this is the main reason these file type strings even are in the representation!
358 # TODO: Consider removing that information from the internal representation for performance.
359 # The file types can still be printed by querying them only during tracing
360 " (${tree})";
362 # Only for attribute set trees
363 traceTreeAttrs =
364 prevLine: indent: tree:
365 foldl' (
366 prevLine: name:
367 let
368 subtree = tree.${name};
370 # Evaluating this prints the line for this subtree
371 thisLine = trace "${indent}- ${name}${treeSuffix subtree}" prevLine;
372 in
373 if subtree == null || subtree == "emptyDir" then
374 # Don't print anything at all if this subtree is empty
375 prevLine
376 else if isAttrs subtree then
377 # A directory with explicit entries
378 # Do print this node, but also recurse
379 traceTreeAttrs thisLine "${indent} " subtree
380 else
381 # Either a file, or a recursively included directory
382 # Do print this node but no further recursion needed
383 thisLine
384 ) prevLine (attrNames tree);
386 # Evaluating this will print the first line
387 firstLine =
388 if tree == null || tree == "emptyDir" then
389 trace "(empty)" null
390 else
391 trace "${toString base}${treeSuffix tree}" null;
392 in
393 if isAttrs tree then traceTreeAttrs firstLine "" tree else firstLine;
395 # Pretty-print a file set in a pretty way when the resulting value is evaluated
396 # Type: fileset -> Null
397 _printFileset =
398 fileset:
399 if fileset._internalIsEmptyWithoutBase then
400 trace "(empty)" null
401 else
402 _printMinimalTree fileset._internalBase (
403 _normaliseTreeMinimal fileset._internalBase fileset._internalTree
404 );
406 # Turn a fileset into a source filter function suitable for `builtins.path`
407 # Only directories recursively containing at least one files are recursed into
408 # Type: fileset -> (String -> String -> Bool)
409 _toSourceFilter =
410 fileset:
411 let
412 # Simplify the tree, necessary to make sure all empty directories are null
413 # which has the effect that they aren't included in the result
414 tree = _normaliseTreeFilter fileset._internalBase fileset._internalTree;
416 # The base path as a string with a single trailing slash
417 baseString =
418 if fileset._internalBaseComponents == [ ] then
419 # Need to handle the filesystem root specially
420 "/"
421 else
422 "/" + concatStringsSep "/" fileset._internalBaseComponents + "/";
424 baseLength = stringLength baseString;
426 # Check whether a list of path components under the base path exists in the tree.
427 # This function is called often, so it should be fast.
428 # Type: [ String ] -> Bool
429 inTree =
430 components:
431 let
432 recurse =
433 index: localTree:
434 if isAttrs localTree then
435 # We have an attribute set, meaning this is a directory with at least one file
436 if index >= length components then
437 # The path may have no more components though, meaning the filter is running on the directory itself,
438 # so we always include it, again because there's at least one file in it.
439 true
440 else
441 # If we do have more components, the filter runs on some entry inside this directory, so we need to recurse
442 # We do +2 because builtins.split is an interleaved list of the inbetweens and the matches
443 recurse (index + 2) localTree.${elemAt components index}
444 else
445 # If it's not an attribute set it can only be either null (in which case it's not included)
446 # or a string ("directory" or "regular", etc.) in which case it's included
447 localTree != null;
448 in
449 recurse 0 tree;
451 # Filter suited when there's no files
452 empty = _: _: false;
454 # Filter suited when there's some files
455 # This can't be used for when there's no files, because the base directory is always included
456 nonEmpty =
457 path: type:
458 let
459 # Add a slash to the path string, turning "/foo" to "/foo/",
460 # making sure to not have any false prefix matches below.
461 # Note that this would produce "//" for "/",
462 # but builtins.path doesn't call the filter function on the `path` argument itself,
463 # meaning this function can never receive "/" as an argument
464 pathSlash = path + "/";
465 in
466 (
467 # Same as `hasPrefix pathSlash baseString`, but more efficient.
468 # With base /foo/bar we need to include /foo:
469 # hasPrefix "/foo/" "/foo/bar/"
470 if substring 0 (stringLength pathSlash) baseString == pathSlash then
471 true
472 # Same as `! hasPrefix baseString pathSlash`, but more efficient.
473 # With base /foo/bar we need to exclude /baz
474 # ! hasPrefix "/baz/" "/foo/bar/"
475 else if substring 0 baseLength pathSlash != baseString then
476 false
477 else
478 # Same as `removePrefix baseString path`, but more efficient.
479 # From the above code we know that hasPrefix baseString pathSlash holds, so this is safe.
480 # We don't use pathSlash here because we only needed the trailing slash for the prefix matching.
481 # With base /foo and path /foo/bar/baz this gives
482 # inTree (split "/" (removePrefix "/foo/" "/foo/bar/baz"))
483 # == inTree (split "/" "bar/baz")
484 # == inTree [ "bar" "baz" ]
485 inTree (split "/" (substring baseLength (-1) path))
486 )
487 # This is a way have an additional check in case the above is true without any significant performance cost
488 && (
489 # This relies on the fact that Nix only distinguishes path types "directory", "regular", "symlink" and "unknown",
490 # so everything except "unknown" is allowed, seems reasonable to rely on that
491 type != "unknown"
492 || throw ''
493 lib.fileset.toSource: `fileset` contains a file that cannot be added to the store: ${path}
494 This file is neither a regular file nor a symlink, the only file types supported by the Nix store.
495 Therefore the file set cannot be added to the Nix store as is. Make sure to not include that file to avoid this error.''
496 );
497 in
498 # Special case because the code below assumes that the _internalBase is always included in the result
499 # which shouldn't be done when we have no files at all in the base
500 # This also forces the tree before returning the filter, leads to earlier error messages
501 if fileset._internalIsEmptyWithoutBase || tree == null then empty else nonEmpty;
503 # Turn a builtins.filterSource-based source filter on a root path into a file set
504 # containing only files included by the filter.
505 # The filter is lazily called as necessary to determine whether paths are included
506 # Type: Path -> (String -> String -> Bool) -> fileset
507 _fromSourceFilter =
508 root: sourceFilter:
509 let
510 # During the recursion we need to track both:
511 # - The path value such that we can safely call `readDir` on it
512 # - The path string value such that we can correctly call the `filter` with it
513 #
514 # While we could just recurse with the path value,
515 # this would then require converting it to a path string for every path,
516 # which is a fairly expensive operation
518 # Create a file set from a directory entry
519 fromDirEntry =
520 path: pathString: type:
521 # The filter needs to run on the path as a string
522 if !sourceFilter pathString type then
523 null
524 else if type == "directory" then
525 fromDir path pathString
526 else
527 type;
529 # Create a file set from a directory
530 fromDir =
531 path: pathString:
532 mapAttrs
533 # This looks a bit funny, but we need both the path-based and the path string-based values
534 (name: fromDirEntry (path + "/${name}") (pathString + "/${name}"))
535 # We need to readDir on the path value, because reading on a path string
536 # would be unspecified if there are multiple filesystem roots
537 (readDir path);
539 rootPathType = pathType root;
541 # We need to convert the path to a string to imitate what builtins.path calls the filter function with.
542 # We don't want to rely on `toString` for this though because it's not very well defined, see ../path/README.md
543 # So instead we use `lib.path.splitRoot` to safely deconstruct the path into its filesystem root and subpath
544 # We don't need the filesystem root though, builtins.path doesn't expose that in any way to the filter.
545 # So we only need the components, which we then turn into a string as one would expect.
546 rootString = "/" + concatStringsSep "/" (components (splitRoot root).subpath);
547 in
548 if rootPathType == "directory" then
549 # We imitate builtins.path not calling the filter on the root path
550 _create root (fromDir root rootString)
551 else
552 # Direct files are always included by builtins.path without calling the filter
553 # But we need to lift up the base path to its parent to satisfy the base path invariant
554 _create (dirOf root) {
555 ${baseNameOf root} = rootPathType;
556 };
558 # Turns a file set into the list of file paths it includes.
559 # Type: fileset -> [ Path ]
560 _toList =
561 fileset:
562 let
563 recurse =
564 path: tree:
565 if isAttrs tree then
566 concatLists (mapAttrsToList (name: value: recurse (path + "/${name}") value) tree)
567 else if tree == "directory" then
568 recurse path (readDir path)
569 else if tree == null then
570 [ ]
571 else
572 [ path ];
573 in
574 if fileset._internalIsEmptyWithoutBase then
575 [ ]
576 else
577 recurse fileset._internalBase fileset._internalTree;
579 # Transforms the filesetTree of a file set to a shorter base path, e.g.
580 # _shortenTreeBase [ "foo" ] (_create /foo/bar null)
581 # => { bar = null; }
582 _shortenTreeBase =
583 targetBaseComponents: fileset:
584 let
585 recurse =
586 index:
587 # If we haven't reached the required depth yet
588 if index < length fileset._internalBaseComponents then
589 # Create an attribute set and recurse as the value, this can be lazily evaluated this way
590 { ${elemAt fileset._internalBaseComponents index} = recurse (index + 1); }
591 else
592 # Otherwise we reached the appropriate depth, here's the original tree
593 fileset._internalTree;
594 in
595 recurse (length targetBaseComponents);
597 # Transforms the filesetTree of a file set to a longer base path, e.g.
598 # _lengthenTreeBase [ "foo" "bar" ] (_create /foo { bar.baz = "regular"; })
599 # => { baz = "regular"; }
600 _lengthenTreeBase =
601 targetBaseComponents: fileset:
602 let
603 recurse =
604 index: tree:
605 # If the filesetTree is an attribute set and we haven't reached the required depth yet
606 if isAttrs tree && index < length targetBaseComponents then
607 # Recurse with the tree under the right component (which might not exist)
608 recurse (index + 1) (tree.${elemAt targetBaseComponents index} or null)
609 else
610 # For all values here we can just return the tree itself:
611 # tree == null -> the result is also null, everything is excluded
612 # tree == "directory" -> the result is also "directory",
613 # because the base path is always a directory and everything is included
614 # isAttrs tree -> the result is `tree`
615 # because we don't need to recurse any more since `index == length longestBaseComponents`
616 tree;
617 in
618 recurse (length fileset._internalBaseComponents) fileset._internalTree;
620 # Computes the union of a list of filesets.
621 # The filesets must already be coerced and validated to be in the same filesystem root
622 # Type: [ Fileset ] -> Fileset
623 _unionMany =
624 filesets:
625 let
626 # All filesets that have a base, aka not the ones that are the empty value without a base
627 filesetsWithBase = filter (fileset: !fileset._internalIsEmptyWithoutBase) filesets;
629 # The first fileset that has a base.
630 # This value is only accessed if there are at all.
631 firstWithBase = head filesetsWithBase;
633 # To be able to union filesetTree's together, they need to have the same base path.
634 # Base paths can be unioned by taking their common prefix,
635 # e.g. such that `union /foo/bar /foo/baz` has the base path `/foo`
637 # A list of path components common to all base paths.
638 # Note that commonPrefix can only be fully evaluated,
639 # so this cannot cause a stack overflow due to a build-up of unevaluated thunks.
640 commonBaseComponents =
641 foldl' (components: el: commonPrefix components el._internalBaseComponents)
642 firstWithBase._internalBaseComponents
643 # We could also not do the `tail` here to avoid a list allocation,
644 # but then we'd have to pay for a potentially expensive
645 # but unnecessary `commonPrefix` call
646 (tail filesetsWithBase);
648 # The common base path assembled from a filesystem root and the common components
649 commonBase = append firstWithBase._internalBaseRoot (join commonBaseComponents);
651 # A list of filesetTree's that all have the same base path
652 # This is achieved by nesting the trees into the components they have over the common base path
653 # E.g. `union /foo/bar /foo/baz` has the base path /foo
654 # So the tree under `/foo/bar` gets nested under `{ bar = ...; ... }`,
655 # while the tree under `/foo/baz` gets nested under `{ baz = ...; ... }`
656 # Therefore allowing combined operations over them.
657 trees = map (_shortenTreeBase commonBaseComponents) filesetsWithBase;
659 # Folds all trees together into a single one using _unionTree
660 # We do not use a fold here because it would cause a thunk build-up
661 # which could cause a stack overflow for a large number of trees
662 resultTree = _unionTrees trees;
663 in
664 # If there's no values with a base, we have no files
665 if filesetsWithBase == [ ] then _emptyWithoutBase else _create commonBase resultTree;
667 # The union of multiple filesetTree's with the same base path.
668 # Later elements are only evaluated if necessary.
669 # Type: [ filesetTree ] -> filesetTree
670 _unionTrees =
671 trees:
672 let
673 stringIndex = findFirstIndex isString null trees;
674 withoutNull = filter (tree: tree != null) trees;
675 in
676 if stringIndex != null then
677 # If there's a string, it's always a fully included tree (dir or file),
678 # no need to look at other elements
679 elemAt trees stringIndex
680 else if withoutNull == [ ] then
681 # If all trees are null, then the resulting tree is also null
682 null
683 else
684 # The non-null elements have to be attribute sets representing partial trees
685 # We need to recurse into those
686 zipAttrsWith (name: _unionTrees) withoutNull;
688 # Computes the intersection of a list of filesets.
689 # The filesets must already be coerced and validated to be in the same filesystem root
690 # Type: Fileset -> Fileset -> Fileset
691 _intersection =
692 fileset1: fileset2:
693 let
694 # The common base components prefix, e.g.
695 # (/foo/bar, /foo/bar/baz) -> /foo/bar
696 # (/foo/bar, /foo/baz) -> /foo
697 commonBaseComponentsLength =
698 # TODO: Have a `lib.lists.commonPrefixLength` function such that we don't need the list allocation from commonPrefix here
699 length (commonPrefix fileset1._internalBaseComponents fileset2._internalBaseComponents);
701 # To be able to intersect filesetTree's together, they need to have the same base path.
702 # Base paths can be intersected by taking the longest one (if any)
704 # The fileset with the longest base, if any, e.g.
705 # (/foo/bar, /foo/bar/baz) -> /foo/bar/baz
706 # (/foo/bar, /foo/baz) -> null
707 longestBaseFileset =
708 if commonBaseComponentsLength == length fileset1._internalBaseComponents then
709 # The common prefix is the same as the first path, so the second path is equal or longer
710 fileset2
711 else if commonBaseComponentsLength == length fileset2._internalBaseComponents then
712 # The common prefix is the same as the second path, so the first path is longer
713 fileset1
714 else
715 # The common prefix is neither the first nor the second path
716 # This means there's no overlap between the two sets
717 null;
719 # Whether the result should be the empty value without a base
720 resultIsEmptyWithoutBase =
721 # If either fileset is the empty fileset without a base, the intersection is too
722 fileset1._internalIsEmptyWithoutBase
723 || fileset2._internalIsEmptyWithoutBase
724 # If there is no overlap between the base paths
725 || longestBaseFileset == null;
727 # Lengthen each fileset's tree to the longest base prefix
728 tree1 = _lengthenTreeBase longestBaseFileset._internalBaseComponents fileset1;
729 tree2 = _lengthenTreeBase longestBaseFileset._internalBaseComponents fileset2;
731 # With two filesetTree's with the same base, we can compute their intersection
732 resultTree = _intersectTree tree1 tree2;
733 in
734 if resultIsEmptyWithoutBase then
735 _emptyWithoutBase
736 else
737 _create longestBaseFileset._internalBase resultTree;
739 # The intersection of two filesetTree's with the same base path
740 # The second element is only evaluated as much as necessary.
741 # Type: filesetTree -> filesetTree -> filesetTree
742 _intersectTree =
743 lhs: rhs:
744 if isAttrs lhs && isAttrs rhs then
745 # Both sides are attribute sets, we can recurse for the attributes existing on both sides
746 mapAttrs (name: _intersectTree lhs.${name}) (builtins.intersectAttrs lhs rhs)
747 else if lhs == null || isString rhs then
748 # If the lhs is null, the result should also be null
749 # And if the rhs is the identity element
750 # (a string, aka it includes everything), then it's also the lhs
751 lhs
752 else
753 # In all other cases it's the rhs
754 rhs;
756 # Compute the set difference between two file sets.
757 # The filesets must already be coerced and validated to be in the same filesystem root.
758 # Type: Fileset -> Fileset -> Fileset
759 _difference =
760 positive: negative:
761 let
762 # The common base components prefix, e.g.
763 # (/foo/bar, /foo/bar/baz) -> /foo/bar
764 # (/foo/bar, /foo/baz) -> /foo
765 commonBaseComponentsLength =
766 # TODO: Have a `lib.lists.commonPrefixLength` function such that we don't need the list allocation from commonPrefix here
767 length (commonPrefix positive._internalBaseComponents negative._internalBaseComponents);
769 # We need filesetTree's with the same base to be able to compute the difference between them
770 # This here is the filesetTree from the negative file set, but for a base path that matches the positive file set.
771 # Examples:
772 # For `difference /foo /foo/bar`, `negativeTreeWithPositiveBase = { bar = "directory"; }`
773 # because under the base path of `/foo`, only `bar` from the negative file set is included
774 # For `difference /foo/bar /foo`, `negativeTreeWithPositiveBase = "directory"`
775 # because under the base path of `/foo/bar`, everything from the negative file set is included
776 # For `difference /foo /bar`, `negativeTreeWithPositiveBase = null`
777 # because under the base path of `/foo`, nothing from the negative file set is included
778 negativeTreeWithPositiveBase =
779 if commonBaseComponentsLength == length positive._internalBaseComponents then
780 # The common prefix is the same as the positive base path, so the second path is equal or longer.
781 # We need to _shorten_ the negative filesetTree to the same base path as the positive one
782 # E.g. for `difference /foo /foo/bar` the common prefix is /foo, equal to the positive file set's base
783 # So we need to shorten the base of the tree for the negative argument from /foo/bar to just /foo
784 _shortenTreeBase positive._internalBaseComponents negative
785 else if commonBaseComponentsLength == length negative._internalBaseComponents then
786 # The common prefix is the same as the negative base path, so the first path is longer.
787 # We need to lengthen the negative filesetTree to the same base path as the positive one.
788 # E.g. for `difference /foo/bar /foo` the common prefix is /foo, equal to the negative file set's base
789 # So we need to lengthen the base of the tree for the negative argument from /foo to /foo/bar
790 _lengthenTreeBase positive._internalBaseComponents negative
791 else
792 # The common prefix is neither the first nor the second path.
793 # This means there's no overlap between the two file sets,
794 # and nothing from the negative argument should get removed from the positive one
795 # E.g for `difference /foo /bar`, we remove nothing to get the same as `/foo`
796 null;
798 resultingTree =
799 _differenceTree positive._internalBase positive._internalTree
800 negativeTreeWithPositiveBase;
801 in
802 # If the first file set is empty, we can never have any files in the result
803 if positive._internalIsEmptyWithoutBase then
804 _emptyWithoutBase
805 # If the second file set is empty, nothing gets removed, so the result is just the first file set
806 else if negative._internalIsEmptyWithoutBase then
807 positive
808 else
809 # We use the positive file set base for the result,
810 # because only files from the positive side may be included,
811 # which is what base path is for
812 _create positive._internalBase resultingTree;
814 # Computes the set difference of two filesetTree's
815 # Type: Path -> filesetTree -> filesetTree
816 _differenceTree =
817 path: lhs: rhs:
818 # If the lhs doesn't have any files, or the right hand side includes all files
819 if lhs == null || isString rhs then
820 # The result will always be empty
821 null
822 # If the right hand side has no files
823 else if rhs == null then
824 # The result is always the left hand side, because nothing gets removed
825 lhs
826 else
827 # Otherwise we always have two attribute sets to recurse into
828 mapAttrs (name: lhsValue: _differenceTree (path + "/${name}") lhsValue (rhs.${name} or null)) (
829 _directoryEntries path lhs
830 );
832 # Filters all files in a path based on a predicate
833 # Type: ({ name, type, ... } -> Bool) -> Path -> FileSet
834 _fileFilter =
835 predicate: root:
836 let
837 # Check the predicate for a single file
838 # Type: String -> String -> filesetTree
839 fromFile =
840 name: type:
841 if
842 predicate {
843 inherit name type;
844 hasExt = ext: hasSuffix ".${ext}" name;
846 # To ensure forwards compatibility with more arguments being added in the future,
847 # adding an attribute which can't be deconstructed :)
848 "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." =
849 null;
850 }
851 then
852 type
853 else
854 null;
856 # Check the predicate for all files in a directory
857 # Type: Path -> filesetTree
858 fromDir =
859 path:
860 mapAttrs (
861 name: type: if type == "directory" then fromDir (path + "/${name}") else fromFile name type
862 ) (readDir path);
864 rootType = pathType root;
865 in
866 if rootType == "directory" then
867 _create root (fromDir root)
868 else
869 # Single files are turned into a directory containing that file or nothing.
870 _create (dirOf root) {
871 ${baseNameOf root} = fromFile (baseNameOf root) rootType;
872 };
874 # Support for `builtins.fetchGit` with `submodules = true` was introduced in 2.4
875 # https://github.com/NixOS/nix/commit/55cefd41d63368d4286568e2956afd535cb44018
876 _fetchGitSubmodulesMinver = "2.4";
878 # Support for `builtins.fetchGit` with `shallow = true` was introduced in 2.4
879 # https://github.com/NixOS/nix/commit/d1165d8791f559352ff6aa7348e1293b2873db1c
880 _fetchGitShallowMinver = "2.4";
882 # Mirrors the contents of a Nix store path relative to a local path as a file set.
883 # Some notes:
884 # - The store path is read at evaluation time.
885 # - The store path must not include files that don't exist in the respective local path.
886 #
887 # Type: Path -> String -> FileSet
888 _mirrorStorePath =
889 localPath: storePath:
890 let
891 recurse =
892 focusedStorePath:
893 mapAttrs (
894 name: type: if type == "directory" then recurse (focusedStorePath + "/${name}") else type
895 ) (builtins.readDir focusedStorePath);
896 in
897 _create localPath (recurse storePath);
899 # Create a file set from the files included in the result of a fetchGit call
900 # Type: String -> String -> Path -> Attrs -> FileSet
901 _fromFetchGit =
902 function: argument: path: extraFetchGitAttrs:
903 let
904 # The code path for when isStorePath is true
905 tryStorePath =
906 if pathExists (path + "/.git") then
907 # If there is a `.git` directory in the path,
908 # it means that the path was imported unfiltered into the Nix store.
909 # This function should throw in such a case, because
910 # - `fetchGit` doesn't generally work with `.git` directories in store paths
911 # - Importing the entire path could include Git-tracked files
912 throw ''
913 lib.fileset.${function}: The ${argument} (${toString path}) is a store path within a working tree of a Git repository.
914 This indicates that a source directory was imported into the store using a method such as `import "''${./.}"` or `path:.`.
915 This function currently does not support such a use case, since it currently relies on `builtins.fetchGit`.
916 You could make this work by using a fetcher such as `fetchGit` instead of copying the whole repository.
917 If you can't avoid copying the repo to the store, see https://github.com/NixOS/nix/issues/9292.''
918 else
919 # Otherwise we're going to assume that the path was a Git directory originally,
920 # but it was fetched using a method that already removed files not tracked by Git,
921 # such as `builtins.fetchGit`, `pkgs.fetchgit` or others.
922 # So we can just import the path in its entirety.
923 _singleton path;
925 # The code path for when isStorePath is false
926 tryFetchGit =
927 let
928 # This imports the files unnecessarily, which currently can't be avoided
929 # because `builtins.fetchGit` is the only function exposing which files are tracked by Git.
930 # With the [lazy trees PR](https://github.com/NixOS/nix/pull/6530),
931 # the unnecessarily import could be avoided.
932 # However a simpler alternative still would be [a builtins.gitLsFiles](https://github.com/NixOS/nix/issues/2944).
933 fetchResult = fetchGit (
934 {
935 url = path;
936 }
937 # In older Nix versions, repositories were always assumed to be deep clones, which made `fetchGit` fail for shallow clones
938 # For newer versions this was fixed, but the `shallow` flag is required.
939 # The only behavioral difference is that for shallow clones, `fetchGit` doesn't return a `revCount`,
940 # which we don't need here, so it's fine to always pass it.
942 # Unfortunately this means older Nix versions get a poor error message for shallow repositories, and there's no good way to improve that.
943 # Checking for `.git/shallow` doesn't seem worth it, especially since that's more of an implementation detail,
944 # and would also require more code to handle worktrees where `.git` is a file.
945 // optionalAttrs (versionAtLeast nixVersion _fetchGitShallowMinver) { shallow = true; }
946 // extraFetchGitAttrs
947 );
948 in
949 # We can identify local working directories by checking for .git,
950 # see https://git-scm.com/docs/gitrepository-layout#_description.
951 # Note that `builtins.fetchGit` _does_ work for bare repositories (where there's no `.git`),
952 # even though `git ls-files` wouldn't return any files in that case.
953 if !pathExists (path + "/.git") then
954 throw "lib.fileset.${function}: Expected the ${argument} (${toString path}) to point to a local working tree of a Git repository, but it's not."
955 else
956 _mirrorStorePath path fetchResult.outPath;
958 in
959 if !isPath path then
960 throw "lib.fileset.${function}: Expected the ${argument} to be a path, but it's a ${typeOf path} instead."
961 else if pathType path != "directory" then
962 throw "lib.fileset.${function}: Expected the ${argument} (${toString path}) to be a directory, but it's a file instead."
963 else if hasStorePathPrefix path then
964 tryStorePath
965 else
966 tryFetchGit;
968 }