src/compiler/dmd/object_.d

   1 /**
   2  * Part of the D programming language runtime library.
   3  * Forms the symbols available to all D programs. Includes
   4  * Object, which is the root of the class object hierarchy.
   5  *
   6  * This module is implicitly imported.
   7  * Macros:
   8  *      WIKI = Object
   9  */
  10
  11 /*
  12  *  Copyright (C) 2004-2007 by Digital Mars, www.digitalmars.com
  13  *  Written by Walter Bright
  14  *
  15  *  This software is provided 'as-is', without any express or implied
  16  *  warranty. In no event will the authors be held liable for any damages
  17  *  arising from the use of this software.
  18  *
  19  *  Permission is granted to anyone to use this software for any purpose,
  20  *  including commercial applications, and to alter it and redistribute it
  21  *  freely, in both source and binary form, subject to the following
  22  *  restrictions:
  23  *
  24  *  o  The origin of this software must not be misrepresented; you must not
  25  *     claim that you wrote the original software. If you use this software
  26  *     in a product, an acknowledgment in the product documentation would be
  27  *     appreciated but is not required.
  28  *  o  Altered source versions must be plainly marked as such, and must not
  29  *     be misrepresented as being the original software.
  30  *  o  This notice may not be removed or altered from any source
  31  *     distribution.
  32  */
  33
  34 /*
  35  *  Modified by Sean Kelly for use with the D Runtime Project
  36  */
  37
  38 module object;
  39
  40 private
  41 {
  42     import stdc.string;
  43     import stdc.stdlib;
  44     import util.string;
  45     debug(PRINTF) import stdc.stdio;
  46
  47     extern (C) void onOutOfMemoryError();
  48     extern (C) Object _d_newclass(ClassInfo ci);
  49 }
  50
  51 // NOTE: For some reason, this declaration method doesn't work
  52 //       in this particular file (and this file only).  It must
  53 //       be a DMD thing.
  54 //alias typeof(int.sizeof)                    size_t;
  55 //alias typeof(cast(void*)0 - cast(void*)0)   ptrdiff_t;
  56
  57 version( X86_64 )
  58 {
  59     alias ulong size_t;
  60     alias long  ptrdiff_t;
  61 }
  62 else
  63 {
  64     alias uint  size_t;
  65     alias int   ptrdiff_t;
  66 }
  67
  68 alias size_t hash_t;
  69 alias int equals_t;
  70
  71 alias invariant(char)[]  string;
  72 alias invariant(wchar)[] wstring;
  73 alias invariant(dchar)[] dstring;
  74
  75 /**
  76  * All D class objects inherit from Object.
  77  */
  78 class Object
  79 {
  80     /**
  81      * Convert Object to a human readable string.
  82      */
  83     string toString()
  84     {
  85         return this.classinfo.name;
  86     }
  87
  88     /**
  89      * Compute hash function for Object.
  90      */
  91     hash_t toHash()
  92     {
  93         // BUG: this prevents a compacting GC from working, needs to be fixed
  94         return cast(hash_t)cast(void*)this;
  95     }
  96
  97     /**
  98      * Compare with another Object obj.
  99      * Returns:
 100      *  $(TABLE
 101      *  $(TR $(TD this &lt; obj) $(TD &lt; 0))
 102      *  $(TR $(TD this == obj) $(TD 0))
 103      *  $(TR $(TD this &gt; obj) $(TD &gt; 0))
 104      *  )
 105      */
 106     int opCmp(Object o)
 107     {
 108         // BUG: this prevents a compacting GC from working, needs to be fixed
 109         //return cast(int)cast(void*)this - cast(int)cast(void*)o;
 110
 111         throw new Exception("need opCmp for class " ~ this.classinfo.name);
 112         //return this !is o;
 113     }
 114
 115     /**
 116      * Returns !=0 if this object does have the same contents as obj.
 117      */
 118     equals_t opEquals(Object o)
 119     {
 120         return this is o;
 121     }
 122
 123     interface Monitor
 124     {
 125         void lock();
 126         void unlock();
 127     }
 128 }
 129
 130 /**
 131  * Information about an interface.
 132  * When an object is accessed via an interface, an Interface* appears as the
 133  * first entry in its vtbl.
 134  */
 135 struct Interface
 136 {
 137     ClassInfo   classinfo;  /// .classinfo for this interface (not for containing class)
 138     void*[]     vtbl;
 139     ptrdiff_t   offset;     /// offset to Interface 'this' from Object 'this'
 140 }
 141
 142 /**
 143  * Runtime type information about a class. Can be retrieved for any class type
 144  * or instance by using the .classinfo property.
 145  * A pointer to this appears as the first entry in the class's vtbl[].
 146  */
 147 class ClassInfo : Object
 148 {
 149     byte[]      init;           /** class static initializer
 150                                  * (init.length gives size in bytes of class)
 151                                  */
 152     string      name;           /// class name
 153     void*[]     vtbl;           /// virtual function pointer table
 154     Interface[] interfaces;     /// interfaces this class implements
 155     ClassInfo   base;           /// base class
 156     void*       destructor;
 157     void function(Object) classInvariant;
 158     uint        flags;
 159     //  1:                      // is IUnknown or is derived from IUnknown
 160     //  2:                      // has no possible pointers into GC memory
 161     //  4:                      // has offTi[] member
 162     //  8:                      // has constructors
 163     // 16:                      // has xgetMembers member
 164     void*       deallocator;
 165     OffsetTypeInfo[] offTi;
 166     void function(Object) defaultConstructor;   // default Constructor
 167     const(MemberInfo[]) function(in char[]) xgetMembers;
 168
 169     /**
 170      * Search all modules for ClassInfo corresponding to classname.
 171      * Returns: null if not found
 172      */
 173     static ClassInfo find(in char[] classname)
 174     {
 175         foreach (m; ModuleInfo)
 176         {
 177             //writefln("module %s, %d", m.name, m.localClasses.length);
 178             foreach (c; m.localClasses)
 179             {
 180                 //writefln("\tclass %s", c.name);
 181                 if (c.name == classname)
 182                     return c;
 183             }
 184         }
 185         return null;
 186     }
 187
 188     /**
 189      * Create instance of Object represented by 'this'.
 190      */
 191     Object create()
 192     {
 193         if (flags & 8 && !defaultConstructor)
 194             return null;
 195         Object o = _d_newclass(this);
 196         if (flags & 8 && defaultConstructor)
 197         {
 198             defaultConstructor(o);
 199         }
 200         return o;
 201     }
 202     /**
 203      * Search for all members with the name 'name'.
 204      * If name[] is null, return all members.
 205      */
 206     const(MemberInfo[]) getMembers(in char[] name)
 207     {
 208         if (flags & 16 && xgetMembers)
 209             return xgetMembers(name);
 210         return null;
 211     }
 212 }
 213
 214 /**
 215  * Array of pairs giving the offset and type information for each
 216  * member in an aggregate.
 217  */
 218 struct OffsetTypeInfo
 219 {
 220     size_t   offset;    /// Offset of member from start of object
 221     TypeInfo ti;        /// TypeInfo for this member
 222 }
 223
 224 /**
 225  * Runtime type information about a type.
 226  * Can be retrieved for any type using a
 227  * <a href="../expression.html#typeidexpression">TypeidExpression</a>.
 228  */
 229 class TypeInfo
 230 {
 231     override hash_t toHash()
 232     {   hash_t hash;
 233
 234         foreach (char c; this.toString())
 235             hash = hash * 9 + c;
 236         return hash;
 237     }
 238
 239     override int opCmp(Object o)
 240     {
 241         if (this is o)
 242             return 0;
 243         TypeInfo ti = cast(TypeInfo)o;
 244         if (ti is null)
 245             return 1;
 246         return dstrcmp(this.toString(), ti.toString());
 247     }
 248
 249     override equals_t opEquals(Object o)
 250     {
 251         /* TypeInfo instances are singletons, but duplicates can exist
 252          * across DLL's. Therefore, comparing for a name match is
 253          * sufficient.
 254          */
 255         if (this is o)
 256             return true;
 257         TypeInfo ti = cast(TypeInfo)o;
 258         return ti && this.toString() == ti.toString();
 259     }
 260
 261     /// Returns a hash of the instance of a type.
 262     hash_t getHash(in void* p) { return cast(hash_t)p; }
 263
 264     /// Compares two instances for equality.
 265     equals_t equals(in void* p1, in void* p2) { return p1 == p2; }
 266
 267     /// Compares two instances for &lt;, ==, or &gt;.
 268     int compare(in void* p1, in void* p2) { return 0; }
 269
 270     /// Returns size of the type.
 271     size_t tsize() { return 0; }
 272
 273     /// Swaps two instances of the type.
 274     void swap(void* p1, void* p2)
 275     {
 276         size_t n = tsize();
 277         for (size_t i = 0; i < n; i++)
 278         {
 279             byte t = (cast(byte *)p1)[i];
 280             (cast(byte*)p1)[i] = (cast(byte*)p2)[i];
 281             (cast(byte*)p2)[i] = t;
 282         }
 283     }
 284
 285     /// Get TypeInfo for 'next' type, as defined by what kind of type this is,
 286     /// null if none.
 287     TypeInfo next() { return null; }
 288
 289     /// Return default initializer, null if default initialize to 0
 290     void[] init() { return null; }
 291
 292     /// Get flags for type: 1 means GC should scan for pointers
 293     uint flags() { return 0; }
 294
 295     /// Get type information on the contents of the type; null if not available
 296     OffsetTypeInfo[] offTi() { return null; }
 297     /// Run the destructor on the object and all its sub-objects
 298     void destroy(void* p) {}
 299     /// Run the postblit on the object and all its sub-objects
 300     void postblit(void* p) {}
 301 }
 302
 303 class TypeInfo_Typedef : TypeInfo
 304 {
 305     override string toString() { return name; }
 306
 307     override equals_t opEquals(Object o)
 308     {
 309         TypeInfo_Typedef c;
 310         return this is o ||
 311                ((c = cast(TypeInfo_Typedef)o) !is null &&
 312                 this.name == c.name &&
 313                 this.base == c.base);
 314     }
 315
 316     override hash_t getHash(in void* p) { return base.getHash(p); }
 317     override equals_t equals(in void* p1, in void* p2) { return base.equals(p1, p2); }
 318     override int compare(in void* p1, in void* p2) { return base.compare(p1, p2); }
 319     override size_t tsize() { return base.tsize(); }
 320     override void swap(void* p1, void* p2) { return base.swap(p1, p2); }
 321
 322     override TypeInfo next() { return base.next(); }
 323     override uint flags() { return base.flags(); }
 324     override void[] init() { return m_init.length ? m_init : base.init(); }
 325
 326     TypeInfo base;
 327     string   name;
 328     void[]   m_init;
 329 }
 330
 331 class TypeInfo_Enum : TypeInfo_Typedef
 332 {
 333
 334 }
 335
 336 class TypeInfo_Pointer : TypeInfo
 337 {
 338     override string toString() { return m_next.toString() ~ "*"; }
 339
 340     override equals_t opEquals(Object o)
 341     {
 342         TypeInfo_Pointer c;
 343         return this is o ||
 344                 ((c = cast(TypeInfo_Pointer)o) !is null &&
 345                  this.m_next == c.m_next);
 346     }
 347
 348     override hash_t getHash(in void* p)
 349     {
 350         return cast(hash_t)*cast(void**)p;
 351     }
 352
 353     override equals_t equals(in void* p1, in void* p2)
 354     {
 355         return *cast(void**)p1 == *cast(void**)p2;
 356     }
 357
 358     override int compare(in void* p1, in void* p2)
 359     {
 360         if (*cast(void**)p1 < *cast(void**)p2)
 361             return -1;
 362         else if (*cast(void**)p1 > *cast(void**)p2)
 363             return 1;
 364         else
 365             return 0;
 366     }
 367
 368     override size_t tsize()
 369     {
 370         return (void*).sizeof;
 371     }
 372
 373     override void swap(void* p1, void* p2)
 374     {
 375         void* tmp = *cast(void**)p1;
 376         *cast(void**)p1 = *cast(void**)p2;
 377         *cast(void**)p2 = tmp;
 378     }
 379
 380     override TypeInfo next() { return m_next; }
 381     override uint flags() { return 1; }
 382
 383     TypeInfo m_next;
 384 }
 385
 386 class TypeInfo_Array : TypeInfo
 387 {
 388     override string toString() { return value.toString() ~ "[]"; }
 389
 390     override equals_t opEquals(Object o)
 391     {
 392         TypeInfo_Array c;
 393         return this is o ||
 394                ((c = cast(TypeInfo_Array)o) !is null &&
 395                 this.value == c.value);
 396     }
 397
 398     override hash_t getHash(in void* p)
 399     {
 400         size_t sz = value.tsize();
 401         hash_t hash = 0;
 402         void[] a = *cast(void[]*)p;
 403         for (size_t i = 0; i < a.length; i++)
 404             hash += value.getHash(a.ptr + i * sz);
 405         return hash;
 406     }
 407
 408     override equals_t equals(in void* p1, in void* p2)
 409     {
 410         void[] a1 = *cast(void[]*)p1;
 411         void[] a2 = *cast(void[]*)p2;
 412         if (a1.length != a2.length)
 413             return false;
 414         size_t sz = value.tsize();
 415         for (size_t i = 0; i < a1.length; i++)
 416         {
 417             if (!value.equals(a1.ptr + i * sz, a2.ptr + i * sz))
 418                 return false;
 419         }
 420         return true;
 421     }
 422
 423     override int compare(in void* p1, in void* p2)
 424     {
 425         void[] a1 = *cast(void[]*)p1;
 426         void[] a2 = *cast(void[]*)p2;
 427         size_t sz = value.tsize();
 428         size_t len = a1.length;
 429
 430         if (a2.length < len)
 431             len = a2.length;
 432         for (size_t u = 0; u < len; u++)
 433         {
 434             int result = value.compare(a1.ptr + u * sz, a2.ptr + u * sz);
 435             if (result)
 436                 return result;
 437         }
 438         return cast(int)a1.length - cast(int)a2.length;
 439     }
 440
 441     override size_t tsize()
 442     {
 443         return (void[]).sizeof;
 444     }
 445
 446     override void swap(void* p1, void* p2)
 447     {
 448         void[] tmp = *cast(void[]*)p1;
 449         *cast(void[]*)p1 = *cast(void[]*)p2;
 450         *cast(void[]*)p2 = tmp;
 451     }
 452
 453     TypeInfo value;
 454
 455     override TypeInfo next()
 456     {
 457         return value;
 458     }
 459
 460     override uint flags() { return 1; }
 461 }
 462
 463 class TypeInfo_StaticArray : TypeInfo
 464 {
 465     override string toString()
 466     {
 467         char[10] tmp = void;
 468         return cast(string)(value.toString() ~ "[" ~ tmp.intToString(len) ~ "]");
 469     }
 470
 471     override equals_t opEquals(Object o)
 472     {
 473         TypeInfo_StaticArray c;
 474         return this is o ||
 475                ((c = cast(TypeInfo_StaticArray)o) !is null &&
 476                 this.len == c.len &&
 477                 this.value == c.value);
 478     }
 479
 480     override hash_t getHash(in void* p)
 481     {
 482         size_t sz = value.tsize();
 483         hash_t hash = 0;
 484         for (size_t i = 0; i < len; i++)
 485             hash += value.getHash(p + i * sz);
 486         return hash;
 487     }
 488
 489     override equals_t equals(in void* p1, in void* p2)
 490     {
 491         size_t sz = value.tsize();
 492
 493         for (size_t u = 0; u < len; u++)
 494         {
 495             if (!value.equals(p1 + u * sz, p2 + u * sz))
 496                 return false;
 497         }
 498         return true;
 499     }
 500
 501     override int compare(in void* p1, in void* p2)
 502     {
 503         size_t sz = value.tsize();
 504
 505         for (size_t u = 0; u < len; u++)
 506         {
 507             int result = value.compare(p1 + u * sz, p2 + u * sz);
 508             if (result)
 509                 return result;
 510         }
 511         return 0;
 512     }
 513
 514     override size_t tsize()
 515     {
 516         return len * value.tsize();
 517     }
 518
 519     override void swap(void* p1, void* p2)
 520     {
 521         void* tmp;
 522         size_t sz = value.tsize();
 523         ubyte[16] buffer;
 524         void* pbuffer;
 525
 526         if (sz < buffer.sizeof)
 527             tmp = buffer.ptr;
 528         else
 529             tmp = pbuffer = (new void[sz]).ptr;
 530
 531         for (size_t u = 0; u < len; u += sz)
 532         {   size_t o = u * sz;
 533             memcpy(tmp, p1 + o, sz);
 534             memcpy(p1 + o, p2 + o, sz);
 535             memcpy(p2 + o, tmp, sz);
 536         }
 537         if (pbuffer)
 538             delete pbuffer;
 539     }
 540
 541     override void[] init() { return value.init(); }
 542     override TypeInfo next() { return value; }
 543     override uint flags() { return value.flags(); }
 544
 545     override void destroy(void* p)
 546     {
 547         auto sz = value.tsize();
 548         p += sz * len;
 549         foreach (i; 0 .. len)
 550         {
 551             p -= sz;
 552             value.destroy(p);
 553         }
 554     }
 555
 556     override void postblit(void* p)
 557     {
 558         auto sz = value.tsize();
 559         foreach (i; 0 .. len)
 560         {
 561             value.postblit(p);
 562             p += sz;
 563         }
 564     }
 565
 566     TypeInfo value;
 567     size_t   len;
 568 }
 569
 570 class TypeInfo_AssociativeArray : TypeInfo
 571 {
 572     override string toString()
 573     {
 574         return cast(string)(next.toString() ~ "[" ~ key.toString() ~ "]");
 575     }
 576
 577     override equals_t opEquals(Object o)
 578     {
 579         TypeInfo_AssociativeArray c;
 580         return this is o ||
 581                 ((c = cast(TypeInfo_AssociativeArray)o) !is null &&
 582                  this.key == c.key &&
 583                  this.value == c.value);
 584     }
 585
 586     // BUG: need to add the rest of the functions
 587
 588     override size_t tsize()
 589     {
 590         return (char[int]).sizeof;
 591     }
 592
 593     override TypeInfo next() { return value; }
 594     override uint flags() { return 1; }
 595
 596     TypeInfo value;
 597     TypeInfo key;
 598 }
 599
 600 class TypeInfo_Function : TypeInfo
 601 {
 602     override string toString()
 603     {
 604         return cast(string)(next.toString() ~ "()");
 605     }
 606
 607     override equals_t opEquals(Object o)
 608     {
 609         TypeInfo_Function c;
 610         return this is o ||
 611                 ((c = cast(TypeInfo_Function)o) !is null &&
 612                  this.next == c.next);
 613     }
 614
 615     // BUG: need to add the rest of the functions
 616
 617     override size_t tsize()
 618     {
 619         return 0;       // no size for functions
 620     }
 621
 622     TypeInfo next;
 623 }
 624
 625 class TypeInfo_Delegate : TypeInfo
 626 {
 627     override string toString()
 628     {
 629         return cast(string)(next.toString() ~ " delegate()");
 630     }
 631
 632     override equals_t opEquals(Object o)
 633     {
 634         TypeInfo_Delegate c;
 635         return this is o ||
 636                 ((c = cast(TypeInfo_Delegate)o) !is null &&
 637                  this.next == c.next);
 638     }
 639
 640     // BUG: need to add the rest of the functions
 641
 642     override size_t tsize()
 643     {
 644         alias int delegate() dg;
 645         return dg.sizeof;
 646     }
 647
 648     override uint flags() { return 1; }
 649
 650     TypeInfo next;
 651 }
 652
 653 class TypeInfo_Class : TypeInfo
 654 {
 655     override string toString() { return info.name; }
 656
 657     override equals_t opEquals(Object o)
 658     {
 659         TypeInfo_Class c;
 660         return this is o ||
 661                 ((c = cast(TypeInfo_Class)o) !is null &&
 662                  this.info.name == c.classinfo.name);
 663     }
 664
 665     override hash_t getHash(in void* p)
 666     {
 667         Object o = *cast(Object*)p;
 668         return o ? o.toHash() : 0;
 669     }
 670
 671     override equals_t equals(in void* p1, in void* p2)
 672     {
 673         Object o1 = *cast(Object*)p1;
 674         Object o2 = *cast(Object*)p2;
 675
 676         return (o1 is o2) || (o1 && o1.opEquals(o2));
 677     }
 678
 679     override int compare(in void* p1, in void* p2)
 680     {
 681         Object o1 = *cast(Object*)p1;
 682         Object o2 = *cast(Object*)p2;
 683         int c = 0;
 684
 685         // Regard null references as always being "less than"
 686         if (o1 !is o2)
 687         {
 688             if (o1)
 689             {
 690                 if (!o2)
 691                     c = 1;
 692                 else
 693                     c = o1.opCmp(o2);
 694             }
 695             else
 696                 c = -1;
 697         }
 698         return c;
 699     }
 700
 701     override size_t tsize()
 702     {
 703         return Object.sizeof;
 704     }
 705
 706     override uint flags() { return 1; }
 707
 708     override OffsetTypeInfo[] offTi()
 709     {
 710         return (info.flags & 4) ? info.offTi : null;
 711     }
 712
 713     ClassInfo info;
 714 }
 715
 716 class TypeInfo_Interface : TypeInfo
 717 {
 718     override string toString() { return info.name; }
 719
 720     override equals_t opEquals(Object o)
 721     {
 722         TypeInfo_Interface c;
 723         return this is o ||
 724                 ((c = cast(TypeInfo_Interface)o) !is null &&
 725                  this.info.name == c.classinfo.name);
 726     }
 727
 728     override hash_t getHash(in void* p)
 729     {
 730         Interface* pi = **cast(Interface ***)*cast(void**)p;
 731         Object o = cast(Object)(*cast(void**)p - pi.offset);
 732         assert(o);
 733         return o.toHash();
 734     }
 735
 736     override equals_t equals(in void* p1, in void* p2)
 737     {
 738         Interface* pi = **cast(Interface ***)*cast(void**)p1;
 739         Object o1 = cast(Object)(*cast(void**)p1 - pi.offset);
 740         pi = **cast(Interface ***)*cast(void**)p2;
 741         Object o2 = cast(Object)(*cast(void**)p2 - pi.offset);
 742
 743         return o1 == o2 || (o1 && o1.opCmp(o2) == 0);
 744     }
 745
 746     override int compare(in void* p1, in void* p2)
 747     {
 748         Interface* pi = **cast(Interface ***)*cast(void**)p1;
 749         Object o1 = cast(Object)(*cast(void**)p1 - pi.offset);
 750         pi = **cast(Interface ***)*cast(void**)p2;
 751         Object o2 = cast(Object)(*cast(void**)p2 - pi.offset);
 752         int c = 0;
 753
 754         // Regard null references as always being "less than"
 755         if (o1 != o2)
 756         {
 757             if (o1)
 758             {
 759                 if (!o2)
 760                     c = 1;
 761                 else
 762                     c = o1.opCmp(o2);
 763             }
 764             else
 765                 c = -1;
 766         }
 767         return c;
 768     }
 769
 770     override size_t tsize()
 771     {
 772         return Object.sizeof;
 773     }
 774
 775     override uint flags() { return 1; }
 776
 777     ClassInfo info;
 778 }
 779
 780 class TypeInfo_Struct : TypeInfo
 781 {
 782     override string toString() { return name; }
 783
 784     override equals_t opEquals(Object o)
 785     {
 786         TypeInfo_Struct s;
 787         return this is o ||
 788                 ((s = cast(TypeInfo_Struct)o) !is null &&
 789                  this.name == s.name &&
 790                  this.init.length == s.init.length);
 791     }
 792
 793     override hash_t getHash(in void* p)
 794     {
 795         assert(p);
 796         if (xtoHash)
 797         {
 798             debug(PRINTF) printf("getHash() using xtoHash\n");
 799             return (*xtoHash)(p);
 800         }
 801         else
 802         {
 803             hash_t h;
 804             debug(PRINTF) printf("getHash() using default hash\n");
 805             // A sorry hash algorithm.
 806             // Should use the one for strings.
 807             // BUG: relies on the GC not moving objects
 808             auto q = cast(const(ubyte)*)p;
 809             for (size_t i = 0; i < init.length; i++)
 810             {
 811                 h = h * 9 + *q;
 812                 q++;
 813             }
 814             return h;
 815         }
 816     }
 817
 818     override equals_t equals(in void* p1, in void* p2)
 819     {
 820         if (p1 == p2)
 821             return true;
 822         else if (!p1 || !p2)
 823             return false;
 824         else if (xopEquals)
 825             return (*xopEquals)(p1, p2);
 826         else
 827             // BUG: relies on the GC not moving objects
 828             return memcmp(p1, p2, init.length) == 0;
 829     }
 830
 831     override int compare(in void* p1, in void* p2)
 832     {
 833         // Regard null references as always being "less than"
 834         if (p1 != p2)
 835         {
 836             if (p1)
 837             {
 838                 if (!p2)
 839                     return true;
 840                 else if (xopCmp)
 841                     return (*xopCmp)(p2, p1);
 842                 else
 843                     // BUG: relies on the GC not moving objects
 844                     return memcmp(p1, p2, init.length);
 845             }
 846             else
 847                 return -1;
 848         }
 849         return 0;
 850     }
 851
 852     override size_t tsize()
 853     {
 854         return init.length;
 855     }
 856
 857     override void[] init() { return m_init; }
 858
 859     override uint flags() { return m_flags; }
 860
 861     override void destroy(void* p)
 862     {
 863         if (xdtor)
 864             (*xdtor)(p);
 865     }
 866
 867     override void postblit(void* p)
 868     {
 869         if (xpostblit)
 870             (*xpostblit)(p);
 871     }
 872
 873     string name;
 874     void[] m_init;      // initializer; init.ptr == null if 0 initialize
 875
 876     hash_t   function(in void*)           xtoHash;
 877     equals_t function(in void*, in void*) xopEquals;
 878     int      function(in void*, in void*) xopCmp;
 879     char[]   function(in void*)           xtoString;
 880
 881     uint m_flags;
 882
 883     const(MemberInfo[]) function(in char[]) xgetMembers;
 884     void function(void*)                    xdtor;
 885     void function(void*)                    xpostblit;
 886 }
 887
 888 class TypeInfo_Tuple : TypeInfo
 889 {
 890     TypeInfo[] elements;
 891
 892     override string toString()
 893     {
 894         string s = "(";
 895         foreach (i, element; elements)
 896         {
 897             if (i)
 898                 s ~= ',';
 899             s ~= element.toString();
 900         }
 901         s ~= ")";
 902         return s;
 903     }
 904
 905     override equals_t opEquals(Object o)
 906     {
 907         if (this is o)
 908             return true;
 909
 910         auto t = cast(TypeInfo_Tuple)o;
 911         if (t && elements.length == t.elements.length)
 912         {
 913             for (size_t i = 0; i < elements.length; i++)
 914             {
 915                 if (elements[i] != t.elements[i])
 916                     return false;
 917             }
 918             return true;
 919         }
 920         return false;
 921     }
 922
 923     override hash_t getHash(in void* p)
 924     {
 925         assert(0);
 926     }
 927
 928     override equals_t equals(in void* p1, in void* p2)
 929     {
 930         assert(0);
 931     }
 932
 933     override int compare(in void* p1, in void* p2)
 934     {
 935         assert(0);
 936     }
 937
 938     override size_t tsize()
 939     {
 940         assert(0);
 941     }
 942
 943     override void swap(void* p1, void* p2)
 944     {
 945         assert(0);
 946     }
 947
 948     override void destroy(void* p)
 949     {
 950         assert(0);
 951     }
 952
 953     override void postblit(void* p)
 954     {
 955         assert(0);
 956     }
 957 }
 958
 959 class TypeInfo_Const : TypeInfo
 960 {
 961     override string toString()
 962     {
 963         return cast(string) ("const(" ~ base.toString() ~ ")");
 964     }
 965
 966     override equals_t opEquals(Object o) { return base.opEquals(o); }
 967     override hash_t getHash(in void *p) { return base.getHash(p); }
 968     override equals_t equals(in void *p1, in void *p2) { return base.equals(p1, p2); }
 969     override int compare(in void *p1, in void *p2) { return base.compare(p1, p2); }
 970     override size_t tsize() { return base.tsize(); }
 971     override void swap(void *p1, void *p2) { return base.swap(p1, p2); }
 972
 973     override TypeInfo next() { return base.next(); }
 974     override uint flags() { return base.flags(); }
 975     override void[] init() { return base.init(); }
 976
 977     TypeInfo base;
 978 }
 979
 980 class TypeInfo_Invariant : TypeInfo_Const
 981 {
 982     override string toString()
 983     {
 984         return cast(string) ("invariant(" ~ base.toString() ~ ")");
 985     }
 986 }
 987
 988 abstract class MemberInfo
 989 {
 990     string name();
 991 }
 992
 993 class MemberInfo_field : MemberInfo
 994 {
 995     this(string name, TypeInfo ti, size_t offset)
 996     {
 997         m_name = name;
 998         m_typeinfo = ti;
 999         m_offset = offset;
1000     }
1001
1002     override string name() { return m_name; }
1003     TypeInfo typeInfo() { return m_typeinfo; }
1004     size_t offset() { return m_offset; }
1005
1006     string   m_name;
1007     TypeInfo m_typeinfo;
1008     size_t   m_offset;
1009 }
1010
1011 class MemberInfo_function : MemberInfo
1012 {
1013     this(string name, TypeInfo ti, void* fp, uint flags)
1014     {
1015         m_name = name;
1016         m_typeinfo = ti;
1017         m_fp = fp;
1018         m_flags = flags;
1019     }
1020
1021     override string name() { return m_name; }
1022     TypeInfo typeInfo() { return m_typeinfo; }
1023     void* fp() { return m_fp; }
1024     uint flags() { return m_flags; }
1025
1026     string   m_name;
1027     TypeInfo m_typeinfo;
1028     void*    m_fp;
1029     uint     m_flags;
1030 }
1031
1032
1033 ///////////////////////////////////////////////////////////////////////////////
1034 // Exception
1035 ///////////////////////////////////////////////////////////////////////////////
1036
1037
1038 class Exception : Object
1039 {
1040     interface TraceInfo
1041     {
1042         int opApply( int delegate(inout char[]) );
1043     }
1044
1045     string      msg;
1046     string      file;
1047     size_t      line;
1048     TraceInfo   info;
1049     Exception   next;
1050
1051     this( string msg, Exception next = null )
1052     {
1053         this.msg = msg;
1054         this.next = next;
1055         this.info = traceContext();
1056     }
1057
1058     this( string msg, string file, size_t line, Exception next = null )
1059     {
1060         this(msg, next);
1061         this.file = file;
1062         this.line = line;
1063         this.info = traceContext();
1064     }
1065
1066     override string toString()
1067     {
1068         return msg;
1069     }
1070 }
1071
1072
1073 alias Exception.TraceInfo function( void* ptr = null ) TraceHandler;
1074 private TraceHandler traceHandler = null;
1075
1076
1077 /**
1078  * Overrides the default trace hander with a user-supplied version.
1079  *
1080  * Params:
1081  *  h = The new trace handler.  Set to null to use the default handler.
1082  */
1083 extern (C) void  rt_setTraceHandler( TraceHandler h )
1084 {
1085     traceHandler = h;
1086 }
1087
1088
1089 /**
1090  * This function will be called when an Exception is constructed.  The
1091  * user-supplied trace handler will be called if one has been supplied,
1092  * otherwise no trace will be generated.
1093  *
1094  * Params:
1095  *  ptr = A pointer to the location from which to generate the trace, or null
1096  *        if the trace should be generated from within the trace handler
1097  *        itself.
1098  *
1099  * Returns:
1100  *  An object describing the current calling context or null if no handler is
1101  *  supplied.
1102  */
1103 Exception.TraceInfo traceContext( void* ptr = null )
1104 {
1105     if( traceHandler is null )
1106         return null;
1107     return traceHandler( ptr );
1108 }
1109
1110
1111 ///////////////////////////////////////////////////////////////////////////////
1112 // ModuleInfo
1113 ///////////////////////////////////////////////////////////////////////////////
1114
1115
1116 enum
1117 {
1118     MIctorstart  = 1,   // we've started constructing it
1119     MIctordone   = 2,   // finished construction
1120     MIstandalone = 4,   // module ctor does not depend on other module
1121                         // ctors being done first
1122     MIhasictor   = 8,   // has ictor member
1123 }
1124
1125
1126 class ModuleInfo
1127 {
1128     string          name;
1129     ModuleInfo[]    importedModules;
1130     ClassInfo[]     localClasses;
1131     uint            flags;
1132
1133     void function() ctor;       // module static constructor (order dependent)
1134     void function() dtor;       // module static destructor
1135     void function() unitTest;   // module unit tests
1136
1137     void* xgetMembers;          // module getMembers() function
1138
1139     void function() ictor;      // module static constructor (order independent)
1140
1141     static int opApply( int delegate(inout ModuleInfo) dg )
1142     {
1143         int ret = 0;
1144
1145         foreach( m; _moduleinfo_array )
1146         {
1147             ret = dg( m );
1148             if( ret )
1149                 break;
1150         }
1151         return ret;
1152     }
1153 }
1154
1155
1156 // Windows: this gets initialized by minit.asm
1157 // linux: this gets initialized in _moduleCtor()
1158 extern (C) ModuleInfo[] _moduleinfo_array;
1159
1160
1161 version (linux)
1162 {
1163     // This linked list is created by a compiler generated function inserted
1164     // into the .ctor list by the compiler.
1165     struct ModuleReference
1166     {
1167         ModuleReference* next;
1168         ModuleInfo       mod;
1169     }
1170
1171     extern (C) ModuleReference* _Dmodule_ref;   // start of linked list
1172 }
1173
1174 ModuleInfo[] _moduleinfo_dtors;
1175 uint         _moduleinfo_dtors_i;
1176
1177 // Register termination function pointers
1178 extern (C) int _fatexit(void*);
1179
1180 /**
1181  * Initialize the modules.
1182  */
1183
1184 extern (C) void _moduleCtor()
1185 {
1186     debug(PRINTF) printf("_moduleCtor()\n");
1187     version (linux)
1188     {
1189         int len = 0;
1190         ModuleReference *mr;
1191
1192         for (mr = _Dmodule_ref; mr; mr = mr.next)
1193             len++;
1194         _moduleinfo_array = new ModuleInfo[len];
1195         len = 0;
1196         for (mr = _Dmodule_ref; mr; mr = mr.next)
1197         {   _moduleinfo_array[len] = mr.mod;
1198             len++;
1199         }
1200     }
1201
1202     version (Windows)
1203     {
1204         // Ensure module destructors also get called on program termination
1205         //_fatexit(&_STD_moduleDtor);
1206     }
1207
1208     _moduleinfo_dtors = new ModuleInfo[_moduleinfo_array.length];
1209     debug(PRINTF) printf("_moduleinfo_dtors = x%x\n", cast(void*)_moduleinfo_dtors);
1210     _moduleIndependentCtors();
1211     _moduleCtor2(_moduleinfo_array, 0);
1212 }
1213
1214 extern (C) void _moduleIndependentCtors()
1215 {
1216     debug(PRINTF) printf("_moduleIndependentCtors()\n");
1217     foreach (m; _moduleinfo_array)
1218     {
1219         if (m && m.flags & MIhasictor && m.ictor)
1220         {
1221             (*m.ictor)();
1222         }
1223     }
1224 }
1225
1226 void _moduleCtor2(ModuleInfo[] mi, int skip)
1227 {
1228     debug(PRINTF) printf("_moduleCtor2(): %d modules\n", mi.length);
1229     for (uint i = 0; i < mi.length; i++)
1230     {
1231         ModuleInfo m = mi[i];
1232
1233         debug(PRINTF) printf("\tmodule[%d] = '%p'\n", i, m);
1234         if (!m)
1235             continue;
1236         debug(PRINTF) printf("\tmodule[%d] = '%.*s'\n", i, m.name);
1237         if (m.flags & MIctordone)
1238             continue;
1239         debug(PRINTF) printf("\tmodule[%d] = '%.*s', m = x%x\n", i, m.name, m);
1240
1241         if (m.ctor || m.dtor)
1242         {
1243             if (m.flags & MIctorstart)
1244             {   if (skip || m.flags & MIstandalone)
1245                     continue;
1246                     throw new Exception( "Cyclic dependency in module " ~ m.name );
1247             }
1248
1249             m.flags |= MIctorstart;
1250             _moduleCtor2(m.importedModules, 0);
1251             if (m.ctor)
1252                 (*m.ctor)();
1253             m.flags &= ~MIctorstart;
1254             m.flags |= MIctordone;
1255
1256             // Now that construction is done, register the destructor
1257             //printf("\tadding module dtor x%x\n", m);
1258             assert(_moduleinfo_dtors_i < _moduleinfo_dtors.length);
1259             _moduleinfo_dtors[_moduleinfo_dtors_i++] = m;
1260         }
1261         else
1262         {
1263             m.flags |= MIctordone;
1264             _moduleCtor2(m.importedModules, 1);
1265         }
1266     }
1267 }
1268
1269 /**
1270  * Destruct the modules.
1271  */
1272
1273 // Starting the name with "_STD" means under linux a pointer to the
1274 // function gets put in the .dtors segment.
1275
1276 extern (C) void _moduleDtor()
1277 {
1278     debug(PRINTF) printf("_moduleDtor(): %d modules\n", _moduleinfo_dtors_i);
1279
1280     for (uint i = _moduleinfo_dtors_i; i-- != 0;)
1281     {
1282         ModuleInfo m = _moduleinfo_dtors[i];
1283
1284         debug(PRINTF) printf("\tmodule[%d] = '%.*s', x%x\n", i, m.name, m);
1285         if (m.dtor)
1286         {
1287             (*m.dtor)();
1288         }
1289     }
1290     debug(PRINTF) printf("_moduleDtor() done\n");
1291 }
1292
1293 ///////////////////////////////////////////////////////////////////////////////
1294 // Monitor
1295 ///////////////////////////////////////////////////////////////////////////////
1296
1297 alias Object.Monitor        IMonitor;
1298 alias void delegate(Object) DEvent;
1299
1300 // NOTE: The dtor callback feature is only supported for monitors that are not
1301 //       supplied by the user.  The assumption is that any object with a user-
1302 //       supplied monitor may have special storage or lifetime requirements and
1303 //       that as a result, storing references to local objects within Monitor
1304 //       may not be safe or desirable.  Thus, devt is only valid if impl is
1305 //       null.
1306 struct Monitor
1307 {
1308     IMonitor impl;
1309     /* internal */
1310     DEvent[] devt;
1311     /* stuff */
1312 }
1313
1314 Monitor* getMonitor(Object h)
1315 {
1316     return cast(Monitor*) (cast(void**) h)[1];
1317 }
1318
1319 void setMonitor(Object h, Monitor* m)
1320 {
1321     (cast(void**) h)[1] = m;
1322 }
1323
1324 extern (C) void _d_monitor_create(Object);
1325 extern (C) void _d_monitor_destroy(Object);
1326 extern (C) void _d_monitor_lock(Object);
1327 extern (C) int  _d_monitor_unlock(Object);
1328
1329 extern (C) void _d_monitordelete(Object h, bool det)
1330 {
1331     Monitor* m = getMonitor(h);
1332
1333     if (m !is null)
1334     {
1335         IMonitor i = m.impl;
1336         if (i is null)
1337         {
1338             _d_monitor_devt(m, h);
1339             _d_monitor_destroy(h);
1340             setMonitor(h, null);
1341             return;
1342         }
1343         if (det && (cast(void*) i) !is (cast(void*) h))
1344             delete i;
1345         setMonitor(h, null);
1346     }
1347 }
1348
1349 extern (C) void _d_monitorenter(Object h)
1350 {
1351     Monitor* m = getMonitor(h);
1352
1353     if (m is null)
1354     {
1355         _d_monitor_create(h);
1356         m = getMonitor(h);
1357     }
1358
1359     IMonitor i = m.impl;
1360
1361     if (i is null)
1362     {
1363         _d_monitor_lock(h);
1364         return;
1365     }
1366     i.lock();
1367 }
1368
1369 extern (C) void _d_monitorexit(Object h)
1370 {
1371     Monitor* m = getMonitor(h);
1372     IMonitor i = m.impl;
1373
1374     if (i is null)
1375     {
1376         _d_monitor_unlock(h);
1377         return;
1378     }
1379     i.unlock();
1380 }
1381
1382 extern (C) void _d_monitor_devt(Monitor* m, Object h)
1383 {
1384     if (m.devt.length)
1385     {
1386         DEvent[] devt;
1387
1388         synchronized (h)
1389         {
1390             devt = m.devt;
1391             m.devt = null;
1392         }
1393         foreach (v; devt)
1394         {
1395             if (v)
1396                 v(h);
1397         }
1398         free(devt.ptr);
1399     }
1400 }
1401
1402 extern (C) void rt_attachDisposeEvent(Object h, DEvent e)
1403 {
1404     synchronized (h)
1405     {
1406         Monitor* m = getMonitor(h);
1407         assert(m.impl is null);
1408
1409         foreach (inout v; m.devt)
1410         {
1411             if (v is null || v == e)
1412             {
1413                 v = e;
1414                 return;
1415             }
1416         }
1417
1418         auto len = m.devt.length + 4; // grow by 4 elements
1419         auto pos = m.devt.length;     // insert position
1420         auto p = realloc(m.devt.ptr, DEvent.sizeof * len);
1421         if (!p)
1422             onOutOfMemoryError();
1423         m.devt = (cast(DEvent*)p)[0 .. len];
1424         m.devt[pos+1 .. len] = null;
1425         m.devt[pos] = e;
1426     }
1427 }
1428
1429 extern (C) void rt_detachDisposeEvent(Object h, DEvent e)
1430 {
1431     synchronized (h)
1432     {
1433         Monitor* m = getMonitor(h);
1434         assert(m.impl is null);
1435
1436         foreach (p, v; m.devt)
1437         {
1438             if (v == e)
1439             {
1440                 memmove(&m.devt[p],
1441                         &m.devt[p+1],
1442                         (m.devt.length - p - 1) * DEvent.sizeof);
1443                 m.devt[$ - 1] = null;
1444                 return;
1445             }
1446         }
1447     }
1448 }