mcs/mcs/flowanalysis.cs

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