File: DataFlow\ControlFlowGraphProxy.cs
Web Access
Project: src\src\tools\illink\src\ILLink.RoslynAnalyzer\ILLink.RoslynAnalyzer.csproj (ILLink.RoslynAnalyzer)
// Copyright (c) .NET Foundation and contributors. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for full license information.
 
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using ILLink.Shared.DataFlow;
using Microsoft.CodeAnalysis.CSharp.Syntax;
using Microsoft.CodeAnalysis.FlowAnalysis;
 
using ControlFlowBranch = ILLink.Shared.DataFlow.IControlFlowGraph<
    ILLink.RoslynAnalyzer.DataFlow.BlockProxy,
    ILLink.RoslynAnalyzer.DataFlow.RegionProxy
>.ControlFlowBranch;
 
namespace ILLink.RoslynAnalyzer.DataFlow
{
    // Blocks should be usable as keys of a dictionary.
    // The record equality implementation will check for reference equality
    // on the underlying BasicBlock, so uses of this class should not expect
    // any kind of value equality for different block instances. In practice
    // this should be fine as long as we consistently use block instances from
    // a single ControlFlowGraph.
    public readonly record struct BlockProxy(BasicBlock Block) : IBlock<BlockProxy>
    {
        public override string ToString()
        {
            return base.ToString() + $"[{Block.Ordinal}]";
        }
 
        public ConditionKind ConditionKind => (ConditionKind)Block.ConditionKind;
    }
 
    public readonly record struct RegionProxy(ControlFlowRegion Region) : IRegion<RegionProxy>
    {
        public RegionKind Kind => Region.Kind switch
        {
            ControlFlowRegionKind.Try => RegionKind.Try,
            ControlFlowRegionKind.Catch => RegionKind.Catch,
            ControlFlowRegionKind.Filter => RegionKind.Filter,
            ControlFlowRegionKind.Finally => RegionKind.Finally,
            _ => throw new InvalidOperationException()
        };
    }
 
