Debian Codegraph @

vendor/opam/src/core/opamVersionCompare.ml

raw
1 (******************************************************************************)
2 (* This file is part of the Dose library http://www.irill.org/software/dose *)
3 (* *)
4 (* Copyright (C) 2011 Ralf Treinen <[email protected]> *)
5 (* *)
6 (* All rights reserved. This file is distributed under the terms of the *)
7 (* GNU Lesser General Public License version 2.1, with the special *)
8 (* exception on linking described in the file LICENSE. *)
9 (* *)
10 (* Work developed with the support of the Mancoosi Project *)
11 (* http://www.mancoosi.org *)
12 (* *)
13 (******************************************************************************)
14
15 let is_digit = function
16 | '0'..'9' -> true
17 | _ -> false
18 ;;
19
20 (* [skip_while_from i f w m] yields the index of the leftmost character
21 * in the string [s], starting from [i], and ending at [m], that does
22 * not satisfy the predicate [f], or [length w] if no such index exists. *)
23 let rec skip_while_from i f w m =
24 if i = m then i
25 else if f w.[i] then skip_while_from (i + 1) f w m else i
26
27 (* splits a version into (epoch,rest), without the separating ':'. The
28 * epoch is delimited by the leftmost occurrence of ':' in x, and is ""
29 * in case there is no ':' in x. *)
30 let extract_epoch x =
31 match String.index_opt x ':' with
32 | None -> ("", x)
33 | Some ci ->
34 let epoch = String.sub x 0 ci
35 and rest = String.sub x (ci + 1) (String.length x - ci - 1)
36 in (epoch,rest)
37 ;;
38
39 (* splits a version into (prefix,revision). The revision starts on the
40 * right-most occurrence of '-', or is empty in case the version does
41 * not contain '-'. *)
42 let extract_revision x =
43 match String.rindex_opt x '-' with
44 | None -> (x, "")
45 | Some di ->
46 let before = String.sub x 0 di in
47 let after = String.sub x (di+1) (String.length x - di -1) in
48 (before,after)
49 ;;
50
51 (* character comparison uses a modified character ordering: '~' first,
52 then letters, then anything else *)
53 let compare_chars c1 c2 = match c1 with
54 | '~' -> (match c2 with
55 | '~' -> 0
56 | _ -> -1)
57 | 'a'..'z'|'A'..'Z' -> (match c2 with
58 | '~' -> 1
59 | 'a'..'z'|'A'..'Z' -> Char.compare c1 c2
60 | _ -> -1)
61 | _ -> (match c2 with
62 | '~'|'a'..'z'|'A'..'Z' -> 1
63 | _ -> Char.compare c1 c2)
64 ;;
65
66 (* return the first index of x, starting from xi, of a nun-null
67 * character in x. or (length x) in case x contains only 0's starting
68 * from xi on. *)
69 let skip_zeros x xi xl = skip_while_from xi (fun c -> c = '0') x xl;;
70
71 (* compare versions chunks, that is parts of version strings that are
72 * epoch, upstream version, or revisision. Alternates string comparison
73 * and numerical comparison. *)
74 let compare_chunks x y =
75 (* x and y may be empty *)
76 let xl = String.length x
77 and yl = String.length y
78 in
79 let rec loop_lexical xi yi =
80 assert (xi <= xl && yi <= yl);
81 match (xi=xl,yi=yl) with (* which of x and y is exhausted? *)
82 | true,true -> 0
83 | true,false ->
84 (* if y continues numerically than we have to continue by
85 * comparing numerically. In this case the x part is
86 * interpreted as 0 (since empty). If the y part consists
87 * only of 0's then both parts are equal, otherwise the y
88 * part is larger. If y continues non-numerically then y is
89 * larger anyway, so we only have to skip 0's in the y part
90 * and check whether this exhausts the y part. *)
91 let ys = skip_zeros y yi yl in
92 if ys = yl then 0 else if y.[ys]='~' then 1 else -1
93 | false,true -> (* symmetric to the preceding case *)
94 let xs = skip_zeros x xi xl in
95 if xs = xl then 0 else if x.[xs]='~' then -1 else 1
96 | false,false -> (* which of x and y continues numerically? *)
97 match (is_digit x.[xi], is_digit y.[yi]) with
98 | true,true ->
99 (* both continue numerically. Skip leading zeros in the
100 * remaining parts, and then continue by
101 * comparing numerically. *)
102 compare_numerical (skip_zeros x xi xl) (skip_zeros y yi yl)
103 | true,false -> (* '~' is smaller than any numeric part *)
104 if y.[yi]='~' then 1 else -1
105 | false,true -> (* '~' is smaller than any numeric part *)
106 if x.[xi]='~' then -1 else 1
107 | false,false -> (* continue comparing lexically *)
108 let comp = compare_chars x.[xi] y.[yi]
109 in if comp = 0 then loop_lexical (xi+1) (yi+1) else comp
110 and compare_numerical xi yi =
111 assert (xi = xl || (xi < xl && x.[xi] <> '0'));
112 (* leading zeros have been stripped *)
113 assert (yi = yl || (yi < yl && y.[yi] <> '0'));
114 (* leading zeros have been stripped *)
115 let xn = skip_while_from xi is_digit x xl (* length of numerical part *)
116 and yn = skip_while_from yi is_digit y yl (* length of numerical part *)
117 in
118 let comp = compare (xn-xi) (yn-yi)
119 in if comp = 0
120 then (* both numerical parts have same length: compare digit by digit *)
121 loop_numerical xi yi yn
122 else
123 (* if one numerical part is longer than the other we have found the
124 * answer since leading 0 have been striped when switching
125 * to numerical comparison. *)
126 comp
127 and loop_numerical xi yi yn =
128 assert (xi <= xl && yi <= yn && yn <= yl);
129 (* invariant: the two numerical parts that remain to compare are
130 of the same length *)
131 if yi=yn
132 then
133 (* both numerical parts are exhausted, we switch to lexical
134 comparison *)
135 loop_lexical xi yi
136 else
137 (* both numerical parts are not exhausted, we continue comparing
138 digit by digit *)
139 let comp = Char.compare x.[xi] y.[yi]
140 in if comp = 0 then loop_numerical (xi+1) (yi+1) yn else comp
141 in loop_lexical 0 0
142 ;;
143
144 let compare (x : string) (y : string) =
145 let normalize_comp_result x = if x=0 then 0 else if x < 0 then -1 else 1
146 in
147 if x = y then 0
148 else
149 let (e1,rest1) = extract_epoch x
150 and (e2,rest2) = extract_epoch y in
151 let e_comp = compare_chunks e1 e2 in
152 if e_comp <> 0 then normalize_comp_result e_comp
153 else
154 let (u1,r1) = extract_revision rest1
155 and (u2,r2) = extract_revision rest2 in
156 let u_comp = compare_chunks u1 u2 in
157 if u_comp <> 0 then normalize_comp_result u_comp
158 else normalize_comp_result (compare_chunks r1 r2)
159 ;;
160
161 let equal (x : string) (y : string) =
162 if x = y then true else (compare x y) = 0
163 ;;