evaluator: implement new evaluator as the basis for performance and other improvements #2884

myitcv · 2024-02-29T05:32:25Z

This is a placeholder issue for the implementation of a new version of the core CUE evaluator, a version that will enable (further) performance improvements referenced in #2850. It will also serve as a better platform for fixing any correctness issues.

The new evaluator will not be enabled by default.

The top of stack for this change is currently https://review.gerrithub.io/c/cue-lang/cue/+/1174341 (there are many changes below it that have already been submitted). We will update the issue description with more details and better links shortly.

This adds functionality to open a Mermaid graph visualizing the state in a browser. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I0b59815069bffa4c66eeaac1612f955017ab8e46

Whether a struct is a definition should be propagated up. Adds tests and logic. As a consequence, some nodes that were marked as embedding only before, are now marked as a embedding as well as definition. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I4d97a4087734719471588f0b39561fbbca8f53b4

We will first implement the new evaluator without support for disjunctions. This change excludes such tests by examining the AST. Some additional tests that indirectly use disjunctions are explicitly excluded. Moved todoAlpha to within the test to facilitate editors that can run a test in place. This allows editing the list and running the file without having to move the cursor around. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I838745476fa7ba1354772c2fbbe4197ba9af2713

Functions that are no longer used by the new evaluator are marked with the unreachableForDev assertion. This avoids accidentally mixing old and new evaluator, but also makes it easier to review which parts are called by the new evaluator and which not. Note that some functions that are now not marked may still be only partially used in follow up CLs using the OpContext.useDevVersion method. But we wanted to have these changes in before the new evaluator is added and in a separate CL, so that 1) these changes do not interfere with that CL 2) one can quickly see which parts are not called during the review. The panic should be uncommented once the new evaluator lands. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ic96098928c7a35a6e02c5929d2ea788a8ceafc85

Once a counter was decremented to zero, it is no longer allowed to be incremented. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I82e0883467babd474ae8aaecb729418365181929

Differentiate between the one-level closedness of the closed builtin and that of definitions. Keep track of whether nodes use ellipses or top values. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I561f813b8384af7eccdfbe2d22900037b13d1229

Especially if other nodes are still running, it is normal that their counters will not be zero. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ice2bf915dcf4d30a0c439103caf804c2262c14b7

This does not yet implement disjunctions. Much of the specific code from the old evaluator is shared with the new evaluator. It is mostly the top-level control that is reimplemented. The new evaluator is based on the new scheduler and the new closedness implementation. We will describe the function of each new file below, with more details in the file itself. conjuncts.go: This file take adt.Expr and adt.Value and either stores the corresponding value, if present, in a Vertex directly or otherwise schedules a task in the scheduler for later evaluation. tasks.go: This file implements the tasks corresponding to the various adt.Expr expressions needed to evaluate them. These are scheduled by the code in conjuncts.go states.go: This file adds more of the low-level state logic around the various properties a CUE node can achieve. These state map to the low-level scheduler, which is CUE agnostic. unify.go: This file contains the high-level evaluation code that kicks off the evaluation process, including the initialization of a scheduler for each node. The analogous file for the old evaluator is eval.go. Tests: Some of the test results are different between the old and new evaluator. In this case, the txtar files will contain both an out/evalalpha file for the new evaluator, the original out/alpha file for the old evaluator, and a diff file for the diffed results. If the changes were an improvement, this is described in the diff/explanation file. Otherwise, there is a diff/todo/pX, where X is the priority of the fix, with an explanation of what still needs to be done. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ia0c5ad71cfdc7777b29f0aafd768da199844b710

This adds functionality to open a Mermaid graph visualizing the state in a browser. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I0b59815069bffa4c66eeaac1612f955017ab8e46 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1174002 TryBot-Result: CUEcueckoo <cueckoo@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Whether a struct is a definition should be propagated up. Adds tests and logic. As a consequence, some nodes that were marked as embedding only before, are now marked as a embedding as well as definition. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I4d97a4087734719471588f0b39561fbbca8f53b4 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1174003 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@gmail.com> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

We will first implement the new evaluator without support for disjunctions. This change excludes such tests by examining the AST. Some additional tests that indirectly use disjunctions are explicitly excluded. Moved todoAlpha to within the test to facilitate editors that can run a test in place. This allows editing the list and running the file without having to move the cursor around. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I838745476fa7ba1354772c2fbbe4197ba9af2713 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1174004 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@gmail.com> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Functions that are no longer used by the new evaluator are marked with the unreachableForDev assertion. This avoids accidentally mixing old and new evaluator, but also makes it easier to review which parts are called by the new evaluator and which not. Note that some functions that are now not marked may still be only partially used in follow up CLs using the OpContext.useDevVersion method. But we wanted to have these changes in before the new evaluator is added and in a separate CL, so that 1) these changes do not interfere with that CL 2) one can quickly see which parts are not called during the review. The panic should be uncommented once the new evaluator lands. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ic96098928c7a35a6e02c5929d2ea788a8ceafc85 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1174006 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@gmail.com> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Once a counter was decremented to zero, it is no longer allowed to be incremented. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I82e0883467babd474ae8aaecb729418365181929 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1174013 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@gmail.com>

