Каков алгоритм, используемый тестом-методом равенства в .NET-структурах?

Ответ 1

Это реализация ValueType.Equals из общей инфраструктуры общего источника (версия 2.0).

public override bool Equals (Object obj) {
    BCLDebug.Perf(false, "ValueType::Equals is not fast.  "+
        this.GetType().FullName+" should override Equals(Object)");
    if (null==obj) {
        return false;
    }
    RuntimeType thisType = (RuntimeType)this.GetType();
    RuntimeType thatType = (RuntimeType)obj.GetType();

    if (thatType!=thisType) {
        return false;
    }

    Object thisObj = (Object)this;
    Object thisResult, thatResult;

    // if there are no GC references in this object we can avoid reflection 
    // and do a fast memcmp
    if (CanCompareBits(this))
        return FastEqualsCheck(thisObj, obj);

    FieldInfo[] thisFields = thisType.GetFields(
        BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic);

    for (int i=0; i<thisFields.Length; i++) {
        thisResult = ((RtFieldInfo)thisFields[i])
            .InternalGetValue(thisObj, false);
        thatResult = ((RtFieldInfo)thisFields[i])
            .InternalGetValue(obj, false);

        if (thisResult == null) {
            if (thatResult != null)
                return false;
        }
        else
        if (!thisResult.Equals(thatResult)) {
            return false;
        }
    }

    return true;
}

Интересно отметить, что это точно такой код, который показан в Reflector. Это меня поразило, потому что я думал, что SSCLI - это просто эталонная реализация, а не финальная библиотека. Опять же, я предполагаю, что существует ограниченное число способов реализации этого относительно простого алгоритма.

Детали, которые я хотел бы понять больше, - это призывы к CanCompareBits и FastEqualsCheck. Они реализованы как собственные методы, но их код также включен в SSCLI. Как видно из приведенных ниже реализаций, CLI рассматривает определение класса объекта (через его таблицу методов), чтобы увидеть, содержит ли он указатели на ссылочные типы и как выделяется память для объекта. Если ссылок нет, и объект смежный, то память напрямую сравнивается с помощью функции C memcmp.

// Return true if the valuetype does not contain pointer and is tightly packed
FCIMPL1(FC_BOOL_RET, ValueTypeHelper::CanCompareBits, Object* obj)
{
    WRAPPER_CONTRACT;
    STATIC_CONTRACT_SO_TOLERANT;

    _ASSERTE(obj != NULL);
    MethodTable* mt = obj->GetMethodTable();
    FC_RETURN_BOOL(!mt->ContainsPointers() && !mt->IsNotTightlyPacked());
}
FCIMPLEND

FCIMPL2(FC_BOOL_RET, ValueTypeHelper::FastEqualsCheck, Object* obj1,
    Object* obj2)
{
    WRAPPER_CONTRACT;
    STATIC_CONTRACT_SO_TOLERANT;

    _ASSERTE(obj1 != NULL);
    _ASSERTE(obj2 != NULL);
    _ASSERTE(!obj1->GetMethodTable()->ContainsPointers());
    _ASSERTE(obj1->GetSize() == obj2->GetSize());

    TypeHandle pTh = obj1->GetTypeHandle();

    FC_RETURN_BOOL(memcmp(obj1->GetData(),obj2->GetData(),pTh.GetSize()) == 0);
}
FCIMPLEND

Если бы я был не совсем ленив, я мог бы изучить реализацию ContainsPointers и IsNotTightlyPacked. Тем не менее, я окончательно выяснил, что я хотел знать (и я ленив), чтобы работа на другой день.

• Общая инфраструктура общего языка 2.0

Ответ 2

Нет стандартного равенства по умолчанию, но для базовых типов значений (float, byte, decimal и т.д.) спецификация языка требует поразрядного сравнения. Оптимизатор JIT оптимизирует это для правильных инструкций по сборке, но технически это поведение равно функции C memcmp.

Некоторые примеры BCL

