Use `std::set<StringContextElem>` not `PathSet` for string contexts by Ericson2314 · Pull Request #7710 · NixOS/nix

Ericson2314 · 2023-01-29T16:48:58Z

Motivation

PathSet is not correct because string contexts have other forms (Built and DrvDeep) that are not rendered as plain store paths. Instead of wrongly using PathSet, or "stringly typed" using StringSet, use std::std<StringContextElem>.

In support of this change, NixStringContext is now defined as std::std<StringContextElem> not std:vector<StringContextElem>. The old definition was just used by a getContext method which was only used by the eval cache. It can be deleted altogether since the types are now unified and the preexisting copyContext function already suffices.

Summarizing the previous paragraph:

Old:

value/context.hh: NixStringContext = std::vector<StringContextElem>
value.hh: NixStringContext Value::getContext(...)
value.hh: copyContext(...)

New:

value/context.hh: NixStringContext = std::set<StringContextElem>
value.hh: copyContext(...)

This makes NixStringContext the common thing, and narrows the scope of the odder and rarely used NixStringContextExact.

The string representation of string context elements no longer contains the store dir. The diff of src/libexpr/tests/value/context.cc should make clear what the new representation is, so we recommend reviewing that file first. This was done for two reasons:

Less API churn:

Value::mkString and friends did not take a Store before. But if NixStringContextElem::{parse, to_string} do take a store (as they did before), then we cannot have the Value functions use them (in order to work with the fully-structured NixStringContext) without adding that argument.

That would have been a lot of churn of threading the store, and this diff is already large enough, so the easier and less invasive thing to do was simply make the element parse and to_string functions not take the Store reference, and the easiest way to do that was to simply drop the store dir.

Space usage:

Dropping the /nix/store/ (or similar) from the internal representation will safe space in the heap of the Nix programming being interpreted. If the heap contains many strings with non-trivial contexts, the saving could add up to something significant.

The eval cache version is bumped.

The eval cache serialization uses NixStringContextElem::{parse, to_string}, and since those functions are changed per the above, that means the on-disk representation is also changed.

