|
// 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;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
// This is needed due to NativeAOT which doesn't enable nullable globally yet
#nullable enable
namespace ILLink.Shared.DataFlow
{
public readonly struct ValueSet<TValue> : IEquatable<ValueSet<TValue>>, IDeepCopyValue<ValueSet<TValue>>
where TValue : notnull
{
const int MaxValuesInSet = 256;
public static readonly ValueSet<TValue> Empty;
private sealed class ValueSetSentinel
{
}
private static readonly ValueSetSentinel UnknownSentinel = new ();
public static readonly ValueSet<TValue> Unknown = new (UnknownSentinel);
// Since we're going to do lot of type checks for this class a lot, it is much more efficient
// if the class is sealed (as then the runtime can do a simple method table pointer comparison)
private sealed class EnumerableValues : HashSet<TValue>
{
public EnumerableValues (IEnumerable<TValue> values) : base (values) { }
public override int GetHashCode ()
{
int hashCode = 0;
foreach (var item in this)
hashCode = HashUtils.Combine (hashCode, item);
return hashCode;
}
public bool Equals (EnumerableValues other)
{
// Unfortunately if some of the values are ArrayValues then they can mutate
// after being added to the set, in which case their "hashing" is broken
// The set will self-heal on every Meet since we recreate the HashSet
// but equality is not guaranteed in the interim state.
// So to workaround this for now, iterate over both sets and check
// that the item can be found in the other set.
foreach (TValue item in this)
if (!other.Contains (item))
return false;
foreach (TValue item in other)
if (!Contains (item))
return false;
return true;
}
public bool Equals (TValue other)
{
// As described above, it's possible to end up with a hashset which has multiple
// values which are equal (due to mutability). So we can't rely on item count.
bool found = false;
foreach (TValue item in this) {
if (!item.Equals (other))
return false;
found = true;
}
return found;
}
}
public struct Enumerator : IEnumerator<TValue>, IDisposable, IEnumerator
{
private readonly object? _value;
private int _state; // 0 before beginning, 1 at item, 2 after end
private readonly IEnumerator<TValue>? _enumerator;
internal Enumerator (object? values)
{
_state = 0;
if (values is EnumerableValues valuesSet) {
_enumerator = valuesSet.GetEnumerator ();
_value = null;
} else {
_enumerator = null;
_value = values;
}
}
public TValue Current => _enumerator is not null
? _enumerator.Current
: (_state == 1 ? (TValue) _value! : default!);
object? IEnumerator.Current => Current;
public void Dispose ()
{
}
public bool MoveNext ()
{
if (_enumerator is not null)
return _enumerator.MoveNext ();
if (_value is null)
return false;
if (_state > 1)
return false;
_state++;
return _state == 1;
}
public void Reset ()
{
if (_enumerator is not null)
_enumerator.Reset ();
else
_state = 0;
}
}
public readonly struct Enumerable : IEnumerable<TValue>
{
private readonly object? _values;
public Enumerable (object? values) => _values = values;
public Enumerator GetEnumerator () => new (_values);
IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator () => GetEnumerator ();
IEnumerator IEnumerable.GetEnumerator () => GetEnumerator ();
}
// This stores the values. By far the most common case will be either no values, or a single value.
// Cases where there are multiple values stored are relatively very rare.
// null - no values (empty set)
// TValue - single value itself
// EnumerableValues typed object - multiple values, stored in the hashset
// ValueSetSentinel.Unknown - unknown value, or "any possible value"
private readonly object? _values;
public ValueSet (TValue value) => _values = value;
public ValueSet (IEnumerable<TValue> values) => _values = new EnumerableValues (values);
private ValueSet (EnumerableValues values) => _values = values;
private ValueSet (ValueSetSentinel sentinel) => _values = sentinel;
public static implicit operator ValueSet<TValue> (TValue value) => new (value);
// Note: returns false for Unknown
public bool HasMultipleValues => _values is EnumerableValues;
public override bool Equals (object? obj) => obj is ValueSet<TValue> other && Equals (other);
public bool Equals (ValueSet<TValue> other)
{
if (_values == null)
return other._values == null;
if (other._values == null)
return false;
if (_values is EnumerableValues enumerableValues) {
if (other._values is EnumerableValues otherValuesSet) {
return enumerableValues.Equals (otherValuesSet);
} else if (other._values is TValue otherValue) {
return enumerableValues.Equals (otherValue);
} else {
Debug.Assert (other._values == UnknownSentinel);
return false;
}
} else if (_values is TValue value) {
if (other._values is EnumerableValues otherEnumerableValues) {
return otherEnumerableValues.Equals (value);
} else if (other._values is TValue otherValue) {
return EqualityComparer<TValue>.Default.Equals (value, otherValue);
} else {
Debug.Assert (other._values == UnknownSentinel);
return false;
}
} else {
Debug.Assert (_values == UnknownSentinel);
return other._values == UnknownSentinel;
}
}
public static bool operator == (ValueSet<TValue> left, ValueSet<TValue> right) => left.Equals (right);
public static bool operator != (ValueSet<TValue> left, ValueSet<TValue> right) => !(left == right);
public override int GetHashCode ()
{
if (_values == null)
return typeof (ValueSet<TValue>).GetHashCode ();
if (_values is EnumerableValues enumerableValues)
return enumerableValues.GetHashCode ();
return _values.GetHashCode ();
}
public Enumerable GetKnownValues () => new Enumerable (_values == UnknownSentinel ? null : _values);
// Note: returns false for Unknown
public bool Contains (TValue value)
{
if (_values is null)
return false;
if (_values is EnumerableValues valuesSet)
return valuesSet.Contains (value);
if (_values is TValue thisValue)
return EqualityComparer<TValue>.Default.Equals (value, thisValue);
Debug.Assert (_values == UnknownSentinel);
return false;
}
internal static ValueSet<TValue> Union (ValueSet<TValue> left, ValueSet<TValue> right)
{
if (left._values == null)
return right.DeepCopy ();
if (right._values == null)
return left.DeepCopy ();
if (left._values == UnknownSentinel || right._values == UnknownSentinel)
return Unknown;
if (left._values is not EnumerableValues && right.Contains ((TValue) left._values))
return right.DeepCopy ();
if (right._values is not EnumerableValues && left.Contains ((TValue) right._values))
return left.DeepCopy ();
var values = new EnumerableValues (left.DeepCopy ().GetKnownValues ());
values.UnionWith (right.DeepCopy ().GetKnownValues ());
// Limit the number of values we track, to prevent hangs in case of patterns that
// create exponentially many possible values.
if (values.Count > MaxValuesInSet)
return Unknown;
return new ValueSet<TValue> (values);
}
internal static ValueSet<TValue> Intersection (ValueSet<TValue> left, ValueSet<TValue> right)
{
if (left._values == null || right._values == null)
return Empty;
if (left._values == UnknownSentinel)
return right.DeepCopy ();
if (right._values == UnknownSentinel)
return left.DeepCopy ();
if (left._values is not EnumerableValues)
return right.Contains ((TValue) left._values) ? left.DeepCopy () : Empty;
if (right._values is not EnumerableValues)
return left.Contains ((TValue) right._values) ? right.DeepCopy () : Empty;
var values = new EnumerableValues (left.DeepCopy ().GetKnownValues ());
values.IntersectWith (right.GetKnownValues ());
return new ValueSet<TValue> (values);
}
public bool IsEmpty () => _values == null;
public bool IsUnknown () => _values == UnknownSentinel;
public override string ToString ()
{
if (IsUnknown ())
return "Unknown";
StringBuilder sb = new ();
sb.Append ('{');
sb.Append (string.Join (",", GetKnownValues ().Select (v => v.ToString ())));
sb.Append ('}');
return sb.ToString ();
}
// Meet should copy the values, but most SingleValues are immutable.
// Clone returns `this` if there are no mutable SingleValues (SingleValues that implement IDeepCopyValue), otherwise creates a new ValueSet with copies of the copiable Values
public ValueSet<TValue> DeepCopy ()
{
if (_values is null)
return this;
if (_values == UnknownSentinel)
return this;
// Optimize for the most common case with only a single value
if (_values is not EnumerableValues) {
if (_values is IDeepCopyValue<TValue> copyValue)
return new ValueSet<TValue> (copyValue.DeepCopy ());
else
return this;
}
return new ValueSet<TValue> (GetKnownValues ().Select (value => value is IDeepCopyValue<TValue> copyValue ? copyValue.DeepCopy () : value));
}
}
}
|