Differentiate between the one-level closedness of the closed builtin and that of definitions. Keep track of whether nodes use ellipses or top values. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I561f813b8384af7eccdfbe2d22900037b13d1229

Especially if other nodes are still running, it is normal that their counters will not be zero. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ice2bf915dcf4d30a0c439103caf804c2262c14b7

This does not yet implement disjunctions. Much of the specific code from the old evaluator is shared with the new evaluator. It is mostly the top-level control that is reimplemented. The new evaluator is based on the new scheduler and the new closedness implementation. We will describe the function of each new file below, with more details in the file itself. conjuncts.go: This file take adt.Expr and adt.Value and either stores the corresponding value, if present, in a Vertex directly or otherwise schedules a task in the scheduler for later evaluation. tasks.go: This file implements the tasks corresponding to the various adt.Expr expressions needed to evaluate them. These are scheduled by the code in conjuncts.go states.go: This file adds more of the low-level state logic around the various properties a CUE node can achieve. These state map to the low-level scheduler, which is CUE agnostic. unify.go: This file contains the high-level evaluation code that kicks off the evaluation process, including the initialization of a scheduler for each node. The analogous file for the old evaluator is eval.go. Tests: Some of the test results are different between the old and new evaluator. In this case, the txtar files will contain both an out/evalalpha file for the new evaluator, the original out/alpha file for the old evaluator, and a diff file for the diffed results. If the changes were an improvement, this is described in the diff/explanation file. Otherwise, there is a diff/todo/pX, where X is the priority of the fix, with an explanation of what still needs to be done. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ia0c5ad71cfdc7777b29f0aafd768da199844b710

The conjunct index was previously incorrectly computed. This was fine, as it was unused. The bug was exposed by the upcoming implementation of disjunctions. We put the fix in a separate CL to minimize diffs later. Testing of this fix is done by adding support to disjunctions. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I027ffae6bc3aba3ce419e179bd21570b159ae789

This fixes a bug in the API, where dereferencing caused Value.Dereference to be too eager. This changes test in elimination.txtar. The results are a bit better, but still wrong, so it seems. So no changes in the todos. The main change is that Vertex.lookup no longer fully dereferences. Dereferencing is now done in a bespoke manner at the call sites of lookup. Issue #3060 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I59f791e78213c3cdacdb8ad3b6ba829a73d2d6ca

The new evaluator computes closedness quite differently from the old one. This CL adapts the API to use the new data. Note that the data the new evaluator generates is considerably more convenient. That is why the logic is quite a bit simpler. The logic could probably be simplified more. Also note that HasEllipsis seems to be not computed correclty entirely. Although it seems that many tests improve if we add the check to isClosed or IsClosedStruct, there are some cases where this causes errors. This seems to be the case with one of the tests in TestAllows. As this only manifests itself when structure sharing is disabled, we just mark this test as todo and leave the investigation for later. Issue #3060 Issue #543 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I98e8c25e0680674e2aaa9f743a49b39920d7b266 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194080 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Now we have structure sharing, we need to ensure that Vertex values are dereferenced properly. Issue #3060 Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ied35aa7f7f08205bbdb54415d78e78f1b83c8b62 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194081 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

Recent changes were dereferencing was introduced elsewhere make this use unnecessary. Keep this in a separate CL to allow tracking possible bugs this introduces. Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Iffbbbb3bef513205a0f6a29571bc6c6a37692bb1

This fixes a bug in the API, where dereferencing caused Value.Dereference to be too eager. This changes test in elimination.txtar. The results are a bit better, but still wrong, so it seems. So no changes in the todos. The main change is that Vertex.lookup no longer fully dereferences. Dereferencing is now done in a bespoke manner at the call sites of lookup. Issue #3060 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I59f791e78213c3cdacdb8ad3b6ba829a73d2d6ca

Recent changes were dereferencing was introduced elsewhere make this use unnecessary. Keep this in a separate CL to allow tracking possible bugs this introduces. Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Iffbbbb3bef513205a0f6a29571bc6c6a37692bb1 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194088 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

This fixes a bug in the API, where dereferencing caused Value.Dereference to be too eager. This changes test in elimination.txtar. The results are a bit better, but still wrong, so it seems. So no changes in the todos. The main change is that Vertex.lookup no longer fully dereferences. Dereferencing is now done in a bespoke manner at the call sites of lookup. Issue #3060 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I59f791e78213c3cdacdb8ad3b6ba829a73d2d6ca Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194104 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

To reduce the otherwise large number of diffs, we filter the "(and X more errors)" strings from error messages. Issue #3060 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I47c140f04dcbd78a2cd22fc7ca074f4e323dc843

To reduce the otherwise large number of diffs, we filter the "(and X more errors)" strings from error messages. Issue #3060 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I47c140f04dcbd78a2cd22fc7ca074f4e323dc843 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194196 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