• DateTime просто сравнивает свое внутреннее поле члена InternalTicks, которое длинное;
• PointF сравнивает X и Y как в (left.X == right.X) && (left.Y == right.Y);
• decimal не сравнивает внутренние поля, а возвращается к InternalImpl, что означает, что он во внутренней части unviewable.NET(но вы можете проверить SSCLI);
• Rectangle явно сравнивает каждое поле (x, y, ширина, высота);
• ModuleHandle использует переопределение Equals, и есть еще много этого,
• SqlString, а другие структуры SqlXXX используют реализацию IComparable.Compare;
• Guid является самым странным в этом списке: он имеет свой собственный длинный короткий список if-операторов, сравнивающий каждое внутреннее поле (_a to _k, все int) для неравенства, возвращающее false, когда неравны. Если все не являются неравными, оно возвращает true.

Заключение

Этот список довольно произволен, но я надеюсь, что он освещает проблему: нет способа по умолчанию, и даже BCL использует другой подход для каждой структуры, в зависимости от его назначения. Суть в том, что более поздние добавления чаще называют их переопределение Equals или IComparable.Compare, но это просто переносит проблему на другой метод.

Другие способы:

Вы можете использовать отражение, чтобы пройти через каждое поле, но это очень медленно. Вы также можете создать один метод расширения или статический помощник, который побито сравнивает внутренние поля. Используйте StructLayout.Sequential, возьмите адрес памяти и размер и сравните блоки памяти. Для этого требуется небезопасный код, но он быстрый, легкий (и немного грязный).

Обновить: перефразировать, добавить некоторые фактические примеры, добавить новое заключение

Обновление: реализация сравнения по методу

Выше, по-видимому, было небольшое недоразумение в вопросе, но я оставляю его там, поскольку я думаю, что он имеет определенную ценность для будущих посетителей независимо. Вот еще один ответ:

Здесь реализуется элементное сравнение для объектов и типов значений, которые могут проходить через все свойства, поля и перечислимое содержимое, рекурсивно, независимо от глубины. Он не протестирован, вероятно, содержит некоторые опечатки, но он компилируется в порядке. См. Комментарии в коде для более подробной информации:

public static bool MemberCompare(object left, object right)
{
    if (Object.ReferenceEquals(left, right))
        return true;

    if (left == null || right == null)
        return false;

    Type type = left.GetType();
    if (type != right.GetType())
        return false;

    if(left as ValueType != null)
    {
        // do a field comparison, or use the override if Equals is implemented:
        return left.Equals(right);
    }

    // check for override:
    if (type != typeof(object)
        && type == type.GetMethod("Equals").DeclaringType)
    {
        // the Equals method is overridden, use it:
        return left.Equals(right);
    }

    // all Arrays, Lists, IEnumerable<> etc implement IEnumerable
    if (left as IEnumerable != null)
    {
        IEnumerator rightEnumerator = (right as IEnumerable).GetEnumerator();
        rightEnumerator.Reset();
        foreach (object leftItem in left as IEnumerable)
        {
            // unequal amount of items
            if (!rightEnumerator.MoveNext())
                return false;
            else
            {
                if (!MemberCompare(leftItem, rightEnumerator.Current))
                    return false;
            }                    
        }
    }
    else
    {
        // compare each property
        foreach (PropertyInfo info in type.GetProperties(
            BindingFlags.Public | 
            BindingFlags.NonPublic | 
            BindingFlags.Instance | 
            BindingFlags.GetProperty))
        {
            // TODO: need to special-case indexable properties
            if (!MemberCompare(info.GetValue(left, null), info.GetValue(right, null)))
                return false;
        }

        // compare each field
        foreach (FieldInfo info in type.GetFields(
            BindingFlags.GetField |
            BindingFlags.NonPublic |
            BindingFlags.Public |
            BindingFlags.Instance))
        {
            if (!MemberCompare(info.GetValue(left), info.GetValue(right)))
                return false;
        }
    }
    return true;
}

Обновление: исправлено несколько ошибок, добавлено использование переопределенного Equals тогда и только тогда, когда доступно Обновление: object.Equals не должно рассматриваться как переопределение, исправлено.

Ответ 3

Это сложнее, чем кажется на первый взгляд. Короткий ответ:

