mongoengine-migrate
mongoengine-migrate copied to clipboard
Fix migrations graph traversal algorithm
Now the modified DFS (depth-first search) algorithm is used as graph traversal algorithm. Migration graph is directed graph (digraph) which can have cycles. According with this algorithm we use a counter for every node which initially equal to node's parents count. During walking down we decrement counter in node when we getting to it. If counter > 0 after that then we don't yield this node and break traversing on this branch and go up. If counter == 0 then we yield this node and continue walking down. This approach garantees that the migration will not be applied until all its dependencies will not be applied first. Walking up process is performed in reverse order.
But there is one problem:
(1)
/ \
(2) (3)
| |
(4) (5)
\ /
(6)
Suppose that all migrations are applied, current is (6). If we set (4) as a target, then branch (3), (5) could be also unapplied, but should not. Actually they not needed to unapply to get to (4).
It's needed to improve this behavior. "Sibling" migrations should not be applied/unapplied if it not needed to get to the target migration.