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