commit: 91dfeadf8408ca47b434c65753564b55a912f884
Author: Michał Górny <mgorny <AT> gentoo <DOT> org>
AuthorDate: Wed Sep 20 22:07:15 2017 +0000
Commit: Ulrich Müller <ulm <AT> gentoo <DOT> org>
CommitDate: Tue Sep 26 18:46:27 2017 +0000
URL: https://gitweb.gentoo.org/repo/gentoo.git/commit/?id=91dfeadf
eapi7-ver.eclass: Ultra-fast algo for comparison
eclass/eapi7-ver.eclass | 325 ++++++++++++++++++++++++++++++++----------------
1 file changed, 218 insertions(+), 107 deletions(-)
diff --git a/eclass/eapi7-ver.eclass b/eclass/eapi7-ver.eclass
index 1ad1cbe2edc..2644832574a 100644
--- a/eclass/eapi7-ver.eclass
+++ b/eclass/eapi7-ver.eclass
@@ -174,6 +174,81 @@ ver_rs() {
echo "${comp[*]}"
}
+# @FUNCTION: _ver_validate
+# @USAGE: <comp[0]>...
+# @DESCRIPTION:
+# Verify that the version component array passed as the argument
+# validates according to the PMS version rules. Returns 0 if it does,
+# 1 otherwise.
+_ver_validate() {
+ local prev=start
+
+ while [[ ${1} || ${2} ]]; do
+ local s=${1}
+ local c=${2}
+
+ if [[ -z ${s} ]]; then
+ if [[ ${c} == [0-9]* ]]; then
+ # number without preceding sep may be either:
+ case ${prev} in
+ # a. 1st version number
+ start) prev=numeric;;
+ # b. _foo suffix number
+ suffix) prev=suffix_num;;
+ # c. -rN revision number
+ revision) prev=revision_num;;
+ *) return 1;;
+ esac
+ elif [[ -n ${c} ]]; then
+ # letter without preceding sep = letter after
version
+ [[ ${prev} == numeric ]] || return 1
+ [[ ${#c} -eq 1 ]] || return 1
+ prev=letter
+ fi
+ elif [[ -z ${c} ]]; then
+ # trailing suffix?
+ return 1
+ elif [[ ${s} == . ]]; then
+ # number preceded by dot = numeric component
+ [[ ${prev} == numeric ]] || return 1
+ elif [[ ${s} == _ ]]; then
+ # _ implies _foo suffix
+ case ${prev} in
+ numeric|letter|suffix|suffix_num) ;;
+ *) return 1;;
+ esac
+
+ case ${c} in
+ alpha) ;;
+ beta) ;;
+ rc) ;;
+ pre) ;;
+ p) ;;
+ *) return 1;;
+ esac
+ prev=suffix
+ elif [[ ${s} == - ]]; then
+ # - implies revision
+ case ${prev} in
+ numeric|letter|suffix|suffix_num) ;;
+ *) return 1;;
+ esac
+
+ [[ ${c} == r ]] || return 1
+ prev=revision
+ else
+ return 1
+ fi
+
+ shift 2
+ done
+
+ # empty version string?
+ [[ ${prev} != start ]] || return 1
+
+ return 0
+}
+
# @FUNCTION: ver_test
# @USAGE: [<v1>] <op> <v2>
# @DESCRIPTION:
@@ -183,127 +258,163 @@ ver_rs() {
# revision parts), and the comparison is performed according to
# the algorithm specified in the PMS.
ver_test() {
- local v1 v2 op i tail result
- local -a v1comp v2comp
- local match=(
- "+([0-9])*(.+([0-9]))"
# numeric components
- "[a-z]"
# letter component
- "*(@(_alpha|_beta|_pre|_rc|_p)*([0-9]))" # suffixes
- "-r+([0-9])"
# revision
- )
-
- local LC_ALL=C shopt_save=$(shopt -p extglob)
- shopt -s extglob
-
- if [[ $# -eq 2 ]]; then
- v1=${PVR}
- elif [[ $# -eq 3 ]]; then
- v1=$1; shift
+ local LC_ALL=C
+ local va op vb
+
+ if [[ $# -eq 3 ]]; then
+ va=${1}
+ shift
else
- die "${FUNCNAME}: bad number of arguments"
+ va=${PVR}
fi
- op=$1
- v2=$2
+
+ [[ $# -eq 2 ]] || die "${FUNCNAME}: bad number of arguments"
+
+ op=${1}
+ vb=${2}
case ${op} in
-eq|-ne|-lt|-le|-gt|-ge) ;;
*) die "${FUNCNAME}: invalid operator: ${op}" ;;
esac
- # Test for both versions being valid, and split them into parts
- for (( i=0; i<4; i++ )); do
- tail=${v1##${match[i]}}
- v1comp[i]=${v1%"${tail}"}
- v1=${tail}
- tail=${v2##${match[i]}}
- v2comp[i]=${v2%"${tail}"}
- v2=${tail}
- done
- # There must not be any remaining tail, and the numeric part
- # must be non-empty. All other parts are optional.
- [[ -z ${v1} && -z ${v2} && -n ${v1comp[0]} && -n ${v2comp[0]} ]] \
- || die "${FUNCNAME}: invalid version"
-
- # Compare numeric components (PMS algorithm 3.2)
- _ver_cmp_num() {
- local a=(${1//./ }) b=(${2//./ })
- local an=${#a[@]} bn=${#b[@]}
- local i
- # First component
- [[ 10#${a[0]} -gt 10#${b[0]} ]] && return 2
- [[ 10#${a[0]} -lt 10#${b[0]} ]] && return 1
- for (( i=1; i<an && i<bn; i++ )); do
- # Other components (PMS algorithm 3.3)
- if [[ ${a[i]} == 0* || ${b[i]} == 0* ]]; then
- local ap=${a[i]%%*(0)} bp=${b[i]%%*(0)}
- [[ ${ap} > ${bp} ]] && return 2
- [[ ${ap} < ${bp} ]] && return 1
+ # explicitly strip -r0[00000...] to avoid overcomplexifying the algo
+ [[ ${va} == *-r0* && 10#${va#*-r} -eq 0 ]] && va=${va%-r*}
+ [[ ${vb} == *-r0* && 10#${vb#*-r} -eq 0 ]] && vb=${vb%-r*}
+
+ local comp compb
+ _ver_split "${vb}"
+ compb=( "${comp[@]}" )
+ _ver_split "${va}"
+
+ _ver_validate "${comp[@]}" || die "${FUNCNAME}: invalid version: ${va}"
+ _ver_validate "${compb[@]}" || die "${FUNCNAME}: invalid version: ${vb}"
+
+ local i sa sb ca cb wa wb result=0
+ for (( i = 0;; i += 2 )); do
+ sa=${comp[i]}
+ ca=${comp[i+1]}
+ sb=${compb[i]}
+ cb=${compb[i+1]}
+
+ # 1. determine the component type for Ca
+ if [[ -z ${sa} ]]; then
+ if [[ ${ca} == [0-9]* ]]; then
+ # number without preceding sep may be either:
+ # a. 1st version number
+ # b. _foo suffix number
+ # c. -rN revision number
+ # weight is irrelevant since (a) occurs
simultaneously,
+ # and (b)/(c) use weight of preceding component
+ wa=0
+ # method: plain numeric
+ m=pn
+ elif [[ -n ${ca} ]]; then
+ # letter without preceding sep = letter after
version
+ # weight below numeric, lexical method
+ wa=9
+ m=l
else
- [[ ${a[i]} -gt ${b[i]} ]] && return 2
- [[ ${a[i]} -lt ${b[i]} ]] && return 1
+ # empty == end of version string
+ # weight below all positive stuff but above
negative
+ wa=6
+ m=
fi
- done
- [[ ${an} -gt ${bn} ]] && return 2
- [[ ${an} -lt ${bn} ]] && return 1
- return 0
- }
-
- # Compare letter components (PMS algorithm 3.4)
- _ver_cmp_let() {
- local a=$1 b=$2
- [[ ${a} > ${b} ]] && return 2
- [[ ${a} < ${b} ]] && return 1
- return 0
- }
-
- # Compare suffixes (PMS algorithm 3.5)
- _ver_cmp_suf() {
- local a=(${1//_/ }) b=(${2//_/ })
- local an=${#a[@]} bn=${#b[@]}
- local i
- for (( i=0; i<an && i<bn; i++ )); do
- # Compare each suffix (PMS algorithm 3.6)
- if [[ ${a[i]%%*([0-9])} == "${b[i]%%*([0-9])}" ]]; then
- [[ 10#${a[i]##*([a-z])} -gt
10#${b[i]##*([a-z])} ]] && return 2
- [[ 10#${a[i]##*([a-z])} -lt
10#${b[i]##*([a-z])} ]] && return 1
+ elif [[ ${sa} == . ]]; then
+ # number preceded by dot = numeric component
+ # highest weight, weird PMS 2+ component comparison
+ wa=10
+ m=wn
+ elif [[ ${sa} == _ ]]; then
+ # _ implies _foo suffix
+ # weights differ, comparison by weight
+ case ${ca} in
+ alpha) wa=2 ;;
+ beta) wa=3 ;;
+ rc) wa=4 ;;
+ pre) wa=5 ;;
+ p) wa=8 ;;
+ *) die "Invalid version suffix: _${ca}";;
+ esac
+ m=
+ elif [[ ${sa} == - ]]; then
+ # - implies revision
+ # weight below positive suffixes, no comparison
+ [[ ${ca} == r ]] || die "Invalid version part: -${ca}"
+ wa=7
+ m=
+ fi
+
+ # 2. determine the component type for Cb
+ if [[ -z ${sb} ]]; then
+ if [[ ${cb} == [0-9]* ]]; then
+ wb=0
+ elif [[ -n ${cb} ]]; then
+ wb=9
else
- # Check for p first
- [[ ${a[i]} == p*([0-9]) ]] && return 2
- [[ ${b[i]} == p*([0-9]) ]] && return 1
- # Hack: Use that alpha < beta < pre < rc
alphabetically
- [[ ${a[i]} > ${b[i]} ]] && return 2 || return 1
+ wb=6
fi
- done
- if [[ ${an} -gt ${bn} ]]; then
- [[ ${a[bn]} == p*([0-9]) ]] && return 2 || return 1
- elif [[ ${an} -lt ${bn} ]]; then
- [[ ${b[an]} == p*([0-9]) ]] && return 1 || return 2
+ elif [[ ${sb} == . ]]; then
+ wb=10
+ elif [[ ${sb} == _ ]]; then
+ case ${cb} in
+ alpha) wb=2 ;;
+ beta) wb=3 ;;
+ rc) wb=4 ;;
+ pre) wb=5 ;;
+ p) wb=8 ;;
+ *) die "Invalid version suffix: _${cb}";;
+ esac
+ elif [[ ${sb} == - ]]; then
+ [[ ${cb} == r ]] || die "Invalid version part: -${cb}"
+ wb=7
fi
- return 0
- }
-
- # Compare revision components (PMS algorithm 3.7)
- _ver_cmp_rev() {
- local a=${1#-r} b=${2#-r}
- [[ 10#${a} -gt 10#${b} ]] && return 2
- [[ 10#${a} -lt 10#${b} ]] && return 1
- return 0
- }
-
- # Version comparison top-level logic (PMS algorithm 3.1)
- _ver_cmp_num "${v1comp[0]}" "${v2comp[0]}" &&
- _ver_cmp_let "${v1comp[1]}" "${v2comp[1]}" &&
- _ver_cmp_suf "${v1comp[2]}" "${v2comp[2]}" &&
- _ver_cmp_rev "${v1comp[3]}" "${v2comp[3]}"
-
- case $? in
- 0) result=0 ;; # a = b
- 1) result=-1 ;; # a < b
- 2) result=1 ;; # a > b
- *) die "${FUNCNAME}: invalid return code: $?" ;;
- esac
- ${shopt_save}
+ # DEBUG
+ #echo "$sa $ca [$wa] <$m> $sb $cb [$wb]" >&2
+
+ # 3. compare weights, we can proceed further only if weights
match
+ if [[ ${wa} -ne ${wb} ]]; then
+ result=$(( wa - wb ))
+ break
+ fi
+
+ # 4. both empty maybe?
+ [[ -z ${ca} && -z ${cb} ]] && break
+
+ # 5. compare components according to the algo
+
+ # weird numeric is weird and reuses pn/l, so do it first
+ # (PMS algo 3.3)
+ if [[ ${m} == wn ]]; then
+ if [[ ${ca} != 0* && ${cb} != 0* ]]; then
+ # if neither of them starts with 0, use normal
numeric
+ m=pn
+ else
+ # strip trailing zeros
+ while [[ ${ca} == *0 ]]; do ca=${ca::-1}; done
+ while [[ ${cb} == *0 ]]; do cb=${cb::-1}; done
+ m=l
+ fi
+ fi
+
+ case ${m} in
+ pn) # plain numeric
+ if [[ 10#${ca} -ne 10#${cb} ]]; then
+ result=$(( 10#${ca} - 10#${cb} ))
+ break
+ fi
+ ;;
+ l) # lexical
+ if [[ ${ca} != ${cb} ]]; then
+ [[ ${ca} > ${cb} ]] && result=1 ||
result=-1
+ break
+ fi
+ ;;
+ '') ;;
+ *) die "Unexpected comparison method m=${m}";;
+ esac
+ done
test "${result}" "${op}" 0
}
