From 667a5f7be3e01b0ccbb56098e37cf4153b2b3121 Mon Sep 17 00:00:00 2001 From: merakor Date: Mon, 25 Oct 2021 14:56:45 +0000 Subject: initial tsort implementation FossilOrigin-Name: a1935da292ffec854437cbaf527b715e94d9c25ff9afd6af791261f8698958c1 --- src/cpt-lib.in | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 59 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/cpt-lib.in b/src/cpt-lib.in index 09b78e1..32ce2e1 100644 --- a/src/cpt-lib.in +++ b/src/cpt-lib.in @@ -76,6 +76,43 @@ colors_enabled() { esac } +_tsort() { + # Return a linear reverse topological sort of the piped input, so we + # generate a proper build order. Returns 1 if a dependency cycle occurs. + # + # I was really excited when I saw POSIX specified a tsort(1) implementation, + # but the specification is quite vague, it doesn't specify cycles as a + # reason of error, and implementations differ on how it's handled. coreutils + # tsort(1) exits with an error, while openbsd tsort(1) doesn't. Both + # implementations are correct according to the specification. This leaves us + # with the following awk script, because the POSIX shell is not up for the + # job without super ugly hacks. + awk 'function fv(s) { + for (sp in e) { + split (e[sp],t) + for (j in t) if (s == t[j]) return 0 + } return 1 + } + function el(_l) {for(i in e){_l=_l" "i;}; return _l;} + function ce(t) {if (!(t in e)) e[t]="";} + function err(s) {print "Dependency cycle deteced between: " s; exit 1;} + {ce($1);$1!=$2&&e[$1]=e[$1]" "$2;} + END { + do {p=el() + for (s in e) { + if (fv(s)) { + pr=s" "pr + split(e[s],t) + for(i in t){ce(t[i]);} + delete e[s] + } + } c=el() + } while (p != c) + if (length(p)!=0) err(p); + print pr + }' +} + trap_set() { # Function to set the trap value. case ${1:-cleanup} in @@ -845,12 +882,8 @@ pkg_depends() { # Resolve all dependencies and generate an ordered list. # This does a depth-first search. The deepest dependencies are # listed first and then the parents in reverse order. - contains "$deps" "$1" || { - # Filter out non-explicit, aleady installed dependencies. - # Only filter installed if called from 'pkg_build()'. - [ "$pkg_build" ] && [ -z "$2" ] && - (pkg_list "$1" >/dev/null) && return - + contains "$pkgs" "$1" || { + pkgs="$pkgs $1 " while read -r dep type || [ "$dep" ]; do # Skip comments and empty lines. [ "${dep##\#*}" ] || continue @@ -863,6 +896,18 @@ pkg_depends() { make) [ "$2" = tree ] && [ -z "${3#first-nomake}" ] && continue esac + # Filter out non-explicit, already installed dependencies if called + # from 'pkg_build()'. + [ "$pkg_build" ] && (pkg_list "$1" >/dev/null) && continue + + if [ "$2" = explicit ] || [ "$3" ]; then + dep_graph="$dep_graph + $dep $dep" + else + dep_graph="$dep_graph + $1 $dep" + fi + # Recurse through the dependencies of the child packages. Forward # the 'tree' operation. if [ "$2" = tree ]; then @@ -872,12 +917,14 @@ pkg_depends() { fi done 2>/dev/null < "$(pkg_find "$1")/depends" ||: - # After child dependencies are added to the list, - # add the package which depends on them. - [ "$2" = explicit ] || [ "$3" ] || deps="$deps $1 " } } +pkg_depends_commit() { + # Set deps, and cleanup dep_graph, pkgs + deps=$(printf '%s\n' "$dep_graph" | _tsort) dep_graph='' pkgs='' || warn "Dependency cycle detected" +} + pkg_order() { # Order a list of packages based on dependence and # take into account pre-built tarballs if this is @@ -888,6 +935,7 @@ pkg_order() { *.tar.*) deps="$deps $pkg " ;; *) pkg_depends "$pkg" raw esac done + pkg_depends_commit # Filter the list, only keeping explicit packages. # The purpose of these two loops is to order the @@ -1087,6 +1135,7 @@ pkg_build() { # separately from those detected as dependencies. explicit="$explicit $pkg " } done + pkg_depends_commit [ "$pkg_update" ] || explicit_build=$explicit @@ -2126,6 +2175,7 @@ _tmp_cp() { _tmp_create() { # Create given file to the temporary directory and return its name + create_tmp _ret=$(_tmp_name "$1") # False positive, we are not reading from the file. # shellcheck disable=2094 -- cgit v1.2.3 From eb16aede0f1d7c1c35f552181879fe794ebe7087 Mon Sep 17 00:00:00 2001 From: merakor Date: Mon, 25 Oct 2021 22:03:22 +0000 Subject: _tsort: fix implementation FossilOrigin-Name: 0f8ddafd39ca827197f99011564d0b4de9a62dce151e12914a7da9385ac3e369 --- src/cpt-lib.in | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/cpt-lib.in b/src/cpt-lib.in index 32ce2e1..1280765 100644 --- a/src/cpt-lib.in +++ b/src/cpt-lib.in @@ -76,6 +76,10 @@ colors_enabled() { esac } +_dep_append() { + dep_graph=$(printf '%s\n%s %s\n' "$dep_graph" "$@" ;) +} + _tsort() { # Return a linear reverse topological sort of the piped input, so we # generate a proper build order. Returns 1 if a dependency cycle occurs. @@ -884,6 +888,7 @@ pkg_depends() { # listed first and then the parents in reverse order. contains "$pkgs" "$1" || { pkgs="$pkgs $1 " + [ "$2" = raw ] && _dep_append "$1" "$1" while read -r dep type || [ "$dep" ]; do # Skip comments and empty lines. [ "${dep##\#*}" ] || continue @@ -898,14 +903,12 @@ pkg_depends() { # Filter out non-explicit, already installed dependencies if called # from 'pkg_build()'. - [ "$pkg_build" ] && (pkg_list "$1" >/dev/null) && continue + [ "$pkg_build" ] && (pkg_list "$dep" >/dev/null) && continue if [ "$2" = explicit ] || [ "$3" ]; then - dep_graph="$dep_graph - $dep $dep" + _dep_append "$dep" "$dep" else - dep_graph="$dep_graph - $1 $dep" + _dep_append "$1" "$dep" fi # Recurse through the dependencies of the child packages. Forward @@ -932,7 +935,7 @@ pkg_order() { order=; redro=; deps= for pkg do case $pkg in - *.tar.*) deps="$deps $pkg " ;; + *.tar.*) _dep_append "$pkg" "$pkg" ;; *) pkg_depends "$pkg" raw esac done pkg_depends_commit -- cgit v1.2.3 From 731f0c9d775b2cbb6fa77d8bbe1c505b16fa6abf Mon Sep 17 00:00:00 2001 From: merakor Date: Thu, 4 Nov 2021 12:34:27 +0000 Subject: sepchar: simplify FossilOrigin-Name: 45602b1963d7ef0f2e3ec7489883e14803a8881798339fe2a61701305451abc0 --- src/cpt-lib.in | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) (limited to 'src') diff --git a/src/cpt-lib.in b/src/cpt-lib.in index 1280765..b01790d 100644 --- a/src/cpt-lib.in +++ b/src/cpt-lib.in @@ -132,20 +132,16 @@ trap_set() { esac } -sepchar() ( +sepchar() { # Seperate every character on the given string without resorting to external # processes. [ "$1" ] || return 0; str=$1; set -- while [ "$str" ]; do - str_tmp=$str - for i in $(_seq $(( ${#str} - 1 ))); do - str_tmp=${str_tmp%?} - done - set -- "$@" "$str_tmp" - str=${str#$str_tmp} + set -- "$@" "${str%${str#?}}" + str=${str#?} done printf '%s\n' "$@" -) +} _re() { # Check that the string supplied in $2 conforms to the regular expression -- cgit v1.2.3