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