On 2026-06-22 at 17:50+09:00, Nguyễn Gia Phong wrote:
> if we do 300-dependent cutoffs, we would have 4 "rings"
> going inward of 30722, 1775, 348 and 49 packages
> (the number could change a bit since I used last week's master,
> I'll follow up with the reprod scripts shortly).
As promised, attached are the scripts producing packages.py
and ring.{0,1,2,3} through the following:
./pre-inst-env guix repl -- generate-packages.py.scm
guix shell python -- python3 split.py
The second one takes a good 5 minutes computing
the transitive dependencies for all packages
on a Ryzen 3700X because I'm bad at graphing.
;;; Generator of packages.py
;;; SPDX-FileCopyrightText: 2026 Nguyễn Gia Phong
;;; SPDX-License-Identifier: GPL-3.0-or-later
(use-modules (gnu packages)
(guix diagnostics)
(guix packages))
(define (format-package pkg)
(let ((loc (package-location pkg)))
(simple-format #t "'~a:~a ~a@~a'"
(package-name pkg)
(package-version pkg)
(location-file loc)
(location-line loc))))
(with-output-to-file "packages.py"
(lambda _
(display "direct_inputs = {\n")
(for-each (lambda (dependant)
(display " ")
(format-package dependant)
(display ": ")
(let ((inputs (filter package?
(map cadr (bag-direct-inputs
(package->bag dependant))))))
(if (null? inputs)
(display "set(),\n")
(begin
(display "{\n")
(for-each (lambda (input)
(display " ")
(format-package input)
(display ",\n"))
inputs)
(display " },\n")))))
(all-packages))
(display "}\n")))
# Guix package collection splitter
# SPDX-FileCopyrightText: 2026 Nguyễn Gia Phong
# SPDX-License-Identifier: GPL-3.0-or-later
from copy import deepcopy
from functools import reduce
from packages import direct_inputs
THRESHOLD = 300
def transit(dependants, key):
"""Transit one level of dependence."""
dependants[key] |= reduce(set.__or__,
map(dependants.__getitem__, dependants[key]),
set())
for inputs in tuple(direct_inputs.values()):
for i in inputs:
direct_inputs.setdefault(i, set())
direct_dependants = {package: set() for package in direct_inputs}
#undirected_edges = deepcopy(direct_inputs) # use for graph components
for dependant, inputs in direct_inputs.items():
for i in inputs:
direct_dependants[i].add(dependant)
#undirected_edges[i].add(dependant)
transitive_inputs = deepcopy(direct_inputs)
transitive_dependants = deepcopy(direct_dependants)
while direct_dependants:
leaves = {package for package, dependants in direct_dependants.items()
if not dependants}
if leaves:
for leaf in leaves:
for i in direct_inputs[leaf]:
direct_dependants[i].remove(leaf)
else: # circular dependence, somehow
visited = deepcopy(direct_dependants)
while not leaves:
for package, dependants in visited.items():
transit(visited, package)
if package in dependants:
leaves.add(package)
for dependants in direct_dependants.values():
dependants -= leaves
for leaf in leaves:
transit(transitive_dependants, leaf)
for dependant in transitive_dependants[leaf]:
transitive_inputs[dependant].add(leaf)
direct_dependants.pop(leaf)
rings = []
while transitive_dependants:
ring = {package for package, dependants in transitive_dependants.items()
if len(dependants) <= THRESHOLD}
# The graph components are not balanced enough to be practical.
#components = []
#while ring:
# component = set()
# queue = {ring.pop()}
# while queue:
# package = queue.pop()
# if package not in component:
# component.add(package)
# queue |= undirected_edges[package] & ring
# ring -= queue
# for i in transitive_inputs[package]:
# if i in transitive_dependants:
# transitive_dependants[i].discard(package)
# transitive_dependants.pop(package)
# components.append(component)
#rings.append(components)
for package in ring:
transitive_dependants.pop(package)
for package in ring:
for i in transitive_inputs[package]:
if i in transitive_dependants:
transitive_dependants[i].discard(package)
rings.append(sorted(ring))
rings.reverse()
for i, ring in enumerate(rings):
with open(f'ring-{i}', 'w') as f:
for package in ring:
f.write(f'{package}\n')
