* [gentoo-pms] [PATCH] Rewrite version comparison rules in pseudocode
@ 2009-10-17 20:21 99% David Leverton
0 siblings, 0 replies; 1+ results
From: David Leverton @ 2009-10-17 20:21 UTC (permalink / raw
To: gentoo-pms; +Cc: David Leverton
Describing it in English gets a bit messy; this is more verbose, but
hopefully more precise.
---
names.tex | 205 ++++++++++++++++++++++++++++++++++++++++++++++---------------
1 files changed, 156 insertions(+), 49 deletions(-)
Prebuilt version at
http://dev.exherbo.org/~dleverton/pms/pms.html#x1-280003.3 if that's
easier.
diff --git a/names.tex b/names.tex
index 7bd572d..ce2d2d0 100644
--- a/names.tex
+++ b/names.tex
@@ -93,63 +93,170 @@ This may optionally be followed by the suffix \t{-r} followed immediately by an
\section{Version Comparison}
-Version specifications are compared component by component, moving from left to right.
-
-\IFKDEBUILDELSE
-{
- If a version starts with \t{scm}, it orders higher than any version that does not
- start with \t{scm}. Otherwise, if neither version starts with \t{scm}, the first
- component of the number part is compared using strict integer comparison.
+Version comparison is defined by Algorithm~\ref{alg:version-comparison} and sub-algorithms.
+If a sub-algorithm returns a decision, then that is the result of the whole comparison;
+if it terminates without returning a decision, the process continues from the point
+from which it was invoked.
+
+\begin{algorithm}
+\caption{Version comparison top-level logic} \label{alg:version-comparison}
+\IFKDEBUILDELSE{
+ \begin{algorithmic}[1]
+ \STATE let $A$ and $B$ be the versions to be compared
+ \IF{$A$ and $B$ both begin with \t{scm}}
+ \STATE compare revision components using Algorithm~\ref{alg:version-comparison-revision}
+ \ELSIF{$A$ begins with \t{scm}}
+ \RETURN $A>B$
+ \ELSIF{$B$ begins with \t{scm}}
+ \RETURN $A<B$
+ \ELSE
+ \STATE compare numeric components using Algorithm~\ref{alg:version-comparison-numeric}
+ \STATE compare letter components using Algorithm~\ref{alg:version-comparison-letter}
+ \STATE compare suffixes using Algorithm~\ref{alg:version-comparison-suffix}
+ \STATE compare revision components using Algorithm~\ref{alg:version-comparison-revision}
+ \ENDIF
+ \RETURN $A=B$
+ \end{algorithmic}
}{
- The first component of the number part is compared using strict integer comparison.
+ \begin{algorithmic}[1]
+ \STATE let $A$ and $B$ be the versions to be compared
+ \STATE compare numeric components using Algorithm~\ref{alg:version-comparison-numeric}
+ \STATE compare letter components using Algorithm~\ref{alg:version-comparison-letter}
+ \STATE compare suffixes using Algorithm~\ref{alg:version-comparison-suffix}
+ \STATE compare revision components using Algorithm~\ref{alg:version-comparison-revision}
+ \RETURN $A=B$
+ \end{algorithmic}
}
+\end{algorithm}
+
+\begin{algorithm}
+\caption{Version comparison logic for numeric components} \label{alg:version-comparison-numeric}
+\begin{algorithmic}[1]
+ \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
+ \IF{$An_0>Bn_0$ using integer comparison}
+ \RETURN $A>B$
+ \ELSIF{$An_0<Bn_0$ using integer comparison}
+ \RETURN $A<B$
+ \ENDIF
+ \STATE let $Ann$ be the number of numeric components of $A$
+ \STATE let $Bnn$ be the number of numeric components of $B$
+ \FORALL{$i$ such that $i\geq1$ and $i<Ann$ and $i<Bnn$, in ascending order}
+ \STATE compare $An_i$ and $Bn_i$ using Algorithm~\ref{alg:version-comparison-numeric-nonfirst}
+ \ENDFOR
+ \IF{$Ann>Bnn$}
+ \RETURN $A>B$
+ \ELSIF{$Ann<Bnn$}
+ \RETURN $A<B$
+ \ENDIF
+\end{algorithmic}
+\end{algorithm}
+
+\begin{algorithm}
+\caption{Version comparison logic for each numeric component after the first} \label{alg:version-comparison-numeric-nonfirst}
+\begin{algorithmic}[1]
+ \IF{either $An_i$ or $Bn_i$ has a leading \t{0}}
+ \STATE let $An'_i$ be $An_i$ with any trailing \t{0}s removed
+ \STATE let $Bn'_i$ be $Bn_i$ with any trailing \t{0}s removed
+ \IF{$An'_i>Bn'_i$ using ASCII stringwise comparison}
+ \RETURN $A>B$
+ \ELSIF{$An'_i<Bn'_i$ using ASCII stringwise comparison}
+ \RETURN $A<B$
+ \ENDIF
+ \ELSE
+ \IF{$An_i>Bn_i$ using integer comparison}
+ \RETURN $A>B$
+ \ELSIF{$An_i<Bn_i$ using integer comparison}
+ \RETURN $A<B$
+ \ENDIF
+ \ENDIF
+\end{algorithmic}
+\end{algorithm}
+
+\begin{algorithm}
+\caption{Version comparison logic for letter components} \label{alg:version-comparison-letter}
+\begin{algorithmic}[1]
+ \STATE let $Al$ be the letter component of $A$ if any, otherwise the empty string
+ \STATE let $Bl$ be the letter component of $B$ if any, otherwise the empty string
+ \IF{$Al>Bl$ using ASCII stringwise comparison}
+ \RETURN $A>B$
+ \ELSIF{$Al<Bl$ using ASCII stringwise comparison}
+ \RETURN $A<B$
+ \ENDIF
+\end{algorithmic}
+\end{algorithm}
+
+\begin{algorithm}
+\caption{Version comparison logic for suffixes} \label{alg:version-comparison-suffix}
+\begin{algorithmic}[1]
+ \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
+ \STATE let $Asn$ be the number of suffixes of $A$
+ \STATE let $Bsn$ be the number of suffixes of $B$
+ \FORALL{$i$ such that $i\geq0$ and $i<Asn$ and $i<Bsn$, in ascending order}
+ \STATE compare $As_i$ and $Bs_i$ using Algorithm~\ref{alg:version-comparison-suffix-each}
+ \ENDFOR
+ \IF{$Asn>Bsn$}
+ \IF{$As_{Bsn}$ is of type \t{\_p} \IFKDEBUILDELSE{or \t{-scm}}{}}
+ \RETURN $A>B$
+ \ELSE
+ \RETURN $A<B$
+ \ENDIF
+ \ELSIF{$Asn<Bsn$}
+ \IF{$Bs_{Asn}$ is of type \t{\_p} \IFKDEBUILDELSE{or \t{-scm}}{}}
+ \RETURN $A<B$
+ \ELSE
+ \RETURN $A>B$
+ \ENDIF
+ \ENDIF
+\end{algorithmic}
+\end{algorithm}
+
+\begin{algorithm}
+\caption{Version comparison logic for each suffix} \label{alg:version-comparison-suffix-each}
+\begin{algorithmic}[1]
+ \IF{$As_i$ and $Bs_i$ are of the same type (\t{\_alpha} vs \t{\_beta} etc)}
+ \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}}
+ \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}}
+ \IF{$As'_i>Bs'_i$, using integer comparison \IFKDEBUILDELSE{and with $\infty$ greater than any integer}{}}
+ \RETURN $A>B$
+ \ELSIF{$As'_i<Bs'_i$, using integer comparison \IFKDEBUILDELSE{and with $\infty$ greater than any integer}{}}
+ \RETURN $A<B$
+ \ENDIF
+ \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}}}{}$}
+ \RETURN $A>B$
+ \ELSE
+ \RETURN $A<B$
+ \ENDIF
+\end{algorithmic}
+\end{algorithm}
-Any subsequent components of the number part are compared as follows:
-
-\begin{compactitem}
-\item If neither component has a leading zero, components are compared using strict integer
- comparison.
-\item Otherwise, if a component has a leading zero, any trailing zeroes in that component
- are stripped (if this makes the component empty, proceed as if it were \t{0} instead),
- and the components are compared using a stringwise comparison.
-\end{compactitem}
-
-\IFKDEBUILDELSE
-{
- If one number part is a prefix of the other, then the version with the longer number
- part is greater, unless the shorter part is immediately followed by \t{-scm}, in which
- case the version with the shorter part is greater.
-}{
- If one number part is a prefix of the other, then the version with the longer number
- part is greater.
-}
-Note in particular that \t{1.0} is less than \t{1.0.0}.
-
-Letter suffixes are compared alphabetically, with any letter being newer than no letter.
-
-If the letters are equal, suffixes are compared.
-\IFKDEBUILDELSE
-{
- The ordering is \t{\_alpha} is less than \t{\_beta} is less than \t{\_pre} is less
- than \t{\_rc} is less than no suffix is less than \t{\_p} is less than \t{-scm}.
-}{
- The ordering is \t{\_alpha} is less than \t{\_beta} is less than \t{\_pre} is less
- than \t{\_rc} is less than no suffix is less than \t{\_p}.
-}
-If a suffix string is equal, the associated integer parts
-\IFKDEBUILDELSE{(except for \t{scm} parts)}{}
-are compared using strict integer comparison.
\IFKDEBUILDELSE
{
- A missing integer part is treated as zero, unless the suffix is directly followed
- by \t{-scm}, in which case it is treated as being higher than any integer.
+ \begin{algorithm}
+ \caption{Deciding an unspecified integer part of a suffix component, for comparison purposes} \label{alg:version-comparison-suffix-missingint}
+ \begin{algorithmic}[1]
+ \STATE let $X$ refer to either $A$ or $B$, whichever version contains the suffix under question
+ \IF{$i+1<Xsn$ and $Xs_{i+1}$ is of type \t{-scm}}
+ \STATE let $Xs'_i$ be $\infty$
+ \ELSE
+ \STATE let $Xs'_i$ be \t{0}
+ \ENDIF
+ \end{algorithmic}
+ \end{algorithm}
}{
- A missing integer part is treated as zero.
}
-If at this point the two versions are still equal, the revision number is compared using strict
-integer comparison as per the previous part. If the revision numbers are equal, so are the two
-versions.
+\begin{algorithm}
+\caption{Version comparison logic for revision components} \label{alg:version-comparison-revision}
+\begin{algorithmic}[1]
+ \STATE let $Ar$ be the integer part of the revision component of $A$ if any, otherwise $\t{0}$
+ \STATE let $Br$ be the integer part of the revision component of $B$ if any, otherwise $\t{0}$
+ \IF{$Ar>Br$ using integer comparison}
+ \RETURN $A>B$
+ \ELSIF{$Ar<Br$ using integer comparison}
+ \RETURN $A<B$
+ \ENDIF
+\end{algorithmic}
+\end{algorithm}
\section{Uniqueness of versions}
--
1.6.4.4
^ permalink raw reply related [relevance 99%]
Results 1-1 of 1 | reverse | options above
-- pct% links below jump to the message on this page, permalinks otherwise --
2009-10-17 20:21 99% [gentoo-pms] [PATCH] Rewrite version comparison rules in pseudocode David Leverton
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox