|
// 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);
}
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]);
}
}
|