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