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