Repository: iterative/dvc

Issue:
repro: downstream: reproducing in wrong order 
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:
```sh
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`)

Discussion:
pmrowla: test_pull_git_imports is occasionally failing on travis, but unrelated to this issue (see #3570)

Patch:
diff --git a/dvc/repo/reproduce.py b/dvc/repo/reproduce.py
index e77934e89..288bdd39a 100644
--- a/dvc/repo/reproduce.py
+++ b/dvc/repo/reproduce.py
@@ -126,7 +126,8 @@ def _reproduce_stages(
     is to derive the evaluation starting from the given stage up to the
     ancestors. However, the `networkx.ancestors` returns a set, without
     any guarantee of any order, so we are going to reverse the graph and
-    use a pre-ordered search using the given stage as a starting point.
+    use a reverse post-ordered search using the given stage as a starting
+    point.
 
                    E                                   A
                   / \                                 / \
@@ -154,9 +155,10 @@ def _reproduce_stages(
                 # itself, and then reverse it, instead of using
                 # graph.reverse() directly because it calls `deepcopy`
                 # underneath -- unless copy=False is specified.
-                all_pipelines += nx.dfs_preorder_nodes(
+                nodes = nx.dfs_postorder_nodes(
                     G.copy().reverse(copy=False), stage
                 )
+                all_pipelines += reversed(list(nodes))
             else:
                 all_pipelines += nx.dfs_postorder_nodes(G, stage)
 
diff --git a/scripts/innosetup/setup.iss b/scripts/innosetup/setup.iss
index 1bff3a246..bf690f893 100644
--- a/scripts/innosetup/setup.iss
+++ b/scripts/innosetup/setup.iss
@@ -1,4 +1,4 @@
-#define MyAppName "Data Version Control"
+#define MyAppName "DVC (Data Version Control)"
 #define MyAppVersion ReadIni(".\scripts\innosetup\config.ini", "Version", "version", "unknown")
 #define MyAppPublisher "Dmitry Petrov"
 #define MyAppURL "https://dataversioncontrol.com/"


Test patch:
diff --git a/tests/func/test_repro.py b/tests/func/test_repro.py
index 186c0a829..ce13ddd9f 100644
--- a/tests/func/test_repro.py
+++ b/tests/func/test_repro.py
@@ -1586,40 +1586,49 @@ def _hide_md5(text):
     return re.sub(r"\b[a-f0-9]{32}\b", "<md5>", text)
 
 
-class TestReproDownstream(TestDvc):
-    def test(self):
-        # The dependency graph should look like this:
-        #
-        #       E
-        #      / \
-        #     D   F
-        #    / \   \
-        #   B   C   G
-        #    \ /
-        #     A
-        #
-        assert main(["run", "-o", "A", "echo A>A"]) == 0
-        assert main(["run", "-d", "A", "-o", "B", "echo B>B"]) == 0
-        assert main(["run", "-d", "A", "-o", "C", "echo C>C"]) == 0
-        assert main(["run", "-d", "B", "-d", "C", "-o", "D", "echo D>D"]) == 0
-        assert main(["run", "-o", "G", "echo G>G"]) == 0
-        assert main(["run", "-d", "G", "-o", "F", "echo F>F"]) == 0
-        assert main(["run", "-d", "D", "-d", "F", "-o", "E", "echo E>E"]) == 0
-
-        # We want the evaluation to move from B to E
-        #
-        #       E
-        #      /
-        #     D
-        #    /
-        #   B
-        #
-        evaluation = self.dvc.reproduce("B.dvc", downstream=True, force=True)
-
-        assert len(evaluation) == 3
-        assert evaluation[0].relpath == "B.dvc"
-        assert evaluation[1].relpath == "D.dvc"
-        assert evaluation[2].relpath == "E.dvc"
+def test_downstream(dvc):
+    # The dependency graph should look like this:
+    #
+    #       E
+    #      / \
+    #     D   F
+    #    / \   \
+    #   B   C   G
+    #    \ /
+    #     A
+    #
+    assert main(["run", "-o", "A", "echo A>A"]) == 0
+    assert main(["run", "-d", "A", "-o", "B", "echo B>B"]) == 0
+    assert main(["run", "-d", "A", "-o", "C", "echo C>C"]) == 0
+    assert main(["run", "-d", "B", "-d", "C", "-o", "D", "echo D>D"]) == 0
+    assert main(["run", "-o", "G", "echo G>G"]) == 0
+    assert main(["run", "-d", "G", "-o", "F", "echo F>F"]) == 0
+    assert main(["run", "-d", "D", "-d", "F", "-o", "E", "echo E>E"]) == 0
+
+    # We want the evaluation to move from B to E
+    #
+    #       E
+    #      /
+    #     D
+    #    /
+    #   B
+    #
+    evaluation = dvc.reproduce("B.dvc", downstream=True, force=True)
+
+    assert len(evaluation) == 3
+    assert evaluation[0].relpath == "B.dvc"
+    assert evaluation[1].relpath == "D.dvc"
+    assert evaluation[2].relpath == "E.dvc"
+
+    # B, C should be run (in any order) before D
+    # See https://github.com/iterative/dvc/issues/3602
+    evaluation = dvc.reproduce("A.dvc", downstream=True, force=True)
+
+    assert len(evaluation) == 5
+    assert evaluation[0].relpath == "A.dvc"
+    assert {evaluation[1].relpath, evaluation[2].relpath} == {"B.dvc", "C.dvc"}
+    assert evaluation[3].relpath == "D.dvc"
+    assert evaluation[4].relpath == "E.dvc"
 
 
 @pytest.mark.skipif(
diff --git a/tests/func/test_repro_multistage.py b/tests/func/test_repro_multistage.py
index 08d059326..529f1f658 100644
--- a/tests/func/test_repro_multistage.py
+++ b/tests/func/test_repro_multistage.py
@@ -259,6 +259,36 @@ def test_downstream(tmp_dir, dvc):
         and evaluation[2].relpath == "E.dvc"
     )
 
+    # B, C should be run (in any order) before D
+    # See https://github.com/iterative/dvc/issues/3602
+    evaluation = dvc.reproduce(
+        PIPELINE_FILE + ":A-gen", downstream=True, force=True
+    )
+
+    assert len(evaluation) == 5
+    assert (
+        isinstance(evaluation[0], PipelineStage)
+        and evaluation[0].relpath == PIPELINE_FILE
+        and evaluation[0].name == "A-gen"
+    )
+    names = set()
+    for stage in evaluation[1:3]:
+        if isinstance(stage, PipelineStage):
+            assert stage.relpath == PIPELINE_FILE
+            names.add(stage.name)
+        else:
+            names.add(stage.relpath)
+    assert names == {"B-gen", "C.dvc"}
+    assert (
+        isinstance(evaluation[3], PipelineStage)
+        and evaluation[3].relpath == PIPELINE_FILE
+        and evaluation[3].name == "D-gen"
+    )
+    assert (
+        not isinstance(evaluation[4], PipelineStage)
+        and evaluation[4].relpath == "E.dvc"
+    )
+
 
 def test_repro_when_cmd_changes(tmp_dir, dvc, run_copy):
     from dvc.dvcfile import PipelineFile