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

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