|
// 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.
#nullable disable
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Linq;
using Microsoft.CodeAnalysis.Collections;
using Microsoft.CodeAnalysis.PooledObjects;
using Roslyn.Utilities;
namespace Microsoft.CodeAnalysis.CSharp.Symbols
{
internal static class ConstantEvaluationHelpers
{
[DebuggerDisplay("{GetDebuggerDisplay(), nq}")]
internal readonly struct FieldInfo
{
public readonly SourceFieldSymbolWithSyntaxReference Field;
public readonly bool StartsCycle;
public FieldInfo(SourceFieldSymbolWithSyntaxReference field, bool startsCycle)
{
this.Field = field;
this.StartsCycle = startsCycle;
}
private string GetDebuggerDisplay()
{
var value = this.Field.ToString();
if (this.StartsCycle)
{
value += " [cycle]";
}
return value;
}
}
/// <summary>
/// Generate a list containing the given field and all dependencies
/// of that field that require evaluation. The list is ordered by
/// dependencies, with fields with no dependencies first. Cycles are
/// broken at the first field lexically in the cycle. If multiple threads
/// call this method with the same field, the order of the fields
/// returned should be the same, although some fields may be missing
/// from the lists in some threads as other threads evaluate fields.
/// </summary>
internal static void OrderAllDependencies(
this SourceFieldSymbolWithSyntaxReference field,
ArrayBuilder<FieldInfo> order,
bool earlyDecodingWellKnownAttributes)
{
Debug.Assert(order.Count == 0);
var graph = PooledDictionary<SourceFieldSymbolWithSyntaxReference, Node<SourceFieldSymbolWithSyntaxReference>>.GetInstance();
CreateGraph(graph, field, earlyDecodingWellKnownAttributes);
Debug.Assert(graph.Count >= 1);
CheckGraph(graph);
#if DEBUG
var fields = ArrayBuilder<SourceFieldSymbolWithSyntaxReference>.GetInstance();
fields.AddRange(graph.Keys);
#endif
OrderGraph(graph, order);
#if DEBUG
// Verify all entries in the graph are in the ordered list.
var map = new HashSet<SourceFieldSymbolWithSyntaxReference>(order.Select(o => o.Field).Distinct());
Debug.Assert(fields.All(f => map.Contains(f)));
fields.Free();
#endif
graph.Free();
}
private struct Node<T> where T : class
{
/// <summary>
/// The set of fields on which the field depends.
/// </summary>
public ImmutableHashSet<T> Dependencies;
/// <summary>
/// The set of fields that depend on the field.
/// </summary>
public ImmutableHashSet<T> DependedOnBy;
}
/// <summary>
/// Build a dependency graph (a map from
/// field to dependencies).
/// </summary>
private static void CreateGraph(
Dictionary<SourceFieldSymbolWithSyntaxReference, Node<SourceFieldSymbolWithSyntaxReference>> graph,
SourceFieldSymbolWithSyntaxReference field,
bool earlyDecodingWellKnownAttributes)
{
var pending = ArrayBuilder<SourceFieldSymbolWithSyntaxReference>.GetInstance();
pending.Push(field);
while (pending.Count > 0)
{
field = pending.Pop();
Node<SourceFieldSymbolWithSyntaxReference> node;
if (graph.TryGetValue(field, out node))
{
if (node.Dependencies != null)
{
// Already visited node.
continue;
}
}
else
{
node = new Node<SourceFieldSymbolWithSyntaxReference>();
node.DependedOnBy = ImmutableHashSet<SourceFieldSymbolWithSyntaxReference>.Empty;
}
var dependencies = field.GetConstantValueDependencies(earlyDecodingWellKnownAttributes);
// GetConstantValueDependencies will return an empty set if
// the constant value has already been calculated. That avoids
// calculating the full graph repeatedly. For instance with
// "enum E { M0 = 0, M1 = M0 + 1, ..., Mn = Mn-1 + 1 }", we'll calculate
// the graph M0, ..., Mi for the first field we evaluate, Mi. But for
// the next field, Mj, we should only calculate the graph Mi, ..., Mj.
node.Dependencies = dependencies;
graph[field] = node;
foreach (var dependency in dependencies)
{
pending.Push(dependency);
if (!graph.TryGetValue(dependency, out node))
{
node = new Node<SourceFieldSymbolWithSyntaxReference>();
node.DependedOnBy = ImmutableHashSet<SourceFieldSymbolWithSyntaxReference>.Empty;
}
node.DependedOnBy = node.DependedOnBy.Add(field);
graph[dependency] = node;
}
}
pending.Free();
}
private static void OrderGraph(
Dictionary<SourceFieldSymbolWithSyntaxReference, Node<SourceFieldSymbolWithSyntaxReference>> graph,
ArrayBuilder<FieldInfo> order)
{
Debug.Assert(graph.Count > 0);
PooledHashSet<SourceFieldSymbolWithSyntaxReference> lastUpdated = null;
ArrayBuilder<SourceFieldSymbolWithSyntaxReference> fieldsInvolvedInCycles = null;
while (graph.Count > 0)
{
// Get the set of fields in the graph that have no dependencies.
var search = ((IEnumerable<SourceFieldSymbolWithSyntaxReference>)lastUpdated) ?? graph.Keys;
var set = ArrayBuilder<SourceFieldSymbolWithSyntaxReference>.GetInstance();
foreach (var field in search)
{
Node<SourceFieldSymbolWithSyntaxReference> node;
if (graph.TryGetValue(field, out node))
{
if (node.Dependencies.Count == 0)
{
set.Add(field);
}
}
}
lastUpdated?.Free();
lastUpdated = null;
if (set.Count > 0)
{
var updated = PooledHashSet<SourceFieldSymbolWithSyntaxReference>.GetInstance();
// Remove fields with no dependencies from the graph.
foreach (var field in set)
{
var node = graph[field];
// Remove the field from the Dependencies
// of each field that depends on it.
foreach (var dependedOnBy in node.DependedOnBy)
{
var n = graph[dependedOnBy];
n.Dependencies = n.Dependencies.Remove(field);
graph[dependedOnBy] = n;
updated.Add(dependedOnBy);
}
graph.Remove(field);
}
CheckGraph(graph);
// Add the set to the ordered list.
foreach (var item in set)
{
order.Add(new FieldInfo(item, startsCycle: false));
}
lastUpdated = updated;
}
else
{
// All fields have dependencies which means all fields are involved
// in cycles. Break the first cycle found. (Note some fields may have
// dependencies but are not strictly part of any cycle. For instance,
// B and C in: "enum E { A = A | B, B = C, C = D, D = D }").
var field = GetStartOfFirstCycle(graph, ref fieldsInvolvedInCycles);
// Break the dependencies.
var node = graph[field];
// Remove the field from the DependedOnBy
// of each field it has as a dependency.
foreach (var dependency in node.Dependencies)
{
var n = graph[dependency];
n.DependedOnBy = n.DependedOnBy.Remove(field);
graph[dependency] = n;
}
node = graph[field];
var updated = PooledHashSet<SourceFieldSymbolWithSyntaxReference>.GetInstance();
// Remove the field from the Dependencies
// of each field that depends on it.
foreach (var dependedOnBy in node.DependedOnBy)
{
var n = graph[dependedOnBy];
n.Dependencies = n.Dependencies.Remove(field);
graph[dependedOnBy] = n;
updated.Add(dependedOnBy);
}
graph.Remove(field);
CheckGraph(graph);
// Add the start of the cycle to the ordered list.
order.Add(new FieldInfo(field, startsCycle: true));
lastUpdated = updated;
}
set.Free();
}
lastUpdated?.Free();
fieldsInvolvedInCycles?.Free();
}
private static SourceFieldSymbolWithSyntaxReference GetStartOfFirstCycle(
Dictionary<SourceFieldSymbolWithSyntaxReference, Node<SourceFieldSymbolWithSyntaxReference>> graph,
ref ArrayBuilder<SourceFieldSymbolWithSyntaxReference> fieldsInvolvedInCycles)
{
Debug.Assert(graph.Count > 0);
if (fieldsInvolvedInCycles is null)
{
fieldsInvolvedInCycles = ArrayBuilder<SourceFieldSymbolWithSyntaxReference>.GetInstance(graph.Count);
// We sort fields that belong to the same compilation by location to process cycles in deterministic order.
// Relative order between compilations is not important, cycles do not cross compilation boundaries.
fieldsInvolvedInCycles.AddRange(graph.Keys.GroupBy(static f => f.DeclaringCompilation).
SelectMany(static g => g.OrderByDescending((f1, f2) => g.Key.CompareSourceLocations(f1.ErrorLocation, f2.ErrorLocation))));
}
while (true)
{
SourceFieldSymbolWithSyntaxReference field = fieldsInvolvedInCycles.Pop();
if (graph.ContainsKey(field) && IsPartOfCycle(graph, field))
{
return field;
}
}
}
private static bool IsPartOfCycle(
Dictionary<SourceFieldSymbolWithSyntaxReference, Node<SourceFieldSymbolWithSyntaxReference>> graph,
SourceFieldSymbolWithSyntaxReference field)
{
var set = PooledHashSet<SourceFieldSymbolWithSyntaxReference>.GetInstance();
var stack = ArrayBuilder<SourceFieldSymbolWithSyntaxReference>.GetInstance();
SourceFieldSymbolWithSyntaxReference stopAt = field;
bool result = false;
stack.Push(field);
while (stack.Count > 0)
{
field = stack.Pop();
var node = graph[field];
if (node.Dependencies.Contains(stopAt))
{
result = true;
break;
}
foreach (var dependency in node.Dependencies)
{
if (set.Add(dependency))
{
stack.Push(dependency);
}
}
}
stack.Free();
set.Free();
return result;
}
[Conditional("DEBUG")]
private static void CheckGraph(Dictionary<SourceFieldSymbolWithSyntaxReference, Node<SourceFieldSymbolWithSyntaxReference>> graph)
{
// Avoid O(n^2) behavior by checking
// a maximum number of entries.
int i = 10;
foreach (var pair in graph)
{
var field = pair.Key;
var node = pair.Value;
Debug.Assert(node.Dependencies != null);
Debug.Assert(node.DependedOnBy != null);
foreach (var dependency in node.Dependencies)
{
Node<SourceFieldSymbolWithSyntaxReference> n;
var ok = graph.TryGetValue(dependency, out n);
Debug.Assert(ok);
Debug.Assert(n.DependedOnBy.Contains(field));
}
foreach (var dependedOnBy in node.DependedOnBy)
{
Node<SourceFieldSymbolWithSyntaxReference> n;
var ok = graph.TryGetValue(dependedOnBy, out n);
Debug.Assert(ok);
Debug.Assert(n.Dependencies.Contains(field));
}
i--;
if (i == 0)
{
break;
}
}
Debug.Assert(graph.Values.Sum(n => n.DependedOnBy.Count) == graph.Values.Sum(n => n.Dependencies.Count));
}
}
}
|