public bool MyEquals(object obj1, object obj2)
{
  if(obj1==null || obj2==null)
    return obj1==obj2;
  else if(...)
    ...  // Your custom code here
  else if(obj1.GetType().IsValueType)
    return
      obj1.GetType()==obj2.GetType() &&
      !struct1.GetType().GetFields(ALL_FIELDS).Any(field =>
       !MyEquals(field.GetValue(struct1), field.GetValue(struct2)));
  else
    return object.Equals(obj1, obj2);
}

const BindingFlags ALL_FIELDS =
  BindingFlags.Instance |
  BindingFlags.Public |
  BindingFlags.NonPublic;

Однако это гораздо больше, чем это. Вот подробности:

Если вы объявляете структуру и не переопределяете .Equals(), NET Framework будет использовать одну из двух разных стратегий в зависимости от того, имеет ли ваша структура только "простые" типы значений ( "простой" определен ниже):

Если структура содержит только "простые" типы значений, выполняется поразрядное сравнение, в основном:

strncmp((byte*)&struct1, (byte*)&struct2, Marshal.Sizeof(struct1));

Если структура содержит ссылки или не "простые" типы значений, каждое объявленное поле сравнивается как с объектом. Equals():

struct1.GetType()==struct2.GetType() &&
!struct1.GetType().GetFields(ALL_FIELDS).Any(field =>
  !object.Equals(field.GetValue(struct1), field.GetValue(struct2)));

Что квалифицируется как "простой" тип? Из моих тестов это любой базовый скалярный тип (int, long, decimal, double и т.д.), Плюс любая структура, которая не имеет переопределения .Equals и содержит только "простые" типы (рекурсивно).

У этого есть некоторые интересные разветвления. Например, в этом коде:

struct DoubleStruct
{
  public double value;
}

public void TestDouble()
{
  var test1 = new DoubleStruct { value = 1 / double.PositiveInfinity };
  var test2 = new DoubleStruct { value = 1 / double.NegativeInfinity };

  bool valueEqual = test1.value.Equals(test2.value);
  bool structEqual = test1.Equals(test2);

  MessageBox.Show("valueEqual=" + valueEqual + ", structEqual=" + structEqual);
}

вы ожидали бы, что valueEqual всегда будет идентичным structEqual, независимо от того, что было присвоено test1.value и test2.value. Это не так!

Причиной этого удивительного результата является то, что double.Equals() учитывает некоторые из тонкостей кодирования IEEE 754, такие как множественные представления NaN и нулевые представления, но побитовое сравнение этого не делает. Поскольку "double" считается простым типом, structEqual возвращает false, когда бит отличается, даже когда valueEqual возвращает true.

В приведенном выше примере использованы альтернативные нулевые представления, но это также может иметь место с несколькими значениями NaN:

...
  var test1 = new DoubleStruct { value = CreateNaN(1) };
  var test2 = new DoubleStruct { value = CreateNaN(2) };
...
public unsafe double CreateNaN(byte lowByte)
{
  double result = double.NaN;
  ((byte*)&result)[0] = lowByte;
  return result;
}

В большинстве обычных ситуаций это не будет иметь никакого значения, но это то, о чем нужно знать.

Ответ 4

Вот моя собственная попытка этой проблемы. Это работает, но я не уверен, что я рассмотрел все базы.

