diff options
author | Silvan Mosberger <contact@infinisil.com> | 2023-11-01 19:40:45 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-11-01 19:40:45 +0100 |
commit | fc28c5e5b79ada17ce17b5c83e07a2949b959fcf (patch) | |
tree | 8955af520cba3d6f3539d8b182960b7bd376f31b /lib/fileset/internal.nix | |
parent | 1c7f17f39502a27885d9b9c9505c612adb41823e (diff) | |
parent | 50df7f977548c296e475ad37c1d44afcdc9f8e26 (diff) |
Merge pull request #259065 from tweag/fileset.difference
`lib.fileset.difference`: init
Diffstat (limited to 'lib/fileset/internal.nix')
-rw-r--r-- | lib/fileset/internal.nix | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/lib/fileset/internal.nix b/lib/fileset/internal.nix index 76b95c6ae471b..b919a5de3eef4 100644 --- a/lib/fileset/internal.nix +++ b/lib/fileset/internal.nix @@ -651,6 +651,86 @@ rec { # In all other cases it's the rhs rhs; + # Compute the set difference between two file sets. + # The filesets must already be coerced and validated to be in the same filesystem root. + # Type: Fileset -> Fileset -> Fileset + _difference = positive: negative: + let + # The common base components prefix, e.g. + # (/foo/bar, /foo/bar/baz) -> /foo/bar + # (/foo/bar, /foo/baz) -> /foo + commonBaseComponentsLength = + # TODO: Have a `lib.lists.commonPrefixLength` function such that we don't need the list allocation from commonPrefix here + length ( + commonPrefix + positive._internalBaseComponents + negative._internalBaseComponents + ); + + # We need filesetTree's with the same base to be able to compute the difference between them + # This here is the filesetTree from the negative file set, but for a base path that matches the positive file set. + # Examples: + # For `difference /foo /foo/bar`, `negativeTreeWithPositiveBase = { bar = "directory"; }` + # because under the base path of `/foo`, only `bar` from the negative file set is included + # For `difference /foo/bar /foo`, `negativeTreeWithPositiveBase = "directory"` + # because under the base path of `/foo/bar`, everything from the negative file set is included + # For `difference /foo /bar`, `negativeTreeWithPositiveBase = null` + # because under the base path of `/foo`, nothing from the negative file set is included + negativeTreeWithPositiveBase = + if commonBaseComponentsLength == length positive._internalBaseComponents then + # The common prefix is the same as the positive base path, so the second path is equal or longer. + # We need to _shorten_ the negative filesetTree to the same base path as the positive one + # E.g. for `difference /foo /foo/bar` the common prefix is /foo, equal to the positive file set's base + # So we need to shorten the base of the tree for the negative argument from /foo/bar to just /foo + _shortenTreeBase positive._internalBaseComponents negative + else if commonBaseComponentsLength == length negative._internalBaseComponents then + # The common prefix is the same as the negative base path, so the first path is longer. + # We need to lengthen the negative filesetTree to the same base path as the positive one. + # E.g. for `difference /foo/bar /foo` the common prefix is /foo, equal to the negative file set's base + # So we need to lengthen the base of the tree for the negative argument from /foo to /foo/bar + _lengthenTreeBase positive._internalBaseComponents negative + else + # The common prefix is neither the first nor the second path. + # This means there's no overlap between the two file sets, + # and nothing from the negative argument should get removed from the positive one + # E.g for `difference /foo /bar`, we remove nothing to get the same as `/foo` + null; + + resultingTree = + _differenceTree + positive._internalBase + positive._internalTree + negativeTreeWithPositiveBase; + in + # If the first file set is empty, we can never have any files in the result + if positive._internalIsEmptyWithoutBase then + _emptyWithoutBase + # If the second file set is empty, nothing gets removed, so the result is just the first file set + else if negative._internalIsEmptyWithoutBase then + positive + else + # We use the positive file set base for the result, + # because only files from the positive side may be included, + # which is what base path is for + _create positive._internalBase resultingTree; + + # Computes the set difference of two filesetTree's + # Type: Path -> filesetTree -> filesetTree + _differenceTree = path: lhs: rhs: + # If the lhs doesn't have any files, or the right hand side includes all files + if lhs == null || isString rhs then + # The result will always be empty + null + # If the right hand side has no files + else if rhs == null then + # The result is always the left hand side, because nothing gets removed + lhs + else + # Otherwise we always have two attribute sets to recurse into + mapAttrs (name: lhsValue: + _differenceTree (path + "/${name}") lhsValue (rhs.${name} or null) + ) (_directoryEntries path lhs); + _fileFilter = predicate: fileset: let recurse = path: tree: |