aboutsummaryrefslogtreecommitdiff
path: root/src/cpt-lib.in
diff options
context:
space:
mode:
authormerakor <cem@ckyln.com>2023-02-05 13:39:03 +0000
committermerakor <cem@ckyln.com>2023-02-05 13:39:03 +0000
commit1d8c311d19521f86a6221765b4a3992bf867813c (patch)
tree30d6ab0ed8706357bdcd889f84102472bed4c5e0 /src/cpt-lib.in
parent96f191fc91e66837fed2793ba7c43c45d8edac50 (diff)
downloadcpt-1d8c311d19521f86a6221765b4a3992bf867813c.tar.gz
use a tsort function compatible with POSIX and fix dependency
calculation issues FossilOrigin-Name: faa4f309950d79caab445296a3dfb3008552067e6ec7aeedd7ddef904a577b09
Diffstat (limited to 'src/cpt-lib.in')
-rw-r--r--src/cpt-lib.in128
1 files changed, 100 insertions, 28 deletions
diff --git a/src/cpt-lib.in b/src/cpt-lib.in
index 5a0d463..55a8688 100644
--- a/src/cpt-lib.in
+++ b/src/cpt-lib.in
@@ -88,32 +88,100 @@ _tsort() {
# 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
+ # implementations are correct according to the specification.
+ #
+ # The script below was taken from <https://gist.github.com/apainintheneck/1803fb91dde3ba048ec51d44fa6065a4>
+ #
+ # The MIT License (MIT)
+ # Copyright (c) 2023 Kevin Robell
+ #
+ # Permission is hereby granted, free of charge, to any person obtaining a
+ # copy of this software and associated documentation files (the “Software”),
+ # to deal in the Software without restriction, including without limitation
+ # the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ # and/or sell copies of the Software, and to permit persons to whom the
+ # Software is furnished to do so, subject to the following conditions:
+ #
+ # The above copyright notice and this permission notice shall be included in
+ # all copies or substantial portions of the Software.
+ #
+ # THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ # THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ # DEALINGS IN THE SOFTWARE.
+ awk '{
+ for (i = 1; i <= NF; ++i) {
+ # Store each node.
+ nodes[$i] = 1
+ if (is_child) {
+ child = $i
+ # Skip nodes that point to themselves.
+ # This traditionally means that the node
+ # is disconnected from the rest of the graph.
+ if (parent != child) {
+ # Store from parent to child.
+ idx = ++child_count[parent]
+ child_graph[parent, idx] = child
+ # Store count from child to parent.
+ ++parent_count[child]
+ }
+ } else {
+ parent = $i
+ }
+ # Flip switch
+ is_child = !is_child
+ }
}
- 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]
+ # Print errors to the stderr
+ stderr = "/dev/stderr"
+
+ # Sanity Check
+ if (is_child) {
+ print("Error: odd number of input values: expected pairs of values") > stderr
+ exit(1)
+ }
+
+ #####
+ # Topological Sort
+ #####
+
+ # Remove unconnected nodes first.
+ for (node in nodes) {
+ if (parent_count[node] == 0 && child_count[node] == 0) {
+ delete nodes[node]
+ print(node)
+ }
+ }
+
+ # Remove the rest of the nodes starting with those without parents.
+ while (length(nodes) > 0) {
+ removed_node = 0
+ for (node in nodes) {
+ # Delete and print nodes without any remaining parents.
+ if (parent_count[node] == 0) {
+ delete nodes[node]
+ removed_node = 1
+ # Decrease child_count for each parent node.
+ for (i = child_count[node]; i > 0; --i) {
+ child = child_graph[node, i]
+ --parent_count[child]
+ }
+ print(node)
}
- } c=el()
- } while (p != c)
- if (length(p)!=0) err(p);
- print pr
+ }
+
+ # If we havent removed any nodes, it means that there
+ # are no nodes without any remaining parents so we have
+ # a cycle.
+ if (!removed_node) {
+ print("Error: Cycle found") > stderr
+ exit(1)
+ }
+ }
}'
}
@@ -228,7 +296,7 @@ _get_digest() {
# function.
# URL: https://github.com/ko1nksm/getoptions (v2.5.0)
# License: Creative Commons Zero v1.0 Universal
-# shellcheck disable=2016,2086
+# shellcheck disable=2016,2086,2317
getoptions() {
_error='' _on=1 _off='' _export='' _plus='' _mode='' _alt='' _rest=''
_flags='' _nflags='' _opts='' _help='' _abbr='' _cmds='' _init=@empty IFS=' '
@@ -423,6 +491,7 @@ getoptions() {
}
# URL: https://github.com/ko1nksm/getoptions (v2.5.0)
# License: Creative Commons Zero v1.0 Universal
+# shellcheck disable=2317
getoptions_help() {
_width='30,12' _plus='' _leading=' '
@@ -904,8 +973,9 @@ 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 "$pkgs" "$1" || {
- pkgs="$pkgs $1 "
+ #
+ # shellcheck disable=2015
+ contains "$pkgs" "$1" && [ -z "$2" ] || {
[ "$2" = raw ] && _dep_append "$1" "$1"
while read -r dep type || [ "$dep" ]; do
# Skip comments and empty lines.
@@ -926,7 +996,7 @@ pkg_depends() {
if [ "$2" = explicit ] || [ "$3" ]; then
_dep_append "$dep" "$dep"
else
- _dep_append "$1" "$dep"
+ _dep_append "$dep" "$1"
fi
# Recurse through the dependencies of the child packages. Forward
@@ -938,6 +1008,7 @@ pkg_depends() {
fi
done 2>/dev/null < "$(pkg_find "$1")/depends" ||:
+ pkgs="$pkgs $1 "
}
}
@@ -2181,6 +2252,7 @@ pkg_gentree() (
esac
done
pkg_depends "$1" tree "$make_deps"
+ pkg_depends_commit
# Unless 'f' is given, pop the package from the list so that we don't list
# the package (for example if it's part of the base package list). Normally
@@ -2192,7 +2264,7 @@ pkg_gentree() (
# shellcheck disable=2086
[ -z "${2##*f*}" ] || deps=$(pop "$1" from $deps)
- eval set -- "$deps"
+ set -- $deps
pkg_order "$@"
if [ "$reverse" ]; then eval set -- "$redro"; else eval set -- "$order"; fi
[ "$1" ] || return 0