x11rb_protocol/resource_manager/
matcher.rs

1//! Match Xrm entries against a query.
2
3use alloc::string::String;
4use alloc::vec;
5use alloc::vec::Vec;
6use std::cmp::Ordering;
7
8use super::parser::parse_query;
9use super::{Binding, Component, Entry};
10
11mod zip_longest {
12    /// Given two slices, produce an iterator that zips the two slices.
13    ///
14    /// Compared to std::iter::Iterator::zip(), this iterator does not stop at the end of the
15    /// shorter of the two slices, but instead continues to the end of the longer slice. To make
16    /// this possible, the individual items are wrapped in `Option`.
17    ///
18    /// See tests below to make this clearer.
19    pub(super) fn zip_longest<'a, T>(
20        a: &'a [T],
21        b: &'a [T],
22    ) -> impl Iterator<Item = (Option<&'a T>, Option<&'a T>)> + 'a {
23        ZipLongest {
24            a: a.iter(),
25            b: b.iter(),
26        }
27    }
28
29    #[derive(Debug)]
30    struct ZipLongest<A, B> {
31        a: A,
32        b: B,
33    }
34
35    impl<A, B> Iterator for ZipLongest<A, B>
36    where
37        A: Iterator,
38        B: Iterator,
39    {
40        type Item = (Option<A::Item>, Option<B::Item>);
41
42        fn next(&mut self) -> Option<Self::Item> {
43            match (self.a.next(), self.b.next()) {
44                (None, None) => None,
45                (a, b) => Some((a, b)),
46            }
47        }
48    }
49
50    #[cfg(test)]
51    mod test_zip_longest {
52        use super::zip_longest;
53        use alloc::vec::Vec;
54
55        #[test]
56        fn empty() {
57            let (a, b): ([u8; 0], [u8; 0]) = ([], []);
58            let res = zip_longest(&a, &b).collect::<Vec<_>>();
59            assert_eq!(res, []);
60        }
61
62        #[test]
63        fn same_length() {
64            let a = [0, 1, 2];
65            let b = [4, 5, 6];
66            let expected = [
67                (Some(&0), Some(&4)),
68                (Some(&1), Some(&5)),
69                (Some(&2), Some(&6)),
70            ];
71            let res = zip_longest(&a, &b).collect::<Vec<_>>();
72            assert_eq!(res, expected);
73        }
74
75        #[test]
76        fn first_shorter() {
77            let a = [0, 1];
78            let b = [4, 5, 6, 7];
79            let expected = [
80                (Some(&0), Some(&4)),
81                (Some(&1), Some(&5)),
82                (None, Some(&6)),
83                (None, Some(&7)),
84            ];
85            let res = zip_longest(&a, &b).collect::<Vec<_>>();
86            assert_eq!(res, expected);
87        }
88
89        #[test]
90        fn second_shorter() {
91            let a = [0, 1, 2, 3];
92            let b = [4, 5];
93            let expected = [
94                (Some(&0), Some(&4)),
95                (Some(&1), Some(&5)),
96                (Some(&2), None),
97                (Some(&3), None),
98            ];
99            let res = zip_longest(&a, &b).collect::<Vec<_>>();
100            assert_eq!(res, expected);
101        }
102    }
103}
104
105/// Info how a specific component was matched.
106///
107/// This information is used to decide which of two matches is "better" in `compare_matches()`.
108#[derive(Debug, Copy, Clone)]
109enum HowMatched {
110    /// The component matched the instance of the query
111    Instance,
112    /// The component matched the class of the query
113    Class,
114    /// The component is a wildcard and thus matched by default
115    Wildcard,
116}
117
118/// Info on how an (unskipped) component of the query was matched
119///
120/// This information is used to decide which of two matches is "better" in `compare_matches()`.
121#[derive(Debug, Copy, Clone)]
122struct MatchComponent {
123    preceding_binding: Binding,
124    how_matched: HowMatched,
125}
126
127/// Info how a (possibly skipped) component of the query was matched
128///
129/// This information is used to decide which of two matches is "better" in `compare_matches()`.
130#[derive(Debug, Copy, Clone)]
131enum MatchKind {
132    /// The component was skipped via a loose binding ("*")
133    SkippedViaLooseBinding,
134    /// The component was matched against the entry.
135    Matched(MatchComponent),
136}
137
138impl MatchKind {
139    /// Create a new `MatchKind::Match` with the given entries.
140    fn new_match(preceding_binding: Binding, how_matched: HowMatched) -> Self {
141        Self::Matched(MatchComponent {
142            preceding_binding,
143            how_matched,
144        })
145    }
146}
147
148fn check_match(entry: &Entry, resource: &[String], class: &[String]) -> Vec<Vec<MatchKind>> {
149    /// Current state of the matching machinery
150    #[derive(Debug, Default)]
151    struct MatchState {
152        /// Index into the entry on where we have to continue matching
153        index: usize,
154        /// How did we get to this state?
155        history: Vec<MatchKind>,
156    }
157
158    impl MatchState {
159        /// Record that a component was skipped via a loose binding (`*`).
160        fn skip_loose(&self) -> Self {
161            let mut history = self.history.clone();
162            history.push(MatchKind::SkippedViaLooseBinding);
163            Self {
164                index: self.index,
165                history,
166            }
167        }
168
169        /// Record that a component was matched in the given way.
170        fn step(mut self, kind: MatchKind) -> Self {
171            self.history.push(kind);
172            self.index += 1;
173            self
174        }
175    }
176
177    // The idea is to check if a nondeterministic finite automaton accepts a given
178    // word. We have a set of current states. This describes where in the
179    // entry we are while trying to match. When we match a component, we go to the next
180    // component in the entry (index + 1, `MatchState::step()`). When we have a loose binding, we
181    // can accept the current component by staying in the same state (index,
182    // `MatchState::skip_loose()`).
183    let mut states = vec![MatchState::default()];
184
185    // Go through the components and match them against the query
186    for (resource, class) in zip_longest::zip_longest(resource, class) {
187        let mut next_states = Vec::new();
188        for state in states.into_iter() {
189            if state.index == entry.components.len() {
190                // We are at the end of the entry and thus cannot continue this match.
191                // We drop this match state.
192                continue;
193            }
194            let binding = entry.components[state.index].0;
195            match binding {
196                // We have to match here, no way around that.
197                Binding::Tight => {}
198                // We could "eat" this with the loose binding by staying in the state
199                Binding::Loose => next_states.push(state.skip_loose()),
200            }
201            // Does the component match?
202            let kind = match entry.components[state.index].1 {
203                Component::Wildcard => Some(MatchKind::new_match(binding, HowMatched::Wildcard)),
204                Component::Normal(ref s) => {
205                    if Some(s) == resource {
206                        Some(MatchKind::new_match(binding, HowMatched::Instance))
207                    } else if Some(s) == class {
208                        Some(MatchKind::new_match(binding, HowMatched::Class))
209                    } else {
210                        None
211                    }
212                }
213            };
214            if let Some(kind) = kind {
215                // Yes, the component matches and we go to the next state
216                next_states.push(state.step(kind));
217            }
218        }
219        states = next_states;
220    }
221    // We have a match if we reached the end of the components
222    states
223        .into_iter()
224        .filter(|s| s.index == entry.components.len())
225        .map(|s| s.history)
226        .collect()
227}
228
229/// Compare two matches and decide which one of the two is better (`Ordering::Greater`)
230fn compare_matches(match1: &[MatchKind], match2: &[MatchKind]) -> Ordering {
231    use Binding::*;
232    use HowMatched::*;
233    use MatchKind::*;
234
235    fn rule1(match1: &MatchKind, match2: &MatchKind) -> Ordering {
236        // Precedence rule #1: Matching components (including wildcard '?') outweighs loose bindings ('*')
237        if let Matched(_) = match1 {
238            if let SkippedViaLooseBinding = match2 {
239                return Ordering::Greater;
240            }
241        }
242        Ordering::Equal
243    }
244
245    fn rule2(match1: &MatchKind, match2: &MatchKind) -> Ordering {
246        // Precedence rule #2a: Matching instance outweighs both matching class and wildcard
247        if let Matched(MatchComponent {
248            how_matched: Instance,
249            preceding_binding: _,
250        }) = match1
251        {
252            if let Matched(MatchComponent {
253                how_matched: Class,
254                preceding_binding: _,
255            }) = match2
256            {
257                return Ordering::Greater;
258            }
259            if let Matched(MatchComponent {
260                how_matched: Wildcard,
261                ..
262            }) = match2
263            {
264                return Ordering::Greater;
265            }
266        }
267        // Precedence rule #2b: Matching class outweighs wildcard
268        if let Matched(MatchComponent {
269            how_matched: Class, ..
270        }) = match1
271        {
272            if let Matched(MatchComponent {
273                how_matched: Wildcard,
274                ..
275            }) = match2
276            {
277                return Ordering::Greater;
278            }
279        }
280        Ordering::Equal
281    }
282
283    fn rule3(match1: &MatchKind, match2: &MatchKind) -> Ordering {
284        // Precedence rule #3: A preceding exact match outweights a preceding '*'
285        if let Matched(MatchComponent {
286            preceding_binding: Tight,
287            ..
288        }) = match1
289        {
290            if let Matched(MatchComponent {
291                preceding_binding: Loose,
292                ..
293            }) = match2
294            {
295                return Ordering::Greater;
296            }
297        }
298        Ordering::Equal
299    }
300
301    assert_eq!(
302        match1.len(),
303        match2.len(),
304        "Both matches should have the same length (which is guaranteed by the current \
305         implementation of check_match())"
306    );
307    for (m1, m2) in match1.iter().zip(match2.iter()) {
308        let ordering = rule1(m1, m2)
309            .then_with(|| rule1(m2, m1).reverse())
310            .then_with(|| rule2(m1, m2))
311            .then_with(|| rule2(m2, m1).reverse())
312            .then_with(|| rule3(m1, m2))
313            .then_with(|| rule3(m2, m1).reverse());
314        if ordering != Ordering::Equal {
315            return ordering;
316        }
317    }
318    Ordering::Equal
319}
320
321/// Find the best match for the given query in the database, returning `None` when nothing matches.
322pub(crate) fn match_entry<'a>(
323    database: &'a [Entry],
324    resource: &str,
325    class: &str,
326) -> Option<&'a [u8]> {
327    let resource = parse_query(resource.as_bytes())?;
328    let class = parse_query(class.as_bytes())?;
329    database
330        .iter()
331        // Filter for entries that match the query (and record some info on how they match)
332        .flat_map(|entry| {
333            let matches = check_match(entry, &resource, &class);
334            let best_match = matches
335                .into_iter()
336                .max_by(|match1, match2| compare_matches(match1, match2));
337            best_match.map(|m| (entry, m))
338        })
339        .max_by(|(_, match1), (_, match2)| compare_matches(match1, match2))
340        .map(|(entry, _)| &entry.value[..])
341}
342
343#[cfg(test)]
344mod test {
345    use super::super::parser::parse_database;
346    use super::match_entry;
347
348    use alloc::format;
349    use alloc::string::{String, ToString};
350    use alloc::vec::Vec;
351    use std::eprintln;
352
353    // Most tests in here are based on [1], which is: Copyright © 2016 Ingo Bürk
354    // [1]: https://github.com/Airblader/xcb-util-xrm/blob/master/tests/tests_match.c
355
356    #[test]
357    fn test_matches() {
358        let tests = [
359            // Non-matches / Errors
360            (&b""[..], "", "", None),
361            // Xlib returns the match here, despite the query violating the specs (different number
362            // of components in the query)
363            (
364                b"First.second: 1",
365                "First.second",
366                "First.second.third",
367                None,
368            ),
369            (b"", "First.second", "", None),
370            (b"First.second: 1", "First.third", "", None),
371            (b"First.second: 1", "First", "", None),
372            (b"First: 1", "First.second", "", None),
373            (b"First.?.fourth: 1", "First.second.third.fourth", "", None),
374            (b"First*?.third: 1", "First.third", "", None),
375            (b"First: 1", "first", "", None),
376            (b"First: 1", "", "first", None),
377            // Duplicate entries
378            (
379                b"First: 1\nFirst: 2\nFirst: 3\n",
380                "First",
381                "",
382                Some(&b"3"[..]),
383            ),
384            (
385                b"First: 1\nSecond: 2\nSecond: 3\nThird: 4\n",
386                "Second",
387                "",
388                Some(b"3"),
389            ),
390            // Basic matching
391            (b"First: 1", "First", "", Some(b"1")),
392            (b"First.second: 1", "First.second", "", Some(b"1")),
393            (b"?.second: 1", "First.second", "", Some(b"1")),
394            (b"First.?.third: 1", "First.second.third", "", Some(b"1")),
395            (
396                b"First.?.?.fourth: 1",
397                "First.second.third.fourth",
398                "",
399                Some(b"1"),
400            ),
401            (b"*second: 1", "First.second", "", Some(b"1")),
402            (b".second: 1", "First.second", "", None),
403            (b"*third: 1", "First.second.third", "", Some(b"1")),
404            (b"First*second: 1", "First.second", "", Some(b"1")),
405            (b"First*third: 1", "First.second.third", "", Some(b"1")),
406            (
407                b"First*fourth: 1",
408                "First.second.third.fourth",
409                "",
410                Some(b"1"),
411            ),
412            (b"First*?.third: 1", "First.second.third", "", Some(b"1")),
413            (b"First: 1", "Second", "First", Some(b"1")),
414            (
415                b"First.second: 1",
416                "First.third",
417                "first.second",
418                Some(b"1"),
419            ),
420            (
421                b"First.second.third: 1",
422                "First.third.third",
423                "first.second.fourth",
424                Some(b"1"),
425            ),
426            (
427                b"First*third*fifth: 1",
428                "First.second.third.fourth.third.fifth",
429                "",
430                Some(b"1"),
431            ),
432            (b"First: x\\\ny", "First", "", Some(b"xy")),
433            (b"! First: x", "First", "", None),
434            (b"# First: x", "First", "", None),
435            (b"First:", "First", "", Some(b"")),
436            (b"First: ", "First", "", Some(b"")),
437            (b"First: \t ", "First", "", Some(b"")),
438            // Consecutive bindings
439            (b"*.bar: 1", "foo.foo.bar", "", Some(b"1")),
440            (b"...bar: 1", "foo.bar", "", None),
441            (b"...bar: 1", "foo.foo.foo.bar", "", None),
442            (b"***bar: 1", "foo.bar", "", Some(b"1")),
443            (b".*.bar: 1", "foo.bar", "", Some(b"1")),
444            (b".*.bar: 1", "foo.foo.bar", "", Some(b"1")),
445            (b"..*bar: 1", "foo.foo.foo.foo.bar", "", Some(b"1")),
446            (b"a.*.z: 1", "a.b.c.d.e.f.z", "", Some(b"1")),
447            (b"a...z: 1", "a.z", "", Some(b"1")),
448            (b"a...z: 1", "a.b.z", "", None),
449            // Matching among multiple entries
450            (b"First: 1\nSecond: 2\n", "First", "", Some(b"1")),
451            (b"First: 1\nSecond: 2\n", "Second", "", Some(b"2")),
452            // Greediness
453            (b"a*c.e: 1", "a.b.c.d.c.e", "", Some(b"1")),
454            (b"a*c.e: 1", "a.b.c.c.e", "", Some(b"1")),
455            (b"a*?.e: 1", "a.b.c.e", "", Some(b"1")),
456            (b"a*c*e: 1", "a.b.c.d.c.d.e.d.e", "", Some(b"1")),
457            // Precedence rules
458            // Rule 1
459            (
460                b"First.second.third: 1\nFirst*third: 2\n",
461                "First.second.third",
462                "",
463                Some(b"1"),
464            ),
465            (
466                b"First*third: 2\nFirst.second.third: 1\n",
467                "First.second.third",
468                "",
469                Some(b"1"),
470            ),
471            (
472                b"First.second.third: 1\nFirst*third: 2\n",
473                "x.x.x",
474                "First.second.third",
475                Some(b"1"),
476            ),
477            (
478                b"First*third: 2\nFirst.second.third: 1\n",
479                "x.x.x",
480                "First.second.third",
481                Some(b"1"),
482            ),
483            // Rule 2
484            (
485                b"First.second: 1\nFirst.third: 2\n",
486                "First.second",
487                "First.third",
488                Some(b"1"),
489            ),
490            (
491                b"First.third: 2\nFirst.second: 1\n",
492                "First.second",
493                "First.third",
494                Some(b"1"),
495            ),
496            (
497                b"First.second.third: 1\nFirst.?.third: 2\n",
498                "First.second.third",
499                "",
500                Some(b"1"),
501            ),
502            (
503                b"First.?.third: 2\nFirst.second.third: 1\n",
504                "First.second.third",
505                "",
506                Some(b"1"),
507            ),
508            (
509                b"First.second.third: 1\nFirst.?.third: 2\n",
510                "x.x.x",
511                "First.second.third",
512                Some(b"1"),
513            ),
514            (
515                b"First.?.third: 2\nFirst.second.third: 1\n",
516                "x.x.x",
517                "First.second.third",
518                Some(b"1"),
519            ),
520            // Rule 3
521            (
522                b"First.second: 1\nFirst*second: 2\n",
523                "First.second",
524                "",
525                Some(b"1"),
526            ),
527            (
528                b"First*second: 2\nFirst.second: 1\n",
529                "First.second",
530                "",
531                Some(b"1"),
532            ),
533            // Some real world examples. May contain duplicates to the above tests.
534
535            // From the specification:
536            // https://tronche.com/gui/x/xlib/resource-manager/matching-rules.html
537            (
538                b"xmh*Paned*activeForeground: red\n\
539                  *incorporate.Foreground: blue\n\
540                  xmh.toc*Command*activeForeground: green\n\
541                  xmh.toc*?.Foreground: white\n\
542                  xmh.toc*Command.activeForeground: black",
543                "xmh.toc.messagefunctions.incorporate.activeForeground",
544                "Xmh.Paned.Box.Command.Foreground",
545                Some(b"black"),
546            ),
547            (
548                b"urxvt*background: [95]#000",
549                "urxvt.background",
550                "",
551                Some(b"[95]#000"),
552            ),
553            (
554                b"urxvt*scrollBar_right:true",
555                "urxvt.scrollBar_right",
556                "",
557                Some(b"true"),
558            ),
559            (
560                b"urxvt*cutchars:    '\"'()*<>[]{|}",
561                "urxvt.cutchars",
562                "",
563                Some(b"'\"'()*<>[]{|}"),
564            ),
565            (
566                b"urxvt.keysym.Control-Shift-Up: perl:font:increment",
567                "urxvt.keysym.Control-Shift-Up",
568                "",
569                Some(b"perl:font:increment"),
570            ),
571            (
572                b"rofi.normal: #000000, #000000, #000000, #000000",
573                "rofi.normal",
574                "",
575                Some(b"#000000, #000000, #000000, #000000"),
576            ),
577            // Own tests
578            (b"*foo.bar: 1", "bar", "", None),
579            (
580                b"First.Second.Third: 1\nFirst.Second: 2",
581                "First.Second.Third",
582                "First.Second",
583                Some(b"1"),
584            ),
585            (
586                b"First.Second.Third: 1\nFirst.Second: 2",
587                "First.Second",
588                "First.Second.Third",
589                Some(b"1"),
590            ),
591        ];
592        let mut failures = 0;
593        for &(data, resource, class, expected) in tests.iter() {
594            let mut entries = Vec::new();
595            parse_database(data, &mut entries, |_, _| unreachable!());
596            let result = match_entry(&entries, resource, class);
597            if result != expected {
598                eprintln!(
599                    "While testing resource '{}' and class '{}' with the following input:",
600                    resource, class
601                );
602                eprintln!("{}", print_string(data));
603                eprintln!("Expected: {:?}", expected.map(print_string));
604                eprintln!("Got:      {:?}", result.map(print_string));
605                eprintln!();
606                failures += 1;
607            }
608        }
609        if failures != 0 {
610            panic!("Had {} failures", failures)
611        }
612    }
613
614    fn print_string(data: &[u8]) -> String {
615        std::str::from_utf8(data)
616            .map(|s| s.to_string())
617            .unwrap_or_else(|_| format!("{:?}", data))
618    }
619}