File: src\RoslynAnalyzers\Utilities\FlowAnalysis\Extensions\BasicBlockExtensions.cs
Web Access
Project: src\src\RoslynAnalyzers\Microsoft.CodeAnalysis.AnalyzerUtilities\Microsoft.CodeAnalysis.AnalyzerUtilities.csproj (Microsoft.CodeAnalysis.AnalyzerUtilities)
// 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.Diagnostics.CodeAnalysis;
using Analyzer.Utilities.PooledObjects;
using Microsoft.CodeAnalysis.Operations;
 
namespace Microsoft.CodeAnalysis.FlowAnalysis
{
    internal static class BasicBlockExtensions
    {
        internal static IEnumerable<(BasicBlock predecessorBlock, BranchWithInfo branchWithInfo)> GetPredecessorsWithBranches(this BasicBlock basicBlock, ControlFlowGraph cfg)
        {
            foreach (ControlFlowBranch predecessorBranch in basicBlock.Predecessors)
            {
                var branchWithInfo = new BranchWithInfo(predecessorBranch);
                if (!predecessorBranch.FinallyRegions.IsEmpty)
                {
                    var lastFinally = predecessorBranch.FinallyRegions[^1];
                    yield return (predecessorBlock: cfg.Blocks[lastFinally.LastBlockOrdinal], branchWithInfo);
                }
                else
                {
                    yield return (predecessorBlock: predecessorBranch.Source, branchWithInfo);
                }
            }
        }
 
        internal static ITypeSymbol? GetEnclosingRegionExceptionType(this BasicBlock basicBlock)
        {
            var region = basicBlock.EnclosingRegion;
            while (region != null)
            {
                if (region.ExceptionType != null)
                {
                    return region.ExceptionType;
                }
 
                region = region.EnclosingRegion;
            }
 
            return null;
        }
 
        public static IEnumerable<IOperation> DescendantOperations(this BasicBlock basicBlock)
        {
            foreach (var statement in basicBlock.Operations)
            {
                foreach (var operation in statement.DescendantsAndSelf())
                {
                    yield return operation;
                }
            }
 
            if (basicBlock.BranchValue != null)
            {
                foreach (var operation in basicBlock.BranchValue.DescendantsAndSelf())
                {
                    yield return operation;
                }
            }
        }
 
        /// <summary>
        /// Returns true if the given <paramref name="basicBlock"/> is contained in a control flow region with the given <paramref name="regionKind"/>.
        /// </summary>
        public static bool IsContainedInRegionOfKind(this BasicBlock basicBlock, ControlFlowRegionKind regionKind)
            => basicBlock.GetContainingRegionOfKind(regionKind) != null;
 
        /// <summary>
        /// Returns the innermost control flow region of the given <paramref name="regionKind"/> that contains the given <paramref name="basicBlock"/>.
        /// </summary>
        public static ControlFlowRegion? GetContainingRegionOfKind(this BasicBlock basicBlock, ControlFlowRegionKind regionKind)
        {
            var enclosingRegion = basicBlock.EnclosingRegion;
            while (enclosingRegion != null)
            {
                if (enclosingRegion.Kind == regionKind)
                {
                    return enclosingRegion;
                }
 
                enclosingRegion = enclosingRegion.EnclosingRegion;
            }
 
            return null;
        }
 
        /// <summary>
        /// Returns true if the given basic block is the first block of a finally region.
        /// </summary>
        public static bool IsFirstBlockOfFinally(this BasicBlock basicBlock, [NotNullWhen(returnValue: true)] out ControlFlowRegion? finallyRegion)
            => basicBlock.IsFirstBlockOfRegionKind(ControlFlowRegionKind.Finally, out finallyRegion);
 
        /// <summary>
        /// Returns true if the given basic block is the last block of a finally region.
        /// </summary>
        public static bool IsLastBlockOfFinally(this BasicBlock basicBlock, [NotNullWhen(returnValue: true)] out ControlFlowRegion? finallyRegion)
            => basicBlock.IsLastBlockOfRegionKind(ControlFlowRegionKind.Finally, out finallyRegion);
 
        /// <summary>
        /// Returns true if the given basic block is the first block of a region of the given regionKind.
        /// </summary>
        public static bool IsFirstBlockOfRegionKind(this BasicBlock basicBlock, ControlFlowRegionKind regionKind, [NotNullWhen(returnValue: true)] out ControlFlowRegion? region)
            => basicBlock.IsFirstOrLastBlockOfRegionKind(regionKind, first: true, out region);
 
        /// <summary>
        /// Returns true if the given basic block is the last block of a region of the given regionKind.
        /// </summary>
        public static bool IsLastBlockOfRegionKind(this BasicBlock basicBlock, ControlFlowRegionKind regionKind, [NotNullWhen(returnValue: true)] out ControlFlowRegion? region)
            => basicBlock.IsFirstOrLastBlockOfRegionKind(regionKind, first: false, out region);
 
