1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//! Intarsia: A Cascades-Style Optimizer Framework
//!
//! Intarsia is an extensible optimizer framework for building property-aware,
//! cost-based optimizers in Rust. It combines the power of [egg]'s e-graphs with
//! cascades-style optimization and [ISLE] DSL integration for declarative rewrite rules.
//!
//! [egg]: https://docs.rs/egg/
//! [ISLE]: https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/isle/docs/language-reference.md
//!
//! # Key Features
//!
//! - **Property-Aware Optimization**: Track semantic properties (sorted, distributed, etc.)
//! through the optimization process
//! - **Cascades-Style Search**: Explore equivalent expressions and select optimal plans
//! - **ISLE Integration**: Write rewrite rules in a declarative DSL
//! - **Generic Framework**: Works with any language defined using egg's `define_language!` macro
//! - **Extensible Cost Model**: Define custom cost functions for your domain
//!
//! # Quick Start
//!
//! ## 1. Define Your Language
//!
//! ```rust,ignore
//! use egg::{define_language, Id};
//!
//! define_language! {
//! pub enum QueryLang {
//! "scan" = Scan(i64),
//! "filter" = Filter([Id; 2]),
//! "join" = Join([Id; 2]),
//! }
//! }
//! ```
//!
//! ## 2. Define Properties
//!
//! ```rust,ignore
//! use intarsia::Property;
//!
//! #[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd)]
//! enum QueryProperty {
//! Sorted,
//! Unsorted,
//! Bottom,
//! }
//!
//! impl Property for QueryProperty {
//! fn satisfies(&self, required: &Self) -> bool {
//! match required {
//! QueryProperty::Bottom => true,
//! QueryProperty::Unsorted => true,
//! QueryProperty::Sorted => matches!(self, QueryProperty::Sorted),
//! }
//! }
//!
//! fn bottom() -> Self {
//! QueryProperty::Bottom
//! }
//! }
//! ```
//!
//! ## 3. Implement Required Traits
//!
//! ```rust,ignore
//! use intarsia::{
//! PropertyAwareLanguage, CostFunction, ExplorerHooks,
//! SimpleCost, SimpleOptimizerFramework,
//! };
//!
//! impl PropertyAwareLanguage<QueryProperty> for QueryLang {
//! fn property_req(&self, child_index: usize) -> QueryProperty {
//! // Define property requirements for each operator
//! QueryProperty::Bottom
//! }
//! }
//!
//! type MyOptimizer = SimpleOptimizerFramework<QueryLang, QueryProperty>;
//!
//! impl CostFunction<QueryLang, QueryProperty, SimpleCost<QueryProperty>> for MyOptimizer {
//! fn compute_cost<F>(&self, node: &QueryLang, mut get_child_cost: F) -> SimpleCost<QueryProperty>
//! where
//! F: FnMut(egg::Id) -> SimpleCost<QueryProperty>,
//! {
//! // Compute cost based on operator and child costs
//! SimpleCost::simple(1)
//! }
//! }
//!
//! impl ExplorerHooks<QueryLang> for MyOptimizer {
//! fn explore(&mut self, id: egg::Id) -> Vec<egg::Id> {
//! // Apply rewrite rules (typically ISLE-generated)
//! vec![]
//! }
//! }
//! ```
//!
//! ## 4. Run Optimization
//!
//! ```rust,ignore
//! // Create optimizer
//! let mut optimizer = MyOptimizer::new(());
//!
//! // Add initial expression
//! let expr = /* build your expression */;
//! let root = optimizer.init(expr);
//!
//! // Run optimization
//! optimizer.run(root);
//!
//! // Extract best plan
//! let best_plan = optimizer.extract(root);
//! ```
//!
//! # ISLE Integration
//!
//! Use [`intarsia-build`] in your `build.rs` to compile ISLE rules:
//!
//! [`intarsia-build`]: https://docs.rs/intarsia-build/
//!
//! ```rust,ignore
//! // build.rs
//! fn main() -> Result<(), Box<dyn std::error::Error>> {
//! intarsia_build::compile_isle_auto()?;
//! Ok(())
//! }
//! ```
//!
//! Then use [`intarsia-macros`] to integrate the generated code:
//!
//! [`intarsia-macros`]: https://docs.rs/intarsia-macros/
//!
//! ```rust,ignore
//! use intarsia_macros::{isle_integration, isle_accessors};
//!
//! isle_integration!();
//!
//! impl rules::Context for MyOptimizer {
//! isle_accessors! {
//! Filter(extractor_filter, constructor_filter, 2);
//! Join(extractor_join, constructor_join, 2);
//! }
//! }
//! ```
//!
//! # Feature Flags
//!
//! - `build-helpers`: Re-exports build script utilities (from `intarsia-build`)
//!
//! # Further Reading
//!
//! - [Examples](https://github.com/sarahmorin/intarsia/tree/main/examples) - Database and boolean optimizers
//! - [Documentation](https://github.com/sarahmorin/intarsia/wiki) - Detailed guides and API reference