[Database] Cache the dependency tree in AddinDependsOn

[Therzok]

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.

[slluis]

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.

Ok, but you should take into account that add-ins can be upgraded at run-time. So we may have AddinMaker 1.2 installed and then upgrade it to 1.3, which may have a different set of dependencies and extensions.

[Therzok]

Is there any way to detect that an addin was upgraded at runtime so we invalidate the cache?

[Therzok]

Okay, I think we can reset the dictionary inside ResetCachedData.

[Therzok]

Ready for re-review

[Therzok]

Is this better? Tried to make the changes non-intrusive.