File: Declarations\DeclarationTable.cs
Web Access
Project: src\src\Compilers\CSharp\Portable\Microsoft.CodeAnalysis.CSharp.csproj (Microsoft.CodeAnalysis.CSharp)
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
 
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
using Microsoft.CodeAnalysis.PooledObjects;
using Roslyn.Utilities;
 
namespace Microsoft.CodeAnalysis.CSharp
{
    /// <summary>
    /// A declaration table is a device which keeps track of type and namespace declarations from
    /// parse trees. It is optimized for the case where there is one set of declarations that stays
    /// constant, and a specific root namespace declaration corresponding to the currently edited
    /// file which is being added and removed repeatedly. It maintains a cache of information for
    /// "merging" the root declarations into one big summary declaration; this cache is efficiently
    /// re-used provided that the pattern of adds and removes is as we expect.
    /// </summary>
    internal sealed partial class DeclarationTable
    {
        public static readonly DeclarationTable Empty = new DeclarationTable(
            allOlderRootDeclarations: ImmutableSetWithInsertionOrder<Lazy<RootSingleNamespaceDeclaration>>.Empty,
            latestLazyRootDeclaration: null,
            cache: null);
 
        // All our root declarations.  We split these so we can separate out the unchanging 'older'
        // declarations from the constantly changing 'latest' declaration.
        private readonly ImmutableSetWithInsertionOrder<Lazy<RootSingleNamespaceDeclaration>> _allOlderRootDeclarations;
        private readonly Lazy<RootSingleNamespaceDeclaration>? _latestLazyRootDeclaration;
 
        // The cache of computed values for the old declarations.
        private readonly Cache _cache;
 
        // The lazily computed total merged declaration.
        private MergedNamespaceDeclaration? _mergedRoot;
 
        private ICollection<string>? _typeNames;
        private ICollection<string>? _namespaceNames;
        private ICollection<ReferenceDirective>? _referenceDirectives;
 
        private DeclarationTable(
            ImmutableSetWithInsertionOrder<Lazy<RootSingleNamespaceDeclaration>> allOlderRootDeclarations,
            Lazy<RootSingleNamespaceDeclaration>? latestLazyRootDeclaration,
            Cache? cache)
        {
            _allOlderRootDeclarations = allOlderRootDeclarations;
            _latestLazyRootDeclaration = latestLazyRootDeclaration;
            _cache = cache ?? new Cache(this);
        }
 
        public DeclarationTable AddRootDeclaration(Lazy<RootSingleNamespaceDeclaration> lazyRootDeclaration)
        {
            // We can only re-use the cache if we don't already have a 'latest' item for the decl
            // table.
            if (_latestLazyRootDeclaration == null)
            {
                return new DeclarationTable(_allOlderRootDeclarations, lazyRootDeclaration, _cache);
            }
            else
            {
                // we already had a 'latest' item.  This means we're hearing about a change to a
                // different tree.  Add old latest item to the 'oldest' collection
                // and don't reuse the cache.
                return new DeclarationTable(_allOlderRootDeclarations.Add(_latestLazyRootDeclaration), lazyRootDeclaration, cache: null);
            }
        }
 
        public DeclarationTable RemoveRootDeclaration(Lazy<RootSingleNamespaceDeclaration> lazyRootDeclaration)
        {
            // We can only reuse the cache if we're removing the decl that was just added.
            if (_latestLazyRootDeclaration == lazyRootDeclaration)
            {
                return new DeclarationTable(_allOlderRootDeclarations, latestLazyRootDeclaration: null, cache: _cache);
            }
            else
            {
                // We're removing a different tree than the latest one added.  We need
                // to remove the passed in root from our 'older' list.  We also can't reuse the
                // cache.
                //
                // Note: we can keep around the 'latestLazyRootDeclaration'.
                return new DeclarationTable(_allOlderRootDeclarations.Remove(lazyRootDeclaration), _latestLazyRootDeclaration, cache: null);
            }
        }
 
