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