mcs/mcs/flowanalysis.cs

   1 //
   2 // flowanalyis.cs: The control flow analysis code
   3 //
   4 // Author:
   5 //   Martin Baulig (martin@ximian.com)
   6 //   Raja R Harinath (rharinath@novell.com)
   7 //
   8 // (C) 2001, 2002, 2003 Ximian, Inc.
   9 //
  10
  11 using System;
  12 using System.Text;
  13 using System.Collections;
  14 using System.Reflection;
  15 using System.Reflection.Emit;
  16 using System.Diagnostics;
  17
  18 namespace Mono.CSharp
  19 {
  20         // <summary>
  21         //   A new instance of this class is created every time a new block is resolved
  22         //   and if there's branching in the block's control flow.
  23         // </summary>
  24         public abstract class FlowBranching
  25         {
  26                 // <summary>
  27                 //   The type of a FlowBranching.
  28                 // </summary>
  29                 public enum BranchingType : byte {
  30                         // Normal (conditional or toplevel) block.
  31                         Block,
  32
  33                         // Conditional.
  34                         Conditional,
  35
  36                         // A loop block.
  37                         Loop,
  38
  39                         // The statement embedded inside a loop
  40                         Embedded,
  41
  42                         // part of a block headed by a jump target
  43                         Labeled,
  44
  45                         // TryCatch block.
  46                         TryCatch,
  47
  48                         // TryFinally, Using, Lock, CollectionForeach
  49                         Exception,
  50
  51                         // Switch block.
  52                         Switch,
  53
  54                         // The toplevel block of a function
  55                         Toplevel
  56                 }
  57
  58                 // <summary>
  59                 //   The type of one sibling of a branching.
  60                 // </summary>
  61                 public enum SiblingType : byte {
  62                         Block,
  63                         Conditional,
  64                         SwitchSection,
  65                         Try,
  66                         Catch,
  67                         Finally
  68                 }
  69
  70                 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
  71                 {
  72                         switch (type) {
  73                         case BranchingType.Exception:
  74                         case BranchingType.Labeled:
  75                         case BranchingType.Toplevel:
  76                                 throw new InvalidOperationException ();
  77
  78                         case BranchingType.Switch:
  79                                 return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
  80
  81                         case BranchingType.Block:
  82                                 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
  83
  84                         case BranchingType.Loop:
  85                                 return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
  86
  87                         case BranchingType.Embedded:
  88                                 return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
  89
  90                         case BranchingType.TryCatch:
  91                                 return new FlowBranchingTryCatch (parent, loc);
  92
  93                         default:
  94                                 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
  95                         }
  96                 }
  97
  98                 // <summary>
  99                 //   The type of this flow branching.
 100                 // </summary>
 101                 public readonly BranchingType Type;
 102
 103                 // <summary>
 104                 //   The block this branching is contained in.  This may be null if it's not
 105                 //   a top-level block and it doesn't declare any local variables.
 106                 // </summary>
 107                 public readonly Block Block;
 108
 109                 // <summary>
 110                 //   The parent of this branching or null if this is the top-block.
 111                 // </summary>
 112                 public readonly FlowBranching Parent;
 113
 114                 // <summary>
 115                 //   Start-Location of this flow branching.
 116                 // </summary>
 117                 public readonly Location Location;
 118
 119                 static int next_id = 0;
 120                 int id;
 121
 122                 // <summary>
 123                 //   The vector contains a BitArray with information about which local variables
 124                 //   and parameters are already initialized at the current code position.
 125                 // </summary>
 126                 public class UsageVector {
 127                         // <summary>
 128                         //   The type of this branching.
 129                         // </summary>
 130                         public readonly SiblingType Type;
 131
 132                         // <summary>
 133                         //   Start location of this branching.
 134                         // </summary>
 135                         public Location Location;
 136
 137                         // <summary>
 138                         //   This is only valid for SwitchSection, Try, Catch and Finally.
 139                         // </summary>
 140                         public readonly Block Block;
 141
 142                         // <summary>
 143                         //   The number of locals in this block.
 144                         // </summary>
 145                         public readonly int CountLocals;
 146
 147                         // <summary>
 148                         //   If not null, then we inherit our state from this vector and do a
 149                         //   copy-on-write.  If null, then we're the first sibling in a top-level
 150                         //   block and inherit from the empty vector.
 151                         // </summary>
 152                         public readonly UsageVector InheritsFrom;
 153
 154                         // <summary>
 155                         //   This is used to construct a list of UsageVector's.
 156                         // </summary>
 157                         public UsageVector Next;
 158
 159                         //
 160                         // Private.
 161                         //
 162                         MyBitVector locals;
 163                         bool is_unreachable;
 164
 165                         static int next_id = 0;
 166                         int id;
 167
 168                         //
 169                         // Normally, you should not use any of these constructors.
 170                         //
 171                         public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc, int num_locals)
 172                         {
 173                                 this.Type = type;
 174                                 this.Block = block;
 175                                 this.Location = loc;
 176                                 this.InheritsFrom = parent;
 177                                 this.CountLocals = num_locals;
 178
 179                                 locals = num_locals == 0
 180                                         ? MyBitVector.Empty
 181                                         : new MyBitVector (parent == null ? MyBitVector.Empty : parent.locals, num_locals);
 182
 183                                 if (parent != null)
 184                                         is_unreachable = parent.is_unreachable;
 185
 186                                 id = ++next_id;
 187
 188                         }
 189
 190                         public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
 191                                 : this (type, parent, block, loc, parent.CountLocals)
 192                         { }
 193
 194                         private UsageVector (MyBitVector locals, bool is_unreachable, Block block, Location loc)
 195                         {
 196                                 this.Type = SiblingType.Block;
 197                                 this.Location = loc;
 198                                 this.Block = block;
 199
 200                                 this.is_unreachable = is_unreachable;
 201
 202                                 this.locals = locals;
 203
 204                                 id = ++next_id;
 205
 206                         }
 207
 208                         // <summary>
 209                         //   This does a deep copy of the usage vector.
 210                         // </summary>
 211                         public UsageVector Clone ()
 212                         {
 213                                 UsageVector retval = new UsageVector (Type, null, Block, Location, CountLocals);
 214
 215                                 retval.locals = locals.Clone ();
 216                                 retval.is_unreachable = is_unreachable;
 217
 218                                 return retval;
 219                         }
 220
 221                         public bool IsAssigned (VariableInfo var, bool ignoreReachability)
 222                         {
 223                                 if (!ignoreReachability && !var.IsParameter && IsUnreachable)
 224                                         return true;
 225
 226                                 return var.IsAssigned (locals);
 227                         }
 228
 229                         public void SetAssigned (VariableInfo var)
 230                         {
 231                                 if (!var.IsParameter && IsUnreachable)
 232                                         return;
 233
 234                                 var.SetAssigned (locals);
 235                         }
 236
 237                         public bool IsFieldAssigned (VariableInfo var, string name)
 238                         {
 239                                 if (!var.IsParameter && IsUnreachable)
 240                                         return true;
 241
 242                                 return var.IsFieldAssigned (locals, name);
 243                         }
 244
 245                         public void SetFieldAssigned (VariableInfo var, string name)
 246                         {
 247                                 if (!var.IsParameter && IsUnreachable)
 248                                         return;
 249
 250                                 var.SetFieldAssigned (locals, name);
 251                         }
 252
 253                         public bool IsUnreachable {
 254                                 get { return is_unreachable; }
 255                         }
 256
 257                         public void ResetBarrier ()
 258                         {
 259                                 is_unreachable = false;
 260                         }
 261
 262                         public void Goto ()
 263                         {
 264                                 is_unreachable = true;
 265                         }
 266
 267                         public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
 268                         {
 269                                 if (sibling_list.Next == null)
 270                                         return sibling_list;
 271
 272                                 MyBitVector locals = null;
 273                                 bool is_unreachable = sibling_list.is_unreachable;
 274
 275                                 if (!sibling_list.IsUnreachable)
 276                                         locals &= sibling_list.locals;
 277
 278                                 for (UsageVector child = sibling_list.Next; child != null; child = child.Next) {
 279                                         is_unreachable &= child.is_unreachable;
 280
 281                                         if (!child.IsUnreachable)
 282                                                 locals &= child.locals;
 283                                 }
 284
 285                                 return new UsageVector (locals, is_unreachable, null, loc);
 286                         }
 287
 288                         // <summary>
 289                         //   Merges a child branching.
 290                         // </summary>
 291                         public UsageVector MergeChild (UsageVector child, bool overwrite)
 292                         {
 293                                 Report.Debug (2, "    MERGING CHILD EFFECTS", this, child, Type);
 294
 295                                 bool new_isunr = child.is_unreachable;
 296
 297                                 //
 298                                 // We've now either reached the point after the branching or we will
 299                                 // never get there since we always return or always throw an exception.
 300                                 //
 301                                 // If we can reach the point after the branching, mark all locals and
 302                                 // parameters as initialized which have been initialized in all branches
 303                                 // we need to look at (see above).
 304                                 //
 305
 306                                 if ((Type == SiblingType.SwitchSection) && !new_isunr) {
 307                                         Report.Error (163, Location,
 308                                                       "Control cannot fall through from one " +
 309                                                       "case label to another");
 310                                         return child;
 311                                 }
 312
 313                                 locals |= child.locals;
 314
 315                                 if (overwrite)
 316                                         is_unreachable = new_isunr;
 317                                 else
 318                                         is_unreachable |= new_isunr;
 319
 320                                 return child;
 321                         }
 322
 323                         public void MergeOrigins (UsageVector o_vectors)
 324                         {
 325                                 Report.Debug (1, "  MERGING BREAK ORIGINS", this);
 326
 327                                 if (o_vectors == null)
 328                                         return;
 329
 330                                 if (IsUnreachable && locals != null)
 331                                         locals.SetAll (true);
 332
 333                                 for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
 334                                         Report.Debug (1, "    MERGING BREAK ORIGIN", vector);
 335                                         if (vector.IsUnreachable)
 336                                                 continue;
 337                                         locals &= vector.locals;
 338                                         is_unreachable &= vector.is_unreachable;
 339                                 }
 340
 341                                 Report.Debug (1, "  MERGING BREAK ORIGINS DONE", this);
 342                         }
 343
 344                         //
 345                         // Debugging stuff.
 346                         //
 347
 348                         public override string ToString ()
 349                         {
 350                                 return String.Format ("Vector ({0},{1},{2}-{3})", Type, id, is_unreachable, locals);
 351                         }
 352                 }
 353
 354                 // <summary>
 355                 //   Creates a new flow branching which is contained in `parent'.
 356                 //   You should only pass non-null for the `block' argument if this block
 357                 //   introduces any new variables - in this case, we need to create a new
 358                 //   usage vector with a different size than our parent's one.
 359                 // </summary>
 360                 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
 361                                          Block block, Location loc)
 362                 {
 363                         Parent = parent;
 364                         Block = block;
 365                         Location = loc;
 366                         Type = type;
 367                         id = ++next_id;
 368
 369                         UsageVector vector;
 370                         if (Block != null) {
 371                                 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
 372                                 vector = new UsageVector (stype, parent_vector, Block, loc, Block.AssignableSlots);
 373                         } else {
 374                                 vector = new UsageVector (stype, Parent.CurrentUsageVector, null, loc);
 375                         }
 376
 377                         AddSibling (vector);
 378                 }
 379
 380                 public abstract UsageVector CurrentUsageVector {
 381                         get;
 382                 }
 383
 384                 // <summary>
 385                 //   Creates a sibling of the current usage vector.
 386                 // </summary>
 387                 public virtual void CreateSibling (Block block, SiblingType type)
 388                 {
 389                         UsageVector vector = new UsageVector (
 390                                 type, Parent.CurrentUsageVector, block, Location);
 391                         AddSibling (vector);
 392
 393                         Report.Debug (1, "  CREATED SIBLING", CurrentUsageVector);
 394                 }
 395
 396                 public void CreateSibling ()
 397                 {
 398                         CreateSibling (null, SiblingType.Conditional);
 399                 }
 400
 401                 protected abstract void AddSibling (UsageVector uv);
 402
 403                 protected abstract UsageVector Merge ();
 404
 405                 // <summary>
 406                 //   Merge a child branching.
 407                 // </summary>
 408                 public UsageVector MergeChild (FlowBranching child)
 409                 {
 410                         bool overwrite = false;
 411
 412                         switch (child.Type) {
 413                         case BranchingType.Labeled:
 414                                 overwrite = true;
 415                                 break;
 416                         case BranchingType.Block:
 417                                 if (child.Block != null && child.Block != child.Block.Explicit)
 418                                         overwrite = true;
 419                                 break;
 420                         }
 421
 422                         Report.Debug (2, "  MERGING CHILD", this, child);
 423                         UsageVector result = CurrentUsageVector.MergeChild (child.Merge (), overwrite);
 424                         Report.Debug (2, "  MERGING CHILD DONE", this, result);
 425                         return result;
 426                 }
 427
 428                 public virtual bool InTryWithCatch ()
 429                 {
 430                         return Parent.InTryWithCatch ();
 431                 }
 432
 433                 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 434                 public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
 435                 {
 436                         return Parent.AddBreakOrigin (vector, loc);
 437                 }
 438
 439                 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 440                 public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
 441                 {
 442                         return Parent.AddContinueOrigin (vector, loc);
 443                 }
 444
 445                 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 446                 public virtual bool AddReturnOrigin (UsageVector vector, Location loc)
 447                 {
 448                         return Parent.AddReturnOrigin (vector, loc);
 449                 }
 450
 451                 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 452                 public virtual bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 453                 {
 454                         return Parent.AddGotoOrigin (vector, goto_stmt);
 455                 }
 456
 457                 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 458                 public virtual bool StealFinallyClauses (ref ArrayList list)
 459                 {
 460                         return Parent.StealFinallyClauses (ref list);
 461                 }
 462
 463                 public bool IsAssigned (VariableInfo vi)
 464                 {
 465                         return CurrentUsageVector.IsAssigned (vi, false);
 466                 }
 467
 468                 public bool IsFieldAssigned (VariableInfo vi, string field_name)
 469                 {
 470                         return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
 471                 }
 472
 473                 public void SetAssigned (VariableInfo vi)
 474                 {
 475                         CurrentUsageVector.SetAssigned (vi);
 476                 }
 477
 478                 public void SetFieldAssigned (VariableInfo vi, string name)
 479                 {
 480                         CurrentUsageVector.SetFieldAssigned (vi, name);
 481                 }
 482
 483                 public override string ToString ()
 484                 {
 485                         StringBuilder sb = new StringBuilder ();
 486                         sb.Append (GetType ());
 487                         sb.Append (" (");
 488
 489                         sb.Append (id);
 490                         sb.Append (",");
 491                         sb.Append (Type);
 492                         if (Block != null) {
 493                                 sb.Append (" - ");
 494                                 sb.Append (Block.ID);
 495                                 sb.Append (" - ");
 496                                 sb.Append (Block.StartLocation);
 497                         }
 498                         sb.Append (" - ");
 499                         // sb.Append (Siblings.Length);
 500                         // sb.Append (" - ");
 501                         sb.Append (CurrentUsageVector);
 502                         sb.Append (")");
 503                         return sb.ToString ();
 504                 }
 505
 506                 public string Name {
 507                         get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
 508                 }
 509         }
 510
 511         public class FlowBranchingBlock : FlowBranching
 512         {
 513                 UsageVector sibling_list = null;
 514
 515                 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
 516                                            SiblingType stype, Block block, Location loc)
 517                         : base (parent, type, stype, block, loc)
 518                 { }
 519
 520                 public override UsageVector CurrentUsageVector {
 521                         get { return sibling_list; }
 522                 }
 523
 524                 protected override void AddSibling (UsageVector sibling)
 525                 {
 526                         if (sibling.Type == SiblingType.Block && sibling_list != null)
 527                                 throw new InternalErrorException ("Blocks don't have sibling flow paths");
 528                         sibling.Next = sibling_list;
 529                         sibling_list = sibling;
 530                 }
 531
 532                 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 533                 {
 534                         LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
 535                         if (stmt == null)
 536                                 return Parent.AddGotoOrigin (vector, goto_stmt);
 537
 538                         // forward jump
 539                         goto_stmt.SetResolvedTarget (stmt);
 540                         stmt.AddUsageVector (vector);
 541                         return false;
 542                 }
 543
 544                 public static void Error_UnknownLabel (Location loc, string label)
 545                 {
 546                         Report.Error(159, loc, "The label `{0}:' could not be found within the scope of the goto statement",
 547                                 label);
 548                 }
 549
 550                 protected override UsageVector Merge ()
 551                 {
 552                         Report.Debug (2, "  MERGING SIBLINGS", Name);
 553                         UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
 554                         Report.Debug (2, "  MERGING SIBLINGS DONE", Name, vector);
 555                         return vector;
 556                 }
 557         }
 558
 559         public class FlowBranchingBreakable : FlowBranchingBlock
 560         {
 561                 UsageVector break_origins;
 562
 563                 public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
 564                         : base (parent, type, stype, block, loc)
 565                 { }
 566
 567                 public override bool AddBreakOrigin (UsageVector vector, Location loc)
 568                 {
 569                         vector = vector.Clone ();
 570                         vector.Next = break_origins;
 571                         break_origins = vector;
 572                         return false;
 573                 }
 574
 575                 protected override UsageVector Merge ()
 576                 {
 577                         UsageVector vector = base.Merge ();
 578                         vector.MergeOrigins (break_origins);
 579                         return vector;
 580                 }
 581         }
 582
 583         public class FlowBranchingContinuable : FlowBranchingBlock
 584         {
 585                 UsageVector continue_origins;
 586
 587                 public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
 588                         : base (parent, type, stype, block, loc)
 589                 { }
 590
 591                 public override bool AddContinueOrigin (UsageVector vector, Location loc)
 592                 {
 593                         vector = vector.Clone ();
 594                         vector.Next = continue_origins;
 595                         continue_origins = vector;
 596                         return false;
 597                 }
 598
 599                 protected override UsageVector Merge ()
 600                 {
 601                         UsageVector vector = base.Merge ();
 602                         vector.MergeOrigins (continue_origins);
 603                         return vector;
 604                 }
 605         }
 606
 607         public class FlowBranchingLabeled : FlowBranchingBlock
 608         {
 609                 LabeledStatement stmt;
 610                 UsageVector actual;
 611
 612                 public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
 613                         : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
 614                 {
 615                         this.stmt = stmt;
 616                         CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
 617                         actual = CurrentUsageVector.Clone ();
 618
 619                         // stand-in for backward jumps
 620                         CurrentUsageVector.ResetBarrier ();
 621                 }
 622
 623                 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 624                 {
 625                         if (goto_stmt.Target != stmt.Name)
 626                                 return Parent.AddGotoOrigin (vector, goto_stmt);
 627
 628                         // backward jump
 629                         goto_stmt.SetResolvedTarget (stmt);
 630                         actual.MergeOrigins (vector.Clone ());
 631
 632                         return false;
 633                 }
 634
 635                 protected override UsageVector Merge ()
 636                 {
 637                         UsageVector vector = base.Merge ();
 638
 639                         if (actual.IsUnreachable)
 640                                 Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
 641
 642                         actual.MergeChild (vector, false);
 643                         return actual;
 644                 }
 645         }
 646
 647         public class FlowBranchingToplevel : FlowBranchingBlock
 648         {
 649                 UsageVector return_origins;
 650
 651                 public FlowBranchingToplevel (FlowBranching parent, ToplevelBlock stmt)
 652                         : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
 653                 {
 654                 }
 655
 656                 public override bool InTryWithCatch ()
 657                 {
 658                         return false;
 659                 }
 660
 661                 public override bool AddBreakOrigin (UsageVector vector, Location loc)
 662                 {
 663                         Report.Error (139, loc, "No enclosing loop out of which to break or continue");
 664                         return false;
 665                 }
 666
 667                 public override bool AddContinueOrigin (UsageVector vector, Location loc)
 668                 {
 669                         Report.Error (139, loc, "No enclosing loop out of which to break or continue");
 670                         return false;
 671                 }
 672
 673                 public override bool AddReturnOrigin (UsageVector vector, Location loc)
 674                 {
 675                         vector = vector.Clone ();
 676                         vector.Location = loc;
 677                         vector.Next = return_origins;
 678                         return_origins = vector;
 679                         return false;
 680                 }
 681
 682                 public override bool StealFinallyClauses (ref ArrayList list)
 683                 {
 684                         return false;
 685                 }
 686
 687                 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 688                 {
 689                         string name = goto_stmt.Target;
 690                         LabeledStatement s = Block.LookupLabel (name);
 691                         if (s != null)
 692                                 throw new InternalErrorException ("Shouldn't get here");
 693
 694                         if (Parent == null) {
 695                                 Error_UnknownLabel (goto_stmt.loc, name);
 696                                 return false;
 697                         }
 698
 699                         int errors = Report.Errors;
 700                         Parent.AddGotoOrigin (vector, goto_stmt);
 701                         if (errors == Report.Errors)
 702                                 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
 703                         return false;
 704                 }
 705
 706                 protected override UsageVector Merge ()
 707                 {
 708                         for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
 709                                 Block.Toplevel.CheckOutParameters (origin, origin.Location);
 710
 711                         UsageVector vector = base.Merge ();
 712                         Block.Toplevel.CheckOutParameters (vector, Block.loc);
 713                         // Note: we _do_not_ merge in the return origins
 714                         return vector;
 715                 }
 716
 717                 public bool End ()
 718                 {
 719                         return Merge ().IsUnreachable;
 720                 }
 721         }
 722
 723         public class FlowBranchingTryCatch : FlowBranchingBlock
 724         {
 725                 public FlowBranchingTryCatch (FlowBranching parent, Location loc)
 726                         : base (parent, BranchingType.Block, SiblingType.Try, null, loc)
 727                 {
 728                 }
 729
 730                 public override bool InTryWithCatch ()
 731                 {
 732                         return true;
 733                 }
 734
 735                 public override bool AddBreakOrigin (UsageVector vector, Location loc)
 736                 {
 737                         Parent.AddBreakOrigin (vector, loc);
 738                         return true;
 739                 }
 740
 741                 public override bool AddContinueOrigin (UsageVector vector, Location loc)
 742                 {
 743                         Parent.AddContinueOrigin (vector, loc);
 744                         return true;
 745                 }
 746
 747                 public override bool AddReturnOrigin (UsageVector vector, Location loc)
 748                 {
 749                         Parent.AddReturnOrigin (vector, loc);
 750                         return true;
 751                 }
 752
 753                 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 754                 {
 755                         Parent.AddGotoOrigin (vector, goto_stmt);
 756                         return true;
 757                 }
 758
 759                 public override bool StealFinallyClauses (ref ArrayList list)
 760                 {
 761                         Parent.StealFinallyClauses (ref list);
 762                         return true;
 763                 }
 764         }
 765
 766         public class FlowBranchingException : FlowBranching
 767         {
 768                 ExceptionStatement stmt;
 769                 UsageVector current_vector;
 770                 UsageVector try_vector;
 771                 UsageVector finally_vector;
 772
 773                 UsageVector break_origins;
 774                 UsageVector continue_origins;
 775                 UsageVector return_origins;
 776                 GotoOrigin goto_origins;
 777
 778                 class GotoOrigin {
 779                         public GotoOrigin Next;
 780                         public Goto GotoStmt;
 781                         public UsageVector Vector;
 782
 783                         public GotoOrigin (UsageVector vector, Goto goto_stmt, GotoOrigin next)
 784                         {
 785                                 Vector = vector;
 786                                 GotoStmt = goto_stmt;
 787                                 Next = next;
 788                         }
 789                 }
 790
 791                 bool emit_finally;
 792
 793                 public FlowBranchingException (FlowBranching parent,
 794                                                ExceptionStatement stmt)
 795                         : base (parent, BranchingType.Exception, SiblingType.Try,
 796                                 null, stmt.loc)
 797                 {
 798                         this.stmt = stmt;
 799                         this.emit_finally = true;
 800                 }
 801
 802                 protected override void AddSibling (UsageVector sibling)
 803                 {
 804                         switch (sibling.Type) {
 805                         case SiblingType.Try:
 806                                 try_vector = sibling;
 807                                 break;
 808                         case SiblingType.Finally:
 809                                 finally_vector = sibling;
 810                                 break;
 811                         default:
 812                                 throw new InvalidOperationException ();
 813                         }
 814                         current_vector = sibling;
 815                 }
 816
 817                 public override UsageVector CurrentUsageVector {
 818                         get { return current_vector; }
 819                 }
 820
 821                 public override bool AddBreakOrigin (UsageVector vector, Location loc)
 822                 {
 823                         vector = vector.Clone ();
 824                         if (finally_vector != null) {
 825                                 int errors = Report.Errors;
 826                                 Parent.AddBreakOrigin (vector, loc);
 827                                 if (errors == Report.Errors)
 828                                         Report.Error (157, loc, "Control cannot leave the body of a finally clause");
 829                         } else {
 830                                 vector.Location = loc;
 831                                 vector.Next = break_origins;
 832                                 break_origins = vector;
 833                         }
 834                         return true;
 835                 }
 836
 837                 public override bool AddContinueOrigin (UsageVector vector, Location loc)
 838                 {
 839                         vector = vector.Clone ();
 840                         if (finally_vector != null) {
 841                                 int errors = Report.Errors;
 842                                 Parent.AddContinueOrigin (vector, loc);
 843                                 if (errors == Report.Errors)
 844                                         Report.Error (157, loc, "Control cannot leave the body of a finally clause");
 845                         } else {
 846                                 vector.Location = loc;
 847                                 vector.Next = continue_origins;
 848                                 continue_origins = vector;
 849                         }
 850                         return true;
 851                 }
 852
 853                 public override bool AddReturnOrigin (UsageVector vector, Location loc)
 854                 {
 855                         vector = vector.Clone ();
 856                         if (finally_vector != null) {
 857                                 int errors = Report.Errors;
 858                                 Parent.AddReturnOrigin (vector, loc);
 859                                 if (errors == Report.Errors)
 860                                         Report.Error (157, loc, "Control cannot leave the body of a finally clause");
 861                         } else {
 862                                 vector.Location = loc;
 863                                 vector.Next = return_origins;
 864                                 return_origins = vector;
 865                         }
 866                         return true;
 867                 }
 868
 869                 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 870                 {
 871                         LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
 872                         if (s != null)
 873                                 throw new InternalErrorException ("Shouldn't get here");
 874
 875                         vector = vector.Clone ();
 876                         if (finally_vector != null) {
 877                                 int errors = Report.Errors;
 878                                 Parent.AddGotoOrigin (vector, goto_stmt);
 879                                 if (errors == Report.Errors)
 880                                         Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
 881                         } else {
 882                                 goto_origins = new GotoOrigin (vector, goto_stmt, goto_origins);
 883                         }
 884                         return true;
 885                 }
 886
 887                 public override bool StealFinallyClauses (ref ArrayList list)
 888                 {
 889                         if (list == null)
 890                                 list = new ArrayList ();
 891                         list.Add (stmt);
 892                         emit_finally = false;
 893                         base.StealFinallyClauses (ref list);
 894                         return true;
 895                 }
 896
 897                 public bool EmitFinally {
 898                         get { return emit_finally; }
 899                 }
 900
 901                 protected override UsageVector Merge ()
 902                 {
 903                         UsageVector vector = try_vector.Clone ();
 904
 905                         if (finally_vector != null)
 906                                 vector.MergeChild (finally_vector, false);
 907
 908                         for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
 909                                 if (finally_vector != null)
 910                                         origin.MergeChild (finally_vector, false);
 911                                 Parent.AddBreakOrigin (origin, origin.Location);
 912                         }
 913
 914                         for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
 915                                 if (finally_vector != null)
 916                                         origin.MergeChild (finally_vector, false);
 917                                 Parent.AddContinueOrigin (origin, origin.Location);
 918                         }
 919
 920                         for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
 921                                 if (finally_vector != null)
 922                                         origin.MergeChild (finally_vector, false);
 923                                 Parent.AddReturnOrigin (origin, origin.Location);
 924                         }
 925
 926                         for (GotoOrigin origin = goto_origins; origin != null; origin = origin.Next) {
 927                                 if (finally_vector != null)
 928                                         origin.Vector.MergeChild (finally_vector, false);
 929                                 Parent.AddGotoOrigin (origin.Vector, origin.GotoStmt);
 930                         }
 931
 932                         return vector;
 933                 }
 934         }
 935
 936         // <summary>
 937         //   This is used by the flow analysis code to keep track of the type of local variables
 938         //   and variables.
 939         //
 940         //   The flow code uses a BitVector to keep track of whether a variable has been assigned
 941         //   or not.  This is easy for fundamental types (int, char etc.) or reference types since
 942         //   you can only assign the whole variable as such.
 943         //
 944         //   For structs, we also need to keep track of all its fields.  To do this, we allocate one
 945         //   bit for the struct itself (it's used if you assign/access the whole struct) followed by
 946         //   one bit for each of its fields.
 947         //
 948         //   This class computes this `layout' for each type.
 949         // </summary>
 950         public class TypeInfo
 951         {
 952                 public readonly Type Type;
 953
 954                 // <summary>
 955                 //   Total number of bits a variable of this type consumes in the flow vector.
 956                 // </summary>
 957                 public readonly int TotalLength;
 958
 959                 // <summary>
 960                 //   Number of bits the simple fields of a variable of this type consume
 961                 //   in the flow vector.
 962                 // </summary>
 963                 public readonly int Length;
 964
 965                 // <summary>
 966                 //   This is only used by sub-structs.
 967                 // </summary>
 968                 public readonly int Offset;
 969
 970                 // <summary>
 971                 //   If this is a struct.
 972                 // </summary>
 973                 public readonly bool IsStruct;
 974
 975                 // <summary>
 976                 //   If this is a struct, all fields which are structs theirselves.
 977                 // </summary>
 978                 public TypeInfo[] SubStructInfo;
 979
 980                 protected readonly StructInfo struct_info;
 981                 private static Hashtable type_hash = new Hashtable ();
 982
 983                 public static TypeInfo GetTypeInfo (Type type)
 984                 {
 985                         TypeInfo info = (TypeInfo) type_hash [type];
 986                         if (info != null)
 987                                 return info;
 988
 989                         info = new TypeInfo (type);
 990                         type_hash.Add (type, info);
 991                         return info;
 992                 }
 993
 994                 public static TypeInfo GetTypeInfo (TypeContainer tc)
 995                 {
 996                         TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
 997                         if (info != null)
 998                                 return info;
 999
1000                         info = new TypeInfo (tc);
1001                         type_hash.Add (tc.TypeBuilder, info);
1002                         return info;
1003                 }
1004
1005                 private TypeInfo (Type type)
1006                 {
1007                         this.Type = type;
1008
1009                         struct_info = StructInfo.GetStructInfo (type);
1010                         if (struct_info != null) {
1011                                 Length = struct_info.Length;
1012                                 TotalLength = struct_info.TotalLength;
1013                                 SubStructInfo = struct_info.StructFields;
1014                                 IsStruct = true;
1015                         } else {
1016                                 Length = 0;
1017                                 TotalLength = 1;
1018                                 IsStruct = false;
1019                         }
1020                 }
1021
1022                 private TypeInfo (TypeContainer tc)
1023                 {
1024                         this.Type = tc.TypeBuilder;
1025
1026                         struct_info = StructInfo.GetStructInfo (tc);
1027                         if (struct_info != null) {
1028                                 Length = struct_info.Length;
1029                                 TotalLength = struct_info.TotalLength;
1030                                 SubStructInfo = struct_info.StructFields;
1031                                 IsStruct = true;
1032                         } else {
1033                                 Length = 0;
1034                                 TotalLength = 1;
1035                                 IsStruct = false;
1036                         }
1037                 }
1038
1039                 protected TypeInfo (StructInfo struct_info, int offset)
1040                 {
1041                         this.struct_info = struct_info;
1042                         this.Offset = offset;
1043                         this.Length = struct_info.Length;
1044                         this.TotalLength = struct_info.TotalLength;
1045                         this.SubStructInfo = struct_info.StructFields;
1046                         this.Type = struct_info.Type;
1047                         this.IsStruct = true;
1048                 }
1049
1050                 public int GetFieldIndex (string name)
1051                 {
1052                         if (struct_info == null)
1053                                 return 0;
1054
1055                         return struct_info [name];
1056                 }
1057
1058                 public TypeInfo GetSubStruct (string name)
1059                 {
1060                         if (struct_info == null)
1061                                 return null;
1062
1063                         return struct_info.GetStructField (name);
1064                 }
1065
1066                 // <summary>
1067                 //   A struct's constructor must always assign all fields.
1068                 //   This method checks whether it actually does so.
1069                 // </summary>
1070                 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1071                 {
1072                         if (struct_info == null)
1073                                 return true;
1074
1075                         bool ok = true;
1076                         for (int i = 0; i < struct_info.Count; i++) {
1077                                 FieldInfo field = struct_info.Fields [i];
1078
1079                                 if (!branching.IsFieldAssigned (vi, field.Name)) {
1080                                         Report.Error (171, loc,
1081                                                 "Field `{0}' must be fully assigned before control leaves the constructor",
1082                                                 TypeManager.GetFullNameSignature (field));
1083                                         ok = false;
1084                                 }
1085                         }
1086
1087                         return ok;
1088                 }
1089
1090                 public override string ToString ()
1091                 {
1092                         return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1093                                               Type, Offset, Length, TotalLength);
1094                 }
1095
1096                 protected class StructInfo {
1097                         public readonly Type Type;
1098                         public readonly FieldInfo[] Fields;
1099                         public readonly TypeInfo[] StructFields;
1100                         public readonly int Count;
1101                         public readonly int CountPublic;
1102                         public readonly int CountNonPublic;
1103                         public readonly int Length;
1104                         public readonly int TotalLength;
1105                         public readonly bool HasStructFields;
1106
1107                         private static Hashtable field_type_hash = new Hashtable ();
1108                         private Hashtable struct_field_hash;
1109                         private Hashtable field_hash;
1110
1111                         protected bool InTransit = false;
1112
1113                         // Private constructor.  To save memory usage, we only need to create one instance
1114                         // of this class per struct type.
1115                         private StructInfo (Type type)
1116                         {
1117                                 this.Type = type;
1118
1119                                 field_type_hash.Add (type, this);
1120
1121                                 if (type is TypeBuilder) {
1122                                         TypeContainer tc = TypeManager.LookupTypeContainer (type);
1123
1124                                         ArrayList fields = null;
1125                                         if (tc != null)
1126                                                 fields = tc.Fields;
1127
1128                                         ArrayList public_fields = new ArrayList ();
1129                                         ArrayList non_public_fields = new ArrayList ();
1130
1131                                         if (fields != null) {
1132                                                 foreach (FieldBase field in fields) {
1133                                                         if ((field.ModFlags & Modifiers.STATIC) != 0)
1134                                                                 continue;
1135                                                         if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1136                                                                 public_fields.Add (field.FieldBuilder);
1137                                                         else
1138                                                                 non_public_fields.Add (field.FieldBuilder);
1139                                                 }
1140                                         }
1141
1142                                         CountPublic = public_fields.Count;
1143                                         CountNonPublic = non_public_fields.Count;
1144                                         Count = CountPublic + CountNonPublic;
1145
1146                                         Fields = new FieldInfo [Count];
1147                                         public_fields.CopyTo (Fields, 0);
1148                                         non_public_fields.CopyTo (Fields, CountPublic);
1149 #if GMCS_SOURCE
1150                                 } else if (type is GenericTypeParameterBuilder) {
1151                                         CountPublic = CountNonPublic = Count = 0;
1152
1153                                         Fields = new FieldInfo [0];
1154 #endif
1155                                 } else {
1156                                         FieldInfo[] public_fields = type.GetFields (
1157                                                 BindingFlags.Instance|BindingFlags.Public);
1158                                         FieldInfo[] non_public_fields = type.GetFields (
1159                                                 BindingFlags.Instance|BindingFlags.NonPublic);
1160
1161                                         CountPublic = public_fields.Length;
1162                                         CountNonPublic = non_public_fields.Length;
1163                                         Count = CountPublic + CountNonPublic;
1164
1165                                         Fields = new FieldInfo [Count];
1166                                         public_fields.CopyTo (Fields, 0);
1167                                         non_public_fields.CopyTo (Fields, CountPublic);
1168                                 }
1169
1170                                 struct_field_hash = new Hashtable ();
1171                                 field_hash = new Hashtable ();
1172
1173                                 Length = 0;
1174                                 StructFields = new TypeInfo [Count];
1175                                 StructInfo[] sinfo = new StructInfo [Count];
1176
1177                                 InTransit = true;
1178
1179                                 for (int i = 0; i < Count; i++) {
1180                                         FieldInfo field = (FieldInfo) Fields [i];
1181
1182                                         sinfo [i] = GetStructInfo (field.FieldType);
1183                                         if (sinfo [i] == null)
1184                                                 field_hash.Add (field.Name, ++Length);
1185                                         else if (sinfo [i].InTransit) {
1186                                                 Report.Error (523, String.Format (
1187                                                                       "Struct member `{0}.{1}' of type `{2}' causes " +
1188                                                                       "a cycle in the structure layout",
1189                                                                       type, field.Name, sinfo [i].Type));
1190                                                 sinfo [i] = null;
1191                                                 return;
1192                                         }
1193                                 }
1194
1195                                 InTransit = false;
1196
1197                                 TotalLength = Length + 1;
1198                                 for (int i = 0; i < Count; i++) {
1199                                         FieldInfo field = (FieldInfo) Fields [i];
1200
1201                                         if (sinfo [i] == null)
1202                                                 continue;
1203
1204                                         field_hash.Add (field.Name, TotalLength);
1205
1206                                         HasStructFields = true;
1207                                         StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1208                                         struct_field_hash.Add (field.Name, StructFields [i]);
1209                                         TotalLength += sinfo [i].TotalLength;
1210                                 }
1211                         }
1212
1213                         public int this [string name] {
1214                                 get {
1215                                         if (field_hash.Contains (name))
1216                                                 return (int) field_hash [name];
1217                                         else
1218                                                 return 0;
1219                                 }
1220                         }
1221
1222                         public TypeInfo GetStructField (string name)
1223                         {
1224                                 return (TypeInfo) struct_field_hash [name];
1225                         }
1226
1227                         public static StructInfo GetStructInfo (Type type)
1228                         {
1229                                 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1230                                     TypeManager.IsBuiltinType (type))
1231                                         return null;
1232
1233                                 StructInfo info = (StructInfo) field_type_hash [type];
1234                                 if (info != null)
1235                                         return info;
1236
1237                                 return new StructInfo (type);
1238                         }
1239
1240                         public static StructInfo GetStructInfo (TypeContainer tc)
1241                         {
1242                                 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1243                                 if (info != null)
1244                                         return info;
1245
1246                                 return new StructInfo (tc.TypeBuilder);
1247                         }
1248                 }
1249         }
1250
1251         // <summary>
1252         //   This is used by the flow analysis code to store information about a single local variable
1253         //   or parameter.  Depending on the variable's type, we need to allocate one or more elements
1254         //   in the BitVector - if it's a fundamental or reference type, we just need to know whether
1255         //   it has been assigned or not, but for structs, we need this information for each of its fields.
1256         // </summary>
1257         public class VariableInfo {
1258                 public readonly string Name;
1259                 public readonly TypeInfo TypeInfo;
1260
1261                 // <summary>
1262                 //   The bit offset of this variable in the flow vector.
1263                 // </summary>
1264                 public readonly int Offset;
1265
1266                 // <summary>
1267                 //   The number of bits this variable needs in the flow vector.
1268                 //   The first bit always specifies whether the variable as such has been assigned while
1269                 //   the remaining bits contain this information for each of a struct's fields.
1270                 // </summary>
1271                 public readonly int Length;
1272
1273                 // <summary>
1274                 //   If this is a parameter of local variable.
1275                 // </summary>
1276                 public readonly bool IsParameter;
1277
1278                 public readonly LocalInfo LocalInfo;
1279
1280                 readonly VariableInfo Parent;
1281                 VariableInfo[] sub_info;
1282
1283                 protected VariableInfo (string name, Type type, int offset)
1284                 {
1285                         this.Name = name;
1286                         this.Offset = offset;
1287                         this.TypeInfo = TypeInfo.GetTypeInfo (type);
1288
1289                         Length = TypeInfo.TotalLength;
1290
1291                         Initialize ();
1292                 }
1293
1294                 protected VariableInfo (VariableInfo parent, TypeInfo type)
1295                 {
1296                         this.Name = parent.Name;
1297                         this.TypeInfo = type;
1298                         this.Offset = parent.Offset + type.Offset;
1299                         this.Parent = parent;
1300                         this.Length = type.TotalLength;
1301
1302                         this.IsParameter = parent.IsParameter;
1303                         this.LocalInfo = parent.LocalInfo;
1304
1305                         Initialize ();
1306                 }
1307
1308                 protected void Initialize ()
1309                 {
1310                         TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1311                         if (sub_fields != null) {
1312                                 sub_info = new VariableInfo [sub_fields.Length];
1313                                 for (int i = 0; i < sub_fields.Length; i++) {
1314                                         if (sub_fields [i] != null)
1315                                                 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1316                                 }
1317                         } else
1318                                 sub_info = new VariableInfo [0];
1319                 }
1320
1321                 public VariableInfo (LocalInfo local_info, int offset)
1322                         : this (local_info.Name, local_info.VariableType, offset)
1323                 {
1324                         this.LocalInfo = local_info;
1325                         this.IsParameter = false;
1326                 }
1327
1328                 public VariableInfo (Parameters ip, int i, int offset)
1329                         : this (ip.ParameterName (i), TypeManager.GetElementType (ip.ParameterType (i)), offset)
1330                 {
1331                         this.IsParameter = true;
1332                 }
1333
1334                 public bool IsAssigned (EmitContext ec)
1335                 {
1336                         return !ec.DoFlowAnalysis ||
1337                                 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1338                                 ec.CurrentBranching.IsAssigned (this);
1339                 }
1340
1341                 public bool IsAssigned (EmitContext ec, Location loc)
1342                 {
1343                         if (IsAssigned (ec))
1344                                 return true;
1345
1346                         Report.Error (165, loc,
1347                                       "Use of unassigned local variable `" + Name + "'");
1348                         ec.CurrentBranching.SetAssigned (this);
1349                         return false;
1350                 }
1351
1352                 public bool IsAssigned (MyBitVector vector)
1353                 {
1354                         if (vector == null)
1355                                 return true;
1356
1357                         if (vector [Offset])
1358                                 return true;
1359
1360                         // FIXME: Fix SetFieldAssigned to set the whole range like SetAssigned below. Then, get rid of this stanza
1361                         for (VariableInfo parent = Parent; parent != null; parent = parent.Parent) {
1362                                 if (vector [parent.Offset]) {
1363                                         // 'parent' is assigned, but someone forgot to note that all its components are assigned too
1364                                         parent.SetAssigned (vector);
1365                                         return true;
1366                                 }
1367                         }
1368
1369                         // Return unless this is a struct.
1370                         if (!TypeInfo.IsStruct)
1371                                 return false;
1372
1373                         // Ok, so each field must be assigned.
1374                         for (int i = 0; i < TypeInfo.Length; i++) {
1375                                 if (!vector [Offset + i + 1])
1376                                         return false;
1377                         }
1378
1379                         // Ok, now check all fields which are structs.
1380                         for (int i = 0; i < sub_info.Length; i++) {
1381                                 VariableInfo sinfo = sub_info [i];
1382                                 if (sinfo == null)
1383                                         continue;
1384
1385                                 if (!sinfo.IsAssigned (vector))
1386                                         return false;
1387                         }
1388
1389                         vector [Offset] = true;
1390                         return true;
1391                 }
1392
1393                 public void SetAssigned (EmitContext ec)
1394                 {
1395                         if (ec.DoFlowAnalysis)
1396                                 ec.CurrentBranching.SetAssigned (this);
1397                 }
1398
1399                 public void SetAssigned (MyBitVector vector)
1400                 {
1401                         if (Length == 1)
1402                                 vector [Offset] = true;
1403                         else
1404                                 vector.SetRange (Offset, Length);
1405                 }
1406
1407                 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1408                 {
1409                         if (!ec.DoFlowAnalysis ||
1410                                 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1411                                 ec.CurrentBranching.IsFieldAssigned (this, name))
1412                                 return true;
1413
1414                         Report.Error (170, loc,
1415                                       "Use of possibly unassigned field `" + name + "'");
1416                         ec.CurrentBranching.SetFieldAssigned (this, name);
1417                         return false;
1418                 }
1419
1420                 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1421                 {
1422                         int field_idx = TypeInfo.GetFieldIndex (field_name);
1423
1424                         if (field_idx == 0)
1425                                 return true;
1426
1427                         return vector [Offset + field_idx];
1428                 }
1429
1430                 public void SetFieldAssigned (EmitContext ec, string name)
1431                 {
1432                         if (ec.DoFlowAnalysis)
1433                                 ec.CurrentBranching.SetFieldAssigned (this, name);
1434                 }
1435
1436                 public void SetFieldAssigned (MyBitVector vector, string field_name)
1437                 {
1438                         int field_idx = TypeInfo.GetFieldIndex (field_name);
1439
1440                         if (field_idx == 0)
1441                                 return;
1442
1443                         vector [Offset + field_idx] = true;
1444                 }
1445
1446                 public VariableInfo GetSubStruct (string name)
1447                 {
1448                         TypeInfo type = TypeInfo.GetSubStruct (name);
1449
1450                         if (type == null)
1451                                 return null;
1452
1453                         return new VariableInfo (this, type);
1454                 }
1455
1456                 public override string ToString ()
1457                 {
1458                         return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1459                                               Name, TypeInfo, Offset, Length, IsParameter);
1460                 }
1461         }
1462
1463         // <summary>
1464         //   This is a special bit vector which can inherit from another bit vector doing a
1465         //   copy-on-write strategy.  The inherited vector may have a smaller size than the
1466         //   current one.
1467         // </summary>
1468         public class MyBitVector {
1469                 public readonly int Count;
1470                 public static readonly MyBitVector Empty = new MyBitVector ();
1471
1472                 // Invariant: vector != null => vector.Count == Count
1473                 // Invariant: vector == null || shared == null
1474                 //            i.e., at most one of 'vector' and 'shared' can be non-null.  They can both be null -- that means all-ones
1475                 // The object in 'shared' cannot be modified, while 'vector' can be freely modified
1476                 BitArray vector, shared;
1477
1478                 MyBitVector ()
1479                 {
1480                         shared = new BitArray (0, false);
1481                 }
1482
1483                 public MyBitVector (MyBitVector InheritsFrom, int Count)
1484                 {
1485                         if (InheritsFrom != null)
1486                                 shared = InheritsFrom.Shared;
1487
1488                         this.Count = Count;
1489                 }
1490
1491                 // Use this accessor to get a shareable copy of the underlying BitArray representation
1492                 BitArray Shared {
1493                         get {
1494                                 // Post-condition: vector == null
1495                                 if (shared == null) {
1496                                         shared = vector;
1497                                         vector = null;
1498                                 }
1499                                 return shared;
1500                         }
1501                 }
1502
1503                 // <summary>
1504                 //   Get/set bit `index' in the bit vector.
1505                 // </summary>
1506                 public bool this [int index] {
1507                         get {
1508                                 if (index >= Count)
1509                                         throw new ArgumentOutOfRangeException ();
1510
1511                                 if (vector != null)
1512                                         return vector [index];
1513                                 if (shared == null)
1514                                         return true;
1515                                 if (index < shared.Count)
1516                                         return shared [index];
1517                                 return false;
1518                         }
1519
1520                         set {
1521                                 // Only copy the vector if we're actually modifying it.
1522                                 if (this [index] != value) {
1523                                         if (vector == null)
1524                                                 initialize_vector ();
1525                                         vector [index] = value;
1526                                 }
1527                         }
1528                 }
1529
1530                 // <summary>
1531                 //   Performs an `or' operation on the bit vector.  The `new_vector' may have a
1532                 //   different size than the current one.
1533                 // </summary>
1534                 private MyBitVector Or (MyBitVector new_vector)
1535                 {
1536                         if (Count == 0 || new_vector.Count == 0)
1537                                 return this;
1538
1539                         BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1540
1541                         if (o == null) {
1542                                 int n = new_vector.Count;
1543                                 if (n < Count) {
1544                                         for (int i = 0; i < n; ++i)
1545                                                 this [i] = true;
1546                                 } else {
1547                                         SetAll (true);
1548                                 }
1549                                 return this;
1550                         }
1551
1552                         if (Count == o.Count) {
1553                                 if (vector == null) {
1554                                         if (shared == null)
1555                                                 return this;
1556                                         initialize_vector ();
1557                                 }
1558                                 vector.Or (o);
1559                                 return this;
1560                         }
1561
1562                         int min = o.Count;
1563                         if (Count < min)
1564                                 min = Count;
1565
1566                         for (int i = 0; i < min; i++) {
1567                                 if (o [i])
1568                                         this [i] = true;
1569                         }
1570
1571                         return this;
1572                 }
1573
1574                 // <summary>
1575                 //   Performs an `and' operation on the bit vector.  The `new_vector' may have
1576                 //   a different size than the current one.
1577                 // </summary>
1578                 private MyBitVector And (MyBitVector new_vector)
1579                 {
1580                         if (Count == 0)
1581                                 return this;
1582
1583                         BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1584
1585                         if (o == null) {
1586                                 for (int i = new_vector.Count; i < Count; ++i)
1587                                         this [i] = false;
1588                                 return this;
1589                         }
1590
1591                         if (o.Count == 0) {
1592                                 SetAll (false);
1593                                 return this;
1594                         }
1595
1596                         if (Count == o.Count) {
1597                                 if (vector == null) {
1598                                         if (shared == null) {
1599                                                 shared = new_vector.Shared;
1600                                                 return this;
1601                                         }
1602                                         initialize_vector ();
1603                                 }
1604                                 vector.And (o);
1605                                 return this;
1606                         }
1607
1608                         int min = o.Count;
1609                         if (Count < min)
1610                                 min = Count;
1611
1612                         for (int i = 0; i < min; i++) {
1613                                 if (! o [i])
1614                                         this [i] = false;
1615                         }
1616
1617                         for (int i = min; i < Count; i++)
1618                                 this [i] = false;
1619
1620                         return this;
1621                 }
1622
1623                 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1624                 {
1625                         if (a == b)
1626                                 return a;
1627                         if (a == null)
1628                                 return b.Clone ();
1629                         if (b == null)
1630                                 return a.Clone ();
1631                         if (a.Count > b.Count)
1632                                 return a.Clone ().And (b);
1633                         else
1634                                 return b.Clone ().And (a);
1635                 }
1636
1637                 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1638                 {
1639                         if (a == b)
1640                                 return a;
1641                         if (a == null)
1642                                 return new MyBitVector (null, b.Count);
1643                         if (b == null)
1644                                 return new MyBitVector (null, a.Count);
1645                         if (a.Count > b.Count)
1646                                 return a.Clone ().Or (b);
1647                         else
1648                                 return b.Clone ().Or (a);
1649                 }
1650
1651                 public MyBitVector Clone ()
1652                 {
1653                         return Count == 0 ? Empty : new MyBitVector (this, Count);
1654                 }
1655
1656                 public void SetRange (int offset, int length)
1657                 {
1658                         if (offset > Count || offset + length > Count)
1659                                 throw new ArgumentOutOfRangeException ();
1660
1661                         if (shared == null && vector == null)
1662                                 return;
1663
1664                         int i = 0;
1665                         if (shared != null) {
1666                                 if (offset + length <= shared.Count) {
1667                                         for (; i < length; ++i)
1668                                                 if (!shared [i+offset])
1669                                                     break;
1670                                         if (i == length)
1671                                                 return;
1672                                 }
1673                                 initialize_vector ();
1674                         }
1675                         for (; i < length; ++i)
1676                                 vector [i+offset] = true;
1677
1678                 }
1679
1680                 public void SetAll (bool value)
1681                 {
1682                         // Don't clobber Empty
1683                         if (Count == 0)
1684                                 return;
1685                         shared = value ? null : Empty.Shared;
1686                         vector = null;
1687                 }
1688
1689                 void initialize_vector ()
1690                 {
1691                         // Post-condition: vector != null
1692                         if (shared == null) {
1693                                 vector = new BitArray (Count, true);
1694                                 return;
1695                         }
1696
1697                         vector = new BitArray (shared);
1698                         if (Count != vector.Count)
1699                                 vector.Length = Count;
1700                         shared = null;
1701                 }
1702
1703                 StringBuilder Dump (StringBuilder sb)
1704                 {
1705                         BitArray dump = vector == null ? shared : vector;
1706                         if (dump == null)
1707                                 return sb.Append ("/");
1708                         if (dump == shared)
1709                                 sb.Append ("=");
1710                         for (int i = 0; i < dump.Count; i++)
1711                                 sb.Append (dump [i] ? "1" : "0");
1712                         return sb;
1713                 }
1714
1715                 public override string ToString ()
1716                 {
1717                         return Dump (new StringBuilder ("{")).Append ("}").ToString ();
1718                 }
1719         }
1720 }