stephencleary / comparers Goto Github PK

EqualityCompare<int?>.Default().GetHashCode(null).Dump();                          // == 0
EqualityCompare<int?>.EquateBy(k => k, allowNulls:true).GetHashCode(null).Dump();  // == 585969562
EqualityCompare<int?>.EquateBy(k => k, allowNulls:false).GetHashCode(null).Dump(); // == 585969562

//All true.
EqualityCompare<int?>.Default().Equals(null, null).Dump();
EqualityCompare<int?>.EquateBy(k => k, allowNulls:true).Equals(null, null).Dump();
EqualityCompare<int?>.EquateBy(k => k, allowNulls:false).Equals(null, null).Dump();

Is this expected behaviour?

• I would have thought .Default() would be equivalent to one of the other two for .GetHashCode(null).
• I also expected .Equals(null, null) would either throw or return false for allowNulls:false.

Just came across these as I was writing some tests for this unordered sequence comparer. My null treatment was off, so I've been investigating how the existing classes handle it.

We should remove the comparer-builder overloads for BinarySearch (for both T[] and List<T>).

Reasoning:

• BinarySearch only works on sorted collections. The standard use case is to use the same comparer for Sort and then BinarySearch, in which case using the comparer-builder overloads would require code duplication.
• The BinarySearch comparer may be a "widening" comparer for that used in the Sort. This is the only realistic use case for BinarySearch comparer-builder overloads. E.g., list.Sort(c => c.OrderBy(x => x.LastName).ThenBy(x => x.FirstName)) followed by list.BinarySearch(c => c.OrderBy(x => x.LastName)). In this case, the stricter Sort comparer is compatible with the wider BinarySearch comparer. IMO, this is insufficiently common to warrant the overloads.
• Sort is useful on its own, so it should keep the comparer-builder overloads.

