Gentoo Archives: gentoo-pms

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

Replies

Subject Author
[gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode David Leverton <levertond@××××××××××.com>