From 3381da9cdbe7d9516271154c765a369b70cf8f49 Mon Sep 17 00:00:00 2001
From: Karen Arutyunov <karen@codesynthesis.com>
Date: Thu, 25 May 2023 12:32:30 +0300
Subject: Optimize build_packages::collect_order_dependents() to skip already
 visited dependencies

---
 bpkg/pkg-build-collect.cxx | 27 ++++++++++++++++++++++++---
 bpkg/pkg-build-collect.hxx | 25 ++++++++++++++++++++-----
 2 files changed, 44 insertions(+), 8 deletions(-)

diff --git a/bpkg/pkg-build-collect.cxx b/bpkg/pkg-build-collect.cxx
index 98b76b9..95e4eee 100644
--- a/bpkg/pkg-build-collect.cxx
+++ b/bpkg/pkg-build-collect.cxx
@@ -5769,6 +5769,10 @@ namespace bpkg
   collect_order_dependents (const repointed_dependents& rpt_depts,
                             unsatisfied_dependents& unsatisfied_depts)
   {
+    // Note: the pointer is stable (points to a value in std::map).
+    //
+    set<const build_package*> visited_deps;
+
     // For each package on the list we want to insert all its dependents
     // before it so that they get configured after the package on which they
     // depend is configured (remember, our build order is reverse, with the
@@ -5787,14 +5791,18 @@ namespace bpkg
       // Dropped package may have no dependents.
       //
       if (*p.action != build_package::drop && p.reconfigure ())
-        collect_order_dependents (i, rpt_depts, unsatisfied_depts);
+        collect_order_dependents (i,
+                                  rpt_depts,
+                                  unsatisfied_depts,
+                                  visited_deps);
     }
   }
 
   void build_packages::
   collect_order_dependents (iterator pos,
                             const repointed_dependents& rpt_depts,
-                            unsatisfied_dependents& unsatisfied_depts)
+                            unsatisfied_dependents& unsatisfied_depts,
+                            set<const build_package*>& visited_deps)
   {
     tracer trace ("collect_order_dependents");
 
@@ -5802,6 +5810,12 @@ namespace bpkg
 
     build_package& p (*pos);
 
+    // Bail out if the dependency has already been visited and add it to the
+    // visited set otherwise.
+    //
+    if (!visited_deps.insert (&p).second)
+      return;
+
     database& pdb (p.db);
     const shared_ptr<selected_package>& sp (p.selected);
 
@@ -5988,6 +6002,12 @@ namespace bpkg
               {
                 erase (dpos);
                 dpos = insert (pos, dp);
+
+                // Remove the moved dependent from the visited dependencies
+                // set, if present, so its own dependents can be reordered to
+                // the left of this dependent.
+                //
+                visited_deps.erase (&dp);
                 break;
               }
             }
@@ -6013,7 +6033,8 @@ namespace bpkg
         //
         collect_order_dependents (i->second.position,
                                   rpt_depts,
-                                  unsatisfied_depts);
+                                  unsatisfied_depts,
+                                  visited_deps);
       }
     }
   }
diff --git a/bpkg/pkg-build-collect.hxx b/bpkg/pkg-build-collect.hxx
index 30f993b..f237b11 100644
--- a/bpkg/pkg-build-collect.hxx
+++ b/bpkg/pkg-build-collect.hxx
@@ -1440,11 +1440,6 @@ namespace bpkg
                               unsatisfied_dependents&);
 
     void
-    collect_order_dependents (iterator,
-                              const repointed_dependents&,
-                              unsatisfied_dependents&);
-
-    void
     clear ();
 
     void
@@ -1525,6 +1520,26 @@ namespace bpkg
            const function<find_database_function>&,
            bool reorder);
 
+    // Skip the dependents collection/ordering for the specified dependency if
+    // that has already be done.
+    //
+    // Note that if this function has already been called for this dependency,
+    // then all its dependents are already in the map and the dependency
+    // constraints have been checked for them. Also they are in the list and
+    // are ordered to the left of this dependency, unless this dependency has
+    // been moved to the left itself since the previous visit. Such a move can
+    // only happen if this dependency is a dependent of some other dependency
+    // whose dependents have been collected/ordered since that previous visit.
+    // This function tracks such moves and just removes the moved dependencies
+    // from the visited set, so their dependents can be properly reordered
+    // after the move.
+    //
+    void
+    collect_order_dependents (iterator,
+                              const repointed_dependents&,
+                              unsatisfied_dependents&,
+                              std::set<const build_package*>& visited_deps);
+
   private:
     struct data_type
     {
-- 
cgit v1.1