mcs/class/Mono.C5/C5/Hashers.cs

   1 /*
   2  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
   3  Permission is hereby granted, free of charge, to any person obtaining a copy
   4  of this software and associated documentation files (the "Software"), to deal
   5  in the Software without restriction, including without limitation the rights
   6  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7  copies of the Software, and to permit persons to whom the Software is
   8  furnished to do so, subject to the following conditions:
   9
  10  The above copyright notice and this permission notice shall be included in
  11  all copies or substantial portions of the Software.
  12
  13  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  19  SOFTWARE.
  20 */
  21
  22 using C5;
  23 using System;
  24 using System.Reflection;
  25 using System.Reflection.Emit;
  26 using System.Diagnostics;
  27 using SCG = System.Collections.Generic;
  28
  29 namespace C5
  30 {
  31   /// <summary>
  32   /// Utility class for building default generic equalityComparers.
  33   /// </summary>
  34   /// <typeparam name="T"></typeparam>
  35   public static class EqualityComparer<T>
  36   {
  37     readonly static Type isequenced = typeof(ISequenced<>);
  38
  39     readonly static Type icollection = typeof(ICollection<>);
  40
  41     readonly static Type orderedcollectionequalityComparer = typeof(SequencedCollectionEqualityComparer<,>);
  42
  43     readonly static Type unorderedcollectionequalityComparer = typeof(UnsequencedCollectionEqualityComparer<,>);
  44
  45     readonly static Type equalityequalityComparer = typeof(EquatableEqualityComparer<>);
  46
  47     readonly static Type iequalitytype = typeof(IEquatable<T>);
  48
  49     static SCG.IEqualityComparer<T> cachedDefault = null;
  50
  51     //TODO: find the right word for initialized+invocation
  52     /// <summary>
  53     /// A default generic equality comparer for type T. The procedure is as follows:
  54     /// <list>
  55     /// <item>If T is a primitive type (char, sbyte, byte, short, ushort, int, uint, float, double, decimal),
  56     /// the equalityComparer will be a standard equalityComparer for that type</item>
  57     /// <item>If the actual generic argument T implements the generic interface
  58     /// <see cref="T:C5.ISequenced`1"/> for some value W of its generic parameter T,
  59     /// the equalityComparer will be <see cref="T:C5.SequencedCollectionEqualityComparer`2"/></item>
  60     /// <item>If the actual generic argument T implements
  61     /// <see cref="T:C5.ICollection`1"/> for some value W of its generic parameter T,
  62     /// the equalityComparer will be <see cref="T:C5.UnsequencedCollectionEqualityComparer`2"/></item>
  63     /// <item>If T is a type implementing <see cref="T:C5.IEquatable`1"/>, the equalityComparer
  64     /// will be <see cref="T:C5.EquatableEqualityComparer`1"/></item>
  65     /// <item>If T is a type not implementing <see cref="T:C5.IEquatable`1"/>, the equalityComparer
  66     /// will be <see cref="T:C5.NaturalEqualityComparer`1"/> </item>
  67     /// </list>
  68     /// The <see cref="T:C5.IEqualityComparer`1"/> object is constructed when this class is initialised, i.e.
  69     /// its static constructors called. Thus, the property will be the same object
  70     /// for the duration of an invocation of the runtime, but a value serialized in
  71     /// another invocation and deserialized here will not be the same object.
  72     /// </summary>
  73     /// <value></value>
  74     public static SCG.IEqualityComparer<T> Default
  75     {
  76       get
  77       {
  78         if (cachedDefault != null)
  79           return cachedDefault;
  80
  81         Type t = typeof(T);
  82
  83         if (t.IsValueType)
  84         {
  85           if (t.Equals(typeof(char)))
  86             return cachedDefault = (SCG.IEqualityComparer<T>)(CharEqualityComparer.Default);
  87
  88           if (t.Equals(typeof(sbyte)))
  89             return cachedDefault = (SCG.IEqualityComparer<T>)(SByteEqualityComparer.Default);
  90
  91           if (t.Equals(typeof(byte)))
  92             return cachedDefault = (SCG.IEqualityComparer<T>)(ByteEqualityComparer.Default);
  93
  94           if (t.Equals(typeof(short)))
  95             return cachedDefault = (SCG.IEqualityComparer<T>)(ShortEqualityComparer.Default);
  96
  97           if (t.Equals(typeof(ushort)))
  98             return cachedDefault = (SCG.IEqualityComparer<T>)(UShortEqualityComparer.Default);
  99
 100           if (t.Equals(typeof(int)))
 101             return cachedDefault = (SCG.IEqualityComparer<T>)(IntEqualityComparer.Default);
 102
 103           if (t.Equals(typeof(uint)))
 104             return cachedDefault = (SCG.IEqualityComparer<T>)(UIntEqualityComparer.Default);
 105
 106           if (t.Equals(typeof(long)))
 107             return cachedDefault = (SCG.IEqualityComparer<T>)(LongEqualityComparer.Default);
 108
 109           if (t.Equals(typeof(ulong)))
 110             return cachedDefault = (SCG.IEqualityComparer<T>)(ULongEqualityComparer.Default);
 111
 112           if (t.Equals(typeof(float)))
 113             return cachedDefault = (SCG.IEqualityComparer<T>)(FloatEqualityComparer.Default);
 114
 115           if (t.Equals(typeof(double)))
 116             return cachedDefault = (SCG.IEqualityComparer<T>)(DoubleEqualityComparer.Default);
 117
 118           if (t.Equals(typeof(decimal)))
 119             return cachedDefault = (SCG.IEqualityComparer<T>)(DecimalEqualityComparer.Default);
 120         }
 121         Type[] interfaces = t.GetInterfaces();
 122         if (t.IsGenericType && t.GetGenericTypeDefinition().Equals(isequenced))
 123           return createAndCache(orderedcollectionequalityComparer.MakeGenericType(new Type[] { t, t.GetGenericArguments()[0] }));
 124         foreach (Type ty in interfaces)
 125         {
 126           if (ty.IsGenericType && ty.GetGenericTypeDefinition().Equals(isequenced))
 127             return createAndCache(orderedcollectionequalityComparer.MakeGenericType(new Type[] { t, ty.GetGenericArguments()[0] }));
 128         }
 129         if (t.IsGenericType && t.GetGenericTypeDefinition().Equals(icollection))
 130           return createAndCache(unorderedcollectionequalityComparer.MakeGenericType(new Type[] { t, t.GetGenericArguments()[0] }));
 131         foreach (Type ty in interfaces)
 132         {
 133           if (ty.IsGenericType && ty.GetGenericTypeDefinition().Equals(icollection))
 134             return createAndCache(unorderedcollectionequalityComparer.MakeGenericType(new Type[] { t, ty.GetGenericArguments()[0] }));
 135         }
 136         if (iequalitytype.IsAssignableFrom(t))
 137           return createAndCache(equalityequalityComparer.MakeGenericType(new Type[] { t }));
 138         else
 139           return cachedDefault = NaturalEqualityComparer<T>.Default;
 140       }
 141     }
 142     static SCG.IEqualityComparer<T> createAndCache(Type equalityComparertype)
 143     {
 144       return cachedDefault = (SCG.IEqualityComparer<T>)(equalityComparertype.GetProperty("Default", BindingFlags.Static | BindingFlags.Public).GetValue(null, null));
 145     }
 146   }
 147
 148   /// <summary>
 149   /// A default item equalityComparer calling through to
 150   /// the GetHashCode and Equals methods inherited from System.Object.
 151   /// </summary>
 152   [Serializable]
 153   public sealed class NaturalEqualityComparer<T> : SCG.IEqualityComparer<T>
 154   {
 155     static NaturalEqualityComparer<T> cached;
 156     NaturalEqualityComparer() { }
 157     /// <summary>
 158     ///
 159     /// </summary>
 160     /// <value></value>
 161     public static NaturalEqualityComparer<T> Default { get { return cached ?? (cached = new NaturalEqualityComparer<T>()); } }
 162     //TODO: check if null check is reasonable
 163     //Answer: if we have struct C<T> { T t; int i;} and implement GetHashCode as
 164     //the sum of hashcodes, and T may be any type, we cannot make the null check
 165     //inside the definition of C<T> in a reasonable way.
 166     /// <summary>
 167     /// Get the hash code with respect to this item equalityComparer
 168     /// </summary>
 169     /// <param name="item">The item</param>
 170     /// <returns>The hash code</returns>
 171     [Tested]
 172     public int GetHashCode(T item) { return item == null ? 0 : item.GetHashCode(); }
 173
 174     /// <summary>
 175     /// Check if two items are equal with respect to this item equalityComparer
 176     /// </summary>
 177     /// <param name="item1">first item</param>
 178     /// <param name="item2">second item</param>
 179     /// <returns>True if equal</returns>
 180     [Tested]
 181     public bool Equals(T item1, T item2)
 182     {
 183       return item1 == null ? item2 == null : item1.Equals(item2);
 184     }
 185   }
 186
 187   /// <summary>
 188   /// A default equality comparer for a type T that implements System.IEquatable<typeparamref name="T"/>.
 189   ///
 190   /// The equality comparer forwards calls to GetHashCode and Equals to the IEquatable methods
 191   /// on T, so Equals(T) is called, not Equals(object).
 192   /// This will save boxing abd unboxing if T is a value type
 193   /// and in general saves a runtime type check.
 194   /// </summary>
 195   /// <typeparam name="T"></typeparam>
 196   [Serializable]
 197   public class EquatableEqualityComparer<T> : SCG.IEqualityComparer<T> where T : IEquatable<T>
 198   {
 199     static EquatableEqualityComparer<T> cached = new EquatableEqualityComparer<T>();
 200     EquatableEqualityComparer() { }
 201     /// <summary>
 202     ///
 203     /// </summary>
 204     /// <value></value>
 205     public static EquatableEqualityComparer<T> Default {
 206       get { return cached ?? (cached = new EquatableEqualityComparer<T>()); }
 207     }
 208     /// <summary>
 209     ///
 210     /// </summary>
 211     /// <param name="item"></param>
 212     /// <returns></returns>
 213     public int GetHashCode(T item) { return item == null ? 0 : item.GetHashCode(); }
 214
 215     /// <summary>
 216     ///
 217     /// </summary>
 218     /// <param name="item1"></param>
 219     /// <param name="item2"></param>
 220     /// <returns></returns>
 221     public bool Equals(T item1, T item2) { return item1 == null ? item2 == null : item1.Equals(item2); }
 222   }
 223
 224   /// <summary>
 225   /// A equalityComparer for a reference type that uses reference equality for equality and the hash code from object as hash code.
 226   /// </summary>
 227   /// <typeparam name="T">The item type. Must be a reference type.</typeparam>
 228   [Serializable]
 229   public class ReferenceEqualityComparer<T> : SCG.IEqualityComparer<T> where T : class
 230   {
 231     static ReferenceEqualityComparer<T> cached;
 232     ReferenceEqualityComparer() { }
 233     /// <summary>
 234     ///
 235     /// </summary>
 236     /// <value></value>
 237     public static ReferenceEqualityComparer<T> Default {
 238       get { return cached ?? (cached = new ReferenceEqualityComparer<T>()); }
 239     }
 240     /// <summary>
 241     ///
 242     /// </summary>
 243     /// <param name="item"></param>
 244     /// <returns></returns>
 245     public int GetHashCode(T item)
 246     {
 247       return System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(item);
 248     }
 249
 250     /// <summary>
 251     ///
 252     /// </summary>
 253     /// <param name="i1"></param>
 254     /// <param name="i2"></param>
 255     /// <returns></returns>
 256     public bool Equals(T i1, T i2)
 257     {
 258       return object.ReferenceEquals(i1, i2);
 259     }
 260   }
 261
 262   /// <summary>
 263   /// An equalityComparer compatible with a given comparer. All hash codes are 0,
 264   /// meaning that anything based on hash codes will be quite inefficient.
 265   /// <para><b>Note: this will give a new EqualityComparer each time created!</b></para>
 266   /// </summary>
 267   /// <typeparam name="T"></typeparam>
 268   [Serializable]
 269   public class ComparerZeroHashCodeEqualityComparer<T> : SCG.IEqualityComparer<T>
 270   {
 271     SCG.IComparer<T> comparer;
 272     /// <summary>
 273     /// Create a trivial <see cref="T:C5.IEqualityComparer`1"/> compatible with the
 274     /// <see cref="T:C5.IComparer`1"/> <code>comparer</code>
 275     /// </summary>
 276     /// <param name="comparer"></param>
 277     public ComparerZeroHashCodeEqualityComparer(SCG.IComparer<T> comparer)
 278     {
 279       if (comparer == null)
 280         throw new NullReferenceException("Comparer cannot be null");
 281       this.comparer = comparer;
 282     }
 283     /// <summary>
 284     /// A trivial, inefficient hash fuction. Compatible with any equality relation.
 285     /// </summary>
 286     /// <param name="item"></param>
 287     /// <returns>0</returns>
 288     public int GetHashCode(T item) { return 0; }
 289     /// <summary>
 290     /// Equality of two items as defined by the comparer.
 291     /// </summary>
 292     /// <param name="item1"></param>
 293     /// <param name="item2"></param>
 294     /// <returns></returns>
 295     public bool Equals(T item1, T item2) { return comparer.Compare(item1, item2) == 0; }
 296   }
 297
 298   /// <summary>
 299   /// Prototype for a sequenced equalityComparer for something (T) that implements ISequenced[W].
 300   /// This will use ISequenced[W] specific implementations of the equality comparer operations.
 301   /// </summary>
 302   /// <typeparam name="T"></typeparam>
 303   /// <typeparam name="W"></typeparam>
 304   [Serializable]
 305   public class SequencedCollectionEqualityComparer<T, W> : SCG.IEqualityComparer<T>
 306       where T : ISequenced<W>
 307   {
 308     static SequencedCollectionEqualityComparer<T, W> cached;
 309     SequencedCollectionEqualityComparer() { }
 310     /// <summary>
 311     ///
 312     /// </summary>
 313     /// <value></value>
 314     public static SequencedCollectionEqualityComparer<T, W> Default {
 315       get { return cached ?? (cached = new SequencedCollectionEqualityComparer<T, W>()); }
 316     }
 317     /// <summary>
 318     /// Get the hash code with respect to this sequenced equalityComparer
 319     /// </summary>
 320     /// <param name="collection">The collection</param>
 321     /// <returns>The hash code</returns>
 322     [Tested]
 323     public int GetHashCode(T collection) { return collection.GetSequencedHashCode(); }
 324
 325     /// <summary>
 326     /// Check if two items are equal with respect to this sequenced equalityComparer
 327     /// </summary>
 328     /// <param name="collection1">first collection</param>
 329     /// <param name="collection2">second collection</param>
 330     /// <returns>True if equal</returns>
 331     [Tested]
 332     public bool Equals(T collection1, T collection2) { return collection1 == null ? collection2 == null : collection1.SequencedEquals(collection2); }
 333   }
 334
 335   /// <summary>
 336   /// Prototype for an unsequenced equalityComparer for something (T) that implements ICollection[W]
 337   /// This will use ICollection[W] specific implementations of the equalityComparer operations
 338   /// </summary>
 339   /// <typeparam name="T"></typeparam>
 340   /// <typeparam name="W"></typeparam>
 341   [Serializable]
 342   public class UnsequencedCollectionEqualityComparer<T, W> : SCG.IEqualityComparer<T>
 343       where T : ICollection<W>
 344   {
 345     static UnsequencedCollectionEqualityComparer<T, W> cached;
 346     UnsequencedCollectionEqualityComparer() { }
 347     /// <summary>
 348     ///
 349     /// </summary>
 350     /// <value></value>
 351     public static UnsequencedCollectionEqualityComparer<T, W> Default { get { return cached ?? (cached = new UnsequencedCollectionEqualityComparer<T, W>()); } }
 352     /// <summary>
 353     /// Get the hash code with respect to this unsequenced equalityComparer
 354     /// </summary>
 355     /// <param name="collection">The collection</param>
 356     /// <returns>The hash code</returns>
 357     [Tested]
 358     public int GetHashCode(T collection) { return collection.GetUnsequencedHashCode(); }
 359
 360
 361     /// <summary>
 362     /// Check if two collections are equal with respect to this unsequenced equalityComparer
 363     /// </summary>
 364     /// <param name="collection1">first collection</param>
 365     /// <param name="collection2">second collection</param>
 366     /// <returns>True if equal</returns>
 367     [Tested]
 368     public bool Equals(T collection1, T collection2) { return collection1 == null ? collection2 == null : collection1.UnsequencedEquals(collection2); }
 369   }
 370
 371 }
 372
 373
 374 #if EXPERIMENTAL
 375 namespace C5.EqualityComparerBuilder
 376 {
 377
 378   /// <summary>
 379   /// IEqualityComparer factory class: examines at instatiation time if T is an
 380   /// interface implementing "int GetHashCode()" and "bool Equals(T)".
 381   /// If those are not present, MakeEqualityComparer will return a default equalityComparer,
 382   /// else this class will implement IequalityComparer[T] via Invoke() on the
 383   /// reflected method infos.
 384   /// </summary>
 385   public class ByInvoke<T> : SCG.IEqualityComparer<T>
 386   {
 387     internal static readonly System.Reflection.MethodInfo hinfo, einfo;
 388
 389
 390     static ByInvoke()
 391     {
 392       Type t = typeof(T);
 393
 394       if (!t.IsInterface) return;
 395
 396       BindingFlags f = BindingFlags.Public | BindingFlags.Instance;
 397
 398       hinfo = t.GetMethod("GetHashCode", f, null, new Type[0], null);
 399       einfo = t.GetMethod("Equals", f, null, new Type[1] { t }, null);
 400     }
 401
 402
 403     private ByInvoke() { }
 404
 405 /// <summary>
 406 ///
 407 /// </summary>
 408 /// <returns></returns>
 409     public static SCG.IEqualityComparer<T> MakeEqualityComparer()
 410     {
 411       if (hinfo != null && einfo != null)
 412         return new ByInvoke<T>();
 413       else
 414         return NaturalEqualityComparer<T>.Default;
 415     }
 416
 417 /// <summary>
 418 ///
 419 /// </summary>
 420 /// <param name="item"></param>
 421 /// <returns></returns>
 422     public int GetHashCode(T item)
 423     {
 424       return (int)(hinfo.Invoke(item, null));
 425     }
 426
 427 /// <summary>
 428 ///
 429 /// </summary>
 430 /// <param name="i1"></param>
 431 /// <param name="i2"></param>
 432 /// <returns></returns>
 433     public bool Equals(T i1, T i2)
 434     {
 435       return (bool)(einfo.Invoke(i1, new object[1] { i2 }));
 436     }
 437   }
 438
 439
 440
 441   /// <summary>
 442   /// Like ByInvoke, but tries to build a equalityComparer by RTCG to
 443   /// avoid the Invoke() overhead.
 444   /// </summary>
 445   public class ByRTCG
 446   {
 447     private static ModuleBuilder moduleBuilder;
 448
 449     private static AssemblyBuilder assemblyBuilder;
 450
 451     /// <summary>
 452     ///
 453     /// </summary>
 454     /// <param name="hinfo"></param>
 455     /// <param name="einfo"></param>
 456     /// <returns></returns>
 457     public static SCG.IEqualityComparer<T> CreateEqualityComparer<T>(MethodInfo hinfo, MethodInfo einfo)
 458     {
 459       if (moduleBuilder == null)
 460       {
 461         string assmname = "LeFake";
 462         string filename = assmname + ".dll";
 463         AssemblyName assemblyName = new AssemblyName("LeFake");
 464         AppDomain appdomain = AppDomain.CurrentDomain;
 465         AssemblyBuilderAccess acc = AssemblyBuilderAccess.RunAndSave;
 466
 467         assemblyBuilder = appdomain.DefineDynamicAssembly(assemblyName, acc);
 468         moduleBuilder = assemblyBuilder.DefineDynamicModule(assmname, filename);
 469       }
 470
 471       Type t = typeof(T);
 472       Type o_t = typeof(object);
 473       Type h_t = typeof(SCG.IEqualityComparer<T>);
 474       Type i_t = typeof(int);
 475       //TODO: protect uid for thread safety!
 476       string name = "C5.Dynamic.EqualityComparer_" + Guid.NewGuid().ToString();
 477       TypeAttributes tatt = TypeAttributes.Class | TypeAttributes.Public | TypeAttributes.Sealed;
 478       TypeBuilder tb = moduleBuilder.DefineType(name, tatt, o_t, new Type[1] { h_t });
 479       MethodAttributes matt = MethodAttributes.Public | MethodAttributes.Virtual;
 480       MethodBuilder mb = tb.DefineMethod("GetHashCode", matt, i_t, new Type[1] { t });
 481       ILGenerator ilg = mb.GetILGenerator();
 482
 483       ilg.Emit(OpCodes.Ldarg_1);
 484       ilg.Emit(OpCodes.Callvirt, hinfo);
 485       ilg.Emit(OpCodes.Ret);
 486       mb = tb.DefineMethod("Equals", matt, typeof(bool), new Type[2] { t, t });
 487       ilg = mb.GetILGenerator();
 488       ilg.Emit(OpCodes.Ldarg_1);
 489       ilg.Emit(OpCodes.Ldarg_2);
 490       ilg.Emit(OpCodes.Callvirt, einfo);
 491       ilg.Emit(OpCodes.Ret);
 492
 493       Type equalityComparer_t = tb.CreateType();
 494       object equalityComparer = equalityComparer_t.GetConstructor(new Type[0]).Invoke(null);
 495
 496       return (SCG.IEqualityComparer<T>)equalityComparer;
 497     }
 498
 499 /// <summary>
 500 ///
 501 /// </summary>
 502 /// <typeparam name="T"></typeparam>
 503 /// <returns></returns>
 504     public static SCG.IEqualityComparer<T> build<T>()
 505     {
 506       MethodInfo hinfo = ByInvoke<T>.hinfo, einfo = ByInvoke<T>.einfo;
 507
 508       if (hinfo != null && einfo != null)
 509         return CreateEqualityComparer<T>(hinfo, einfo);
 510       else
 511         return EqualityComparer<T>.Default;
 512     }
 513
 514 /// <summary>
 515 ///
 516 /// </summary>
 517     public void dump()
 518     {
 519       assemblyBuilder.Save("LeFake.dll");
 520     }
 521   }
 522 }
 523 #endif