verlib/
cmp.rs

1//! Provides the comparison logic for the `Version`.
2
3use std::cmp::Ordering;
4
5pub const CHAR_ORDER: &'static [u8] = &[
6    255u8, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
7    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
8    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 27,
9    255, 28, 255, 255, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 255, 255, 255,
10    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
11    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
12    255, 255, 255, 255, 255, 255, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
13    14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 255, 255, 255, 0, 255,
14    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
15    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
16    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
17    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
18    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
19    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
20    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
21    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
22    255, 255, 255, 255, 255, 255, 255, 255,
23];
24
25/// Modified string comparison.
26///
27/// Compares ASCII strings using the following rules:
28///
29/// * All the letters sort earlier than all non-letter
30/// * Tilde sorts before anything, including the end of the string
31///
32/// For example, the following strings are in sorted order: `"~~"`, `"~~a"`,
33/// `""`, `"a"`.
34///
35/// See https://www.debian.org/doc/debian-policy/ch-controlfields.html#version
36fn compare_alpha(a: &[u8], b: &[u8]) -> std::cmp::Ordering {
37    // Compare characters using the CHAR_ORDER array
38    for (&ca, &cb) in a.iter().zip(b.iter()) {
39        let pa = CHAR_ORDER[usize::from(ca)];
40        let pb = CHAR_ORDER[usize::from(cb)];
41        match pa.cmp(&pb) {
42            Ordering::Equal => {},
43            o => return o,
44        }
45    }
46
47    // If the strings are the same size, then they are the same
48    if a.len() == b.len() {
49        Ordering::Equal
50    // Otherwise, the longer string is greater (unless tilde comes next)
51    } else if a.len() < b.len() {
52        if b[a.len()] == b'~' {
53            Ordering::Greater
54        } else {
55            Ordering::Less
56        }
57    } else if a.len() > b.len() {
58        if a[b.len()] == b'~' {
59            Ordering::Less
60        } else {
61            Ordering::Greater
62        }
63    } else {
64        unreachable!()
65    }
66}
67
68fn position<T, F>(slice: &[T], start: usize, pred: F) -> usize
69where F: FnMut(&T) -> bool {
70    slice[start ..].iter().position(pred).map(|idx| idx + start).unwrap_or(slice.len())
71}
72
73fn parse_int(slice: &[u8]) -> u32 {
74   use std::str::from_utf8;
75   from_utf8(slice).ok().and_then(|s| s.parse::<u32>().ok()).unwrap_or(0)
76}
77
78/// Compare version strings.
79///
80/// This follows [Debian's algorithm][deb]:
81///
82/// [deb]: https://www.debian.org/doc/debian-policy/ch-controlfields.html#version
83///
84/// First the epoch of each are compared. If they are equal, the strings are
85/// compared from left to right as follows:
86///
87/// First the initial part of each string consisting entirely of non-digit
88/// characters is determined. These two parts (one of which may be empty) are
89/// compared lexically. If a difference is found it is returned. The lexical
90/// comparison is a comparison of ASCII values modified so that all the letters
91/// sort earlier than all the non-letters and so that a tilde sorts before
92/// anything, even the end of a part. For example, the following parts are in
93/// sorted order from earliest to latest: ~~, ~~a, ~, the empty part, a. [7]
94///
95/// Then the initial part of the remainder of each string which consists
96/// entirely of digit characters is determined. The numerical values of these
97/// two parts are compared, and any difference found is returned as the result
98/// of the comparison. For these purposes an empty string (which can only occur
99/// at the end of one or both version strings being compared) counts as zero.
100///
101/// These two steps (comparing and removing initial non-digit strings and
102/// initial digit strings) are repeated until a difference is found or both
103/// strings are exhausted.
104pub fn compare_versions(a: &str, b: &str) -> std::cmp::Ordering {
105    let a = a.as_bytes();
106    let b = b.as_bytes();
107
108    // FIXME: Epoch first
109
110    let mut pos_a = 0;
111    let mut pos_b = 0;
112    while pos_a < a.len() || pos_b < b.len() {
113       // Compare alphabetical sections
114       {
115           let end_alpha_a = position(a, pos_a, u8::is_ascii_digit);
116           let end_alpha_b = position(b, pos_b, u8::is_ascii_digit);
117           match compare_alpha(&a[pos_a .. end_alpha_a], &b[pos_b .. end_alpha_b]) {
118               Ordering::Equal => {},
119               o => return o,
120           }
121           pos_a = end_alpha_a;
122           pos_b = end_alpha_b;
123        }
124
125       // Compare numerical sections
126       {
127           let end_num_a = position(a, pos_a, |c| !c.is_ascii_digit());
128           let end_num_b = position(b, pos_b, |c| !c.is_ascii_digit());
129           let num_a = parse_int(&a[pos_a .. end_num_a]);
130           let num_b = parse_int(&b[pos_b .. end_num_b]);
131           match num_a.cmp(&num_b) {
132               Ordering::Equal => {},
133               o => return o,
134           }
135           pos_a = end_num_a;
136           pos_b = end_num_b;
137        }
138    }
139    Ordering::Equal
140}
141
142#[cfg(test)]
143mod tests {
144    use std::cmp::Ordering;
145
146    use crate::Version;
147    use super::{CHAR_ORDER, compare_alpha};
148
149    struct PrioSetter {
150        prio: u8,
151        char_order: [u8; 256],
152    }
153
154    impl PrioSetter {
155        fn new() -> PrioSetter {
156            PrioSetter {
157                prio: 0,
158                char_order: [255u8; 256],
159            }
160        }
161
162        fn set(&mut self, character: u8) {
163            self.char_order[usize::from(character)] = self.prio;
164            self.prio += 1;
165        }
166
167        fn build(self) -> [u8; 256] {
168            self.char_order
169        }
170    }
171
172    #[test]
173    fn test_char_order() {
174        // This is how I generated the array
175        let mut prios = PrioSetter::new();
176        prios.set(b'~');
177        for c in b'a' ..= b'z' {
178            prios.set(c);
179        }
180        prios.set(b'+');
181        prios.set(b'-');
182        for c in b'0' ..= b'9' {
183            prios.set(c);
184        }
185        let prios = prios.build();
186
187        print!("[");
188        for c in &prios as &[u8] {
189            print!("{}, ", c);
190        }
191        println!("]");
192
193        assert!(prios.len() == CHAR_ORDER.len());
194        assert!(prios.iter().zip(CHAR_ORDER.iter()).all(|(a, b)| a == b));
195    }
196
197    #[test]
198    fn test_compare_alpha() {
199        // Equal
200        assert_eq!(compare_alpha(b"test", b"test"), Ordering::Equal);
201        assert_eq!(compare_alpha(b"", b""), Ordering::Equal);
202        // Ordering
203        assert_eq!(compare_alpha(b"t1", b"t2"), Ordering::Less);
204        assert_eq!(compare_alpha(b"t2", b"t1"), Ordering::Greater);
205        assert_eq!(compare_alpha(b"t133", b"t2"), Ordering::Less);
206        assert_eq!(compare_alpha(b"t2", b"t133"), Ordering::Greater);
207        assert_eq!(compare_alpha(b"ta", b"tb"), Ordering::Less);
208        assert_eq!(compare_alpha(b"tb", b"ta"), Ordering::Greater);
209        assert_eq!(compare_alpha(b"tz", b"test"), Ordering::Greater);
210        assert_eq!(compare_alpha(b"test", b"tz"), Ordering::Less);
211        // Letters come before numbers
212        assert_eq!(compare_alpha(b"test", b"te5t"), Ordering::Less);
213        assert_eq!(compare_alpha(b"te5t", b"test"), Ordering::Greater);
214        // End comes before all (but tilde)
215        assert_eq!(compare_alpha(b"test", b"te"), Ordering::Greater);
216        assert_eq!(compare_alpha(b"te", b"test"), Ordering::Less);
217        assert_eq!(compare_alpha(b"te-", b"te"), Ordering::Greater);
218        assert_eq!(compare_alpha(b"te", b"te-"), Ordering::Less);
219        // Tilde comes before end
220        assert_eq!(compare_alpha(b"te~", b"te"), Ordering::Less);
221        assert_eq!(compare_alpha(b"te", b"te~"), Ordering::Greater);
222    }
223
224    #[test]
225    fn test_compare_versions() {
226        assert!(Version("".into()) == Version("".into()));
227        assert!(Version("1.2".into()) == Version("1.2".into()));
228        assert!(Version("1.2".into()) < Version("1.2.0".into()));
229        assert!(Version("1.3.1".into()) > Version("1.1.3".into()));
230        assert!(Version("1.1.3".into()) < Version("1.3.1".into()));
231        assert!(Version("1.1~rc1".into()) < Version("1.1".into()));
232        assert!(Version("1.1-fix1".into()) > Version("1.1".into()));
233    }
234}
verlib/cmp.rs

verlib/
cmp.rs
