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: Vec = parse_query(data:resource.as_bytes())?;
328 let class: Vec = parse_query(data:class.as_bytes())?;
329 databaseOption<(&Entry, Vec)>
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: &Vec), (_, match2: &Vec)| compare_matches(match1, match2))
340 .map(|(entry: &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}
620