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