This is simply done by changing the name of the used for the eval cache from eval-cache-v4 to eval-cache-v5`.

To avoid some duplication EvalCache::mkPathString is added to abstract over the simple case of turning a store path to a string with just that string in the context.

Context

This PR picks up where #7543 left off. That one introduced the fully structured NixStringContextElem data type, but kept PathSet context as an awkward middle ground between internal char[][] interpreter heap string contexts and NixStringContext fully parsed string contexts.

The infelicity of PathSet context was specifically called out during Nix team group review, but it was agreeing that fixing it could be left as future work. This is that future work.

A possible follow-up step would be to get rid of the char[][] evaluator heap representation, too, but it is not yet clear how to do that. To use NixStringContextElem there we would need to get the STL containers to GC pointers in the GC build, and I am not sure how to do that.

PR #7543 effectively is writing the inverse of a mkPathString, mkOutputString, and one more such function for the DrvDeep case. I would like that PR to have property tests ensuring it is actually the inverse as expected.

This PR sets things up nicely so that reworking that PR to be in that more elegant and better tested way is possible.

Checklist for maintainers

Maintainers: tick if completed or explain if not relevant

agreed on idea
agreed on implementation strategy
tests, as appropriate
- functional tests - tests/**.sh
- unit tests - src/*/tests
- integration tests - tests/nixos/*
documentation in the manual
code and comments are self-explanatory
commit message explains why the change was made
new feature or bug fix: updated release notes

cole-h · 2023-01-29T18:42:49Z

The pedant in me notes that your commit and PR title uses std::std rather than the (likely) intended std::set ;)

nixos-discourse · 2023-02-13T15:54:13Z

This pull request has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/2023-02-10-nix-team-meeting-minutes-31/25438/1

Ericson2314 · 2023-04-20T03:51:26Z

Rebased, conflicts fixed.

thufschmitt

Looks good overal, quite welcome change :)

A few unusual things wrt the for loops that would at least deserve a bit of explanation.

The thing I'm not sure about is whether we need the Exact variant is still needed. But since this PR made the conservative choice here, we might just merge it and see later in the worst case.

thufschmitt · 2023-04-20T07:13:51Z

src/libexpr/primops.cc

+    NixStringContext context;
+    std::transform(
+        std::make_move_iterator(refs.begin()),
+        std::make_move_iterator(refs.end()),
+        std::inserter(context, context.begin()),
+        [](const StorePath && p) {
+            return NixStringContextElem::Opaque {
+                .path = std::move((StorePath &&)p),
+            };
+        });


Is there a reason for not using a plain for loop here? As much as I like good functional structures, C++ makes it painfully verbose and hard to understand compared to the simpler

Suggested change

NixStringContext context;

std::transform(

std::make_move_iterator(refs.begin()),

std::make_move_iterator(refs.end()),

std::inserter(context, context.begin()),

[](const StorePath && p) {

return NixStringContextElem::Opaque {

.path = std::move((StorePath &&)p),

};

});

NixStringContext context;

for (auto & p : refs) {

context.insert(NixStringContextElem::Opaque(std::move(p)));

}

I think I was concerned about copying vs moving, but sure we can try to for loop first.

I accepted the change, but based on trying the thing below I think that auto expands to const _, and thus I am not really sure what is happening.

I suppose it might leave behind an invalid std::set which nonetheless does still deallocate correctly.

thufschmitt · 2023-04-20T07:17:48Z

src/libexpr/primops/context.cc

+    auto i = std::make_move_iterator(context.begin());
+    auto e = std::make_move_iterator(context.end());
+    for (; i != e; ++i) {


What's the reason for this rather than directly iterating over context ?

probably again concerned about moving.

I tired getting rid of this but it was not obvious how to do so without an incorrect const sneaking in.

Ah I just did the same cast for this and the other one, to make clang happy. Probably same making invalid set + safe dealloc is going on.

thufschmitt · 2023-04-20T07:25:13Z

src/libexpr/eval-cache.hh

+// The order is not supposed to matter, we but we are precisely tracking
+// evaluation
+typedef std::vector<NixStringContextElem> NixStringContextExact;
+typedef std::pair<std::string, NixStringContextExact> string_t;


I'm not sure whether we really need that. The definition of the String type mentions that the context must be sorted any way. So I think it's OK to just store it in an arbitrary order in the db

Oh nice, I'll do what you say and cite that comment. Thanks!

Motivation `PathSet` is not correct because string contexts have other forms (`Built` and `DrvDeep`) that are not rendered as plain store paths. Instead of wrongly using `PathSet`, or "stringly typed" using `StringSet`, use `std::std<StringContextElem>`. ----- In support of this change, `NixStringContext` is now defined as `std::std<StringContextElem>` not `std:vector<StringContextElem>`. The old definition was just used by a `getContext` method which was only used by the eval cache. It can be deleted altogether since the types are now unified and the preexisting `copyContext` function already suffices. Summarizing the previous paragraph: Old: - `value/context.hh`: `NixStringContext = std::vector<StringContextElem>` - `value.hh`: `NixStringContext Value::getContext(...)` - `value.hh`: `copyContext(...)` New: - `value/context.hh`: `NixStringContext = std::set<StringContextElem>` - `value.hh`: `copyContext(...)` ---- The string representation of string context elements no longer contains the store dir. The diff of `src/libexpr/tests/value/context.cc` should make clear what the new representation is, so we recommend reviewing that file first. This was done for two reasons: Less API churn: `Value::mkString` and friends did not take a `Store` before. But if `NixStringContextElem::{parse, to_string}` *do* take a store (as they did before), then we cannot have the `Value` functions use them (in order to work with the fully-structured `NixStringContext`) without adding that argument. That would have been a lot of churn of threading the store, and this diff is already large enough, so the easier and less invasive thing to do was simply make the element `parse` and `to_string` functions not take the `Store` reference, and the easiest way to do that was to simply drop the store dir. Space usage: Dropping the `/nix/store/` (or similar) from the internal representation will safe space in the heap of the Nix programming being interpreted. If the heap contains many strings with non-trivial contexts, the saving could add up to something significant. ---- The eval cache version is bumped. The eval cache serialization uses `NixStringContextElem::{parse, to_string}`, and since those functions are changed per the above, that means the on-disk representation is also changed. This is simply done by changing the name of the used for the eval cache from `eval-cache-v4` to eval-cache-v5`. ---- To avoid some duplication `EvalCache::mkPathString` is added to abstract over the simple case of turning a store path to a string with just that string in the context. Context This PR picks up where NixOS#7543 left off. That one introduced the fully structured `NixStringContextElem` data type, but kept `PathSet context` as an awkward middle ground between internal `char[][]` interpreter heap string contexts and `NixStringContext` fully parsed string contexts. The infelicity of `PathSet context` was specifically called out during Nix team group review, but it was agreeing that fixing it could be left as future work. This is that future work. A possible follow-up step would be to get rid of the `char[][]` evaluator heap representation, too, but it is not yet clear how to do that. To use `NixStringContextElem` there we would need to get the STL containers to GC pointers in the GC build, and I am not sure how to do that. ---- PR NixOS#7543 effectively is writing the inverse of a `mkPathString`, `mkOutputString`, and one more such function for the `DrvDeep` case. I would like that PR to have property tests ensuring it is actually the inverse as expected. This PR sets things up nicely so that reworking that PR to be in that more elegant and better tested way is possible. Co-authored-by: Théophane Hufschmitt <[email protected]>

