mcs/gmcs/flowanalysis.cs

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