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