Gentoo Archives: gentoo-pms

From: David Leverton <levertond@××××××××××.com>
To: gentoo-pms@l.g.o
Cc: David Leverton <levertond@××××××××××.com>
Subject: [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode
Date: Tue, 03 Nov 2009 18:12:05
Message-Id: 1257271908-9355-1-git-send-email-levertond@googlemail.com
In Reply to: Re: [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode by Christian Faulhammer
1 Describing it in English gets a bit messy; this is more verbose, but
2 hopefully more precise.
3 ---
4 names.tex | 222 +++++++++++++++++++++++++++++++++++++++++++++++--------------
5 1 files changed, 173 insertions(+), 49 deletions(-)
6
7 Sorry for slacking on this, life tends to be a distraction.
8
9 diff --git a/names.tex b/names.tex
10 index 7bd572d..be155ad 100644
11 --- a/names.tex
12 +++ b/names.tex
13 @@ -93,63 +93,187 @@ This may optionally be followed by the suffix \t{-r} followed immediately by an
14
15 \section{Version Comparison}
16
17 -Version specifications are compared component by component, moving from left to right.
18 -
19 -\IFKDEBUILDELSE
20 -{
21 - If a version starts with \t{scm}, it orders higher than any version that does not
22 - start with \t{scm}. Otherwise, if neither version starts with \t{scm}, the first
23 - component of the number part is compared using strict integer comparison.
24 +Version specifications are compared component by component, moving from left to right,
25 +as detailed in Algorithm~\ref{alg:version-comparison} and sub-algorithms.
26 +If a sub-algorithm returns a decision, then that is the result of the whole comparison;
27 +if it terminates without returning a decision, the process continues from the point
28 +from which it was invoked.
29 +
30 +\begin{algorithm}
31 +\caption{Version comparison top-level logic} \label{alg:version-comparison}
32 +\IFKDEBUILDELSE{
33 + \begin{algorithmic}[1]
34 + \STATE let $A$ and $B$ be the versions to be compared
35 + \IF{$A$ and $B$ both begin with \t{scm}}
36 + \STATE compare revision components using Algorithm~\ref{alg:version-comparison-revision}
37 + \ELSIF{$A$ begins with \t{scm}}
38 + \RETURN $A>B$
39 + \ELSIF{$B$ begins with \t{scm}}
40 + \RETURN $A<B$
41 + \ELSE
42 + \STATE compare numeric components using Algorithm~\ref{alg:version-comparison-numeric}
43 + \STATE compare letter components using Algorithm~\ref{alg:version-comparison-letter}
44 + \STATE compare suffixes using Algorithm~\ref{alg:version-comparison-suffix}
45 + \STATE compare revision components using Algorithm~\ref{alg:version-comparison-revision}
46 + \ENDIF
47 + \RETURN $A=B$
48 + \end{algorithmic}
49 }{
50 - The first component of the number part is compared using strict integer comparison.
51 + \begin{algorithmic}[1]
52 + \STATE let $A$ and $B$ be the versions to be compared
53 + \STATE compare numeric components using Algorithm~\ref{alg:version-comparison-numeric}
54 + \STATE compare letter components using Algorithm~\ref{alg:version-comparison-letter}
55 + \STATE compare suffixes using Algorithm~\ref{alg:version-comparison-suffix}
56 + \STATE compare revision components using Algorithm~\ref{alg:version-comparison-revision}
57 + \RETURN $A=B$
58 + \end{algorithmic}
59 }
60 +\end{algorithm}
61 +
62 +\begin{algorithm}
63 +\caption{Version comparison logic for numeric components} \label{alg:version-comparison-numeric}
64 +\begin{algorithmic}[1]
65 + \STATE define the notations $An_k$ and $Bn_k$ to mean the $k$\textsuperscript{th} numeric component of $A$ and $B$ respectively, using $0$-based indexing
66 + \IF{$An_0>Bn_0$ using integer comparison}
67 + \RETURN $A>B$
68 + \ELSIF{$An_0<Bn_0$ using integer comparison}
69 + \RETURN $A<B$
70 + \ENDIF
71 + \STATE let $Ann$ be the number of numeric components of $A$
72 + \STATE let $Bnn$ be the number of numeric components of $B$
73 + \FORALL{$i$ such that $i\geq1$ and $i<Ann$ and $i<Bnn$, in ascending order}
74 + \STATE compare $An_i$ and $Bn_i$ using Algorithm~\ref{alg:version-comparison-numeric-nonfirst}
75 + \ENDFOR
76 + \IF{$Ann>Bnn$}
77 + \IFKDEBUILDELSE{
78 + \IF{$B$ has any suffixes and no letter, and its first suffix is \t{-scm}}
79 + \RETURN $A<B$
80 + \ELSE
81 + \RETURN $A>B$
82 + \ENDIF
83 + }{
84 + \RETURN $A>B$
85 + }
86 + \ELSIF{$Ann<Bnn$}
87 + \IFKDEBUILDELSE{
88 + \IF{$A$ has any suffixes and no letter, and its first suffix is \t{-scm}}
89 + \RETURN $A>B$
90 + \ELSE
91 + \RETURN $A<B$
92 + \ENDIF
93 + }{
94 + \RETURN $A<B$
95 + }
96 + \ENDIF
97 +\end{algorithmic}
98 +\end{algorithm}
99 +
100 +\begin{algorithm}
101 +\caption{Version comparison logic for each numeric component after the first} \label{alg:version-comparison-numeric-nonfirst}
102 +\begin{algorithmic}[1]
103 + \IF{either $An_i$ or $Bn_i$ has a leading \t{0}}
104 + \STATE let $An'_i$ be $An_i$ with any trailing \t{0}s removed
105 + \STATE let $Bn'_i$ be $Bn_i$ with any trailing \t{0}s removed
106 + \IF{$An'_i>Bn'_i$ using ASCII stringwise comparison}
107 + \RETURN $A>B$
108 + \ELSIF{$An'_i<Bn'_i$ using ASCII stringwise comparison}
109 + \RETURN $A<B$
110 + \ENDIF
111 + \ELSE
112 + \IF{$An_i>Bn_i$ using integer comparison}
113 + \RETURN $A>B$
114 + \ELSIF{$An_i<Bn_i$ using integer comparison}
115 + \RETURN $A<B$
116 + \ENDIF
117 + \ENDIF
118 +\end{algorithmic}
119 +\end{algorithm}
120 +
121 +\begin{algorithm}
122 +\caption{Version comparison logic for letter components} \label{alg:version-comparison-letter}
123 +\begin{algorithmic}[1]
124 + \STATE let $Al$ be the letter component of $A$ if any, otherwise the empty string
125 + \STATE let $Bl$ be the letter component of $B$ if any, otherwise the empty string
126 + \IF{$Al>Bl$ using ASCII stringwise comparison}
127 + \RETURN $A>B$
128 + \ELSIF{$Al<Bl$ using ASCII stringwise comparison}
129 + \RETURN $A<B$
130 + \ENDIF
131 +\end{algorithmic}
132 +\end{algorithm}
133 +
134 +\begin{algorithm}
135 +\caption{Version comparison logic for suffixes} \label{alg:version-comparison-suffix}
136 +\begin{algorithmic}[1]
137 + \STATE define the notations $As_k$ and $Bs_k$ to mean the $k$\textsuperscript{th} suffix of $A$ and $B$ respectively, using $0$-based indexing
138 + \STATE let $Asn$ be the number of suffixes of $A$
139 + \STATE let $Bsn$ be the number of suffixes of $B$
140 + \FORALL{$i$ such that $i\geq0$ and $i<Asn$ and $i<Bsn$, in ascending order}
141 + \STATE compare $As_i$ and $Bs_i$ using Algorithm~\ref{alg:version-comparison-suffix-each}
142 + \ENDFOR
143 + \IF{$Asn>Bsn$}
144 + \IF{$As_{Bsn}$ is of type \t{\_p} \IFKDEBUILDELSE{or \t{-scm}}{}}
145 + \RETURN $A>B$
146 + \ELSE
147 + \RETURN $A<B$
148 + \ENDIF
149 + \ELSIF{$Asn<Bsn$}
150 + \IF{$Bs_{Asn}$ is of type \t{\_p} \IFKDEBUILDELSE{or \t{-scm}}{}}
151 + \RETURN $A<B$
152 + \ELSE
153 + \RETURN $A>B$
154 + \ENDIF
155 + \ENDIF
156 +\end{algorithmic}
157 +\end{algorithm}
158 +
159 +\begin{algorithm}
160 +\caption{Version comparison logic for each suffix} \label{alg:version-comparison-suffix-each}
161 +\begin{algorithmic}[1]
162 + \IF{$As_i$ and $Bs_i$ are of the same type (\t{\_alpha} vs \t{\_beta} etc)}
163 + \STATE let $As'_i$ be the integer part of $As_i$ if any, otherwise \IFKDEBUILDELSE{as specified by Algorithm~\ref{alg:version-comparison-suffix-missingint}}{\t{0}}
164 + \STATE let $Bs'_i$ be the integer part of $Bs_i$ if any, otherwise \IFKDEBUILDELSE{as specified by Algorithm~\ref{alg:version-comparison-suffix-missingint}}{\t{0}}
165 + \IF{$As'_i>Bs'_i$, using integer comparison \IFKDEBUILDELSE{and with $\infty$ greater than any integer}{}}
166 + \RETURN $A>B$
167 + \ELSIF{$As'_i<Bs'_i$, using integer comparison \IFKDEBUILDELSE{and with $\infty$ greater than any integer}{}}
168 + \RETURN $A<B$
169 + \ENDIF
170 + \ELSIF{the type of $As_i$ is greater than the type of $Bs_i$ using the ordering $\mbox{\t{\_alpha}}<\mbox{\t{\_beta}}<\mbox{\t{\_pre}}<\mbox{\t{\_rc}}<\mbox{\t{\_p}}\IFKDEBUILDELSE{<\mbox{\t{-scm}}}{}$}
171 + \RETURN $A>B$
172 + \ELSE
173 + \RETURN $A<B$
174 + \ENDIF
175 +\end{algorithmic}
176 +\end{algorithm}
177
178 -Any subsequent components of the number part are compared as follows:
179 -
180 -\begin{compactitem}
181 -\item If neither component has a leading zero, components are compared using strict integer
182 - comparison.
183 -\item Otherwise, if a component has a leading zero, any trailing zeroes in that component
184 - are stripped (if this makes the component empty, proceed as if it were \t{0} instead),
185 - and the components are compared using a stringwise comparison.
186 -\end{compactitem}
187 -
188 -\IFKDEBUILDELSE
189 -{
190 - If one number part is a prefix of the other, then the version with the longer number
191 - part is greater, unless the shorter part is immediately followed by \t{-scm}, in which
192 - case the version with the shorter part is greater.
193 -}{
194 - If one number part is a prefix of the other, then the version with the longer number
195 - part is greater.
196 -}
197 -Note in particular that \t{1.0} is less than \t{1.0.0}.
198 -
199 -Letter suffixes are compared alphabetically, with any letter being newer than no letter.
200 -
201 -If the letters are equal, suffixes are compared.
202 -\IFKDEBUILDELSE
203 -{
204 - The ordering is \t{\_alpha} is less than \t{\_beta} is less than \t{\_pre} is less
205 - than \t{\_rc} is less than no suffix is less than \t{\_p} is less than \t{-scm}.
206 -}{
207 - The ordering is \t{\_alpha} is less than \t{\_beta} is less than \t{\_pre} is less
208 - than \t{\_rc} is less than no suffix is less than \t{\_p}.
209 -}
210 -If a suffix string is equal, the associated integer parts
211 -\IFKDEBUILDELSE{(except for \t{scm} parts)}{}
212 -are compared using strict integer comparison.
213 \IFKDEBUILDELSE
214 {
215 - A missing integer part is treated as zero, unless the suffix is directly followed
216 - by \t{-scm}, in which case it is treated as being higher than any integer.
217 + \begin{algorithm}
218 + \caption{Deciding an unspecified integer part of a suffix component, for comparison purposes} \label{alg:version-comparison-suffix-missingint}
219 + \begin{algorithmic}[1]
220 + \STATE let $X$ refer to either $A$ or $B$, whichever version contains the suffix under question
221 + \IF{$i+1<Xsn$ and $Xs_{i+1}$ is of type \t{-scm}}
222 + \STATE let $Xs'_i$ be $\infty$
223 + \ELSE
224 + \STATE let $Xs'_i$ be \t{0}
225 + \ENDIF
226 + \end{algorithmic}
227 + \end{algorithm}
228 }{
229 - A missing integer part is treated as zero.
230 }
231
232 -If at this point the two versions are still equal, the revision number is compared using strict
233 -integer comparison as per the previous part. If the revision numbers are equal, so are the two
234 -versions.
235 +\begin{algorithm}
236 +\caption{Version comparison logic for revision components} \label{alg:version-comparison-revision}
237 +\begin{algorithmic}[1]
238 + \STATE let $Ar$ be the integer part of the revision component of $A$ if any, otherwise $\t{0}$
239 + \STATE let $Br$ be the integer part of the revision component of $B$ if any, otherwise $\t{0}$
240 + \IF{$Ar>Br$ using integer comparison}
241 + \RETURN $A>B$
242 + \ELSIF{$Ar<Br$ using integer comparison}
243 + \RETURN $A<B$
244 + \ENDIF
245 +\end{algorithmic}
246 +\end{algorithm}
247
248 \section{Uniqueness of versions}
249
250 --
251 1.6.4.4

Replies

Subject Author
[gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison David Leverton <levertond@××××××××××.com>