[PR PATCH] common/scripts: import xbps-cycles.

[PR PATCH] common/scripts: import xbps-cycles.

[ericonr]

[-- Attachment #1: Type: text/plain, Size: 1750 bytes --]

There is a new pull request by ericonr against master on the void-packages repository

https://github.com/ericonr/void-packages cycles
https://github.com/void-linux/void-packages/pull/31631

common/scripts: import xbps-cycles.
From https://github.com/ahesford/xbps-cycles, license is compatible with
void-packages. Will be run in CI, so it should live in the same
repository.

<!-- Mark items with [x] where applicable -->

#### General
- [ ] This is a new package and it conforms to the [quality requirements](https://github.com/void-linux/void-packages/blob/master/Manual.md#quality-requirements)

#### Have the results of the proposed changes been tested?
- [ ] I use the packages affected by the proposed changes on a regular basis and confirm this PR works for me
- [ ] I generally don't use the affected packages but briefly tested this PR

<!--
If GitHub CI cannot be used to validate the build result (for example, if the
build is likely to take several hours), make sure to
[skip CI](https://github.com/void-linux/void-packages/blob/master/CONTRIBUTING.md#continuous-integration).
When skipping CI, uncomment and fill out the following section.
Note: for builds that are likely to complete in less than 2 hours, it is not
acceptable to skip CI.
-->
<!-- 
#### Does it build and run successfully? 
(Please choose at least one native build and, if supported, at least one cross build. More are better.)
- [ ] I built this PR locally for my native architecture, (ARCH-LIBC)
- [ ] I built this PR locally for these architectures (if supported. mark crossbuilds):
  - [ ] aarch64-musl
  - [ ] armv7l
  - [ ] armv6l-musl
-->


A patch file from https://github.com/void-linux/void-packages/pull/31631.patch is attached

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: github-pr-cycles-31631.patch --]
[-- Type: text/x-diff, Size: 5196 bytes --]

From a7e3cdb63b7e681158db4f57c75204c7d0cccc53 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:39:19 -0300
Subject: [PATCH] common/scripts: import xbps-cycles.

From https://github.com/ahesford/xbps-cycles, license is compatible with
void-packages. Will be run in CI, so it should live in the same
repository.
---
 common/scripts/README.xbps-cycles.md |  23 ++++++
 common/scripts/xbps-cycles.py        | 102 +++++++++++++++++++++++++++
 2 files changed, 125 insertions(+)
 create mode 100644 common/scripts/README.xbps-cycles.md
 create mode 100755 common/scripts/xbps-cycles.py

diff --git a/common/scripts/README.xbps-cycles.md b/common/scripts/README.xbps-cycles.md
new file mode 100644
index 000000000000..458f3787278b
--- /dev/null
+++ b/common/scripts/README.xbps-cycles.md
@@ -0,0 +1,23 @@
+# Cycle detector for void-packages
+
+This script enumerates dependencies for packages in a
+[void-packages repository](https://github.com/void-linux/void-packages)
+and identifies build-time dependency cycles. It is based on 
+[earlier scripts](https://gist.github.com/Chocimier/de76441493ec7775c201dac0bb03ced5)
+provided by the Void maintainer @Chocimier. The key differences are
+- No intermediate files are created
+- Dependency enumeration is parallelized by default
+- Output provides a more illustrative view of cycles
+
+For command syntax, run `xbps-cycles.py -h`. Often, it may be sufficient to run
+`xbps-cycles.py` with no arguments. By default, the script will look for a
+repository at `$XBPS_DISTDIR`; if that variable is not defined, the current
+directory is used instead. To override this behavior, use the `-d` option to
+provide the path to your desired void-packages clone.
+
+The standard behavior will be to spawn multiple processes, one per CPU, to
+enumerate package dependencies. This is by far the most time-consuming part of
+the execution. To override the degree of parallelism, use the `-j` option.
+
+Failures should be harmless but, at this early stage, unlikely to be pretty or
+even helpful.
diff --git a/common/scripts/xbps-cycles.py b/common/scripts/xbps-cycles.py
new file mode 100755
index 000000000000..24ef17156336
--- /dev/null
+++ b/common/scripts/xbps-cycles.py
@@ -0,0 +1,102 @@
+#!/usr/bin/env python3
+
+import os
+import sys
+import glob
+import subprocess
+import multiprocessing
+
+from argparse import ArgumentParser
+
+import networkx as nx
+
+
+def enum_depends(pkg, xbpsdir):
+	'''
+	Return a pair (pkg, [dependencies]), where [dependencies] is the list
+	of dependencies for the given package pkg. The argument xbpsdir should
+	be a path to a void-packages repository. Dependencies will be
+	determined by invoking
+
+		<xbpsdir>/xbps-src show-build-deps <pkg>
+
+	If the return code of this call nonzero, a message will be printed but
+	the package will treated as if it has no dependencies.
+	'''
+	cmd = [os.path.join(xbpsdir, 'xbps-src'), 'show-build-deps', pkg]
+
+	try:
+		deps = subprocess.check_output(cmd)
+	except subprocess.CalledProcessError as err:
+		print('xbps-src failed to find dependencies for package', pkg) 
+		deps = [ ]
+	else:
+		deps = [d for d in deps.decode('utf-8').split('\n') if d]
+
+	return pkg, deps
+
+
+def find_cycles(depmap, xbpsdir):
+	'''
+	For a map depmap: package -> [dependencies], construct a directed graph
+	and identify any cycles therein.
+
+	The argument xbpsdir should be a path to the root of a void-packages
+	repository. All package names in depmap will be appended to the path
+	<xbpsdir>/srcpkgs and reduced with os.path.realpath to coalesce
+	subpackages.
+	'''
+	G = nx.DiGraph()
+
+	for i, deps in depmap.items():
+		path = os.path.join(xbpsdir, 'srcpkgs', i)
+		i = os.path.basename(os.path.realpath(path))
+
+		for j in deps:
+			path = os.path.join(xbpsdir, 'srcpkgs', j.strip())
+			j = os.path.basename(os.path.realpath(path))
+			G.add_edge(i, j)
+
+	for c in nx.strongly_connected_components(G):
+		if len(c) < 2: continue
+		pkgs = nx.to_dict_of_lists(G, c)
+
+		p = next(iter(pkgs.keys()))
+		cycles = [ ]
+		while True:
+			cycles.append(p)
+
+			# Cycle is complete when package is not in map
+			try: deps = pkgs.pop(p)
+			except KeyError: break
+
+		        # Any of the dependencies here contributes to a cycle
+			p = deps[0]
+			if len(deps) > 1:
+				print('Mulitpath: {} -> {}, choosing first'.format(p, deps))
+
+		if cycles:
+			print('Cycle: ' + ' -> '.join(cycles) + '\n')
+
+
+if __name__ == '__main__':
+	parser = ArgumentParser(description='Cycle detector for xbps-src')
+	parser.add_argument('-j', '--jobs', default=None,
+			type=int, help='Number of parallel jobs')
+	parser.add_argument('-d', '--directory',
+			default=None, help='Path to void-packages repo')
+
+	args = parser.parse_args()
+
+	if not args.directory:
+		try: args.directory = os.environ['XBPS_DISTDIR']
+		except KeyError: args.directory = '.'
+
+	pool = multiprocessing.Pool(processes = args.jobs)
+
+	pattern = os.path.join(args.directory, 'srcpkgs', '*')
+	depmap = dict(pool.starmap(enum_depends, 
+			((os.path.basename(g), args.directory)
+				for g in glob.iglob(pattern))))
+
+	find_cycles(depmap, args.directory)

Re: [PR PATCH] [Updated] common/scripts: import xbps-cycles.

[ericonr]

[-- Attachment #1: Type: text/plain, Size: 1755 bytes --]

There is an updated pull request by ericonr against master on the void-packages repository

https://github.com/ericonr/void-packages cycles
https://github.com/void-linux/void-packages/pull/31631

common/scripts: import xbps-cycles.
From https://github.com/ahesford/xbps-cycles, license is compatible with
void-packages. Will be run in CI, so it should live in the same
repository.

<!-- Mark items with [x] where applicable -->

#### General
- [ ] This is a new package and it conforms to the [quality requirements](https://github.com/void-linux/void-packages/blob/master/Manual.md#quality-requirements)

#### Have the results of the proposed changes been tested?
- [ ] I use the packages affected by the proposed changes on a regular basis and confirm this PR works for me
- [ ] I generally don't use the affected packages but briefly tested this PR

<!--
If GitHub CI cannot be used to validate the build result (for example, if the
build is likely to take several hours), make sure to
[skip CI](https://github.com/void-linux/void-packages/blob/master/CONTRIBUTING.md#continuous-integration).
When skipping CI, uncomment and fill out the following section.
Note: for builds that are likely to complete in less than 2 hours, it is not
acceptable to skip CI.
-->
<!-- 
#### Does it build and run successfully? 
(Please choose at least one native build and, if supported, at least one cross build. More are better.)
- [ ] I built this PR locally for my native architecture, (ARCH-LIBC)
- [ ] I built this PR locally for these architectures (if supported. mark crossbuilds):
  - [ ] aarch64-musl
  - [ ] armv7l
  - [ ] armv6l-musl
-->


A patch file from https://github.com/void-linux/void-packages/pull/31631.patch is attached

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: github-pr-cycles-31631.patch --]
[-- Type: text/x-diff, Size: 6382 bytes --]

From a7e3cdb63b7e681158db4f57c75204c7d0cccc53 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:39:19 -0300
Subject: [PATCH 1/2] common/scripts: import xbps-cycles.

From https://github.com/ahesford/xbps-cycles, license is compatible with
void-packages. Will be run in CI, so it should live in the same
repository.
---
 common/scripts/README.xbps-cycles.md |  23 ++++++
 common/scripts/xbps-cycles.py        | 102 +++++++++++++++++++++++++++
 2 files changed, 125 insertions(+)
 create mode 100644 common/scripts/README.xbps-cycles.md
 create mode 100755 common/scripts/xbps-cycles.py

diff --git a/common/scripts/README.xbps-cycles.md b/common/scripts/README.xbps-cycles.md
new file mode 100644
index 000000000000..458f3787278b
--- /dev/null
+++ b/common/scripts/README.xbps-cycles.md
@@ -0,0 +1,23 @@
+# Cycle detector for void-packages
+
+This script enumerates dependencies for packages in a
+[void-packages repository](https://github.com/void-linux/void-packages)
+and identifies build-time dependency cycles. It is based on 
+[earlier scripts](https://gist.github.com/Chocimier/de76441493ec7775c201dac0bb03ced5)
+provided by the Void maintainer @Chocimier. The key differences are
+- No intermediate files are created
+- Dependency enumeration is parallelized by default
+- Output provides a more illustrative view of cycles
+
+For command syntax, run `xbps-cycles.py -h`. Often, it may be sufficient to run
+`xbps-cycles.py` with no arguments. By default, the script will look for a
+repository at `$XBPS_DISTDIR`; if that variable is not defined, the current
+directory is used instead. To override this behavior, use the `-d` option to
+provide the path to your desired void-packages clone.
+
+The standard behavior will be to spawn multiple processes, one per CPU, to
+enumerate package dependencies. This is by far the most time-consuming part of
+the execution. To override the degree of parallelism, use the `-j` option.
+
+Failures should be harmless but, at this early stage, unlikely to be pretty or
+even helpful.
diff --git a/common/scripts/xbps-cycles.py b/common/scripts/xbps-cycles.py
new file mode 100755
index 000000000000..24ef17156336
--- /dev/null
+++ b/common/scripts/xbps-cycles.py
@@ -0,0 +1,102 @@
+#!/usr/bin/env python3
+
+import os
+import sys
+import glob
+import subprocess
+import multiprocessing
+
+from argparse import ArgumentParser
+
+import networkx as nx
+
+
+def enum_depends(pkg, xbpsdir):
+	'''
+	Return a pair (pkg, [dependencies]), where [dependencies] is the list
+	of dependencies for the given package pkg. The argument xbpsdir should
+	be a path to a void-packages repository. Dependencies will be
+	determined by invoking
+
+		<xbpsdir>/xbps-src show-build-deps <pkg>
+
+	If the return code of this call nonzero, a message will be printed but
+	the package will treated as if it has no dependencies.
+	'''
+	cmd = [os.path.join(xbpsdir, 'xbps-src'), 'show-build-deps', pkg]
+
+	try:
+		deps = subprocess.check_output(cmd)
+	except subprocess.CalledProcessError as err:
+		print('xbps-src failed to find dependencies for package', pkg) 
+		deps = [ ]
+	else:
+		deps = [d for d in deps.decode('utf-8').split('\n') if d]
+
+	return pkg, deps
+
+
+def find_cycles(depmap, xbpsdir):
+	'''
+	For a map depmap: package -> [dependencies], construct a directed graph
+	and identify any cycles therein.
+
+	The argument xbpsdir should be a path to the root of a void-packages
+	repository. All package names in depmap will be appended to the path
+	<xbpsdir>/srcpkgs and reduced with os.path.realpath to coalesce
+	subpackages.
+	'''
+	G = nx.DiGraph()
+
+	for i, deps in depmap.items():
+		path = os.path.join(xbpsdir, 'srcpkgs', i)
+		i = os.path.basename(os.path.realpath(path))
+
+		for j in deps:
+			path = os.path.join(xbpsdir, 'srcpkgs', j.strip())
+			j = os.path.basename(os.path.realpath(path))
+			G.add_edge(i, j)
+
+	for c in nx.strongly_connected_components(G):
+		if len(c) < 2: continue
+		pkgs = nx.to_dict_of_lists(G, c)
+
+		p = next(iter(pkgs.keys()))
+		cycles = [ ]
+		while True:
+			cycles.append(p)
+
+			# Cycle is complete when package is not in map
+			try: deps = pkgs.pop(p)
+			except KeyError: break
+
+		        # Any of the dependencies here contributes to a cycle
+			p = deps[0]
+			if len(deps) > 1:
+				print('Mulitpath: {} -> {}, choosing first'.format(p, deps))
+
+		if cycles:
+			print('Cycle: ' + ' -> '.join(cycles) + '\n')
+
+
+if __name__ == '__main__':
+	parser = ArgumentParser(description='Cycle detector for xbps-src')
+	parser.add_argument('-j', '--jobs', default=None,
+			type=int, help='Number of parallel jobs')
+	parser.add_argument('-d', '--directory',
+			default=None, help='Path to void-packages repo')
+
+	args = parser.parse_args()
+
+	if not args.directory:
+		try: args.directory = os.environ['XBPS_DISTDIR']
+		except KeyError: args.directory = '.'
+
+	pool = multiprocessing.Pool(processes = args.jobs)
+
+	pattern = os.path.join(args.directory, 'srcpkgs', '*')
+	depmap = dict(pool.starmap(enum_depends, 
+			((os.path.basename(g), args.directory)
+				for g in glob.iglob(pattern))))
+
+	find_cycles(depmap, args.directory)

From e9a46f7e3913456c2bc4ad840e0623c6f028bbbb Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:45:23 -0300
Subject: [PATCH 2/2] .github/workflows: run xbps-cycles daily.

Should help in catching cyclic dependencies early.

Rename lockthreads.yml to include all scheduled CI tasks.
---
 .github/workflows/{lockthreads.yml => cron.yml} | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
 rename .github/workflows/{lockthreads.yml => cron.yml} (61%)

diff --git a/.github/workflows/lockthreads.yml b/.github/workflows/cron.yml
similarity index 61%
rename from .github/workflows/lockthreads.yml
rename to .github/workflows/cron.yml
index f3ec106a6e6c..c87446743fe5 100644
--- a/.github/workflows/lockthreads.yml
+++ b/.github/workflows/cron.yml
@@ -1,4 +1,4 @@
-name: 'Lock threads'
+name: 'Scheduled tasks'
 
 on:
   schedule:
@@ -13,3 +13,8 @@ jobs:
           github-token: ${{ github.token }}
           pr-lock-inactive-days: '90'
           process-only: 'prs'
+  cycles:
+    runs-on: ubuntu-latest
+    steps:
+      - run: apt-get install -y python3-networkx
+      - run: common/scripts/xbps-cycles.py

Re: common/scripts: import xbps-cycles.

[ericonr]

[-- Attachment #1: Type: text/plain, Size: 203 bytes --]

New comment by ericonr on void-packages repository

https://github.com/void-linux/void-packages/pull/31631#issuecomment-866998992

Comment:
Probably won't work as is, should run inside a void container.

Re: [PR PATCH] [Updated] common/scripts: import xbps-cycles.

[Chocimier]

[-- Attachment #1: Type: text/plain, Size: 1757 bytes --]

There is an updated pull request by Chocimier against master on the void-packages repository

https://github.com/ericonr/void-packages cycles
https://github.com/void-linux/void-packages/pull/31631

common/scripts: import xbps-cycles.
From https://github.com/ahesford/xbps-cycles, license is compatible with
void-packages. Will be run in CI, so it should live in the same
repository.

<!-- Mark items with [x] where applicable -->

#### General
- [ ] This is a new package and it conforms to the [quality requirements](https://github.com/void-linux/void-packages/blob/master/Manual.md#quality-requirements)

#### Have the results of the proposed changes been tested?
- [ ] I use the packages affected by the proposed changes on a regular basis and confirm this PR works for me
- [ ] I generally don't use the affected packages but briefly tested this PR

<!--
If GitHub CI cannot be used to validate the build result (for example, if the
build is likely to take several hours), make sure to
[skip CI](https://github.com/void-linux/void-packages/blob/master/CONTRIBUTING.md#continuous-integration).
When skipping CI, uncomment and fill out the following section.
Note: for builds that are likely to complete in less than 2 hours, it is not
acceptable to skip CI.
-->
<!-- 
#### Does it build and run successfully? 
(Please choose at least one native build and, if supported, at least one cross build. More are better.)
- [ ] I built this PR locally for my native architecture, (ARCH-LIBC)
- [ ] I built this PR locally for these architectures (if supported. mark crossbuilds):
  - [ ] aarch64-musl
  - [ ] armv7l
  - [ ] armv6l-musl
-->


A patch file from https://github.com/void-linux/void-packages/pull/31631.patch is attached

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: github-pr-cycles-31631.patch --]
[-- Type: text/x-diff, Size: 9456 bytes --]

From ef724c4960027f7758f15952e8f5a85a1dba1673 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:39:19 -0300
Subject: [PATCH 1/4] common/scripts: import xbps-cycles.

From https://github.com/ahesford/xbps-cycles, that is based on
https://gist.github.com/Chocimier/de76441493ec7775c201dac0bb03ced5 .
License is compatible with void-packages. Will be run in CI, so it
should live in the same repository.
---
 common/scripts/README.xbps-cycles.md |  18 +++++
 common/scripts/xbps-cycles.py        | 102 +++++++++++++++++++++++++++
 2 files changed, 120 insertions(+)
 create mode 100644 common/scripts/README.xbps-cycles.md
 create mode 100755 common/scripts/xbps-cycles.py

diff --git a/common/scripts/README.xbps-cycles.md b/common/scripts/README.xbps-cycles.md
new file mode 100644
index 000000000000..075484829716
--- /dev/null
+++ b/common/scripts/README.xbps-cycles.md
@@ -0,0 +1,18 @@
+# Cycle detector for void-packages
+
+This script enumerates dependencies for packages in a
+[void-packages repository](https://github.com/void-linux/void-packages)
+and identifies build-time dependency cycles.
+
+For command syntax, run `xbps-cycles.py -h`. Often, it may be sufficient to run
+`xbps-cycles.py` with no arguments. By default, the script will look for a
+repository at `$XBPS_DISTDIR`; if that variable is not defined, the current
+directory is used instead. To override this behavior, use the `-d` option to
+provide the path to your desired void-packages clone.
+
+The standard behavior will be to spawn multiple processes, one per CPU, to
+enumerate package dependencies. This is by far the most time-consuming part of
+the execution. To override the degree of parallelism, use the `-j` option.
+
+Failures should be harmless but, at this early stage, unlikely to be pretty or
+even helpful.
diff --git a/common/scripts/xbps-cycles.py b/common/scripts/xbps-cycles.py
new file mode 100755
index 000000000000..24ef17156336
--- /dev/null
+++ b/common/scripts/xbps-cycles.py
@@ -0,0 +1,102 @@
+#!/usr/bin/env python3
+
+import os
+import sys
+import glob
+import subprocess
+import multiprocessing
+
+from argparse import ArgumentParser
+
+import networkx as nx
+
+
+def enum_depends(pkg, xbpsdir):
+	'''
+	Return a pair (pkg, [dependencies]), where [dependencies] is the list
+	of dependencies for the given package pkg. The argument xbpsdir should
+	be a path to a void-packages repository. Dependencies will be
+	determined by invoking
+
+		<xbpsdir>/xbps-src show-build-deps <pkg>
+
+	If the return code of this call nonzero, a message will be printed but
+	the package will treated as if it has no dependencies.
+	'''
+	cmd = [os.path.join(xbpsdir, 'xbps-src'), 'show-build-deps', pkg]
+
+	try:
+		deps = subprocess.check_output(cmd)
+	except subprocess.CalledProcessError as err:
+		print('xbps-src failed to find dependencies for package', pkg) 
+		deps = [ ]
+	else:
+		deps = [d for d in deps.decode('utf-8').split('\n') if d]
+
+	return pkg, deps
+
+
+def find_cycles(depmap, xbpsdir):
+	'''
+	For a map depmap: package -> [dependencies], construct a directed graph
+	and identify any cycles therein.
+
+	The argument xbpsdir should be a path to the root of a void-packages
+	repository. All package names in depmap will be appended to the path
+	<xbpsdir>/srcpkgs and reduced with os.path.realpath to coalesce
+	subpackages.
+	'''
+	G = nx.DiGraph()
+
+	for i, deps in depmap.items():
+		path = os.path.join(xbpsdir, 'srcpkgs', i)
+		i = os.path.basename(os.path.realpath(path))
+
+		for j in deps:
+			path = os.path.join(xbpsdir, 'srcpkgs', j.strip())
+			j = os.path.basename(os.path.realpath(path))
+			G.add_edge(i, j)
+
+	for c in nx.strongly_connected_components(G):
+		if len(c) < 2: continue
+		pkgs = nx.to_dict_of_lists(G, c)
+
+		p = next(iter(pkgs.keys()))
+		cycles = [ ]
+		while True:
+			cycles.append(p)
+
+			# Cycle is complete when package is not in map
+			try: deps = pkgs.pop(p)
+			except KeyError: break
+
+		        # Any of the dependencies here contributes to a cycle
+			p = deps[0]
+			if len(deps) > 1:
+				print('Mulitpath: {} -> {}, choosing first'.format(p, deps))
+
+		if cycles:
+			print('Cycle: ' + ' -> '.join(cycles) + '\n')
+
+
+if __name__ == '__main__':
+	parser = ArgumentParser(description='Cycle detector for xbps-src')
+	parser.add_argument('-j', '--jobs', default=None,
+			type=int, help='Number of parallel jobs')
+	parser.add_argument('-d', '--directory',
+			default=None, help='Path to void-packages repo')
+
+	args = parser.parse_args()
+
+	if not args.directory:
+		try: args.directory = os.environ['XBPS_DISTDIR']
+		except KeyError: args.directory = '.'
+
+	pool = multiprocessing.Pool(processes = args.jobs)
+
+	pattern = os.path.join(args.directory, 'srcpkgs', '*')
+	depmap = dict(pool.starmap(enum_depends, 
+			((os.path.basename(g), args.directory)
+				for g in glob.iglob(pattern))))
+
+	find_cycles(depmap, args.directory)

From 8807abcead4be8c36e61a5ece6ab8508f304914f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:45:23 -0300
Subject: [PATCH 2/4] .github/workflows: run xbps-cycles daily.

Should help in catching cyclic dependencies early.

Rename lockthreads.yml to include all scheduled CI tasks.
---
 .github/workflows/{lockthreads.yml => cron.yml} | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
 rename .github/workflows/{lockthreads.yml => cron.yml} (61%)

diff --git a/.github/workflows/lockthreads.yml b/.github/workflows/cron.yml
similarity index 61%
rename from .github/workflows/lockthreads.yml
rename to .github/workflows/cron.yml
index f3ec106a6e6c..c87446743fe5 100644
--- a/.github/workflows/lockthreads.yml
+++ b/.github/workflows/cron.yml
@@ -1,4 +1,4 @@
-name: 'Lock threads'
+name: 'Scheduled tasks'
 
 on:
   schedule:
@@ -13,3 +13,8 @@ jobs:
           github-token: ${{ github.token }}
           pr-lock-inactive-days: '90'
           process-only: 'prs'
+  cycles:
+    runs-on: ubuntu-latest
+    steps:
+      - run: apt-get install -y python3-networkx
+      - run: common/scripts/xbps-cycles.py

From b3c34c8791feabd0ac57100a13fc263211cd6ed2 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Piotr=20W=C3=B3jcik?= <chocimier@tlen.pl>
Date: Wed, 23 Jun 2021 23:11:13 +0200
Subject: [PATCH 3/4] .github/workflows: prepare container for xbps-cycles

---
 .github/workflows/cron.yml | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/.github/workflows/cron.yml b/.github/workflows/cron.yml
index c87446743fe5..c284857efcb6 100644
--- a/.github/workflows/cron.yml
+++ b/.github/workflows/cron.yml
@@ -15,6 +15,23 @@ jobs:
           process-only: 'prs'
   cycles:
     runs-on: ubuntu-latest
+    container:
+        image: 'ghcr.io/void-linux/xbps-src-masterdir:20210313rc01-x86_64-musl'
     steps:
-      - run: apt-get install -y python3-networkx
+      - name: Prepare container
+        run: |
+          # Sync and upgrade once, assume error comes from xbps update
+          xbps-install -Syu || xbps-install -yu xbps
+          # Upgrade again (in case there was a xbps update)
+          xbps-install -yu
+          # Install script dependencies
+          xbps-install -y python3-networkx
+      - uses: actions/checkout@v1
+        with:
+          fetch-depth: 1
+      - name: Create hostrepo and prepare masterdir
+        run: |
+         ln -s "$(pwd)" /hostrepo &&
+         common/travis/set_mirror.sh &&
+         common/travis/prepare.sh
       - run: common/scripts/xbps-cycles.py

From 86fd1a16daf38588df71e8e8a57b052cb34ce7be Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Piotr=20W=C3=B3jcik?= <chocimier@tlen.pl>
Date: Thu, 24 Jun 2021 20:19:26 +0200
Subject: [PATCH 4/4] common/xbps-cycles.py: return nonzero on cycle detected

---
 common/scripts/xbps-cycles.py | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/common/scripts/xbps-cycles.py b/common/scripts/xbps-cycles.py
index 24ef17156336..94994bd91646 100755
--- a/common/scripts/xbps-cycles.py
+++ b/common/scripts/xbps-cycles.py
@@ -28,7 +28,7 @@ def enum_depends(pkg, xbpsdir):
 	try:
 		deps = subprocess.check_output(cmd)
 	except subprocess.CalledProcessError as err:
-		print('xbps-src failed to find dependencies for package', pkg) 
+		print('xbps-src failed to find dependencies for package', pkg)
 		deps = [ ]
 	else:
 		deps = [d for d in deps.decode('utf-8').split('\n') if d]
@@ -47,6 +47,7 @@ def find_cycles(depmap, xbpsdir):
 	subpackages.
 	'''
 	G = nx.DiGraph()
+	rv = 0
 
 	for i, deps in depmap.items():
 		path = os.path.join(xbpsdir, 'srcpkgs', i)
@@ -59,6 +60,7 @@ def find_cycles(depmap, xbpsdir):
 
 	for c in nx.strongly_connected_components(G):
 		if len(c) < 2: continue
+		rv = 1
 		pkgs = nx.to_dict_of_lists(G, c)
 
 		p = next(iter(pkgs.keys()))
@@ -77,6 +79,7 @@ def find_cycles(depmap, xbpsdir):
 
 		if cycles:
 			print('Cycle: ' + ' -> '.join(cycles) + '\n')
+	return rv
 
 
 if __name__ == '__main__':
@@ -95,8 +98,9 @@ def find_cycles(depmap, xbpsdir):
 	pool = multiprocessing.Pool(processes = args.jobs)
 
 	pattern = os.path.join(args.directory, 'srcpkgs', '*')
-	depmap = dict(pool.starmap(enum_depends, 
+	depmap = dict(pool.starmap(enum_depends,
 			((os.path.basename(g), args.directory)
 				for g in glob.iglob(pattern))))
 
-	find_cycles(depmap, args.directory)
+	rv = find_cycles(depmap, args.directory)
+	sys.exit(rv)

Re: common/scripts: import xbps-cycles.

[Chocimier]

[-- Attachment #1: Type: text/plain, Size: 192 bytes --]

New comment by Chocimier on void-packages repository

https://github.com/void-linux/void-packages/pull/31631#issuecomment-867884742

Comment:
Top patch is for sending mail on cycles detected.

Re: [PR PATCH] [Updated] common/scripts: import xbps-cycles.

[Chocimier]

[-- Attachment #1: Type: text/plain, Size: 1757 bytes --]

There is an updated pull request by Chocimier against master on the void-packages repository

https://github.com/ericonr/void-packages cycles
https://github.com/void-linux/void-packages/pull/31631

common/scripts: import xbps-cycles.
From https://github.com/ahesford/xbps-cycles, license is compatible with
void-packages. Will be run in CI, so it should live in the same
repository.

<!-- Mark items with [x] where applicable -->

#### General
- [ ] This is a new package and it conforms to the [quality requirements](https://github.com/void-linux/void-packages/blob/master/Manual.md#quality-requirements)

#### Have the results of the proposed changes been tested?
- [ ] I use the packages affected by the proposed changes on a regular basis and confirm this PR works for me
- [ ] I generally don't use the affected packages but briefly tested this PR

<!--
If GitHub CI cannot be used to validate the build result (for example, if the
build is likely to take several hours), make sure to
[skip CI](https://github.com/void-linux/void-packages/blob/master/CONTRIBUTING.md#continuous-integration).
When skipping CI, uncomment and fill out the following section.
Note: for builds that are likely to complete in less than 2 hours, it is not
acceptable to skip CI.
-->
<!-- 
#### Does it build and run successfully? 
(Please choose at least one native build and, if supported, at least one cross build. More are better.)
- [ ] I built this PR locally for my native architecture, (ARCH-LIBC)
- [ ] I built this PR locally for these architectures (if supported. mark crossbuilds):
  - [ ] aarch64-musl
  - [ ] armv7l
  - [ ] armv6l-musl
-->


A patch file from https://github.com/void-linux/void-packages/pull/31631.patch is attached

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: github-pr-cycles-31631.patch --]
[-- Type: text/x-diff, Size: 9126 bytes --]

From ef724c4960027f7758f15952e8f5a85a1dba1673 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:39:19 -0300
Subject: [PATCH 1/4] common/scripts: import xbps-cycles.

From https://github.com/ahesford/xbps-cycles, that is based on
https://gist.github.com/Chocimier/de76441493ec7775c201dac0bb03ced5 .
License is compatible with void-packages. Will be run in CI, so it
should live in the same repository.
---
 common/scripts/README.xbps-cycles.md |  18 +++++
 common/scripts/xbps-cycles.py        | 102 +++++++++++++++++++++++++++
 2 files changed, 120 insertions(+)
 create mode 100644 common/scripts/README.xbps-cycles.md
 create mode 100755 common/scripts/xbps-cycles.py

diff --git a/common/scripts/README.xbps-cycles.md b/common/scripts/README.xbps-cycles.md
new file mode 100644
index 000000000000..075484829716
--- /dev/null
+++ b/common/scripts/README.xbps-cycles.md
@@ -0,0 +1,18 @@
+# Cycle detector for void-packages
+
+This script enumerates dependencies for packages in a
+[void-packages repository](https://github.com/void-linux/void-packages)
+and identifies build-time dependency cycles.
+
+For command syntax, run `xbps-cycles.py -h`. Often, it may be sufficient to run
+`xbps-cycles.py` with no arguments. By default, the script will look for a
+repository at `$XBPS_DISTDIR`; if that variable is not defined, the current
+directory is used instead. To override this behavior, use the `-d` option to
+provide the path to your desired void-packages clone.
+
+The standard behavior will be to spawn multiple processes, one per CPU, to
+enumerate package dependencies. This is by far the most time-consuming part of
+the execution. To override the degree of parallelism, use the `-j` option.
+
+Failures should be harmless but, at this early stage, unlikely to be pretty or
+even helpful.
diff --git a/common/scripts/xbps-cycles.py b/common/scripts/xbps-cycles.py
new file mode 100755
index 000000000000..24ef17156336
--- /dev/null
+++ b/common/scripts/xbps-cycles.py
@@ -0,0 +1,102 @@
+#!/usr/bin/env python3
+
+import os
+import sys
+import glob
+import subprocess
+import multiprocessing
+
+from argparse import ArgumentParser
+
+import networkx as nx
+
+
+def enum_depends(pkg, xbpsdir):
+	'''
+	Return a pair (pkg, [dependencies]), where [dependencies] is the list
+	of dependencies for the given package pkg. The argument xbpsdir should
+	be a path to a void-packages repository. Dependencies will be
+	determined by invoking
+
+		<xbpsdir>/xbps-src show-build-deps <pkg>
+
+	If the return code of this call nonzero, a message will be printed but
+	the package will treated as if it has no dependencies.
+	'''
+	cmd = [os.path.join(xbpsdir, 'xbps-src'), 'show-build-deps', pkg]
+
+	try:
+		deps = subprocess.check_output(cmd)
+	except subprocess.CalledProcessError as err:
+		print('xbps-src failed to find dependencies for package', pkg) 
+		deps = [ ]
+	else:
+		deps = [d for d in deps.decode('utf-8').split('\n') if d]
+
+	return pkg, deps
+
+
+def find_cycles(depmap, xbpsdir):
+	'''
+	For a map depmap: package -> [dependencies], construct a directed graph
+	and identify any cycles therein.
+
+	The argument xbpsdir should be a path to the root of a void-packages
+	repository. All package names in depmap will be appended to the path
+	<xbpsdir>/srcpkgs and reduced with os.path.realpath to coalesce
+	subpackages.
+	'''
+	G = nx.DiGraph()
+
+	for i, deps in depmap.items():
+		path = os.path.join(xbpsdir, 'srcpkgs', i)
+		i = os.path.basename(os.path.realpath(path))
+
+		for j in deps:
+			path = os.path.join(xbpsdir, 'srcpkgs', j.strip())
+			j = os.path.basename(os.path.realpath(path))
+			G.add_edge(i, j)
+
+	for c in nx.strongly_connected_components(G):
+		if len(c) < 2: continue
+		pkgs = nx.to_dict_of_lists(G, c)
+
+		p = next(iter(pkgs.keys()))
+		cycles = [ ]
+		while True:
+			cycles.append(p)
+
+			# Cycle is complete when package is not in map
+			try: deps = pkgs.pop(p)
+			except KeyError: break
+
+		        # Any of the dependencies here contributes to a cycle
+			p = deps[0]
+			if len(deps) > 1:
+				print('Mulitpath: {} -> {}, choosing first'.format(p, deps))
+
+		if cycles:
+			print('Cycle: ' + ' -> '.join(cycles) + '\n')
+
+
+if __name__ == '__main__':
+	parser = ArgumentParser(description='Cycle detector for xbps-src')
+	parser.add_argument('-j', '--jobs', default=None,
+			type=int, help='Number of parallel jobs')
+	parser.add_argument('-d', '--directory',
+			default=None, help='Path to void-packages repo')
+
+	args = parser.parse_args()
+
+	if not args.directory:
+		try: args.directory = os.environ['XBPS_DISTDIR']
+		except KeyError: args.directory = '.'
+
+	pool = multiprocessing.Pool(processes = args.jobs)
+
+	pattern = os.path.join(args.directory, 'srcpkgs', '*')
+	depmap = dict(pool.starmap(enum_depends, 
+			((os.path.basename(g), args.directory)
+				for g in glob.iglob(pattern))))
+
+	find_cycles(depmap, args.directory)

From 8807abcead4be8c36e61a5ece6ab8508f304914f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:45:23 -0300
Subject: [PATCH 2/4] .github/workflows: run xbps-cycles daily.

Should help in catching cyclic dependencies early.

Rename lockthreads.yml to include all scheduled CI tasks.
---
 .github/workflows/{lockthreads.yml => cron.yml} | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
 rename .github/workflows/{lockthreads.yml => cron.yml} (61%)

diff --git a/.github/workflows/lockthreads.yml b/.github/workflows/cron.yml
similarity index 61%
rename from .github/workflows/lockthreads.yml
rename to .github/workflows/cron.yml
index f3ec106a6e6c..c87446743fe5 100644
--- a/.github/workflows/lockthreads.yml
+++ b/.github/workflows/cron.yml
@@ -1,4 +1,4 @@
-name: 'Lock threads'
+name: 'Scheduled tasks'
 
 on:
   schedule:
@@ -13,3 +13,8 @@ jobs:
           github-token: ${{ github.token }}
           pr-lock-inactive-days: '90'
           process-only: 'prs'
+  cycles:
+    runs-on: ubuntu-latest
+    steps:
+      - run: apt-get install -y python3-networkx
+      - run: common/scripts/xbps-cycles.py

From b3c34c8791feabd0ac57100a13fc263211cd6ed2 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Piotr=20W=C3=B3jcik?= <chocimier@tlen.pl>
Date: Wed, 23 Jun 2021 23:11:13 +0200
Subject: [PATCH 3/4] .github/workflows: prepare container for xbps-cycles

---
 .github/workflows/cron.yml | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/.github/workflows/cron.yml b/.github/workflows/cron.yml
index c87446743fe5..c284857efcb6 100644
--- a/.github/workflows/cron.yml
+++ b/.github/workflows/cron.yml
@@ -15,6 +15,23 @@ jobs:
           process-only: 'prs'
   cycles:
     runs-on: ubuntu-latest
+    container:
+        image: 'ghcr.io/void-linux/xbps-src-masterdir:20210313rc01-x86_64-musl'
     steps:
-      - run: apt-get install -y python3-networkx
+      - name: Prepare container
+        run: |
+          # Sync and upgrade once, assume error comes from xbps update
+          xbps-install -Syu || xbps-install -yu xbps
+          # Upgrade again (in case there was a xbps update)
+          xbps-install -yu
+          # Install script dependencies
+          xbps-install -y python3-networkx
+      - uses: actions/checkout@v1
+        with:
+          fetch-depth: 1
+      - name: Create hostrepo and prepare masterdir
+        run: |
+         ln -s "$(pwd)" /hostrepo &&
+         common/travis/set_mirror.sh &&
+         common/travis/prepare.sh
       - run: common/scripts/xbps-cycles.py

From fcc3d671f0a84a51f1dc4ca600445d53f271e0ae Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Piotr=20W=C3=B3jcik?= <chocimier@tlen.pl>
Date: Tue, 29 Jun 2021 19:58:45 +0200
Subject: [PATCH 4/4] .github/workflows: open issue when cycle is detected

---
 .github/workflows/cron.yml | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)

diff --git a/.github/workflows/cron.yml b/.github/workflows/cron.yml
index c284857efcb6..1b53808a7588 100644
--- a/.github/workflows/cron.yml
+++ b/.github/workflows/cron.yml
@@ -25,7 +25,7 @@ jobs:
           # Upgrade again (in case there was a xbps update)
           xbps-install -yu
           # Install script dependencies
-          xbps-install -y python3-networkx
+          xbps-install -y python3-networkx github-cli
       - uses: actions/checkout@v1
         with:
           fetch-depth: 1
@@ -34,4 +34,15 @@ jobs:
          ln -s "$(pwd)" /hostrepo &&
          common/travis/set_mirror.sh &&
          common/travis/prepare.sh
-      - run: common/scripts/xbps-cycles.py
+      - name: Find cycles and open issues
+        run: |
+         common/scripts/xbps-cycles.py | tee cycles
+         grep 'Cycle:' cycles | while read -r line; do
+             if gh issue list -R "$GITHUB_REPOSITORY" -S "$line" | grep .; then
+                 printf "Issue on '%s' already exists.\n" "$line"
+             else
+                 gh issue create -R "$GITHUB_REPOSITORY" -b '' -t "$line"
+             fi
+         done
+        env:
+            GITHUB_TOKEN: ${{secrets.GITHUB_TOKEN }}

Re: common/scripts: import xbps-cycles.

[Chocimier]

[-- Attachment #1: Type: text/plain, Size: 361 bytes --]

New comment by Chocimier on void-packages repository

https://github.com/void-linux/void-packages/pull/31631#issuecomment-870890062

Comment:
Changed to open informative issue rather than sending vague email.
Same cycle is reported only once, but if there are branches, it can open more than one issue.

https://github.com/Chocimier/void-packages-org/issues

Re: common/scripts: import xbps-cycles.

[ericonr]

[-- Attachment #1: Type: text/plain, Size: 229 bytes --]

New comment by ericonr on void-packages repository

https://github.com/void-linux/void-packages/pull/31631#issuecomment-871005936

Comment:
Ok, and it already implements a check to not open repeat issues ! ANything else we need?

Re: [PR PATCH] [Updated] common/scripts: import xbps-cycles.

[Chocimier]

[-- Attachment #1: Type: text/plain, Size: 1757 bytes --]

There is an updated pull request by Chocimier against master on the void-packages repository

https://github.com/ericonr/void-packages cycles
https://github.com/void-linux/void-packages/pull/31631

common/scripts: import xbps-cycles.
From https://github.com/ahesford/xbps-cycles, license is compatible with
void-packages. Will be run in CI, so it should live in the same
repository.

<!-- Mark items with [x] where applicable -->

#### General
- [ ] This is a new package and it conforms to the [quality requirements](https://github.com/void-linux/void-packages/blob/master/Manual.md#quality-requirements)

#### Have the results of the proposed changes been tested?
- [ ] I use the packages affected by the proposed changes on a regular basis and confirm this PR works for me
- [ ] I generally don't use the affected packages but briefly tested this PR

<!--
If GitHub CI cannot be used to validate the build result (for example, if the
build is likely to take several hours), make sure to
[skip CI](https://github.com/void-linux/void-packages/blob/master/CONTRIBUTING.md#continuous-integration).
When skipping CI, uncomment and fill out the following section.
Note: for builds that are likely to complete in less than 2 hours, it is not
acceptable to skip CI.
-->
<!-- 
#### Does it build and run successfully? 
(Please choose at least one native build and, if supported, at least one cross build. More are better.)
- [ ] I built this PR locally for my native architecture, (ARCH-LIBC)
- [ ] I built this PR locally for these architectures (if supported. mark crossbuilds):
  - [ ] aarch64-musl
  - [ ] armv7l
  - [ ] armv6l-musl
-->


A patch file from https://github.com/void-linux/void-packages/pull/31631.patch is attached

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: github-pr-cycles-31631.patch --]
[-- Type: text/x-diff, Size: 13821 bytes --]

From ef724c4960027f7758f15952e8f5a85a1dba1673 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:39:19 -0300
Subject: [PATCH 1/6] common/scripts: import xbps-cycles.

From https://github.com/ahesford/xbps-cycles, that is based on
https://gist.github.com/Chocimier/de76441493ec7775c201dac0bb03ced5 .
License is compatible with void-packages. Will be run in CI, so it
should live in the same repository.
---
 common/scripts/README.xbps-cycles.md |  18 +++++
 common/scripts/xbps-cycles.py        | 102 +++++++++++++++++++++++++++
 2 files changed, 120 insertions(+)
 create mode 100644 common/scripts/README.xbps-cycles.md
 create mode 100755 common/scripts/xbps-cycles.py

diff --git a/common/scripts/README.xbps-cycles.md b/common/scripts/README.xbps-cycles.md
new file mode 100644
index 000000000000..075484829716
--- /dev/null
+++ b/common/scripts/README.xbps-cycles.md
@@ -0,0 +1,18 @@
+# Cycle detector for void-packages
+
+This script enumerates dependencies for packages in a
+[void-packages repository](https://github.com/void-linux/void-packages)
+and identifies build-time dependency cycles.
+
+For command syntax, run `xbps-cycles.py -h`. Often, it may be sufficient to run
+`xbps-cycles.py` with no arguments. By default, the script will look for a
+repository at `$XBPS_DISTDIR`; if that variable is not defined, the current
+directory is used instead. To override this behavior, use the `-d` option to
+provide the path to your desired void-packages clone.
+
+The standard behavior will be to spawn multiple processes, one per CPU, to
+enumerate package dependencies. This is by far the most time-consuming part of
+the execution. To override the degree of parallelism, use the `-j` option.
+
+Failures should be harmless but, at this early stage, unlikely to be pretty or
+even helpful.
diff --git a/common/scripts/xbps-cycles.py b/common/scripts/xbps-cycles.py
new file mode 100755
index 000000000000..24ef17156336
--- /dev/null
+++ b/common/scripts/xbps-cycles.py
@@ -0,0 +1,102 @@
+#!/usr/bin/env python3
+
+import os
+import sys
+import glob
+import subprocess
+import multiprocessing
+
+from argparse import ArgumentParser
+
+import networkx as nx
+
+
+def enum_depends(pkg, xbpsdir):
+	'''
+	Return a pair (pkg, [dependencies]), where [dependencies] is the list
+	of dependencies for the given package pkg. The argument xbpsdir should
+	be a path to a void-packages repository. Dependencies will be
+	determined by invoking
+
+		<xbpsdir>/xbps-src show-build-deps <pkg>
+
+	If the return code of this call nonzero, a message will be printed but
+	the package will treated as if it has no dependencies.
+	'''
+	cmd = [os.path.join(xbpsdir, 'xbps-src'), 'show-build-deps', pkg]
+
+	try:
+		deps = subprocess.check_output(cmd)
+	except subprocess.CalledProcessError as err:
+		print('xbps-src failed to find dependencies for package', pkg) 
+		deps = [ ]
+	else:
+		deps = [d for d in deps.decode('utf-8').split('\n') if d]
+
+	return pkg, deps
+
+
+def find_cycles(depmap, xbpsdir):
+	'''
+	For a map depmap: package -> [dependencies], construct a directed graph
+	and identify any cycles therein.
+
+	The argument xbpsdir should be a path to the root of a void-packages
+	repository. All package names in depmap will be appended to the path
+	<xbpsdir>/srcpkgs and reduced with os.path.realpath to coalesce
+	subpackages.
+	'''
+	G = nx.DiGraph()
+
+	for i, deps in depmap.items():
+		path = os.path.join(xbpsdir, 'srcpkgs', i)
+		i = os.path.basename(os.path.realpath(path))
+
+		for j in deps:
+			path = os.path.join(xbpsdir, 'srcpkgs', j.strip())
+			j = os.path.basename(os.path.realpath(path))
+			G.add_edge(i, j)
+
+	for c in nx.strongly_connected_components(G):
+		if len(c) < 2: continue
+		pkgs = nx.to_dict_of_lists(G, c)
+
+		p = next(iter(pkgs.keys()))
+		cycles = [ ]
+		while True:
+			cycles.append(p)
+
+			# Cycle is complete when package is not in map
+			try: deps = pkgs.pop(p)
+			except KeyError: break
+
+		        # Any of the dependencies here contributes to a cycle
+			p = deps[0]
+			if len(deps) > 1:
+				print('Mulitpath: {} -> {}, choosing first'.format(p, deps))
+
+		if cycles:
+			print('Cycle: ' + ' -> '.join(cycles) + '\n')
+
+
+if __name__ == '__main__':
+	parser = ArgumentParser(description='Cycle detector for xbps-src')
+	parser.add_argument('-j', '--jobs', default=None,
+			type=int, help='Number of parallel jobs')
+	parser.add_argument('-d', '--directory',
+			default=None, help='Path to void-packages repo')
+
+	args = parser.parse_args()
+
+	if not args.directory:
+		try: args.directory = os.environ['XBPS_DISTDIR']
+		except KeyError: args.directory = '.'
+
+	pool = multiprocessing.Pool(processes = args.jobs)
+
+	pattern = os.path.join(args.directory, 'srcpkgs', '*')
+	depmap = dict(pool.starmap(enum_depends, 
+			((os.path.basename(g), args.directory)
+				for g in glob.iglob(pattern))))
+
+	find_cycles(depmap, args.directory)

From 8807abcead4be8c36e61a5ece6ab8508f304914f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=C3=89rico=20Nogueira?= <erico.erc@gmail.com>
Date: Wed, 23 Jun 2021 13:45:23 -0300
Subject: [PATCH 2/6] .github/workflows: run xbps-cycles daily.

Should help in catching cyclic dependencies early.

Rename lockthreads.yml to include all scheduled CI tasks.
---
 .github/workflows/{lockthreads.yml => cron.yml} | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
 rename .github/workflows/{lockthreads.yml => cron.yml} (61%)

diff --git a/.github/workflows/lockthreads.yml b/.github/workflows/cron.yml
similarity index 61%
rename from .github/workflows/lockthreads.yml
rename to .github/workflows/cron.yml
index f3ec106a6e6c..c87446743fe5 100644
--- a/.github/workflows/lockthreads.yml
+++ b/.github/workflows/cron.yml
@@ -1,4 +1,4 @@
-name: 'Lock threads'
+name: 'Scheduled tasks'
 
 on:
   schedule:
@@ -13,3 +13,8 @@ jobs:
           github-token: ${{ github.token }}
           pr-lock-inactive-days: '90'
           process-only: 'prs'
+  cycles:
+    runs-on: ubuntu-latest
+    steps:
+      - run: apt-get install -y python3-networkx
+      - run: common/scripts/xbps-cycles.py

From b3c34c8791feabd0ac57100a13fc263211cd6ed2 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Piotr=20W=C3=B3jcik?= <chocimier@tlen.pl>
Date: Wed, 23 Jun 2021 23:11:13 +0200
Subject: [PATCH 3/6] .github/workflows: prepare container for xbps-cycles

---
 .github/workflows/cron.yml | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/.github/workflows/cron.yml b/.github/workflows/cron.yml
index c87446743fe5..c284857efcb6 100644
--- a/.github/workflows/cron.yml
+++ b/.github/workflows/cron.yml
@@ -15,6 +15,23 @@ jobs:
           process-only: 'prs'
   cycles:
     runs-on: ubuntu-latest
+    container:
+        image: 'ghcr.io/void-linux/xbps-src-masterdir:20210313rc01-x86_64-musl'
     steps:
-      - run: apt-get install -y python3-networkx
+      - name: Prepare container
+        run: |
+          # Sync and upgrade once, assume error comes from xbps update
+          xbps-install -Syu || xbps-install -yu xbps
+          # Upgrade again (in case there was a xbps update)
+          xbps-install -yu
+          # Install script dependencies
+          xbps-install -y python3-networkx
+      - uses: actions/checkout@v1
+        with:
+          fetch-depth: 1
+      - name: Create hostrepo and prepare masterdir
+        run: |
+         ln -s "$(pwd)" /hostrepo &&
+         common/travis/set_mirror.sh &&
+         common/travis/prepare.sh
       - run: common/scripts/xbps-cycles.py

From fcc3d671f0a84a51f1dc4ca600445d53f271e0ae Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Piotr=20W=C3=B3jcik?= <chocimier@tlen.pl>
Date: Tue, 29 Jun 2021 19:58:45 +0200
Subject: [PATCH 4/6] .github/workflows: open issue when cycle is detected

---
 .github/workflows/cron.yml | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)

diff --git a/.github/workflows/cron.yml b/.github/workflows/cron.yml
index c284857efcb6..1b53808a7588 100644
--- a/.github/workflows/cron.yml
+++ b/.github/workflows/cron.yml
@@ -25,7 +25,7 @@ jobs:
           # Upgrade again (in case there was a xbps update)
           xbps-install -yu
           # Install script dependencies
-          xbps-install -y python3-networkx
+          xbps-install -y python3-networkx github-cli
       - uses: actions/checkout@v1
         with:
           fetch-depth: 1
@@ -34,4 +34,15 @@ jobs:
          ln -s "$(pwd)" /hostrepo &&
          common/travis/set_mirror.sh &&
          common/travis/prepare.sh
-      - run: common/scripts/xbps-cycles.py
+      - name: Find cycles and open issues
+        run: |
+         common/scripts/xbps-cycles.py | tee cycles
+         grep 'Cycle:' cycles | while read -r line; do
+             if gh issue list -R "$GITHUB_REPOSITORY" -S "$line" | grep .; then
+                 printf "Issue on '%s' already exists.\n" "$line"
+             else
+                 gh issue create -R "$GITHUB_REPOSITORY" -b '' -t "$line"
+             fi
+         done
+        env:
+            GITHUB_TOKEN: ${{secrets.GITHUB_TOKEN }}

From ec550b63b1d9b99ee028306efcaf045a5a439372 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Piotr=20W=C3=B3jcik?= <chocimier@tlen.pl>
Date: Wed, 30 Jun 2021 20:38:44 +0200
Subject: [PATCH 5/6] common/xbps-cycles.py: Add cache option

allows to modify deps and see if cycle is resolved
---
 common/scripts/README.xbps-cycles.md |  4 ++++
 common/scripts/xbps-cycles.py        | 26 ++++++++++++++++++++++----
 2 files changed, 26 insertions(+), 4 deletions(-)

diff --git a/common/scripts/README.xbps-cycles.md b/common/scripts/README.xbps-cycles.md
index 075484829716..12774e52c707 100644
--- a/common/scripts/README.xbps-cycles.md
+++ b/common/scripts/README.xbps-cycles.md
@@ -14,5 +14,9 @@ The standard behavior will be to spawn multiple processes, one per CPU, to
 enumerate package dependencies. This is by far the most time-consuming part of
 the execution. To override the degree of parallelism, use the `-j` option.
 
+Dependencies can be cached on disk, one file per package, in directory
+passed with `-c` option. On next execution with same option, dependencies are
+read from file rather than computed.
+
 Failures should be harmless but, at this early stage, unlikely to be pretty or
 even helpful.
diff --git a/common/scripts/xbps-cycles.py b/common/scripts/xbps-cycles.py
index 24ef17156336..769e941ad89e 100755
--- a/common/scripts/xbps-cycles.py
+++ b/common/scripts/xbps-cycles.py
@@ -11,7 +11,7 @@
 import networkx as nx
 
 
-def enum_depends(pkg, xbpsdir):
+def enum_depends(pkg, xbpsdir, cachedir):
 	'''
 	Return a pair (pkg, [dependencies]), where [dependencies] is the list
 	of dependencies for the given package pkg. The argument xbpsdir should
@@ -20,18 +20,32 @@ def enum_depends(pkg, xbpsdir):
 
 		<xbpsdir>/xbps-src show-build-deps <pkg>
 
+	unless <cachedir>/deps-<pkg> file exist, in that case it is read.
+
 	If the return code of this call nonzero, a message will be printed but
 	the package will treated as if it has no dependencies.
 	'''
+	if cachedir:
+		cachepath = os.path.join(cachedir, 'deps-' + pkg)
+		try:
+			with open(cachepath) as f:
+				return pkg, [l.strip() for l in f]
+		except FileNotFoundError:
+			pass
+
 	cmd = [os.path.join(xbpsdir, 'xbps-src'), 'show-build-deps', pkg]
 
 	try:
 		deps = subprocess.check_output(cmd)
 	except subprocess.CalledProcessError as err:
-		print('xbps-src failed to find dependencies for package', pkg) 
+		print('xbps-src failed to find dependencies for package', pkg)
 		deps = [ ]
 	else:
 		deps = [d for d in deps.decode('utf-8').split('\n') if d]
+		if cachedir:
+			with open(cachepath, 'w') as f:
+				for d in deps:
+					print(d, file=f)
 
 	return pkg, deps
 
@@ -83,6 +97,8 @@ def find_cycles(depmap, xbpsdir):
 	parser = ArgumentParser(description='Cycle detector for xbps-src')
 	parser.add_argument('-j', '--jobs', default=None,
 			type=int, help='Number of parallel jobs')
+	parser.add_argument('-c', '--cachedir',
+			default=None, help='''Directory to use as cache for xbps-src show-build-deps. Directory must exist already.''')
 	parser.add_argument('-d', '--directory',
 			default=None, help='Path to void-packages repo')
 
@@ -92,11 +108,13 @@ def find_cycles(depmap, xbpsdir):
 		try: args.directory = os.environ['XBPS_DISTDIR']
 		except KeyError: args.directory = '.'
 
+	cachedir = args.cachedir
+
 	pool = multiprocessing.Pool(processes = args.jobs)
 
 	pattern = os.path.join(args.directory, 'srcpkgs', '*')
-	depmap = dict(pool.starmap(enum_depends, 
-			((os.path.basename(g), args.directory)
+	depmap = dict(pool.starmap(enum_depends,
+			((os.path.basename(g), args.directory, cachedir)
 				for g in glob.iglob(pattern))))
 
 	find_cycles(depmap, args.directory)

From acc1111c84064fa9a88cd343f15d1bf98f9466f8 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Piotr=20W=C3=B3jcik?= <chocimier@tlen.pl>
Date: Wed, 30 Jun 2021 20:39:34 +0200
Subject: [PATCH 6/6] common/xbps-cycles.py: deterministic cycle path

---
 common/scripts/xbps-cycles.py | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/common/scripts/xbps-cycles.py b/common/scripts/xbps-cycles.py
index 769e941ad89e..dbfd538235ca 100755
--- a/common/scripts/xbps-cycles.py
+++ b/common/scripts/xbps-cycles.py
@@ -75,7 +75,7 @@ def find_cycles(depmap, xbpsdir):
 		if len(c) < 2: continue
 		pkgs = nx.to_dict_of_lists(G, c)
 
-		p = next(iter(pkgs.keys()))
+		p = min(pkgs.keys())
 		cycles = [ ]
 		while True:
 			cycles.append(p)
@@ -85,7 +85,7 @@ def find_cycles(depmap, xbpsdir):
 			except KeyError: break
 
 		        # Any of the dependencies here contributes to a cycle
-			p = deps[0]
+			p = min(deps)
 			if len(deps) > 1:
 				print('Mulitpath: {} -> {}, choosing first'.format(p, deps))
 

Re: common/scripts: import xbps-cycles.

[Chocimier]

[-- Attachment #1: Type: text/plain, Size: 174 bytes --]

New comment by Chocimier on void-packages repository

https://github.com/void-linux/void-packages/pull/31631#issuecomment-871655069

Comment:
I think it's ready. @ahesford ?

Re: common/scripts: import xbps-cycles.

[ahesford]

[-- Attachment #1: Type: text/plain, Size: 158 bytes --]

New comment by ahesford on void-packages repository

https://github.com/void-linux/void-packages/pull/31631#issuecomment-871657312

Comment:
Looks good to me

Re: [PR PATCH] [Merged]: common/scripts: import xbps-cycles.

[Chocimier]

[-- Attachment #1: Type: text/plain, Size: 1600 bytes --]

There's a merged pull request on the void-packages repository

common/scripts: import xbps-cycles.
https://github.com/void-linux/void-packages/pull/31631

Description:
From https://github.com/ahesford/xbps-cycles, license is compatible with
void-packages. Will be run in CI, so it should live in the same
repository.

<!-- Mark items with [x] where applicable -->

#### General
- [ ] This is a new package and it conforms to the [quality requirements](https://github.com/void-linux/void-packages/blob/master/Manual.md#quality-requirements)

#### Have the results of the proposed changes been tested?
- [ ] I use the packages affected by the proposed changes on a regular basis and confirm this PR works for me
- [ ] I generally don't use the affected packages but briefly tested this PR

<!--
If GitHub CI cannot be used to validate the build result (for example, if the
build is likely to take several hours), make sure to
[skip CI](https://github.com/void-linux/void-packages/blob/master/CONTRIBUTING.md#continuous-integration).
When skipping CI, uncomment and fill out the following section.
Note: for builds that are likely to complete in less than 2 hours, it is not
acceptable to skip CI.
-->
<!-- 
#### Does it build and run successfully? 
(Please choose at least one native build and, if supported, at least one cross build. More are better.)
- [ ] I built this PR locally for my native architecture, (ARCH-LIBC)
- [ ] I built this PR locally for these architectures (if supported. mark crossbuilds):
  - [ ] aarch64-musl
  - [ ] armv7l
  - [ ] armv6l-musl
-->