hyper_scripter/query/
the_multifuzz_algo.rs

1use crate::fuzzy::{is_prefix, FuzzKey};
2use crate::SEP;
3use std::borrow::Cow;
4use std::cmp::Ordering;
5
6pub(super) trait MultiFuzzObj: FuzzKey {
7    fn beats(&self, other: &Self) -> bool;
8}
9
10struct MultiFuzzTuple<T: MultiFuzzObj> {
11    obj: T,
12    is_ans: bool,
13    visited: bool,
14}
15impl<T: MultiFuzzObj> MultiFuzzTuple<T> {
16    fn new(obj: T) -> Self {
17        MultiFuzzTuple {
18            obj,
19            is_ans: false,
20            visited: false,
21        }
22    }
23    fn new_ans(obj: T) -> Self {
24        MultiFuzzTuple {
25            obj,
26            is_ans: true,
27            visited: false,
28        }
29    }
30    fn fuzz_key(&self) -> Cow<'_, str> {
31        self.obj.fuzz_key()
32    }
33    fn cmp(&self, other: &Self) -> Ordering {
34        other.fuzz_key().len().cmp(&self.fuzz_key().len())
35    }
36}
37
38fn find_dag_sink<T: MultiFuzzObj>(
39    offset: usize,
40    candidates: &mut [MultiFuzzTuple<T>],
41    best_sink: &mut Option<usize>,
42) {
43    candidates[offset].visited = true;
44    let cur_key = candidates[offset].fuzz_key();
45    // SAFETY: 同一個元素的鍵不可能被拜訪第二次，而且唯一的可變性發生在 `visited` 欄位
46    let cur_key = unsafe { &*(cur_key.as_ref() as *const str) };
47    let mut prefix_found = false;
48    for i in offset + 1..candidates.len() {
49        if candidates[i].visited {
50            continue;
51        }
52        let other_key = candidates[i].fuzz_key();
53        if other_key.len() != cur_key.len() && is_prefix(&other_key, cur_key, SEP) {
54            prefix_found = true;
55            find_dag_sink(i, candidates, best_sink);
56        }
57    }
58
59    if !prefix_found {
60        // 沉沒點！
61        if let Some(best_sink) = best_sink {
62            if candidates[offset].obj.beats(&candidates[*best_sink].obj) {
63                *best_sink = offset;
64            }
65        } else {
66            *best_sink = Some(offset)
67        }
68    }
69}
70
71/// with several elements equally maximum, the **FIRST** position will be returned
72fn find_max_and_ans_pos<T: MultiFuzzObj>(candidates: &[MultiFuzzTuple<T>]) -> (usize, usize) {
73    let mut max_pos = 0;
74    let mut ans_pos = 0;
75    for i in 1..candidates.len() {
76        if candidates[i].is_ans {
77            ans_pos = i;
78        }
79        if candidates[i].obj.beats(&candidates[max_pos].obj) {
80            max_pos = i;
81        }
82    }
83    (max_pos, ans_pos)
84}
85
86/// 從多個模糊搜分數相近者中裁決出「最合適者」。函式過程不太直覺，故在此詳述。
87/// 參數：正解(ans)即分數最高者，其它(others)即其它分數相近的候選人。
88///       應保證正解的長度不大於所有其它人
89///
90/// 1. 建立一個有向無環圖，路徑由長節點指向短節點
91/// 2. 從「最強者」（根據 MultiFuzzObj::beats）出發，找到所有沉沒點
92/// 3. 於所有沉沒點中選出最強沉沒點
93/// 4. 若最強沉沒點為正解之前綴（重排序），回傳正解
94pub(super) fn the_multifuzz_algo<T: MultiFuzzObj>(ans: T, others: Vec<T>) -> T {
95    let mut candidates: Vec<_> = others.into_iter().map(|t| MultiFuzzTuple::new(t)).collect();
96    candidates.push(MultiFuzzTuple::new_ans(ans));
97    // 由長至短排序
98    candidates.sort_by(MultiFuzzTuple::cmp);
99    let (max_pos, ans_pos) = find_max_and_ans_pos(&candidates);
100    let mut ret_pos = None;
101    log::warn!(
102        "multifuzz algo 2: ans = {}, best = {}",
103        candidates[ans_pos].fuzz_key(),
104        candidates[max_pos].fuzz_key()
105    );
106    find_dag_sink(max_pos, &mut candidates, &mut ret_pos);
107    let mut ret_pos = ret_pos.unwrap();
108    log::warn!(
109        "multifuzz algo 3: best_sink = {}",
110        candidates[ret_pos].fuzz_key()
111    );
112    if ret_pos != ans_pos
113        && is_prefix(
114            &candidates[ret_pos].fuzz_key(),
115            &candidates[ans_pos].fuzz_key(),
116            SEP,
117        )
118    {
119        log::warn!("multifuzz algo 4, return answer instead");
120        ret_pos = ans_pos;
121    }
122    candidates.into_iter().skip(ret_pos).next().unwrap().obj
123}
124
125#[cfg(test)]
126mod test {
127    use super::*;
128    #[derive(PartialEq, Eq, Clone, Copy, Debug)]
129    struct MyObj {
130        s: &'static str,
131        order: usize,
132    }
133    impl MyObj {
134        fn new(s: &'static str) -> Self {
135            MyObj { s, order: 0 }
136        }
137    }
138    impl FuzzKey for MyObj {
139        fn fuzz_key(&self) -> Cow<'_, str> {
140            std::borrow::Cow::Borrowed(self.s)
141        }
142    }
143    impl MultiFuzzObj for MyObj {
144        fn beats(&self, other: &Self) -> bool {
145            other.order > self.order
146        }
147    }
148    fn reorder<const S: usize>(mut arr: [&mut MyObj; S]) {
149        for (i, obj) in arr.iter_mut().enumerate() {
150            obj.order = i;
151        }
152    }
153
154    #[test]
155    fn test_the_multifuzz_algo() {
156        let mut ans = MyObj::new("dir");
157        let mut other_p = MyObj::new("dir/a");
158        let mut other = MyObj::new("dother");
159        macro_rules! run_the_algo {
160            () => {
161                the_multifuzz_algo(ans, vec![other, other_p])
162            };
163        }
164
165        reorder([&mut other_p, &mut other, &mut ans]);
166        assert_eq!(ans, run_the_algo!());
167        reorder([&mut other, &mut other_p, &mut ans]);
168        assert_eq!(other, run_the_algo!());
169        reorder([&mut ans, &mut other, &mut other_p]);
170        assert_eq!(ans, run_the_algo!());
171
172        assert_eq!(ans, the_multifuzz_algo(ans, vec![]));
173
174        assert_eq!(ans, the_multifuzz_algo(ans, vec![other_p]));
175        assert_eq!(ans, the_multifuzz_algo(ans, vec![other]));
176        reorder([&mut other, &mut other_p, &mut ans]);
177        assert_eq!(ans, the_multifuzz_algo(ans, vec![other_p]));
178        assert_eq!(other, the_multifuzz_algo(ans, vec![other]));
179    }
180    #[test]
181    fn test_the_multi_sink_multifuzz_algo() {
182        let mut root = MyObj::new("a/b/c/d");
183        let mut b1_1 = MyObj::new("a/b/c");
184        let mut b1_2 = MyObj::new("b/c");
185        let mut b2_1 = MyObj::new("a/c/d");
186        macro_rules! run_the_algo {
187            () => {
188                the_multifuzz_algo(b1_2, vec![root, b1_1, b2_1])
189            };
190        }
191
192        reorder([&mut root, &mut b1_1, &mut b2_1, &mut b1_2]);
193        assert_eq!(b2_1, run_the_algo!());
194        reorder([&mut root, &mut b1_1, &mut b1_2, &mut b2_1]);
195        assert_eq!(b1_2, run_the_algo!());
196
197        reorder([&mut b1_1, &mut root, &mut b1_2, &mut b2_1]);
198        assert_eq!(b1_2, run_the_algo!());
199        reorder([&mut b1_1, &mut root, &mut b2_1, &mut b1_2]);
200        assert_eq!(b1_2, run_the_algo!());
201    }
202    #[test]
203    fn test_multifuzz_determined_ans() {
204        let mut abcd = MyObj::new("a/b/c/d");
205        let mut bacd = MyObj::new("b/a/c/d");
206        let mut cabd = MyObj::new("c/a/b/d");
207        let mut dacb = MyObj::new("d/a/c/b");
208        let mut acbd = MyObj::new("a/c/b/d");
209
210        let mut abc = MyObj::new("a/b/c");
211        let mut cab = MyObj::new("c/a/b");
212
213        reorder([&mut abcd, &mut bacd, &mut cabd, &mut dacb, &mut acbd]);
214        assert_eq!(abcd, the_multifuzz_algo(abcd, vec![bacd, cabd, dacb, acbd]));
215        assert_eq!(bacd, the_multifuzz_algo(bacd, vec![abcd, cabd, dacb, acbd]));
216        assert_eq!(dacb, the_multifuzz_algo(dacb, vec![abcd, bacd, cabd, acbd]));
217
218        // prefix is still preferred
219        reorder([&mut abc, &mut cab]);
220        assert_eq!(
221            abc,
222            the_multifuzz_algo(abc, vec![cab, abcd, bacd, cabd, dacb])
223        );
224        assert_eq!(
225            cab,
226            the_multifuzz_algo(cab, vec![abc, abcd, bacd, cabd, dacb])
227        );
228    }
229}
hyper_scripter/query/the_multifuzz_algo.rs

hyper_scripter/query/
the_multifuzz_algo.rs
