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 |