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
)
118 case 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 ("shouldn't get here");
140 public static FlowReturns
OrFlowReturns (FlowReturns a
, FlowReturns b
)
143 case FlowReturns
.Undefined
:
146 case FlowReturns
.Never
:
149 case FlowReturns
.Sometimes
:
150 if (b
== FlowReturns
.Always
)
151 return FlowReturns
.Always
;
153 return FlowReturns
.Sometimes
;
155 case FlowReturns
.Always
:
156 return FlowReturns
.Always
;
159 throw new ArgumentException ("shouldn't get here");
162 public static void And (ref Reachability a
, Reachability b
, bool do_break
)
172 public void And (Reachability b
, bool do_break
)
175 // `break' does not "break" in a Switch or a LoopBlock
177 bool a_breaks
= do_break
&& AlwaysBreaks
;
178 bool b_breaks
= do_break
&& b
.AlwaysBreaks
;
180 bool a_has_barrier
, b_has_barrier
;
183 // This is the normal case: the code following a barrier
184 // cannot be reached.
186 a_has_barrier
= AlwaysHasBarrier
;
187 b_has_barrier
= b
.AlwaysHasBarrier
;
190 // Special case for Switch and LoopBlocks: we can reach the
191 // code after the barrier via the `break'.
193 a_has_barrier
= !AlwaysBreaks
&& AlwaysHasBarrier
;
194 b_has_barrier
= !b
.AlwaysBreaks
&& b
.AlwaysHasBarrier
;
197 bool a_unreachable
= a_breaks
|| AlwaysThrows
|| a_has_barrier
;
198 bool b_unreachable
= b_breaks
|| b
.AlwaysThrows
|| b_has_barrier
;
201 // Do all code paths always return ?
204 if (b
.AlwaysReturns
|| b_unreachable
)
205 returns
= FlowReturns
.Always
;
207 returns
= FlowReturns
.Sometimes
;
208 } else if (b
.AlwaysReturns
) {
209 if (AlwaysReturns
|| a_unreachable
)
210 returns
= FlowReturns
.Always
;
212 returns
= FlowReturns
.Sometimes
;
213 } else if (!MayReturn
) {
215 returns
= FlowReturns
.Sometimes
;
217 returns
= FlowReturns
.Never
;
218 } else if (!b
.MayReturn
) {
220 returns
= FlowReturns
.Sometimes
;
222 returns
= FlowReturns
.Never
;
225 breaks
= AndFlowReturns (breaks
, b
.breaks
);
226 throws
= AndFlowReturns (throws
, b
.throws
);
227 barrier
= AndFlowReturns (barrier
, b
.barrier
);
229 if (a_unreachable
&& b_unreachable
)
230 barrier
= FlowReturns
.Always
;
231 else if (a_unreachable
|| b_unreachable
)
232 barrier
= FlowReturns
.Sometimes
;
234 barrier
= FlowReturns
.Never
;
237 public void Or (Reachability b
)
239 returns
= OrFlowReturns (returns
, b
.returns
);
240 breaks
= OrFlowReturns (breaks
, b
.breaks
);
241 throws
= OrFlowReturns (throws
, b
.throws
);
242 barrier
= OrFlowReturns (barrier
, b
.barrier
);
245 public static Reachability
Never ()
247 return new Reachability (
248 FlowReturns
.Never
, FlowReturns
.Never
,
249 FlowReturns
.Never
, FlowReturns
.Never
);
252 public FlowReturns Reachable
{
254 if ((returns
== FlowReturns
.Always
) ||
255 (breaks
== FlowReturns
.Always
) ||
256 (throws
== FlowReturns
.Always
) ||
257 (barrier
== FlowReturns
.Always
))
258 return FlowReturns
.Never
;
259 else if ((returns
== FlowReturns
.Never
) &&
260 (breaks
== FlowReturns
.Never
) &&
261 (throws
== FlowReturns
.Never
) &&
262 (barrier
== FlowReturns
.Never
))
263 return FlowReturns
.Always
;
265 return FlowReturns
.Sometimes
;
269 public bool AlwaysBreaks
{
270 get { return breaks == FlowReturns.Always; }
273 public bool MayBreak
{
274 get { return breaks != FlowReturns.Never; }
277 public bool AlwaysReturns
{
278 get { return returns == FlowReturns.Always; }
281 public bool MayReturn
{
282 get { return returns != FlowReturns.Never; }
285 public bool AlwaysThrows
{
286 get { return throws == FlowReturns.Always; }
289 public bool MayThrow
{
290 get { return throws != FlowReturns.Never; }
293 public bool AlwaysHasBarrier
{
294 get { return barrier == FlowReturns.Always; }
297 public bool MayHaveBarrier
{
298 get { return barrier != FlowReturns.Never; }
301 public bool IsUnreachable
{
302 get { return Reachable == FlowReturns.Never; }
305 public void SetReturns ()
307 returns
= FlowReturns
.Always
;
310 public void SetReturnsSometimes ()
312 returns
= FlowReturns
.Sometimes
;
315 public void SetBreaks ()
317 breaks
= FlowReturns
.Always
;
320 public void ResetBreaks ()
322 breaks
= FlowReturns
.Never
;
325 public void SetThrows ()
327 throws
= FlowReturns
.Always
;
330 public void SetThrowsSometimes ()
332 throws
= FlowReturns
.Sometimes
;
335 public void SetBarrier ()
337 barrier
= FlowReturns
.Always
;
340 public void ResetBarrier ()
342 barrier
= FlowReturns
.Never
;
345 static string ShortName (FlowReturns returns
)
348 case FlowReturns
.Never
:
350 case FlowReturns
.Sometimes
:
357 public override string ToString ()
359 return String
.Format ("[{0}:{1}:{2}:{3}:{4}]",
360 ShortName (returns
), ShortName (breaks
),
361 ShortName (throws
), ShortName (barrier
),
362 ShortName (Reachable
));
366 public static FlowBranching
CreateBranching (FlowBranching parent
, BranchingType type
, Block block
, Location loc
)
369 case BranchingType
.Exception
:
370 throw new InvalidOperationException ();
372 case BranchingType
.Switch
:
373 return new FlowBranchingSwitch (parent
, block
, loc
);
375 case BranchingType
.SwitchSection
:
376 return new FlowBranchingBlock (parent
, type
, SiblingType
.Block
, block
, loc
);
378 case BranchingType
.Block
:
379 return new FlowBranchingBlock (parent
, type
, SiblingType
.Block
, block
, loc
);
381 case BranchingType
.Loop
:
382 return new FlowBranchingLoop (parent
, block
, loc
);
385 return new FlowBranchingBlock (parent
, type
, SiblingType
.Conditional
, block
, loc
);
390 // The type of this flow branching.
392 public readonly BranchingType Type
;
395 // The block this branching is contained in. This may be null if it's not
396 // a top-level block and it doesn't declare any local variables.
398 public readonly Block Block
;
401 // The parent of this branching or null if this is the top-block.
403 public readonly FlowBranching Parent
;
406 // Start-Location of this flow branching.
408 public readonly Location Location
;
411 // If this is an infinite loop.
413 public bool Infinite
;
418 VariableMap param_map
, local_map
;
420 static int next_id
= 0;
424 // The vector contains a BitArray with information about which local variables
425 // and parameters are already initialized at the current code position.
427 public class UsageVector
{
429 // The type of this branching.
431 public readonly SiblingType Type
;
434 // Start location of this branching.
436 public readonly Location Location
;
439 // This is only valid for SwitchSection, Try, Catch and Finally.
441 public readonly Block Block
;
444 // If this is true, then the usage vector has been modified and must be
445 // merged when we're done with this branching.
450 // The number of parameters in this block.
452 public readonly int CountParameters
;
455 // The number of locals in this block.
457 public readonly int CountLocals
;
460 // If not null, then we inherit our state from this vector and do a
461 // copy-on-write. If null, then we're the first sibling in a top-level
462 // block and inherit from the empty vector.
464 public readonly UsageVector InheritsFrom
;
467 // This is used to construct a list of UsageVector's.
469 public UsageVector Next
;
474 MyBitVector locals
, parameters
;
475 Reachability reachability
;
477 static int next_id
= 0;
481 // Normally, you should not use any of these constructors.
483 public UsageVector (SiblingType type
, UsageVector parent
,
484 Block block
, Location loc
,
485 int num_params
, int num_locals
)
490 this.InheritsFrom
= parent
;
491 this.CountParameters
= num_params
;
492 this.CountLocals
= num_locals
;
494 if (parent
!= null) {
496 locals
= new MyBitVector (parent
.locals
, CountLocals
);
499 parameters
= new MyBitVector (parent
.parameters
, num_params
);
501 reachability
= parent
.Reachability
.Clone ();
504 locals
= new MyBitVector (null, CountLocals
);
507 parameters
= new MyBitVector (null, num_params
);
509 reachability
= Reachability
.Never ();
515 public UsageVector (SiblingType type
, UsageVector parent
,
516 Block block
, Location loc
)
517 : this (type
, parent
, block
, loc
,
518 parent
.CountParameters
, parent
.CountLocals
)
521 public UsageVector (MyBitVector parameters
, MyBitVector locals
,
522 Reachability reachability
, Block block
,
525 this.Type
= SiblingType
.Block
;
529 this.reachability
= reachability
;
530 this.parameters
= parameters
;
531 this.locals
= locals
;
537 // This does a deep copy of the usage vector.
539 public UsageVector
Clone ()
541 UsageVector retval
= new UsageVector (
542 Type
, null, Block
, Location
,
543 CountParameters
, CountLocals
);
545 if (retval
.locals
!= null)
546 retval
.locals
= locals
.Clone ();
548 if (parameters
!= null)
549 retval
.parameters
= parameters
.Clone ();
551 retval
.reachability
= reachability
.Clone ();
556 public bool IsAssigned (VariableInfo
var)
558 if (!var.IsParameter
&& Reachability
.IsUnreachable
)
561 return var.IsAssigned (var.IsParameter
? parameters
: locals
);
564 public void SetAssigned (VariableInfo
var)
566 if (!var.IsParameter
&& Reachability
.IsUnreachable
)
570 var.SetAssigned (var.IsParameter
? parameters
: locals
);
573 public bool IsFieldAssigned (VariableInfo
var, string name
)
575 if (!var.IsParameter
&& Reachability
.IsUnreachable
)
578 return var.IsFieldAssigned (var.IsParameter
? parameters
: locals
, name
);
581 public void SetFieldAssigned (VariableInfo
var, string name
)
583 if (!var.IsParameter
&& Reachability
.IsUnreachable
)
587 var.SetFieldAssigned (var.IsParameter
? parameters
: locals
, name
);
590 public Reachability Reachability
{
591 get { return reachability; }
594 public void Return ()
596 if (!reachability
.IsUnreachable
) {
598 reachability
.SetReturns ();
604 if (!reachability
.IsUnreachable
) {
606 reachability
.SetBreaks ();
612 if (!reachability
.IsUnreachable
) {
614 reachability
.SetThrows ();
620 if (!reachability
.IsUnreachable
) {
622 reachability
.SetBarrier ();
627 // Merges a child branching.
629 public UsageVector
MergeChild (FlowBranching branching
)
631 UsageVector result
= branching
.Merge ();
633 Report
.Debug (2, " MERGING CHILD", this, branching
, IsDirty
,
634 result
.ParameterVector
, result
.LocalVector
,
635 result
.Reachability
, reachability
, Type
);
637 Reachability new_r
= result
.Reachability
;
640 // We've now either reached the point after the branching or we will
641 // never get there since we always return or always throw an exception.
643 // If we can reach the point after the branching, mark all locals and
644 // parameters as initialized which have been initialized in all branches
645 // we need to look at (see above).
648 if ((Type
== SiblingType
.SwitchSection
) && !new_r
.IsUnreachable
) {
649 Report
.Error (163, Location
,
650 "Control cannot fall through from one " +
651 "case label to another");
655 if (locals
!= null && result
.LocalVector
!= null)
656 locals
.Or (result
.LocalVector
);
658 if (result
.ParameterVector
!= null)
659 parameters
.Or (result
.ParameterVector
);
661 if ((branching
.Type
== BranchingType
.Block
) && branching
.Block
.Implicit
)
662 reachability
= new_r
.Clone ();
664 reachability
.Or (new_r
);
666 Report
.Debug (2, " MERGING CHILD DONE", this, result
,
667 new_r
, reachability
);
674 protected static void MergeFinally (UsageVector f_origins
,
675 MyBitVector f_params
)
677 for (UsageVector vector
= f_origins
; vector
!= null; vector
= vector
.Next
) {
678 MyBitVector temp_params
= f_params
.Clone ();
679 temp_params
.Or (vector
.Parameters
);
683 public void MergeFinally (UsageVector f_vector
,
684 UsageVector f_origins
)
686 if (parameters
!= null) {
687 if (f_vector
!= null) {
688 MergeFinally (f_origins
, f_vector
.Parameters
);
689 MyBitVector
.Or (ref parameters
, f_vector
.ParameterVector
);
691 MergeFinally (f_origins
, parameters
);
694 if (f_vector
!= null && f_vector
.LocalVector
!= null)
695 MyBitVector
.Or (ref locals
, f_vector
.LocalVector
);
699 // Tells control flow analysis that the current code position may be reached with
700 // a forward jump from any of the origins listed in `origin_vectors' which is a
701 // list of UsageVectors.
703 // This is used when resolving forward gotos - in the following example, the
704 // variable `a' is uninitialized in line 8 becase this line may be reached via
705 // the goto in line 4:
715 // 8 Console.WriteLine (a);
718 public void MergeJumpOrigins (UsageVector o_vectors
)
720 Report
.Debug (1, " MERGING JUMP ORIGINS", this);
722 reachability
= Reachability
.Never ();
724 if (o_vectors
== null) {
725 reachability
.SetBarrier ();
731 for (UsageVector vector
= o_vectors
; vector
!= null;
732 vector
= vector
.Next
) {
733 Report
.Debug (1, " MERGING JUMP ORIGIN", vector
,
734 first
, locals
, vector
.Locals
);
737 if (locals
!= null && vector
.Locals
!= null)
738 locals
.Or (vector
.locals
);
740 if (parameters
!= null)
741 parameters
.Or (vector
.parameters
);
745 locals
.And (vector
.locals
);
746 if (parameters
!= null)
747 parameters
.And (vector
.parameters
);
750 Reachability
.And (ref reachability
, vector
.Reachability
, true);
752 Report
.Debug (1, " MERGING JUMP ORIGIN #1", vector
);
755 Report
.Debug (1, " MERGING JUMP ORIGINS DONE", this);
759 // This is used at the beginning of a finally block if there were
760 // any return statements in the try block or one of the catch blocks.
762 public void MergeFinallyOrigins (UsageVector f_origins
)
764 Report
.Debug (1, " MERGING FINALLY ORIGIN", this);
766 reachability
= Reachability
.Never ();
768 for (UsageVector vector
= f_origins
; vector
!= null; vector
= vector
.Next
) {
769 Report
.Debug (1, " MERGING FINALLY ORIGIN", vector
);
771 if (parameters
!= null)
772 parameters
.And (vector
.parameters
);
774 Reachability
.And (ref reachability
, vector
.Reachability
, true);
777 Report
.Debug (1, " MERGING FINALLY ORIGIN DONE", this);
780 public void MergeBreakOrigins (FlowBranching branching
, UsageVector o_vectors
)
782 Report
.Debug (1, " MERGING BREAK ORIGINS", this);
784 if (o_vectors
== null)
787 bool first
= branching
.Infinite
;
789 for (UsageVector vector
= o_vectors
; vector
!= null;
790 vector
= vector
.Next
) {
791 Report
.Debug (1, " MERGING BREAK ORIGIN", vector
, first
);
794 if (locals
!= null && vector
.Locals
!= null)
795 locals
.Or (vector
.locals
);
797 if (parameters
!= null)
798 parameters
.Or (vector
.parameters
);
801 if (locals
!= null && vector
.Locals
!= null)
802 locals
.And (vector
.locals
);
803 if (parameters
!= null)
804 parameters
.And (vector
.parameters
);
807 reachability
.And (vector
.Reachability
, false);
810 Report
.Debug (1, " MERGING BREAK ORIGINS DONE", this);
813 public void CheckOutParameters (FlowBranching branching
)
815 if (parameters
!= null)
816 branching
.CheckOutParameters (parameters
, branching
.Location
);
820 // Performs an `or' operation on the locals and the parameters.
822 public void Or (UsageVector new_vector
)
825 locals
.Or (new_vector
.locals
);
826 if (parameters
!= null)
827 parameters
.Or (new_vector
.parameters
);
831 // Performs an `and' operation on the locals.
833 public void AndLocals (UsageVector new_vector
)
836 locals
.And (new_vector
.locals
);
839 public bool HasParameters
{
840 get { return parameters != null; }
843 public bool HasLocals
{
844 get { return locals != null; }
848 // Returns a deep copy of the parameters.
850 public MyBitVector Parameters
{
851 get { return parameters == null ? null : parameters.Clone (); }
855 // Returns a deep copy of the locals.
857 public MyBitVector Locals
{
858 get { return locals == null ? null : locals.Clone (); }
861 public MyBitVector ParameterVector
{
862 get { return parameters; }
865 public MyBitVector LocalVector
{
866 get { return locals; }
873 public override string ToString ()
875 StringBuilder sb
= new StringBuilder ();
877 sb
.Append ("Vector (");
884 sb
.Append (reachability
);
885 if (parameters
!= null) {
887 sb
.Append (parameters
);
893 return sb
.ToString ();
898 // Creates a new flow branching which is contained in `parent'.
899 // You should only pass non-null for the `block' argument if this block
900 // introduces any new variables - in this case, we need to create a new
901 // usage vector with a different size than our parent's one.
903 protected FlowBranching (FlowBranching parent
, BranchingType type
, SiblingType stype
,
904 Block block
, Location loc
)
914 param_map
= Block
.ParameterMap
;
915 local_map
= Block
.LocalMap
;
917 UsageVector parent_vector
= parent
!= null ? parent
.CurrentUsageVector
: null;
918 vector
= new UsageVector (
919 stype
, parent_vector
, Block
, loc
,
920 param_map
.Length
, local_map
.Length
);
922 param_map
= Parent
.param_map
;
923 local_map
= Parent
.local_map
;
924 vector
= new UsageVector (
925 stype
, Parent
.CurrentUsageVector
, null, loc
);
931 public abstract UsageVector CurrentUsageVector
{
936 // Creates a sibling of the current usage vector.
938 public virtual void CreateSibling (Block block
, SiblingType type
)
940 UsageVector vector
= new UsageVector (
941 type
, Parent
.CurrentUsageVector
, block
, Location
);
944 Report
.Debug (1, " CREATED SIBLING", CurrentUsageVector
);
947 public void CreateSibling ()
949 CreateSibling (null, SiblingType
.Conditional
);
952 protected abstract void AddSibling (UsageVector uv
);
954 public virtual LabeledStatement
LookupLabel (string name
, Location loc
)
957 return Parent
.LookupLabel (name
, loc
);
961 "No such label `" + name
+ "' in this scope");
965 public abstract void Label (UsageVector origin_vectors
);
968 // Check whether all `out' parameters have been assigned.
970 public void CheckOutParameters (MyBitVector parameters
, Location loc
)
972 for (int i
= 0; i
< param_map
.Count
; i
++) {
973 VariableInfo
var = param_map
[i
];
978 if (var.IsAssigned (parameters
))
981 Report
.Error (177, loc
, "The out parameter `{0}' must be assigned to before control leaves the current method",
986 protected UsageVector
Merge (UsageVector sibling_list
)
988 if (sibling_list
.Next
== null)
991 MyBitVector locals
= null;
992 MyBitVector parameters
= null;
994 Reachability reachability
= null;
996 Report
.Debug (2, " MERGING SIBLINGS", this, Name
);
998 for (UsageVector child
= sibling_list
; child
!= null; child
= child
.Next
) {
999 bool do_break
= (Type
!= BranchingType
.Switch
) &&
1000 (Type
!= BranchingType
.Loop
);
1002 Report
.Debug (2, " MERGING SIBLING ", child
,
1003 child
.ParameterVector
, child
.LocalVector
,
1004 reachability
, child
.Reachability
, do_break
);
1006 Reachability
.And (ref reachability
, child
.Reachability
, do_break
);
1008 // A local variable is initialized after a flow branching if it
1009 // has been initialized in all its branches which do neither
1010 // always return or always throw an exception.
1012 // If a branch may return, but does not always return, then we
1013 // can treat it like a never-returning branch here: control will
1014 // only reach the code position after the branching if we did not
1017 // It's important to distinguish between always and sometimes
1018 // returning branches here:
1021 // 2 if (something) {
1025 // 6 Console.WriteLine (a);
1027 // The if block in lines 3-4 always returns, so we must not look
1028 // at the initialization of `a' in line 4 - thus it'll still be
1029 // uninitialized in line 6.
1031 // On the other hand, the following is allowed:
1038 // 6 Console.WriteLine (a);
1040 // Here, `a' is initialized in line 3 and we must not look at
1041 // line 5 since it always returns.
1043 bool do_break_2
= (child
.Type
!= SiblingType
.Block
) &&
1044 (child
.Type
!= SiblingType
.SwitchSection
);
1045 bool always_throws
= (child
.Type
!= SiblingType
.Try
) &&
1046 child
.Reachability
.AlwaysThrows
;
1047 bool unreachable
= always_throws
||
1048 (do_break_2
&& child
.Reachability
.AlwaysBreaks
) ||
1049 child
.Reachability
.AlwaysReturns
||
1050 child
.Reachability
.AlwaysHasBarrier
;
1052 Report
.Debug (2, " MERGING SIBLING #1", reachability
,
1053 Type
, child
.Type
, child
.Reachability
.IsUnreachable
,
1054 do_break_2
, always_throws
, unreachable
);
1056 if (!unreachable
&& (child
.LocalVector
!= null))
1057 MyBitVector
.And (ref locals
, child
.LocalVector
);
1059 // An `out' parameter must be assigned in all branches which do
1060 // not always throw an exception.
1061 if ((child
.ParameterVector
!= null) && !child
.Reachability
.AlwaysThrows
)
1062 MyBitVector
.And (ref parameters
, child
.ParameterVector
);
1064 Report
.Debug (2, " MERGING SIBLING #2", parameters
, locals
);
1067 if (reachability
== null)
1068 reachability
= Reachability
.Never ();
1070 Report
.Debug (2, " MERGING SIBLINGS DONE", parameters
, locals
,
1071 reachability
, Infinite
);
1073 return new UsageVector (
1074 parameters
, locals
, reachability
, null, Location
);
1077 protected abstract UsageVector
Merge ();
1080 // Merge a child branching.
1082 public UsageVector
MergeChild (FlowBranching child
)
1084 return CurrentUsageVector
.MergeChild (child
);
1088 // Does the toplevel merging.
1090 public Reachability
MergeTopBlock ()
1092 if ((Type
!= BranchingType
.Block
) || (Block
== null))
1093 throw new NotSupportedException ();
1095 UsageVector vector
= new UsageVector (
1096 SiblingType
.Block
, null, Block
, Location
,
1097 param_map
.Length
, local_map
.Length
);
1099 UsageVector result
= vector
.MergeChild (this);
1101 Report
.Debug (4, "MERGE TOP BLOCK", Location
, vector
, result
.Reachability
);
1103 if ((vector
.Reachability
.Throws
!= FlowReturns
.Always
) &&
1104 (vector
.Reachability
.Barrier
!= FlowReturns
.Always
))
1105 CheckOutParameters (vector
.Parameters
, Location
);
1107 return result
.Reachability
;
1111 // Checks whether we're in a `try' block.
1113 public virtual bool InTryOrCatch (bool is_return
)
1115 if (Block
!= null && Block
.IsDestructor
)
1117 if (!is_return
&& (Type
== BranchingType
.Loop
|| Type
== BranchingType
.Switch
))
1119 return Parent
!= null && Parent
.InTryOrCatch (is_return
);
1122 public virtual bool InTryWithCatch ()
1124 return Parent
!= null && Parent
.InTryWithCatch ();
1127 public virtual bool InLoop ()
1129 return Parent
!= null && Parent
.InLoop ();
1132 public virtual bool InSwitch ()
1134 return Parent
!= null && Parent
.InSwitch ();
1137 public virtual bool BreakCrossesTryCatchBoundary ()
1139 return Parent
!= null && Parent
.BreakCrossesTryCatchBoundary ();
1142 public virtual void AddFinallyVector (UsageVector vector
)
1145 Parent
.AddFinallyVector (vector
);
1146 else if ((Block
== null) || !Block
.IsDestructor
)
1147 throw new NotSupportedException ();
1150 public virtual void AddBreakVector (UsageVector vector
)
1153 Parent
.AddBreakVector (vector
);
1154 else if ((Block
== null) || !Block
.IsDestructor
)
1155 throw new NotSupportedException ();
1158 public virtual void StealFinallyClauses (ref ArrayList list
)
1161 Parent
.StealFinallyClauses (ref list
);
1164 public bool IsAssigned (VariableInfo vi
)
1166 return CurrentUsageVector
.IsAssigned (vi
);
1169 public bool IsFieldAssigned (VariableInfo vi
, string field_name
)
1171 return CurrentUsageVector
.IsAssigned (vi
) || CurrentUsageVector
.IsFieldAssigned (vi
, field_name
);
1174 public void SetAssigned (VariableInfo vi
)
1176 CurrentUsageVector
.SetAssigned (vi
);
1179 public void SetFieldAssigned (VariableInfo vi
, string name
)
1181 CurrentUsageVector
.SetFieldAssigned (vi
, name
);
1184 public override string ToString ()
1186 StringBuilder sb
= new StringBuilder ();
1187 sb
.Append (GetType ());
1193 if (Block
!= null) {
1195 sb
.Append (Block
.ID
);
1197 sb
.Append (Block
.StartLocation
);
1200 // sb.Append (Siblings.Length);
1201 // sb.Append (" - ");
1202 sb
.Append (CurrentUsageVector
);
1204 return sb
.ToString ();
1207 public string Name
{
1208 get { return String.Format ("{0}
({1}
:{2}
:{3}
)", GetType (), id, Type, Location); }
1212 public class FlowBranchingBlock : FlowBranching
1214 UsageVector sibling_list = null;
1216 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
1217 SiblingType stype, Block block, Location loc)
1218 : base (parent, type, stype, block, loc)
1221 public override UsageVector CurrentUsageVector {
1222 get { return sibling_list; }
1225 protected override void AddSibling (UsageVector sibling)
1227 sibling.Next = sibling_list;
1228 sibling_list = sibling;
1231 public override LabeledStatement LookupLabel (string name, Location loc)
1234 return base.LookupLabel (name, loc);
1236 LabeledStatement s = Block.LookupLabel (name);
1240 return base.LookupLabel (name, loc);
1243 public override void Label (UsageVector origin_vectors)
1245 if (!CurrentUsageVector.Reachability.IsUnreachable) {
1246 UsageVector vector = CurrentUsageVector.Clone ();
1247 vector.Next = origin_vectors;
1248 origin_vectors = vector;
1251 CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1254 protected override UsageVector Merge ()
1256 return Merge (sibling_list);
1260 public class FlowBranchingLoop : FlowBranchingBlock
1262 UsageVector break_origins;
1264 public FlowBranchingLoop (FlowBranching parent, Block block, Location loc)
1265 : base (parent, BranchingType.Loop, SiblingType.Conditional, block, loc)
1268 public override void AddBreakVector (UsageVector vector)
1270 vector = vector.Clone ();
1271 vector.Next = break_origins;
1272 break_origins = vector;
1275 public override bool InLoop ()
1280 public override bool BreakCrossesTryCatchBoundary ()
1285 protected override UsageVector Merge ()
1287 UsageVector vector = base.Merge ();
1289 vector.MergeBreakOrigins (this, break_origins);
1291 Reachability r = vector.Reachability;
1295 } else if (Infinite) {
1298 // If we're an infinite loop and do not break,
1299 // the code after the loop can never be reached.
1300 // However, if we may return from the loop,
1301 // then we do always return (or stay in the
1307 // swallow up the 'break'
1314 public class FlowBranchingSwitch : FlowBranchingBlock
1316 UsageVector break_origins;
1318 public FlowBranchingSwitch (FlowBranching parent, Block block, Location loc)
1319 : base (parent, BranchingType.Switch, SiblingType.SwitchSection, block, loc)
1322 public override void AddBreakVector (UsageVector vector)
1324 vector = vector.Clone ();
1325 vector.Next = break_origins;
1326 break_origins = vector;
1329 public override bool InSwitch ()
1334 public override bool BreakCrossesTryCatchBoundary ()
1339 protected override UsageVector Merge ()
1341 UsageVector vector = base.Merge ();
1343 vector.MergeBreakOrigins (this, break_origins);
1345 Reachability r = vector.Reachability;
1347 if (r.MayBreak || r.MayReturn)
1356 public class FlowBranchingException : FlowBranching
1358 ExceptionStatement stmt;
1359 UsageVector current_vector;
1360 UsageVector catch_vectors;
1361 UsageVector finally_vector;
1362 UsageVector finally_origins;
1365 public FlowBranchingException (FlowBranching parent,
1366 ExceptionStatement stmt)
1367 : base (parent, BranchingType.Exception, SiblingType.Try,
1371 this.emit_finally = true;
1374 protected override void AddSibling (UsageVector sibling)
1376 if (sibling.Type == SiblingType.Try) {
1377 sibling.Next = catch_vectors;
1378 catch_vectors = sibling;
1379 } else if (sibling.Type == SiblingType.Catch) {
1380 sibling.Next = catch_vectors;
1381 catch_vectors = sibling;
1382 } else if (sibling.Type == SiblingType.Finally) {
1383 sibling.MergeFinallyOrigins (finally_origins);
1384 finally_vector = sibling;
1386 throw new InvalidOperationException ();
1388 current_vector = sibling;
1391 public override UsageVector CurrentUsageVector {
1392 get { return current_vector; }
1395 public override bool InTryOrCatch (bool is_return)
1397 return finally_vector == null;
1400 public override bool InTryWithCatch ()
1402 if (finally_vector == null) {
1403 Try t = stmt as Try;
1404 if (t != null && t.HasCatch)
1408 return base.InTryWithCatch ();
1411 public override bool BreakCrossesTryCatchBoundary ()
1416 public override void AddFinallyVector (UsageVector vector)
1418 vector = vector.Clone ();
1419 vector.Next = finally_origins;
1420 finally_origins = vector;
1423 public override void StealFinallyClauses (ref ArrayList list)
1426 list = new ArrayList ();
1428 emit_finally = false;
1429 base.StealFinallyClauses (ref list);
1432 public bool EmitFinally {
1433 get { return emit_finally; }
1436 public override LabeledStatement LookupLabel (string name, Location loc)
1438 if (current_vector.Block == null)
1439 return base.LookupLabel (name, loc);
1441 LabeledStatement s = current_vector.Block.LookupLabel (name);
1445 if (finally_vector != null) {
1446 Report.Error (157, loc,
1447 "Control cannot leave the body of a
finally clause
");
1451 return base.LookupLabel (name, loc);
1454 public override void Label (UsageVector origin_vectors)
1456 CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1459 protected override UsageVector Merge ()
1461 UsageVector vector = Merge (catch_vectors);
1463 vector.MergeFinally (finally_vector, finally_origins);
1470 // This is used by the flow analysis code to keep track of the type of local variables
1473 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1474 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1475 // you can only assign the whole variable as such.
1477 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1478 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1479 // one bit for each of its fields.
1481 // This class computes this `layout' for each type.
1483 public class TypeInfo
1485 public readonly Type Type;
1488 // Total number of bits a variable of this type consumes in the flow vector.
1490 public readonly int TotalLength;
1493 // Number of bits the simple fields of a variable of this type consume
1494 // in the flow vector.
1496 public readonly int Length;
1499 // This is only used by sub-structs.
1501 public readonly int Offset;
1504 // If this is a struct.
1506 public readonly bool IsStruct;
1509 // If this is a struct, all fields which are structs theirselves.
1511 public TypeInfo[] SubStructInfo;
1513 protected readonly StructInfo struct_info;
1514 private static Hashtable type_hash = new Hashtable ();
1516 public static TypeInfo GetTypeInfo (Type type)
1518 TypeInfo info = (TypeInfo) type_hash [type];
1522 info = new TypeInfo (type);
1523 type_hash.Add (type, info);
1527 public static TypeInfo GetTypeInfo (TypeContainer tc)
1529 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1533 info = new TypeInfo (tc);
1534 type_hash.Add (tc.TypeBuilder, info);
1538 private TypeInfo (Type type)
1542 struct_info = StructInfo.GetStructInfo (type);
1543 if (struct_info != null) {
1544 Length = struct_info.Length;
1545 TotalLength = struct_info.TotalLength;
1546 SubStructInfo = struct_info.StructFields;
1555 private TypeInfo (TypeContainer tc)
1557 this.Type = tc.TypeBuilder;
1559 struct_info = StructInfo.GetStructInfo (tc);
1560 if (struct_info != null) {
1561 Length = struct_info.Length;
1562 TotalLength = struct_info.TotalLength;
1563 SubStructInfo = struct_info.StructFields;
1572 protected TypeInfo (StructInfo struct_info, int offset)
1574 this.struct_info = struct_info;
1575 this.Offset = offset;
1576 this.Length = struct_info.Length;
1577 this.TotalLength = struct_info.TotalLength;
1578 this.SubStructInfo = struct_info.StructFields;
1579 this.Type = struct_info.Type;
1580 this.IsStruct = true;
1583 public int GetFieldIndex (string name)
1585 if (struct_info == null)
1588 return struct_info [name];
1591 public TypeInfo GetSubStruct (string name)
1593 if (struct_info == null)
1596 return struct_info.GetStructField (name);
1600 // A struct's constructor must always assign all fields.
1601 // This method checks whether it actually does so.
1603 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1605 if (struct_info == null)
1609 for (int i = 0; i < struct_info.Count; i++) {
1610 FieldInfo field = struct_info.Fields [i];
1612 if (!branching.IsFieldAssigned (vi, field.Name)) {
1613 Report.Error (171, loc,
1614 "Field `{0}
' must be fully assigned before control leaves the constructor",
1615 TypeManager.GetFullNameSignature (field));
1623 public override string ToString ()
1625 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1626 Type, Offset, Length, TotalLength);
1629 protected class StructInfo {
1630 public readonly Type Type;
1631 public readonly FieldInfo[] Fields;
1632 public readonly TypeInfo[] StructFields;
1633 public readonly int Count;
1634 public readonly int CountPublic;
1635 public readonly int CountNonPublic;
1636 public readonly int Length;
1637 public readonly int TotalLength;
1638 public readonly bool HasStructFields;
1640 private static Hashtable field_type_hash = new Hashtable ();
1641 private Hashtable struct_field_hash;
1642 private Hashtable field_hash;
1644 protected bool InTransit = false;
1646 // Private constructor. To save memory usage, we only need to create one instance
1647 // of this class per struct type.
1648 private StructInfo (Type type)
1652 field_type_hash.Add (type, this);
1654 if (type is TypeBuilder) {
1655 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1657 ArrayList fields = null;
1661 ArrayList public_fields = new ArrayList ();
1662 ArrayList non_public_fields = new ArrayList ();
1664 if (fields != null) {
1665 foreach (FieldMember field in fields) {
1666 if ((field.ModFlags & Modifiers.STATIC) != 0)
1668 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1669 public_fields.Add (field.FieldBuilder);
1671 non_public_fields.Add (field.FieldBuilder);
1675 CountPublic = public_fields.Count;
1676 CountNonPublic = non_public_fields.Count;
1677 Count = CountPublic + CountNonPublic;
1679 Fields = new FieldInfo [Count];
1680 public_fields.CopyTo (Fields, 0);
1681 non_public_fields.CopyTo (Fields, CountPublic);
1682 } else if (type is GenericTypeParameterBuilder) {
1683 CountPublic = CountNonPublic = Count = 0;
1685 Fields = new FieldInfo [0];
1687 FieldInfo[] public_fields = type.GetFields (
1688 BindingFlags.Instance|BindingFlags.Public);
1689 FieldInfo[] non_public_fields = type.GetFields (
1690 BindingFlags.Instance|BindingFlags.NonPublic);
1692 CountPublic = public_fields.Length;
1693 CountNonPublic = non_public_fields.Length;
1694 Count = CountPublic + CountNonPublic;
1696 Fields = new FieldInfo [Count];
1697 public_fields.CopyTo (Fields, 0);
1698 non_public_fields.CopyTo (Fields, CountPublic);
1701 struct_field_hash = new Hashtable ();
1702 field_hash = new Hashtable ();
1705 StructFields = new TypeInfo [Count];
1706 StructInfo[] sinfo = new StructInfo [Count];
1710 for (int i = 0; i < Count; i++) {
1711 FieldInfo field = (FieldInfo) Fields [i];
1713 sinfo [i] = GetStructInfo (field.FieldType);
1714 if (sinfo [i] == null)
1715 field_hash.Add (field.Name, ++Length);
1716 else if (sinfo [i].InTransit) {
1717 Report.Error (523, String.Format (
1718 "Struct member `{0}.{1}' of type `{2}
' causes " +
1719 "a cycle in the structure layout",
1720 type, field.Name, sinfo [i].Type));
1728 TotalLength = Length + 1;
1729 for (int i = 0; i < Count; i++) {
1730 FieldInfo field = (FieldInfo) Fields [i];
1732 if (sinfo [i] == null)
1735 field_hash.Add (field.Name, TotalLength);
1737 HasStructFields = true;
1738 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1739 struct_field_hash.Add (field.Name, StructFields [i]);
1740 TotalLength += sinfo [i].TotalLength;
1744 public int this [string name] {
1746 if (field_hash.Contains (name))
1747 return (int) field_hash [name];
1753 public TypeInfo GetStructField (string name)
1755 return (TypeInfo) struct_field_hash [name];
1758 public static StructInfo GetStructInfo (Type type)
1760 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1761 TypeManager.IsBuiltinType (type))
1764 StructInfo info = (StructInfo) field_type_hash [type];
1768 return new StructInfo (type);
1771 public static StructInfo GetStructInfo (TypeContainer tc)
1773 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1777 return new StructInfo (tc.TypeBuilder);
1783 // This is used by the flow analysis code to store information about a single local variable
1784 // or parameter. Depending on the variable's type
, we need to allocate one or more elements
1785 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1786 // it has been assigned or not, but for structs, we need this information for each of its fields.
1788 public class VariableInfo
{
1789 public readonly string Name
;
1790 public readonly TypeInfo TypeInfo
;
1793 // The bit offset of this variable in the flow vector.
1795 public readonly int Offset
;
1798 // The number of bits this variable needs in the flow vector.
1799 // The first bit always specifies whether the variable as such has been assigned while
1800 // the remaining bits contain this information for each of a struct's fields.
1802 public readonly int Length
;
1805 // If this is a parameter of local variable.
1807 public readonly bool IsParameter
;
1809 public readonly LocalInfo LocalInfo
;
1810 public readonly int ParameterIndex
;
1812 readonly VariableInfo Parent
;
1813 VariableInfo
[] sub_info
;
1815 protected VariableInfo (string name
, Type type
, int offset
)
1818 this.Offset
= offset
;
1819 this.TypeInfo
= TypeInfo
.GetTypeInfo (type
);
1821 Length
= TypeInfo
.TotalLength
;
1826 protected VariableInfo (VariableInfo parent
, TypeInfo type
)
1828 this.Name
= parent
.Name
;
1829 this.TypeInfo
= type
;
1830 this.Offset
= parent
.Offset
+ type
.Offset
;
1831 this.Parent
= parent
;
1832 this.Length
= type
.TotalLength
;
1834 this.IsParameter
= parent
.IsParameter
;
1835 this.LocalInfo
= parent
.LocalInfo
;
1836 this.ParameterIndex
= parent
.ParameterIndex
;
1841 protected void Initialize ()
1843 TypeInfo
[] sub_fields
= TypeInfo
.SubStructInfo
;
1844 if (sub_fields
!= null) {
1845 sub_info
= new VariableInfo
[sub_fields
.Length
];
1846 for (int i
= 0; i
< sub_fields
.Length
; i
++) {
1847 if (sub_fields
[i
] != null)
1848 sub_info
[i
] = new VariableInfo (this, sub_fields
[i
]);
1851 sub_info
= new VariableInfo
[0];
1854 public VariableInfo (LocalInfo local_info
, int offset
)
1855 : this (local_info
.Name
, local_info
.VariableType
, offset
)
1857 this.LocalInfo
= local_info
;
1858 this.IsParameter
= false;
1861 public VariableInfo (string name
, Type type
, int param_idx
, int offset
)
1862 : this (name
, type
, offset
)
1864 this.ParameterIndex
= param_idx
;
1865 this.IsParameter
= true;
1868 public bool IsAssigned (EmitContext ec
)
1870 return !ec
.DoFlowAnalysis
||
1871 ec
.OmitStructFlowAnalysis
&& TypeInfo
.IsStruct
||
1872 ec
.CurrentBranching
.IsAssigned (this);
1875 public bool IsAssigned (EmitContext ec
, Location loc
)
1877 if (IsAssigned (ec
))
1880 Report
.Error (165, loc
,
1881 "Use of unassigned local variable `" + Name
+ "'");
1882 ec
.CurrentBranching
.SetAssigned (this);
1886 public bool IsAssigned (MyBitVector vector
)
1888 if (vector
[Offset
])
1891 for (VariableInfo parent
= Parent
; parent
!= null; parent
= parent
.Parent
)
1892 if (vector
[parent
.Offset
])
1895 // Return unless this is a struct.
1896 if (!TypeInfo
.IsStruct
)
1899 // Ok, so each field must be assigned.
1900 for (int i
= 0; i
< TypeInfo
.Length
; i
++) {
1901 if (!vector
[Offset
+ i
+ 1])
1905 // Ok, now check all fields which are structs.
1906 for (int i
= 0; i
< sub_info
.Length
; i
++) {
1907 VariableInfo sinfo
= sub_info
[i
];
1911 if (!sinfo
.IsAssigned (vector
))
1915 vector
[Offset
] = true;
1919 public void SetAssigned (EmitContext ec
)
1921 if (ec
.DoFlowAnalysis
)
1922 ec
.CurrentBranching
.SetAssigned (this);
1925 public void SetAssigned (MyBitVector vector
)
1927 vector
[Offset
] = true;
1930 public bool IsFieldAssigned (EmitContext ec
, string name
, Location loc
)
1932 if (!ec
.DoFlowAnalysis
||
1933 ec
.OmitStructFlowAnalysis
&& TypeInfo
.IsStruct
||
1934 ec
.CurrentBranching
.IsFieldAssigned (this, name
))
1937 Report
.Error (170, loc
,
1938 "Use of possibly unassigned field `" + name
+ "'");
1939 ec
.CurrentBranching
.SetFieldAssigned (this, name
);
1943 public bool IsFieldAssigned (MyBitVector vector
, string field_name
)
1945 int field_idx
= TypeInfo
.GetFieldIndex (field_name
);
1950 return vector
[Offset
+ field_idx
];
1953 public void SetFieldAssigned (EmitContext ec
, string name
)
1955 if (ec
.DoFlowAnalysis
)
1956 ec
.CurrentBranching
.SetFieldAssigned (this, name
);
1959 public void SetFieldAssigned (MyBitVector vector
, string field_name
)
1961 int field_idx
= TypeInfo
.GetFieldIndex (field_name
);
1966 vector
[Offset
+ field_idx
] = true;
1969 public VariableInfo
GetSubStruct (string name
)
1971 TypeInfo type
= TypeInfo
.GetSubStruct (name
);
1976 return new VariableInfo (this, type
);
1979 public override string ToString ()
1981 return String
.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1982 Name
, TypeInfo
, Offset
, Length
, IsParameter
);
1987 // This is used by the flow code to hold the `layout' of the flow vector for
1988 // all locals and all parameters (ie. we create one instance of this class for the
1989 // locals and another one for the params).
1991 public class VariableMap
{
1993 // The number of variables in the map.
1995 public readonly int Count
;
1998 // Total length of the flow vector for this map.
2000 public readonly int Length
;
2004 public VariableMap (Parameters ip
)
2006 Count
= ip
!= null ? ip
.Count
: 0;
2008 // Dont bother allocating anything!
2014 for (int i
= 0; i
< Count
; i
++) {
2015 Parameter
.Modifier mod
= ip
.ParameterModifier (i
);
2017 if ((mod
& Parameter
.Modifier
.OUT
) != Parameter
.Modifier
.OUT
)
2020 // Dont allocate till we find an out var.
2022 map
= new VariableInfo
[Count
];
2024 map
[i
] = new VariableInfo (ip
.ParameterName (i
),
2025 TypeManager
.GetElementType (ip
.ParameterType (i
)), i
, Length
);
2027 Length
+= map
[i
].Length
;
2031 public VariableMap (LocalInfo
[] locals
)
2032 : this (null, locals
)
2035 public VariableMap (VariableMap parent
, LocalInfo
[] locals
)
2037 int offset
= 0, start
= 0;
2038 if (parent
!= null && parent
.map
!= null) {
2039 offset
= parent
.Length
;
2040 start
= parent
.Count
;
2043 Count
= locals
.Length
+ start
;
2048 map
= new VariableInfo
[Count
];
2051 if (parent
!= null && parent
.map
!= null) {
2052 parent
.map
.CopyTo (map
, 0);
2055 for (int i
= start
; i
< Count
; i
++) {
2056 LocalInfo li
= locals
[i
-start
];
2058 if (li
.VariableType
== null)
2061 map
[i
] = li
.VariableInfo
= new VariableInfo (li
, Length
);
2062 Length
+= map
[i
].Length
;
2067 // Returns the VariableInfo for variable @index or null if we don't need to
2068 // compute assignment info for this variable.
2070 public VariableInfo
this [int index
] {
2079 public override string ToString ()
2081 return String
.Format ("VariableMap ({0}:{1})", Count
, Length
);
2086 // This is a special bit vector which can inherit from another bit vector doing a
2087 // copy-on-write strategy. The inherited vector may have a smaller size than the
2090 public class MyBitVector
{
2091 public readonly int Count
;
2092 public readonly MyBitVector InheritsFrom
;
2097 public MyBitVector (int Count
)
2098 : this (null, Count
)
2101 public MyBitVector (MyBitVector InheritsFrom
, int Count
)
2103 this.InheritsFrom
= InheritsFrom
;
2108 // Checks whether this bit vector has been modified. After setting this to true,
2109 // we won't use the inherited vector anymore, but our own copy of it.
2111 public bool IsDirty
{
2112 get { return is_dirty; }
2116 initialize_vector ();
2121 // Get/set bit `index' in the bit vector.
2123 public bool this [int index
]
2127 throw new ArgumentOutOfRangeException ();
2129 // We're doing a "copy-on-write" strategy here; as long
2130 // as nobody writes to the array, we can use our parent's
2131 // copy instead of duplicating the vector.
2134 return vector
[index
];
2135 else if (InheritsFrom
!= null) {
2136 BitArray inherited
= InheritsFrom
.Vector
;
2138 if (index
< inherited
.Count
)
2139 return inherited
[index
];
2148 throw new ArgumentOutOfRangeException ();
2150 // Only copy the vector if we're actually modifying it.
2152 if (this [index
] != value) {
2153 initialize_vector ();
2155 vector
[index
] = value;
2161 // If you explicitly convert the MyBitVector to a BitArray, you will get a deep
2162 // copy of the bit vector.
2164 public static explicit operator BitArray (MyBitVector vector
)
2166 vector
.initialize_vector ();
2167 return vector
.Vector
;
2171 // Performs an `or' operation on the bit vector. The `new_vector' may have a
2172 // different size than the current one.
2174 public void Or (MyBitVector new_vector
)
2176 // Treat null 'new_vector' as all false, just like the And() below
2177 if (new_vector
== null)
2179 BitArray new_array
= new_vector
.Vector
;
2181 initialize_vector ();
2184 if (vector
.Count
< new_array
.Count
)
2185 upper
= vector
.Count
;
2187 upper
= new_array
.Count
;
2189 for (int i
= 0; i
< upper
; i
++)
2190 vector
[i
] = vector
[i
] | new_array
[i
];
2194 // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
2195 // a different size than the current one.
2197 public void And (MyBitVector new_vector
)
2201 if (new_vector
!= null)
2202 new_array
= new_vector
.Vector
;
2204 new_array
= new BitArray (Count
, false);
2206 initialize_vector ();
2209 if (vector
.Count
< new_array
.Count
)
2210 lower
= upper
= vector
.Count
;
2212 lower
= new_array
.Count
;
2213 upper
= vector
.Count
;
2216 for (int i
= 0; i
< lower
; i
++)
2217 vector
[i
] = vector
[i
] & new_array
[i
];
2219 for (int i
= lower
; i
< upper
; i
++)
2223 public static void And (ref MyBitVector target
, MyBitVector vector
)
2226 target
.And (vector
);
2228 target
= vector
.Clone ();
2231 public static void Or (ref MyBitVector target
, MyBitVector vector
)
2236 target
= vector
.Clone ();
2240 // This does a deep copy of the bit vector.
2242 public MyBitVector
Clone ()
2244 MyBitVector retval
= new MyBitVector (Count
);
2246 retval
.Vector
= Vector
;
2255 else if (!is_dirty
&& (InheritsFrom
!= null))
2256 return InheritsFrom
.Vector
;
2258 initialize_vector ();
2264 initialize_vector ();
2266 for (int i
= 0; i
< System
.Math
.Min (vector
.Count
, value.Count
); i
++)
2267 vector
[i
] = value [i
];
2271 void initialize_vector ()
2276 vector
= new BitArray (Count
, false);
2277 if (InheritsFrom
!= null)
2278 Vector
= InheritsFrom
.Vector
;
2283 public override string ToString ()
2285 StringBuilder sb
= new StringBuilder ("{");
2287 BitArray vector
= Vector
;
2290 for (int i
= 0; i
< vector
.Count
; i
++) {
2291 sb
.Append (vector
[i
] ? "1" : "0");
2295 return sb
.ToString ();