[Database] Cache the dependency tree in AddinDependsOn

Every time we load an extension point, we sort the data by the addin
dependency tree.

In the case of 100 extensions, we end up doing a linear search with
every addin when inserting into the sorted list.

The old code's limitation was that we had to create an addin dependency
tree on the spot for every addin with every addin.

That means we'd traverse the whole tree and construct it on every iteration,
for every check.

That potentially rounds up to O(N_DEPS) * O(N_EXTENSIONS^2).

This code makes the tree construction on demand, so the checking where it fits
is an O(1) for constructed cache, and O(N_DEPS) for non-constructed.

We transitively propagate deps of an addin to the parent, for hitting O(1)
in all cases.

The reason we now put the Name instead of FullId when doing recursive search is because,
for example, an addin written with AddinMaker will depend on MD.Core,7.0.

If 7.5 is installed, this would return false because we don't have an exact
match in the cache.

Making the HashSet use a custom comparer or getting the addin parts from
the addin id would be allocation heavy, so resort to discarding the version
when adding the list of addins (as the dependency code discards the version
anyway by doing in-exact matches)

Fixes #95. This reduces an UI hang that takes 1.70s when loading the project model extensions
in VSMac, and probably a lot more places are now faster because of this.

1 files changed, 23 insertions, 21 deletions

diff --git a/Mono.Addins/Mono.Addins.Database/AddinDatabase.cs b/Mono.Addins/Mono.Addins.Database/AddinDatabase.cs
index ebd15d1..6bef095 100644
--- a/Mono.Addins/Mono.Addins.Database/AddinDatabase.cs
+++ b/Mono.Addins/Mono.Addins.Database/AddinDatabase.cs
@@ -966,39 +966,41 @@ namespace Mono.Addins.Database
 			if (addinEngine != null)
 				addinEngine.ResetCachedData ();
 		}
-		
-		
+
+		Dictionary<string, HashSet<string>> dependsOnCache = new Dictionary<string, HashSet<string>> ();
 		public bool AddinDependsOn (string domain, string id1, string id2)
 		{
-			Hashtable visited = new Hashtable ();
-			return AddinDependsOn (visited, domain, id1, id2);
+			var depTree = GetOrCreateAddInDependencyTree (domain, id1);
+			return depTree.Contains (id2);
 		}
-		
-		bool AddinDependsOn (Hashtable visited, string domain, string id1, string id2)
+
+		HashSet<string> GetOrCreateAddInDependencyTree (string domain, string addin)
 		{
-			if (visited.Contains (id1))
-				return false;
-			
-			visited.Add (id1, id1);
-			
-			Addin addin1 = GetInstalledAddin (domain, id1, false);
-			
+			HashSet<string> cache;
+			if (dependsOnCache.TryGetValue (addin, out cache)) {
+				return cache;
+			}
+
+			dependsOnCache [addin] = cache = new HashSet<string> ();
+
+			Addin addin1 = GetInstalledAddin (domain, addin, false);
+
 			// We can assume that if the add-in is not returned here, it may be a root addin.
 			if (addin1 == null)
-				return false;
-
-			id2 = Addin.GetIdName (id2);
+				return cache;
+			
 			foreach (Dependency dep in addin1.AddinInfo.Dependencies) {
 				AddinDependency adep = dep as AddinDependency;
 				if (adep == null)
 					continue;
+				
 				string depid = Addin.GetFullId (addin1.AddinInfo.Namespace, adep.AddinId, null);
-				if (depid == id2)
-					return true;
-				else if (AddinDependsOn (visited, domain, depid, id2))
-					return true;
+				cache.Add (depid);
+
+				var recursiveDependencies = GetOrCreateAddInDependencyTree (domain, depid);
+				cache.UnionWith (recursiveDependencies);
 			}
-			return false;
+			return cache;
 		}
 		
 		public void Repair (IProgressStatus monitor, string domain)