1use 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 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#[derive(Debug, Copy, Clone)]
109enum HowMatched {
110 Instance,
112 Class,
114 Wildcard,
116}
117
118#[derive(Debug, Copy, Clone)]
122struct MatchComponent {
123 preceding_binding: Binding,
124 how_matched: HowMatched,
125}
126
127#[derive(Debug, Copy, Clone)]
131enum MatchKind {
132 SkippedViaLooseBinding,
134 Matched(MatchComponent),
136}
137
138impl MatchKind {
139 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 #[derive(Debug, Default)]
151 struct MatchState {
152 index: usize,
154 history: Vec<MatchKind>,
156 }
157
158 impl MatchState {
159 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 fn step(mut self, kind: MatchKind) -> Self {
171 self.history.push(kind);
172 self.index += 1;
173 self
174 }
175 }
176
177 let mut states = vec![MatchState::default()];
184
185 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 continue;
193 }
194 let binding = entry.components[state.index].0;
195 match binding {
196 Binding::Tight => {}
198 Binding::Loose => next_states.push(state.skip_loose()),
200 }
201 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 next_states.push(state.step(kind));
217 }
218 }
219 states = next_states;
220 }
221 states
223 .into_iter()
224 .filter(|s| s.index == entry.components.len())
225 .map(|s| s.history)
226 .collect()
227}
228
229fn 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 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 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 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 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
321pub(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 .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 #[test]
357 fn test_matches() {
358 let tests = [
359 (&b""[..], "", "", None),
361 (
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 (
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 (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 (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 (b"First: 1\nSecond: 2\n", "First", "", Some(b"1")),
451 (b"First: 1\nSecond: 2\n", "Second", "", Some(b"2")),
452 (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 (
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 (
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 (
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 (
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 (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}