@@ -8,7 +8,10 @@ use vortex_error::VortexResult;
88use vortex_utils:: aliases:: hash_map:: HashMap ;
99use vortex_utils:: aliases:: hash_set:: HashSet ;
1010
11+ use crate :: expr:: BoundExpression ;
12+ use crate :: expr:: ExactBoundExpr ;
1113use crate :: expr:: Expression ;
14+ use crate :: expr:: traversal:: Node ;
1215use crate :: expr:: traversal:: NodeExt ;
1316use crate :: expr:: traversal:: NodeVisitor ;
1417use crate :: expr:: traversal:: TraversalOrder ;
@@ -17,28 +20,38 @@ pub trait Annotation: Clone + Hash + Eq {}
1720
1821impl < A > Annotation for A where A : Clone + Hash + Eq { }
1922
20- pub trait AnnotationFn : Fn ( & Expression ) -> Vec < Self :: Annotation > {
23+ pub trait AnnotationFn < N = Expression > : Fn ( & N ) -> Vec < Self :: Annotation > {
2124 type Annotation : Annotation ;
2225}
2326
24- impl < A , F > AnnotationFn for F
27+ impl < N , A , F > AnnotationFn < N > for F
2528where
2629 A : Annotation ,
27- F : Fn ( & Expression ) -> Vec < A > ,
30+ F : Fn ( & N ) -> Vec < A > ,
2831{
2932 type Annotation = A ;
3033}
3134
32- pub type Annotations < ' a , A > = HashMap < & ' a Expression , HashSet < A > > ;
35+ pub type Annotations < ' a , A , N = Expression > = HashMap < & ' a N , HashSet < A > > ;
36+
37+ /// Annotations keyed by bound-tree identity.
38+ ///
39+ /// Identity keys avoid structurally hashing every node's dtype. That matters when a bound root
40+ /// carries a lazy schema whose structural hash would deserialize every field.
41+ pub type BoundAnnotations < A > = HashMap < ExactBoundExpr , HashSet < A > > ;
3342
3443/// Walk the expression tree and annotate each expression with zero or more annotations.
3544///
3645/// Returns a map of each expression to all annotations that any of its descendent (child)
3746/// expressions are annotated with.
38- pub fn descendent_annotations < A : AnnotationFn > (
39- expr : & Expression ,
47+ pub fn descendent_annotations < ' a , N , A > (
48+ expr : & ' a N ,
4049 annotate : A ,
41- ) -> Annotations < ' _ , A :: Annotation > {
50+ ) -> Annotations < ' a , A :: Annotation , N >
51+ where
52+ N : Node + Eq + Hash ,
53+ A : AnnotationFn < N > ,
54+ {
4255 let mut visitor = AnnotationVisitor {
4356 annotations : Default :: default ( ) ,
4457 annotate,
@@ -53,10 +66,11 @@ pub fn descendent_annotations<A: AnnotationFn>(
5366///
5467/// Returns a map of each expression to all annotations. Annotations of
5568/// children are not propagated to parents.
56- pub fn direct_annotations < A : AnnotationFn > (
57- expr : & Expression ,
58- annotate : A ,
59- ) -> Annotations < ' _ , A :: Annotation > {
69+ pub fn direct_annotations < ' a , N , A > ( expr : & ' a N , annotate : A ) -> Annotations < ' a , A :: Annotation , N >
70+ where
71+ N : Node + Eq + Hash ,
72+ A : AnnotationFn < N > ,
73+ {
6074 let mut visitor = AnnotationVisitor {
6175 annotations : Default :: default ( ) ,
6276 annotate,
@@ -66,14 +80,66 @@ pub fn direct_annotations<A: AnnotationFn>(
6680 visitor. annotations
6781}
6882
69- struct AnnotationVisitor < ' a , A : AnnotationFn > {
70- annotations : Annotations < ' a , A :: Annotation > ,
83+ /// Annotate a bound expression and propagate each annotation to its ancestors.
84+ ///
85+ /// Unlike [`descendent_annotations`], this uses [`ExactBoundExpr`] keys to preserve the cheap
86+ /// identity semantics of an already-bound tree.
87+ pub fn descendent_bound_annotations < A > (
88+ expr : & BoundExpression ,
89+ annotate : A ,
90+ ) -> BoundAnnotations < A :: Annotation >
91+ where
92+ A : AnnotationFn < BoundExpression > ,
93+ {
94+ bound_annotations ( expr, annotate, true )
95+ }
96+
97+ /// Annotate each bound-expression node without propagating annotations to its ancestors.
98+ ///
99+ /// The returned map uses [`ExactBoundExpr`] keys so lookups do not structurally hash node dtypes.
100+ pub fn direct_bound_annotations < A > (
101+ expr : & BoundExpression ,
102+ annotate : A ,
103+ ) -> BoundAnnotations < A :: Annotation >
104+ where
105+ A : AnnotationFn < BoundExpression > ,
106+ {
107+ bound_annotations ( expr, annotate, false )
108+ }
109+
110+ fn bound_annotations < A > (
111+ expr : & BoundExpression ,
112+ annotate : A ,
113+ propagate_up : bool ,
114+ ) -> BoundAnnotations < A :: Annotation >
115+ where
116+ A : AnnotationFn < BoundExpression > ,
117+ {
118+ let mut visitor = BoundAnnotationVisitor {
119+ annotations : Default :: default ( ) ,
120+ annotate,
121+ propagate_up,
122+ } ;
123+ expr. accept ( & mut visitor) . vortex_expect ( "Infallible" ) ;
124+ visitor. annotations
125+ }
126+
127+ struct AnnotationVisitor < ' a , N , A >
128+ where
129+ N : Node + Eq + Hash ,
130+ A : AnnotationFn < N > ,
131+ {
132+ annotations : Annotations < ' a , A :: Annotation , N > ,
71133 annotate : A ,
72134 propagate_up : bool ,
73135}
74136
75- impl < ' a , A : AnnotationFn > NodeVisitor < ' a > for AnnotationVisitor < ' a , A > {
76- type NodeTy = Expression ;
137+ impl < ' a , N , A > NodeVisitor < ' a > for AnnotationVisitor < ' a , N , A >
138+ where
139+ N : Node + Eq + Hash ,
140+ A : AnnotationFn < N > ,
141+ {
142+ type NodeTy = N ;
77143
78144 fn visit_down ( & mut self , node : & ' a Self :: NodeTy ) -> VortexResult < TraversalOrder > {
79145 let annotations = ( self . annotate ) ( node) ;
@@ -89,20 +155,74 @@ impl<'a, A: AnnotationFn> NodeVisitor<'a> for AnnotationVisitor<'a, A> {
89155 }
90156 }
91157
92- fn visit_up ( & mut self , node : & ' a Expression ) -> VortexResult < TraversalOrder > {
158+ fn visit_up ( & mut self , node : & ' a N ) -> VortexResult < TraversalOrder > {
93159 if !self . propagate_up {
94160 return Ok ( TraversalOrder :: Continue ) ;
95161 }
162+ let child_annotations = node. iter_children ( |children| {
163+ children
164+ . filter_map ( |child| self . annotations . get ( child) . cloned ( ) )
165+ . collect :: < Vec < _ > > ( )
166+ } ) ;
167+
168+ let annotations = self . annotations . entry ( node) . or_default ( ) ;
169+ child_annotations
170+ . into_iter ( )
171+ . for_each ( |ps| annotations. extend ( ps. iter ( ) . cloned ( ) ) ) ;
172+
173+ Ok ( TraversalOrder :: Continue )
174+ }
175+ }
176+
177+ struct BoundAnnotationVisitor < A >
178+ where
179+ A : AnnotationFn < BoundExpression > ,
180+ {
181+ annotations : BoundAnnotations < A :: Annotation > ,
182+ annotate : A ,
183+ propagate_up : bool ,
184+ }
185+
186+ impl < ' a , A > NodeVisitor < ' a > for BoundAnnotationVisitor < A >
187+ where
188+ A : AnnotationFn < BoundExpression > ,
189+ {
190+ type NodeTy = BoundExpression ;
191+
192+ fn visit_down ( & mut self , node : & ' a Self :: NodeTy ) -> VortexResult < TraversalOrder > {
193+ let annotations = ( self . annotate ) ( node) ;
194+ if annotations. is_empty ( ) {
195+ return Ok ( TraversalOrder :: Continue ) ;
196+ }
197+
198+ self . annotations
199+ . entry ( ExactBoundExpr ( node. clone ( ) ) )
200+ . or_default ( )
201+ . extend ( annotations) ;
202+ Ok ( TraversalOrder :: Skip )
203+ }
204+
205+ fn visit_up ( & mut self , node : & ' a Self :: NodeTy ) -> VortexResult < TraversalOrder > {
206+ if !self . propagate_up {
207+ return Ok ( TraversalOrder :: Continue ) ;
208+ }
209+
96210 let child_annotations = node
97211 . children ( )
98212 . iter ( )
99- . filter_map ( |c| self . annotations . get ( c) . cloned ( ) )
213+ . filter_map ( |child| {
214+ self . annotations
215+ . get ( & ExactBoundExpr ( child. clone ( ) ) )
216+ . cloned ( )
217+ } )
100218 . collect :: < Vec < _ > > ( ) ;
101-
102- let annotations = self . annotations . entry ( node) . or_default ( ) ;
219+ let annotations = self
220+ . annotations
221+ . entry ( ExactBoundExpr ( node. clone ( ) ) )
222+ . or_default ( ) ;
103223 child_annotations
104224 . into_iter ( )
105- . for_each ( |ps | annotations. extend ( ps . iter ( ) . cloned ( ) ) ) ;
225+ . for_each ( |child | annotations. extend ( child ) ) ;
106226
107227 Ok ( TraversalOrder :: Continue )
108228 }
0 commit comments