mcs/mcs/flowanalysis.cs

   1 //
   2 // flowanalyis.cs: The control flow analysis code
   3 //
   4 // Author:
   5 //   Martin Baulig (martin@ximian.com)
   6 //
   7 // (C) 2001, 2002, 2003 Ximian, Inc.
   8 //
   9
  10 using System;
  11 using System.Text;
  12 using System.Collections;
  13 using System.Reflection;
  14 using System.Reflection.Emit;
  15 using System.Diagnostics;
  16
  17 namespace Mono.CSharp
  18 {
  19         // <summary>
  20         //   A new instance of this class is created every time a new block is resolved
  21         //   and if there's branching in the block's control flow.
  22         // </summary>
  23         public abstract class FlowBranching
  24         {
  25                 // <summary>
  26                 //   The type of a FlowBranching.
  27                 // </summary>
  28                 public enum BranchingType {
  29                         // Normal (conditional or toplevel) block.
  30                         Block,
  31
  32                         // Conditional.
  33                         Conditional,
  34
  35                         // A loop block.
  36                         LoopBlock,
  37
  38                         // Try/Catch block.
  39                         Exception,
  40
  41                         // Switch block.
  42                         Switch,
  43
  44                         // Switch section.
  45                         SwitchSection
  46                 }
  47
  48                 // <summary>
  49                 //   The type of one sibling of a branching.
  50                 // </summary>
  51                 public enum SiblingType {
  52                         Block,
  53                         Conditional,
  54                         SwitchSection,
  55                         Try,
  56                         Catch,
  57                         Finally
  58                 }
  59
  60                 // <summary>
  61                 //   This is used in the control flow analysis code to specify whether the
  62                 //   current code block may return to its enclosing block before reaching
  63                 //   its end.
  64                 // </summary>
  65                 public enum FlowReturns {
  66                         Undefined = 0,
  67
  68                         // It can never return.
  69                         Never,
  70
  71                         // This means that the block contains a conditional return statement
  72                         // somewhere.
  73                         Sometimes,
  74
  75                         // The code always returns, ie. there's an unconditional return / break
  76                         // statement in it.
  77                         Always
  78                 }
  79
  80                 public sealed class Reachability
  81                 {
  82                         FlowReturns returns, breaks, throws, barrier, reachable;
  83
  84                         public FlowReturns Returns {
  85                                 get { return returns; }
  86                         }
  87                         public FlowReturns Breaks {
  88                                 get { return breaks; }
  89                         }
  90                         public FlowReturns Throws {
  91                                 get { return throws; }
  92                         }
  93                         public FlowReturns Barrier {
  94                                 get { return barrier; }
  95                         }
  96                         public FlowReturns Reachable {
  97                                 get { return reachable; }
  98                         }
  99
 100                         public Reachability (FlowReturns returns, FlowReturns breaks,
 101                                              FlowReturns throws, FlowReturns barrier)
 102                         {
 103                                 this.returns = returns;
 104                                 this.breaks = breaks;
 105                                 this.throws = throws;
 106                                 this.barrier = barrier;
 107
 108                                 update ();
 109                         }
 110
 111                         public Reachability Clone ()
 112                         {
 113                                 Reachability cloned = new Reachability (returns, breaks, throws, barrier);
 114                                 cloned.reachable = reachable;
 115                                 return cloned;
 116                         }
 117
 118                         public static void And (ref Reachability a, Reachability b, bool do_break)
 119                         {
 120                                 if (a == null) {
 121                                         a = b.Clone ();
 122                                         return;
 123                                 }
 124
 125                                 Report.Debug (4, "AND REACHABILITY", a, b, do_break);
 126
 127                                 //
 128                                 // `break' does not "break" in a Switch or a LoopBlock
 129                                 //
 130                                 bool a_breaks = do_break && a.AlwaysBreaks;
 131                                 bool b_breaks = do_break && b.AlwaysBreaks;
 132
 133                                 bool a_has_barrier, b_has_barrier;
 134                                 if (do_break) {
 135                                         //
 136                                         // This is the normal case: the code following a barrier
 137                                         // cannot be reached.
 138                                         //
 139                                         a_has_barrier = a.AlwaysHasBarrier;
 140                                         b_has_barrier = b.AlwaysHasBarrier;
 141                                 } else {
 142                                         //
 143                                         // Special case for Switch and LoopBlocks: we can reach the
 144                                         // code after the barrier via the `break'.
 145                                         //
 146                                         a_has_barrier = !a.AlwaysBreaks && a.AlwaysHasBarrier;
 147                                         b_has_barrier = !b.AlwaysBreaks && b.AlwaysHasBarrier;
 148                                 }
 149
 150                                 bool a_unreachable = a_breaks || a.AlwaysThrows || a_has_barrier;
 151                                 bool b_unreachable = b_breaks || b.AlwaysThrows || b_has_barrier;
 152
 153                                 //
 154                                 // Do all code paths always return ?
 155                                 //
 156                                 if (a.AlwaysReturns) {
 157                                         if (b.AlwaysReturns || b_unreachable)
 158                                                 a.returns = FlowReturns.Always;
 159                                         else
 160                                                 a.returns = FlowReturns.Sometimes;
 161                                 } else if (b.AlwaysReturns) {
 162                                         if (a.AlwaysReturns || a_unreachable)
 163                                                 a.returns = FlowReturns.Always;
 164                                         else
 165                                                 a.returns = FlowReturns.Sometimes;
 166                                 } else if (!a.MayReturn) {
 167                                         if (b.MayReturn)
 168                                                 a.returns = FlowReturns.Sometimes;
 169                                         else
 170                                                 a.returns = FlowReturns.Never;
 171                                 } else if (!b.MayReturn) {
 172                                         if (a.MayReturn)
 173                                                 a.returns = FlowReturns.Sometimes;
 174                                         else
 175                                                 a.returns = FlowReturns.Never;
 176                                 }
 177
 178                                 a.breaks = AndFlowReturns (a.breaks, b.breaks);
 179                                 a.throws = AndFlowReturns (a.throws, b.throws);
 180                                 a.barrier = AndFlowReturns (a.barrier, b.barrier);
 181
 182                                 a.reachable = AndFlowReturns (a.reachable, b.reachable);
 183                         }
 184
 185                         public static Reachability Never ()
 186                         {
 187                                 return new Reachability (
 188                                         FlowReturns.Never, FlowReturns.Never,
 189                                         FlowReturns.Never, FlowReturns.Never);
 190                         }
 191
 192                         void update ()
 193                         {
 194                                 if ((returns == FlowReturns.Always) || (breaks == FlowReturns.Always) ||
 195                                     (throws == FlowReturns.Always) || (barrier == FlowReturns.Always))
 196                                         reachable = FlowReturns.Never;
 197                                 else if ((returns == FlowReturns.Never) && (breaks == FlowReturns.Never) &&
 198                                          (throws == FlowReturns.Never) && (barrier == FlowReturns.Never))
 199                                         reachable = FlowReturns.Always;
 200                                 else
 201                                         reachable = FlowReturns.Sometimes;
 202                         }
 203
 204                         public bool AlwaysBreaks {
 205                                 get { return breaks == FlowReturns.Always; }
 206                         }
 207
 208                         public bool MayBreak {
 209                                 get { return breaks != FlowReturns.Never; }
 210                         }
 211
 212                         public bool AlwaysReturns {
 213                                 get { return returns == FlowReturns.Always; }
 214                         }
 215
 216                         public bool MayReturn {
 217                                 get { return returns != FlowReturns.Never; }
 218                         }
 219
 220                         public bool AlwaysThrows {
 221                                 get { return throws == FlowReturns.Always; }
 222                         }
 223
 224                         public bool MayThrow {
 225                                 get { return throws != FlowReturns.Never; }
 226                         }
 227
 228                         public bool AlwaysHasBarrier {
 229                                 get { return barrier == FlowReturns.Always; }
 230                         }
 231
 232                         public bool MayHaveBarrier {
 233                                 get { return barrier != FlowReturns.Never; }
 234                         }
 235
 236                         public bool IsUnreachable {
 237                                 get { return reachable == FlowReturns.Never; }
 238                         }
 239
 240                         public void SetReturns ()
 241                         {
 242                                 returns = FlowReturns.Always;
 243                                 update ();
 244                         }
 245
 246                         public void SetReturnsSometimes ()
 247                         {
 248                                 returns = FlowReturns.Sometimes;
 249                                 update ();
 250                         }
 251
 252                         public void SetBreaks ()
 253                         {
 254                                 breaks = FlowReturns.Always;
 255                                 update ();
 256                         }
 257
 258                         public void ResetBreaks ()
 259                         {
 260                                 breaks = FlowReturns.Never;
 261                                 update ();
 262                         }
 263
 264                         public void SetThrows ()
 265                         {
 266                                 throws = FlowReturns.Always;
 267                                 update ();
 268                         }
 269
 270                         public void SetBarrier ()
 271                         {
 272                                 barrier = FlowReturns.Always;
 273                                 update ();
 274                         }
 275
 276                         static string ShortName (FlowReturns returns)
 277                         {
 278                                 switch (returns) {
 279                                 case FlowReturns.Never:
 280                                         return "N";
 281                                 case FlowReturns.Sometimes:
 282                                         return "S";
 283                                 default:
 284                                         return "A";
 285                                 }
 286                         }
 287
 288                         public override string ToString ()
 289                         {
 290                                 return String.Format ("[{0}:{1}:{2}:{3}:{4}]",
 291                                                       ShortName (returns), ShortName (breaks),
 292                                                       ShortName (throws), ShortName (barrier),
 293                                                       ShortName (reachable));
 294                         }
 295                 }
 296
 297                 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
 298                 {
 299                         switch (type) {
 300                         case BranchingType.Exception:
 301                                 return new FlowBranchingException (parent, type, block, loc);
 302
 303                         case BranchingType.Switch:
 304                                 return new FlowBranchingBlock (parent, type, SiblingType.SwitchSection, block, loc);
 305
 306                         case BranchingType.SwitchSection:
 307                                 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
 308
 309                         case BranchingType.Block:
 310                                 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
 311
 312                         default:
 313                                 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
 314                         }
 315                 }
 316
 317                 // <summary>
 318                 //   The type of this flow branching.
 319                 // </summary>
 320                 public readonly BranchingType Type;
 321
 322                 // <summary>
 323                 //   The block this branching is contained in.  This may be null if it's not
 324                 //   a top-level block and it doesn't declare any local variables.
 325                 // </summary>
 326                 public readonly Block Block;
 327
 328                 // <summary>
 329                 //   The parent of this branching or null if this is the top-block.
 330                 // </summary>
 331                 public readonly FlowBranching Parent;
 332
 333                 // <summary>
 334                 //   Start-Location of this flow branching.
 335                 // </summary>
 336                 public readonly Location Location;
 337
 338                 // <summary>
 339                 //   If this is an infinite loop.
 340                 // </summary>
 341                 public bool Infinite;
 342
 343                 //
 344                 // Private
 345                 //
 346                 VariableMap param_map, local_map;
 347
 348                 static int next_id = 0;
 349                 int id;
 350
 351                 // <summary>
 352                 //   Performs an `And' operation on the FlowReturns status
 353                 //   (for instance, a block only returns Always if all its siblings
 354                 //   always return).
 355                 // </summary>
 356                 public static FlowReturns AndFlowReturns (FlowReturns a, FlowReturns b)
 357                 {
 358                         if (a == FlowReturns.Undefined)
 359                                 return b;
 360
 361                         switch (a) {
 362                         case FlowReturns.Never:
 363                                 if (b == FlowReturns.Never)
 364                                         return FlowReturns.Never;
 365                                 else
 366                                         return FlowReturns.Sometimes;
 367
 368                         case FlowReturns.Sometimes:
 369                                 return FlowReturns.Sometimes;
 370
 371                         case FlowReturns.Always:
 372                                 if (b == FlowReturns.Always)
 373                                         return FlowReturns.Always;
 374                                 else
 375                                         return FlowReturns.Sometimes;
 376
 377                         default:
 378                                 throw new ArgumentException ();
 379                         }
 380
 381                         return b;
 382                 }
 383
 384                 // <summary>
 385                 //   The vector contains a BitArray with information about which local variables
 386                 //   and parameters are already initialized at the current code position.
 387                 // </summary>
 388                 public class UsageVector {
 389                         // <summary>
 390                         //   The type of this branching.
 391                         // </summary>
 392                         public readonly SiblingType Type;
 393
 394                         // <summary>
 395                         //   Start location of this branching.
 396                         // </summary>
 397                         public readonly Location Location;
 398
 399                         // <summary>
 400                         //   If this is true, then the usage vector has been modified and must be
 401                         //   merged when we're done with this branching.
 402                         // </summary>
 403                         public bool IsDirty;
 404
 405                         // <summary>
 406                         //   The number of parameters in this block.
 407                         // </summary>
 408                         public readonly int CountParameters;
 409
 410                         // <summary>
 411                         //   The number of locals in this block.
 412                         // </summary>
 413                         public readonly int CountLocals;
 414
 415                         // <summary>
 416                         //   If not null, then we inherit our state from this vector and do a
 417                         //   copy-on-write.  If null, then we're the first sibling in a top-level
 418                         //   block and inherit from the empty vector.
 419                         // </summary>
 420                         public readonly UsageVector InheritsFrom;
 421
 422                         // <summary>
 423                         //   This is used to construct a list of UsageVector's.
 424                         // </summary>
 425                         public UsageVector Next;
 426
 427                         //
 428                         // Private.
 429                         //
 430                         MyBitVector locals, parameters;
 431                         Reachability reachability;
 432                         bool is_finally;
 433
 434                         static int next_id = 0;
 435                         int id;
 436
 437                         //
 438                         // Normally, you should not use any of these constructors.
 439                         //
 440                         public UsageVector (SiblingType type, UsageVector parent, Location loc, int num_params, int num_locals)
 441                         {
 442                                 this.Type = type;
 443                                 this.Location = loc;
 444                                 this.InheritsFrom = parent;
 445                                 this.CountParameters = num_params;
 446                                 this.CountLocals = num_locals;
 447
 448                                 if (parent != null) {
 449                                         locals = new MyBitVector (parent.locals, CountLocals);
 450                                         if (num_params > 0)
 451                                                 parameters = new MyBitVector (parent.parameters, num_params);
 452
 453                                         reachability = parent.Reachability.Clone ();
 454                                 } else {
 455                                         locals = new MyBitVector (null, CountLocals);
 456                                         if (num_params > 0)
 457                                                 parameters = new MyBitVector (null, num_params);
 458
 459                                         reachability = Reachability.Never ();
 460                                 }
 461
 462                                 id = ++next_id;
 463                         }
 464
 465                         public UsageVector (SiblingType type, UsageVector parent, Location loc)
 466                                 : this (type, parent, loc, parent.CountParameters, parent.CountLocals)
 467                         { }
 468
 469                         public UsageVector (MyBitVector parameters, MyBitVector locals,
 470                                             Reachability reachability, Location loc)
 471                         {
 472                                 this.Type = SiblingType.Block;
 473                                 this.Location = loc;
 474
 475                                 this.reachability = reachability;
 476                                 this.parameters = parameters;
 477                                 this.locals = locals;
 478
 479                                 id = ++next_id;
 480                         }
 481
 482                         // <summary>
 483                         //   This does a deep copy of the usage vector.
 484                         // </summary>
 485                         public UsageVector Clone ()
 486                         {
 487                                 UsageVector retval = new UsageVector (Type, null, Location, CountParameters, CountLocals);
 488
 489                                 retval.locals = locals.Clone ();
 490                                 if (parameters != null)
 491                                         retval.parameters = parameters.Clone ();
 492                                 retval.reachability = reachability.Clone ();
 493
 494                                 return retval;
 495                         }
 496
 497                         public bool IsAssigned (VariableInfo var)
 498                         {
 499                                 if (!var.IsParameter && Reachability.AlwaysBreaks)
 500                                         return true;
 501
 502                                 return var.IsAssigned (var.IsParameter ? parameters : locals);
 503                         }
 504
 505                         public void SetAssigned (VariableInfo var)
 506                         {
 507                                 if (!var.IsParameter && Reachability.AlwaysBreaks)
 508                                         return;
 509
 510                                 IsDirty = true;
 511                                 var.SetAssigned (var.IsParameter ? parameters : locals);
 512                         }
 513
 514                         public bool IsFieldAssigned (VariableInfo var, string name)
 515                         {
 516                                 if (!var.IsParameter && Reachability.AlwaysBreaks)
 517                                         return true;
 518
 519                                 return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
 520                         }
 521
 522                         public void SetFieldAssigned (VariableInfo var, string name)
 523                         {
 524                                 if (!var.IsParameter && Reachability.AlwaysBreaks)
 525                                         return;
 526
 527                                 IsDirty = true;
 528                                 var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
 529                         }
 530
 531                         public Reachability Reachability {
 532                                 get {
 533                                         return reachability;
 534                                 }
 535                         }
 536
 537                         public void Return ()
 538                         {
 539                                 if (!reachability.IsUnreachable) {
 540                                         IsDirty = true;
 541                                         reachability.SetReturns ();
 542                                 }
 543                         }
 544
 545                         public void Break ()
 546                         {
 547                                 if (!reachability.IsUnreachable) {
 548                                         IsDirty = true;
 549                                         reachability.SetBreaks ();
 550                                 }
 551                         }
 552
 553                         public void Throw ()
 554                         {
 555                                 if (!reachability.IsUnreachable) {
 556                                         IsDirty = true;
 557                                         reachability.SetThrows ();
 558                                 }
 559                         }
 560
 561                         public void Goto ()
 562                         {
 563                                 if (!reachability.IsUnreachable) {
 564                                         IsDirty = true;
 565                                         reachability.SetBarrier ();
 566                                 }
 567                         }
 568
 569                         // <summary>
 570                         //   Merges a child branching.
 571                         // </summary>
 572                         public void MergeResult (MyBitVector new_params, MyBitVector new_locals,
 573                                                 Reachability new_reachability)
 574                         {
 575                                 Report.Debug (2, "  MERGING RESULT", this, IsDirty,
 576                                               new_params, new_locals, new_reachability, Type);
 577
 578                                 reachability = new_reachability;
 579
 580                                 //
 581                                 // We've now either reached the point after the branching or we will
 582                                 // never get there since we always return or always throw an exception.
 583                                 //
 584                                 // If we can reach the point after the branching, mark all locals and
 585                                 // parameters as initialized which have been initialized in all branches
 586                                 // we need to look at (see above).
 587                                 //
 588
 589                                 if ((Type == SiblingType.SwitchSection) && !reachability.IsUnreachable) {
 590                                         Report.Error (163, Location,
 591                                                       "Control cannot fall through from one " +
 592                                                       "case label to another");
 593                                         return;
 594                                 }
 595
 596                                 if (new_locals != null)
 597                                         locals.Or (new_locals);
 598
 599                                 if (new_params != null)
 600                                         parameters.Or (new_params);
 601
 602                                 Report.Debug (2, "  MERGING RESULT DONE", this);
 603
 604                                 IsDirty = true;
 605                         }
 606
 607                         protected void MergeFinally (FlowBranching branching, UsageVector f_origins,
 608                                                      MyBitVector f_params)
 609                         {
 610                                 for (UsageVector vector = f_origins; vector != null; vector = vector.Next) {
 611                                         MyBitVector temp_params = f_params.Clone ();
 612                                         temp_params.Or (vector.Parameters);
 613
 614                                         branching.CheckOutParameters (temp_params, branching.Location);
 615                                 }
 616                         }
 617
 618                         public void MergeFinally (FlowBranching branching, UsageVector f_vector,
 619                                                   UsageVector f_origins)
 620                         {
 621                                 if (parameters != null) {
 622                                         if (f_vector != null) {
 623                                                 MergeFinally (branching, f_origins, f_vector.Parameters);
 624                                                 MyBitVector.Or (ref parameters, f_vector.ParameterVector);
 625                                         } else
 626                                                 MergeFinally (branching, f_origins, parameters);
 627                                 }
 628
 629                                 if (f_vector != null)
 630                                         MyBitVector.Or (ref locals, f_vector.LocalVector);
 631                         }
 632
 633                         // <summary>
 634                         //   Tells control flow analysis that the current code position may be reached with
 635                         //   a forward jump from any of the origins listed in `origin_vectors' which is a
 636                         //   list of UsageVectors.
 637                         //
 638                         //   This is used when resolving forward gotos - in the following example, the
 639                         //   variable `a' is uninitialized in line 8 becase this line may be reached via
 640                         //   the goto in line 4:
 641                         //
 642                         //      1     int a;
 643                         //
 644                         //      3     if (something)
 645                         //      4        goto World;
 646                         //
 647                         //      6     a = 5;
 648                         //
 649                         //      7  World:
 650                         //      8     Console.WriteLine (a);
 651                         //
 652                         // </summary>
 653                         public void MergeJumpOrigins (ICollection origin_vectors)
 654                         {
 655                                 Report.Debug (1, "  MERGING JUMP ORIGIN", this);
 656
 657                                 reachability = Reachability.Never ();
 658
 659                                 if (origin_vectors == null)
 660                                         return;
 661
 662                                 foreach (UsageVector vector in origin_vectors) {
 663                                         Report.Debug (1, "    MERGING JUMP ORIGIN", vector);
 664
 665                                         locals.And (vector.locals);
 666                                         if (parameters != null)
 667                                                 parameters.And (vector.parameters);
 668
 669                                         Reachability.And (ref reachability, vector.Reachability, true);
 670                                 }
 671
 672                                 Report.Debug (1, "  MERGING JUMP ORIGIN DONE", this);
 673                         }
 674
 675                         // <summary>
 676                         //   This is used at the beginning of a finally block if there were
 677                         //   any return statements in the try block or one of the catch blocks.
 678                         // </summary>
 679                         public void MergeFinallyOrigins (ICollection finally_vectors)
 680                         {
 681                                 Report.Debug (1, "  MERGING FINALLY ORIGIN", this);
 682
 683 #if FIXME
 684                                 RealBreaks = FlowReturns.Never;
 685 #endif
 686
 687                                 foreach (UsageVector vector in finally_vectors) {
 688                                         Report.Debug (1, "    MERGING FINALLY ORIGIN", vector);
 689
 690                                         if (parameters != null)
 691                                                 parameters.And (vector.parameters);
 692
 693 #if FIXME
 694                                         RealBreaks = AndFlowReturns (Breaks, vector.Breaks);
 695 #endif
 696                                 }
 697
 698                                 is_finally = true;
 699
 700                                 Report.Debug (1, "  MERGING FINALLY ORIGIN DONE", this);
 701                         }
 702
 703                         public void CheckOutParameters (FlowBranching branching)
 704                         {
 705                                 if (parameters != null)
 706                                         branching.CheckOutParameters (parameters, branching.Location);
 707                         }
 708
 709                         // <summary>
 710                         //   Performs an `or' operation on the locals and the parameters.
 711                         // </summary>
 712                         public void Or (UsageVector new_vector)
 713                         {
 714                                 IsDirty = true;
 715                                 locals.Or (new_vector.locals);
 716                                 if (parameters != null)
 717                                         parameters.Or (new_vector.parameters);
 718                         }
 719
 720                         // <summary>
 721                         //   Performs an `and' operation on the locals.
 722                         // </summary>
 723                         public void AndLocals (UsageVector new_vector)
 724                         {
 725                                 IsDirty = true;
 726                                 locals.And (new_vector.locals);
 727                         }
 728
 729                         public bool HasParameters {
 730                                 get {
 731                                         return parameters != null;
 732                                 }
 733                         }
 734
 735                         public bool HasLocals {
 736                                 get {
 737                                         return locals != null;
 738                                 }
 739                         }
 740
 741                         // <summary>
 742                         //   Returns a deep copy of the parameters.
 743                         // </summary>
 744                         public MyBitVector Parameters {
 745                                 get {
 746                                         if (parameters != null)
 747                                                 return parameters.Clone ();
 748                                         else
 749                                                 return null;
 750                                 }
 751                         }
 752
 753                         // <summary>
 754                         //   Returns a deep copy of the locals.
 755                         // </summary>
 756                         public MyBitVector Locals {
 757                                 get {
 758                                         return locals.Clone ();
 759                                 }
 760                         }
 761
 762                         public MyBitVector ParameterVector {
 763                                 get {
 764                                         return parameters;
 765                                 }
 766                         }
 767
 768                         public MyBitVector LocalVector {
 769                                 get {
 770                                         return locals;
 771                                 }
 772                         }
 773
 774                         //
 775                         // Debugging stuff.
 776                         //
 777
 778                         public override string ToString ()
 779                         {
 780                                 StringBuilder sb = new StringBuilder ();
 781
 782                                 sb.Append ("Vector (");
 783                                 sb.Append (id);
 784                                 sb.Append (",");
 785                                 sb.Append (IsDirty);
 786                                 sb.Append (",");
 787                                 sb.Append (reachability);
 788                                 if (parameters != null) {
 789                                         sb.Append (" - ");
 790                                         sb.Append (parameters);
 791                                 }
 792                                 sb.Append (" - ");
 793                                 sb.Append (locals);
 794                                 sb.Append (")");
 795
 796                                 return sb.ToString ();
 797                         }
 798                 }
 799
 800                 // <summary>
 801                 //   Creates a new flow branching which is contained in `parent'.
 802                 //   You should only pass non-null for the `block' argument if this block
 803                 //   introduces any new variables - in this case, we need to create a new
 804                 //   usage vector with a different size than our parent's one.
 805                 // </summary>
 806                 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
 807                                          Block block, Location loc)
 808                 {
 809                         Parent = parent;
 810                         Block = block;
 811                         Location = loc;
 812                         Type = type;
 813                         id = ++next_id;
 814
 815                         UsageVector vector;
 816                         if (Block != null) {
 817                                 param_map = Block.ParameterMap;
 818                                 local_map = Block.LocalMap;
 819
 820                                 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
 821                                 vector = new UsageVector (stype, parent_vector, loc, param_map.Length, local_map.Length);
 822                         } else {
 823                                 param_map = Parent.param_map;
 824                                 local_map = Parent.local_map;
 825                                 vector = new UsageVector (stype, Parent.CurrentUsageVector, loc);
 826                         }
 827
 828                         AddSibling (vector);
 829                 }
 830
 831                 public abstract UsageVector CurrentUsageVector {
 832                         get;
 833                 }
 834
 835                 // <summary>
 836                 //   Creates a sibling of the current usage vector.
 837                 // </summary>
 838                 public virtual void CreateSibling (SiblingType type)
 839                 {
 840                         AddSibling (new UsageVector (type, Parent.CurrentUsageVector, Location));
 841
 842                         Report.Debug (1, "  CREATED SIBLING", CurrentUsageVector);
 843                 }
 844
 845                 protected abstract void AddSibling (UsageVector uv);
 846
 847                 public abstract void Label (ArrayList origin_vectors);
 848
 849                 // <summary>
 850                 //   Check whether all `out' parameters have been assigned.
 851                 // </summary>
 852                 public void CheckOutParameters (MyBitVector parameters, Location loc)
 853                 {
 854                         for (int i = 0; i < param_map.Count; i++) {
 855                                 VariableInfo var = param_map [i];
 856
 857                                 if (var == null)
 858                                         continue;
 859
 860                                 if (var.IsAssigned (parameters))
 861                                         continue;
 862
 863                                 Report.Error (177, loc, "The out parameter `" +
 864                                               param_map.VariableNames [i] + "' must be " +
 865                                               "assigned before control leave the current method.");
 866                         }
 867                 }
 868
 869                 protected UsageVector Merge (UsageVector sibling_list)
 870                 {
 871                         MyBitVector locals = null;
 872                         MyBitVector parameters = null;
 873
 874                         Reachability reachability = null;
 875
 876                         Report.Debug (2, "  MERGING CHILDREN", Name);
 877
 878                         for (UsageVector child = sibling_list; child != null; child = child.Next) {
 879                                 bool do_break = (Type != BranchingType.Switch) &&
 880                                         (Type != BranchingType.LoopBlock);
 881
 882                                 Report.Debug (2, "    MERGING CHILD   ", child,
 883                                               child.Locals, child.Parameters,
 884                                               reachability, child.Reachability, do_break);
 885
 886                                 Reachability.And (ref reachability, child.Reachability, do_break);
 887
 888                                 // A local variable is initialized after a flow branching if it
 889                                 // has been initialized in all its branches which do neither
 890                                 // always return or always throw an exception.
 891                                 //
 892                                 // If a branch may return, but does not always return, then we
 893                                 // can treat it like a never-returning branch here: control will
 894                                 // only reach the code position after the branching if we did not
 895                                 // return here.
 896                                 //
 897                                 // It's important to distinguish between always and sometimes
 898                                 // returning branches here:
 899                                 //
 900                                 //    1   int a;
 901                                 //    2   if (something) {
 902                                 //    3      return;
 903                                 //    4      a = 5;
 904                                 //    5   }
 905                                 //    6   Console.WriteLine (a);
 906                                 //
 907                                 // The if block in lines 3-4 always returns, so we must not look
 908                                 // at the initialization of `a' in line 4 - thus it'll still be
 909                                 // uninitialized in line 6.
 910                                 //
 911                                 // On the other hand, the following is allowed:
 912                                 //
 913                                 //    1   int a;
 914                                 //    2   if (something)
 915                                 //    3      a = 5;
 916                                 //    4   else
 917                                 //    5      return;
 918                                 //    6   Console.WriteLine (a);
 919                                 //
 920                                 // Here, `a' is initialized in line 3 and we must not look at
 921                                 // line 5 since it always returns.
 922                                 //
 923                                 bool do_break_2 = (child.Type != SiblingType.Block) &&
 924                                         (child.Type != SiblingType.SwitchSection);
 925                                 bool unreachable = (do_break_2 && child.Reachability.AlwaysBreaks) ||
 926                                         child.Reachability.AlwaysThrows ||
 927                                         child.Reachability.AlwaysReturns ||
 928                                         child.Reachability.AlwaysHasBarrier;
 929
 930                                 Report.Debug (2, "    MERGING CHILD #1", reachability,
 931                                               Type, child.Type, child.Reachability.IsUnreachable,
 932                                               do_break_2, unreachable);
 933
 934                                 if (!unreachable)
 935                                         MyBitVector.And (ref locals, child.LocalVector);
 936
 937                                 // An `out' parameter must be assigned in all branches which do
 938                                 // not always throw an exception.
 939                                 if ((child.Type != SiblingType.Catch) &&
 940                                     (child.ParameterVector != null) && !child.Reachability.AlwaysThrows)
 941                                         MyBitVector.And (ref parameters, child.ParameterVector);
 942                         }
 943
 944                         if (reachability == null)
 945                                 reachability = Reachability.Never ();
 946
 947                         Report.Debug (2, "  MERGING CHILDREN #1  ", Type, reachability,
 948                                       Infinite, reachability.MayBreak);
 949
 950                         if (Type == BranchingType.LoopBlock) {
 951                                 bool may_leave_loop = reachability.MayBreak;
 952                                 reachability.ResetBreaks ();
 953
 954                                 if (Infinite && !may_leave_loop) {
 955                                         if (reachability.Returns == FlowReturns.Sometimes) {
 956                                                 // If we're an infinite loop and do not break, the code
 957                                                 // after the loop can never be reached.  However, if we
 958                                                 // may return from the loop, then we do always return
 959                                                 // (or stay in the loop forever).
 960                                                 reachability.SetReturns ();
 961                                         }
 962
 963                                         reachability.SetBarrier ();
 964                                 } else {
 965                                         if (reachability.Returns == FlowReturns.Always) {
 966                                                 // We're either finite or we may leave the loop.
 967                                                 reachability.SetReturnsSometimes ();
 968                                         }
 969                                 }
 970                         } else if (Type == BranchingType.Switch)
 971                                 reachability.ResetBreaks ();
 972
 973                         Report.Debug (2, "  MERGING CHILDREN DONE", parameters, locals,
 974                                       reachability, Infinite);
 975
 976                         return new UsageVector (parameters, locals, reachability, Location);
 977                 }
 978
 979                 protected abstract UsageVector Merge ();
 980
 981                 // <summary>
 982                 //   Merge a child branching.
 983                 // </summary>
 984                 public Reachability MergeChild (FlowBranching child)
 985                 {
 986                         UsageVector result = child.Merge ();
 987
 988                         CurrentUsageVector.MergeResult (
 989                                 result.ParameterVector, result.LocalVector, result.Reachability);
 990
 991                         Report.Debug (4, "  MERGE CHILD", Location, child, CurrentUsageVector,
 992                                       result.Reachability);
 993
 994                         return result.Reachability;
 995                 }
 996
 997                 // <summary>
 998                 //   Does the toplevel merging.
 999                 // </summary>
1000                 public Reachability MergeTopBlock ()
1001                 {
1002                         if ((Type != BranchingType.Block) || (Block == null))
1003                                 throw new NotSupportedException ();
1004
1005                         UsageVector vector = new UsageVector (
1006                                 SiblingType.Conditional, null, Location, param_map.Length, local_map.Length);
1007
1008                         UsageVector result = Merge ();
1009                         vector.MergeResult (result.ParameterVector, result.LocalVector,
1010                                             result.Reachability);
1011
1012                         Report.Debug (4, "MERGE TOP BLOCK", Location, vector, result.Reachability);
1013
1014                         if (vector.Reachability.Throws != FlowReturns.Always)
1015                                 CheckOutParameters (vector.Parameters, Location);
1016
1017                         return result.Reachability;
1018                 }
1019
1020                 public virtual bool InTryBlock ()
1021                 {
1022                         if (Parent != null)
1023                                 return Parent.InTryBlock ();
1024                         else
1025                                 return false;
1026                 }
1027
1028                 public virtual void AddFinallyVector (UsageVector vector)
1029                 {
1030                         if (Parent != null)
1031                                 Parent.AddFinallyVector (vector);
1032                         else
1033                                 throw new NotSupportedException ();
1034                 }
1035
1036                 public bool IsAssigned (VariableInfo vi)
1037                 {
1038                         return CurrentUsageVector.IsAssigned (vi);
1039                 }
1040
1041                 public bool IsFieldAssigned (VariableInfo vi, string field_name)
1042                 {
1043                         if (CurrentUsageVector.IsAssigned (vi))
1044                                 return true;
1045
1046                         return CurrentUsageVector.IsFieldAssigned (vi, field_name);
1047                 }
1048
1049                 public void SetAssigned (VariableInfo vi)
1050                 {
1051                         CurrentUsageVector.SetAssigned (vi);
1052                 }
1053
1054                 public void SetFieldAssigned (VariableInfo vi, string name)
1055                 {
1056                         CurrentUsageVector.SetFieldAssigned (vi, name);
1057                 }
1058
1059                 public override string ToString ()
1060                 {
1061                         StringBuilder sb = new StringBuilder ();
1062                         sb.Append (GetType ());
1063                         sb.Append (" (");
1064
1065                         sb.Append (id);
1066                         sb.Append (",");
1067                         sb.Append (Type);
1068                         if (Block != null) {
1069                                 sb.Append (" - ");
1070                                 sb.Append (Block.ID);
1071                                 sb.Append (" - ");
1072                                 sb.Append (Block.StartLocation);
1073                         }
1074                         sb.Append (" - ");
1075                         // sb.Append (Siblings.Length);
1076                         // sb.Append (" - ");
1077                         sb.Append (CurrentUsageVector);
1078                         sb.Append (")");
1079                         return sb.ToString ();
1080                 }
1081
1082                 public string Name {
1083                         get {
1084                                 return String.Format ("{0} ({1}:{2}:{3})",
1085                                                       GetType (), id, Type, Location);
1086                         }
1087                 }
1088         }
1089
1090         public class FlowBranchingBlock : FlowBranching
1091         {
1092                 UsageVector sibling_list = null;
1093
1094                 public FlowBranchingBlock (FlowBranching parent, BranchingType type, SiblingType stype,
1095                                            Block block, Location loc)
1096                         : base (parent, type, stype, block, loc)
1097                 { }
1098
1099                 public override UsageVector CurrentUsageVector {
1100                         get { return sibling_list; }
1101                 }
1102
1103                 protected override void AddSibling (UsageVector sibling)
1104                 {
1105                         sibling.Next = sibling_list;
1106                         sibling_list = sibling;
1107                 }
1108
1109                 public override void Label (ArrayList origin_vectors)
1110                 {
1111                         CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1112                 }
1113
1114                 protected override UsageVector Merge ()
1115                 {
1116                         return Merge (sibling_list);
1117                 }
1118         }
1119
1120         public class FlowBranchingException : FlowBranching
1121         {
1122                 UsageVector current_vector;
1123                 UsageVector try_vector;
1124                 UsageVector catch_vectors;
1125                 UsageVector finally_vector;
1126                 UsageVector finally_origins;
1127
1128                 public FlowBranchingException (FlowBranching parent, BranchingType type, Block block, Location loc)
1129                         : base (parent, type, SiblingType.Try, block, loc)
1130                 { }
1131
1132                 protected override void AddSibling (UsageVector sibling)
1133                 {
1134                         if (sibling.Type == SiblingType.Try) {
1135                                 try_vector = sibling;
1136                                 sibling.Next = catch_vectors;
1137                                 catch_vectors = sibling;
1138                         } else if (sibling.Type == SiblingType.Catch) {
1139                                 sibling.Next = catch_vectors;
1140                                 catch_vectors = sibling;
1141                         } else if (sibling.Type == SiblingType.Finally) {
1142                                 // sibling.MergeFinallyOrigins (finally_vectors);
1143                                 finally_vector = sibling;
1144                         } else
1145                                 throw new InvalidOperationException ();
1146
1147                         current_vector = sibling;
1148                 }
1149
1150                 public override UsageVector CurrentUsageVector {
1151                         get { return current_vector; }
1152                 }
1153
1154                 public override bool InTryBlock ()
1155                 {
1156                         return true;
1157                 }
1158
1159                 public override void AddFinallyVector (UsageVector vector)
1160                 {
1161                         vector = vector.Clone ();
1162                         vector.Next = finally_origins;
1163                         finally_origins = vector;
1164                 }
1165
1166                 public override void Label (ArrayList origin_vectors)
1167                 {
1168                         CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1169                 }
1170
1171                 protected override UsageVector Merge ()
1172                 {
1173                         UsageVector vector = Merge (catch_vectors);
1174
1175                         vector.MergeFinally (this, finally_vector, finally_origins);
1176
1177                         return vector;
1178                 }
1179         }
1180
1181         // <summary>
1182         //   This is used by the flow analysis code to keep track of the type of local variables
1183         //   and variables.
1184         //
1185         //   The flow code uses a BitVector to keep track of whether a variable has been assigned
1186         //   or not.  This is easy for fundamental types (int, char etc.) or reference types since
1187         //   you can only assign the whole variable as such.
1188         //
1189         //   For structs, we also need to keep track of all its fields.  To do this, we allocate one
1190         //   bit for the struct itself (it's used if you assign/access the whole struct) followed by
1191         //   one bit for each of its fields.
1192         //
1193         //   This class computes this `layout' for each type.
1194         // </summary>
1195         public class TypeInfo
1196         {
1197                 public readonly Type Type;
1198
1199                 // <summary>
1200                 //   Total number of bits a variable of this type consumes in the flow vector.
1201                 // </summary>
1202                 public readonly int TotalLength;
1203
1204                 // <summary>
1205                 //   Number of bits the simple fields of a variable of this type consume
1206                 //   in the flow vector.
1207                 // </summary>
1208                 public readonly int Length;
1209
1210                 // <summary>
1211                 //   This is only used by sub-structs.
1212                 // </summary>
1213                 public readonly int Offset;
1214
1215                 // <summary>
1216                 //   If this is a struct.
1217                 // </summary>
1218                 public readonly bool IsStruct;
1219
1220                 // <summary>
1221                 //   If this is a struct, all fields which are structs theirselves.
1222                 // </summary>
1223                 public TypeInfo[] SubStructInfo;
1224
1225                 protected readonly StructInfo struct_info;
1226                 private static Hashtable type_hash = new Hashtable ();
1227
1228                 public static TypeInfo GetTypeInfo (Type type)
1229                 {
1230                         TypeInfo info = (TypeInfo) type_hash [type];
1231                         if (info != null)
1232                                 return info;
1233
1234                         info = new TypeInfo (type);
1235                         type_hash.Add (type, info);
1236                         return info;
1237                 }
1238
1239                 public static TypeInfo GetTypeInfo (TypeContainer tc)
1240                 {
1241                         TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1242                         if (info != null)
1243                                 return info;
1244
1245                         info = new TypeInfo (tc);
1246                         type_hash.Add (tc.TypeBuilder, info);
1247                         return info;
1248                 }
1249
1250                 private TypeInfo (Type type)
1251                 {
1252                         this.Type = type;
1253
1254                         struct_info = StructInfo.GetStructInfo (type);
1255                         if (struct_info != null) {
1256                                 Length = struct_info.Length;
1257                                 TotalLength = struct_info.TotalLength;
1258                                 SubStructInfo = struct_info.StructFields;
1259                                 IsStruct = true;
1260                         } else {
1261                                 Length = 0;
1262                                 TotalLength = 1;
1263                                 IsStruct = false;
1264                         }
1265                 }
1266
1267                 private TypeInfo (TypeContainer tc)
1268                 {
1269                         this.Type = tc.TypeBuilder;
1270
1271                         struct_info = StructInfo.GetStructInfo (tc);
1272                         if (struct_info != null) {
1273                                 Length = struct_info.Length;
1274                                 TotalLength = struct_info.TotalLength;
1275                                 SubStructInfo = struct_info.StructFields;
1276                                 IsStruct = true;
1277                         } else {
1278                                 Length = 0;
1279                                 TotalLength = 1;
1280                                 IsStruct = false;
1281                         }
1282                 }
1283
1284                 protected TypeInfo (StructInfo struct_info, int offset)
1285                 {
1286                         this.struct_info = struct_info;
1287                         this.Offset = offset;
1288                         this.Length = struct_info.Length;
1289                         this.TotalLength = struct_info.TotalLength;
1290                         this.SubStructInfo = struct_info.StructFields;
1291                         this.Type = struct_info.Type;
1292                         this.IsStruct = true;
1293                 }
1294
1295                 public int GetFieldIndex (string name)
1296                 {
1297                         if (struct_info == null)
1298                                 return 0;
1299
1300                         return struct_info [name];
1301                 }
1302
1303                 public TypeInfo GetSubStruct (string name)
1304                 {
1305                         if (struct_info == null)
1306                                 return null;
1307
1308                         return struct_info.GetStructField (name);
1309                 }
1310
1311                 // <summary>
1312                 //   A struct's constructor must always assign all fields.
1313                 //   This method checks whether it actually does so.
1314                 // </summary>
1315                 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1316                 {
1317                         if (struct_info == null)
1318                                 return true;
1319
1320                         bool ok = true;
1321                         for (int i = 0; i < struct_info.Count; i++) {
1322                                 FieldInfo field = struct_info.Fields [i];
1323
1324                                 if (!branching.IsFieldAssigned (vi, field.Name)) {
1325                                         Report.Error (171, loc,
1326                                                       "Field `" + TypeManager.CSharpName (Type) +
1327                                                       "." + field.Name + "' must be fully initialized " +
1328                                                       "before control leaves the constructor");
1329                                         ok = false;
1330                                 }
1331                         }
1332
1333                         return ok;
1334                 }
1335
1336                 public override string ToString ()
1337                 {
1338                         return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1339                                               Type, Offset, Length, TotalLength);
1340                 }
1341
1342                 protected class StructInfo {
1343                         public readonly Type Type;
1344                         public readonly FieldInfo[] Fields;
1345                         public readonly TypeInfo[] StructFields;
1346                         public readonly int Count;
1347                         public readonly int CountPublic;
1348                         public readonly int CountNonPublic;
1349                         public readonly int Length;
1350                         public readonly int TotalLength;
1351                         public readonly bool HasStructFields;
1352
1353                         private static Hashtable field_type_hash = new Hashtable ();
1354                         private Hashtable struct_field_hash;
1355                         private Hashtable field_hash;
1356
1357                         protected bool InTransit = false;
1358
1359                         // Private constructor.  To save memory usage, we only need to create one instance
1360                         // of this class per struct type.
1361                         private StructInfo (Type type)
1362                         {
1363                                 this.Type = type;
1364
1365                                 field_type_hash.Add (type, this);
1366
1367                                 if (type is TypeBuilder) {
1368                                         TypeContainer tc = TypeManager.LookupTypeContainer (type);
1369
1370                                         ArrayList fields = tc.Fields;
1371
1372                                         ArrayList public_fields = new ArrayList ();
1373                                         ArrayList non_public_fields = new ArrayList ();
1374
1375                                         if (fields != null) {
1376                                                 foreach (Field field in fields) {
1377                                                         if ((field.ModFlags & Modifiers.STATIC) != 0)
1378                                                                 continue;
1379                                                         if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1380                                                                 public_fields.Add (field.FieldBuilder);
1381                                                         else
1382                                                                 non_public_fields.Add (field.FieldBuilder);
1383                                                 }
1384                                         }
1385
1386                                         CountPublic = public_fields.Count;
1387                                         CountNonPublic = non_public_fields.Count;
1388                                         Count = CountPublic + CountNonPublic;
1389
1390                                         Fields = new FieldInfo [Count];
1391                                         public_fields.CopyTo (Fields, 0);
1392                                         non_public_fields.CopyTo (Fields, CountPublic);
1393                                 } else {
1394                                         FieldInfo[] public_fields = type.GetFields (
1395                                                 BindingFlags.Instance|BindingFlags.Public);
1396                                         FieldInfo[] non_public_fields = type.GetFields (
1397                                                 BindingFlags.Instance|BindingFlags.NonPublic);
1398
1399                                         CountPublic = public_fields.Length;
1400                                         CountNonPublic = non_public_fields.Length;
1401                                         Count = CountPublic + CountNonPublic;
1402
1403                                         Fields = new FieldInfo [Count];
1404                                         public_fields.CopyTo (Fields, 0);
1405                                         non_public_fields.CopyTo (Fields, CountPublic);
1406                                 }
1407
1408                                 struct_field_hash = new Hashtable ();
1409                                 field_hash = new Hashtable ();
1410
1411                                 Length = 0;
1412                                 StructFields = new TypeInfo [Count];
1413                                 StructInfo[] sinfo = new StructInfo [Count];
1414
1415                                 InTransit = true;
1416
1417                                 for (int i = 0; i < Count; i++) {
1418                                         FieldInfo field = (FieldInfo) Fields [i];
1419
1420                                         sinfo [i] = GetStructInfo (field.FieldType);
1421                                         if (sinfo [i] == null)
1422                                                 field_hash.Add (field.Name, ++Length);
1423                                         else if (sinfo [i].InTransit) {
1424                                                 Report.Error (523, String.Format (
1425                                                                       "Struct member '{0}.{1}' of type '{2}' causes " +
1426                                                                       "a cycle in the structure layout",
1427                                                                       type, field.Name, sinfo [i].Type));
1428                                                 sinfo [i] = null;
1429                                                 return;
1430                                         }
1431                                 }
1432
1433                                 InTransit = false;
1434
1435                                 TotalLength = Length + 1;
1436                                 for (int i = 0; i < Count; i++) {
1437                                         FieldInfo field = (FieldInfo) Fields [i];
1438
1439                                         if (sinfo [i] == null)
1440                                                 continue;
1441
1442                                         field_hash.Add (field.Name, TotalLength);
1443
1444                                         HasStructFields = true;
1445                                         StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1446                                         struct_field_hash.Add (field.Name, StructFields [i]);
1447                                         TotalLength += sinfo [i].TotalLength;
1448                                 }
1449                         }
1450
1451                         public int this [string name] {
1452                                 get {
1453                                         if (field_hash.Contains (name))
1454                                                 return (int) field_hash [name];
1455                                         else
1456                                                 return 0;
1457                                 }
1458                         }
1459
1460                         public TypeInfo GetStructField (string name)
1461                         {
1462                                 return (TypeInfo) struct_field_hash [name];
1463                         }
1464
1465                         public static StructInfo GetStructInfo (Type type)
1466                         {
1467                                 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1468                                     TypeManager.IsBuiltinType (type))
1469                                         return null;
1470
1471                                 StructInfo info = (StructInfo) field_type_hash [type];
1472                                 if (info != null)
1473                                         return info;
1474
1475                                 return new StructInfo (type);
1476                         }
1477
1478                         public static StructInfo GetStructInfo (TypeContainer tc)
1479                         {
1480                                 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1481                                 if (info != null)
1482                                         return info;
1483
1484                                 return new StructInfo (tc.TypeBuilder);
1485                         }
1486                 }
1487         }
1488
1489         // <summary>
1490         //   This is used by the flow analysis code to store information about a single local variable
1491         //   or parameter.  Depending on the variable's type, we need to allocate one or more elements
1492         //   in the BitVector - if it's a fundamental or reference type, we just need to know whether
1493         //   it has been assigned or not, but for structs, we need this information for each of its fields.
1494         // </summary>
1495         public class VariableInfo {
1496                 public readonly string Name;
1497                 public readonly TypeInfo TypeInfo;
1498
1499                 // <summary>
1500                 //   The bit offset of this variable in the flow vector.
1501                 // </summary>
1502                 public readonly int Offset;
1503
1504                 // <summary>
1505                 //   The number of bits this variable needs in the flow vector.
1506                 //   The first bit always specifies whether the variable as such has been assigned while
1507                 //   the remaining bits contain this information for each of a struct's fields.
1508                 // </summary>
1509                 public readonly int Length;
1510
1511                 // <summary>
1512                 //   If this is a parameter of local variable.
1513                 // </summary>
1514                 public readonly bool IsParameter;
1515
1516                 public readonly LocalInfo LocalInfo;
1517                 public readonly int ParameterIndex;
1518
1519                 readonly VariableInfo Parent;
1520                 VariableInfo[] sub_info;
1521
1522                 protected VariableInfo (string name, Type type, int offset)
1523                 {
1524                         this.Name = name;
1525                         this.Offset = offset;
1526                         this.TypeInfo = TypeInfo.GetTypeInfo (type);
1527
1528                         Length = TypeInfo.TotalLength;
1529
1530                         Initialize ();
1531                 }
1532
1533                 protected VariableInfo (VariableInfo parent, TypeInfo type)
1534                 {
1535                         this.Name = parent.Name;
1536                         this.TypeInfo = type;
1537                         this.Offset = parent.Offset + type.Offset;
1538                         this.Parent = parent;
1539                         this.Length = type.TotalLength;
1540
1541                         this.IsParameter = parent.IsParameter;
1542                         this.LocalInfo = parent.LocalInfo;
1543                         this.ParameterIndex = parent.ParameterIndex;
1544
1545                         Initialize ();
1546                 }
1547
1548                 protected void Initialize ()
1549                 {
1550                         TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1551                         if (sub_fields != null) {
1552                                 sub_info = new VariableInfo [sub_fields.Length];
1553                                 for (int i = 0; i < sub_fields.Length; i++) {
1554                                         if (sub_fields [i] != null)
1555                                                 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1556                                 }
1557                         } else
1558                                 sub_info = new VariableInfo [0];
1559                 }
1560
1561                 public VariableInfo (LocalInfo local_info, int offset)
1562                         : this (local_info.Name, local_info.VariableType, offset)
1563                 {
1564                         this.LocalInfo = local_info;
1565                         this.IsParameter = false;
1566                 }
1567
1568                 public VariableInfo (string name, Type type, int param_idx, int offset)
1569                         : this (name, type, offset)
1570                 {
1571                         this.ParameterIndex = param_idx;
1572                         this.IsParameter = true;
1573                 }
1574
1575                 public bool IsAssigned (EmitContext ec)
1576                 {
1577                         return !ec.DoFlowAnalysis || ec.CurrentBranching.IsAssigned (this);
1578                 }
1579
1580                 public bool IsAssigned (EmitContext ec, Location loc)
1581                 {
1582                         if (IsAssigned (ec))
1583                                 return true;
1584
1585                         Report.Error (165, loc,
1586                                       "Use of unassigned local variable `" + Name + "'");
1587                         ec.CurrentBranching.SetAssigned (this);
1588                         return false;
1589                 }
1590
1591                 public bool IsAssigned (MyBitVector vector)
1592                 {
1593                         if (vector [Offset])
1594                                 return true;
1595
1596                         for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1597                                 if (vector [parent.Offset])
1598                                         return true;
1599
1600                         // Return unless this is a struct.
1601                         if (!TypeInfo.IsStruct)
1602                                 return false;
1603
1604                         // Ok, so each field must be assigned.
1605                         for (int i = 0; i < TypeInfo.Length; i++) {
1606                                 if (!vector [Offset + i + 1])
1607                                         return false;
1608                         }
1609
1610                         // Ok, now check all fields which are structs.
1611                         for (int i = 0; i < sub_info.Length; i++) {
1612                                 VariableInfo sinfo = sub_info [i];
1613                                 if (sinfo == null)
1614                                         continue;
1615
1616                                 if (!sinfo.IsAssigned (vector))
1617                                         return false;
1618                         }
1619
1620                         vector [Offset] = true;
1621                         return true;
1622                 }
1623
1624                 public void SetAssigned (EmitContext ec)
1625                 {
1626                         if (ec.DoFlowAnalysis)
1627                                 ec.CurrentBranching.SetAssigned (this);
1628                 }
1629
1630                 public void SetAssigned (MyBitVector vector)
1631                 {
1632                         vector [Offset] = true;
1633                 }
1634
1635                 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1636                 {
1637                         if (!ec.DoFlowAnalysis || ec.CurrentBranching.IsFieldAssigned (this, name))
1638                                 return true;
1639
1640                         Report.Error (170, loc,
1641                                       "Use of possibly unassigned field `" + name + "'");
1642                         ec.CurrentBranching.SetFieldAssigned (this, name);
1643                         return false;
1644                 }
1645
1646                 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1647                 {
1648                         int field_idx = TypeInfo.GetFieldIndex (field_name);
1649
1650                         if (field_idx == 0)
1651                                 return true;
1652
1653                         return vector [Offset + field_idx];
1654                 }
1655
1656                 public void SetFieldAssigned (EmitContext ec, string name)
1657                 {
1658                         if (ec.DoFlowAnalysis)
1659                                 ec.CurrentBranching.SetFieldAssigned (this, name);
1660                 }
1661
1662                 public void SetFieldAssigned (MyBitVector vector, string field_name)
1663                 {
1664                         int field_idx = TypeInfo.GetFieldIndex (field_name);
1665
1666                         if (field_idx == 0)
1667                                 return;
1668
1669                         vector [Offset + field_idx] = true;
1670                 }
1671
1672                 public VariableInfo GetSubStruct (string name)
1673                 {
1674                         TypeInfo type = TypeInfo.GetSubStruct (name);
1675
1676                         if (type == null)
1677                                 return null;
1678
1679                         return new VariableInfo (this, type);
1680                 }
1681
1682                 public override string ToString ()
1683                 {
1684                         return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1685                                               Name, TypeInfo, Offset, Length, IsParameter);
1686                 }
1687         }
1688
1689         // <summary>
1690         //   This is used by the flow code to hold the `layout' of the flow vector for
1691         //   all locals and all parameters (ie. we create one instance of this class for the
1692         //   locals and another one for the params).
1693         // </summary>
1694         public class VariableMap {
1695                 // <summary>
1696                 //   The number of variables in the map.
1697                 // </summary>
1698                 public readonly int Count;
1699
1700                 // <summary>
1701                 //   Total length of the flow vector for this map.
1702                 // <summary>
1703                 public readonly int Length;
1704
1705                 // <summary>
1706                 //   Type and name of all the variables.
1707                 //   Note that this is null for variables for which we do not need to compute
1708                 //   assignment info.
1709                 // </summary>
1710                 public readonly Type[] VariableTypes;
1711                 public readonly string[] VariableNames;
1712
1713                 VariableInfo[] map;
1714
1715                 public VariableMap (InternalParameters ip)
1716                 {
1717                         Count = ip != null ? ip.Count : 0;
1718                         map = new VariableInfo [Count];
1719                         VariableNames = new string [Count];
1720                         VariableTypes = new Type [Count];
1721                         Length = 0;
1722
1723                         for (int i = 0; i < Count; i++) {
1724                                 Parameter.Modifier mod = ip.ParameterModifier (i);
1725
1726                                 if ((mod & Parameter.Modifier.OUT) == 0)
1727                                         continue;
1728
1729                                 VariableNames [i] = ip.ParameterName (i);
1730                                 VariableTypes [i] = TypeManager.GetElementType (ip.ParameterType (i));
1731
1732                                 map [i] = new VariableInfo (VariableNames [i], VariableTypes [i], i, Length);
1733                                 Length += map [i].Length;
1734                         }
1735                 }
1736
1737                 public VariableMap (LocalInfo[] locals)
1738                         : this (null, locals)
1739                 { }
1740
1741                 public VariableMap (VariableMap parent, LocalInfo[] locals)
1742                 {
1743                         int offset = 0, start = 0;
1744                         if (parent != null) {
1745                                 offset = parent.Length;
1746                                 start = parent.Count;
1747                         }
1748
1749                         Count = locals.Length + start;
1750                         map = new VariableInfo [Count];
1751                         VariableNames = new string [Count];
1752                         VariableTypes = new Type [Count];
1753                         Length = offset;
1754
1755                         if (parent != null) {
1756                                 parent.map.CopyTo (map, 0);
1757                                 parent.VariableNames.CopyTo (VariableNames, 0);
1758                                 parent.VariableTypes.CopyTo (VariableTypes, 0);
1759                         }
1760
1761                         for (int i = start; i < Count; i++) {
1762                                 LocalInfo li = locals [i-start];
1763
1764                                 if (li.VariableType == null)
1765                                         continue;
1766
1767                                 VariableNames [i] = li.Name;
1768                                 VariableTypes [i] = li.VariableType;
1769
1770                                 map [i] = li.VariableInfo = new VariableInfo (li, Length);
1771                                 Length += map [i].Length;
1772                         }
1773                 }
1774
1775                 // <summary>
1776                 //   Returns the VariableInfo for variable @index or null if we don't need to
1777                 //   compute assignment info for this variable.
1778                 // </summary>
1779                 public VariableInfo this [int index] {
1780                         get {
1781                                 return map [index];
1782                         }
1783                 }
1784
1785                 public override string ToString ()
1786                 {
1787                         return String.Format ("VariableMap ({0}:{1})", Count, Length);
1788                 }
1789         }
1790
1791         // <summary>
1792         //   This is a special bit vector which can inherit from another bit vector doing a
1793         //   copy-on-write strategy.  The inherited vector may have a smaller size than the
1794         //   current one.
1795         // </summary>
1796         public class MyBitVector {
1797                 public readonly int Count;
1798                 public readonly MyBitVector InheritsFrom;
1799
1800                 bool is_dirty;
1801                 BitArray vector;
1802
1803                 public MyBitVector (int Count)
1804                         : this (null, Count)
1805                 { }
1806
1807                 public MyBitVector (MyBitVector InheritsFrom, int Count)
1808                 {
1809                         this.InheritsFrom = InheritsFrom;
1810                         this.Count = Count;
1811                 }
1812
1813                 // <summary>
1814                 //   Checks whether this bit vector has been modified.  After setting this to true,
1815                 //   we won't use the inherited vector anymore, but our own copy of it.
1816                 // </summary>
1817                 public bool IsDirty {
1818                         get {
1819                                 return is_dirty;
1820                         }
1821
1822                         set {
1823                                 if (!is_dirty)
1824                                         initialize_vector ();
1825                         }
1826                 }
1827
1828                 // <summary>
1829                 //   Get/set bit `index' in the bit vector.
1830                 // </summary>
1831                 public bool this [int index]
1832                 {
1833                         get {
1834                                 if (index > Count)
1835                                         throw new ArgumentOutOfRangeException ();
1836
1837                                 // We're doing a "copy-on-write" strategy here; as long
1838                                 // as nobody writes to the array, we can use our parent's
1839                                 // copy instead of duplicating the vector.
1840
1841                                 if (vector != null)
1842                                         return vector [index];
1843                                 else if (InheritsFrom != null) {
1844                                         BitArray inherited = InheritsFrom.Vector;
1845
1846                                         if (index < inherited.Count)
1847                                                 return inherited [index];
1848                                         else
1849                                                 return false;
1850                                 } else
1851                                         return false;
1852                         }
1853
1854                         set {
1855                                 if (index > Count)
1856                                         throw new ArgumentOutOfRangeException ();
1857
1858                                 // Only copy the vector if we're actually modifying it.
1859
1860                                 if (this [index] != value) {
1861                                         initialize_vector ();
1862
1863                                         vector [index] = value;
1864                                 }
1865                         }
1866                 }
1867
1868                 // <summary>
1869                 //   If you explicitly convert the MyBitVector to a BitArray, you will get a deep
1870                 //   copy of the bit vector.
1871                 // </summary>
1872                 public static explicit operator BitArray (MyBitVector vector)
1873                 {
1874                         vector.initialize_vector ();
1875                         return vector.Vector;
1876                 }
1877
1878                 // <summary>
1879                 //   Performs an `or' operation on the bit vector.  The `new_vector' may have a
1880                 //   different size than the current one.
1881                 // </summary>
1882                 public void Or (MyBitVector new_vector)
1883                 {
1884                         BitArray new_array = new_vector.Vector;
1885
1886                         initialize_vector ();
1887
1888                         int upper;
1889                         if (vector.Count < new_array.Count)
1890                                 upper = vector.Count;
1891                         else
1892                                 upper = new_array.Count;
1893
1894                         for (int i = 0; i < upper; i++)
1895                                 vector [i] = vector [i] | new_array [i];
1896                 }
1897
1898                 // <summary>
1899                 //   Perfonrms an `and' operation on the bit vector.  The `new_vector' may have
1900                 //   a different size than the current one.
1901                 // </summary>
1902                 public void And (MyBitVector new_vector)
1903                 {
1904                         BitArray new_array = new_vector.Vector;
1905
1906                         initialize_vector ();
1907
1908                         int lower, upper;
1909                         if (vector.Count < new_array.Count)
1910                                 lower = upper = vector.Count;
1911                         else {
1912                                 lower = new_array.Count;
1913                                 upper = vector.Count;
1914                         }
1915
1916                         for (int i = 0; i < lower; i++)
1917                                 vector [i] = vector [i] & new_array [i];
1918
1919                         for (int i = lower; i < upper; i++)
1920                                 vector [i] = false;
1921                 }
1922
1923                 public static void And (ref MyBitVector target, MyBitVector vector)
1924                 {
1925                         if (target != null)
1926                                 target.And (vector);
1927                         else
1928                                 target = vector.Clone ();
1929                 }
1930
1931                 public static void Or (ref MyBitVector target, MyBitVector vector)
1932                 {
1933                         if (target != null)
1934                                 target.Or (vector);
1935                         else
1936                                 target = vector.Clone ();
1937                 }
1938
1939                 // <summary>
1940                 //   This does a deep copy of the bit vector.
1941                 // </summary>
1942                 public MyBitVector Clone ()
1943                 {
1944                         MyBitVector retval = new MyBitVector (Count);
1945
1946                         retval.Vector = Vector;
1947
1948                         return retval;
1949                 }
1950
1951                 BitArray Vector {
1952                         get {
1953                                 if (vector != null)
1954                                         return vector;
1955                                 else if (!is_dirty && (InheritsFrom != null))
1956                                         return InheritsFrom.Vector;
1957
1958                                 initialize_vector ();
1959
1960                                 return vector;
1961                         }
1962
1963                         set {
1964                                 initialize_vector ();
1965
1966                                 for (int i = 0; i < System.Math.Min (vector.Count, value.Count); i++)
1967                                         vector [i] = value [i];
1968                         }
1969                 }
1970
1971                 void initialize_vector ()
1972                 {
1973                         if (vector != null)
1974                                 return;
1975
1976                         vector = new BitArray (Count, false);
1977                         if (InheritsFrom != null)
1978                                 Vector = InheritsFrom.Vector;
1979
1980                         is_dirty = true;
1981                 }
1982
1983                 public override string ToString ()
1984                 {
1985                         StringBuilder sb = new StringBuilder ("{");
1986
1987                         BitArray vector = Vector;
1988                         if (!IsDirty)
1989                                 sb.Append ("=");
1990                         for (int i = 0; i < vector.Count; i++) {
1991                                 sb.Append (vector [i] ? "1" : "0");
1992                         }
1993
1994                         sb.Append ("}");
1995                         return sb.ToString ();
1996                 }
1997         }
1998 }