zrx_id/id/filter/candidates.rs
1// Copyright (c) 2025-2026 Zensical and contributors
2
3// SPDX-License-Identifier: MIT
4// All contributions are certified under the DCO
5
6// Permission is hereby granted, free of charge, to any person obtaining a copy
7// of this software and associated documentation files (the "Software"), to
8// deal in the Software without restriction, including without limitation the
9// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10// sell copies of the Software, and to permit persons to whom the Software is
11// furnished to do so, subject to the following conditions:
12
13// The above copyright notice and this permission notice shall be included in
14// all copies or substantial portions of the Software.
15
16// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18// FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE
19// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22// IN THE SOFTWARE.
23
24// ----------------------------------------------------------------------------
25
26//! Iterator over candidates.
27
28use slab::Slab;
29use std::iter::Peekable;
30
31use crate::id::matcher::matches::IntoIter;
32use crate::id::matcher::Matches;
33use crate::id::TryToId;
34
35use super::condition::Condition;
36use super::error::Result;
37use super::Filter;
38
39// ----------------------------------------------------------------------------
40// Structs
41// ----------------------------------------------------------------------------
42
43/// Iterator over candidates.
44pub struct Candidates<'a> {
45 /// Iterator over matches.
46 matches: Peekable<IntoIter>,
47 /// Condition set, built from expressions.
48 conditions: &'a Slab<Condition>,
49 /// Condition indices of negations.
50 negations: &'a [u32],
51 /// Condition term mappings.
52 mapping: &'a [u32],
53 /// Match set used during iteration.
54 workset: Matches,
55}
56
57// ----------------------------------------------------------------------------
58// Implementations
59// ----------------------------------------------------------------------------
60
61impl Filter {
62 /// Returns the indices of expressions that match the identifier.
63 ///
64 /// This method compares expressions part of the filter against the given
65 /// identifier, and returns an iterator over the indices of the expressions
66 /// that match. Note that the order of the returned indices corresponds to
67 /// the order in which the expressions were added to the filter.
68 ///
69 /// # Errors
70 ///
71 /// Returns [`Error::Matcher`][] if the identifier is invalid.
72 ///
73 /// [`Error::Matcher`]: crate::id::filter::Error::Matcher
74 ///
75 /// # Examples
76 ///
77 /// ```
78 /// # use std::error::Error;
79 /// # fn main() -> Result<(), Box<dyn Error>> {
80 /// use zrx_id::{selector, Expression, Filter, Id};
81 ///
82 /// // Create filter builder and insert expression
83 /// let mut builder = Filter::builder();
84 /// builder.insert(Expression::all(|expr| {
85 /// expr.with(selector!(location = "**/*.md")?)?
86 /// .with(selector!(provider = "file")?)
87 /// })?);
88 ///
89 /// // Create filter from builder
90 /// let filter = builder.build()?;
91 ///
92 /// // Create identifier and obtain candidate expressions
93 /// let id: Id = "zri:file:::docs:index.md:".parse()?;
94 /// for index in filter.candidates(&id)? {
95 /// println!("{index:?}");
96 /// }
97 /// # Ok(())
98 /// # }
99 /// ```
100 #[inline]
101 pub fn candidates<T>(&self, id: &T) -> Result<Candidates<'_>>
102 where
103 T: TryToId,
104 {
105 let matches = self.matcher.matches(id)?;
106 Ok(Candidates {
107 matches: matches.into_iter().peekable(),
108 conditions: &self.conditions,
109 negations: &self.negations,
110 mapping: &self.mapping,
111 workset: Matches::new(),
112 })
113 }
114}
115
116// ----------------------------------------------------------------------------
117// Trait implementations
118// ----------------------------------------------------------------------------
119
120impl Iterator for Candidates<'_> {
121 type Item = usize;
122
123 /// Returns the next candidate.
124 fn next(&mut self) -> Option<Self::Item> {
125 loop {
126 self.workset.clear();
127
128 // Retrieve the next match without consuming it, as we must first
129 // check if there're any conditions with negations that we need to
130 // process first, or whether the current match lies exactly within
131 // one of those negations
132 let opt = self.matches.peek().copied();
133
134 // Retrieve the index of the current condition for processing - if
135 // there's a match within the match set, use that to check if we
136 // should process the condition the match is a part of, or the
137 // next condition with a negation first
138 let check = if let Some(start) = opt {
139 let index = self.mapping[start];
140
141 // Either chose the current condition, or the condition that
142 // needs to be checked despite of any matches being present
143 let opt = self.negations.first().copied();
144 opt.filter(|&first| first <= index).map_or(index, |first| {
145 self.negations = &self.negations[1..];
146 first
147 })
148
149 // No more matches - in this case we need to process all remaining
150 // conditions that contain negations
151 } else if let Some(&first) = self.negations.first() {
152 self.negations = &self.negations[1..];
153 first
154
155 // No more conditions to check
156 } else {
157 return None;
158 };
159
160 // If there're matches, consume all matches that belong to the
161 // condition, and insert them into the working set of matches
162 if let Some(mut start) = opt {
163 // Do a backwards scan on the terms to find the index of the
164 // first term for the condition, to correctly assign matches
165 while start > 0 && self.mapping[start - 1] == check {
166 start -= 1;
167 }
168
169 // Next, consume all matches for the current condition, and
170 // add them to the working set of matches
171 while let Some(index) =
172 self.matches.next_if(|&index| self.mapping[index] == check)
173 {
174 self.workset.add(index - start);
175 }
176 }
177
178 // After consuming all matches for this condition, check whether
179 // it is satisfied - if not, continue with the next condition
180 let index = check as usize;
181 if self.conditions[index].satisfies(&self.workset) {
182 return Some(index);
183 }
184 }
185 }
186}
187
188// ----------------------------------------------------------------------------
189// Tests
190// ----------------------------------------------------------------------------
191
192#[cfg(test)]
193mod tests {
194
195 mod matches {
196 use crate::id::expression::Expression;
197 use crate::id::filter::{Filter, Result};
198 use crate::selector;
199
200 #[test]
201 fn handles_any() -> Result {
202 let mut builder = Filter::builder();
203 let _ = builder.insert(Expression::any(|expr| {
204 expr.with(selector!(location = "**/*.jpg")?)?
205 .with(selector!(location = "**/*.png")?)
206 })?);
207 let filter = builder.build()?;
208 for (id, check) in [
209 ("zri:file:::docs:image.jpg:", vec![0]),
210 ("zri:file:::docs:image.png:", vec![0]),
211 ("zri:file:::docs:image.gif:", vec![]),
212 ] {
213 assert_eq!(
214 filter.candidates(&id)?.collect::<Vec<_>>(), // fmt
215 check
216 );
217 }
218 Ok(())
219 }
220
221 #[test]
222 fn handles_all() -> Result {
223 let mut builder = Filter::builder();
224 let _ = builder.insert(Expression::all(|expr| {
225 expr.with(selector!(location = "**/*.md")?)?
226 .with(selector!(provider = "file")?)
227 })?);
228 let filter = builder.build()?;
229 for (id, check) in [
230 ("zri:file:::docs:index.md:", vec![0]),
231 ("zri:file:::docs:image.png:", vec![]),
232 ("zri:git:::docs:image.md:", vec![]),
233 ] {
234 assert_eq!(
235 filter.candidates(&id)?.collect::<Vec<_>>(), // fmt
236 check
237 );
238 }
239 Ok(())
240 }
241
242 #[test]
243 fn handles_not() -> Result {
244 let mut builder = Filter::builder();
245 let _ = builder.insert(Expression::not(|expr| {
246 expr.with(selector!(location = "**/*.jpg")?)?
247 .with(selector!(location = "**/*.png")?)
248 })?);
249 let filter = builder.build()?;
250 for (id, check) in [
251 ("zri:file:::docs:index.md:", vec![0]),
252 ("zri:file:::docs:image.jpg:", vec![]),
253 ("zri:file:::docs:image.png:", vec![]),
254 ] {
255 assert_eq!(
256 filter.candidates(&id)?.collect::<Vec<_>>(), // fmt
257 check
258 );
259 }
260 Ok(())
261 }
262
263 #[test]
264 fn handles_all_any() -> Result {
265 let mut builder = Filter::builder();
266 let _ = builder.insert(Expression::all(|expr| {
267 expr.with(selector!(provider = "file")?)?
268 .with(Expression::any(|expr| {
269 expr.with(selector!(location = "**/*.jpg")?)?
270 .with(selector!(location = "**/*.png")?)
271 }))
272 })?);
273 let filter = builder.build()?;
274 for (id, check) in [
275 ("zri:file:::docs:index.md:", vec![]),
276 ("zri:file:::docs:image.jpg:", vec![0]),
277 ("zri:file:::docs:image.png:", vec![0]),
278 ("zri:file:::docs:image.gif:", vec![]),
279 ("zri:git:::docs:image.jpg:", vec![]),
280 ("zri:git:::docs:image.png:", vec![]),
281 ] {
282 assert_eq!(
283 filter.candidates(&id)?.collect::<Vec<_>>(), // fmt
284 check
285 );
286 }
287 Ok(())
288 }
289
290 #[test]
291 fn handles_all_any_not() -> Result {
292 let mut builder = Filter::builder();
293 let _ = builder.insert(Expression::all(|expr| {
294 expr.with(selector!(provider = "file")?)?
295 .with(Expression::any(|expr| {
296 expr.with(selector!(context = "docs")?)? // fmt
297 .with(Expression::not(|expr| {
298 expr.with(selector!(location = "**/*.jpg")?)?
299 .with(selector!(location = "**/*.png")?)
300 }),
301 )
302 }))
303 })?);
304 let filter = builder.build()?;
305 for (id, check) in [
306 ("zri:file:::docs:index.md:", vec![0]),
307 ("zri:file:::docs:image.jpg:", vec![0]),
308 ("zri:file:::docs:image.png:", vec![0]),
309 ("zri:file:::docs:image.gif:", vec![0]),
310 ("zri:git:::docs:image.jpg:", vec![]),
311 ("zri:git:::docs:image.png:", vec![]),
312 ] {
313 assert_eq!(
314 filter.candidates(&id)?.collect::<Vec<_>>(), // fmt
315 check
316 );
317 }
318 Ok(())
319 }
320 }
321}