Additional tree-morph selection strategies

lixitrixi commented 1 week ago

WIP adding useful out-of-the-box selection strategies for tree-morph.

I encourage people to comment ideas that might be useful! See helpers.rs for a current TODO list.

github-actions[bot] commented 1 week ago

Code and Documentation Coverage Report

Documentation Coverage

Click to view documentation coverage for this PR

``` +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | crates/tree_morph/src/commands.rs | 1 | 100.0% | 0 | 0.0% | | crates/tree_morph/src/helpers.rs | 1 | 50.0% | 0 | 0.0% | | crates/tree_morph/src/lib.rs | 1 | 100.0% | 1 | 100.0% | | crates/tree_morph/src/reduce.rs | 2 | 100.0% | 0 | 0.0% | | crates/tree_morph/src/reduction.rs | 0 | 0.0% | 0 | 0.0% | | crates/tree_morph/src/rule.rs | 0 | 0.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 5 | 50.0% | 1 | 33.3% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | crates/conjure_macros/src/lib.rs | 2 | 66.7% | 1 | 33.3% | +-------------------------------------+------------+------------+------------+------------+ | Total | 2 | 66.7% | 1 | 33.3% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | ...m_compatability_macro/src/lib.rs | 2 | 100.0% | 1 | 50.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 2 | 100.0% | 1 | 50.0% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | solvers/kissat/src/lib.rs | 0 | 0.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 0 | 0.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | solvers/minion/src/ast.rs | 11 | 11.0% | 0 | 0.0% | | solvers/minion/src/error.rs | 8 | 100.0% | 0 | 0.0% | | solvers/minion/src/lib.rs | 1 | 100.0% | 1 | 100.0% | | solvers/minion/src/run.rs | 2 | 100.0% | 1 | 100.0% | | solvers/minion/src/wrappers.rs | 1 | 100.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 23 | 20.5% | 2 | 11.8% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | crates/conjure_core/src/ast/atom.rs | 1 | 33.3% | 0 | 0.0% | | .../conjure_core/src/ast/domains.rs | 0 | 0.0% | 0 | 0.0% | | ...jure_core/src/ast/expressions.rs | 27 | 93.1% | 0 | 0.0% | | ...conjure_core/src/ast/literals.rs | 1 | 33.3% | 0 | 0.0% | | crates/conjure_core/src/ast/mod.rs | 0 | 0.0% | 0 | 0.0% | | ...ure_core/src/ast/symbol_table.rs | 0 | 0.0% | 0 | 0.0% | | ...es/conjure_core/src/ast/types.rs | 0 | 0.0% | 0 | 0.0% | | ...onjure_core/src/ast/variables.rs | 1 | 50.0% | 0 | 0.0% | | crates/conjure_core/src/bug.rs | 1 | 50.0% | 1 | 50.0% | | crates/conjure_core/src/context.rs | 0 | 0.0% | 0 | 0.0% | | crates/conjure_core/src/error.rs | 1 | 14.3% | 0 | 0.0% | | crates/conjure_core/src/lib.rs | 0 | 0.0% | 0 | 0.0% | | crates/conjure_core/src/metadata.rs | 0 | 0.0% | 0 | 0.0% | | crates/conjure_core/src/model.rs | 3 | 17.6% | 0 | 0.0% | | ...core/src/parse/example_models.rs | 2 | 100.0% | 0 | 0.0% | | ...es/conjure_core/src/parse/mod.rs | 0 | 0.0% | 0 | 0.0% | | ...re_core/src/parse/parse_model.rs | 0 | 0.0% | 0 | 0.0% | | ...jure_core/src/rule_engine/mod.rs | 5 | 71.4% | 5 | 71.4% | | ...src/rule_engine/resolve_rules.rs | 3 | 100.0% | 0 | 0.0% | | ..._core/src/rule_engine/rewrite.rs | 2 | 66.7% | 0 | 0.0% | | ...ure_core/src/rule_engine/rule.rs | 3 | 25.0% | 1 | 100.0% | | ...core/src/rule_engine/rule_set.rs | 4 | 100.0% | 0 | 0.0% | | ...njure_core/src/rules/constant.rs | 1 | 100.0% | 0 | 0.0% | | ...es/conjure_core/src/rules/mod.rs | 1 | 100.0% | 0 | 0.0% | | ...re/src/solver/adaptors/kissat.rs | 1 | 100.0% | 0 | 0.0% | | ...re/src/solver/adaptors/minion.rs | 1 | 100.0% | 0 | 0.0% | | ..._core/src/solver/adaptors/mod.rs | 1 | 100.0% | 0 | 0.0% | | ...s/conjure_core/src/solver/mod.rs | 14 | 33.3% | 1 | 4.2% | | ...ore/src/solver/model_modifier.rs | 7 | 70.0% | 0 | 0.0% | | ...onjure_core/src/solver/states.rs | 7 | 63.6% | 0 | 0.0% | | ...es/conjure_core/src/stats/mod.rs | 0 | 0.0% | 0 | 0.0% | | ...core/src/stats/rewriter_stats.rs | 1 | 20.0% | 0 | 0.0% | | ...e_core/src/stats/solver_stats.rs | 3 | 37.5% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 91 | 42.1% | 8 | 9.8% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | conjure_oxide/src/defaults.rs | 1 | 50.0% | 0 | 0.0% | | conjure_oxide/src/find_conjure.rs | 1 | 50.0% | 0 | 0.0% | | conjure_oxide/src/lib.rs | 0 | 0.0% | 0 | 0.0% | | conjure_oxide/src/utils/conjure.rs | 0 | 0.0% | 0 | 0.0% | | conjure_oxide/src/utils/json.rs | 2 | 66.7% | 0 | 0.0% | | conjure_oxide/src/utils/misc.rs | 0 | 0.0% | 0 | 0.0% | | conjure_oxide/src/utils/mod.rs | 0 | 0.0% | 0 | 0.0% | | conjure_oxide/src/utils/testing.rs | 0 | 0.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 4 | 12.9% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ ```

