1use unicode_normalization::{UnicodeNormalization, char::is_combining_mark};
16
17use crate::db::Item;
18use crate::error::{Error, Result};
19use crate::format::Value;
20use crate::schema::RecordType;
21
22#[derive(Debug, Clone, Default, PartialEq, Eq)]
24pub struct Expression {
25 pub predicates: Vec<Predicate>,
26}
27
28impl Expression {
29 pub fn new(predicates: Vec<Predicate>) -> Self {
30 Self { predicates }
31 }
32
33 pub fn parse_predicates(predicates: impl IntoIterator<Item = impl AsRef<str>>) -> Result<Self> {
35 predicates
36 .into_iter()
37 .map(|predicate| Predicate::parse(predicate.as_ref()))
38 .collect::<Result<Vec<_>>>()
39 .map(Self::new)
40 }
41
42 pub fn parse(expression: &str) -> Result<Self> {
44 Self::parse_predicates(tokenize(expression)?)
45 }
46
47 pub fn is_empty(&self) -> bool {
48 self.predicates.is_empty()
49 }
50
51 pub fn matches(&self, item: &Item<'_>) -> Result<bool> {
52 for predicate in &self.predicates {
53 if !predicate.matches(item)? {
54 return Ok(false);
55 }
56 }
57 Ok(true)
58 }
59}
60
61#[derive(Debug, Clone, PartialEq, Eq)]
63pub struct Predicate {
64 pub field: String,
65 pub comparison: Comparison,
66 pub value: String,
67 pub options: MatchOptions,
68}
69
70impl Predicate {
71 pub fn parse(input: &str) -> Result<Self> {
72 let (field_and_options, raw_value) = input.split_once(':').ok_or_else(|| {
73 Error::other(format!("expected FIELD:VALUE predicate, got {input:?}"))
74 })?;
75 let (field, options) = parse_field(field_and_options)?;
76 let (comparison, value) = parse_comparison(raw_value);
77 if field.is_empty() {
78 return Err(Error::other("a query field cannot be empty"));
79 }
80 if options != MatchOptions::default() && comparison.is_ordering() {
81 return Err(Error::other(format!(
82 "[c] and [d] cannot modify an ordering comparison in {input:?}"
83 )));
84 }
85 if canonical_field(&field) == "class"
86 && comparison == Comparison::Equal
87 && options == MatchOptions::default()
88 && record_type(value).is_none()
89 {
90 return Err(Error::other(format!(
91 "unknown item class {value:?}; expected generic, internet, appleshare, \
92 certificate, private-key, public-key, or item-key"
93 )));
94 }
95 Ok(Self {
96 field: canonical_field(&field).to_string(),
97 comparison,
98 value: value.to_string(),
99 options,
100 })
101 }
102
103 pub fn matches(&self, item: &Item<'_>) -> Result<bool> {
104 let Some(actual) = field_value(item, &self.field) else {
105 return Ok(false);
106 };
107 match actual {
108 FieldValue::Text(actual) => self.compare_text(&actual),
109 FieldValue::Date(actual) => self.compare_date(&actual),
110 FieldValue::Number(actual) => self.compare_number(actual),
111 FieldValue::Boolean(actual) => self.compare_boolean(actual),
112 }
113 }
114
115 fn compare_text(&self, actual: &str) -> Result<bool> {
116 let actual = normalize(actual, self.options);
117 let wanted = normalize(&self.value, self.options);
118 Ok(match self.comparison {
119 Comparison::Equal => actual == wanted,
120 Comparison::NotEqual => actual != wanted,
121 Comparison::Less => actual < wanted,
122 Comparison::LessEqual => actual <= wanted,
123 Comparison::Greater => actual > wanted,
124 Comparison::GreaterEqual => actual >= wanted,
125 Comparison::Like => like(&actual, &wanted),
126 })
127 }
128
129 fn compare_date(&self, actual: &str) -> Result<bool> {
130 if self.comparison == Comparison::Like {
131 return Err(Error::other(format!(
132 "{} is a date field and cannot use wildcards",
133 self.field
134 )));
135 }
136 let actual = normalize_timestamp(actual)?;
137 let wanted = normalize_timestamp(&self.value)?;
138 Ok(compare_ordered(&actual, &wanted, self.comparison))
139 }
140
141 fn compare_number(&self, actual: i64) -> Result<bool> {
142 if self.comparison == Comparison::Like {
143 return Err(Error::other(format!(
144 "{} is a number field and cannot use wildcards",
145 self.field
146 )));
147 }
148 let wanted: i64 = self.value.parse().map_err(|_| {
149 Error::other(format!(
150 "{} is a number field; {:?} is not a number",
151 self.field, self.value
152 ))
153 })?;
154 Ok(compare_ordered(&actual, &wanted, self.comparison))
155 }
156
157 fn compare_boolean(&self, actual: bool) -> Result<bool> {
158 let wanted = match self.value.as_str() {
159 "true" | "yes" | "1" => true,
160 "false" | "no" | "0" => false,
161 _ => {
162 return Err(Error::other(format!(
163 "{} is a boolean field; expected true or false",
164 self.field
165 )));
166 }
167 };
168 match self.comparison {
169 Comparison::Equal => Ok(actual == wanted),
170 Comparison::NotEqual => Ok(actual != wanted),
171 _ => Err(Error::other(format!(
172 "{} is a boolean field and only supports = and !=",
173 self.field
174 ))),
175 }
176 }
177}
178
179#[derive(Debug, Clone, Copy, PartialEq, Eq)]
181pub enum Comparison {
182 Equal,
183 NotEqual,
184 Less,
185 LessEqual,
186 Greater,
187 GreaterEqual,
188 Like,
189}
190
191impl Comparison {
192 fn is_ordering(self) -> bool {
193 matches!(
194 self,
195 Self::Less | Self::LessEqual | Self::Greater | Self::GreaterEqual
196 )
197 }
198}
199
200#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
202pub struct MatchOptions {
203 pub case_insensitive: bool,
204 pub diacritic_insensitive: bool,
205}
206
207enum FieldValue {
208 Text(String),
209 Date(String),
210 Number(i64),
211 Boolean(bool),
212}
213
214pub fn class_name(record_type: RecordType) -> Option<&'static str> {
216 match record_type {
217 RecordType::GENERIC_PASSWORD => Some("generic"),
218 RecordType::INTERNET_PASSWORD => Some("internet"),
219 RecordType::APPLESHARE_PASSWORD => Some("appleshare"),
220 RecordType::X509_CERTIFICATE | RecordType::CERT => Some("certificate"),
221 RecordType::PRIVATE_KEY => Some("private-key"),
222 RecordType::PUBLIC_KEY => Some("public-key"),
223 RecordType::SYMMETRIC_KEY => Some("item-key"),
224 _ => None,
225 }
226}
227
228pub fn record_type(name: &str) -> Option<RecordType> {
230 match name.to_ascii_lowercase().as_str() {
231 "generic" => Some(RecordType::GENERIC_PASSWORD),
232 "internet" => Some(RecordType::INTERNET_PASSWORD),
233 "appleshare" => Some(RecordType::APPLESHARE_PASSWORD),
234 "certificate" | "cert" => Some(RecordType::X509_CERTIFICATE),
235 "private-key" => Some(RecordType::PRIVATE_KEY),
236 "public-key" => Some(RecordType::PUBLIC_KEY),
237 "item-key" | "symmetric-key" => Some(RecordType::SYMMETRIC_KEY),
238 _ => None,
239 }
240}
241
242pub fn canonical_field(field: &str) -> &str {
244 match field.to_ascii_lowercase().as_str() {
245 "class" => "class",
246 "record" => "record",
247 "label" | "printname" => "PrintName",
248 "kind" | "description" | "desc" => "desc",
249 "account" | "acct" => "acct",
250 "service" | "svce" => "svce",
251 "server" | "srvr" => "srvr",
252 "security-domain" | "domain" | "sdmn" => "sdmn",
253 "path" => "path",
254 "port" => "port",
255 "protocol" | "ptcl" => "ptcl",
256 "auth-type" | "atyp" => "atyp",
257 "volume" | "vlme" => "vlme",
258 "address" | "addr" => "addr",
259 "signature" | "ssig" => "ssig",
260 "comment" | "icmt" => "icmt",
261 "generic" | "gena" => "gena",
262 "created" | "cdat" => "cdat",
263 "modified" | "mdat" => "mdat",
264 "has-secret" => "has-secret",
265 _ => field,
266 }
267}
268
269fn field_value(item: &Item<'_>, field: &str) -> Option<FieldValue> {
270 match field {
271 "class" => class_name(item.record_type).map(|value| FieldValue::Text(value.to_string())),
272 "record" => Some(FieldValue::Number(i64::from(item.number()))),
273 "has-secret" => Some(FieldValue::Boolean(item.has_secret())),
274 _ => {
275 let value = item.attribute(field)?;
276 if crate::db::FOUR_CHAR_CODE_ATTRIBUTES.contains(&field) {
277 return item.display_attribute(field).map(FieldValue::Text);
278 }
279 match value {
280 Value::Uint32(value) => Some(FieldValue::Number(i64::from(*value))),
281 Value::Sint32(value) => Some(FieldValue::Number(i64::from(*value))),
282 Value::Date(bytes) => Some(FieldValue::Date(
283 String::from_utf8_lossy(crate::format::trim_nul(bytes)).into_owned(),
284 )),
285 _ => item.display_attribute(field).map(FieldValue::Text),
286 }
287 }
288 }
289}
290
291fn parse_field(input: &str) -> Result<(String, MatchOptions)> {
292 let Some(open) = input.rfind('[') else {
293 return Ok((input.to_string(), MatchOptions::default()));
294 };
295 if !input.ends_with(']') {
296 return Err(Error::other(format!(
297 "query modifiers must end with ], got {input:?}"
298 )));
299 }
300 let mut options = MatchOptions::default();
301 for modifier in input[open + 1..input.len() - 1].chars() {
302 match modifier {
303 'c' => options.case_insensitive = true,
304 'd' => options.diacritic_insensitive = true,
305 _ => {
306 return Err(Error::other(format!(
307 "unknown query modifier {modifier:?}; expected c or d"
308 )));
309 }
310 }
311 }
312 Ok((input[..open].to_string(), options))
313}
314
315fn parse_comparison(input: &str) -> (Comparison, &str) {
316 for (prefix, comparison) in [
317 (">=", Comparison::GreaterEqual),
318 ("<=", Comparison::LessEqual),
319 ("!=", Comparison::NotEqual),
320 (">", Comparison::Greater),
321 ("<", Comparison::Less),
322 ("=", Comparison::Equal),
323 ] {
324 if let Some(value) = input.strip_prefix(prefix) {
325 return (comparison, value);
326 }
327 }
328 if has_wildcards(input) {
329 (Comparison::Like, input)
330 } else {
331 (Comparison::Equal, input)
332 }
333}
334
335fn has_wildcards(input: &str) -> bool {
336 let mut escaped = false;
337 for character in input.chars() {
338 if escaped {
339 escaped = false;
340 } else if character == '\\' {
341 escaped = true;
342 } else if matches!(character, '%' | '_') {
343 return true;
344 }
345 }
346 false
347}
348
349fn normalize(input: &str, options: MatchOptions) -> String {
350 let decomposed = input.nfkd();
351 let mut output = String::new();
352 for character in decomposed {
353 if options.diacritic_insensitive && is_combining_mark(character) {
354 continue;
355 }
356 if options.case_insensitive {
357 output.extend(character.to_lowercase());
358 } else {
359 output.push(character);
360 }
361 }
362 output
363}
364
365fn normalize_timestamp(input: &str) -> Result<String> {
366 let input = input.trim_end_matches('\0');
367 let compact = if input.len() == 15 && input.ends_with('Z') {
368 input.to_string()
369 } else if input.len() == 20
370 && input.as_bytes()[4] == b'-'
371 && input.as_bytes()[7] == b'-'
372 && input.as_bytes()[10] == b'T'
373 && input.as_bytes()[13] == b':'
374 && input.as_bytes()[16] == b':'
375 && input.ends_with('Z')
376 {
377 format!(
378 "{}{}{}{}{}{}Z",
379 &input[0..4],
380 &input[5..7],
381 &input[8..10],
382 &input[11..13],
383 &input[14..16],
384 &input[17..19]
385 )
386 } else {
387 return Err(Error::other(format!(
388 "expected YYYYMMDDhhmmssZ or RFC 3339 UTC timestamp, got {input:?}"
389 )));
390 };
391 if !compact[..14].bytes().all(|byte| byte.is_ascii_digit()) {
392 return Err(Error::other(format!("invalid timestamp {input:?}")));
393 }
394 Ok(compact)
395}
396
397fn compare_ordered<T: Ord>(actual: &T, wanted: &T, comparison: Comparison) -> bool {
398 match comparison {
399 Comparison::Equal => actual == wanted,
400 Comparison::NotEqual => actual != wanted,
401 Comparison::Less => actual < wanted,
402 Comparison::LessEqual => actual <= wanted,
403 Comparison::Greater => actual > wanted,
404 Comparison::GreaterEqual => actual >= wanted,
405 Comparison::Like => false,
406 }
407}
408
409fn like(actual: &str, pattern: &str) -> bool {
410 let actual = actual.chars().collect::<Vec<_>>();
411 let pattern = like_tokens(pattern);
412 let mut previous = vec![false; actual.len() + 1];
413 previous[0] = true;
414
415 for token in pattern {
416 let mut current = vec![false; actual.len() + 1];
417 match token {
418 LikeToken::Many => {
419 current[0] = previous[0];
420 for index in 1..=actual.len() {
421 current[index] = previous[index] || current[index - 1];
422 }
423 }
424 LikeToken::One => {
425 current[1..].copy_from_slice(&previous[..actual.len()]);
426 }
427 LikeToken::Literal(wanted) => {
428 for index in 1..=actual.len() {
429 current[index] = previous[index - 1] && actual[index - 1] == wanted;
430 }
431 }
432 }
433 previous = current;
434 }
435 previous[actual.len()]
436}
437
438enum LikeToken {
439 Many,
440 One,
441 Literal(char),
442}
443
444fn like_tokens(pattern: &str) -> Vec<LikeToken> {
445 let mut tokens = Vec::new();
446 let mut escaped = false;
447 for character in pattern.chars() {
448 if escaped {
449 tokens.push(LikeToken::Literal(character));
450 escaped = false;
451 } else {
452 match character {
453 '\\' => escaped = true,
454 '%' => tokens.push(LikeToken::Many),
455 '_' => tokens.push(LikeToken::One),
456 literal => tokens.push(LikeToken::Literal(literal)),
457 }
458 }
459 }
460 if escaped {
461 tokens.push(LikeToken::Literal('\\'));
462 }
463 tokens
464}
465
466fn tokenize(input: &str) -> Result<Vec<String>> {
467 let mut tokens = Vec::new();
468 let mut current = String::new();
469 let mut quote = None;
470 let mut escaped = false;
471
472 for character in input.chars() {
473 if escaped {
474 current.push(character);
475 escaped = false;
476 continue;
477 }
478 match quote {
479 Some('\'') if character == '\'' => quote = None,
480 Some('"') if character == '"' => quote = None,
481 Some('"') if character == '\\' => escaped = true,
482 Some(_) => current.push(character),
483 None if character == '\'' || character == '"' => quote = Some(character),
484 None if character == '\\' => escaped = true,
485 None if character.is_whitespace() => {
486 if !current.is_empty() {
487 tokens.push(std::mem::take(&mut current));
488 }
489 }
490 None => current.push(character),
491 }
492 }
493 if quote.is_some() {
494 return Err(Error::other("unterminated quote in query expression"));
495 }
496 if escaped {
497 current.push('\\');
498 }
499 if !current.is_empty() {
500 tokens.push(current);
501 }
502 Ok(tokens)
503}
504
505#[cfg(test)]
506mod tests {
507 use super::*;
508
509 #[test]
510 fn parses_comparisons_wildcards_and_modifiers() {
511 let expression = Expression::parse(
512 r#"class:internet label:"Gmail Account" cdat:<20260515074219Z icmt:%2026% label[cd]:com.%"#,
513 )
514 .unwrap();
515 assert_eq!(expression.predicates.len(), 5);
516 assert_eq!(expression.predicates[1].value, "Gmail Account");
517 assert_eq!(expression.predicates[2].comparison, Comparison::Less);
518 assert_eq!(expression.predicates[3].comparison, Comparison::Like);
519 assert!(expression.predicates[4].options.case_insensitive);
520 assert!(expression.predicates[4].options.diacritic_insensitive);
521 }
522
523 #[test]
524 fn like_honors_sql_wildcards_and_escapes() {
525 assert!(like("a 2026 note", "%2026%"));
526 assert!(like("com.example", "com.%"));
527 assert!(like("100%", r"100\%"));
528 assert!(!like("1000", r"100\%"));
529 assert!(like("abc", "a_c"));
530 }
531
532 #[test]
533 fn unicode_options_fold_case_and_diacritics() {
534 let options = MatchOptions {
535 case_insensitive: true,
536 diacritic_insensitive: true,
537 };
538 assert_eq!(normalize("Café", options), normalize("CAFE", options));
539 }
540
541 #[test]
542 fn timestamps_accept_keychain_and_rfc3339_forms() {
543 assert_eq!(
544 normalize_timestamp("2026-05-15T07:42:19Z").unwrap(),
545 "20260515074219Z"
546 );
547 assert_eq!(
548 normalize_timestamp("20260515074219Z").unwrap(),
549 "20260515074219Z"
550 );
551 }
552}