Ericson2314 · 2023-04-21T05:07:15Z

OK, I think this is ready now.

Ericson2314 requested review from edolstra and thufschmitt as code owners January 29, 2023 16:48

Ericson2314 changed the title ~~Use std::std<StringContextElem> not PathSet for string contexts~~ Use std::set<StringContextElem> not PathSet for string contexts Jan 29, 2023

Ericson2314 force-pushed the context-not-path-set branch 3 times, most recently from 1de3dc7 to e225eb8 Compare February 1, 2023 22:04

thufschmitt self-assigned this Feb 10, 2023

Ericson2314 force-pushed the context-not-path-set branch from e225eb8 to b192abc Compare April 20, 2023 03:51

github-actions bot added new-cli Relating to the "nix" command repl The Read Eval Print Loop, "nix repl" command and debugger with-tests Issues related to testing. PRs with tests have some priority labels Apr 20, 2023

Ericson2314 mentioned this pull request Apr 20, 2023

Make more string values work as installables #7601

Merged

7 tasks

thufschmitt suggested changes Apr 20, 2023

View reviewed changes

Ericson2314 force-pushed the context-not-path-set branch 2 times, most recently from ab70fa4 to 3607521 Compare April 21, 2023 05:04

Ericson2314 force-pushed the context-not-path-set branch from 3607521 to 85f0cdc Compare April 21, 2023 05:06

thufschmitt approved these changes Apr 21, 2023

View reviewed changes

thufschmitt merged commit 7474a90 into NixOS:master Apr 21, 2023

Ericson2314 deleted the context-not-path-set branch April 21, 2023 06:15

Uh oh!

Comments

Conversation

Ericson2314 commented Jan 29, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Motivation

Less API churn:

Space usage:

Context

Checklist for maintainers

Uh oh!

cole-h commented Jan 29, 2023

Uh oh!

nixos-discourse commented Feb 13, 2023

Uh oh!

Ericson2314 commented Apr 20, 2023

Uh oh!

thufschmitt left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Ericson2314 commented Apr 21, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Ericson2314 commented Jan 29, 2023 •

edited

Loading