Click to view documentation coverage for main

``` +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | crates/conjure_macros/src/lib.rs | 2 | 66.7% | 1 | 33.3% | +-------------------------------------+------------+------------+------------+------------+ | Total | 2 | 66.7% | 1 | 33.3% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | ...m_compatability_macro/src/lib.rs | 2 | 100.0% | 1 | 50.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 2 | 100.0% | 1 | 50.0% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | crates/tree_morph/src/commands.rs | 1 | 100.0% | 0 | 0.0% | | crates/tree_morph/src/helpers.rs | 0 | 0.0% | 0 | 0.0% | | crates/tree_morph/src/lib.rs | 1 | 100.0% | 1 | 100.0% | | crates/tree_morph/src/reduce.rs | 2 | 100.0% | 0 | 0.0% | | crates/tree_morph/src/reduction.rs | 0 | 0.0% | 0 | 0.0% | | crates/tree_morph/src/rule.rs | 0 | 0.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 4 | 40.0% | 1 | 33.3% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | solvers/kissat/src/lib.rs | 0 | 0.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 0 | 0.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | solvers/minion/src/ast.rs | 11 | 11.0% | 0 | 0.0% | | solvers/minion/src/error.rs | 8 | 100.0% | 0 | 0.0% | | solvers/minion/src/lib.rs | 1 | 100.0% | 1 | 100.0% | | solvers/minion/src/run.rs | 2 | 100.0% | 1 | 100.0% | | solvers/minion/src/wrappers.rs | 1 | 100.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 23 | 20.5% | 2 | 11.8% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | crates/conjure_core/src/ast/atom.rs | 1 | 33.3% | 0 | 0.0% | | .../conjure_core/src/ast/domains.rs | 0 | 0.0% | 0 | 0.0% | | ...jure_core/src/ast/expressions.rs | 27 | 93.1% | 0 | 0.0% | | ...conjure_core/src/ast/literals.rs | 1 | 33.3% | 0 | 0.0% | | crates/conjure_core/src/ast/mod.rs | 0 | 0.0% | 0 | 0.0% | | ...ure_core/src/ast/symbol_table.rs | 0 | 0.0% | 0 | 0.0% | | ...es/conjure_core/src/ast/types.rs | 0 | 0.0% | 0 | 0.0% | | ...onjure_core/src/ast/variables.rs | 1 | 50.0% | 0 | 0.0% | | crates/conjure_core/src/bug.rs | 1 | 50.0% | 1 | 50.0% | | crates/conjure_core/src/context.rs | 0 | 0.0% | 0 | 0.0% | | crates/conjure_core/src/error.rs | 1 | 14.3% | 0 | 0.0% | | crates/conjure_core/src/lib.rs | 0 | 0.0% | 0 | 0.0% | | crates/conjure_core/src/metadata.rs | 0 | 0.0% | 0 | 0.0% | | crates/conjure_core/src/model.rs | 3 | 17.6% | 0 | 0.0% | | ...core/src/parse/example_models.rs | 2 | 100.0% | 0 | 0.0% | | ...es/conjure_core/src/parse/mod.rs | 0 | 0.0% | 0 | 0.0% | | ...re_core/src/parse/parse_model.rs | 0 | 0.0% | 0 | 0.0% | | ...jure_core/src/rule_engine/mod.rs | 5 | 71.4% | 5 | 71.4% | | ...src/rule_engine/resolve_rules.rs | 3 | 100.0% | 0 | 0.0% | | ..._core/src/rule_engine/rewrite.rs | 2 | 66.7% | 0 | 0.0% | | ...ure_core/src/rule_engine/rule.rs | 3 | 25.0% | 1 | 100.0% | | ...core/src/rule_engine/rule_set.rs | 4 | 100.0% | 0 | 0.0% | | ...njure_core/src/rules/constant.rs | 1 | 100.0% | 0 | 0.0% | | ...es/conjure_core/src/rules/mod.rs | 1 | 100.0% | 0 | 0.0% | | ...re/src/solver/adaptors/kissat.rs | 1 | 100.0% | 0 | 0.0% | | ...re/src/solver/adaptors/minion.rs | 1 | 100.0% | 0 | 0.0% | | ..._core/src/solver/adaptors/mod.rs | 1 | 100.0% | 0 | 0.0% | | ...s/conjure_core/src/solver/mod.rs | 14 | 33.3% | 1 | 4.2% | | ...ore/src/solver/model_modifier.rs | 7 | 70.0% | 0 | 0.0% | | ...onjure_core/src/solver/states.rs | 7 | 63.6% | 0 | 0.0% | | ...es/conjure_core/src/stats/mod.rs | 0 | 0.0% | 0 | 0.0% | | ...core/src/stats/rewriter_stats.rs | 1 | 20.0% | 0 | 0.0% | | ...e_core/src/stats/solver_stats.rs | 3 | 37.5% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 91 | 42.1% | 8 | 9.8% | +-------------------------------------+------------+------------+------------+------------+ +-------------------------------------+------------+------------+------------+------------+ | File | Documented | Percentage | Examples | Percentage | +-------------------------------------+------------+------------+------------+------------+ | conjure_oxide/src/defaults.rs | 1 | 50.0% | 0 | 0.0% | | conjure_oxide/src/find_conjure.rs | 1 | 50.0% | 0 | 0.0% | | conjure_oxide/src/lib.rs | 0 | 0.0% | 0 | 0.0% | | conjure_oxide/src/utils/conjure.rs | 0 | 0.0% | 0 | 0.0% | | conjure_oxide/src/utils/json.rs | 2 | 66.7% | 0 | 0.0% | | conjure_oxide/src/utils/misc.rs | 0 | 0.0% | 0 | 0.0% | | conjure_oxide/src/utils/mod.rs | 0 | 0.0% | 0 | 0.0% | | conjure_oxide/src/utils/testing.rs | 0 | 0.0% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ | Total | 4 | 12.9% | 0 | 0.0% | +-------------------------------------+------------+------------+------------+------------+ ```