        // The merged-tree-reuse story goes like this. We have a "forest" of old declarations, and
        // possibly a lone tree of new declarations. We construct a merged declaration by merging
        // together everything in the forest. This we can re-use from edit to edit, provided that
        // nothing is added to or removed from the forest. We construct a merged declaration from
        // the lone tree if there is one. (The lone tree might have nodes inside it that need
        // merging, if there are two halves of one partial class.)  Once we have two merged trees, we
        // construct the full merged tree by merging them both together. So, diagrammatically, we
        // have:
        //
        //                   MergedRoot
        //                  /          \
        //   old merged root            new merged root
        //  /   |   |   |   \                \
        // old singles forest                 new single tree
        public MergedNamespaceDeclaration GetMergedRoot(CSharpCompilation compilation)
        {
            Debug.Assert(compilation.Declarations == this);
            if (_mergedRoot == null)
            {
                Interlocked.CompareExchange(ref _mergedRoot, CalculateMergedRoot(compilation), null);
            }
            return _mergedRoot;
        }
 
        // Internal for unit tests only.
        internal MergedNamespaceDeclaration CalculateMergedRoot(CSharpCompilation compilation)
        {
            var oldRoot = _cache.MergedRoot;
            if (_latestLazyRootDeclaration == null)
            {
                return oldRoot;
            }
            else if (oldRoot == null)
            {
                return MergedNamespaceDeclaration.Create(_latestLazyRootDeclaration.Value);
            }
            else
            {
                var oldRootDeclarations = oldRoot.Declarations;
                var builder = ArrayBuilder<SingleNamespaceDeclaration>.GetInstance(oldRootDeclarations.Length + 1);
                builder.AddRange(oldRootDeclarations);
                builder.Add(_latestLazyRootDeclaration.Value);
                // Sort the root namespace declarations to match the order of SyntaxTrees.
                if (compilation != null)
                {
                    builder.Sort(new RootNamespaceLocationComparer(compilation));
                }
                return MergedNamespaceDeclaration.Create(builder.ToImmutableAndFree());
            }
        }
 
        private sealed class RootNamespaceLocationComparer : IComparer<SingleNamespaceDeclaration>
        {
            private readonly CSharpCompilation _compilation;
 
            internal RootNamespaceLocationComparer(CSharpCompilation compilation)
            {
                _compilation = compilation;
            }
 
            [PerformanceSensitive(
                "https://github.com/dotnet/roslyn/issues/23582",
                Constraint = "Avoid " + nameof(SingleNamespaceOrTypeDeclaration.Location) + " since it has a costly allocation on this fast path.")]
            public int Compare(SingleNamespaceDeclaration? x, SingleNamespaceDeclaration? y)
            {
                return _compilation.CompareSourceLocations(x!.SyntaxReference, y!.SyntaxReference);
            }
        }
 
        private ICollection<string> GetMergedTypeNames()
        {
            var cachedTypeNames = _cache.TypeNames;
 
            if (_latestLazyRootDeclaration == null)
            {
                return cachedTypeNames;
            }
            else
            {
                return UnionCollection<string>.Create(cachedTypeNames, GetTypeNames(_latestLazyRootDeclaration.Value));
            }
        }
 
        private ICollection<string> GetMergedNamespaceNames()
        {
            var cachedNamespaceNames = _cache.NamespaceNames;
 
            if (_latestLazyRootDeclaration == null)
            {
                return cachedNamespaceNames;
            }
            else
            {
                return UnionCollection<string>.Create(cachedNamespaceNames, GetNamespaceNames(_latestLazyRootDeclaration.Value));
            }
        }
 
        private ICollection<ReferenceDirective> GetMergedReferenceDirectives()
        {
            var cachedReferenceDirectives = _cache.ReferenceDirectives;
 
            if (_latestLazyRootDeclaration == null)
            {
                return cachedReferenceDirectives;
            }
            else
            {
                return UnionCollection<ReferenceDirective>.Create(cachedReferenceDirectives, _latestLazyRootDeclaration.Value.ReferenceDirectives);
            }
        }
 
        private static readonly Predicate<Declaration> s_isNamespacePredicate = d => d.Kind == DeclarationKind.Namespace;
        private static readonly Predicate<Declaration> s_isTypePredicate = d => d.Kind != DeclarationKind.Namespace;
 
        private static ISet<string> GetTypeNames(Declaration declaration)
        {
            return GetNames(declaration, s_isTypePredicate);
        }
 
