mcs/mcs/flowanalysis.cs

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