This seems to be slower as of yet.
TODO
- [ ] remove merge pass 2 into 1:
- pass 1: fill UpdateQueue
- pass 2: stats (like max output size)
- pass 3: k-way merge
- [ ] maybe tracking sortedness is useful and cheap? in pass 1, building the UpdateQueue
- [ ] make it actually fast; different algorithm depending on size distribution and number of update ops?
- currently solution is the min-heap or priority queue approach
- divide and conquer (see also Nixpkgs which manually implements this for pkgs/by-name)
binary tree-shaped sorted merge operations
- can we take the size of attrsets into account to balance the work?
1000 + (1 + (1 + 1)) is better than ((1000+1)+1)+1 (where number refers to attrset size)
- iterative pairwise merging is more or less what we had, the tree of updates is flattened. Probably worse.
- perhaps some combination of solutions, depending on a heuristic
- [ ] split callFunction into two parts, effectively
- call2Thunk (create the new scope's Env etc)
- eval that thunk (evaluate the body)
- [ ] implement ExprApply::evalForUpdate - easy after the split
- [ ] make foldl' (//) work?
- [ ] optimize listToAttrs and other primops?
This is because with the split packages of the Meson build, we simply
have no idea what directory the binaries will be installed in when we
build the library.
In the process of doing so, consolidate and make more sophisticated the
logic to cope with a few corner cases (e.g. `NIX_BIN_DIR` exists, but no
binaries are inside it).
Co-authored-by: Robert Hensing <roberth@users.noreply.github.com>
This ended up motivating a good deal of other infra improvements in
order to get Windows right:
- `OsString` to complement `std::filesystem::path`
- env var code for working with the underlying `OsString`s
- Rename `PATHNG_LITERAL` to `OS_STR`
- `NativePathTrait` renamed to `OsPathTrait`, given a character template
parameter until #9205 is complete.
Split `tests.cc` matching split of `util.{cc,hh}` last year.
Co-authored-by: Robert Hensing <roberth@users.noreply.github.com>
The test split matches PR #8920, so the utility files and tests files
are once again to 1-1. The string changes continues what was started in
PR #11093.
In the FFI world we have many tools that are not gcc/clang and therefore
not always support the latest C standard. This fixes support with cffi
i.e. used in https://github.com/tweag/python-nix
It was failing with:
error: AWS error fetching 'nix-cache-info': The specified bucket does not exist
because `S3BinaryCacheStoreImpl` had a `bucketName` field that
shadowed the inherited `bucketName from `S3BinaryCacheStoreConfig`.
We didn't even realize you *could* use this syntax with -E and -f, much
less that the attribute path could be *empty*.
Change-Id: Id1a6715609f3a76a5ce477bd43a7832effbbe07b
* docs: unify documentation on search paths
- put all the information on search path semantics into `builtins.findFile`
- put all the information on determining the value of `builtins.nixPath` into the
`nix-path` setting
maybe `builtins.nixPath` is a better place for this, but those bits
can still be moved around now that it's all next to each other.
- link to the syntax page for lookup paths from all places that are
concerned with it
- add or clarify examples
- add a test verifying a claim from documentation
This also bans various sneaking of negative numbers from the language
into unsuspecting builtins as was exposed while auditing the
consequences of changing the Nix language integer type to a newtype.
It's unlikely that this change comprehensively ensures correctness when
passing integers out of the Nix language and we should probably add a
checked-narrowing function or something similar, but that's out of scope
for the immediate change.
During the development of this I found a few fun facts about the
language:
- You could overflow integers by converting from unsigned JSON values.
- You could overflow unsigned integers by converting negative numbers
into them when going into Nix config, into fetchTree, and into flake
inputs.
The flake inputs and Nix config cannot actually be tested properly
since they both ban thunks, however, we put in checks anyway because
it's possible these could somehow be used to do such shenanigans some
other way.
Note that Lix has banned Nix language integer overflows since the very
first public beta, but threw a SIGILL about them because we run with
-fsanitize=signed-overflow -fsanitize-undefined-trap-on-error in
production builds. Since the Nix language uses signed integers, overflow
was simply undefined behaviour, and since we defined that to trap, it
did.
Trapping on it was a bad UX, but we didn't even entirely notice
that we had done this at all until it was reported as a bug a couple of
months later (which is, to be fair, that flag working as intended), and
it's got enough production time that, aside from code that is IMHO buggy
(and which is, in any case, not in nixpkgs) such as
https://git.lix.systems/lix-project/lix/issues/445, we don't think
anyone doing anything reasonable actually depends on wrapping overflow.
Even for weird use cases such as doing funny bit crimes, it doesn't make
sense IMO to have wrapping behaviour, since two's complement arithmetic
overflow behaviour is so *aggressively* not what you want for *any* kind
of mathematics/algorithms. The Nix language exists for package
management, a domain where bit crimes are already only dubiously in
scope to begin with, and it makes a lot more sense for that domain for
the integers to never lose precision, either by throwing errors if they
would, or by being arbitrary-precision.
Fixes: https://github.com/NixOS/nix/issues/10968
Original-CL: https://gerrit.lix.systems/c/lix/+/1596
Change-Id: I51f253840c4af2ea5422b8a420aa5fafbf8fae75
The actual motive here is the avoidance of integer overflow if we were
to make these use checked NixInts and retain the subtraction.
However, the actual *intent* of this code is a three-way comparison,
which can be done with operator<=>, so we should just do *that* instead.
Change-Id: I7f9a7da1f3176424b528af6d1b4f1591e4ab26bf
