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