        private static bool IsFirstOrLastBlockOfRegionKind(this BasicBlock basicBlock, ControlFlowRegionKind regionKind, bool first, [NotNullWhen(returnValue: true)] out ControlFlowRegion? foundRegion)
        {
            foundRegion = null;
 
            var enclosingRegion = basicBlock.EnclosingRegion;
            while (enclosingRegion != null)
            {
                var ordinalToCompare = first ? enclosingRegion.FirstBlockOrdinal : enclosingRegion.LastBlockOrdinal;
                if (ordinalToCompare != basicBlock.Ordinal)
                {
                    return false;
                }
 
                if (enclosingRegion.Kind == regionKind)
                {
                    foundRegion = enclosingRegion;
                    return true;
                }
 
                enclosingRegion = enclosingRegion.EnclosingRegion;
            }
 
            return false;
        }
 
        /// <summary>
        /// Returns true if the given basic block is the first block of a compiler generated finally region.
        /// </summary>
        public static bool IsFirstBlockOfCompilerGeneratedFinally(this BasicBlock basicBlock, ControlFlowGraph cfg)
        {
            if (!basicBlock.IsFirstBlockOfRegionKind(ControlFlowRegionKind.Finally, out var finallyRegion))
            {
                return false;
            }
 
            foreach (var operation in finallyRegion.DescendantOperations(cfg))
            {
                if (!operation.IsImplicit)
                {
                    return false;
                }
            }
 
            return true;
        }
 
        internal static ControlFlowRegion? GetInnermostRegionStartedByBlock(this BasicBlock basicBlock, ControlFlowRegionKind regionKind)
        {
            if (basicBlock.EnclosingRegion?.FirstBlockOrdinal != basicBlock.Ordinal)
            {
                return null;
            }
 
            var enclosingRegion = basicBlock.EnclosingRegion;
            while (enclosingRegion.Kind != regionKind)
            {
                enclosingRegion = enclosingRegion.EnclosingRegion;
                if (enclosingRegion?.FirstBlockOrdinal != basicBlock.Ordinal)
                {
                    return null;
                }
            }
 
            return enclosingRegion;
        }
 
        /// <summary>
        /// Gets the maximum ordinal of a conditional or fall through successor of the given basic block.
        /// Returns -1 if the block has no conditional or fall through successor,
        /// for example, if the block only has a structured exception handling branch for throw operation.
        /// </summary>
        /// <param name="basicBlock"></param>
        /// <returns></returns>
        internal static int GetMaxSuccessorOrdinal(this BasicBlock basicBlock)
            => Math.Max(basicBlock.FallThroughSuccessor?.Destination?.Ordinal ?? -1,
                        basicBlock.ConditionalSuccessor?.Destination?.Ordinal ?? -1);
 
        internal static bool DominatesPredecessors(this BasicBlock? basicBlock, ControlFlowGraph cfg)
        {
            if (basicBlock == null ||
                basicBlock.Predecessors.IsEmpty)
            {
                return false;
            }
 
            using var processedOrdinals = PooledHashSet<int>.GetInstance();
            using var unprocessedOrdinals = ArrayBuilder<int>.GetInstance();
            foreach (var predecessor in basicBlock.Predecessors)
            {
                var sourceBlock = predecessor.Source;
                if (!DominatesBlock(sourceBlock, basicBlock, processedOrdinals, unprocessedOrdinals))
                {
                    return false;
                }
 
                processedOrdinals.Add(sourceBlock.Ordinal);
            }
 
            while (unprocessedOrdinals.Count > 0)
            {
                var ordinal = unprocessedOrdinals[0];
                Debug.Assert(ordinal < basicBlock.Ordinal);
                unprocessedOrdinals.RemoveAt(0);
 
                if (processedOrdinals.Add(ordinal))
                {
                    var sourceBlock = cfg.Blocks[ordinal];
                    if (!DominatesBlock(sourceBlock, basicBlock, processedOrdinals, unprocessedOrdinals))
                    {
                        return false;
                    }
                }
            }
 
            return true;
 
            static bool DominatesBlock(BasicBlock sourceBlock, BasicBlock basicBlock, PooledHashSet<int> processedOrdinals, ArrayBuilder<int> unprocessedOrdinals)
                => DominatesBranch(sourceBlock.ConditionalSuccessor, basicBlock, processedOrdinals, unprocessedOrdinals) &&
                   DominatesBranch(sourceBlock.FallThroughSuccessor, basicBlock, processedOrdinals, unprocessedOrdinals);
 
            static bool DominatesBranch(ControlFlowBranch? branch, BasicBlock basicBlock, PooledHashSet<int> processedOrdinals, ArrayBuilder<int> unprocessedOrdinals)
            {
                var destinationBlock = branch?.Destination;
                if (destinationBlock == null ||
                    destinationBlock == basicBlock)
                {
                    return true;
                }
 
                if (!processedOrdinals.Contains(destinationBlock.Ordinal))
                {
                    unprocessedOrdinals.Add(destinationBlock.Ordinal);
                }
 
                return destinationBlock.Ordinal <= basicBlock.Ordinal;
            }
        }
    }
}