    public readonly record struct ControlFlowGraphProxy(ControlFlowGraph ControlFlowGraph) : IControlFlowGraph<BlockProxy, RegionProxy>
    {
        public IEnumerable<BlockProxy> Blocks
        {
            get
            {
                foreach (var block in ControlFlowGraph.Blocks)
                    yield return new BlockProxy(block);
            }
        }
 
        public BlockProxy Entry => new BlockProxy(ControlFlowGraph.EntryBlock());
 
        public static ControlFlowBranch CreateProxyBranch(Microsoft.CodeAnalysis.FlowAnalysis.ControlFlowBranch branch)
        {
            var finallyRegions = ImmutableArray.CreateBuilder<RegionProxy>();
            foreach (var region in branch.FinallyRegions)
            {
                Debug.Assert(region != null);
                if (region == null)
                    continue;
                finallyRegions.Add(new RegionProxy(region));
            }
 
            // Translate from the Roslyn CFG condition kind to our model.
            // Roslyn blocks have at most two successors, a fall-through and a conditional successor.
            // The ConditionKind stored on the block indicates the condition under which the conditional successor (if there is one) is taken.
 
            // In our model, blocks may have any number of successors. The ConditionKind stored on the branch indicates the condition under
            // which that branch (not necessarily corresponding to Roslyn's conditional successor) is taken.
 
            // So if this branch represents Roslyn's conditional successor, we simply translate the WhenTrue/WhenFalse condition.
            // But if this is the fall-through branch, this branch is taken in the opposite condition to the conditional successor so we invert it.
            var conditionKind = branch.Source.ConditionKind switch
            {
                ControlFlowConditionKind.None => ConditionKind.Unconditional,
                ControlFlowConditionKind.WhenFalse => branch.IsConditionalSuccessor ? ConditionKind.WhenFalse : ConditionKind.WhenTrue,
                ControlFlowConditionKind.WhenTrue => branch.IsConditionalSuccessor ? ConditionKind.WhenTrue : ConditionKind.WhenFalse,
                _ => throw new InvalidOperationException()
            };
 
            // Destination might be null in a 'throw' branch.
            return new ControlFlowBranch(
                new BlockProxy(branch.Source),
                branch.Destination == null ? null : new BlockProxy(branch.Destination),
                finallyRegions.ToImmutable(),
                conditionKind);
        }
 
        // This is implemented by getting predecessors of the underlying Roslyn BasicBlock.
        // This is fine as long as the blocks come from the correct control-flow graph.
        public IEnumerable<ControlFlowBranch> GetPredecessors(BlockProxy block)
        {
            foreach (var predecessor in block.Block.Predecessors)
            {
                if (CreateProxyBranch(predecessor) is ControlFlowBranch branch)
                    yield return branch;
            }
        }
 
        public IEnumerable<ControlFlowBranch> GetSuccessors(BlockProxy block)
        {
            if (block.Block.ConditionalSuccessor is Microsoft.CodeAnalysis.FlowAnalysis.ControlFlowBranch conditionalSuccessor)
                yield return CreateProxyBranch(conditionalSuccessor);
            if (block.Block.FallThroughSuccessor is Microsoft.CodeAnalysis.FlowAnalysis.ControlFlowBranch fallThroughSuccessor)
                yield return CreateProxyBranch(fallThroughSuccessor);
        }
 
        public bool TryGetEnclosingTryOrCatchOrFilter(BlockProxy block, out RegionProxy tryOrCatchOrFilterRegion)
        {
            return TryGetTryOrCatchOrFilter(block.Block.EnclosingRegion, out tryOrCatchOrFilterRegion);
        }
 
        public bool TryGetEnclosingTryOrCatchOrFilter(RegionProxy regionProxy, out RegionProxy tryOrCatchOrFilterRegion)
        {
            return TryGetTryOrCatchOrFilter(regionProxy.Region.EnclosingRegion, out tryOrCatchOrFilterRegion);
        }
 
        private static bool TryGetTryOrCatchOrFilter(ControlFlowRegion? region, out RegionProxy tryOrCatchOrFilterRegion)
        {
            tryOrCatchOrFilterRegion = default;
            // The check for ControlFlowRegionKind.Root prevents us from walking out to regions that
            // contain code outside of the current control flow graph.
            while (region != null && region.Kind != ControlFlowRegionKind.Root)
            {
                if (region.Kind is ControlFlowRegionKind.Try or ControlFlowRegionKind.Catch or ControlFlowRegionKind.Filter)
                {
                    tryOrCatchOrFilterRegion = new RegionProxy(region);
                    return true;
                }
                region = region.EnclosingRegion;
            }
            return false;
        }
 
        public bool TryGetEnclosingFinally(BlockProxy block, out RegionProxy catchRegion)
        {
            catchRegion = default;
            ControlFlowRegion? region = block.Block.EnclosingRegion;
            // The check for ControlFlowRegionKind.Root prevents us from walking out to regions that
            // contain code outside of the current control flow graph.
            while (region != null && region.Kind != ControlFlowRegionKind.Root)
            {
                if (region.Kind == ControlFlowRegionKind.Finally)
                {
                    catchRegion = new RegionProxy(region);
                    return true;
                }
                region = region.EnclosingRegion;
            }
            return false;
        }
 
        public RegionProxy GetCorrespondingTry(RegionProxy catchOrFilterOrFinallyRegion)
        {
            if (catchOrFilterOrFinallyRegion.Region.Kind is not (ControlFlowRegionKind.Catch or ControlFlowRegionKind.Filter or ControlFlowRegionKind.Finally))
                throw new ArgumentException("Must be a catch, filter, or finally region: {}", nameof(catchOrFilterOrFinallyRegion));
 
            // Finally -> TryAndFinally
            // Catch -> TryAndCatch or FilterAndHandler
            // Filter -> FilterAndHandler
            var enclosingRegion = catchOrFilterOrFinallyRegion.Region.EnclosingRegion!;
            // FilterAndHandler -> TryAndCatch
            if (enclosingRegion.Kind == ControlFlowRegionKind.FilterAndHandler)
            {
                enclosingRegion = enclosingRegion.EnclosingRegion!;
                Debug.Assert(enclosingRegion.Kind == ControlFlowRegionKind.TryAndCatch);
            }
 
            // For TryAndFinally or TryAndCatch, get the Try region.
            foreach (var nested in enclosingRegion.NestedRegions)
            {
                // Note that for try+catch+finally, the try corresponding to the finally will not be the same as
                // the try corresponding to the catch, because Roslyn represents this region hierarchy the same as
                // a try+catch nested inside the try block of a try+finally.
                if (nested.Kind == ControlFlowRegionKind.Try)
                    return new(nested);
            }
            throw new InvalidOperationException();
        }
 
        public IEnumerable<RegionProxy> GetPreviousFilters(RegionProxy catchOrFilterRegion)
        {
            var region = catchOrFilterRegion.Region;
            if (region.Kind is not (ControlFlowRegionKind.Catch or ControlFlowRegionKind.Filter))
                throw new ArgumentException("Must be a catch or filter region: {}", nameof(catchOrFilterRegion));
 
            // Should not be called for a catch block that already has a filter.
            if (region.Kind is ControlFlowRegionKind.Catch && region.EnclosingRegion!.Kind is ControlFlowRegionKind.FilterAndHandler)
                throw new ArgumentException("Must not be a catch block with filter: {}", nameof(catchOrFilterRegion));
 
            var tryRegion = GetCorrespondingTry(catchOrFilterRegion);
            // The enclosing region is part of a TryAndCatch region, which has
            // a Try and multiple Catch or FilterAndHandler regions.
            foreach (var nested in tryRegion.Region.EnclosingRegion!.NestedRegions)
            {
                ControlFlowRegion? catchOrFilter = null;
                switch (nested.Kind)
                {
                    case ControlFlowRegionKind.Catch:
                        catchOrFilter = nested;
                        break;
                    case ControlFlowRegionKind.FilterAndHandler:
                        // Get Filter region from the FilterAndHandler
                        foreach (var filter in nested.NestedRegions)
                        {
                            if (filter.Kind == ControlFlowRegionKind.Filter)
                            {
                                catchOrFilter = filter;
                                break;
                            }
                        }
                        // In case there is no filter region, just skip this one.
                        if (catchOrFilter == null)
                            continue;
                        break;
                    default:
                        continue;
                }
 
                // When we reach this one, we are done searching.
                if (catchOrFilter.Equals(region))
                    yield break;
 
                // If the previous region is a filter region, yield it.
                if (catchOrFilter.Kind == ControlFlowRegionKind.Filter)
                    yield return new(catchOrFilter);
            }
            throw new InvalidOperationException();
        }
 
        public bool HasFilter(RegionProxy catchRegion)
        {
            if (catchRegion.Region.Kind is not ControlFlowRegionKind.Catch)
                throw new ArgumentException("Must be a catch region: {}", nameof(catchRegion));
 
            return catchRegion.Region.EnclosingRegion!.Kind == ControlFlowRegionKind.FilterAndHandler;
        }
 
        public BlockProxy FirstBlock(RegionProxy region) =>
            new BlockProxy(ControlFlowGraph.Blocks[region.Region.FirstBlockOrdinal]);
 
        public BlockProxy LastBlock(RegionProxy region) =>
            new BlockProxy(ControlFlowGraph.Blocks[region.Region.LastBlockOrdinal]);
    }
}