dovenest

dovenest/pimdav/src/filter.rs
filter.rs
⎇
Raw
1//! Query filters: `calendar-query` (RFC 4791, 9.7) and `addressbook-query`
2//! (RFC 6352, 10.5). Parsing and evaluation.
3
4use std::borrow::Cow;
5use std::cell::RefCell;
6use std::collections::HashMap;
7use std::ops::Range;
8use std::rc::Rc;
9
10use calcard::icalendar::{
11 ICalendar, ICalendarComponent, ICalendarComponentType, ICalendarEntry, ICalendarParameterName,
12 ICalendarParameterValue, ICalendarProperty, ICalendarRelated, ICalendarValue,
13};
14use calcard::vcard::{VCard, VCardVersion};
15use chrono::{DateTime, NaiveDateTime, TimeDelta, Utc};
16use unicode_normalization::UnicodeNormalization;
17use xmltree::Element;
18
19use crate::expand::{Instance, expand, prop_stamp, stamp};
20use crate::freebusy::periods;
21use crate::itip::endless;
22use crate::report::Refused;
23use crate::text::{param_parts, prop, split_unquoted, unescape_text, unfold, value};
24use crate::xml::{CALDAV, CARDDAV, Name, child, elements, text};
25use crate::zone::{Zone, Zones, add};
26
27pub type TimeRange = Range<DateTime<Utc>>;
28
29#[derive(Debug, Clone, PartialEq)]
30pub struct CompFilter {
31 /// Upper case.
32 pub name: String,
33 pub not_defined: bool,
34 pub time_range: Option<TimeRange>,
35 pub props: Vec<PropFilter>,
36 pub comps: Vec<CompFilter>,
37}
38
39#[derive(Debug, Clone, PartialEq)]
40pub struct PropFilter {
41 pub name: String,
42 pub not_defined: bool,
43 pub time_range: Option<TimeRange>,
44 pub text: Option<TextMatch>,
45 pub params: Vec<ParamFilter>,
46}
47
48#[derive(Debug, Clone, PartialEq)]
49pub struct ParamFilter {
50 pub name: String,
51 pub not_defined: bool,
52 pub text: Option<TextMatch>,
53}
54
55#[derive(Debug, Clone, PartialEq)]
56pub struct CardFilter {
57 /// `test="allof"`. The default is `anyof`.
58 pub all: bool,
59 pub props: Vec<CardPropFilter>,
60}
61
62#[derive(Debug, Clone, PartialEq)]
63pub struct CardPropFilter {
64 pub name: String,
65 pub all: bool,
66 pub not_defined: bool,
67 pub texts: Vec<TextMatch>,
68 pub params: Vec<ParamFilter>,
69}
70
71#[derive(Debug, Clone, PartialEq)]
72pub struct TextMatch {
73 pub text: String,
74 pub collation: Collation,
75 pub match_type: MatchType,
76 pub negate: bool,
77}
78
79#[derive(Debug, Clone, Copy, PartialEq, Eq)]
80pub enum Collation {
81 Octet,
82 AsciiCasemap,
83 UnicodeCasemap,
84}
85
86#[derive(Debug, Clone, Copy, PartialEq, Eq)]
87pub enum MatchType {
88 Equals,
89 Contains,
90 StartsWith,
91 EndsWith,
92}
93
94impl Collation {
95 fn fold<'a>(self, s: &'a str) -> Cow<'a, str> {
96 match self {
97 Collation::Octet => Cow::Borrowed(s),
98 Collation::AsciiCasemap => Cow::Owned(s.to_ascii_lowercase()),
99 // Lowercase after NFKD, so compatibility forms such as U+FB01
100 // (the "fi" ligature) fold too.
101 Collation::UnicodeCasemap => {
102 Cow::Owned(s.nfkd().flat_map(char::to_lowercase).collect())
103 }
104 }
105 }
106}
107
108impl TextMatch {
109 /// `ns` picks the defaults: CalDAV folds ASCII only and CardDAV Unicode.
110 fn parse(e: &Element, ns: &str) -> Result<Self, Refused> {
111 let collation = match e.attributes.get("collation").map(String::as_str) {
112 None if ns == CARDDAV => Collation::UnicodeCasemap,
113 None => Collation::AsciiCasemap,
114 Some("i;octet") => Collation::Octet,
115 Some("i;ascii-casemap") => Collation::AsciiCasemap,
116 Some("i;unicode-casemap") => Collation::UnicodeCasemap,
117 Some(_) => return Err(Refused::Condition(Name::new(ns, "supported-collation"))),
118 };
119 Ok(TextMatch {
120 text: text(e),
121 collation,
122 match_type: match_type(e)?,
123 negate: e.attributes.get("negate-condition").map(String::as_str) == Some("yes"),
124 })
125 }
126
127 pub fn matches(&self, value: &str) -> bool {
128 let (v, t) = (self.collation.fold(value), self.collation.fold(&self.text));
129 let hit = match self.match_type {
130 MatchType::Equals => v == t,
131 MatchType::Contains => v.contains(&*t),
132 MatchType::StartsWith => v.starts_with(&*t),
133 MatchType::EndsWith => v.ends_with(&*t),
134 };
135 hit != self.negate
136 }
137}
138
139pub(crate) fn match_type(e: &Element) -> Result<MatchType, Refused> {
140 match e.attributes.get("match-type").map(String::as_str) {
141 None | Some("contains") => Ok(MatchType::Contains),
142 Some("equals") => Ok(MatchType::Equals),
143 Some("starts-with") => Ok(MatchType::StartsWith),
144 Some("ends-with") => Ok(MatchType::EndsWith),
145 Some(_) => Err(Refused::Invalid),
146 }
147}
148
149// ---------------------------------------------------------------------------
150// Parsing
151// ---------------------------------------------------------------------------
152
153/// The `<C:filter>` of a calendar-query.
154pub fn calendar_filter(e: &Element) -> Result<CompFilter, Refused> {
155 let root = comp_filter(child(e, CALDAV, "comp-filter").ok_or(Refused::Invalid)?)?;
156 if root.name != "VCALENDAR" {
157 return Err(Refused::Condition(Name::new(CALDAV, "valid-filter")));
158 }
159 Ok(root)
160}
161
162fn comp_filter(e: &Element) -> Result<CompFilter, Refused> {
163 let mut f = CompFilter {
164 name: name_attr(e)?.to_ascii_uppercase(),
165 not_defined: false,
166 time_range: None,
167 props: Vec::new(),
168 comps: Vec::new(),
169 };
170 for c in elements(e).filter(|c| Name::of(c).ns == CALDAV) {
171 match c.name.as_str() {
172 "is-not-defined" => f.not_defined = true,
173 "time-range" => f.time_range = Some(time_range(c)?),
174 "prop-filter" => f.props.push(prop_filter(c)?),
175 "comp-filter" => f.comps.push(comp_filter(c)?),
176 _ => {}
177 }
178 }
179 Ok(f)
180}
181
182fn prop_filter(e: &Element) -> Result<PropFilter, Refused> {
183 let mut f = PropFilter {
184 name: name_attr(e)?.to_string(),
185 not_defined: false,
186 time_range: None,
187 text: None,
188 params: Vec::new(),
189 };
190 for c in elements(e).filter(|c| Name::of(c).ns == CALDAV) {
191 match c.name.as_str() {
192 "is-not-defined" => f.not_defined = true,
193 "time-range" => f.time_range = Some(time_range(c)?),
194 "text-match" => f.text = Some(TextMatch::parse(c, CALDAV)?),
195 "param-filter" => f.params.push(param_filter(c, CALDAV)?),
196 _ => {}
197 }
198 }
199 Ok(f)
200}
201
202fn param_filter(e: &Element, ns: &str) -> Result<ParamFilter, Refused> {
203 let mut f = ParamFilter {
204 name: name_attr(e)?.to_string(),
205 not_defined: false,
206 text: None,
207 };
208 for c in elements(e).filter(|c| Name::of(c).ns == ns) {
209 match c.name.as_str() {
210 "is-not-defined" => f.not_defined = true,
211 "text-match" => f.text = Some(TextMatch::parse(c, ns)?),
212 _ => {}
213 }
214 }
215 Ok(f)
216}
217
218/// The `<CR:filter>` of an addressbook-query.
219pub fn card_filter(e: &Element) -> Result<CardFilter, Refused> {
220 let props = elements(e)
221 .filter(|c| Name::of(c).is(CARDDAV, "prop-filter"))
222 .map(card_prop_filter)
223 .collect::<Result<_, _>>()?;
224 Ok(CardFilter {
225 all: all_of(e)?,
226 props,
227 })
228}
229
230fn card_prop_filter(e: &Element) -> Result<CardPropFilter, Refused> {
231 let mut f = CardPropFilter {
232 name: name_attr(e)?.to_string(),
233 all: all_of(e)?,
234 not_defined: false,
235 texts: Vec::new(),
236 params: Vec::new(),
237 };
238 for c in elements(e).filter(|c| Name::of(c).ns == CARDDAV) {
239 match c.name.as_str() {
240 "is-not-defined" => f.not_defined = true,
241 "text-match" => f.texts.push(TextMatch::parse(c, CARDDAV)?),
242 "param-filter" => f.params.push(param_filter(c, CARDDAV)?),
243 _ => {}
244 }
245 }
246 Ok(f)
247}
248
249fn all_of(e: &Element) -> Result<bool, Refused> {
250 match e.attributes.get("test").map(String::as_str) {
251 None | Some("anyof") => Ok(false),
252 Some("allof") => Ok(true),
253 Some(_) => Err(Refused::Invalid),
254 }
255}
256
257fn name_attr(e: &Element) -> Result<&str, Refused> {
258 e.attributes
259 .get("name")
260 .map(String::as_str)
261 .ok_or(Refused::Invalid)
262}
263
264/// A `time-range` or `expand` element. A missing bound is open.
265pub fn time_range(e: &Element) -> Result<TimeRange, Refused> {
266 let at = |k: &str| {
267 e.attributes
268 .get(k)
269 .map(|v| {
270 NaiveDateTime::parse_from_str(v, "%Y%m%dT%H%M%SZ")
271 .map(|t| t.and_utc())
272 .map_err(|_| Refused::Invalid)
273 })
274 .transpose()
275 };
276 let start = at("start")?.unwrap_or(DateTime::<Utc>::MIN_UTC);
277 let end = at("end")?.unwrap_or(DateTime::<Utc>::MAX_UTC);
278 if start >= end {
279 return Err(Refused::Invalid);
280 }
281 Ok(start..end)
282}
283
284// ---------------------------------------------------------------------------
285// Calendar evaluation
286// ---------------------------------------------------------------------------
287
288/// Whether a calendar object matches `filter`. `floating` interprets values
289/// without a zone.
290pub fn matches_calendar(cal: &ICalendar, filter: &CompFilter, floating: &Zone) -> bool {
291 let alarm_reach = cal
292 .components
293 .iter()
294 .filter(|c| c.component_type == ICalendarComponentType::VAlarm)
295 .filter_map(relative_reach)
296 .max()
297 .unwrap_or_default();
298 let ctx = Ctx {
299 cal,
300 zones: Zones::new(cal, floating.clone()),
301 floating,
302 alarm_reach,
303 expanded: RefCell::default(),
304 };
305 ctx.comp(None, filter)
306}
307
308struct Ctx<'a> {
309 cal: &'a ICalendar,
310 zones: Zones,
311 floating: &'a Zone,
312 /// The widest reach of any relative alarm, so all alarms share one
313 /// expansion.
314 alarm_reach: TimeDelta,
315 /// One expansion per window, not one per component.
316 expanded: RefCell<HashMap<TimeRange, Rc<Window>>>,
317}
318
319/// The instances of one expansion by component.
320struct Window {
321 of: HashMap<usize, Vec<Instance>>,
322 truncated: bool,
323}
324
325/// The repetitions of alarm `a` and the time between them.
326fn repetitions(a: &ICalendarComponent) -> (i32, TimeDelta) {
327 let repeat = a
328 .property(&ICalendarProperty::Repeat)
329 .and_then(|e| e.values.first()?.as_integer())
330 .unwrap_or(0)
331 .clamp(0, 1000) as i32;
332 let every = match a
333 .property(&ICalendarProperty::Duration)
334 .and_then(|e| e.values.first())
335 {
336 Some(ICalendarValue::Duration(d)) => d.to_time_delta().unwrap_or_default(),
337 _ => TimeDelta::zero(),
338 };
339 (repeat, every)
340}
341
342/// How far from its instance a relative alarm, repetitions included, can
343/// fire, plus one second. `None` for an absolute trigger.
344fn relative_reach(a: &ICalendarComponent) -> Option<TimeDelta> {
345 let Some(ICalendarValue::Duration(d)) = a.property(&ICalendarProperty::Trigger)?.values.first()
346 else {
347 return None;
348 };
349 let (repeat, every) = repetitions(a);
350 Some(
351 d.to_time_delta()?
352 .abs()
353 .checked_add(&every.checked_mul(repeat).unwrap_or(TimeDelta::MAX))
354 .unwrap_or(TimeDelta::MAX)
355 .checked_add(&TimeDelta::seconds(1))
356 .unwrap_or(TimeDelta::MAX),
357 )
358}
359
360impl Ctx<'_> {
361 fn expand(&self, window: TimeRange) -> Rc<Window> {
362 self.expanded
363 .borrow_mut()
364 .entry(window.clone())
365 .or_insert_with(|| {
366 let exp = expand(self.cal, window, self.floating.clone());
367 let mut of: HashMap<usize, Vec<Instance>> = HashMap::new();
368 for x in exp.instances {
369 of.entry(x.component).or_default().push(x);
370 }
371 Rc::new(Window {
372 of,
373 truncated: exp.truncated,
374 })
375 })
376 .clone()
377 }
378
379 fn comp(&self, parent: Option<usize>, f: &CompFilter) -> bool {
380 let children: Vec<usize> = match parent {
381 None => (!self.cal.components.is_empty())
382 .then_some(0)
383 .into_iter()
384 .collect(),
385 Some(p) => self.cal.components[p]
386 .component_ids
387 .iter()
388 .map(|&i| i as usize)
389 .collect(),
390 };
391 let mut found = children.into_iter().filter(|&i| {
392 self.cal.components[i]
393 .component_type
394 .as_str()
395 .eq_ignore_ascii_case(&f.name)
396 });
397 if f.not_defined {
398 return found.next().is_none();
399 }
400 found.any(|i| {
401 f.time_range.as_ref().is_none_or(|r| self.overlaps(i, r))
402 && f.props.iter().all(|p| self.prop(i, p))
403 && f.comps.iter().all(|c| self.comp(Some(i), c))
404 })
405 }
406
407 /// The time-range rules of RFC 4791, 9.9.
408 fn overlaps(&self, i: usize, r: &TimeRange) -> bool {
409 let c = &self.cal.components[i];
410 let has = |p: ICalendarProperty| c.has_property(&p);
411 let time = |p: ICalendarProperty| Some(prop_stamp(&self.zones, c, &p)?.utc());
412 match c.component_type {
413 ICalendarComponentType::VEvent
414 | ICalendarComponentType::VTodo
415 | ICalendarComponentType::VJournal
416 if has(ICalendarProperty::Dtstart) =>
417 {
418 if r.end == DateTime::<Utc>::MAX_UTC && endless(&self.cal.components[i]) {
419 return true;
420 }
421 let todo = c.component_type == ICalendarComponentType::VTodo;
422 let (due, duration) = (
423 has(ICalendarProperty::Due),
424 has(ICalendarProperty::Duration),
425 );
426 // One second wider, so that the exact rules below decide the
427 // instances that only touch the range.
428 let second = TimeDelta::seconds(1);
429 let exp = self.expand(add(r.start, -second)..add(r.end, second));
430 // Unknown instances may overlap, so the object stays in.
431 if exp.truncated {
432 return true;
433 }
434 exp.of.get(&i).into_iter().flatten().any(|x| {
435 let (s, e) = (x.start, x.end);
436 match (todo, due, duration) {
437 (true, _, true) => r.start <= e && (r.end > s || r.end >= e),
438 (true, true, _) => {
439 (r.start < e || r.start <= s) && (r.end > s || r.end >= e)
440 }
441 (true, ..) => r.start <= s && r.end > s,
442 _ if s == e => r.start <= s && r.end > s,
443 _ => r.start < e && r.end > s,
444 }
445 })
446 }
447 ICalendarComponentType::VTodo => match (
448 time(ICalendarProperty::Due),
449 time(ICalendarProperty::Completed),
450 time(ICalendarProperty::Created),
451 ) {
452 (Some(due), _, _) => r.start < due && r.end >= due,
453 (None, Some(done), Some(made)) => {
454 (r.start <= made || r.start <= done) && (r.end >= made || r.end >= done)
455 }
456 (None, Some(done), None) => r.start <= done && r.end >= done,
457 (None, None, Some(made)) => r.end > made,
458 (None, None, None) => true,
459 },
460 ICalendarComponentType::VFreebusy => {
461 let busy: Vec<_> = c
462 .properties(&ICalendarProperty::Freebusy)
463 .flat_map(|e| periods(&self.zones, e))
464 .collect();
465 if !busy.is_empty() {
466 return busy.iter().any(|(s, e)| r.start < *e && r.end > *s);
467 }
468 match (
469 time(ICalendarProperty::Dtstart),
470 time(ICalendarProperty::Dtend),
471 ) {
472 (Some(s), Some(e)) => r.start <= e && r.end > s,
473 _ => false,
474 }
475 }
476 ICalendarComponentType::VAlarm => self.alarm_overlaps(i, r),
477 _ => false,
478 }
479 }
480
481 /// Whether a trigger of the alarm, repetitions included, falls into `r`.
482 /// A relative trigger fires once per instance of the parent component.
483 fn alarm_overlaps(&self, alarm: usize, r: &TimeRange) -> bool {
484 let a = &self.cal.components[alarm];
485 let Some(trigger) = a.property(&ICalendarProperty::Trigger) else {
486 return false;
487 };
488 let (repeat, every) = repetitions(a);
489 let hit = |base: DateTime<Utc>| {
490 (0..=repeat).any(|k| {
491 let t = add(base, every.checked_mul(k).unwrap_or(TimeDelta::MAX));
492 r.start <= t && r.end > t
493 })
494 };
495 match trigger.values.first() {
496 Some(ICalendarValue::PartialDateTime(p)) => {
497 stamp(&self.zones, p, trigger.tz_id()).is_some_and(|s| hit(s.utc()))
498 }
499 Some(ICalendarValue::Duration(d)) => {
500 let Some(offset) = d.to_time_delta() else {
501 return false;
502 };
503 let Some(parent) = self
504 .cal
505 .components
506 .iter()
507 .position(|c| c.component_ids.contains(&(alarm as u32)))
508 else {
509 return false;
510 };
511 if r.end == DateTime::<Utc>::MAX_UTC && endless(&self.cal.components[parent]) {
512 return true;
513 }
514 let owner = &self.cal.components[parent];
515 // A task without DTSTART has no instances. Its alarm can only
516 // relate to DUE (RFC 4791, 9.9).
517 if !owner.has_property(&ICalendarProperty::Dtstart) {
518 return prop_stamp(&self.zones, owner, &ICalendarProperty::Due)
519 .is_some_and(|due| hit(add(due.utc(), offset)));
520 }
521 let from_end = trigger.parameter(&ICalendarParameterName::Related)
522 == Some(&ICalendarParameterValue::Related(ICalendarRelated::End));
523 let exp =
524 self.expand(add(r.start, -self.alarm_reach)..add(r.end, self.alarm_reach));
525 if exp.truncated {
526 return true;
527 }
528 exp.of
529 .get(&parent)
530 .into_iter()
531 .flatten()
532 .any(|x| hit(add(if from_end { x.end } else { x.start }, offset)))
533 }
534 _ => false,
535 }
536 }
537
538 fn prop(&self, i: usize, f: &PropFilter) -> bool {
539 let mut found = self.cal.components[i]
540 .entries
541 .iter()
542 .filter(|e| e.name.as_str().eq_ignore_ascii_case(&f.name));
543 if f.not_defined {
544 return found.next().is_none();
545 }
546 found.any(|e| {
547 let l = ical_line(e);
548 f.time_range.as_ref().is_none_or(|r| {
549 e.values
550 .iter()
551 .filter_map(|v| stamp(&self.zones, v.as_partial_date_time()?, e.tz_id()))
552 .any(|s| r.start <= s.utc() && r.end > s.utc())
553 }) && f.text.as_ref().is_none_or(|t| t.matches(&l.value))
554 && f.params.iter().all(|p| param_matches(&l, p))
555 })
556 }
557}
558
559// ---------------------------------------------------------------------------
560// Card evaluation
561// ---------------------------------------------------------------------------
562
563pub fn matches_card(card: &VCard, f: &CardFilter) -> bool {
564 if f.props.is_empty() {
565 return true;
566 }
567 let v4 = card.version() == Some(VCardVersion::V4_0);
568 let lines: Vec<Line> = card
569 .entries
570 .iter()
571 .map(|e| {
572 let mut s = String::new();
573 let _ = e.write_to(&mut s, v4);
574 line(&s)
575 })
576 .collect();
577 let hit = |p: &CardPropFilter| card_prop(&lines, p);
578 if f.all {
579 f.props.iter().all(hit)
580 } else {
581 f.props.iter().any(hit)
582 }
583}
584
585/// Each text-match and param-filter is tested against every instance of the
586/// property; `test` combines their results.
587fn card_prop(lines: &[Line], f: &CardPropFilter) -> bool {
588 let found: Vec<&Line> = lines
589 .iter()
590 .filter(|l| l.name.eq_ignore_ascii_case(&f.name))
591 .collect();
592 if f.not_defined {
593 return found.is_empty();
594 }
595 if found.is_empty() {
596 return false;
597 }
598 let mut tests = f
599 .texts
600 .iter()
601 .map(|t| found.iter().any(|l| t.matches(&l.value)))
602 .chain(
603 f.params
604 .iter()
605 .map(|p| found.iter().any(|l| param_matches(l, p))),
606 )
607 .peekable();
608 if tests.peek().is_none() {
609 return true;
610 }
611 if f.all {
612 tests.all(|b| b)
613 } else {
614 tests.any(|b| b)
615 }
616}
617
618fn param_matches(l: &Line, f: &ParamFilter) -> bool {
619 match l
620 .params
621 .iter()
622 .find(|(n, _)| n.eq_ignore_ascii_case(&f.name))
623 {
624 None => f.not_defined,
625 Some(_) if f.not_defined => false,
626 Some((_, values)) => f
627 .text
628 .as_ref()
629 .is_none_or(|t| values.iter().any(|v| t.matches(v))),
630 }
631}
632
633// ---------------------------------------------------------------------------
634// Content lines
635// ---------------------------------------------------------------------------
636
637/// A property as text, the way text-match sees it: the group dropped, the
638/// parameter values unquoted, the value unescaped.
639struct Line {
640 name: String,
641 params: Vec<(String, Vec<String>)>,
642 value: String,
643}
644
645fn ical_line(e: &ICalendarEntry) -> Line {
646 let mut s = String::new();
647 let _ = e.write_to(&mut s);
648 line(&s)
649}
650
651/// Parses one content line as calcard's writer produces it.
652fn line(written: &str) -> Line {
653 let l = unfold(written);
654 let params = param_parts(&l)
655 .into_iter()
656 .filter_map(|p| p.split_once('='))
657 .map(|(k, v)| {
658 let values = split_unquoted(v, ',')
659 .into_iter()
660 .map(|v| v.trim_matches('"').to_string())
661 .collect();
662 (k.to_ascii_uppercase(), values)
663 })
664 .collect();
665 Line {
666 name: prop(&l),
667 params,
668 value: unescape_text(value(&l)),
669 }
670}
671