public class MemberwiseEqualityComparer : IEqualityComparer
{
    public bool Equals(object x, object y)
    {
        // ----------------------------------------------------------------
        // 1. If exactly one is null, return false.
        // 2. If they are the same reference, then they must be equal by
        //    definition.
        // 3. If the objects are both IEnumerable, return the result of
        //    comparing each item.
        // 4. If the objects are equatable, return the result of comparing
        //    them.
        // 5. If the objects are different types, return false.
        // 6. Iterate over the public properties and compare them. If there
        //    is a pair that are not equal, return false.
        // 7. Return true.
        // ----------------------------------------------------------------

        //
        // 1. If exactly one is null, return false.
        //
        if (null == x ^ null == y) return false;

        //
        // 2. If they are the same reference, then they must be equal by
        //    definition.
        //
        if (object.ReferenceEquals(x, y)) return true;

        //
        // 3. If the objects are both IEnumerable, return the result of
        //    comparing each item.
        // For collections, we want to compare the contents rather than
        // the properties of the collection itself so we check if the
        // classes are IEnumerable instances before we check to see that
        // they are the same type.
        //
        if (x is IEnumerable && y is IEnumerable && false == x is string)
        {
            return contentsAreEqual((IEnumerable)x, (IEnumerable)y);
        }

        //
        // 4. If the objects are equatable, return the result of comparing
        //    them.
        // We are assuming that the type of X implements IEquatable<> of itself
        // (see below) which is true for the numeric types and string.
        // e.g.: public class TypeOfX : IEquatable<TypeOfX> { ... }
        //
        var xType = x.GetType();
        var yType = y.GetType();
        var equatableType = typeof(IEquatable<>).MakeGenericType(xType);
        if (equatableType.IsAssignableFrom(xType)
            && xType.IsAssignableFrom(yType))
        {
            return equatablesAreEqual(equatableType, x, y);
        }

        //
        // 5. If the objects are different types, return false.
        //
        if (xType != yType) return false;

        //
        // 6. Iterate over the public properties and compare them. If there
        //    is a pair that are not equal, return false.
        //
        if (false == propertiesAndFieldsAreEqual(x, y)) return false;

        //
        // 7. Return true.
        //
        return true;
    }

    public int GetHashCode(object obj)
    {
        return null != obj ? obj.GetHashCode() : 0;
    }

    private bool contentsAreEqual(IEnumerable enumX, IEnumerable enumY)
    {
        var enumOfObjX = enumX.OfType<object>();
        var enumOfObjY = enumY.OfType<object>();

        if (enumOfObjX.Count() != enumOfObjY.Count()) return false;

        var contentsAreEqual = enumOfObjX
            .Zip(enumOfObjY) // Custom Zip extension which returns
                             // Pair<TFirst,TSecond>. Similar to .NET 4 Zip
                             // extension.
            .All(pair => Equals(pair.First, pair.Second))
            ;

        return contentsAreEqual;
    }

    private bool equatablesAreEqual(Type equatableType, object x, object y)
    {
        var equalsMethod = equatableType.GetMethod("Equals");
        var equal = (bool)equalsMethod.Invoke(x, new[] { y });
        return equal;
    }

    private bool propertiesAndFieldsAreEqual(object x, object y)
    {
        const BindingFlags bindingFlags
            = BindingFlags.Public | BindingFlags.Instance;

        var propertyValues = from pi in x.GetType()
                                         .GetProperties(bindingFlags)
                                         .AsQueryable()
                             where pi.CanRead
                             select new
                             {
                                 Name   = pi.Name,
                                 XValue = pi.GetValue(x, null),
                                 YValue = pi.GetValue(y, null),
                             };

        var fieldValues = from fi in x.GetType()
                                      .GetFields(bindingFlags)
                                      .AsQueryable()
                          select new
                          {
                              Name   = fi.Name,
                              XValue = fi.GetValue(x),
                              YValue = fi.GetValue(y),
                          };

        var propertiesAreEqual = propertyValues.Union(fieldValues)
            .All(v => Equals(v.XValue, v.YValue))
            ;

        return propertiesAreEqual;
    }
}

Ответ 5

public static bool CompareMembers<T>(this T source, T other, params Expression<Func<object>>[] propertiesToSkip)
{
    PropertyInfo[] sourceProperties = source.GetType().GetProperties();

    List<string> propertiesToSkipList = (from x in propertiesToSkip
                                         let a = x.Body as MemberExpression
                                         let b = x.Body as UnaryExpression
                                         select a == null ? ((MemberExpression)b.Operand).Member.Name : a.Member.Name).ToList();

    List<PropertyInfo> lstProperties = (
        from propertyToSkip in propertiesToSkipList
        from property in sourceProperties
        where property.Name != propertyToSkip
        select property).ToList();

    return (!(lstProperties.Any(property => !property.GetValue(source, null).Equals(property.GetValue(other, null)))));
}

Как использовать:

bool test = myObj1.MemberwiseEqual(myObj2,
        () => myObj.Id,
        () => myObj.Name);