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