Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

lib: Improve overrideExisting implementation #46336

Merged
merged 3 commits into from Sep 18, 2018
Merged

lib: Improve overrideExisting implementation #46336

merged 3 commits into from Sep 18, 2018

Conversation

infinisil
Copy link
Member

Motivation for this change

The original implementation was overcomplicated

@Profpatsch

Because it was fun I did the proof for this, even though it's pretty easy to see why it works:

Proof of equivalence

The definition of or can be thought of as:

a.n or e == if a ? n then a.n else e

First we prove that attrByPath [attr] old.${attr} new == new.${attr} or old.${attr}

attrByPath [attr] old.${attr} new
# Def. attrByPath
let attr' = head [attr]; in
if new ? ${attr'} then attrByPath (tail [attr]) old.${attr} new.${attr'} else old.${attr}
# Def. head, tail
let attr' = attr; in
if new ? ${attr'} then attrByPath [] old.${attr} new.${attr'} else old.${attr}
# Substitution
if new ? ${attr} then attrByPath [] old.${attr} new.${attr} else old.${attr}
# Def. attrByPath
if new ? ${attr} then new.${attr} else old.${attr}
# Def. or
new.${attr} or old.${attr}
old // listToAttrs (map (attr: nameValuePair attr (attrByPath [attr] old.${attr} new)) (attrNames old))
# Via above proof
old // listToAttrs (map (attr: nameValuePair attr (new.${attr} or old.${attr})) (attrNames old))
# Def. nameValuePair
old // listToAttrs (map (attr: { name = attr; value = new.${attr} or old.${attr}; }) (attrNames old))
# Def. mapAttrs
old // mapAttrs (attr: value: new.${attr} or value) old
# By handwaving, it's much more work to prove that, but it's pretty obvious
mapAttrs (attr: value: new.${attr} or value) old
# Renaming
mapAttrs (name: value: new.${name} or value) old
Things done
  • Tested using sandboxing (nix.useSandbox on NixOS, or option sandbox in nix.conf on non-NixOS)
  • Built on platform(s)
    • NixOS
    • macOS
    • other Linux distributions
  • Tested via one or more NixOS test(s) if existing and applicable for the change (look inside nixos/tests)
  • Tested compilation of all pkgs that depend on this change using nix-shell -p nox --run "nox-review wip"
  • Tested execution of all binary files (usually in ./result/bin/)
  • Determined the impact on package closure size (by running nix path-info -S before and after)
  • Fits CONTRIBUTING.md.

@Profpatsch
Copy link
Member

Profpatsch commented Sep 7, 2018 •
edited

Yay for referential equality.

I think the existing example is a bit misleading, I think putting these consecutive ones is better:

overrideExisting {} { a = 1; }
=> {}
overrideExisting { b = 2; } { a = 1; }
=> { b = 2; }
overrideExisting { a = 3; b = 2; } { a = 1; }
=> { a = 1; b = 2; }

It would also be nice to have these as tests in lib/tests/misc.nix.

@xeji
Copy link
Contributor

xeji commented Sep 7, 2018

nice! 👍

@infinisil
Copy link
Member Author

@Profpatsch Added some tests :)

@Profpatsch
Copy link
Member

Can you replace the examples in the docstring as well? After that I don’t see a reason we shouldn’t merge.

@infinisil
Copy link
Member Author

@Profpatsch Done did that

@Mic92 Mic92 merged commit 83d89ed into NixOS:master Sep 18, 2018
@Profpatsch
Copy link
Member

Awesome.

@infinisil infinisil deleted the overrideExisting branch September 18, 2018 13:38
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@edolstra edolstra Awaiting requested review from edolstra

@nbp nbp Awaiting requested review from nbp

Assignees
No one assigned
Labels
10.rebuild-darwin: 0 10.rebuild-linux: 0
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
5 participants
@infinisil @Profpatsch @xeji @Mic92 @GrahamcOfBorg