graphrecords_query/optimizer/
builtins.rs

1use super::{
2    Direction, MatchInputs, OperationInputs, Optimizer, OptimizerBuilder, Pattern, PhaseLabel,
3    Rule, capture, matching, rule,
4};
5#[cfg(feature = "dynamic")]
6use crate::dynamic::register_dyn_builtins;
7use crate::{
8    Arity, Bare, ElementShape, Indexed, Mask, Multiple, Operand, Ordered, Unordered,
9    element::{ElementTransition, Preserving},
10    operands::{BoolMaskOperand, OperandHandle},
11    operations::{
12        Apply, DiscardIndexOperation, DiscardValueOperation, ElementKernel, NotOperation,
13        OperationContext, TakeOperation,
14    },
15};
16use graphrecords_core::graphrecord::{EdgeIndex, NodeIndex};
17use std::sync::OnceLock;
18
19#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, PhaseLabel)]
20pub enum BuiltinPhase {
21    Source,
22    Simplify,
23    Reorder,
24    Pushdown,
25    Cse,
26    Limit,
27    Graph,
28}
29
30pub struct EliminateDoubleNegation;
31
32fn eliminate_double_negation<O: Apply<NotOperation, Output = O>>() -> impl Rule<O> {
33    matching::<OperationContext<_, NotOperation>, _>((matching::<
34        OperationContext<_, NotOperation>,
35        _,
36    >((capture(),)),))
37    .rewrite(|((inner,),), _| Some(inner))
38}
39
40pub struct PushDownTake;
41
42fn push_down_take<S, C, P>() -> impl Rule<OperandHandle<P::OutShape, C>>
43where
44    S: ElementShape + ElementTransition<P::OutShape, Preserving>,
45    C: Arity,
46    P: ElementKernel<S, Emission = Preserving>
47        + for<'a> OperationInputs<Inputs<'a, OperandHandle<S, C>> = (&'a OperandHandle<S, C>,)>,
48    OperandHandle<S, C>: Apply<TakeOperation, Output = OperandHandle<S, C>>,
49    OperandHandle<P::OutShape, C>: Apply<TakeOperation, Output = OperandHandle<P::OutShape, C>>,
50{
51    rule(
52        |outer: &OperationContext<OperandHandle<P::OutShape, C>, TakeOperation>,
53         _|
54         -> Option<OperandHandle<P::OutShape, C>> {
55            let (operand,) = MatchInputs::inputs(outer);
56            let inner = operand
57                .as_plan_node()
58                .downcast::<OperationContext<OperandHandle<S, C>, P>>()?;
59
60            if !inner.operation().allows_limit_pushdown() {
61                return None;
62            }
63
64            let (input,) = MatchInputs::inputs(inner);
65            let taken: OperandHandle<S, C> = Operand::new(OperationContext::new(
66                input.clone(),
67                outer.operation().clone(),
68            ));
69
70            let pushed =
71                OperationContext::<OperandHandle<S, C>, P>::new(taken, inner.operation().clone());
72
73            Some(Operand::new(pushed))
74        },
75    )
76}
77
78impl Optimizer {
79    #[must_use]
80    pub fn builtin() -> Self {
81        let mut builder = Self::builder();
82
83        register_builtins(&mut builder);
84
85        #[cfg(feature = "dynamic")]
86        register_dyn_builtins(&mut builder);
87
88        #[allow(clippy::missing_panics_doc)]
89        builder
90            .build()
91            .expect("Builtin phases and rules must form a valid optimizer")
92    }
93
94    #[must_use]
95    pub fn shared_builtin() -> &'static Self {
96        static BUILTIN: OnceLock<Optimizer> = OnceLock::new();
97
98        BUILTIN.get_or_init(Self::builtin)
99    }
100}
101
102pub fn register_builtins(builder: &mut OptimizerBuilder) {
103    use BuiltinPhase::{Cse, Graph, Limit, Pushdown, Reorder, Simplify, Source};
104
105    builder
106        .add_phase(Source)
107        .direction(Direction::TopDown)
108        .fixpoint();
109    builder
110        .add_phase(Simplify)
111        .direction(Direction::BottomUp)
112        .fixpoint()
113        .after(Source);
114    builder
115        .add_phase(Reorder)
116        .direction(Direction::BottomUp)
117        .fixpoint()
118        .after(Simplify);
119    builder
120        .add_phase(Pushdown)
121        .direction(Direction::TopDown)
122        .fixpoint()
123        .after(Reorder);
124    builder
125        .add_phase(Cse)
126        .direction(Direction::Manual)
127        .once()
128        .after(Pushdown);
129    builder
130        .add_phase(Limit)
131        .direction(Direction::TopDown)
132        .fixpoint()
133        .after(Cse);
134    builder
135        .add_phase(Graph)
136        .direction(Direction::BottomUp)
137        .fixpoint()
138        .after(Limit);
139
140    builder
141        .add_rule(
142            Simplify,
143            eliminate_double_negation::<BoolMaskOperand<NodeIndex, Unordered>>(),
144        )
145        .label::<EliminateDoubleNegation>();
146
147    builder
148        .add_rule(
149            Simplify,
150            eliminate_double_negation::<BoolMaskOperand<NodeIndex, Ordered>>(),
151        )
152        .label::<EliminateDoubleNegation>();
153
154    builder
155        .add_rule(
156            Simplify,
157            eliminate_double_negation::<BoolMaskOperand<EdgeIndex, Unordered>>(),
158        )
159        .label::<EliminateDoubleNegation>();
160
161    builder
162        .add_rule(
163            Simplify,
164            eliminate_double_negation::<BoolMaskOperand<EdgeIndex, Ordered>>(),
165        )
166        .label::<EliminateDoubleNegation>();
167
168    builder
169        .add_rule(
170            Limit,
171            push_down_take::<Indexed<NodeIndex, Mask>, Multiple<Ordered>, NotOperation>(),
172        )
173        .label::<PushDownTake>();
174
175    builder
176        .add_rule(
177            Limit,
178            push_down_take::<Indexed<EdgeIndex, Mask>, Multiple<Ordered>, NotOperation>(),
179        )
180        .label::<PushDownTake>();
181
182    builder
183        .add_rule(
184            Limit,
185            push_down_take::<Bare<Mask>, Multiple<Ordered>, NotOperation>(),
186        )
187        .label::<PushDownTake>();
188
189    builder
190        .add_rule(
191            Limit,
192            push_down_take::<Indexed<NodeIndex, Mask>, Multiple<Ordered>, DiscardIndexOperation>(),
193        )
194        .label::<PushDownTake>();
195
196    builder
197        .add_rule(
198            Limit,
199            push_down_take::<Indexed<EdgeIndex, Mask>, Multiple<Ordered>, DiscardIndexOperation>(),
200        )
201        .label::<PushDownTake>();
202
203    builder
204        .add_rule(
205            Limit,
206            push_down_take::<Indexed<NodeIndex, Mask>, Multiple<Ordered>, DiscardValueOperation>(),
207        )
208        .label::<PushDownTake>();
209
210    builder
211        .add_rule(
212            Limit,
213            push_down_take::<Indexed<EdgeIndex, Mask>, Multiple<Ordered>, DiscardValueOperation>(),
214        )
215        .label::<PushDownTake>();
216}
graphrecords_query/optimizer/builtins.rs

graphrecords_query/optimizer/
builtins.rs