Needed to unwrap ConjunctGroup. Although the evaluator would correctly unwrap the ConjunctGroup, it would reprocess the Comprehension, resulting in different semantics. This code ensures the Comprehension is unwrapped before evaluating the let. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I76c10e38dc9ebe244cb6f067f3b26ad95e0efbbb

This does not fix any tests, but it seems like a safe thing to do, as this was the source of various bugs. Also, ultimately, we probably want to move back to a real adt again, in which case all values should be accessible only through methods. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: If5c0a9d11450b8d4b38c50f9be52edab282ccc95

Needed to unwrap ConjunctGroup. Although the evaluator would correctly unwrap the ConjunctGroup, it would reprocess the Comprehension, resulting in different semantics. This code ensures the Comprehension is unwrapped before evaluating the let. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I76c10e38dc9ebe244cb6f067f3b26ad95e0efbbb Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194415 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

This does not fix any tests, but it seems like a safe thing to do, as this was the source of various bugs. Also, ultimately, we probably want to move back to a real adt again, in which case all values should be accessible only through methods. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: If5c0a9d11450b8d4b38c50f9be52edab282ccc95

This causes some more ConjunctGroup unwrapping, which benefits performance. This also fixes a let-related bug in export. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I36012f66c1f1930d75e552286f0af5fb3aab3523

Do some more ConjunctGroup unwrapping. This benefits performance and also fixes a let-related bug in export. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I36012f66c1f1930d75e552286f0af5fb3aab3523

This does not seem to change anything, but it seems that this is strictly a better thing to do and could prevent bugs down the line. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I3b3673be258fd1d0ddfe7788531fbde9e170cf15

This does not fix any tests, but it seems like a safe thing to do, as this was the source of various bugs. Also, ultimately, we probably want to move back to a real adt again, in which case all values should be accessible only through methods. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: If5c0a9d11450b8d4b38c50f9be52edab282ccc95 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194418 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Do some more ConjunctGroup unwrapping. This benefits performance and also fixes a let-related bug in export. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I36012f66c1f1930d75e552286f0af5fb3aab3523 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194439 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

This does not seem to change anything, but it seems that this is strictly a better thing to do and could prevent bugs down the line. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I3b3673be258fd1d0ddfe7788531fbde9e170cf15 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194443 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

When iterating over arcs, one now has to dereference the value to use it. The CUE API does this, but since the test used the low-level API, it now needs to be done manually. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Idda917c057013619db8cd37a182f41a6f0765571

In a previous fix we posponed the dereferencing of a value, because we needed the non-dereferenced value of the ArcType. As it turns out, we also need the non-dereferenced value for the docs and attributes. This change fixes that. Note that the test has some modifications for a debug testing. We leave this in for convenience down the line. We leave the snippet itself to get an idea of the reducer that was used to fix the code. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I59c97bfdb53918cd83b88be23a3a4bc5391fdb6f

When iterating over arcs, one now has to dereference the value to use it. The CUE API does this, but since the test used the low-level API, it now needs to be done manually. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Idda917c057013619db8cd37a182f41a6f0765571 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194465 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

In a previous fix we posponed the dereferencing of a value, because we needed the non-dereferenced value of the ArcType. As it turns out, we also need the non-dereferenced value for the docs and attributes. This change fixes that. Note that the test has some modifications for a debug testing. We leave this in for convenience down the line. We leave the snippet itself to get an idea of the reducer that was used to fix the code. Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I59c97bfdb53918cd83b88be23a3a4bc5391fdb6f Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194651 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

myitcv added the FeatureRequest New feature or request label Feb 29, 2024

myitcv mentioned this issue Feb 29, 2024

evaluator: enable use of new evaluator via CUE_EXPERIMENT #2886

Closed

myitcv added the evaluator label Feb 29, 2024

github-project-automation bot added this to Evaluator Roadmap Feb 29, 2024

github-project-automation bot moved this to Backlog in Evaluator Roadmap Feb 29, 2024

myitcv moved this from Backlog to In progress in Evaluator Roadmap Feb 29, 2024

myitcv assigned mpvl Feb 29, 2024

This was referenced Feb 29, 2024

evaluator: enable re-use buffers #2887

Open

evaluator: bring error messages back up to par with the old evaluator #2890

Open

evaluator: improve error messages with respect to the old evaluator #2891

Open

evaluator: specifying the order of fields #2892

Open

mpvl mentioned this issue Feb 29, 2024

Performance #2850

Open

myitcv mentioned this issue Feb 29, 2024

evaluator: take advantage of disjunction elements being mutually exclusive #2893

Open

mvdan moved this from v0.9.0-alpha.5 to v0.9.0-rc.1 in Release v0.9 May 14, 2024

mvdan moved this from v0.9.0-rc.1 to v0.9.0 in Release v0.9 May 31, 2024

mvdan removed this from Release v0.9 Jun 5, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

evaluator: implement new evaluator as the basis for performance and other improvements #2884

evaluator: implement new evaluator as the basis for performance and other improvements #2884

myitcv commented Feb 29, 2024

evaluator: implement new evaluator as the basis for performance and other improvements #2884

evaluator: implement new evaluator as the basis for performance and other improvements #2884

Comments

myitcv commented Feb 29, 2024