sley_ref_filter/
versioncmp.rs

1//! glibc strverscmp-derived version ordering, as in git's versioncmp.c.
2
3// states: S_N normal, S_I integral part, S_F fractional parts, S_Z idem but
4// leading zeroes only (from glibc strverscmp, as in git's versioncmp.c).
5const VS_S_N: usize = 0x0;
6const VS_S_I: usize = 0x3;
7const VS_S_F: usize = 0x6;
8const VS_S_Z: usize = 0x9;
9// result_type sentinels: CMP return diff, LEN compare via len_diff/diff.
10const VS_CMP: i8 = 2;
11const VS_LEN: i8 = 3;
12
13#[rustfmt::skip]
14const VS_NEXT_STATE: [usize; 12] = [
15    /* state    x    d    0  */
16    /* S_N */  VS_S_N, VS_S_I, VS_S_Z,
17    /* S_I */  VS_S_N, VS_S_I, VS_S_I,
18    /* S_F */  VS_S_N, VS_S_F, VS_S_F,
19    /* S_Z */  VS_S_N, VS_S_F, VS_S_Z,
20];
21
22#[rustfmt::skip]
23const VS_RESULT_TYPE: [i8; 36] = [
24    /* state   x/x  x/d  x/0  d/x  d/d  d/0  0/x  0/d  0/0  */
25    /* S_N */  VS_CMP, VS_CMP, VS_CMP, VS_CMP, VS_LEN, VS_CMP, VS_CMP, VS_CMP, VS_CMP,
26    /* S_I */  VS_CMP, -1,     -1,     1,      VS_LEN, VS_LEN, 1,      VS_LEN, VS_LEN,
27    /* S_F */  VS_CMP, VS_CMP, VS_CMP, VS_CMP, VS_CMP, VS_CMP, VS_CMP, VS_CMP, VS_CMP,
28    /* S_Z */  VS_CMP, 1,      1,      -1,     VS_CMP, VS_CMP, -1,     VS_CMP, VS_CMP,
29];
30
31#[inline]
32pub fn vs_digit_class(c: u8) -> usize {
33    // 0 if not a digit, 1 if digit 1-9, 2 if '0' (matches git's
34    // (c=='0') + (isdigit(c) != 0)).
35    (c == b'0') as usize + c.is_ascii_digit() as usize
36}
37
38pub struct VsSuffixMatch {
39    conf_pos: i64,
40    start: usize,
41    len: i64,
42}
43
44pub fn vs_find_better_matching_suffix(
45    tagname: &[u8],
46    suffix: &[u8],
47    start: usize,
48    conf_pos: usize,
49    m: &mut VsSuffixMatch,
50) {
51    // A better match either starts earlier, or at the same offset but longer.
52    let end = if m.len < suffix.len() as i64 {
53        m.start
54    } else {
55        m.start.saturating_sub(1)
56    };
57    for i in start..=end {
58        if tagname.len() >= i && tagname[i..].starts_with(suffix) {
59            m.conf_pos = conf_pos as i64;
60            m.start = i;
61            m.len = suffix.len() as i64;
62            break;
63        }
64    }
65}
66
67/// Port of git's swap_prereleases(). `off` is the offset of the first
68/// differing character. Returns Some(diff) if a prerelease suffix forces an
69/// order.
70pub fn vs_swap_prereleases(
71    s1: &[u8],
72    s2: &[u8],
73    off: usize,
74    prereleases: &[String],
75) -> Option<std::cmp::Ordering> {
76    let mut m1 = VsSuffixMatch {
77        conf_pos: -1,
78        start: off,
79        len: -1,
80    };
81    let mut m2 = VsSuffixMatch {
82        conf_pos: -1,
83        start: off,
84        len: -1,
85    };
86    for (i, suffix) in prereleases.iter().enumerate() {
87        let suffix = suffix.as_bytes();
88        let suffix_len = suffix.len();
89        let start = off.saturating_sub(suffix_len);
90        vs_find_better_matching_suffix(s1, suffix, start, i, &mut m1);
91        vs_find_better_matching_suffix(s2, suffix, start, i, &mut m2);
92    }
93    if m1.conf_pos == -1 && m2.conf_pos == -1 {
94        return None;
95    }
96    if m1.conf_pos == m2.conf_pos {
97        // Same suffix in both: caller decides by the rest.
98        return None;
99    }
100    let ord = if m1.conf_pos >= 0 && m2.conf_pos >= 0 {
101        m1.conf_pos.cmp(&m2.conf_pos)
102    } else if m1.conf_pos >= 0 {
103        std::cmp::Ordering::Less
104    } else {
105        std::cmp::Ordering::Greater
106    };
107    Some(ord)
108}
109
110/// Faithful port of git's versioncmp() (glibc strverscmp + prerelease swap).
111pub fn version_sort_cmp(s1: &str, s2: &str, prereleases: &[String]) -> std::cmp::Ordering {
112    let b1 = s1.as_bytes();
113    let b2 = s2.as_bytes();
114    // Iterate with a sentinel NUL so we faithfully follow git's pointer walk.
115    let get1 = |i: usize| -> u8 { if i < b1.len() { b1[i] } else { 0 } };
116    let get2 = |i: usize| -> u8 { if i < b2.len() { b2[i] } else { 0 } };
117
118    if std::ptr::eq(b1.as_ptr(), b2.as_ptr()) && b1.len() == b2.len() {
119        return std::cmp::Ordering::Equal;
120    }
121
122    let mut p1 = 0usize;
123    let mut p2 = 0usize;
124    let mut c1 = get1(p1);
125    let mut c2 = get2(p2);
126    p1 += 1;
127    p2 += 1;
128    let mut state = VS_S_N + vs_digit_class(c1);
129
130    let diff = loop {
131        let d = c1 as i32 - c2 as i32;
132        if d != 0 {
133            break d;
134        }
135        if c1 == 0 {
136            return std::cmp::Ordering::Equal;
137        }
138        state = VS_NEXT_STATE[state];
139        c1 = get1(p1);
140        c2 = get2(p2);
141        p1 += 1;
142        p2 += 1;
143        state += vs_digit_class(c1);
144    };
145
146    // off is the index of the first differing character: pointer is one past it.
147    if !prereleases.is_empty()
148        && let Some(ord) = vs_swap_prereleases(b1, b2, p1 - 1, prereleases)
149    {
150        return ord;
151    }
152
153    let result = VS_RESULT_TYPE[state * 3 + vs_digit_class(c2)];
154    match result {
155        VS_CMP => diff.cmp(&0),
156        VS_LEN => {
157            // while (isdigit(*p1++)) if (!isdigit(*p2++)) return 1;
158            loop {
159                let d1 = get1(p1).is_ascii_digit();
160                p1 += 1;
161                if !d1 {
162                    break;
163                }
164                let d2 = get2(p2).is_ascii_digit();
165                p2 += 1;
166                if !d2 {
167                    return std::cmp::Ordering::Greater;
168                }
169            }
170            if get2(p2).is_ascii_digit() {
171                std::cmp::Ordering::Less
172            } else {
173                diff.cmp(&0)
174            }
175        }
176        other => (other as i32).cmp(&0),
177    }
178}
sley_ref_filter/versioncmp.rs

sley_ref_filter/
versioncmp.rs
