mcs/mcs/flowanalysis.cs

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