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