2 // flowanalyis.cs: The control flow analysis code
5 // Martin Baulig (martin@ximian.com)
7 // (C) 2001, 2002, 2003 Ximian, Inc.
12 using System
.Collections
;
13 using System
.Reflection
;
14 using System
.Reflection
.Emit
;
15 using System
.Diagnostics
;
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.
23 public abstract class FlowBranching
26 // The type of a FlowBranching.
28 public enum BranchingType
: byte {
29 // Normal (conditional or toplevel) block.
49 // The type of one sibling of a branching.
51 public enum SiblingType
: byte {
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
65 public enum FlowReturns
: byte {
68 // It can never return.
71 // This means that the block contains a conditional return statement
75 // The code always returns, ie. there's an unconditional return / break
80 public sealed class Reachability
82 FlowReturns returns
, breaks
, throws
, barrier
;
84 public FlowReturns Returns
{
85 get { return returns; }
87 public FlowReturns Breaks
{
88 get { return breaks; }
90 public FlowReturns Throws
{
91 get { return throws; }
93 public FlowReturns Barrier
{
94 get { return barrier; }
96 public Reachability (FlowReturns returns
, FlowReturns breaks
,
97 FlowReturns throws
, FlowReturns barrier
)
99 this.returns
= returns
;
100 this.breaks
= breaks
;
101 this.throws
= throws
;
102 this.barrier
= barrier
;
105 public Reachability
Clone ()
107 return new Reachability (returns
, breaks
, throws
, barrier
);
111 // Performs an `And' operation on the FlowReturns status
112 // (for instance, a block only returns Always if all its siblings
115 public static FlowReturns
AndFlowReturns (FlowReturns a
, FlowReturns b
)
117 if (a
== FlowReturns
.Undefined
)
121 case FlowReturns
.Never
:
122 if (b
== FlowReturns
.Never
)
123 return FlowReturns
.Never
;
125 return FlowReturns
.Sometimes
;
127 case FlowReturns
.Sometimes
:
128 return FlowReturns
.Sometimes
;
130 case FlowReturns
.Always
:
131 if (b
== FlowReturns
.Always
)
132 return FlowReturns
.Always
;
134 return FlowReturns
.Sometimes
;
137 throw new ArgumentException ();
141 public static FlowReturns
OrFlowReturns (FlowReturns a
, FlowReturns b
)
143 if (a
== FlowReturns
.Undefined
)
147 case FlowReturns
.Never
:
150 case FlowReturns
.Sometimes
:
151 if (b
== FlowReturns
.Always
)
152 return FlowReturns
.Always
;
154 return FlowReturns
.Sometimes
;
156 case FlowReturns
.Always
:
157 return FlowReturns
.Always
;
160 throw new ArgumentException ();
164 public static void And (ref Reachability a
, Reachability b
, bool do_break
)
172 // `break' does not "break" in a Switch or a LoopBlock
174 bool a_breaks
= do_break
&& a
.AlwaysBreaks
;
175 bool b_breaks
= do_break
&& b
.AlwaysBreaks
;
177 bool a_has_barrier
, b_has_barrier
;
180 // This is the normal case: the code following a barrier
181 // cannot be reached.
183 a_has_barrier
= a
.AlwaysHasBarrier
;
184 b_has_barrier
= b
.AlwaysHasBarrier
;
187 // Special case for Switch and LoopBlocks: we can reach the
188 // code after the barrier via the `break'.
190 a_has_barrier
= !a
.AlwaysBreaks
&& a
.AlwaysHasBarrier
;
191 b_has_barrier
= !b
.AlwaysBreaks
&& b
.AlwaysHasBarrier
;
194 bool a_unreachable
= a_breaks
|| a
.AlwaysThrows
|| a_has_barrier
;
195 bool b_unreachable
= b_breaks
|| b
.AlwaysThrows
|| b_has_barrier
;
198 // Do all code paths always return ?
200 if (a
.AlwaysReturns
) {
201 if (b
.AlwaysReturns
|| b_unreachable
)
202 a
.returns
= FlowReturns
.Always
;
204 a
.returns
= FlowReturns
.Sometimes
;
205 } else if (b
.AlwaysReturns
) {
206 if (a
.AlwaysReturns
|| a_unreachable
)
207 a
.returns
= FlowReturns
.Always
;
209 a
.returns
= FlowReturns
.Sometimes
;
210 } else if (!a
.MayReturn
) {
212 a
.returns
= FlowReturns
.Sometimes
;
214 a
.returns
= FlowReturns
.Never
;
215 } else if (!b
.MayReturn
) {
217 a
.returns
= FlowReturns
.Sometimes
;
219 a
.returns
= FlowReturns
.Never
;
222 a
.breaks
= AndFlowReturns (a
.breaks
, b
.breaks
);
223 a
.throws
= AndFlowReturns (a
.throws
, b
.throws
);
224 a
.barrier
= AndFlowReturns (a
.barrier
, b
.barrier
);
226 if (a_unreachable
&& b_unreachable
)
227 a
.barrier
= FlowReturns
.Always
;
228 else if (a_unreachable
|| b_unreachable
)
229 a
.barrier
= FlowReturns
.Sometimes
;
231 a
.barrier
= FlowReturns
.Never
;
234 public void Or (Reachability b
)
236 returns
= OrFlowReturns (returns
, b
.returns
);
237 breaks
= OrFlowReturns (breaks
, b
.breaks
);
238 throws
= OrFlowReturns (throws
, b
.throws
);
239 barrier
= OrFlowReturns (barrier
, b
.barrier
);
242 public static Reachability
Never ()
244 return new Reachability (
245 FlowReturns
.Never
, FlowReturns
.Never
,
246 FlowReturns
.Never
, FlowReturns
.Never
);
249 public FlowReturns Reachable
{
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
;
262 return FlowReturns
.Sometimes
;
266 public bool AlwaysBreaks
{
267 get { return breaks == FlowReturns.Always; }
270 public bool MayBreak
{
271 get { return breaks != FlowReturns.Never; }
274 public bool AlwaysReturns
{
275 get { return returns == FlowReturns.Always; }
278 public bool MayReturn
{
279 get { return returns != FlowReturns.Never; }
282 public bool AlwaysThrows
{
283 get { return throws == FlowReturns.Always; }
286 public bool MayThrow
{
287 get { return throws != FlowReturns.Never; }
290 public bool AlwaysHasBarrier
{
291 get { return barrier == FlowReturns.Always; }
294 public bool MayHaveBarrier
{
295 get { return barrier != FlowReturns.Never; }
298 public bool IsUnreachable
{
299 get { return Reachable == FlowReturns.Never; }
302 public void SetReturns ()
304 returns
= FlowReturns
.Always
;
307 public void SetReturnsSometimes ()
309 returns
= FlowReturns
.Sometimes
;
312 public void SetBreaks ()
314 breaks
= FlowReturns
.Always
;
317 public void ResetBreaks ()
319 breaks
= FlowReturns
.Never
;
322 public void SetThrows ()
324 throws
= FlowReturns
.Always
;
327 public void SetThrowsSometimes ()
329 throws
= FlowReturns
.Sometimes
;
332 public void SetBarrier ()
334 barrier
= FlowReturns
.Always
;
337 public void ResetBarrier ()
339 barrier
= FlowReturns
.Never
;
342 static string ShortName (FlowReturns returns
)
345 case FlowReturns
.Never
:
347 case FlowReturns
.Sometimes
:
354 public override string ToString ()
356 return String
.Format ("[{0}:{1}:{2}:{3}:{4}]",
357 ShortName (returns
), ShortName (breaks
),
358 ShortName (throws
), ShortName (barrier
),
359 ShortName (Reachable
));
363 public static FlowBranching
CreateBranching (FlowBranching parent
, BranchingType type
, Block block
, Location loc
)
366 case BranchingType
.Exception
:
367 throw new InvalidOperationException ();
369 case BranchingType
.Switch
:
370 return new FlowBranchingBlock (parent
, type
, SiblingType
.SwitchSection
, block
, loc
);
372 case BranchingType
.SwitchSection
:
373 return new FlowBranchingBlock (parent
, type
, SiblingType
.Block
, block
, loc
);
375 case BranchingType
.Block
:
376 return new FlowBranchingBlock (parent
, type
, SiblingType
.Block
, block
, loc
);
378 case BranchingType
.Loop
:
379 return new FlowBranchingLoop (parent
, block
, loc
);
382 return new FlowBranchingBlock (parent
, type
, SiblingType
.Conditional
, block
, loc
);
387 // The type of this flow branching.
389 public readonly BranchingType Type
;
392 // The block this branching is contained in. This may be null if it's not
393 // a top-level block and it doesn't declare any local variables.
395 public readonly Block Block
;
398 // The parent of this branching or null if this is the top-block.
400 public readonly FlowBranching Parent
;
403 // Start-Location of this flow branching.
405 public readonly Location Location
;
408 // If this is an infinite loop.
410 public bool Infinite
;
415 VariableMap param_map
, local_map
;
417 static int next_id
= 0;
421 // The vector contains a BitArray with information about which local variables
422 // and parameters are already initialized at the current code position.
424 public class UsageVector
{
426 // The type of this branching.
428 public readonly SiblingType Type
;
431 // Start location of this branching.
433 public readonly Location Location
;
436 // This is only valid for SwitchSection, Try, Catch and Finally.
438 public readonly Block Block
;
441 // If this is true, then the usage vector has been modified and must be
442 // merged when we're done with this branching.
447 // The number of parameters in this block.
449 public readonly int CountParameters
;
452 // The number of locals in this block.
454 public readonly int CountLocals
;
457 // If not null, then we inherit our state from this vector and do a
458 // copy-on-write. If null, then we're the first sibling in a top-level
459 // block and inherit from the empty vector.
461 public readonly UsageVector InheritsFrom
;
464 // This is used to construct a list of UsageVector's.
466 public UsageVector Next
;
471 MyBitVector locals
, parameters
;
472 Reachability reachability
;
474 static int next_id
= 0;
478 // Normally, you should not use any of these constructors.
480 public UsageVector (SiblingType type
, UsageVector parent
,
481 Block block
, Location loc
,
482 int num_params
, int num_locals
)
487 this.InheritsFrom
= parent
;
488 this.CountParameters
= num_params
;
489 this.CountLocals
= num_locals
;
491 if (parent
!= null) {
493 locals
= new MyBitVector (parent
.locals
, CountLocals
);
496 parameters
= new MyBitVector (parent
.parameters
, num_params
);
498 reachability
= parent
.Reachability
.Clone ();
501 locals
= new MyBitVector (null, CountLocals
);
504 parameters
= new MyBitVector (null, num_params
);
506 reachability
= Reachability
.Never ();
512 public UsageVector (SiblingType type
, UsageVector parent
,
513 Block block
, Location loc
)
514 : this (type
, parent
, block
, loc
,
515 parent
.CountParameters
, parent
.CountLocals
)
518 public UsageVector (MyBitVector parameters
, MyBitVector locals
,
519 Reachability reachability
, Block block
,
522 this.Type
= SiblingType
.Block
;
526 this.reachability
= reachability
;
527 this.parameters
= parameters
;
528 this.locals
= locals
;
534 // This does a deep copy of the usage vector.
536 public UsageVector
Clone ()
538 UsageVector retval
= new UsageVector (
539 Type
, null, Block
, Location
,
540 CountParameters
, CountLocals
);
542 if (retval
.locals
!= null)
543 retval
.locals
= locals
.Clone ();
545 if (parameters
!= null)
546 retval
.parameters
= parameters
.Clone ();
548 retval
.reachability
= reachability
.Clone ();
553 public bool IsAssigned (VariableInfo
var)
555 if (!var.IsParameter
&& Reachability
.IsUnreachable
)
558 return var.IsAssigned (var.IsParameter
? parameters
: locals
);
561 public void SetAssigned (VariableInfo
var)
563 if (!var.IsParameter
&& Reachability
.IsUnreachable
)
567 var.SetAssigned (var.IsParameter
? parameters
: locals
);
570 public bool IsFieldAssigned (VariableInfo
var, string name
)
572 if (!var.IsParameter
&& Reachability
.IsUnreachable
)
575 return var.IsFieldAssigned (var.IsParameter
? parameters
: locals
, name
);
578 public void SetFieldAssigned (VariableInfo
var, string name
)
580 if (!var.IsParameter
&& Reachability
.IsUnreachable
)
584 var.SetFieldAssigned (var.IsParameter
? parameters
: locals
, name
);
587 public Reachability Reachability
{
593 public void Return ()
595 if (!reachability
.IsUnreachable
) {
597 reachability
.SetReturns ();
603 if (!reachability
.IsUnreachable
) {
605 reachability
.SetBreaks ();
611 if (!reachability
.IsUnreachable
) {
613 reachability
.SetThrows ();
619 if (!reachability
.IsUnreachable
) {
621 reachability
.SetBarrier ();
626 // Merges a child branching.
628 public UsageVector
MergeChild (FlowBranching branching
)
630 UsageVector result
= branching
.Merge ();
632 Report
.Debug (2, " MERGING CHILD", this, branching
, IsDirty
,
633 result
.ParameterVector
, result
.LocalVector
,
634 result
.Reachability
, reachability
, Type
);
636 Reachability new_r
= result
.Reachability
;
638 if (branching
.Type
== BranchingType
.Loop
) {
639 bool may_leave_loop
= new_r
.MayBreak
;
640 new_r
.ResetBreaks ();
642 if (branching
.Infinite
&& !may_leave_loop
) {
643 if (new_r
.Returns
== FlowReturns
.Sometimes
) {
644 // If we're an infinite loop and do not break,
645 // the code after the loop can never be reached.
646 // However, if we may return from the loop,
647 // then we do always return (or stay in the
654 if (new_r
.Returns
== FlowReturns
.Always
) {
655 // We're either finite or we may leave the loop.
656 new_r
.SetReturnsSometimes ();
658 if (new_r
.Throws
== FlowReturns
.Always
) {
659 // We're either finite or we may leave the loop.
660 new_r
.SetThrowsSometimes ();
663 if (!new_r
.MayReturn
&& !new_r
.MayThrow
)
664 new_r
.ResetBarrier ();
666 } else if (branching
.Type
== BranchingType
.Switch
) {
667 if (new_r
.MayBreak
|| new_r
.MayReturn
)
668 new_r
.ResetBarrier ();
670 new_r
.ResetBreaks ();
674 // We've now either reached the point after the branching or we will
675 // never get there since we always return or always throw an exception.
677 // If we can reach the point after the branching, mark all locals and
678 // parameters as initialized which have been initialized in all branches
679 // we need to look at (see above).
682 if ((Type
== SiblingType
.SwitchSection
) && !new_r
.IsUnreachable
) {
683 Report
.Error (163, Location
,
684 "Control cannot fall through from one " +
685 "case label to another");
689 if (locals
!= null && result
.LocalVector
!= null)
690 locals
.Or (result
.LocalVector
);
692 if (result
.ParameterVector
!= null)
693 parameters
.Or (result
.ParameterVector
);
695 reachability
.Or (new_r
);
697 Report
.Debug (2, " MERGING CHILD DONE", this, result
,
698 new_r
, reachability
);
705 protected void MergeFinally (FlowBranching branching
, UsageVector f_origins
,
706 MyBitVector f_params
)
708 for (UsageVector vector
= f_origins
; vector
!= null; vector
= vector
.Next
) {
709 MyBitVector temp_params
= f_params
.Clone ();
710 temp_params
.Or (vector
.Parameters
);
714 public void MergeFinally (FlowBranching branching
, UsageVector f_vector
,
715 UsageVector f_origins
)
717 if (parameters
!= null) {
718 if (f_vector
!= null) {
719 MergeFinally (branching
, f_origins
, f_vector
.Parameters
);
720 MyBitVector
.Or (ref parameters
, f_vector
.ParameterVector
);
722 MergeFinally (branching
, f_origins
, parameters
);
725 if (f_vector
!= null && f_vector
.LocalVector
!= null)
726 MyBitVector
.Or (ref locals
, f_vector
.LocalVector
);
730 // Tells control flow analysis that the current code position may be reached with
731 // a forward jump from any of the origins listed in `origin_vectors' which is a
732 // list of UsageVectors.
734 // This is used when resolving forward gotos - in the following example, the
735 // variable `a' is uninitialized in line 8 becase this line may be reached via
736 // the goto in line 4:
746 // 8 Console.WriteLine (a);
749 public void MergeJumpOrigins (UsageVector o_vectors
)
751 Report
.Debug (1, " MERGING JUMP ORIGINS", this);
753 reachability
= Reachability
.Never ();
755 if (o_vectors
== null) {
756 reachability
.SetBarrier ();
762 for (UsageVector vector
= o_vectors
; vector
!= null;
763 vector
= vector
.Next
) {
764 Report
.Debug (1, " MERGING JUMP ORIGIN", vector
);
767 if (locals
!= null && vector
.Locals
!= null)
768 locals
.Or (vector
.locals
);
770 if (parameters
!= null)
771 parameters
.Or (vector
.parameters
);
774 if (locals
!= null && vector
.Locals
!= null)
775 locals
.And (vector
.locals
);
776 if (parameters
!= null)
777 parameters
.And (vector
.parameters
);
780 Reachability
.And (ref reachability
, vector
.Reachability
, true);
783 Report
.Debug (1, " MERGING JUMP ORIGINS DONE", this);
787 // This is used at the beginning of a finally block if there were
788 // any return statements in the try block or one of the catch blocks.
790 public void MergeFinallyOrigins (UsageVector f_origins
)
792 Report
.Debug (1, " MERGING FINALLY ORIGIN", this);
794 reachability
= Reachability
.Never ();
796 for (UsageVector vector
= f_origins
; vector
!= null; vector
= vector
.Next
) {
797 Report
.Debug (1, " MERGING FINALLY ORIGIN", vector
);
799 if (parameters
!= null)
800 parameters
.And (vector
.parameters
);
802 Reachability
.And (ref reachability
, vector
.Reachability
, true);
805 Report
.Debug (1, " MERGING FINALLY ORIGIN DONE", this);
808 public void MergeBreakOrigins (UsageVector o_vectors
)
810 Report
.Debug (1, " MERGING BREAK ORIGINS", this);
812 if (o_vectors
== null)
817 for (UsageVector vector
= o_vectors
; vector
!= null;
818 vector
= vector
.Next
) {
819 Report
.Debug (1, " MERGING BREAK ORIGIN", vector
);
822 if (locals
!= null && vector
.Locals
!= null)
823 locals
.Or (vector
.locals
);
825 if (parameters
!= null)
826 parameters
.Or (vector
.parameters
);
829 if (locals
!= null && vector
.Locals
!= null)
830 locals
.And (vector
.locals
);
831 if (parameters
!= null)
832 parameters
.And (vector
.parameters
);
836 Report
.Debug (1, " MERGING BREAK ORIGINS DONE", this);
839 public void CheckOutParameters (FlowBranching branching
)
841 if (parameters
!= null)
842 branching
.CheckOutParameters (parameters
, branching
.Location
);
846 // Performs an `or' operation on the locals and the parameters.
848 public void Or (UsageVector new_vector
)
851 locals
.Or (new_vector
.locals
);
852 if (parameters
!= null)
853 parameters
.Or (new_vector
.parameters
);
857 // Performs an `and' operation on the locals.
859 public void AndLocals (UsageVector new_vector
)
862 locals
.And (new_vector
.locals
);
865 public bool HasParameters
{
867 return parameters
!= null;
871 public bool HasLocals
{
873 return locals
!= null;
878 // Returns a deep copy of the parameters.
880 public MyBitVector Parameters
{
882 if (parameters
!= null)
883 return parameters
.Clone ();
890 // Returns a deep copy of the locals.
892 public MyBitVector Locals
{
895 return locals
.Clone ();
901 public MyBitVector ParameterVector
{
907 public MyBitVector LocalVector
{
917 public override string ToString ()
919 StringBuilder sb
= new StringBuilder ();
921 sb
.Append ("Vector (");
928 sb
.Append (reachability
);
929 if (parameters
!= null) {
931 sb
.Append (parameters
);
937 return sb
.ToString ();
942 // Creates a new flow branching which is contained in `parent'.
943 // You should only pass non-null for the `block' argument if this block
944 // introduces any new variables - in this case, we need to create a new
945 // usage vector with a different size than our parent's one.
947 protected FlowBranching (FlowBranching parent
, BranchingType type
, SiblingType stype
,
948 Block block
, Location loc
)
958 param_map
= Block
.ParameterMap
;
959 local_map
= Block
.LocalMap
;
961 UsageVector parent_vector
= parent
!= null ? parent
.CurrentUsageVector
: null;
962 vector
= new UsageVector (
963 stype
, parent_vector
, Block
, loc
,
964 param_map
.Length
, local_map
.Length
);
966 param_map
= Parent
.param_map
;
967 local_map
= Parent
.local_map
;
968 vector
= new UsageVector (
969 stype
, Parent
.CurrentUsageVector
, null, loc
);
975 public abstract UsageVector CurrentUsageVector
{
980 // Creates a sibling of the current usage vector.
982 public virtual void CreateSibling (Block block
, SiblingType type
)
984 UsageVector vector
= new UsageVector (
985 type
, Parent
.CurrentUsageVector
, block
, Location
);
988 Report
.Debug (1, " CREATED SIBLING", CurrentUsageVector
);
991 public void CreateSibling ()
993 CreateSibling (null, SiblingType
.Conditional
);
996 protected abstract void AddSibling (UsageVector uv
);
998 public virtual LabeledStatement
LookupLabel (string name
, Location loc
)
1001 return Parent
.LookupLabel (name
, loc
);
1005 "No such label `" + name
+ "' in this scope");
1009 public abstract void Label (UsageVector origin_vectors
);
1012 // Check whether all `out' parameters have been assigned.
1014 public void CheckOutParameters (MyBitVector parameters
, Location loc
)
1016 for (int i
= 0; i
< param_map
.Count
; i
++) {
1017 VariableInfo
var = param_map
[i
];
1022 if (var.IsAssigned (parameters
))
1025 Report
.Error (177, loc
, "The out parameter `" +
1026 var.Name
+ "' must be " +
1027 "assigned before control leaves the current method.");
1031 protected UsageVector
Merge (UsageVector sibling_list
)
1033 if (sibling_list
.Next
== null)
1034 return sibling_list
;
1036 MyBitVector locals
= null;
1037 MyBitVector parameters
= null;
1039 Reachability reachability
= null;
1041 Report
.Debug (2, " MERGING SIBLINGS", this, Name
);
1043 for (UsageVector child
= sibling_list
; child
!= null; child
= child
.Next
) {
1044 bool do_break
= (Type
!= BranchingType
.Switch
) &&
1045 (Type
!= BranchingType
.Loop
);
1047 Report
.Debug (2, " MERGING SIBLING ", child
,
1048 child
.ParameterVector
, child
.LocalVector
,
1049 reachability
, child
.Reachability
, do_break
);
1051 Reachability
.And (ref reachability
, child
.Reachability
, do_break
);
1053 // A local variable is initialized after a flow branching if it
1054 // has been initialized in all its branches which do neither
1055 // always return or always throw an exception.
1057 // If a branch may return, but does not always return, then we
1058 // can treat it like a never-returning branch here: control will
1059 // only reach the code position after the branching if we did not
1062 // It's important to distinguish between always and sometimes
1063 // returning branches here:
1066 // 2 if (something) {
1070 // 6 Console.WriteLine (a);
1072 // The if block in lines 3-4 always returns, so we must not look
1073 // at the initialization of `a' in line 4 - thus it'll still be
1074 // uninitialized in line 6.
1076 // On the other hand, the following is allowed:
1083 // 6 Console.WriteLine (a);
1085 // Here, `a' is initialized in line 3 and we must not look at
1086 // line 5 since it always returns.
1088 bool do_break_2
= (child
.Type
!= SiblingType
.Block
) &&
1089 (child
.Type
!= SiblingType
.SwitchSection
);
1090 bool always_throws
= (child
.Type
!= SiblingType
.Try
) &&
1091 child
.Reachability
.AlwaysThrows
;
1092 bool unreachable
= always_throws
||
1093 (do_break_2
&& child
.Reachability
.AlwaysBreaks
) ||
1094 child
.Reachability
.AlwaysReturns
||
1095 child
.Reachability
.AlwaysHasBarrier
;
1097 Report
.Debug (2, " MERGING SIBLING #1", reachability
,
1098 Type
, child
.Type
, child
.Reachability
.IsUnreachable
,
1099 do_break_2
, always_throws
, unreachable
);
1101 if (!unreachable
&& (child
.LocalVector
!= null))
1102 MyBitVector
.And (ref locals
, child
.LocalVector
);
1104 // An `out' parameter must be assigned in all branches which do
1105 // not always throw an exception.
1106 if ((child
.ParameterVector
!= null) && !child
.Reachability
.AlwaysThrows
)
1107 MyBitVector
.And (ref parameters
, child
.ParameterVector
);
1109 Report
.Debug (2, " MERGING SIBLING #2", parameters
, locals
);
1112 if (reachability
== null)
1113 reachability
= Reachability
.Never ();
1115 Report
.Debug (2, " MERGING SIBLINGS DONE", parameters
, locals
,
1116 reachability
, Infinite
);
1118 return new UsageVector (
1119 parameters
, locals
, reachability
, null, Location
);
1122 protected abstract UsageVector
Merge ();
1125 // Merge a child branching.
1127 public UsageVector
MergeChild (FlowBranching child
)
1129 return CurrentUsageVector
.MergeChild (child
);
1133 // Does the toplevel merging.
1135 public Reachability
MergeTopBlock ()
1137 if ((Type
!= BranchingType
.Block
) || (Block
== null))
1138 throw new NotSupportedException ();
1140 UsageVector vector
= new UsageVector (
1141 SiblingType
.Conditional
, null, Block
, Location
,
1142 param_map
.Length
, local_map
.Length
);
1144 UsageVector result
= vector
.MergeChild (this);
1146 Report
.Debug (4, "MERGE TOP BLOCK", Location
, vector
, result
.Reachability
);
1148 if ((vector
.Reachability
.Throws
!= FlowReturns
.Always
) &&
1149 (vector
.Reachability
.Barrier
!= FlowReturns
.Always
))
1150 CheckOutParameters (vector
.Parameters
, Location
);
1152 return result
.Reachability
;
1156 // Checks whether we're in a `try' block.
1158 public virtual bool InTryOrCatch (bool is_return
)
1160 if ((Block
!= null) && Block
.IsDestructor
)
1162 else if (!is_return
&&
1163 ((Type
== BranchingType
.Loop
) || (Type
== BranchingType
.Switch
)))
1165 else if (Parent
!= null)
1166 return Parent
.InTryOrCatch (is_return
);
1172 // Checks whether we're in a `catch' block.
1174 public virtual bool InCatch ()
1177 return Parent
.InCatch ();
1183 // Checks whether we're in a `finally' block.
1185 public virtual bool InFinally (bool is_return
)
1188 ((Type
== BranchingType
.Loop
) || (Type
== BranchingType
.Switch
)))
1190 else if (Parent
!= null)
1191 return Parent
.InFinally (is_return
);
1196 public virtual bool InLoop ()
1198 if (Type
== BranchingType
.Loop
)
1200 else if (Parent
!= null)
1201 return Parent
.InLoop ();
1206 public virtual bool InSwitch ()
1208 if (Type
== BranchingType
.Switch
)
1210 else if (Parent
!= null)
1211 return Parent
.InSwitch ();
1216 public virtual bool BreakCrossesTryCatchBoundary ()
1218 if ((Type
== BranchingType
.Loop
) || (Type
== BranchingType
.Switch
))
1220 else if (Parent
!= null)
1221 return Parent
.BreakCrossesTryCatchBoundary ();
1226 public virtual void AddFinallyVector (UsageVector vector
)
1229 Parent
.AddFinallyVector (vector
);
1230 else if ((Block
== null) || !Block
.IsDestructor
)
1231 throw new NotSupportedException ();
1234 public virtual void AddBreakVector (UsageVector vector
)
1237 Parent
.AddBreakVector (vector
);
1238 else if ((Block
== null) || !Block
.IsDestructor
)
1239 throw new NotSupportedException ();
1242 public virtual void StealFinallyClauses (ref ArrayList list
)
1245 Parent
.StealFinallyClauses (ref list
);
1248 public bool IsAssigned (VariableInfo vi
)
1250 return CurrentUsageVector
.IsAssigned (vi
);
1253 public bool IsFieldAssigned (VariableInfo vi
, string field_name
)
1255 if (CurrentUsageVector
.IsAssigned (vi
))
1258 return CurrentUsageVector
.IsFieldAssigned (vi
, field_name
);
1261 public void SetAssigned (VariableInfo vi
)
1263 CurrentUsageVector
.SetAssigned (vi
);
1266 public void SetFieldAssigned (VariableInfo vi
, string name
)
1268 CurrentUsageVector
.SetFieldAssigned (vi
, name
);
1271 public override string ToString ()
1273 StringBuilder sb
= new StringBuilder ();
1274 sb
.Append (GetType ());
1280 if (Block
!= null) {
1282 sb
.Append (Block
.ID
);
1284 sb
.Append (Block
.StartLocation
);
1287 // sb.Append (Siblings.Length);
1288 // sb.Append (" - ");
1289 sb
.Append (CurrentUsageVector
);
1291 return sb
.ToString ();
1294 public string Name
{
1296 return String
.Format ("{0} ({1}:{2}:{3})",
1297 GetType (), id
, Type
, Location
);
1302 public class FlowBranchingBlock
: FlowBranching
1304 UsageVector sibling_list
= null;
1306 public FlowBranchingBlock (FlowBranching parent
, BranchingType type
,
1307 SiblingType stype
, Block block
, Location loc
)
1308 : base (parent
, type
, stype
, block
, loc
)
1311 public override UsageVector CurrentUsageVector
{
1312 get { return sibling_list; }
1315 protected override void AddSibling (UsageVector sibling
)
1317 sibling
.Next
= sibling_list
;
1318 sibling_list
= sibling
;
1321 public override LabeledStatement
LookupLabel (string name
, Location loc
)
1324 return base.LookupLabel (name
, loc
);
1326 LabeledStatement s
= Block
.LookupLabel (name
);
1330 return base.LookupLabel (name
, loc
);
1333 public override void Label (UsageVector origin_vectors
)
1335 if (!CurrentUsageVector
.Reachability
.IsUnreachable
) {
1336 UsageVector vector
= CurrentUsageVector
.Clone ();
1337 vector
.Next
= origin_vectors
;
1338 origin_vectors
= vector
;
1341 CurrentUsageVector
.MergeJumpOrigins (origin_vectors
);
1344 protected override UsageVector
Merge ()
1346 return Merge (sibling_list
);
1350 public class FlowBranchingLoop
: FlowBranchingBlock
1352 UsageVector break_origins
;
1354 public FlowBranchingLoop (FlowBranching parent
, Block block
, Location loc
)
1355 : base (parent
, BranchingType
.Loop
, SiblingType
.Conditional
, block
, loc
)
1358 public override void AddBreakVector (UsageVector vector
)
1360 vector
= vector
.Clone ();
1361 vector
.Next
= break_origins
;
1362 break_origins
= vector
;
1365 protected override UsageVector
Merge ()
1367 UsageVector vector
= base.Merge ();
1369 vector
.MergeBreakOrigins (break_origins
);
1375 public class FlowBranchingException
: FlowBranching
1377 ExceptionStatement stmt
;
1378 UsageVector current_vector
;
1379 UsageVector catch_vectors
;
1380 UsageVector finally_vector
;
1381 UsageVector finally_origins
;
1385 public FlowBranchingException (FlowBranching parent
,
1386 ExceptionStatement stmt
)
1387 : base (parent
, BranchingType
.Exception
, SiblingType
.Try
,
1391 this.emit_finally
= true;
1394 protected override void AddSibling (UsageVector sibling
)
1396 if (sibling
.Type
== SiblingType
.Try
) {
1397 sibling
.Next
= catch_vectors
;
1398 catch_vectors
= sibling
;
1400 } else if (sibling
.Type
== SiblingType
.Catch
) {
1401 sibling
.Next
= catch_vectors
;
1402 catch_vectors
= sibling
;
1404 } else if (sibling
.Type
== SiblingType
.Finally
) {
1405 sibling
.MergeFinallyOrigins (finally_origins
);
1406 finally_vector
= sibling
;
1409 throw new InvalidOperationException ();
1411 current_vector
= sibling
;
1414 public override UsageVector CurrentUsageVector
{
1415 get { return current_vector; }
1418 public override bool InTryOrCatch (bool is_return
)
1420 return finally_vector
== null;
1423 public override bool InCatch ()
1425 return !in_try
&& (finally_vector
== null);
1428 public override bool InFinally (bool is_return
)
1430 return finally_vector
!= null;
1433 public override bool BreakCrossesTryCatchBoundary ()
1438 public override void AddFinallyVector (UsageVector vector
)
1440 vector
= vector
.Clone ();
1441 vector
.Next
= finally_origins
;
1442 finally_origins
= vector
;
1445 public override void StealFinallyClauses (ref ArrayList list
)
1448 list
= new ArrayList ();
1450 emit_finally
= false;
1451 base.StealFinallyClauses (ref list
);
1454 public bool EmitFinally
{
1455 get { return emit_finally; }
1458 public override LabeledStatement
LookupLabel (string name
, Location loc
)
1460 if (current_vector
.Block
== null)
1461 return base.LookupLabel (name
, loc
);
1463 LabeledStatement s
= current_vector
.Block
.LookupLabel (name
);
1467 if (finally_vector
!= null) {
1469 157, loc
, "Control can not leave the body " +
1470 "of the finally block");
1474 return base.LookupLabel (name
, loc
);
1477 public override void Label (UsageVector origin_vectors
)
1479 CurrentUsageVector
.MergeJumpOrigins (origin_vectors
);
1482 protected override UsageVector
Merge ()
1484 UsageVector vector
= Merge (catch_vectors
);
1486 vector
.MergeFinally (this, finally_vector
, finally_origins
);
1493 // This is used by the flow analysis code to keep track of the type of local variables
1496 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1497 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1498 // you can only assign the whole variable as such.
1500 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1501 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1502 // one bit for each of its fields.
1504 // This class computes this `layout' for each type.
1506 public class TypeInfo
1508 public readonly Type Type
;
1511 // Total number of bits a variable of this type consumes in the flow vector.
1513 public readonly int TotalLength
;
1516 // Number of bits the simple fields of a variable of this type consume
1517 // in the flow vector.
1519 public readonly int Length
;
1522 // This is only used by sub-structs.
1524 public readonly int Offset
;
1527 // If this is a struct.
1529 public readonly bool IsStruct
;
1532 // If this is a struct, all fields which are structs theirselves.
1534 public TypeInfo
[] SubStructInfo
;
1536 protected readonly StructInfo struct_info
;
1537 private static Hashtable type_hash
= new Hashtable ();
1539 public static TypeInfo
GetTypeInfo (Type type
)
1541 TypeInfo info
= (TypeInfo
) type_hash
[type
];
1545 info
= new TypeInfo (type
);
1546 type_hash
.Add (type
, info
);
1550 public static TypeInfo
GetTypeInfo (TypeContainer tc
)
1552 TypeInfo info
= (TypeInfo
) type_hash
[tc
.TypeBuilder
];
1556 info
= new TypeInfo (tc
);
1557 type_hash
.Add (tc
.TypeBuilder
, info
);
1561 private TypeInfo (Type type
)
1565 struct_info
= StructInfo
.GetStructInfo (type
);
1566 if (struct_info
!= null) {
1567 Length
= struct_info
.Length
;
1568 TotalLength
= struct_info
.TotalLength
;
1569 SubStructInfo
= struct_info
.StructFields
;
1578 private TypeInfo (TypeContainer tc
)
1580 this.Type
= tc
.TypeBuilder
;
1582 struct_info
= StructInfo
.GetStructInfo (tc
);
1583 if (struct_info
!= null) {
1584 Length
= struct_info
.Length
;
1585 TotalLength
= struct_info
.TotalLength
;
1586 SubStructInfo
= struct_info
.StructFields
;
1595 protected TypeInfo (StructInfo struct_info
, int offset
)
1597 this.struct_info
= struct_info
;
1598 this.Offset
= offset
;
1599 this.Length
= struct_info
.Length
;
1600 this.TotalLength
= struct_info
.TotalLength
;
1601 this.SubStructInfo
= struct_info
.StructFields
;
1602 this.Type
= struct_info
.Type
;
1603 this.IsStruct
= true;
1606 public int GetFieldIndex (string name
)
1608 if (struct_info
== null)
1611 return struct_info
[name
];
1614 public TypeInfo
GetSubStruct (string name
)
1616 if (struct_info
== null)
1619 return struct_info
.GetStructField (name
);
1623 // A struct's constructor must always assign all fields.
1624 // This method checks whether it actually does so.
1626 public bool IsFullyInitialized (FlowBranching branching
, VariableInfo vi
, Location loc
)
1628 if (struct_info
== null)
1632 for (int i
= 0; i
< struct_info
.Count
; i
++) {
1633 FieldInfo field
= struct_info
.Fields
[i
];
1635 if (!branching
.IsFieldAssigned (vi
, field
.Name
)) {
1636 Report
.Error (171, loc
,
1637 "Field `" + TypeManager
.CSharpName (Type
) +
1638 "." + field
.Name
+ "' must be fully initialized " +
1639 "before control leaves the constructor");
1647 public override string ToString ()
1649 return String
.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1650 Type
, Offset
, Length
, TotalLength
);
1653 protected class StructInfo
{
1654 public readonly Type Type
;
1655 public readonly FieldInfo
[] Fields
;
1656 public readonly TypeInfo
[] StructFields
;
1657 public readonly int Count
;
1658 public readonly int CountPublic
;
1659 public readonly int CountNonPublic
;
1660 public readonly int Length
;
1661 public readonly int TotalLength
;
1662 public readonly bool HasStructFields
;
1664 private static Hashtable field_type_hash
= new Hashtable ();
1665 private Hashtable struct_field_hash
;
1666 private Hashtable field_hash
;
1668 protected bool InTransit
= false;
1670 // Private constructor. To save memory usage, we only need to create one instance
1671 // of this class per struct type.
1672 private StructInfo (Type type
)
1676 field_type_hash
.Add (type
, this);
1678 if (type
is TypeBuilder
) {
1679 TypeContainer tc
= TypeManager
.LookupTypeContainer (type
);
1681 ArrayList fields
= tc
.Fields
;
1683 ArrayList public_fields
= new ArrayList ();
1684 ArrayList non_public_fields
= new ArrayList ();
1686 if (fields
!= null) {
1687 foreach (Field field
in fields
) {
1688 if ((field
.ModFlags
& Modifiers
.STATIC
) != 0)
1690 if ((field
.ModFlags
& Modifiers
.PUBLIC
) != 0)
1691 public_fields
.Add (field
.FieldBuilder
);
1693 non_public_fields
.Add (field
.FieldBuilder
);
1697 CountPublic
= public_fields
.Count
;
1698 CountNonPublic
= non_public_fields
.Count
;
1699 Count
= CountPublic
+ CountNonPublic
;
1701 Fields
= new FieldInfo
[Count
];
1702 public_fields
.CopyTo (Fields
, 0);
1703 non_public_fields
.CopyTo (Fields
, CountPublic
);
1705 FieldInfo
[] public_fields
= type
.GetFields (
1706 BindingFlags
.Instance
|BindingFlags
.Public
);
1707 FieldInfo
[] non_public_fields
= type
.GetFields (
1708 BindingFlags
.Instance
|BindingFlags
.NonPublic
);
1710 CountPublic
= public_fields
.Length
;
1711 CountNonPublic
= non_public_fields
.Length
;
1712 Count
= CountPublic
+ CountNonPublic
;
1714 Fields
= new FieldInfo
[Count
];
1715 public_fields
.CopyTo (Fields
, 0);
1716 non_public_fields
.CopyTo (Fields
, CountPublic
);
1719 struct_field_hash
= new Hashtable ();
1720 field_hash
= new Hashtable ();
1723 StructFields
= new TypeInfo
[Count
];
1724 StructInfo
[] sinfo
= new StructInfo
[Count
];
1728 for (int i
= 0; i
< Count
; i
++) {
1729 FieldInfo field
= (FieldInfo
) Fields
[i
];
1731 sinfo
[i
] = GetStructInfo (field
.FieldType
);
1732 if (sinfo
[i
] == null)
1733 field_hash
.Add (field
.Name
, ++Length
);
1734 else if (sinfo
[i
].InTransit
) {
1735 Report
.Error (523, String
.Format (
1736 "Struct member '{0}.{1}' of type '{2}' causes " +
1737 "a cycle in the structure layout",
1738 type
, field
.Name
, sinfo
[i
].Type
));
1746 TotalLength
= Length
+ 1;
1747 for (int i
= 0; i
< Count
; i
++) {
1748 FieldInfo field
= (FieldInfo
) Fields
[i
];
1750 if (sinfo
[i
] == null)
1753 field_hash
.Add (field
.Name
, TotalLength
);
1755 HasStructFields
= true;
1756 StructFields
[i
] = new TypeInfo (sinfo
[i
], TotalLength
);
1757 struct_field_hash
.Add (field
.Name
, StructFields
[i
]);
1758 TotalLength
+= sinfo
[i
].TotalLength
;
1762 public int this [string name
] {
1764 if (field_hash
.Contains (name
))
1765 return (int) field_hash
[name
];
1771 public TypeInfo
GetStructField (string name
)
1773 return (TypeInfo
) struct_field_hash
[name
];
1776 public static StructInfo
GetStructInfo (Type type
)
1778 if (!TypeManager
.IsValueType (type
) || TypeManager
.IsEnumType (type
) ||
1779 TypeManager
.IsBuiltinType (type
))
1782 StructInfo info
= (StructInfo
) field_type_hash
[type
];
1786 return new StructInfo (type
);
1789 public static StructInfo
GetStructInfo (TypeContainer tc
)
1791 StructInfo info
= (StructInfo
) field_type_hash
[tc
.TypeBuilder
];
1795 return new StructInfo (tc
.TypeBuilder
);
1801 // This is used by the flow analysis code to store information about a single local variable
1802 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1803 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1804 // it has been assigned or not, but for structs, we need this information for each of its fields.
1806 public class VariableInfo
{
1807 public readonly string Name
;
1808 public readonly TypeInfo TypeInfo
;
1811 // The bit offset of this variable in the flow vector.
1813 public readonly int Offset
;
1816 // The number of bits this variable needs in the flow vector.
1817 // The first bit always specifies whether the variable as such has been assigned while
1818 // the remaining bits contain this information for each of a struct's fields.
1820 public readonly int Length
;
1823 // If this is a parameter of local variable.
1825 public readonly bool IsParameter
;
1827 public readonly LocalInfo LocalInfo
;
1828 public readonly int ParameterIndex
;
1830 readonly VariableInfo Parent
;
1831 VariableInfo
[] sub_info
;
1833 protected VariableInfo (string name
, Type type
, int offset
)
1836 this.Offset
= offset
;
1837 this.TypeInfo
= TypeInfo
.GetTypeInfo (type
);
1839 Length
= TypeInfo
.TotalLength
;
1844 protected VariableInfo (VariableInfo parent
, TypeInfo type
)
1846 this.Name
= parent
.Name
;
1847 this.TypeInfo
= type
;
1848 this.Offset
= parent
.Offset
+ type
.Offset
;
1849 this.Parent
= parent
;
1850 this.Length
= type
.TotalLength
;
1852 this.IsParameter
= parent
.IsParameter
;
1853 this.LocalInfo
= parent
.LocalInfo
;
1854 this.ParameterIndex
= parent
.ParameterIndex
;
1859 protected void Initialize ()
1861 TypeInfo
[] sub_fields
= TypeInfo
.SubStructInfo
;
1862 if (sub_fields
!= null) {
1863 sub_info
= new VariableInfo
[sub_fields
.Length
];
1864 for (int i
= 0; i
< sub_fields
.Length
; i
++) {
1865 if (sub_fields
[i
] != null)
1866 sub_info
[i
] = new VariableInfo (this, sub_fields
[i
]);
1869 sub_info
= new VariableInfo
[0];
1872 public VariableInfo (LocalInfo local_info
, int offset
)
1873 : this (local_info
.Name
, local_info
.VariableType
, offset
)
1875 this.LocalInfo
= local_info
;
1876 this.IsParameter
= false;
1879 public VariableInfo (string name
, Type type
, int param_idx
, int offset
)
1880 : this (name
, type
, offset
)
1882 this.ParameterIndex
= param_idx
;
1883 this.IsParameter
= true;
1886 public bool IsAssigned (EmitContext ec
)
1888 return !ec
.DoFlowAnalysis
|| ec
.CurrentBranching
.IsAssigned (this);
1891 public bool IsAssigned (EmitContext ec
, Location loc
)
1893 if (IsAssigned (ec
))
1896 Report
.Error (165, loc
,
1897 "Use of unassigned local variable `" + Name
+ "'");
1898 ec
.CurrentBranching
.SetAssigned (this);
1902 public bool IsAssigned (MyBitVector vector
)
1904 if (vector
[Offset
])
1907 for (VariableInfo parent
= Parent
; parent
!= null; parent
= parent
.Parent
)
1908 if (vector
[parent
.Offset
])
1911 // Return unless this is a struct.
1912 if (!TypeInfo
.IsStruct
)
1915 // Ok, so each field must be assigned.
1916 for (int i
= 0; i
< TypeInfo
.Length
; i
++) {
1917 if (!vector
[Offset
+ i
+ 1])
1921 // Ok, now check all fields which are structs.
1922 for (int i
= 0; i
< sub_info
.Length
; i
++) {
1923 VariableInfo sinfo
= sub_info
[i
];
1927 if (!sinfo
.IsAssigned (vector
))
1931 vector
[Offset
] = true;
1935 public void SetAssigned (EmitContext ec
)
1937 if (ec
.DoFlowAnalysis
)
1938 ec
.CurrentBranching
.SetAssigned (this);
1941 public void SetAssigned (MyBitVector vector
)
1943 vector
[Offset
] = true;
1946 public bool IsFieldAssigned (EmitContext ec
, string name
, Location loc
)
1948 if (!ec
.DoFlowAnalysis
|| ec
.CurrentBranching
.IsFieldAssigned (this, name
))
1951 Report
.Error (170, loc
,
1952 "Use of possibly unassigned field `" + name
+ "'");
1953 ec
.CurrentBranching
.SetFieldAssigned (this, name
);
1957 public bool IsFieldAssigned (MyBitVector vector
, string field_name
)
1959 int field_idx
= TypeInfo
.GetFieldIndex (field_name
);
1964 return vector
[Offset
+ field_idx
];
1967 public void SetFieldAssigned (EmitContext ec
, string name
)
1969 if (ec
.DoFlowAnalysis
)
1970 ec
.CurrentBranching
.SetFieldAssigned (this, name
);
1973 public void SetFieldAssigned (MyBitVector vector
, string field_name
)
1975 int field_idx
= TypeInfo
.GetFieldIndex (field_name
);
1980 vector
[Offset
+ field_idx
] = true;
1983 public VariableInfo
GetSubStruct (string name
)
1985 TypeInfo type
= TypeInfo
.GetSubStruct (name
);
1990 return new VariableInfo (this, type
);
1993 public override string ToString ()
1995 return String
.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1996 Name
, TypeInfo
, Offset
, Length
, IsParameter
);
2001 // This is used by the flow code to hold the `layout' of the flow vector for
2002 // all locals and all parameters (ie. we create one instance of this class for the
2003 // locals and another one for the params).
2005 public class VariableMap
{
2007 // The number of variables in the map.
2009 public readonly int Count
;
2012 // Total length of the flow vector for this map.
2014 public readonly int Length
;
2018 public VariableMap (InternalParameters ip
)
2020 Count
= ip
!= null ? ip
.Count
: 0;
2022 // Dont bother allocating anything!
2028 for (int i
= 0; i
< Count
; i
++) {
2029 Parameter
.Modifier mod
= ip
.ParameterModifier (i
);
2031 if ((mod
& Parameter
.Modifier
.OUT
) == 0)
2034 // Dont allocate till we find an out var.
2036 map
= new VariableInfo
[Count
];
2038 map
[i
] = new VariableInfo (ip
.ParameterName (i
),
2039 TypeManager
.GetElementType (ip
.ParameterType (i
)), i
, Length
);
2041 Length
+= map
[i
].Length
;
2045 public VariableMap (LocalInfo
[] locals
)
2046 : this (null, locals
)
2049 public VariableMap (VariableMap parent
, LocalInfo
[] locals
)
2051 int offset
= 0, start
= 0;
2052 if (parent
!= null && parent
.map
!= null) {
2053 offset
= parent
.Length
;
2054 start
= parent
.Count
;
2057 Count
= locals
.Length
+ start
;
2062 map
= new VariableInfo
[Count
];
2065 if (parent
!= null && parent
.map
!= null) {
2066 parent
.map
.CopyTo (map
, 0);
2069 for (int i
= start
; i
< Count
; i
++) {
2070 LocalInfo li
= locals
[i
-start
];
2072 if (li
.VariableType
== null)
2075 map
[i
] = li
.VariableInfo
= new VariableInfo (li
, Length
);
2076 Length
+= map
[i
].Length
;
2081 // Returns the VariableInfo for variable @index or null if we don't need to
2082 // compute assignment info for this variable.
2084 public VariableInfo
this [int index
] {
2093 public override string ToString ()
2095 return String
.Format ("VariableMap ({0}:{1})", Count
, Length
);
2100 // This is a special bit vector which can inherit from another bit vector doing a
2101 // copy-on-write strategy. The inherited vector may have a smaller size than the
2104 public class MyBitVector
{
2105 public readonly int Count
;
2106 public readonly MyBitVector InheritsFrom
;
2111 public MyBitVector (int Count
)
2112 : this (null, Count
)
2115 public MyBitVector (MyBitVector InheritsFrom
, int Count
)
2117 this.InheritsFrom
= InheritsFrom
;
2122 // Checks whether this bit vector has been modified. After setting this to true,
2123 // we won't use the inherited vector anymore, but our own copy of it.
2125 public bool IsDirty
{
2132 initialize_vector ();
2137 // Get/set bit `index' in the bit vector.
2139 public bool this [int index
]
2143 throw new ArgumentOutOfRangeException ();
2145 // We're doing a "copy-on-write" strategy here; as long
2146 // as nobody writes to the array, we can use our parent's
2147 // copy instead of duplicating the vector.
2150 return vector
[index
];
2151 else if (InheritsFrom
!= null) {
2152 BitArray inherited
= InheritsFrom
.Vector
;
2154 if (index
< inherited
.Count
)
2155 return inherited
[index
];
2164 throw new ArgumentOutOfRangeException ();
2166 // Only copy the vector if we're actually modifying it.
2168 if (this [index
] != value) {
2169 initialize_vector ();
2171 vector
[index
] = value;
2177 // If you explicitly convert the MyBitVector to a BitArray, you will get a deep
2178 // copy of the bit vector.
2180 public static explicit operator BitArray (MyBitVector vector
)
2182 vector
.initialize_vector ();
2183 return vector
.Vector
;
2187 // Performs an `or' operation on the bit vector. The `new_vector' may have a
2188 // different size than the current one.
2190 public void Or (MyBitVector new_vector
)
2192 BitArray new_array
= new_vector
.Vector
;
2194 initialize_vector ();
2197 if (vector
.Count
< new_array
.Count
)
2198 upper
= vector
.Count
;
2200 upper
= new_array
.Count
;
2202 for (int i
= 0; i
< upper
; i
++)
2203 vector
[i
] = vector
[i
] | new_array
[i
];
2207 // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
2208 // a different size than the current one.
2210 public void And (MyBitVector new_vector
)
2212 BitArray new_array
= new_vector
.Vector
;
2214 initialize_vector ();
2217 if (vector
.Count
< new_array
.Count
)
2218 lower
= upper
= vector
.Count
;
2220 lower
= new_array
.Count
;
2221 upper
= vector
.Count
;
2224 for (int i
= 0; i
< lower
; i
++)
2225 vector
[i
] = vector
[i
] & new_array
[i
];
2227 for (int i
= lower
; i
< upper
; i
++)
2231 public static void And (ref MyBitVector target
, MyBitVector vector
)
2234 target
.And (vector
);
2236 target
= vector
.Clone ();
2239 public static void Or (ref MyBitVector target
, MyBitVector vector
)
2244 target
= vector
.Clone ();
2248 // This does a deep copy of the bit vector.
2250 public MyBitVector
Clone ()
2252 MyBitVector retval
= new MyBitVector (Count
);
2254 retval
.Vector
= Vector
;
2263 else if (!is_dirty
&& (InheritsFrom
!= null))
2264 return InheritsFrom
.Vector
;
2266 initialize_vector ();
2272 initialize_vector ();
2274 for (int i
= 0; i
< System
.Math
.Min (vector
.Count
, value.Count
); i
++)
2275 vector
[i
] = value [i
];
2279 void initialize_vector ()
2284 vector
= new BitArray (Count
, false);
2285 if (InheritsFrom
!= null)
2286 Vector
= InheritsFrom
.Vector
;
2291 public override string ToString ()
2293 StringBuilder sb
= new StringBuilder ("{");
2295 BitArray vector
= Vector
;
2298 for (int i
= 0; i
< vector
.Count
; i
++) {
2299 sb
.Append (vector
[i
] ? "1" : "0");
2303 return sb
.ToString ();