From d997476f011ae50036ffcabc03af2eaf85f33967 Mon Sep 17 00:00:00 2001
From: eric thul <thul.eric@gmail.com>
Date: Sat, 2 May 2015 10:27:36 -0400
Subject: [PATCH] Optimizing dependency list generation

Improving the generation of the dependencies in `mkDeps` to avoid a
`RangeError` on large inputs.

Resolves #9
---
 bower.json      |  3 ++-
 src/Loader.purs | 19 +++++++++++++------
 2 files changed, 15 insertions(+), 7 deletions(-)

diff --git a/bower.json b/bower.json
index dddddf9..2ee2486 100644
--- a/bower.json
+++ b/bower.json
@@ -11,6 +11,7 @@
     "purescript-tuples": "~0.3.4",
     "purescript-maps": "~0.3.3",
     "purescript-arrays": "~0.3.7",
-    "purescript-monad-eff": "~0.1.0"
+    "purescript-monad-eff": "~0.1.0",
+    "purescript-sets": "0.3.2"
   }
 }
diff --git a/src/Loader.purs b/src/Loader.purs
index 523aa7a..aae51c0 100644
--- a/src/Loader.purs
+++ b/src/Loader.purs
@@ -9,9 +9,11 @@ import Control.Monad.Eff (Eff())
 import Control.Monad.Eff.Class (liftEff)
 import Control.Monad.Eff.Exception (error)
 
-import Data.Array ((!!), catMaybes, concat, nub, null)
+import Data.Array ((!!), catMaybes, concat, filter, null)
+import Data.Foldable (foldl)
 import Data.Function (Fn2(), mkFn2)
 import Data.Maybe (Maybe(..), fromMaybe, maybe)
+import Data.Set (Set(), empty, insert, member, toList, unions)
 import Data.String (joinWith, split)
 import Data.String.Regex (Regex(), match, noFlags, regex)
 import Data.StrMap (StrMap(), fromList, lookup)
@@ -60,11 +62,16 @@ mkGraph files = (fromList <<< catMaybes) <$> sequence (parse <$> files)
                         return $ (\a -> tuple2 a { file: file, imports: imports }) <$> key
 
 mkDeps :: forall eff. String -> Graph -> [String]
-mkDeps key graph = nub $ go [] key
-  where go acc key =
-    maybe acc (\a -> if null a.imports
-                       then acc
-                       else concat $ go (acc <> a.imports) <$> a.imports) (lookup key graph)
+mkDeps key graph = toList $ go empty key
+  where
+    go :: Set String -> String -> Set String
+    go acc key =
+      let node = fromMaybe {file: "", imports: []} (lookup key graph)
+          uniq = filter (not <<< flip member acc) node.imports
+          acc' = foldl (flip insert) acc node.imports
+       in if null uniq
+             then acc'
+             else unions $ go acc' <$> uniq
 
 addDeps :: forall eff. LoaderRef -> Graph -> [String] -> Eff (loader :: Loader | eff) Unit
 addDeps ref graph deps = const unit <$> (sequence $ add <$> deps)
-- 
2.41.0