        private static ISet<string> GetNamespaceNames(Declaration declaration)
        {
            return GetNames(declaration, s_isNamespacePredicate);
        }
 
        private static ISet<string> GetNames(Declaration declaration, Predicate<Declaration> predicate)
        {
            var set = new HashSet<string>();
            var stack = new Stack<Declaration>();
            stack.Push(declaration);
 
            while (stack.Count > 0)
            {
                var current = stack.Pop();
                if (current == null)
                {
                    continue;
                }
 
                if (predicate(current))
                {
                    set.Add(current.Name);
                }
 
                foreach (var child in current.Children)
                {
                    stack.Push(child);
                }
            }
 
            return SpecializedCollections.ReadOnlySet(set);
        }
 
        public ICollection<string> TypeNames
        {
            get
            {
                if (_typeNames is null)
                    Interlocked.CompareExchange(ref _typeNames, GetMergedTypeNames(), comparand: null);
 
                return _typeNames;
            }
        }
 
        public ICollection<string> NamespaceNames
        {
            get
            {
                if (_namespaceNames is null)
                    Interlocked.CompareExchange(ref _namespaceNames, GetMergedNamespaceNames(), comparand: null);
 
                return _namespaceNames;
            }
        }
 
        public IEnumerable<ReferenceDirective> ReferenceDirectives
        {
            get
            {
                if (_referenceDirectives is null)
                    Interlocked.CompareExchange(ref _referenceDirectives, GetMergedReferenceDirectives(), comparand: null);
 
                return _referenceDirectives;
            }
        }
 
        public static bool ContainsName(
            MergedNamespaceDeclaration mergedRoot,
            string name,
            SymbolFilter filter,
            CancellationToken cancellationToken)
        {
            return ContainsNameHelper(
                mergedRoot,
                n => n == name,
                filter,
                t => t.MemberNames.Value.Contains(name),
                cancellationToken);
        }
 
        public static bool ContainsName(
            MergedNamespaceDeclaration mergedRoot,
            Func<string, bool> predicate,
            SymbolFilter filter,
            CancellationToken cancellationToken)
        {
            return ContainsNameHelper(
                mergedRoot, predicate, filter,
                t =>
                {
                    foreach (var name in t.MemberNames.Value)
                    {
                        if (predicate(name))
                        {
                            return true;
                        }
                    }
 
                    return false;
                }, cancellationToken);
        }
 
        private static bool ContainsNameHelper(
            MergedNamespaceDeclaration mergedRoot,
            Func<string, bool> predicate,
            SymbolFilter filter,
            Func<SingleTypeDeclaration, bool> typePredicate,
            CancellationToken cancellationToken)
        {
            var includeNamespace = (filter & SymbolFilter.Namespace) == SymbolFilter.Namespace;
            var includeType = (filter & SymbolFilter.Type) == SymbolFilter.Type;
            var includeMember = (filter & SymbolFilter.Member) == SymbolFilter.Member;
 
            var stack = new Stack<MergedNamespaceOrTypeDeclaration>();
            stack.Push(mergedRoot);
 
            while (stack.Count > 0)
            {
                cancellationToken.ThrowIfCancellationRequested();
 
                var current = stack.Pop();
                if (current == null)
                {
                    continue;
                }
 
                if (current.Kind == DeclarationKind.Namespace)
                {
                    if (includeNamespace && predicate(current.Name))
                    {
                        return true;
                    }
                }
                else
                {
                    if (includeType && predicate(current.Name))
                    {
                        return true;
                    }
 
                    if (includeMember)
                    {
                        var mergedType = (MergedTypeDeclaration)current;
                        foreach (var typeDecl in mergedType.Declarations)
                        {
                            if (typePredicate(typeDecl))
                            {
                                return true;
                            }
                        }
                    }
                }
 
                foreach (var child in current.Children)
                {
                    if (child is MergedNamespaceOrTypeDeclaration childNamespaceOrType)
                    {
                        if (includeMember || includeType || childNamespaceOrType.Kind == DeclarationKind.Namespace)
                        {
                            stack.Push(childNamespaceOrType);
                        }
                    }
                }
            }
 
            return false;
        }
    }
}