repro: downstream: reproducing in wrong order

[liamtoran]

DVC version : 0.92.0 (PyPI) + MacOS

It seems dvc repro --downstream (could also be the -f option) sometimes executes DAGs in the wrong order.

Steps to reproduction:

dvc run -o 1 -o 2 -f step1.dvc 'touch 1 | touch 2'
dvc run -d 1 -o 3 -f step2.dvc 'touch 3'
dvc run -d 3 -d 2 -o 4 -f step3.dvc 'touch 4'
dvc repro --downstream -f step1.dvc

Last bit does :

Running command:                                                        
	touch 1 | touch 2

Running command:
	touch 4

Running command:
	touch 3

Even though the DAG looks like this :

             +-----------+        
             | step1.dvc |        
             +-----------+        
            ***          ***      
           *                *     
         **                  ***  
+-----------+                   * 
| step2.dvc |                ***  
+-----------+               *     
            ***          ***      
               *        *         
                **    **          
             +-----------+        
             | step3.dvc |        
             +-----------+   

In this case step2 (touch 3) should be executed before step3 (touch 4)

[pmrowla]

Can be reproduced with

def test_repro_downstream(dvc):

    assert (
        main(
            [
                "run",
                "-o",
                "A",
                "-o",
                "B",
                "-f",
                "step1.dvc",
                "echo 'A'>A; echo 'B'>B",
            ]
        )
        == 0
    )
    assert (
        main(["run", "-d", "A", "-o", "C", "-f", "step2.dvc", "echo 'C'>C"])
        == 0
    )
    assert (
        main(
            [
                "run",
                "-d",
                "C",
                "-d",
                "B",
                "-o",
                "D",
                "-f",
                "step3.dvc",
                "echo 'D'>D",
            ]
        )
        == 0
    )
    evaluation = dvc.reproduce("step1.dvc", downstream=True, force=True)
    assert len(evaluation) == 3
    assert evaluation[0].relpath == "step1.dvc"
    assert evaluation[1].relpath == "step2.dvc"
    assert evaluation[2].relpath == "step3.dvc"

[pmrowla]

Looks like the issue is that for --downstream, we are reversing the DAG, and then traversing the reversed graph w/DFS pre-ordered search. In the example case, using pre-ordered search provides no guarantee that step3 is only visited after step2.

networkx dfs_preorder_nodes() returns them in some arbitrary order, that is probably just dependent on default python set behavior - in the example test case, if I change the name of the final stage to 3.dvc, the test actually passes in OSX python 3.7.

I think what we should be doing is traversing the reversed graph w/reverse post-ordered search, to ensure that dependencies are run in the correct order.

[pmrowla]

Also reproducible using our existing repro --downstream test (https://github.com/iterative/dvc/blob/fefbcc0b4ccd5a93ab96665c714a93b9fbdd1fa0/tests/func/test_repro.py#L1584)

For the graph

    #       E
    #      / \
    #     D   F
    #    / \   \
    #   B   C   G
    #    \ /
    #     A

downstream A is run as [A, B, D, E, C] even though C should be run before D