-- 
cgit v1.2.3

From 667a5f7be3e01b0ccbb56098e37cf4153b2b3121 Mon Sep 17 00:00:00 2001
From: merakor <cem@ckyln.com>
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(-)

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 <cem@ckyln.com>
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(-)

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 <cem@ckyln.com>
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(-)

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