Slow "unreachable modules" rule

[neelance]

This rule has become very slow (additional 25 seconds) on our large repo:

{
  name: "no-unreachable-from-entrypoint",
  severity: "error",
  from: {
    path: entrypointsRegex,
  },
  to: {
    path: "src",
    pathNot: entrypointsRegex,
    reachable: false,
  },
},

Here is a diff that already cuts half of the duration:

diff --git a/src/enrich/derive/reachable.mjs b/src/enrich/derive/reachable.mjs
index a384cdcb..99ad6049 100644
--- a/src/enrich/derive/reachable.mjs
+++ b/src/enrich/derive/reachable.mjs
@@ -139,11 +139,10 @@ function addReachesToModule(pModule, pGraph, pIndexedGraph, pReachableRule) {
   return pModule;
 }
 
-function addReachableToModule(pModule, pGraph, pIndexedGraph, pReachableRule) {
-  const lFromModules = pGraph.filter(isModuleInRuleFrom(pReachableRule));
+function addReachableToModule(pModule, pIndexedGraph, pReachableRule, pFromModules) {
   let lFound = false;
 
-  for (let lFromModule of lFromModules) {
+  for (let lFromModule of pFromModules) {
     if (
       !lFound &&
       pModule.source !== lFromModule.source &&
@@ -164,6 +163,8 @@ function addReachableToModule(pModule, pGraph, pIndexedGraph, pReachableRule) {
 }
 
 function addReachabilityToGraph(pGraph, pIndexedGraph, pReachableRule) {
+  const lFromModules = pGraph.filter(isModuleInRuleFrom(pReachableRule));
+
   return pGraph.map((pModule) => {
     let lClonedModule = structuredClone(pModule);
 
@@ -178,9 +179,9 @@ function addReachabilityToGraph(pGraph, pIndexedGraph, pReachableRule) {
     if (shouldAddReachable(pReachableRule, lClonedModule, pGraph)) {
       lClonedModule = addReachableToModule(
         lClonedModule,
-        pGraph,
         pIndexedGraph,
         pReachableRule,
+        lFromModules,
       );
     }
     return lClonedModule;

Additionally the rule is slow because it searches the graph for a path repeatedly by calling getPath for each module. In theory it should be possible to just calculate all reachability from the entry points once to determine which modules are not reachable.

[sverweij]

Hi @neelance (as said in the other issue - sorry for the slow response ...)

Thanks for digging into this! The patch already seems like a good catch - and your additional suggestion is very likely on point

I'll try to carve out some time this weekend to at least apply the patch and think about making the 'algorithm' less hamfisted.

[sverweij]

Hi @neelance - as you might've noticed I've merged your patch (and taken the liberty to credit you in both the commit and the release notes) and released it in dependency-cruiser@16.10.1 . Thanks again for the patch, (and for putting attention to more improvements)!

[neelance]

Thanks!

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs.