| 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 |
;; |