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