Code Coverage Summary

This PR: Detailed Report

  lines......: 73.2% (3633 of 4964 lines)
  functions..: 59.0% (372 of 630 functions)
  branches...: no data found

Main: Detailed Report

  lines......: 73.1% (3617 of 4948 lines)
  functions..: 59.2% (371 of 627 functions)
  branches...: no data found

Coverage Main & PR Coverage Change

Lines coverage changed by 0.10% and covered lines changed by 16
Functions coverage changed by -0.20% and covered lines changed by 1
Branches... coverage: No comparison data available

ozgurakgun commented 1 week ago

I like everything on the list!

ozgurakgun commented 6 days ago

Continuing my tradition of writing these in random places...

For tree-morph, I suggest we take an existing test case and see how far uniplate can go. For example:

Take this test: https://github.com/conjure-cp/conjure-oxide/blob/ff378f2a13013be119a3cd085122e714855e8034/crates/tree_morph/tests/add_mul.rs

Instead of rewriting Expr directly say you had a Stmt type that contained a version string and a single expression. Do the rest of the rules continue working on the Stmt type without any changes?
Change Stmt to contain an Option - how about now?
Change the Stmt to contain a Vec - same test.
Create a Program type which has a Vec in it. Change the rules to work on Exprs, but also create an entire new Program object, optionally. This is our in-context rewriting setup in Oxide. tree-morph should be take as input the rule database, a function that implements "adding" a Program object on top of an existing Program object and handle the rest.

Very happy to expand on this. I think tree-morph needs a good design document.

@YehorBoiar @lixitrixi @niklasdewally @TAswan

niklasdewally commented 6 days ago

Continuing my tradition of writing these in random places...

For tree-morph, I suggest we take an existing test case and see how far uniplate can go. For example:

Take this test: https://github.com/conjure-cp/conjure-oxide/blob/ff378f2a13013be119a3cd085122e714855e8034/crates/tree_morph/tests/add_mul.rs

Instead of rewriting Expr directly say you had a Stmt type that contained a version string and a single expression. Do the rest of the rules continue working on the Stmt type without any changes?

Change Stmt to contain an Option - how about now?

Change the Stmt to contain a Vec - same test.

Create a Program type which has a Vec in it. Change the rules to work on Exprs, but also create an entire new Program object, optionally. This is our in-context rewriting setup in Oxide. tree-morph should be take as input the rule database, a function that implements "adding" a Program object on top of an existing Program object and handle the rest.

Very happy to expand on this. I think tree-morph needs a good design document.

@YehorBoiar @lixitrixi @niklasdewally @TAswan

i havent had much chance to test the limits of biplate yet so it would be cool to see how far we can push it!

feel free to dump any problems you run into in issues in the uniplate repo :)

conjure-cp / conjure-oxide