Consider the following DAG (arrows are implicitly downwards):
top -> left, right left,right -> bottom. Or in ASCII art: top / \ left right \ / bottomCurrently, they are sorted incorrectly with topological-sort -- the exact resulting order depends on the order in which the dependencies are passed to 'topological-sort' (from (guix import utils)), but you can get the following:
right bottom left top 'bottom' and 'right' need to be switched. (Background)I would like to use a copy of 'topological-sort' for determining the order in which 'workspace' members need to be built in antioxidant, but currently it produces bogus results (at least for 'greetd').
Theoretically, it would also impact recursive imports (unverified) (topological-sort is used to emit them in topological order).
Code to reproduce the bug: (use-modules (guix sets) (ice-9 match) (srfi srfi-1)) (define (topological-sort nodes node-dependencies node-name)"Perform a breadth-first traversal of the graph rooted at NODES, a list of
nodes, and return the list of nodes sorted in topological order. Call NODE-DEPENDENCIES to obtain the dependencies of a node, and NODE-NAME to obtain a node's uniquely identifying \"key\"." (let loop ((nodes nodes) (result '()) (visited (set))) (match nodes (() result) ((head . tail) (if (set-contains? visited (node-name head)) (loop tail result visited) (let ((dependencies (node-dependencies head))) (loop (append dependencies tail) (cons head result) (set-insert (node-name head) visited)))))))) (define %dependencies '((top left right) (left bottom) (right bottom) (bottom))) (define root-nodes '(top)) (define (node-dependencies node) (assoc-ref %dependencies node)) (define node-name identity) (define sorted (topological-sort root-nodes node-dependencies node-name)) (write sorted) ;; Verify the dependencies have smaller indices (define (node-index node) (list-index (lambda (x) (equal? node x)) sorted)) (define (check node) (unless (<= (apply max 0 (map node-index (node-dependencies node))) (node-index node)) (pk node) (error "incorrectly sorted!"))) (for-each check (map car %dependencies)) Greetings, Maxime.
OpenPGP_0x49E3EE22191725EE.asc
Description: OpenPGP public key
OpenPGP_signature
Description: OpenPGP digital signature