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