It is sometimes desirable to wrap other comparers with a Nito.Comparers comparer that just forwards to the underlying comparer. This brings the benefit of not throwing when GetHashCode(null) is called (see #13). We could make this wrapping easier.

Counterpoint: this wrapping makes it easy to treat an IComparer<T> as though it were an IEqualityComparer<T> (since the wrapper is an IFullComparer<T>). Currently, this would cause a runtime error if GetHashCode is used without being implemented (see https://github.com/StephenCleary/Comparers/wiki/Pitfalls). By making the wrapping easier, this pitfall is more exposed. However, it probably will remain a rare occurrence.

Possible syntax options:

• Simple extension method: StringComparer.Ordinal.NormalizeNullHandling(). Not too wild about the naming.
• Make the delegate in SelectBy/EquateBy optional (default to the identity function): ComparerBuilder.For<string>().CompareBy(StringComparer.Ordinal). Makes it clear that this is a Nito comparer, but seems pretty verbose.

Have a NaturalStringComparer (and case-insensitive variant). Possibly also WithStandardNullHandling wrappers for StringComparer instances.

xxHash (https://cyan4973.github.io/xxHash/) has been adopted by the .NET runtime and looks more distributed than FNV.

Change the semantics of wrapping bare IComparer<T> types from "if you use GetHashCode without implementing it, we'll throw NotImplementedException at the time GetHashCode is called" to "you must implement GetHashCode; otherwise an exception is thrown at construction time".

Note that this is a breaking change.

I just tried using this library on a little stub of a class:

    internal sealed class PortCategory(string name) : ComparableBase<IPortCategory>, IPortCategory
    {
        static PortCategory()
        {
            DefaultComparer = ComparerBuilder.For<IPortCategory>()
                .OrderBy(x => x.Name);
        }

        public string Name { get; } = name ?? throw new ArgumentNullException(nameof(name));
    }

That fails compilation, with:

The type 'Rwv37.FreeBSD.VestertopianPortsBuilder.Core.Interfaces.IPortCategory' cannot be used as type parameter 'T' in the generic type or method 'ComparableBase<T>'. There is no implicit reference conversion from 'Rwv37.FreeBSD.VestertopianPortsBuilder.Core.Interfaces.IPortCategory' to 'Nito.Comparers.ComparableBase<Rwv37.FreeBSD.VestertopianPortsBuilder.Core.Interfaces.IPortCategory>'.

I then noticed that the sample in the docs implements ComparableBase of the class itself, and after looking at the source code it, it looks to me that this is required (?).

If I change ComparableBase<IPortCategory> to ComparableBase<PortCategory>, the compiler error goes away, but it's replaced by others, because PortCategory no longer implements IPortCategory (due to IPortCategory being both IComparable<IPortCategory> and IEquatable<IPortCategory>).

Of course in the case of this little stub class, it might be reasonable to just get rid of IPortCategory entirely, but that doesn't seem like it's necessarily a good solution in other, presumably more complex, cases.

Is there a way to use this library to do what I was hoping to do here? Thanks in advance.

I've been using this package for a while and it's great, but when I recently added it to a .NET 4.5 app, it pulled in a whole lot of .NET standard dependencies (more than doubled my packages list), even though I don't believe it strictly needs them (could be wrong there).

From this SO post I'm guess it might be possible to create a package that only installs those dependencies if it needs them.

Thoughts?

Currently we allow IEqualityComparer.GetHashCode(null) for value types. Should we?

If changed, this would be a breaking change.

In the example code for EquatableBase declare a DefaultComparer property in the derived type to make sure that the static constructor has run. This will prevent users from getting null when using DerivedType.DefaultComparer (as I have repeatedly).

(from #32)

Currently EquateSequence requires elements to be in corresponding order. This issue is to add some kind of support for a collection equality comparer that ignores ordering of elements. This will require some kind of state, so this will be an expensive comparer to use.

The comparer will need to allow a custom element equality comparer, one that may have special null handling.

High-level algorithm:

• If counts (soft reification to ICollection / ICollection<T> / IReadOnlyCollection<T>) aren't equal, then false. If both counts are 0, then true.
• Determine cardinality of equivalence classes, and test that both collections have the same cardinality for equivalent items.

Not sure how to handle GetHashCode, since there's no order defined for the items nor their equivalence classes. Any hash code combination would have to use a commutative combiner, which is not currently in the library.

Is there a way to make the string equality comparer case insensitive using the StringComparison.OrdinalIgnoreCase, I would prefer to no have to do .ToUpper() or .ToLower() if possible.

    class Test:Nito.Comparers.EquatableBaseWithOperators<Test>
    {
        static Test()
        {
            DefaultComparer = Nito.Comparers.EqualityComparerBuilder.For<Test>().Default();
        }
    }
        [Fact]
        public void Test1()
        {
            Test a = null;
            Assert.True(a == null);
        }

this code failed with

   System.NullReferenceException : Object reference not set to an instance of an object.
   Stack Trace:
        at Nito.Comparers.Util.ComparableImplementations.ImplementOpEquality[T](IEqualityComparer`1 equalityComparer, T left, T right)

Hi Stephen,

Given a type deriving from EquatableBase:

        public class ReferenceType: EquatableBase<ReferenceType>
        {
            static ReferenceType()
            {
                DefaultComparer = EqualityComparerBuilder
                    .For<ReferenceType>()
                    .EquateBy(x => x.Value);
            }
            
            public string Value { get; set; }
        }

I was expecting that calling Equals(new ReferenceType { Value = "" }, "Hi!") would return false. Instead, I got an exception Unable to cast object of type 'System.String' to type 'ReferenceType'. Flipping the argument order does return false, as expected. I can see this is because ComparableImplementations.ImplementEquals<T>(IEqualityComparer<T> equalityComparer, T @this, object obj) immediately casts obj to T.

It looks like this is probably intended, but I just wanted to confirm, as this behaviour was unexpected for me. I understand this is a complicated topic, so I'm probably completely wrong here, but it seems like it would be safer to check whether obj is of type T before casting? Would this have some major downsides?

Just to give some context, I ran into this issue when using Json.Net serializer, which calls Equals with parameters of various types from the object graph being serialized. It took me a while to realize the problem was actually with the equality implementation, not the serializer.

It would be really nice if we could have a method in both the ComparerBuilder and EqualityComparerBuilder classes to allow a member to be compared using delegates for both the equality comparison and the hashcode creation.

Is this currently possible? If not would you accept a PR to implement this?

Thanks,
Sean.

Some developers like to have comparers for their types that treat each of its members as a "key". Some alternative comparison libraries actually have this as the default behavior, e.g., OpenCompare.

TL;DR: Nito.Comparers does not directly support this, but it's possible to write your own code to have this behavior.

Design Problems

The first problem with having this behavior by default is that it is seldom the desired behavior. An all-members comparer defines "equivalent" as "nothing has changed", which is not always what the code wants "equivalent" to mean.

Consider a type Circle that has X, Y, and Radius properties. In this case, we could say "equivalent" means X, Y, and Radius are all equal, and in this case an all-members comparer makes sense; if any of those values are different, it's a different circle. But what about a Person? If a person changes their PhoneNumber, are they the same person? To me it makes more sense to have "key" properties that are explicitly specified as such; e.g., an entity Id.

Furthermore, it is often useful to have different parts of the code compare objects differently. With the Circle example, one part of the code may want to sort by size (Radius) only; another part of the code may want to sort by distance from the origin (a combination of X and Y). Person objects may be sorted by birthday in one part of the code, and grouped by zip code in another, and equated by Id in another. In my experience, it's a better design to have each part of the code explicitly specify its desired comparer.

Implementation Problem: Which Members?

One of the big questions when implementing an all-members comparer is: Which Members? In the general case, this becomes a tangle of custom attributes and/or options for opting in and out at various levels.

Do we compare properties? What about computed properties? What about fields?

If members are complex types, do we descend into them? Collections are relatively straightforward, but what about Parent kinds of properties, where Parent contains a collection that includes the current instance? A thorough all-members comparer should have code to detect and break out of reference loops like this.

A truly generic all-members comparer would end up looking a lot like a serialization library, with all the complexity that comes with that.

Implementation Problem: Order

Member ordering is compiler-dependent. This means that a list of members for a type may have a different order depending on compiler/runtime version. So, if an app orders objects with an all-members comparer and saves that collection in persistent storage, then recompiling (or updating the runtime) may make the next invocation of the app with the same all-members comparer use a different ordering. It's possble to work around this behavior by inventing ordering rules for members used internally by the comparer.

There's a second problem with all-member comparers: if a member only supports equality comparison rather than ordering, then it's not possible to build a full ordering comparer with valid semantics (i.e., taking that member into account only for equality).

For this reason, it generally makes sense to restrict all-member comparers to be equality comparers only.

Conclusion

Due to the complexity of maintaining a generic all-members comparer, and due to the limited usefulness of such a type, Nito.Comparers does not provide an all-members comparer out of the box.

However, any given codebase may choose to make simplifying decisions for its own code, which makes an all-members comparer feasible. The following code defines a simple all-members equality comparer by comparing all properties (ignoring fields) and always "drilling down" into reference types:

Is there a way of automatically implementing the required comparison and equality operators for structs?

Our current EqualityComparerBase implementation of System.Collections.IEqualityComparer.Equals has the possibility of stack overflow if applied to objects of unrelated types that both forward their object.Equals(object) implementations to a Nito.Comparer comparer.

• Unit test to replicate.
• Fix this and GetHashCode the same way EqualityComparer<T>.Default does

Hey there,

I've got an extension function which has been kicking around in my LinqPad extensions for while which is basically your .EquateSequence() function, except that it allows the significance of element order to be specified. It takes duplicate elements in each sequence into account when order is not significant, otherwise it just uses System.Linq.Enumerable.SequenceEqual() for order significant equality.

I'd be happy to give you the code, or submit a pull request or something if you'd like to include it in your library?

Cheers,
Frank.

I just hit an exception that I didn't expect where null values are being passed into an inner comparer, which then chokes. I've got a minimal repro below where I would expect the default null handling to kick in and protect the ordinal string comparer from null values, but they always seem to get passed through, no matter whether I specify true or false for specialNullHandling.

Is this expected behaviour? If so, how do I go about making this tolerant of null keys?

void Main()
{
    Measurement.StructuralComparer.GetHashCode(new Measurement { Key = null });
}

struct Measurement
{
    public string Key { get; set; }
    
    public static readonly IEqualityComparer<Measurement> StructuralComparer =
        EqualityComparerBuilder.For<Measurement>()
            .EquateBy(x => x.Key, StringComparer.Ordinal, specialNullHandling: false);
}

We'd like to reference the Comparers package from a strong-named application, but we can't because the Comparers.dll is currently an unsigned assembly.

Would it be possible to add a strong name?

How about adding special equality comparers for float and double types, which allow you to specify the allowed tolerance for difference?

As far as I know there are none in .NET or this library.

For each comparer/equalitycomparer type in the unit tests, include invariant tests.

Also, see if there's a way to structure them more meaningfully, with one check per test, while also enabling test implementation reuse, and if possible applying groups of tests.

Split from #23

Do we need Utf8StringComparer support?

Using Default throws StackOverflowException exception but using OrderBy(x => x.Weight) works fine.

public class Component : ComparableBase<Component>
{
    static Component()
    {
        DefaultComparer = ComparerBuilder.For<Component>().Default();
    }
    
    public double AccWeight { get; set; }

    public double Weight { get; set; }
}

Split from #23

Light-up usage of CompareTo and Equals for spans of chars to make natural string comparisons allocation-free on .NET Core 2.1+.

Light-up GetHashCode for spans of chars to make it allocation-free on .NET Core 3.0+.