mcs/mcs/flowanalysis.cs

   1 //
   2 // flowanalyis.cs: The control flow analysis code
   3 //
   4 // Author:
   5 //   Martin Baulig (martin@ximian.com)
   6 //
   7 // (C) 2001, 2002, 2003 Ximian, Inc.
   8 //
   9
  10 using System;
  11 using System.Text;
  12 using System.Collections;
  13 using System.Reflection;
  14 using System.Reflection.Emit;
  15 using System.Diagnostics;
  16
  17 namespace Mono.CSharp
  18 {
  19         // <summary>
  20         //   A new instance of this class is created every time a new block is resolved
  21         //   and if there's branching in the block's control flow.
  22         // </summary>
  23         public abstract class FlowBranching
  24         {
  25                 // <summary>
  26                 //   The type of a FlowBranching.
  27                 // </summary>
  28                 public enum BranchingType : byte {
  29                         // Normal (conditional or toplevel) block.
  30                         Block,
  31
  32                         // Conditional.
  33                         Conditional,
  34
  35                         // A loop block.
  36                         Loop,
  37
  38                         // Try/Catch block.
  39                         Exception,
  40
  41                         // Switch block.
  42                         Switch,
  43
  44                         // Switch section.
  45                         SwitchSection
  46                 }
  47
  48                 // <summary>
  49                 //   The type of one sibling of a branching.
  50                 // </summary>
  51                 public enum SiblingType : byte {
  52                         Block,
  53                         Conditional,
  54                         SwitchSection,
  55                         Try,
  56                         Catch,
  57                         Finally
  58                 }
  59
  60                 // <summary>
  61                 //   This is used in the control flow analysis code to specify whether the
  62                 //   current code block may return to its enclosing block before reaching
  63                 //   its end.
  64                 // </summary>
  65                 public enum FlowReturns : byte {
  66                         Undefined = 0,
  67
  68                         // It can never return.
  69                         Never,
  70
  71                         // This means that the block contains a conditional return statement
  72                         // somewhere.
  73                         Sometimes,
  74
  75                         // The code always returns, ie. there's an unconditional return / break
  76                         // statement in it.
  77                         Always
  78                 }
  79
  80                 public sealed class Reachability
  81                 {
  82                         FlowReturns returns, breaks, throws, barrier;
  83
  84                         public FlowReturns Returns {
  85                                 get { return returns; }
  86                         }
  87                         public FlowReturns Breaks {
  88                                 get { return breaks; }
  89                         }
  90                         public FlowReturns Throws {
  91                                 get { return throws; }
  92                         }
  93                         public FlowReturns Barrier {
  94                                 get { return barrier; }
  95                         }
  96                         public Reachability (FlowReturns returns, FlowReturns breaks,
  97                                              FlowReturns throws, FlowReturns barrier)
  98                         {
  99                                 this.returns = returns;
 100                                 this.breaks = breaks;
 101                                 this.throws = throws;
 102                                 this.barrier = barrier;
 103                         }
 104
 105                         public Reachability Clone ()
 106                         {
 107                                 return new Reachability (returns, breaks, throws, barrier);
 108                         }
 109
 110                         // <summary>
 111                         //   Performs an `And' operation on the FlowReturns status
 112                         //   (for instance, a block only returns Always if all its siblings
 113                         //   always return).
 114                         // </summary>
 115                         public static FlowReturns AndFlowReturns (FlowReturns a, FlowReturns b)
 116                         {
 117                                 if (a == FlowReturns.Undefined)
 118                                         return b;
 119
 120                                 switch (a) {
 121                                 case FlowReturns.Never:
 122                                         if (b == FlowReturns.Never)
 123                                                 return FlowReturns.Never;
 124                                         else
 125                                                 return FlowReturns.Sometimes;
 126
 127                                 case FlowReturns.Sometimes:
 128                                         return FlowReturns.Sometimes;
 129
 130                                 case FlowReturns.Always:
 131                                         if (b == FlowReturns.Always)
 132                                                 return FlowReturns.Always;
 133                                         else
 134                                                 return FlowReturns.Sometimes;
 135
 136                                 default:
 137                                         throw new ArgumentException ();
 138                                 }
 139                         }
 140
 141                         public static FlowReturns OrFlowReturns (FlowReturns a, FlowReturns b)
 142                         {
 143                                 if (a == FlowReturns.Undefined)
 144                                         return b;
 145
 146                                 switch (a) {
 147                                 case FlowReturns.Never:
 148                                         return b;
 149
 150                                 case FlowReturns.Sometimes:
 151                                         if (b == FlowReturns.Always)
 152                                                 return FlowReturns.Always;
 153                                         else
 154                                                 return FlowReturns.Sometimes;
 155
 156                                 case FlowReturns.Always:
 157                                         return FlowReturns.Always;
 158
 159                                 default:
 160                                         throw new ArgumentException ();
 161                                 }
 162                         }
 163
 164                         public static void And (ref Reachability a, Reachability b, bool do_break)
 165                         {
 166                                 if (a == null) {
 167                                         a = b.Clone ();
 168                                         return;
 169                                 }
 170
 171                                 a.And (b, do_break);
 172                         }
 173
 174                         public void And (Reachability b, bool do_break)
 175                         {
 176                                 //
 177                                 // `break' does not "break" in a Switch or a LoopBlock
 178                                 //
 179                                 bool a_breaks = do_break && AlwaysBreaks;
 180                                 bool b_breaks = do_break && b.AlwaysBreaks;
 181
 182                                 bool a_has_barrier, b_has_barrier;
 183                                 if (do_break) {
 184                                         //
 185                                         // This is the normal case: the code following a barrier
 186                                         // cannot be reached.
 187                                         //
 188                                         a_has_barrier = AlwaysHasBarrier;
 189                                         b_has_barrier = b.AlwaysHasBarrier;
 190                                 } else {
 191                                         //
 192                                         // Special case for Switch and LoopBlocks: we can reach the
 193                                         // code after the barrier via the `break'.
 194                                         //
 195                                         a_has_barrier = !AlwaysBreaks && AlwaysHasBarrier;
 196                                         b_has_barrier = !b.AlwaysBreaks && b.AlwaysHasBarrier;
 197                                 }
 198
 199                                 bool a_unreachable = a_breaks || AlwaysThrows || a_has_barrier;
 200                                 bool b_unreachable = b_breaks || b.AlwaysThrows || b_has_barrier;
 201
 202                                 //
 203                                 // Do all code paths always return ?
 204                                 //
 205                                 if (AlwaysReturns) {
 206                                         if (b.AlwaysReturns || b_unreachable)
 207                                                 returns = FlowReturns.Always;
 208                                         else
 209                                                 returns = FlowReturns.Sometimes;
 210                                 } else if (b.AlwaysReturns) {
 211                                         if (AlwaysReturns || a_unreachable)
 212                                                 returns = FlowReturns.Always;
 213                                         else
 214                                                 returns = FlowReturns.Sometimes;
 215                                 } else if (!MayReturn) {
 216                                         if (b.MayReturn)
 217                                                 returns = FlowReturns.Sometimes;
 218                                         else
 219                                                 returns = FlowReturns.Never;
 220                                 } else if (!b.MayReturn) {
 221                                         if (MayReturn)
 222                                                 returns = FlowReturns.Sometimes;
 223                                         else
 224                                                 returns = FlowReturns.Never;
 225                                 }
 226
 227                                 breaks = AndFlowReturns (breaks, b.breaks);
 228                                 throws = AndFlowReturns (throws, b.throws);
 229                                 barrier = AndFlowReturns (barrier, b.barrier);
 230
 231                                 if (a_unreachable && b_unreachable)
 232                                         barrier = FlowReturns.Always;
 233                                 else if (a_unreachable || b_unreachable)
 234                                         barrier = FlowReturns.Sometimes;
 235                                 else
 236                                         barrier = FlowReturns.Never;
 237                         }
 238
 239                         public void Or (Reachability b)
 240                         {
 241                                 returns = OrFlowReturns (returns, b.returns);
 242                                 breaks = OrFlowReturns (breaks, b.breaks);
 243                                 throws = OrFlowReturns (throws, b.throws);
 244                                 barrier = OrFlowReturns (barrier, b.barrier);
 245                         }
 246
 247                         public static Reachability Never ()
 248                         {
 249                                 return new Reachability (
 250                                         FlowReturns.Never, FlowReturns.Never,
 251                                         FlowReturns.Never, FlowReturns.Never);
 252                         }
 253
 254                         public FlowReturns Reachable {
 255                                 get {
 256                                         if ((returns == FlowReturns.Always) ||
 257                                             (breaks == FlowReturns.Always) ||
 258                                             (throws == FlowReturns.Always) ||
 259                                             (barrier == FlowReturns.Always))
 260                                                 return FlowReturns.Never;
 261                                         else if ((returns == FlowReturns.Never) &&
 262                                                  (breaks == FlowReturns.Never) &&
 263                                                  (throws == FlowReturns.Never) &&
 264                                                  (barrier == FlowReturns.Never))
 265                                                 return FlowReturns.Always;
 266                                         else
 267                                                 return FlowReturns.Sometimes;
 268                                 }
 269                         }
 270
 271                         public bool AlwaysBreaks {
 272                                 get { return breaks == FlowReturns.Always; }
 273                         }
 274
 275                         public bool MayBreak {
 276                                 get { return breaks != FlowReturns.Never; }
 277                         }
 278
 279                         public bool AlwaysReturns {
 280                                 get { return returns == FlowReturns.Always; }
 281                         }
 282
 283                         public bool MayReturn {
 284                                 get { return returns != FlowReturns.Never; }
 285                         }
 286
 287                         public bool AlwaysThrows {
 288                                 get { return throws == FlowReturns.Always; }
 289                         }
 290
 291                         public bool MayThrow {
 292                                 get { return throws != FlowReturns.Never; }
 293                         }
 294
 295                         public bool AlwaysHasBarrier {
 296                                 get { return barrier == FlowReturns.Always; }
 297                         }
 298
 299                         public bool MayHaveBarrier {
 300                                 get { return barrier != FlowReturns.Never; }
 301                         }
 302
 303                         public bool IsUnreachable {
 304                                 get { return Reachable == FlowReturns.Never; }
 305                         }
 306
 307                         public void SetReturns ()
 308                         {
 309                                 returns = FlowReturns.Always;
 310                         }
 311
 312                         public void SetReturnsSometimes ()
 313                         {
 314                                 returns = FlowReturns.Sometimes;
 315                         }
 316
 317                         public void SetBreaks ()
 318                         {
 319                                 breaks = FlowReturns.Always;
 320                         }
 321
 322                         public void ResetBreaks ()
 323                         {
 324                                 breaks = FlowReturns.Never;
 325                         }
 326
 327                         public void SetThrows ()
 328                         {
 329                                 throws = FlowReturns.Always;
 330                         }
 331
 332                         public void SetThrowsSometimes ()
 333                         {
 334                                 throws = FlowReturns.Sometimes;
 335                         }
 336
 337                         public void SetBarrier ()
 338                         {
 339                                 barrier = FlowReturns.Always;
 340                         }
 341
 342                         public void ResetBarrier ()
 343                         {
 344                                 barrier = FlowReturns.Never;
 345                         }
 346
 347                         static string ShortName (FlowReturns returns)
 348                         {
 349                                 switch (returns) {
 350                                 case FlowReturns.Never:
 351                                         return "N";
 352                                 case FlowReturns.Sometimes:
 353                                         return "S";
 354                                 default:
 355                                         return "A";
 356                                 }
 357                         }
 358
 359                         public override string ToString ()
 360                         {
 361                                 return String.Format ("[{0}:{1}:{2}:{3}:{4}]",
 362                                                       ShortName (returns), ShortName (breaks),
 363                                                       ShortName (throws), ShortName (barrier),
 364                                                       ShortName (Reachable));
 365                         }
 366                 }
 367
 368                 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
 369                 {
 370                         switch (type) {
 371                         case BranchingType.Exception:
 372                                 throw new InvalidOperationException ();
 373
 374                         case BranchingType.Switch:
 375                                 return new FlowBranchingSwitch (parent, block, loc);
 376
 377                         case BranchingType.SwitchSection:
 378                                 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
 379
 380                         case BranchingType.Block:
 381                                 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
 382
 383                         case BranchingType.Loop:
 384                                 return new FlowBranchingLoop (parent, block, loc);
 385
 386                         default:
 387                                 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
 388                         }
 389                 }
 390
 391                 // <summary>
 392                 //   The type of this flow branching.
 393                 // </summary>
 394                 public readonly BranchingType Type;
 395
 396                 // <summary>
 397                 //   The block this branching is contained in.  This may be null if it's not
 398                 //   a top-level block and it doesn't declare any local variables.
 399                 // </summary>
 400                 public readonly Block Block;
 401
 402                 // <summary>
 403                 //   The parent of this branching or null if this is the top-block.
 404                 // </summary>
 405                 public readonly FlowBranching Parent;
 406
 407                 // <summary>
 408                 //   Start-Location of this flow branching.
 409                 // </summary>
 410                 public readonly Location Location;
 411
 412                 // <summary>
 413                 //   If this is an infinite loop.
 414                 // </summary>
 415                 public bool Infinite;
 416
 417                 //
 418                 // Private
 419                 //
 420                 VariableMap param_map, local_map;
 421
 422                 static int next_id = 0;
 423                 int id;
 424
 425                 // <summary>
 426                 //   The vector contains a BitArray with information about which local variables
 427                 //   and parameters are already initialized at the current code position.
 428                 // </summary>
 429                 public class UsageVector {
 430                         // <summary>
 431                         //   The type of this branching.
 432                         // </summary>
 433                         public readonly SiblingType Type;
 434
 435                         // <summary>
 436                         //   Start location of this branching.
 437                         // </summary>
 438                         public readonly Location Location;
 439
 440                         // <summary>
 441                         //   This is only valid for SwitchSection, Try, Catch and Finally.
 442                         // </summary>
 443                         public readonly Block Block;
 444
 445                         // <summary>
 446                         //   If this is true, then the usage vector has been modified and must be
 447                         //   merged when we're done with this branching.
 448                         // </summary>
 449                         public bool IsDirty;
 450
 451                         // <summary>
 452                         //   The number of parameters in this block.
 453                         // </summary>
 454                         public readonly int CountParameters;
 455
 456                         // <summary>
 457                         //   The number of locals in this block.
 458                         // </summary>
 459                         public readonly int CountLocals;
 460
 461                         // <summary>
 462                         //   If not null, then we inherit our state from this vector and do a
 463                         //   copy-on-write.  If null, then we're the first sibling in a top-level
 464                         //   block and inherit from the empty vector.
 465                         // </summary>
 466                         public readonly UsageVector InheritsFrom;
 467
 468                         // <summary>
 469                         //   This is used to construct a list of UsageVector's.
 470                         // </summary>
 471                         public UsageVector Next;
 472
 473                         //
 474                         // Private.
 475                         //
 476                         MyBitVector locals, parameters;
 477                         Reachability reachability;
 478
 479                         static int next_id = 0;
 480                         int id;
 481
 482                         //
 483                         // Normally, you should not use any of these constructors.
 484                         //
 485                         public UsageVector (SiblingType type, UsageVector parent,
 486                                             Block block, Location loc,
 487                                             int num_params, int num_locals)
 488                         {
 489                                 this.Type = type;
 490                                 this.Block = block;
 491                                 this.Location = loc;
 492                                 this.InheritsFrom = parent;
 493                                 this.CountParameters = num_params;
 494                                 this.CountLocals = num_locals;
 495
 496                                 if (parent != null) {
 497                                         if (num_locals > 0)
 498                                                 locals = new MyBitVector (parent.locals, CountLocals);
 499
 500                                         if (num_params > 0)
 501                                                 parameters = new MyBitVector (parent.parameters, num_params);
 502
 503                                         reachability = parent.Reachability.Clone ();
 504                                 } else {
 505                                         if (num_locals > 0)
 506                                                 locals = new MyBitVector (null, CountLocals);
 507
 508                                         if (num_params > 0)
 509                                                 parameters = new MyBitVector (null, num_params);
 510
 511                                         reachability = Reachability.Never ();
 512                                 }
 513
 514                                 id = ++next_id;
 515                         }
 516
 517                         public UsageVector (SiblingType type, UsageVector parent,
 518                                             Block block, Location loc)
 519                                 : this (type, parent, block, loc,
 520                                         parent.CountParameters, parent.CountLocals)
 521                         { }
 522
 523                         public UsageVector (MyBitVector parameters, MyBitVector locals,
 524                                             Reachability reachability, Block block,
 525                                             Location loc)
 526                         {
 527                                 this.Type = SiblingType.Block;
 528                                 this.Location = loc;
 529                                 this.Block = block;
 530
 531                                 this.reachability = reachability;
 532                                 this.parameters = parameters;
 533                                 this.locals = locals;
 534
 535                                 id = ++next_id;
 536                         }
 537
 538                         // <summary>
 539                         //   This does a deep copy of the usage vector.
 540                         // </summary>
 541                         public UsageVector Clone ()
 542                         {
 543                                 UsageVector retval = new UsageVector (
 544                                         Type, null, Block, Location,
 545                                         CountParameters, CountLocals);
 546
 547                                 if (retval.locals != null)
 548                                         retval.locals = locals.Clone ();
 549
 550                                 if (parameters != null)
 551                                         retval.parameters = parameters.Clone ();
 552
 553                                 retval.reachability = reachability.Clone ();
 554
 555                                 return retval;
 556                         }
 557
 558                         public bool IsAssigned (VariableInfo var)
 559                         {
 560                                 if (!var.IsParameter && Reachability.IsUnreachable)
 561                                         return true;
 562
 563                                 return var.IsAssigned (var.IsParameter ? parameters : locals);
 564                         }
 565
 566                         public void SetAssigned (VariableInfo var)
 567                         {
 568                                 if (!var.IsParameter && Reachability.IsUnreachable)
 569                                         return;
 570
 571                                 IsDirty = true;
 572                                 var.SetAssigned (var.IsParameter ? parameters : locals);
 573                         }
 574
 575                         public bool IsFieldAssigned (VariableInfo var, string name)
 576                         {
 577                                 if (!var.IsParameter && Reachability.IsUnreachable)
 578                                         return true;
 579
 580                                 return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
 581                         }
 582
 583                         public void SetFieldAssigned (VariableInfo var, string name)
 584                         {
 585                                 if (!var.IsParameter && Reachability.IsUnreachable)
 586                                         return;
 587
 588                                 IsDirty = true;
 589                                 var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
 590                         }
 591
 592                         public Reachability Reachability {
 593                                 get {
 594                                         return reachability;
 595                                 }
 596                         }
 597
 598                         public void Return ()
 599                         {
 600                                 if (!reachability.IsUnreachable) {
 601                                         IsDirty = true;
 602                                         reachability.SetReturns ();
 603                                 }
 604                         }
 605
 606                         public void Break ()
 607                         {
 608                                 if (!reachability.IsUnreachable) {
 609                                         IsDirty = true;
 610                                         reachability.SetBreaks ();
 611                                 }
 612                         }
 613
 614                         public void Throw ()
 615                         {
 616                                 if (!reachability.IsUnreachable) {
 617                                         IsDirty = true;
 618                                         reachability.SetThrows ();
 619                                 }
 620                         }
 621
 622                         public void Goto ()
 623                         {
 624                                 if (!reachability.IsUnreachable) {
 625                                         IsDirty = true;
 626                                         reachability.SetBarrier ();
 627                                 }
 628                         }
 629
 630                         // <summary>
 631                         //   Merges a child branching.
 632                         // </summary>
 633                         public UsageVector MergeChild (FlowBranching branching)
 634                         {
 635                                 UsageVector result = branching.Merge ();
 636
 637                                 Report.Debug (2, "  MERGING CHILD", this, branching, IsDirty,
 638                                               result.ParameterVector, result.LocalVector,
 639                                               result.Reachability, reachability, Type);
 640
 641                                 Reachability new_r = result.Reachability;
 642
 643                                 if (branching.Type == BranchingType.Loop) {
 644                                         bool may_leave_loop = new_r.MayBreak;
 645                                         new_r.ResetBreaks ();
 646
 647                                         if (branching.Infinite && !may_leave_loop) {
 648                                                 if (new_r.Returns == FlowReturns.Sometimes) {
 649                                                         // If we're an infinite loop and do not break,
 650                                                         // the code after the loop can never be reached.
 651                                                         // However, if we may return from the loop,
 652                                                         // then we do always return (or stay in the
 653                                                         // loop forever).
 654                                                         new_r.SetReturns ();
 655                                                 }
 656
 657                                                 new_r.SetBarrier ();
 658                                         }
 659
 660                                         if (may_leave_loop)
 661                                                 new_r.ResetBarrier ();
 662                                 } else if (branching.Type == BranchingType.Switch) {
 663                                         if (new_r.MayBreak || new_r.MayReturn)
 664                                                 new_r.ResetBarrier ();
 665
 666                                         new_r.ResetBreaks ();
 667                                 }
 668
 669                                 //
 670                                 // We've now either reached the point after the branching or we will
 671                                 // never get there since we always return or always throw an exception.
 672                                 //
 673                                 // If we can reach the point after the branching, mark all locals and
 674                                 // parameters as initialized which have been initialized in all branches
 675                                 // we need to look at (see above).
 676                                 //
 677
 678                                 if ((Type == SiblingType.SwitchSection) && !new_r.IsUnreachable) {
 679                                         Report.Error (163, Location,
 680                                                       "Control cannot fall through from one " +
 681                                                       "case label to another");
 682                                         return result;
 683                                 }
 684
 685                                 if (locals != null && result.LocalVector != null)
 686                                         locals.Or (result.LocalVector);
 687
 688                                 if (result.ParameterVector != null)
 689                                         parameters.Or (result.ParameterVector);
 690
 691                                 if ((branching.Type == BranchingType.Block) && branching.Block.Implicit)
 692                                         reachability = new_r.Clone ();
 693                                 else
 694                                         reachability.Or (new_r);
 695
 696                                 Report.Debug (2, "  MERGING CHILD DONE", this, result,
 697                                               new_r, reachability);
 698
 699                                 IsDirty = true;
 700
 701                                 return result;
 702                         }
 703
 704                         protected void MergeFinally (FlowBranching branching, UsageVector f_origins,
 705                                                      MyBitVector f_params)
 706                         {
 707                                 for (UsageVector vector = f_origins; vector != null; vector = vector.Next) {
 708                                         MyBitVector temp_params = f_params.Clone ();
 709                                         temp_params.Or (vector.Parameters);
 710                                 }
 711                         }
 712
 713                         public void MergeFinally (FlowBranching branching, UsageVector f_vector,
 714                                                   UsageVector f_origins)
 715                         {
 716                                 if (parameters != null) {
 717                                         if (f_vector != null) {
 718                                                 MergeFinally (branching, f_origins, f_vector.Parameters);
 719                                                 MyBitVector.Or (ref parameters, f_vector.ParameterVector);
 720                                         } else
 721                                                 MergeFinally (branching, f_origins, parameters);
 722                                 }
 723
 724                                 if (f_vector != null && f_vector.LocalVector != null)
 725                                         MyBitVector.Or (ref locals, f_vector.LocalVector);
 726                         }
 727
 728                         // <summary>
 729                         //   Tells control flow analysis that the current code position may be reached with
 730                         //   a forward jump from any of the origins listed in `origin_vectors' which is a
 731                         //   list of UsageVectors.
 732                         //
 733                         //   This is used when resolving forward gotos - in the following example, the
 734                         //   variable `a' is uninitialized in line 8 becase this line may be reached via
 735                         //   the goto in line 4:
 736                         //
 737                         //      1     int a;
 738                         //
 739                         //      3     if (something)
 740                         //      4        goto World;
 741                         //
 742                         //      6     a = 5;
 743                         //
 744                         //      7  World:
 745                         //      8     Console.WriteLine (a);
 746                         //
 747                         // </summary>
 748                         public void MergeJumpOrigins (UsageVector o_vectors)
 749                         {
 750                                 Report.Debug (1, "  MERGING JUMP ORIGINS", this);
 751
 752                                 reachability = Reachability.Never ();
 753
 754                                 if (o_vectors == null) {
 755                                         reachability.SetBarrier ();
 756                                         return;
 757                                 }
 758
 759                                 bool first = true;
 760
 761                                 for (UsageVector vector = o_vectors; vector != null;
 762                                      vector = vector.Next) {
 763                                         Report.Debug (1, "  MERGING JUMP ORIGIN", vector,
 764                                                       first, locals, vector.Locals);
 765
 766                                         if (first) {
 767                                                 if (locals != null && vector.Locals != null)
 768                                                         locals.Or (vector.locals);
 769
 770                                                 if (parameters != null)
 771                                                         parameters.Or (vector.parameters);
 772                                                 first = false;
 773                                         } else {
 774                                                 if (locals != null)
 775                                                         locals.And (vector.locals);
 776                                                 if (parameters != null)
 777                                                         parameters.And (vector.parameters);
 778                                         }
 779
 780                                         Reachability.And (ref reachability, vector.Reachability, true);
 781
 782                                         Report.Debug (1, "  MERGING JUMP ORIGIN #1", vector);
 783                                 }
 784
 785                                 Report.Debug (1, "  MERGING JUMP ORIGINS DONE", this);
 786                         }
 787
 788                         // <summary>
 789                         //   This is used at the beginning of a finally block if there were
 790                         //   any return statements in the try block or one of the catch blocks.
 791                         // </summary>
 792                         public void MergeFinallyOrigins (UsageVector f_origins)
 793                         {
 794                                 Report.Debug (1, "  MERGING FINALLY ORIGIN", this);
 795
 796                                 reachability = Reachability.Never ();
 797
 798                                 for (UsageVector vector = f_origins; vector != null; vector = vector.Next) {
 799                                         Report.Debug (1, "    MERGING FINALLY ORIGIN", vector);
 800
 801                                         if (parameters != null)
 802                                                 parameters.And (vector.parameters);
 803
 804                                         Reachability.And (ref reachability, vector.Reachability, true);
 805                                 }
 806
 807                                 Report.Debug (1, "  MERGING FINALLY ORIGIN DONE", this);
 808                         }
 809
 810                         public void MergeBreakOrigins (FlowBranching branching, UsageVector o_vectors)
 811                         {
 812                                 Report.Debug (1, "  MERGING BREAK ORIGINS", this);
 813
 814                                 if (o_vectors == null)
 815                                         return;
 816
 817                                 bool first = branching.Infinite;
 818
 819                                 for (UsageVector vector = o_vectors; vector != null;
 820                                      vector = vector.Next) {
 821                                         Report.Debug (1, "    MERGING BREAK ORIGIN", vector, first);
 822
 823                                         if (first) {
 824                                                 if (locals != null && vector.Locals != null)
 825                                                         locals.Or (vector.locals);
 826
 827                                                 if (parameters != null)
 828                                                         parameters.Or (vector.parameters);
 829                                                 first = false;
 830                                         } else {
 831                                                 if (locals != null && vector.Locals != null)
 832                                                         locals.And (vector.locals);
 833                                                 if (parameters != null)
 834                                                         parameters.And (vector.parameters);
 835                                         }
 836
 837                                         reachability.And (vector.Reachability, false);
 838                                 }
 839
 840                                 Report.Debug (1, "  MERGING BREAK ORIGINS DONE", this);
 841                         }
 842
 843                         public void CheckOutParameters (FlowBranching branching)
 844                         {
 845                                 if (parameters != null)
 846                                         branching.CheckOutParameters (parameters, branching.Location);
 847                         }
 848
 849                         // <summary>
 850                         //   Performs an `or' operation on the locals and the parameters.
 851                         // </summary>
 852                         public void Or (UsageVector new_vector)
 853                         {
 854                                 IsDirty = true;
 855                                 locals.Or (new_vector.locals);
 856                                 if (parameters != null)
 857                                         parameters.Or (new_vector.parameters);
 858                         }
 859
 860                         // <summary>
 861                         //   Performs an `and' operation on the locals.
 862                         // </summary>
 863                         public void AndLocals (UsageVector new_vector)
 864                         {
 865                                 IsDirty = true;
 866                                 locals.And (new_vector.locals);
 867                         }
 868
 869                         public bool HasParameters {
 870                                 get {
 871                                         return parameters != null;
 872                                 }
 873                         }
 874
 875                         public bool HasLocals {
 876                                 get {
 877                                         return locals != null;
 878                                 }
 879                         }
 880
 881                         // <summary>
 882                         //   Returns a deep copy of the parameters.
 883                         // </summary>
 884                         public MyBitVector Parameters {
 885                                 get {
 886                                         if (parameters != null)
 887                                                 return parameters.Clone ();
 888                                         else
 889                                                 return null;
 890                                 }
 891                         }
 892
 893                         // <summary>
 894                         //   Returns a deep copy of the locals.
 895                         // </summary>
 896                         public MyBitVector Locals {
 897                                 get {
 898                                         if (locals != null)
 899                                                 return locals.Clone ();
 900                                         else
 901                                                 return null;
 902                                 }
 903                         }
 904
 905                         public MyBitVector ParameterVector {
 906                                 get {
 907                                         return parameters;
 908                                 }
 909                         }
 910
 911                         public MyBitVector LocalVector {
 912                                 get {
 913                                         return locals;
 914                                 }
 915                         }
 916
 917                         //
 918                         // Debugging stuff.
 919                         //
 920
 921                         public override string ToString ()
 922                         {
 923                                 StringBuilder sb = new StringBuilder ();
 924
 925                                 sb.Append ("Vector (");
 926                                 sb.Append (Type);
 927                                 sb.Append (",");
 928                                 sb.Append (id);
 929                                 sb.Append (",");
 930                                 sb.Append (IsDirty);
 931                                 sb.Append (",");
 932                                 sb.Append (reachability);
 933                                 if (parameters != null) {
 934                                         sb.Append (" - ");
 935                                         sb.Append (parameters);
 936                                 }
 937                                 sb.Append (" - ");
 938                                 sb.Append (locals);
 939                                 sb.Append (")");
 940
 941                                 return sb.ToString ();
 942                         }
 943                 }
 944
 945                 // <summary>
 946                 //   Creates a new flow branching which is contained in `parent'.
 947                 //   You should only pass non-null for the `block' argument if this block
 948                 //   introduces any new variables - in this case, we need to create a new
 949                 //   usage vector with a different size than our parent's one.
 950                 // </summary>
 951                 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
 952                                          Block block, Location loc)
 953                 {
 954                         Parent = parent;
 955                         Block = block;
 956                         Location = loc;
 957                         Type = type;
 958                         id = ++next_id;
 959
 960                         UsageVector vector;
 961                         if (Block != null) {
 962                                 param_map = Block.ParameterMap;
 963                                 local_map = Block.LocalMap;
 964
 965                                 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
 966                                 vector = new UsageVector (
 967                                         stype, parent_vector, Block, loc,
 968                                         param_map.Length, local_map.Length);
 969                         } else {
 970                                 param_map = Parent.param_map;
 971                                 local_map = Parent.local_map;
 972                                 vector = new UsageVector (
 973                                         stype, Parent.CurrentUsageVector, null, loc);
 974                         }
 975
 976                         AddSibling (vector);
 977                 }
 978
 979                 public abstract UsageVector CurrentUsageVector {
 980                         get;
 981                 }
 982
 983                 // <summary>
 984                 //   Creates a sibling of the current usage vector.
 985                 // </summary>
 986                 public virtual void CreateSibling (Block block, SiblingType type)
 987                 {
 988                         UsageVector vector = new UsageVector (
 989                                 type, Parent.CurrentUsageVector, block, Location);
 990                         AddSibling (vector);
 991
 992                         Report.Debug (1, "  CREATED SIBLING", CurrentUsageVector);
 993                 }
 994
 995                 public void CreateSibling ()
 996                 {
 997                         CreateSibling (null, SiblingType.Conditional);
 998                 }
 999
1000                 protected abstract void AddSibling (UsageVector uv);
1001
1002                 public virtual LabeledStatement LookupLabel (string name, Location loc)
1003                 {
1004                         if (Parent != null)
1005                                 return Parent.LookupLabel (name, loc);
1006
1007                         Report.Error (
1008                                 159, loc,
1009                                 "No such label `" + name + "' in this scope");
1010                         return null;
1011                 }
1012
1013                 public abstract void Label (UsageVector origin_vectors);
1014
1015                 // <summary>
1016                 //   Check whether all `out' parameters have been assigned.
1017                 // </summary>
1018                 public void CheckOutParameters (MyBitVector parameters, Location loc)
1019                 {
1020                         for (int i = 0; i < param_map.Count; i++) {
1021                                 VariableInfo var = param_map [i];
1022
1023                                 if (var == null)
1024                                         continue;
1025
1026                                 if (var.IsAssigned (parameters))
1027                                         continue;
1028
1029                                 Report.Error (177, loc, "The out parameter `{0}' must be assigned to before control leaves the current method",
1030                                         var.Name);
1031                         }
1032                 }
1033
1034                 protected UsageVector Merge (UsageVector sibling_list)
1035                 {
1036                         if (sibling_list.Next == null)
1037                                 return sibling_list;
1038
1039                         MyBitVector locals = null;
1040                         MyBitVector parameters = null;
1041
1042                         Reachability reachability = null;
1043
1044                         Report.Debug (2, "  MERGING SIBLINGS", this, Name);
1045
1046                         for (UsageVector child = sibling_list; child != null; child = child.Next) {
1047                                 bool do_break = (Type != BranchingType.Switch) &&
1048                                         (Type != BranchingType.Loop);
1049
1050                                 Report.Debug (2, "    MERGING SIBLING   ", child,
1051                                               child.ParameterVector, child.LocalVector,
1052                                               reachability, child.Reachability, do_break);
1053
1054                                 Reachability.And (ref reachability, child.Reachability, do_break);
1055
1056                                 // A local variable is initialized after a flow branching if it
1057                                 // has been initialized in all its branches which do neither
1058                                 // always return or always throw an exception.
1059                                 //
1060                                 // If a branch may return, but does not always return, then we
1061                                 // can treat it like a never-returning branch here: control will
1062                                 // only reach the code position after the branching if we did not
1063                                 // return here.
1064                                 //
1065                                 // It's important to distinguish between always and sometimes
1066                                 // returning branches here:
1067                                 //
1068                                 //    1   int a;
1069                                 //    2   if (something) {
1070                                 //    3      return;
1071                                 //    4      a = 5;
1072                                 //    5   }
1073                                 //    6   Console.WriteLine (a);
1074                                 //
1075                                 // The if block in lines 3-4 always returns, so we must not look
1076                                 // at the initialization of `a' in line 4 - thus it'll still be
1077                                 // uninitialized in line 6.
1078                                 //
1079                                 // On the other hand, the following is allowed:
1080                                 //
1081                                 //    1   int a;
1082                                 //    2   if (something)
1083                                 //    3      a = 5;
1084                                 //    4   else
1085                                 //    5      return;
1086                                 //    6   Console.WriteLine (a);
1087                                 //
1088                                 // Here, `a' is initialized in line 3 and we must not look at
1089                                 // line 5 since it always returns.
1090                                 //
1091                                 bool do_break_2 = (child.Type != SiblingType.Block) &&
1092                                         (child.Type != SiblingType.SwitchSection);
1093                                 bool always_throws = (child.Type != SiblingType.Try) &&
1094                                         child.Reachability.AlwaysThrows;
1095                                 bool unreachable = always_throws ||
1096                                         (do_break_2 && child.Reachability.AlwaysBreaks) ||
1097                                         child.Reachability.AlwaysReturns ||
1098                                         child.Reachability.AlwaysHasBarrier;
1099
1100                                 Report.Debug (2, "    MERGING SIBLING #1", reachability,
1101                                               Type, child.Type, child.Reachability.IsUnreachable,
1102                                               do_break_2, always_throws, unreachable);
1103
1104                                 if (!unreachable && (child.LocalVector != null))
1105                                         MyBitVector.And (ref locals, child.LocalVector);
1106
1107                                 // An `out' parameter must be assigned in all branches which do
1108                                 // not always throw an exception.
1109                                 if ((child.ParameterVector != null) && !child.Reachability.AlwaysThrows)
1110                                         MyBitVector.And (ref parameters, child.ParameterVector);
1111
1112                                 Report.Debug (2, "    MERGING SIBLING #2", parameters, locals);
1113                         }
1114
1115                         if (reachability == null)
1116                                 reachability = Reachability.Never ();
1117
1118                         Report.Debug (2, "  MERGING SIBLINGS DONE", parameters, locals,
1119                                       reachability, Infinite);
1120
1121                         return new UsageVector (
1122                                 parameters, locals, reachability, null, Location);
1123                 }
1124
1125                 protected abstract UsageVector Merge ();
1126
1127                 // <summary>
1128                 //   Merge a child branching.
1129                 // </summary>
1130                 public UsageVector MergeChild (FlowBranching child)
1131                 {
1132                         return CurrentUsageVector.MergeChild (child);
1133                 }
1134
1135                 // <summary>
1136                 //   Does the toplevel merging.
1137                 // </summary>
1138                 public Reachability MergeTopBlock ()
1139                 {
1140                         if ((Type != BranchingType.Block) || (Block == null))
1141                                 throw new NotSupportedException ();
1142
1143                         UsageVector vector = new UsageVector (
1144                                 SiblingType.Block, null, Block, Location,
1145                                 param_map.Length, local_map.Length);
1146
1147                         UsageVector result = vector.MergeChild (this);
1148
1149                         Report.Debug (4, "MERGE TOP BLOCK", Location, vector, result.Reachability);
1150
1151                         if ((vector.Reachability.Throws != FlowReturns.Always) &&
1152                             (vector.Reachability.Barrier != FlowReturns.Always))
1153                                 CheckOutParameters (vector.Parameters, Location);
1154
1155                         return result.Reachability;
1156                 }
1157
1158                 //
1159                 // Checks whether we're in a `try' block.
1160                 //
1161                 public virtual bool InTryOrCatch (bool is_return)
1162                 {
1163                         if ((Block != null) && Block.IsDestructor)
1164                                 return true;
1165                         else if (!is_return &&
1166                             ((Type == BranchingType.Loop) || (Type == BranchingType.Switch)))
1167                                 return false;
1168                         else if (Parent != null)
1169                                 return Parent.InTryOrCatch (is_return);
1170                         else
1171                                 return false;
1172                 }
1173
1174                 public virtual bool InTryWithCatch ()
1175                 {
1176                         if (Parent != null)
1177                                 return Parent.InTryWithCatch ();
1178                         return false;
1179                 }
1180
1181                 public virtual bool InLoop ()
1182                 {
1183                         if (Type == BranchingType.Loop)
1184                                 return true;
1185                         else if (Parent != null)
1186                                 return Parent.InLoop ();
1187                         else
1188                                 return false;
1189                 }
1190
1191                 public virtual bool InSwitch ()
1192                 {
1193                         if (Type == BranchingType.Switch)
1194                                 return true;
1195                         else if (Parent != null)
1196                                 return Parent.InSwitch ();
1197                         else
1198                                 return false;
1199                 }
1200
1201                 public virtual bool BreakCrossesTryCatchBoundary ()
1202                 {
1203                         if ((Type == BranchingType.Loop) || (Type == BranchingType.Switch))
1204                                 return false;
1205                         else if (Parent != null)
1206                                 return Parent.BreakCrossesTryCatchBoundary ();
1207                         else
1208                                 return false;
1209                 }
1210
1211                 public virtual void AddFinallyVector (UsageVector vector)
1212                 {
1213                         if (Parent != null)
1214                                 Parent.AddFinallyVector (vector);
1215                         else if ((Block == null) || !Block.IsDestructor)
1216                                 throw new NotSupportedException ();
1217                 }
1218
1219                 public virtual void AddBreakVector (UsageVector vector)
1220                 {
1221                         if (Parent != null)
1222                                 Parent.AddBreakVector (vector);
1223                         else if ((Block == null) || !Block.IsDestructor)
1224                                 throw new NotSupportedException ();
1225                 }
1226
1227                 public virtual void StealFinallyClauses (ref ArrayList list)
1228                 {
1229                         if (Parent != null)
1230                                 Parent.StealFinallyClauses (ref list);
1231                 }
1232
1233                 public bool IsAssigned (VariableInfo vi)
1234                 {
1235                         return CurrentUsageVector.IsAssigned (vi);
1236                 }
1237
1238                 public bool IsFieldAssigned (VariableInfo vi, string field_name)
1239                 {
1240                         if (CurrentUsageVector.IsAssigned (vi))
1241                                 return true;
1242
1243                         return CurrentUsageVector.IsFieldAssigned (vi, field_name);
1244                 }
1245
1246                 public void SetAssigned (VariableInfo vi)
1247                 {
1248                         CurrentUsageVector.SetAssigned (vi);
1249                 }
1250
1251                 public void SetFieldAssigned (VariableInfo vi, string name)
1252                 {
1253                         CurrentUsageVector.SetFieldAssigned (vi, name);
1254                 }
1255
1256                 public override string ToString ()
1257                 {
1258                         StringBuilder sb = new StringBuilder ();
1259                         sb.Append (GetType ());
1260                         sb.Append (" (");
1261
1262                         sb.Append (id);
1263                         sb.Append (",");
1264                         sb.Append (Type);
1265                         if (Block != null) {
1266                                 sb.Append (" - ");
1267                                 sb.Append (Block.ID);
1268                                 sb.Append (" - ");
1269                                 sb.Append (Block.StartLocation);
1270                         }
1271                         sb.Append (" - ");
1272                         // sb.Append (Siblings.Length);
1273                         // sb.Append (" - ");
1274                         sb.Append (CurrentUsageVector);
1275                         sb.Append (")");
1276                         return sb.ToString ();
1277                 }
1278
1279                 public string Name {
1280                         get {
1281                                 return String.Format ("{0} ({1}:{2}:{3})",
1282                                                       GetType (), id, Type, Location);
1283                         }
1284                 }
1285         }
1286
1287         public class FlowBranchingBlock : FlowBranching
1288         {
1289                 UsageVector sibling_list = null;
1290
1291                 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
1292                                            SiblingType stype, Block block, Location loc)
1293                         : base (parent, type, stype, block, loc)
1294                 { }
1295
1296                 public override UsageVector CurrentUsageVector {
1297                         get { return sibling_list; }
1298                 }
1299
1300                 protected override void AddSibling (UsageVector sibling)
1301                 {
1302                         sibling.Next = sibling_list;
1303                         sibling_list = sibling;
1304                 }
1305
1306                 public override LabeledStatement LookupLabel (string name, Location loc)
1307                 {
1308                         if (Block == null)
1309                                 return base.LookupLabel (name, loc);
1310
1311                         LabeledStatement s = Block.LookupLabel (name);
1312                         if (s != null)
1313                                 return s;
1314
1315                         return base.LookupLabel (name, loc);
1316                 }
1317
1318                 public override void Label (UsageVector origin_vectors)
1319                 {
1320                         if (!CurrentUsageVector.Reachability.IsUnreachable) {
1321                                 UsageVector vector = CurrentUsageVector.Clone ();
1322                                 vector.Next = origin_vectors;
1323                                 origin_vectors = vector;
1324                         }
1325
1326                         CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1327                 }
1328
1329                 protected override UsageVector Merge ()
1330                 {
1331                         return Merge (sibling_list);
1332                 }
1333         }
1334
1335         public class FlowBranchingLoop : FlowBranchingBlock
1336         {
1337                 UsageVector break_origins;
1338
1339                 public FlowBranchingLoop (FlowBranching parent, Block block, Location loc)
1340                         : base (parent, BranchingType.Loop, SiblingType.Conditional, block, loc)
1341                 { }
1342
1343                 public override void AddBreakVector (UsageVector vector)
1344                 {
1345                         vector = vector.Clone ();
1346                         vector.Next = break_origins;
1347                         break_origins = vector;
1348                 }
1349
1350                 protected override UsageVector Merge ()
1351                 {
1352                         UsageVector vector = base.Merge ();
1353
1354                         vector.MergeBreakOrigins (this, break_origins);
1355
1356                         return vector;
1357                 }
1358         }
1359
1360         public class FlowBranchingSwitch : FlowBranchingBlock
1361         {
1362                 UsageVector break_origins;
1363
1364                 public FlowBranchingSwitch (FlowBranching parent, Block block, Location loc)
1365                         : base (parent, BranchingType.Switch, SiblingType.SwitchSection, block, loc)
1366                 { }
1367
1368                 public override void AddBreakVector (UsageVector vector)
1369                 {
1370                         vector = vector.Clone ();
1371                         vector.Next = break_origins;
1372                         break_origins = vector;
1373                 }
1374
1375                 protected override UsageVector Merge ()
1376                 {
1377                         UsageVector vector = base.Merge ();
1378
1379                         vector.MergeBreakOrigins (this, break_origins);
1380
1381                         return vector;
1382                 }
1383         }
1384
1385         public class FlowBranchingException : FlowBranching
1386         {
1387                 ExceptionStatement stmt;
1388                 UsageVector current_vector;
1389                 UsageVector catch_vectors;
1390                 UsageVector finally_vector;
1391                 UsageVector finally_origins;
1392                 bool emit_finally;
1393
1394                 public FlowBranchingException (FlowBranching parent,
1395                                                ExceptionStatement stmt)
1396                         : base (parent, BranchingType.Exception, SiblingType.Try,
1397                                 null, stmt.loc)
1398                 {
1399                         this.stmt = stmt;
1400                         this.emit_finally = true;
1401                 }
1402
1403                 protected override void AddSibling (UsageVector sibling)
1404                 {
1405                         if (sibling.Type == SiblingType.Try) {
1406                                 sibling.Next = catch_vectors;
1407                                 catch_vectors = sibling;
1408                         } else if (sibling.Type == SiblingType.Catch) {
1409                                 sibling.Next = catch_vectors;
1410                                 catch_vectors = sibling;
1411                         } else if (sibling.Type == SiblingType.Finally) {
1412                                 sibling.MergeFinallyOrigins (finally_origins);
1413                                 finally_vector = sibling;
1414                         } else
1415                                 throw new InvalidOperationException ();
1416
1417                         current_vector = sibling;
1418                 }
1419
1420                 public override UsageVector CurrentUsageVector {
1421                         get { return current_vector; }
1422                 }
1423
1424                 public override bool InTryOrCatch (bool is_return)
1425                 {
1426                         return finally_vector == null;
1427                 }
1428
1429                 public override bool InTryWithCatch ()
1430                 {
1431                         if (finally_vector == null) {
1432                                 Try t = stmt as Try;
1433                                 if (t != null && t.HasCatch)
1434                                         return true;
1435                         }
1436
1437                         if (Parent != null)
1438                                 return Parent.InTryWithCatch ();
1439
1440                         return false;
1441                 }
1442
1443                 public override bool BreakCrossesTryCatchBoundary ()
1444                 {
1445                         return true;
1446                 }
1447
1448                 public override void AddFinallyVector (UsageVector vector)
1449                 {
1450                         vector = vector.Clone ();
1451                         vector.Next = finally_origins;
1452                         finally_origins = vector;
1453                 }
1454
1455                 public override void StealFinallyClauses (ref ArrayList list)
1456                 {
1457                         if (list == null)
1458                                 list = new ArrayList ();
1459                         list.Add (stmt);
1460                         emit_finally = false;
1461                         base.StealFinallyClauses (ref list);
1462                 }
1463
1464                 public bool EmitFinally {
1465                         get { return emit_finally; }
1466                 }
1467
1468                 public override LabeledStatement LookupLabel (string name, Location loc)
1469                 {
1470                         if (current_vector.Block == null)
1471                                 return base.LookupLabel (name, loc);
1472
1473                         LabeledStatement s = current_vector.Block.LookupLabel (name);
1474                         if (s != null)
1475                                 return s;
1476
1477                         if (finally_vector != null) {
1478                                 Report.Error (157, loc,
1479                                         "Control cannot leave the body of a finally clause");
1480                                 return null;
1481                         }
1482
1483                         return base.LookupLabel (name, loc);
1484                 }
1485
1486                 public override void Label (UsageVector origin_vectors)
1487                 {
1488                         CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1489                 }
1490
1491                 protected override UsageVector Merge ()
1492                 {
1493                         UsageVector vector = Merge (catch_vectors);
1494
1495                         vector.MergeFinally (this, finally_vector, finally_origins);
1496
1497                         return vector;
1498                 }
1499         }
1500
1501         // <summary>
1502         //   This is used by the flow analysis code to keep track of the type of local variables
1503         //   and variables.
1504         //
1505         //   The flow code uses a BitVector to keep track of whether a variable has been assigned
1506         //   or not.  This is easy for fundamental types (int, char etc.) or reference types since
1507         //   you can only assign the whole variable as such.
1508         //
1509         //   For structs, we also need to keep track of all its fields.  To do this, we allocate one
1510         //   bit for the struct itself (it's used if you assign/access the whole struct) followed by
1511         //   one bit for each of its fields.
1512         //
1513         //   This class computes this `layout' for each type.
1514         // </summary>
1515         public class TypeInfo
1516         {
1517                 public readonly Type Type;
1518
1519                 // <summary>
1520                 //   Total number of bits a variable of this type consumes in the flow vector.
1521                 // </summary>
1522                 public readonly int TotalLength;
1523
1524                 // <summary>
1525                 //   Number of bits the simple fields of a variable of this type consume
1526                 //   in the flow vector.
1527                 // </summary>
1528                 public readonly int Length;
1529
1530                 // <summary>
1531                 //   This is only used by sub-structs.
1532                 // </summary>
1533                 public readonly int Offset;
1534
1535                 // <summary>
1536                 //   If this is a struct.
1537                 // </summary>
1538                 public readonly bool IsStruct;
1539
1540                 // <summary>
1541                 //   If this is a struct, all fields which are structs theirselves.
1542                 // </summary>
1543                 public TypeInfo[] SubStructInfo;
1544
1545                 protected readonly StructInfo struct_info;
1546                 private static Hashtable type_hash = new Hashtable ();
1547
1548                 public static TypeInfo GetTypeInfo (Type type)
1549                 {
1550                         TypeInfo info = (TypeInfo) type_hash [type];
1551                         if (info != null)
1552                                 return info;
1553
1554                         info = new TypeInfo (type);
1555                         type_hash.Add (type, info);
1556                         return info;
1557                 }
1558
1559                 public static TypeInfo GetTypeInfo (TypeContainer tc)
1560                 {
1561                         TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1562                         if (info != null)
1563                                 return info;
1564
1565                         info = new TypeInfo (tc);
1566                         type_hash.Add (tc.TypeBuilder, info);
1567                         return info;
1568                 }
1569
1570                 private TypeInfo (Type type)
1571                 {
1572                         this.Type = type;
1573
1574                         struct_info = StructInfo.GetStructInfo (type);
1575                         if (struct_info != null) {
1576                                 Length = struct_info.Length;
1577                                 TotalLength = struct_info.TotalLength;
1578                                 SubStructInfo = struct_info.StructFields;
1579                                 IsStruct = true;
1580                         } else {
1581                                 Length = 0;
1582                                 TotalLength = 1;
1583                                 IsStruct = false;
1584                         }
1585                 }
1586
1587                 private TypeInfo (TypeContainer tc)
1588                 {
1589                         this.Type = tc.TypeBuilder;
1590
1591                         struct_info = StructInfo.GetStructInfo (tc);
1592                         if (struct_info != null) {
1593                                 Length = struct_info.Length;
1594                                 TotalLength = struct_info.TotalLength;
1595                                 SubStructInfo = struct_info.StructFields;
1596                                 IsStruct = true;
1597                         } else {
1598                                 Length = 0;
1599                                 TotalLength = 1;
1600                                 IsStruct = false;
1601                         }
1602                 }
1603
1604                 protected TypeInfo (StructInfo struct_info, int offset)
1605                 {
1606                         this.struct_info = struct_info;
1607                         this.Offset = offset;
1608                         this.Length = struct_info.Length;
1609                         this.TotalLength = struct_info.TotalLength;
1610                         this.SubStructInfo = struct_info.StructFields;
1611                         this.Type = struct_info.Type;
1612                         this.IsStruct = true;
1613                 }
1614
1615                 public int GetFieldIndex (string name)
1616                 {
1617                         if (struct_info == null)
1618                                 return 0;
1619
1620                         return struct_info [name];
1621                 }
1622
1623                 public TypeInfo GetSubStruct (string name)
1624                 {
1625                         if (struct_info == null)
1626                                 return null;
1627
1628                         return struct_info.GetStructField (name);
1629                 }
1630
1631                 // <summary>
1632                 //   A struct's constructor must always assign all fields.
1633                 //   This method checks whether it actually does so.
1634                 // </summary>
1635                 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1636                 {
1637                         if (struct_info == null)
1638                                 return true;
1639
1640                         bool ok = true;
1641                         for (int i = 0; i < struct_info.Count; i++) {
1642                                 FieldInfo field = struct_info.Fields [i];
1643
1644                                 if (!branching.IsFieldAssigned (vi, field.Name)) {
1645                                         Report.Error (171, loc,
1646                                                 "Field `{0}' must be fully assigned before control leaves the constructor",
1647                                                 TypeManager.GetFullNameSignature (field));
1648                                         ok = false;
1649                                 }
1650                         }
1651
1652                         return ok;
1653                 }
1654
1655                 public override string ToString ()
1656                 {
1657                         return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1658                                               Type, Offset, Length, TotalLength);
1659                 }
1660
1661                 protected class StructInfo {
1662                         public readonly Type Type;
1663                         public readonly FieldInfo[] Fields;
1664                         public readonly TypeInfo[] StructFields;
1665                         public readonly int Count;
1666                         public readonly int CountPublic;
1667                         public readonly int CountNonPublic;
1668                         public readonly int Length;
1669                         public readonly int TotalLength;
1670                         public readonly bool HasStructFields;
1671
1672                         private static Hashtable field_type_hash = new Hashtable ();
1673                         private Hashtable struct_field_hash;
1674                         private Hashtable field_hash;
1675
1676                         protected bool InTransit = false;
1677
1678                         // Private constructor.  To save memory usage, we only need to create one instance
1679                         // of this class per struct type.
1680                         private StructInfo (Type type)
1681                         {
1682                                 this.Type = type;
1683
1684                                 field_type_hash.Add (type, this);
1685
1686                                 if (type is TypeBuilder) {
1687                                         TypeContainer tc = TypeManager.LookupTypeContainer (type);
1688
1689                                         ArrayList fields = null;
1690                                         if (tc != null)
1691                                                 fields = tc.Fields;
1692
1693                                         ArrayList public_fields = new ArrayList ();
1694                                         ArrayList non_public_fields = new ArrayList ();
1695
1696                                         if (fields != null) {
1697                                                 foreach (FieldMember field in fields) {
1698                                                         if ((field.ModFlags & Modifiers.STATIC) != 0)
1699                                                                 continue;
1700                                                         if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1701                                                                 public_fields.Add (field.FieldBuilder);
1702                                                         else
1703                                                                 non_public_fields.Add (field.FieldBuilder);
1704                                                 }
1705                                         }
1706
1707                                         CountPublic = public_fields.Count;
1708                                         CountNonPublic = non_public_fields.Count;
1709                                         Count = CountPublic + CountNonPublic;
1710
1711                                         Fields = new FieldInfo [Count];
1712                                         public_fields.CopyTo (Fields, 0);
1713                                         non_public_fields.CopyTo (Fields, CountPublic);
1714                                 } else {
1715                                         FieldInfo[] public_fields = type.GetFields (
1716                                                 BindingFlags.Instance|BindingFlags.Public);
1717                                         FieldInfo[] non_public_fields = type.GetFields (
1718                                                 BindingFlags.Instance|BindingFlags.NonPublic);
1719
1720                                         CountPublic = public_fields.Length;
1721                                         CountNonPublic = non_public_fields.Length;
1722                                         Count = CountPublic + CountNonPublic;
1723
1724                                         Fields = new FieldInfo [Count];
1725                                         public_fields.CopyTo (Fields, 0);
1726                                         non_public_fields.CopyTo (Fields, CountPublic);
1727                                 }
1728
1729                                 struct_field_hash = new Hashtable ();
1730                                 field_hash = new Hashtable ();
1731
1732                                 Length = 0;
1733                                 StructFields = new TypeInfo [Count];
1734                                 StructInfo[] sinfo = new StructInfo [Count];
1735
1736                                 InTransit = true;
1737
1738                                 for (int i = 0; i < Count; i++) {
1739                                         FieldInfo field = (FieldInfo) Fields [i];
1740
1741                                         sinfo [i] = GetStructInfo (field.FieldType);
1742                                         if (sinfo [i] == null)
1743                                                 field_hash.Add (field.Name, ++Length);
1744                                         else if (sinfo [i].InTransit) {
1745                                                 Report.Error (523, String.Format (
1746                                                                       "Struct member `{0}.{1}' of type `{2}' causes " +
1747                                                                       "a cycle in the structure layout",
1748                                                                       type, field.Name, sinfo [i].Type));
1749                                                 sinfo [i] = null;
1750                                                 return;
1751                                         }
1752                                 }
1753
1754                                 InTransit = false;
1755
1756                                 TotalLength = Length + 1;
1757                                 for (int i = 0; i < Count; i++) {
1758                                         FieldInfo field = (FieldInfo) Fields [i];
1759
1760                                         if (sinfo [i] == null)
1761                                                 continue;
1762
1763                                         field_hash.Add (field.Name, TotalLength);
1764
1765                                         HasStructFields = true;
1766                                         StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1767                                         struct_field_hash.Add (field.Name, StructFields [i]);
1768                                         TotalLength += sinfo [i].TotalLength;
1769                                 }
1770                         }
1771
1772                         public int this [string name] {
1773                                 get {
1774                                         if (field_hash.Contains (name))
1775                                                 return (int) field_hash [name];
1776                                         else
1777                                                 return 0;
1778                                 }
1779                         }
1780
1781                         public TypeInfo GetStructField (string name)
1782                         {
1783                                 return (TypeInfo) struct_field_hash [name];
1784                         }
1785
1786                         public static StructInfo GetStructInfo (Type type)
1787                         {
1788                                 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1789                                     TypeManager.IsBuiltinType (type))
1790                                         return null;
1791
1792                                 StructInfo info = (StructInfo) field_type_hash [type];
1793                                 if (info != null)
1794                                         return info;
1795
1796                                 return new StructInfo (type);
1797                         }
1798
1799                         public static StructInfo GetStructInfo (TypeContainer tc)
1800                         {
1801                                 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1802                                 if (info != null)
1803                                         return info;
1804
1805                                 return new StructInfo (tc.TypeBuilder);
1806                         }
1807                 }
1808         }
1809
1810         // <summary>
1811         //   This is used by the flow analysis code to store information about a single local variable
1812         //   or parameter.  Depending on the variable's type, we need to allocate one or more elements
1813         //   in the BitVector - if it's a fundamental or reference type, we just need to know whether
1814         //   it has been assigned or not, but for structs, we need this information for each of its fields.
1815         // </summary>
1816         public class VariableInfo {
1817                 public readonly string Name;
1818                 public readonly TypeInfo TypeInfo;
1819
1820                 // <summary>
1821                 //   The bit offset of this variable in the flow vector.
1822                 // </summary>
1823                 public readonly int Offset;
1824
1825                 // <summary>
1826                 //   The number of bits this variable needs in the flow vector.
1827                 //   The first bit always specifies whether the variable as such has been assigned while
1828                 //   the remaining bits contain this information for each of a struct's fields.
1829                 // </summary>
1830                 public readonly int Length;
1831
1832                 // <summary>
1833                 //   If this is a parameter of local variable.
1834                 // </summary>
1835                 public readonly bool IsParameter;
1836
1837                 public readonly LocalInfo LocalInfo;
1838                 public readonly int ParameterIndex;
1839
1840                 readonly VariableInfo Parent;
1841                 VariableInfo[] sub_info;
1842
1843                 protected VariableInfo (string name, Type type, int offset)
1844                 {
1845                         this.Name = name;
1846                         this.Offset = offset;
1847                         this.TypeInfo = TypeInfo.GetTypeInfo (type);
1848
1849                         Length = TypeInfo.TotalLength;
1850
1851                         Initialize ();
1852                 }
1853
1854                 protected VariableInfo (VariableInfo parent, TypeInfo type)
1855                 {
1856                         this.Name = parent.Name;
1857                         this.TypeInfo = type;
1858                         this.Offset = parent.Offset + type.Offset;
1859                         this.Parent = parent;
1860                         this.Length = type.TotalLength;
1861
1862                         this.IsParameter = parent.IsParameter;
1863                         this.LocalInfo = parent.LocalInfo;
1864                         this.ParameterIndex = parent.ParameterIndex;
1865
1866                         Initialize ();
1867                 }
1868
1869                 protected void Initialize ()
1870                 {
1871                         TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1872                         if (sub_fields != null) {
1873                                 sub_info = new VariableInfo [sub_fields.Length];
1874                                 for (int i = 0; i < sub_fields.Length; i++) {
1875                                         if (sub_fields [i] != null)
1876                                                 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1877                                 }
1878                         } else
1879                                 sub_info = new VariableInfo [0];
1880                 }
1881
1882                 public VariableInfo (LocalInfo local_info, int offset)
1883                         : this (local_info.Name, local_info.VariableType, offset)
1884                 {
1885                         this.LocalInfo = local_info;
1886                         this.IsParameter = false;
1887                 }
1888
1889                 public VariableInfo (string name, Type type, int param_idx, int offset)
1890                         : this (name, type, offset)
1891                 {
1892                         this.ParameterIndex = param_idx;
1893                         this.IsParameter = true;
1894                 }
1895
1896                 public bool IsAssigned (EmitContext ec)
1897                 {
1898                         return !ec.DoFlowAnalysis || ec.CurrentBranching.IsAssigned (this);
1899                 }
1900
1901                 public bool IsAssigned (EmitContext ec, Location loc)
1902                 {
1903                         if (IsAssigned (ec))
1904                                 return true;
1905
1906                         Report.Error (165, loc,
1907                                       "Use of unassigned local variable `" + Name + "'");
1908                         ec.CurrentBranching.SetAssigned (this);
1909                         return false;
1910                 }
1911
1912                 public bool IsAssigned (MyBitVector vector)
1913                 {
1914                         if (vector [Offset])
1915                                 return true;
1916
1917                         for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1918                                 if (vector [parent.Offset])
1919                                         return true;
1920
1921                         // Return unless this is a struct.
1922                         if (!TypeInfo.IsStruct)
1923                                 return false;
1924
1925                         // Ok, so each field must be assigned.
1926                         for (int i = 0; i < TypeInfo.Length; i++) {
1927                                 if (!vector [Offset + i + 1])
1928                                         return false;
1929                         }
1930
1931                         // Ok, now check all fields which are structs.
1932                         for (int i = 0; i < sub_info.Length; i++) {
1933                                 VariableInfo sinfo = sub_info [i];
1934                                 if (sinfo == null)
1935                                         continue;
1936
1937                                 if (!sinfo.IsAssigned (vector))
1938                                         return false;
1939                         }
1940
1941                         vector [Offset] = true;
1942                         return true;
1943                 }
1944
1945                 public void SetAssigned (EmitContext ec)
1946                 {
1947                         if (ec.DoFlowAnalysis)
1948                                 ec.CurrentBranching.SetAssigned (this);
1949                 }
1950
1951                 public void SetAssigned (MyBitVector vector)
1952                 {
1953                         vector [Offset] = true;
1954                 }
1955
1956                 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1957                 {
1958                         if (!ec.DoFlowAnalysis || ec.CurrentBranching.IsFieldAssigned (this, name))
1959                                 return true;
1960
1961                         Report.Error (170, loc,
1962                                       "Use of possibly unassigned field `" + name + "'");
1963                         ec.CurrentBranching.SetFieldAssigned (this, name);
1964                         return false;
1965                 }
1966
1967                 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1968                 {
1969                         int field_idx = TypeInfo.GetFieldIndex (field_name);
1970
1971                         if (field_idx == 0)
1972                                 return true;
1973
1974                         return vector [Offset + field_idx];
1975                 }
1976
1977                 public void SetFieldAssigned (EmitContext ec, string name)
1978                 {
1979                         if (ec.DoFlowAnalysis)
1980                                 ec.CurrentBranching.SetFieldAssigned (this, name);
1981                 }
1982
1983                 public void SetFieldAssigned (MyBitVector vector, string field_name)
1984                 {
1985                         int field_idx = TypeInfo.GetFieldIndex (field_name);
1986
1987                         if (field_idx == 0)
1988                                 return;
1989
1990                         vector [Offset + field_idx] = true;
1991                 }
1992
1993                 public VariableInfo GetSubStruct (string name)
1994                 {
1995                         TypeInfo type = TypeInfo.GetSubStruct (name);
1996
1997                         if (type == null)
1998                                 return null;
1999
2000                         return new VariableInfo (this, type);
2001                 }
2002
2003                 public override string ToString ()
2004                 {
2005                         return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
2006                                               Name, TypeInfo, Offset, Length, IsParameter);
2007                 }
2008         }
2009
2010         // <summary>
2011         //   This is used by the flow code to hold the `layout' of the flow vector for
2012         //   all locals and all parameters (ie. we create one instance of this class for the
2013         //   locals and another one for the params).
2014         // </summary>
2015         public class VariableMap {
2016                 // <summary>
2017                 //   The number of variables in the map.
2018                 // </summary>
2019                 public readonly int Count;
2020
2021                 // <summary>
2022                 //   Total length of the flow vector for this map.
2023                 // <summary>
2024                 public readonly int Length;
2025
2026                 VariableInfo[] map;
2027
2028                 public VariableMap (InternalParameters ip)
2029                 {
2030                         Count = ip != null ? ip.Count : 0;
2031
2032                         // Dont bother allocating anything!
2033                         if (Count == 0)
2034                                 return;
2035
2036                         Length = 0;
2037
2038                         for (int i = 0; i < Count; i++) {
2039                                 Parameter.Modifier mod = ip.ParameterModifier (i);
2040
2041                                 if ((mod & Parameter.Modifier.OUT) == 0)
2042                                         continue;
2043
2044                                 // Dont allocate till we find an out var.
2045                                 if (map == null)
2046                                         map = new VariableInfo [Count];
2047
2048                                 map [i] = new VariableInfo (ip.ParameterName (i),
2049                                         TypeManager.GetElementType (ip.ParameterType (i)), i, Length);
2050
2051                                 Length += map [i].Length;
2052                         }
2053                 }
2054
2055                 public VariableMap (LocalInfo[] locals)
2056                         : this (null, locals)
2057                 { }
2058
2059                 public VariableMap (VariableMap parent, LocalInfo[] locals)
2060                 {
2061                         int offset = 0, start = 0;
2062                         if (parent != null && parent.map != null) {
2063                                 offset = parent.Length;
2064                                 start = parent.Count;
2065                         }
2066
2067                         Count = locals.Length + start;
2068
2069                         if (Count == 0)
2070                                 return;
2071
2072                         map = new VariableInfo [Count];
2073                         Length = offset;
2074
2075                         if (parent != null && parent.map != null) {
2076                                 parent.map.CopyTo (map, 0);
2077                         }
2078
2079                         for (int i = start; i < Count; i++) {
2080                                 LocalInfo li = locals [i-start];
2081
2082                                 if (li.VariableType == null)
2083                                         continue;
2084
2085                                 map [i] = li.VariableInfo = new VariableInfo (li, Length);
2086                                 Length += map [i].Length;
2087                         }
2088                 }
2089
2090                 // <summary>
2091                 //   Returns the VariableInfo for variable @index or null if we don't need to
2092                 //   compute assignment info for this variable.
2093                 // </summary>
2094                 public VariableInfo this [int index] {
2095                         get {
2096                                 if (map == null)
2097                                         return null;
2098
2099                                 return map [index];
2100                         }
2101                 }
2102
2103                 public override string ToString ()
2104                 {
2105                         return String.Format ("VariableMap ({0}:{1})", Count, Length);
2106                 }
2107         }
2108
2109         // <summary>
2110         //   This is a special bit vector which can inherit from another bit vector doing a
2111         //   copy-on-write strategy.  The inherited vector may have a smaller size than the
2112         //   current one.
2113         // </summary>
2114         public class MyBitVector {
2115                 public readonly int Count;
2116                 public readonly MyBitVector InheritsFrom;
2117
2118                 bool is_dirty;
2119                 BitArray vector;
2120
2121                 public MyBitVector (int Count)
2122                         : this (null, Count)
2123                 { }
2124
2125                 public MyBitVector (MyBitVector InheritsFrom, int Count)
2126                 {
2127                         this.InheritsFrom = InheritsFrom;
2128                         this.Count = Count;
2129                 }
2130
2131                 // <summary>
2132                 //   Checks whether this bit vector has been modified.  After setting this to true,
2133                 //   we won't use the inherited vector anymore, but our own copy of it.
2134                 // </summary>
2135                 public bool IsDirty {
2136                         get {
2137                                 return is_dirty;
2138                         }
2139
2140                         set {
2141                                 if (!is_dirty)
2142                                         initialize_vector ();
2143                         }
2144                 }
2145
2146                 // <summary>
2147                 //   Get/set bit `index' in the bit vector.
2148                 // </summary>
2149                 public bool this [int index]
2150                 {
2151                         get {
2152                                 if (index > Count)
2153                                         throw new ArgumentOutOfRangeException ();
2154
2155                                 // We're doing a "copy-on-write" strategy here; as long
2156                                 // as nobody writes to the array, we can use our parent's
2157                                 // copy instead of duplicating the vector.
2158
2159                                 if (vector != null)
2160                                         return vector [index];
2161                                 else if (InheritsFrom != null) {
2162                                         BitArray inherited = InheritsFrom.Vector;
2163
2164                                         if (index < inherited.Count)
2165                                                 return inherited [index];
2166                                         else
2167                                                 return false;
2168                                 } else
2169                                         return false;
2170                         }
2171
2172                         set {
2173                                 if (index > Count)
2174                                         throw new ArgumentOutOfRangeException ();
2175
2176                                 // Only copy the vector if we're actually modifying it.
2177
2178                                 if (this [index] != value) {
2179                                         initialize_vector ();
2180
2181                                         vector [index] = value;
2182                                 }
2183                         }
2184                 }
2185
2186                 // <summary>
2187                 //   If you explicitly convert the MyBitVector to a BitArray, you will get a deep
2188                 //   copy of the bit vector.
2189                 // </summary>
2190                 public static explicit operator BitArray (MyBitVector vector)
2191                 {
2192                         vector.initialize_vector ();
2193                         return vector.Vector;
2194                 }
2195
2196                 // <summary>
2197                 //   Performs an `or' operation on the bit vector.  The `new_vector' may have a
2198                 //   different size than the current one.
2199                 // </summary>
2200                 public void Or (MyBitVector new_vector)
2201                 {
2202                         BitArray new_array = new_vector.Vector;
2203
2204                         initialize_vector ();
2205
2206                         int upper;
2207                         if (vector.Count < new_array.Count)
2208                                 upper = vector.Count;
2209                         else
2210                                 upper = new_array.Count;
2211
2212                         for (int i = 0; i < upper; i++)
2213                                 vector [i] = vector [i] | new_array [i];
2214                 }
2215
2216                 // <summary>
2217                 //   Perfonrms an `and' operation on the bit vector.  The `new_vector' may have
2218                 //   a different size than the current one.
2219                 // </summary>
2220                 public void And (MyBitVector new_vector)
2221                 {
2222                         BitArray new_array;
2223
2224                         if (new_vector != null)
2225                                 new_array = new_vector.Vector;
2226                         else
2227                                 new_array = new BitArray (Count, false);
2228
2229                         initialize_vector ();
2230
2231                         int lower, upper;
2232                         if (vector.Count < new_array.Count)
2233                                 lower = upper = vector.Count;
2234                         else {
2235                                 lower = new_array.Count;
2236                                 upper = vector.Count;
2237                         }
2238
2239                         for (int i = 0; i < lower; i++)
2240                                 vector [i] = vector [i] & new_array [i];
2241
2242                         for (int i = lower; i < upper; i++)
2243                                 vector [i] = false;
2244                 }
2245
2246                 public static void And (ref MyBitVector target, MyBitVector vector)
2247                 {
2248                         if (target != null)
2249                                 target.And (vector);
2250                         else
2251                                 target = vector.Clone ();
2252                 }
2253
2254                 public static void Or (ref MyBitVector target, MyBitVector vector)
2255                 {
2256                         if (target != null)
2257                                 target.Or (vector);
2258                         else
2259                                 target = vector.Clone ();
2260                 }
2261
2262                 // <summary>
2263                 //   This does a deep copy of the bit vector.
2264                 // </summary>
2265                 public MyBitVector Clone ()
2266                 {
2267                         MyBitVector retval = new MyBitVector (Count);
2268
2269                         retval.Vector = Vector;
2270
2271                         return retval;
2272                 }
2273
2274                 BitArray Vector {
2275                         get {
2276                                 if (vector != null)
2277                                         return vector;
2278                                 else if (!is_dirty && (InheritsFrom != null))
2279                                         return InheritsFrom.Vector;
2280
2281                                 initialize_vector ();
2282
2283                                 return vector;
2284                         }
2285
2286                         set {
2287                                 initialize_vector ();
2288
2289                                 for (int i = 0; i < System.Math.Min (vector.Count, value.Count); i++)
2290                                         vector [i] = value [i];
2291                         }
2292                 }
2293
2294                 void initialize_vector ()
2295                 {
2296                         if (vector != null)
2297                                 return;
2298
2299                         vector = new BitArray (Count, false);
2300                         if (InheritsFrom != null)
2301                                 Vector = InheritsFrom.Vector;
2302
2303                         is_dirty = true;
2304                 }
2305
2306                 public override string ToString ()
2307                 {
2308                         StringBuilder sb = new StringBuilder ("{");
2309
2310                         BitArray vector = Vector;
2311                         if (!IsDirty)
2312                                 sb.Append ("=");
2313                         for (int i = 0; i < vector.Count; i++) {
2314                                 sb.Append (vector [i] ? "1" : "0");
2315                         }
2316
2317                         sb.Append ("}");
2318                         return sb.ToString ();
2319                 }
2320         }
2321 }