* [gentoo-pms] [PATCH] Rewrite version comparison rules in pseudocode @ 2009-10-17 20:21 David Leverton 2009-10-17 23:21 ` [gentoo-pms] [PATCH 1/2] " David Leverton 0 siblings, 1 reply; 9+ messages in thread 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 [flat|nested] 9+ messages in thread
* [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode 2009-10-17 20:21 [gentoo-pms] [PATCH] Rewrite version comparison rules in pseudocode David Leverton @ 2009-10-17 23:21 ` David Leverton 2009-10-17 23:21 ` [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison David Leverton 2009-10-18 17:45 ` [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode Christian Faulhammer 0 siblings, 2 replies; 9+ messages in thread From: David Leverton @ 2009-10-17 23: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 | 221 +++++++++++++++++++++++++++++++++++++++----------- pkg-mgr-commands.tex | 4 +- pms.cls | 2 +- 3 files changed, 175 insertions(+), 52 deletions(-) Updated to match the old wording for -scm diff --git a/names.tex b/names.tex index 7bd572d..c75c2c1 100644 --- a/names.tex +++ b/names.tex @@ -93,63 +93,186 @@ 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$} + \IFKDEBUILDELSE{ + \IF{$B$ has any suffixes and no letter, and its first suffix is \t{-scm}} + \RETURN $A<B$ + \ELSE + \RETURN $A>B$ + \ENDIF + }{ + \RETURN $A>B$ + } + \ELSIF{$Ann<Bnn$} + \IFKDEBUILDELSE{ + \IF{$A$ has any suffixes and no letter, and its first suffix is \t{-scm}} + \RETURN $A>B$ + \ELSE + \RETURN $A<B$ + \ENDIF + }{ + \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} diff --git a/pkg-mgr-commands.tex b/pkg-mgr-commands.tex index ff2b9a6..7a5fdac 100644 --- a/pkg-mgr-commands.tex +++ b/pkg-mgr-commands.tex @@ -340,8 +340,8 @@ that can be passed to \t{dohtml} are as follows: \t{INSDESTTREE}, by default with file mode \t{0644}. This can be overridden by setting \t{INSOPTIONS} with the \t{insopts} function. If the first argument is \t{-r}, then operates recursively, descending into any directories given. For EAPIs listed in - table~\ref{tab:doins-table}, \t{doins} must install symlinks as symlinks; - for other EAPIs, behaviour is undefined if any symlink is encountered. Failure + table~\ref{tab:doins-table}, \t{doins} must install symlinks as symlinks when installing + recursively; for other EAPIs, behaviour is undefined if any symlink is encountered. Failure behaviour is EAPI dependent as per section~\ref{sec:failure-behaviour}. \item[dolib] For each argument, installs it into the appropriate library directory as determined by diff --git a/pms.cls b/pms.cls index 05d44b0..df15108 100644 --- a/pms.cls +++ b/pms.cls @@ -100,7 +100,7 @@ % Enable the below option if you'd like to see both sides of KDEBUILD % conditionals shown in different colours. Disable it to either fully % enable or fully disable KDEBUILD. Not compatible with HTML output. -\setboolean{ENABLE-ALL-OPTIONS}{false} +\setboolean{ENABLE-ALL-OPTIONS}{true} % Enable the below if you'd like to see KDEBUILD things. \setboolean{ENABLE-KDEBUILD}{true} -- 1.6.4.4 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison 2009-10-17 23:21 ` [gentoo-pms] [PATCH 1/2] " David Leverton @ 2009-10-17 23:21 ` David Leverton 2009-10-18 17:45 ` [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode Christian Faulhammer 1 sibling, 0 replies; 9+ messages in thread From: David Leverton @ 2009-10-17 23:21 UTC (permalink / raw To: gentoo-pms; +Cc: David Leverton --- names.tex | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) Sending this separately because it's a change in logic from the old wording. diff --git a/names.tex b/names.tex index c75c2c1..5738a50 100644 --- a/names.tex +++ b/names.tex @@ -191,8 +191,8 @@ from which it was invoked. \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 + \STATE let $Al$ be the letter component of $A$ if any, \IFKDEBUILDELSE{otherwise \t{zz} if $A$ has any suffixes and its first suffix is \t{-scm}, }{}otherwise the empty string + \STATE let $Bl$ be the letter component of $B$ if any, \IFKDEBUILDELSE{otherwise \t{zz} if $B$ has any suffixes and its first suffix is \t{-scm}, }{}otherwise the empty string \IF{$Al>Bl$ using ASCII stringwise comparison} \RETURN $A>B$ \ELSIF{$Al<Bl$ using ASCII stringwise comparison} -- 1.6.4.4 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode 2009-10-17 23:21 ` [gentoo-pms] [PATCH 1/2] " David Leverton 2009-10-17 23:21 ` [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison David Leverton @ 2009-10-18 17:45 ` Christian Faulhammer 2009-10-19 17:19 ` David Leverton 1 sibling, 1 reply; 9+ messages in thread From: Christian Faulhammer @ 2009-10-18 17:45 UTC (permalink / raw To: gentoo-pms [-- Attachment #1: Type: text/plain, Size: 1069 bytes --] Hi, I like the better readability of algorithmic presentation, but its wording is not entirely clear, but maybe I am wrong from solely patch reading. So those are algorithms for the comparison of components (separated by dots). For me it read on first try like a comparison of the whole version string, maybe an introducing sentence like the one you removed is suited: -Version specifications are compared component by component, moving from left to right. David Leverton <levertond@googlemail.com>: > --- a/pms.cls > +++ b/pms.cls > @@ -100,7 +100,7 @@ > % Enable the below option if you'd like to see both sides of KDEBUILD > % conditionals shown in different colours. Disable it to either fully > % enable or fully disable KDEBUILD. Not compatible with HTML output. > -\setboolean{ENABLE-ALL-OPTIONS}{false} > +\setboolean{ENABLE-ALL-OPTIONS}{true} Is this intended? V-Li -- Christian Faulhammer, Gentoo Lisp project <URL:http://www.gentoo.org/proj/en/lisp/>, #gentoo-lisp on FreeNode <URL:http://gentoo.faulhammer.org/> [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 198 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode 2009-10-18 17:45 ` [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode Christian Faulhammer @ 2009-10-19 17:19 ` David Leverton 2009-10-22 14:52 ` Christian Faulhammer 0 siblings, 1 reply; 9+ messages in thread From: David Leverton @ 2009-10-19 17:19 UTC (permalink / raw To: gentoo-pms On Sunday 18 October 2009 18:45:23 Christian Faulhammer wrote: > Hi, > > I like the better readability of algorithmic presentation, but its > wording is not entirely clear, but maybe I am wrong from solely > patch reading. So those are algorithms for the comparison of > components (separated by dots). For me it read on first try like a > comparison of the whole version string, maybe an introducing sentence > like the one you removed is suited: Not quite sure what you mean by that... it is an algorithm for the whole comparison, but it's broken up for readability. > -Version specifications are compared component by component, moving > from left to right. Maybe "Version specifications are compared component by component, moving from left to right, as detailed in Algorithm 1"? > David Leverton <levertond@googlemail.com>: > > --- a/pms.cls > > +++ b/pms.cls > > @@ -100,7 +100,7 @@ > > % Enable the below option if you'd like to see both sides of KDEBUILD > > % conditionals shown in different colours. Disable it to either fully > > % enable or fully disable KDEBUILD. Not compatible with HTML output. > > -\setboolean{ENABLE-ALL-OPTIONS}{false} > > +\setboolean{ENABLE-ALL-OPTIONS}{true} > > Is this intended? Oops. > V-Li ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode 2009-10-19 17:19 ` David Leverton @ 2009-10-22 14:52 ` Christian Faulhammer 2009-11-03 18:11 ` David Leverton 0 siblings, 1 reply; 9+ messages in thread From: Christian Faulhammer @ 2009-10-22 14:52 UTC (permalink / raw To: gentoo-pms [-- Attachment #1: Type: text/plain, Size: 435 bytes --] Hi, > > -Version specifications are compared component by component, moving > > from left to right. > > Maybe "Version specifications are compared component by component, > moving from left to right, as detailed in Algorithm 1"? Yes, that would be great. V-Li -- Christian Faulhammer, Gentoo Lisp project <URL:http://www.gentoo.org/proj/en/lisp/>, #gentoo-lisp on FreeNode <URL:http://gentoo.faulhammer.org/> [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 198 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
* [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode 2009-10-22 14:52 ` Christian Faulhammer @ 2009-11-03 18:11 ` David Leverton 2009-11-03 18:11 ` [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison David Leverton 0 siblings, 1 reply; 9+ messages in thread From: David Leverton @ 2009-11-03 18:11 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 | 222 +++++++++++++++++++++++++++++++++++++++++++++++-------------- 1 files changed, 173 insertions(+), 49 deletions(-) Sorry for slacking on this, life tends to be a distraction. diff --git a/names.tex b/names.tex index 7bd572d..be155ad 100644 --- a/names.tex +++ b/names.tex @@ -93,63 +93,187 @@ 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 specifications are compared component by component, moving from left to right, +as detailed in 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$} + \IFKDEBUILDELSE{ + \IF{$B$ has any suffixes and no letter, and its first suffix is \t{-scm}} + \RETURN $A<B$ + \ELSE + \RETURN $A>B$ + \ENDIF + }{ + \RETURN $A>B$ + } + \ELSIF{$Ann<Bnn$} + \IFKDEBUILDELSE{ + \IF{$A$ has any suffixes and no letter, and its first suffix is \t{-scm}} + \RETURN $A>B$ + \ELSE + \RETURN $A<B$ + \ENDIF + }{ + \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 [flat|nested] 9+ messages in thread
* [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison 2009-11-03 18:11 ` David Leverton @ 2009-11-03 18:11 ` David Leverton 2009-11-03 18:31 ` Ciaran McCreesh 0 siblings, 1 reply; 9+ messages in thread From: David Leverton @ 2009-11-03 18:11 UTC (permalink / raw To: gentoo-pms; +Cc: David Leverton --- names.tex | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/names.tex b/names.tex index be155ad..f72bc98 100644 --- a/names.tex +++ b/names.tex @@ -192,8 +192,8 @@ from which it was invoked. \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 + \STATE let $Al$ be the letter component of $A$ if any, \IFKDEBUILDELSE{otherwise \t{zz} if $A$ has any suffixes and its first suffix is \t{-scm}, }{}otherwise the empty string + \STATE let $Bl$ be the letter component of $B$ if any, \IFKDEBUILDELSE{otherwise \t{zz} if $B$ has any suffixes and its first suffix is \t{-scm}, }{}otherwise the empty string \IF{$Al>Bl$ using ASCII stringwise comparison} \RETURN $A>B$ \ELSIF{$Al<Bl$ using ASCII stringwise comparison} -- 1.6.4.4 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison 2009-11-03 18:11 ` [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison David Leverton @ 2009-11-03 18:31 ` Ciaran McCreesh 0 siblings, 0 replies; 9+ messages in thread From: Ciaran McCreesh @ 2009-11-03 18:31 UTC (permalink / raw To: David Leverton; +Cc: gentoo-pms, David Leverton [-- Attachment #1: Type: text/plain, Size: 214 bytes --] On Tue, 3 Nov 2009 18:11:48 +0000 David Leverton <levertond@googlemail.com> wrote: > names.tex | 4 ++-- > 1 files changed, 2 insertions(+), 2 deletions(-) Applied both, thanks. -- Ciaran McCreesh [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 198 bytes --] ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2009-11-03 18:31 UTC | newest] Thread overview: 9+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2009-10-17 20:21 [gentoo-pms] [PATCH] Rewrite version comparison rules in pseudocode David Leverton 2009-10-17 23:21 ` [gentoo-pms] [PATCH 1/2] " David Leverton 2009-10-17 23:21 ` [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison David Leverton 2009-10-18 17:45 ` [gentoo-pms] [PATCH 1/2] Rewrite version comparison rules in pseudocode Christian Faulhammer 2009-10-19 17:19 ` David Leverton 2009-10-22 14:52 ` Christian Faulhammer 2009-11-03 18:11 ` David Leverton 2009-11-03 18:11 ` [gentoo-pms] [PATCH 2/2] Fix 1a versus 1-scm comparison David Leverton 2009-11-03 18:31 ` Ciaran McCreesh
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox