Skip to main content

keychain/
query.rs

1//! Typed item predicates shared by the library and `kc get`.
2//!
3//! The surface grammar is deliberately small:
4//!
5//! ```text
6//! field:value
7//! field[cd]:pattern
8//! field:>=value
9//! ```
10//!
11//! Predicates in an [`Expression`] are ANDed. `%` and `_` use SQL-LIKE
12//! semantics; `c` and `d` request case- and diacritic-insensitive text
13//! matching.
14
15use 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/// A conjunction of item predicates.
23#[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    /// Parse shell-tokenized predicates.
34    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    /// Parse one explicitly quoted expression, including its inner quotes.
43    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/// One typed comparison against an item field.
62#[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/// The operation applied by a predicate.
180#[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/// Unicode matching modifiers.
201#[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
214/// Stable public name for a queryable record relation.
215pub 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
228/// Resolve a class name accepted by the query language.
229pub 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
242/// Friendly names and native Keychain attribute names share one namespace.
243pub 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}