2 // flowanalyis.cs: The control flow analysis code
5 // Martin Baulig (martin@ximian.com)
6 // Raja R Harinath (rharinath@novell.com)
8 // (C) 2001, 2002, 2003 Ximian, Inc.
13 using System.Collections;
14 using System.Reflection;
15 using System.Reflection.Emit;
16 using System.Diagnostics;
20 public enum TriState : byte {
21 // Never < Sometimes < Always
28 // A new instance of this class is created every time a new block is resolved
29 // and if there's branching in the block's control flow.
31 public abstract class FlowBranching
34 // The type of a FlowBranching.
36 public enum BranchingType : byte {
37 // Normal (conditional or toplevel) block.
46 // The statement embedded inside a loop
49 // part of a block headed by a jump target
61 // The toplevel block of a function
66 // The type of one sibling of a branching.
68 public enum SiblingType : byte {
77 public sealed class Reachability
79 TriState returns, throws, barrier;
81 public TriState Returns {
82 get { return returns; }
84 public TriState Throws {
85 get { return throws; }
87 public TriState Barrier {
88 get { return barrier; }
91 Reachability (TriState returns, TriState throws, TriState barrier)
93 this.returns = returns;
95 this.barrier = barrier;
98 public Reachability Clone ()
100 return new Reachability (returns, throws, barrier);
103 public static TriState TriState_Meet (TriState a, TriState b)
105 // (1) if both are Never, return Never
106 // (2) if both are Always, return Always
107 // (3) otherwise, return Sometimes
108 // note that (3) => (3') if both are Sometimes, return Sometimes
109 return a == b ? a : TriState.Sometimes;
112 public static TriState TriState_Max (TriState a, TriState b)
114 return ((byte) a > (byte) b) ? a : b;
117 public void Meet (Reachability b)
119 if ((AlwaysReturns && b.AlwaysHasBarrier) || (AlwaysHasBarrier && b.AlwaysReturns))
120 returns = TriState.Always;
122 returns = TriState_Meet (returns, b.returns);
124 throws = TriState_Meet (throws, b.throws);
125 barrier = TriState_Meet (barrier, b.barrier);
128 public void Or (Reachability b)
130 returns = TriState_Max (returns, b.returns);
131 throws = TriState_Max (throws, b.throws);
132 barrier = TriState_Max (barrier, b.barrier);
135 public static Reachability Always ()
137 return new Reachability (TriState.Never, TriState.Never, TriState.Never);
140 TriState Unreachable {
141 get { return TriState_Max (returns, TriState_Max (throws, barrier)); }
146 TriState unreachable = Unreachable;
147 if (unreachable == TriState.Sometimes)
148 return TriState.Sometimes;
149 return unreachable == TriState.Always ? TriState.Never : TriState.Always;
153 public bool AlwaysReturns {
154 get { return returns == TriState.Always; }
157 public bool AlwaysThrows {
158 get { return throws == TriState.Always; }
161 public bool AlwaysHasBarrier {
162 get { return barrier == TriState.Always; }
165 public bool IsUnreachable {
166 get { return Unreachable == TriState.Always; }
169 public void SetReturns ()
171 returns = TriState.Always;
174 public void SetThrows ()
176 throws = TriState.Always;
179 public void SetBarrier ()
181 barrier = TriState.Always;
184 static string ShortName (TriState returns)
189 case TriState.Sometimes:
196 public override string ToString ()
198 return String.Format ("[{0}:{1}:{2}:{3}]",
199 ShortName (returns), ShortName (throws), ShortName (barrier),
200 ShortName (Reachable));
204 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
207 case BranchingType.Exception:
208 case BranchingType.Labeled:
209 case BranchingType.Toplevel:
210 throw new InvalidOperationException ();
212 case BranchingType.Switch:
213 return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
215 case BranchingType.SwitchSection:
216 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
218 case BranchingType.Block:
219 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
221 case BranchingType.Loop:
222 return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
224 case BranchingType.Embedded:
225 return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
228 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
233 // The type of this flow branching.
235 public readonly BranchingType Type;
238 // The block this branching is contained in. This may be null if it's not
239 // a top-level block and it doesn't declare any local variables.
241 public readonly Block Block;
244 // The parent of this branching or null if this is the top-block.
246 public readonly FlowBranching Parent;
249 // Start-Location of this flow branching.
251 public readonly Location Location;
253 protected VariableMap param_map, local_map;
255 static int next_id = 0;
259 // The vector contains a BitArray with information about which local variables
260 // and parameters are already initialized at the current code position.
262 public class UsageVector {
264 // The type of this branching.
266 public readonly SiblingType Type;
269 // Start location of this branching.
271 public Location Location;
274 // This is only valid for SwitchSection, Try, Catch and Finally.
276 public readonly Block Block;
279 // The number of parameters in this block.
281 public readonly int CountParameters;
284 // The number of locals in this block.
286 public readonly int CountLocals;
289 // If not null, then we inherit our state from this vector and do a
290 // copy-on-write. If null, then we're the first sibling in a top-level
291 // block and inherit from the empty vector.
293 public readonly UsageVector InheritsFrom;
296 // This is used to construct a list of UsageVector's.
298 public UsageVector Next;
303 MyBitVector locals, parameters;
304 Reachability reachability;
306 static int next_id = 0;
310 // Normally, you should not use any of these constructors.
312 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc, int num_params, int num_locals)
317 this.InheritsFrom = parent;
318 this.CountParameters = num_params;
319 this.CountLocals = num_locals;
321 locals = num_locals == 0
323 : new MyBitVector (parent == null ? MyBitVector.Empty : parent.locals, num_locals);
325 parameters = num_params == 0
327 : new MyBitVector (parent == null ? MyBitVector.Empty : parent.parameters, num_params);
329 reachability = parent == null ? Reachability.Always () : parent.Reachability.Clone ();
334 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
335 : this (type, parent, block, loc, parent.CountParameters, parent.CountLocals)
338 public UsageVector (MyBitVector parameters, MyBitVector locals, Reachability reachability, Block block, Location loc)
340 this.Type = SiblingType.Block;
344 this.reachability = reachability;
345 this.parameters = parameters;
346 this.locals = locals;
352 // This does a deep copy of the usage vector.
354 public UsageVector Clone ()
356 UsageVector retval = new UsageVector (Type, null, Block, Location, CountParameters, CountLocals);
358 retval.locals = locals.Clone ();
359 retval.parameters = parameters.Clone ();
360 retval.reachability = reachability.Clone ();
365 public bool IsAssigned (VariableInfo var, bool ignoreReachability)
367 if (!ignoreReachability && !var.IsParameter && Reachability.IsUnreachable)
370 return var.IsAssigned (var.IsParameter ? parameters : locals);
373 public void SetAssigned (VariableInfo var)
375 if (!var.IsParameter && Reachability.IsUnreachable)
378 var.SetAssigned (var.IsParameter ? parameters : locals);
381 public bool IsFieldAssigned (VariableInfo var, string name)
383 if (!var.IsParameter && Reachability.IsUnreachable)
386 return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
389 public void SetFieldAssigned (VariableInfo var, string name)
391 if (!var.IsParameter && Reachability.IsUnreachable)
394 var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
397 public Reachability Reachability {
398 get { return reachability; }
401 public void Return ()
403 if (!reachability.IsUnreachable)
404 reachability.SetReturns ();
409 if (!reachability.IsUnreachable) {
410 reachability.SetThrows ();
411 reachability.SetBarrier ();
417 if (!reachability.IsUnreachable)
418 reachability.SetBarrier ();
421 public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
423 if (sibling_list.Next == null)
426 MyBitVector locals = null;
427 MyBitVector parameters = null;
428 Reachability reachability = null;
430 for (UsageVector child = sibling_list; child != null; child = child.Next) {
431 Report.Debug (2, " MERGING SIBLING ", reachability, child);
433 if (reachability == null)
434 reachability = child.Reachability.Clone ();
436 reachability.Meet (child.Reachability);
438 // A local variable is initialized after a flow branching if it
439 // has been initialized in all its branches which do neither
440 // always return or always throw an exception.
442 // If a branch may return, but does not always return, then we
443 // can treat it like a never-returning branch here: control will
444 // only reach the code position after the branching if we did not
447 // It's important to distinguish between always and sometimes
448 // returning branches here:
451 // 2 if (something) {
455 // 6 Console.WriteLine (a);
457 // The if block in lines 3-4 always returns, so we must not look
458 // at the initialization of `a' in line 4 - thus it'll still be
459 // uninitialized in line 6.
461 // On the other hand, the following is allowed:
468 // 6 Console.WriteLine (a);
470 // Here, `a' is initialized in line 3 and we must not look at
471 // line 5 since it always returns.
473 bool unreachable = child.Reachability.IsUnreachable;
475 Report.Debug (2, " MERGING SIBLING #1", reachability,
476 child.Type, child.Reachability.IsUnreachable, unreachable);
479 locals &= child.locals;
481 // An `out' parameter must be assigned in all branches which do
482 // not always throw an exception.
483 if (!child.Reachability.AlwaysThrows)
484 parameters &= child.parameters;
486 Report.Debug (2, " MERGING SIBLING #2", parameters, locals);
489 if (reachability == null)
490 throw new InternalErrorException ("Cannot happen: the loop above runs at least twice");
492 return new UsageVector (parameters, locals, reachability, null, loc);
496 // Merges a child branching.
498 public UsageVector MergeChild (UsageVector child, bool overwrite)
500 Report.Debug (2, " MERGING CHILD EFFECTS", this, child, reachability, Type);
502 Reachability new_r = child.Reachability;
505 // We've now either reached the point after the branching or we will
506 // never get there since we always return or always throw an exception.
508 // If we can reach the point after the branching, mark all locals and
509 // parameters as initialized which have been initialized in all branches
510 // we need to look at (see above).
513 if ((Type == SiblingType.SwitchSection) && !new_r.IsUnreachable) {
514 Report.Error (163, Location,
515 "Control cannot fall through from one " +
516 "case label to another");
520 locals |= child.locals;
521 parameters |= child.parameters;
524 reachability = new_r.Clone ();
526 reachability.Or (new_r);
531 public void MergeOrigins (UsageVector o_vectors)
533 Report.Debug (1, " MERGING BREAK ORIGINS", this);
535 if (o_vectors == null)
538 if (reachability.IsUnreachable) {
540 locals.SetAll (true);
541 if (parameters != null)
542 parameters.SetAll (true);
545 for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
546 Report.Debug (1, " MERGING BREAK ORIGIN", vector);
547 if (vector.Reachability.IsUnreachable)
549 locals &= vector.locals;
550 parameters &= vector.parameters;
551 reachability.Meet (vector.Reachability);
554 Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
561 public override string ToString ()
563 return String.Format ("Vector ({0},{1},{2}-{3}-{4})", Type, id, reachability, parameters, locals);
568 // Creates a new flow branching which is contained in `parent'.
569 // You should only pass non-null for the `block' argument if this block
570 // introduces any new variables - in this case, we need to create a new
571 // usage vector with a different size than our parent's one.
573 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
574 Block block, Location loc)
584 param_map = Block.ParameterMap;
585 local_map = Block.LocalMap;
587 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
588 vector = new UsageVector (
589 stype, parent_vector, Block, loc,
590 param_map.Length, local_map.Length);
592 param_map = Parent.param_map;
593 local_map = Parent.local_map;
594 vector = new UsageVector (
595 stype, Parent.CurrentUsageVector, null, loc);
601 public abstract UsageVector CurrentUsageVector {
606 // Creates a sibling of the current usage vector.
608 public virtual void CreateSibling (Block block, SiblingType type)
610 UsageVector vector = new UsageVector (
611 type, Parent.CurrentUsageVector, block, Location);
614 Report.Debug (1, " CREATED SIBLING", CurrentUsageVector);
617 public void CreateSibling ()
619 CreateSibling (null, SiblingType.Conditional);
622 protected abstract void AddSibling (UsageVector uv);
624 protected abstract UsageVector Merge ();
627 // Merge a child branching.
629 public UsageVector MergeChild (FlowBranching child)
631 bool overwrite = child.Type == BranchingType.Labeled ||
632 (child.Type == BranchingType.Block && child.Block.Implicit);
633 Report.Debug (2, " MERGING CHILD", this, child);
634 UsageVector result = CurrentUsageVector.MergeChild (child.Merge (), overwrite);
635 Report.Debug (2, " MERGING CHILD DONE", this, result);
639 public virtual bool InTryWithCatch ()
641 return Parent.InTryWithCatch ();
644 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
645 public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
647 return Parent.AddBreakOrigin (vector, loc);
650 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
651 public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
653 return Parent.AddContinueOrigin (vector, loc);
656 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
657 public virtual bool AddReturnOrigin (UsageVector vector, Location loc)
659 return Parent.AddReturnOrigin (vector, loc);
662 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
663 public virtual bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
665 return Parent.AddGotoOrigin (vector, goto_stmt);
668 public virtual void StealFinallyClauses (ref ArrayList list)
670 Parent.StealFinallyClauses (ref list);
673 public bool IsAssigned (VariableInfo vi)
675 return CurrentUsageVector.IsAssigned (vi, false);
678 public bool IsFieldAssigned (VariableInfo vi, string field_name)
680 return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
683 public void SetAssigned (VariableInfo vi)
685 CurrentUsageVector.SetAssigned (vi);
688 public void SetFieldAssigned (VariableInfo vi, string name)
690 CurrentUsageVector.SetFieldAssigned (vi, name);
693 public override string ToString ()
695 StringBuilder sb = new StringBuilder ();
696 sb.Append (GetType ());
704 sb.Append (Block.ID);
706 sb.Append (Block.StartLocation);
709 // sb.Append (Siblings.Length);
710 // sb.Append (" - ");
711 sb.Append (CurrentUsageVector);
713 return sb.ToString ();
717 get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
721 public class FlowBranchingBlock : FlowBranching
723 UsageVector sibling_list = null;
725 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
726 SiblingType stype, Block block, Location loc)
727 : base (parent, type, stype, block, loc)
730 public override UsageVector CurrentUsageVector {
731 get { return sibling_list; }
734 protected override void AddSibling (UsageVector sibling)
736 sibling.Next = sibling_list;
737 sibling_list = sibling;
740 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
742 LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
744 return Parent.AddGotoOrigin (vector, goto_stmt);
747 goto_stmt.SetResolvedTarget (stmt);
748 stmt.AddUsageVector (vector);
752 protected override UsageVector Merge ()
754 Report.Debug (2, " MERGING SIBLINGS", Name);
755 UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
756 Report.Debug (2, " MERGING SIBLINGS DONE", Name, vector);
761 public class FlowBranchingBreakable : FlowBranchingBlock
763 UsageVector break_origins;
765 public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
766 : base (parent, type, stype, block, loc)
769 public override bool AddBreakOrigin (UsageVector vector, Location loc)
771 vector = vector.Clone ();
772 vector.Next = break_origins;
773 break_origins = vector;
777 protected override UsageVector Merge ()
779 UsageVector vector = base.Merge ();
780 vector.MergeOrigins (break_origins);
785 public class FlowBranchingContinuable : FlowBranchingBlock
787 UsageVector continue_origins;
789 public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
790 : base (parent, type, stype, block, loc)
793 public override bool AddContinueOrigin (UsageVector vector, Location loc)
795 vector = vector.Clone ();
796 vector.Next = continue_origins;
797 continue_origins = vector;
801 protected override UsageVector Merge ()
803 UsageVector vector = base.Merge ();
804 vector.MergeOrigins (continue_origins);
809 public class FlowBranchingLabeled : FlowBranchingBlock
811 LabeledStatement stmt;
814 public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
815 : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
818 CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
819 actual = CurrentUsageVector.Clone ();
821 // stand-in for backward jumps
822 CurrentUsageVector.Reachability.Meet (Reachability.Always ());
825 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
827 if (goto_stmt.Target != stmt.Name)
828 return Parent.AddGotoOrigin (vector, goto_stmt);
831 goto_stmt.SetResolvedTarget (stmt);
832 actual.MergeOrigins (vector.Clone ());
837 protected override UsageVector Merge ()
839 UsageVector vector = base.Merge ();
841 if (actual.Reachability.IsUnreachable)
842 Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
844 actual.MergeChild (vector, false);
849 public class FlowBranchingToplevel : FlowBranchingBlock
851 UsageVector return_origins;
853 public FlowBranchingToplevel (FlowBranching parent, ToplevelBlock stmt)
854 : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
859 // Check whether all `out' parameters have been assigned.
861 void CheckOutParameters (UsageVector vector, Location loc)
863 if (vector.Reachability.IsUnreachable)
865 for (int i = 0; i < param_map.Count; i++) {
866 VariableInfo var = param_map [i];
871 if (vector.IsAssigned (var, false))
874 Report.Error (177, loc, "The out parameter `{0}' must be assigned to before control leaves the current method",
879 public override bool InTryWithCatch ()
884 public override bool AddBreakOrigin (UsageVector vector, Location loc)
886 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
890 public override bool AddContinueOrigin (UsageVector vector, Location loc)
892 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
896 public override bool AddReturnOrigin (UsageVector vector, Location loc)
898 vector = vector.Clone ();
899 vector.Location = loc;
900 vector.Next = return_origins;
901 return_origins = vector;
905 public override void StealFinallyClauses (ref ArrayList list)
910 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
912 string name = goto_stmt.Target;
913 LabeledStatement s = Block.LookupLabel (name);
915 throw new InternalErrorException ("Shouldn't get here");
917 if (Parent == null) {
918 Report.Error (159, goto_stmt.loc, "No such label `{0}' in this scope", name);
922 int errors = Report.Errors;
923 Parent.AddGotoOrigin (vector, goto_stmt);
924 if (errors == Report.Errors)
925 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
929 protected override UsageVector Merge ()
931 for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
932 CheckOutParameters (origin, origin.Location);
934 UsageVector vector = base.Merge ();
935 CheckOutParameters (vector, Block.loc);
936 // Note: we _do_not_ merge in the return origins
940 public Reachability End ()
942 return Merge ().Reachability;
946 public class FlowBranchingException : FlowBranching
948 ExceptionStatement stmt;
949 UsageVector current_vector;
950 UsageVector catch_vectors;
951 UsageVector finally_vector;
953 UsageVector break_origins;
954 UsageVector continue_origins;
955 UsageVector return_origins;
956 GotoOrigin goto_origins;
959 public GotoOrigin Next;
960 public Goto GotoStmt;
961 public UsageVector Vector;
963 public GotoOrigin (UsageVector vector, Goto goto_stmt, GotoOrigin next)
966 GotoStmt = goto_stmt;
973 public FlowBranchingException (FlowBranching parent,
974 ExceptionStatement stmt)
975 : base (parent, BranchingType.Exception, SiblingType.Try,
979 this.emit_finally = true;
982 protected override void AddSibling (UsageVector sibling)
984 switch (sibling.Type) {
985 case SiblingType.Try:
986 case SiblingType.Catch:
987 sibling.Next = catch_vectors;
988 catch_vectors = sibling;
990 case SiblingType.Finally:
991 finally_vector = sibling;
994 throw new InvalidOperationException ();
996 current_vector = sibling;
999 public override UsageVector CurrentUsageVector {
1000 get { return current_vector; }
1003 public override bool InTryWithCatch ()
1005 if (finally_vector == null) {
1006 Try t = stmt as Try;
1007 if (t != null && t.HasCatch)
1011 return base.InTryWithCatch ();
1014 public override bool AddBreakOrigin (UsageVector vector, Location loc)
1016 vector = vector.Clone ();
1017 if (finally_vector != null) {
1018 vector.MergeChild (finally_vector, false);
1019 int errors = Report.Errors;
1020 Parent.AddBreakOrigin (vector, loc);
1021 if (errors == Report.Errors)
1022 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1024 vector.Location = loc;
1025 vector.Next = break_origins;
1026 break_origins = vector;
1031 public override bool AddContinueOrigin (UsageVector vector, Location loc)
1033 vector = vector.Clone ();
1034 if (finally_vector != null) {
1035 vector.MergeChild (finally_vector, false);
1036 int errors = Report.Errors;
1037 Parent.AddContinueOrigin (vector, loc);
1038 if (errors == Report.Errors)
1039 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1041 vector.Location = loc;
1042 vector.Next = continue_origins;
1043 continue_origins = vector;
1048 public override bool AddReturnOrigin (UsageVector vector, Location loc)
1050 vector = vector.Clone ();
1051 if (finally_vector != null) {
1052 vector.MergeChild (finally_vector, false);
1053 int errors = Report.Errors;
1054 Parent.AddReturnOrigin (vector, loc);
1055 if (errors == Report.Errors)
1056 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1058 vector.Location = loc;
1059 vector.Next = return_origins;
1060 return_origins = vector;
1065 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
1067 LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
1069 throw new InternalErrorException ("Shouldn't get here");
1071 vector = vector.Clone ();
1072 if (finally_vector != null) {
1073 vector.MergeChild (finally_vector, false);
1074 int errors = Report.Errors;
1075 Parent.AddGotoOrigin (vector, goto_stmt);
1076 if (errors == Report.Errors)
1077 Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
1079 goto_origins = new GotoOrigin (vector, goto_stmt, goto_origins);
1084 public override void StealFinallyClauses (ref ArrayList list)
1087 list = new ArrayList ();
1089 emit_finally = false;
1090 base.StealFinallyClauses (ref list);
1093 public bool EmitFinally {
1094 get { return emit_finally; }
1097 protected override UsageVector Merge ()
1099 Report.Debug (2, " MERGING TRY/CATCH", Name);
1100 UsageVector vector = UsageVector.MergeSiblings (catch_vectors, Location);
1101 Report.Debug (2, " MERGING TRY/CATCH DONE", vector);
1103 if (finally_vector != null)
1104 vector.MergeChild (finally_vector, false);
1106 for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
1107 if (finally_vector != null)
1108 origin.MergeChild (finally_vector, false);
1109 Parent.AddBreakOrigin (origin, origin.Location);
1112 for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
1113 if (finally_vector != null)
1114 origin.MergeChild (finally_vector, false);
1115 Parent.AddContinueOrigin (origin, origin.Location);
1118 for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
1119 if (finally_vector != null)
1120 origin.MergeChild (finally_vector, false);
1121 Parent.AddReturnOrigin (origin, origin.Location);
1124 for (GotoOrigin origin = goto_origins; origin != null; origin = origin.Next) {
1125 if (finally_vector != null)
1126 origin.Vector.MergeChild (finally_vector, false);
1127 Parent.AddGotoOrigin (origin.Vector, origin.GotoStmt);
1135 // This is used by the flow analysis code to keep track of the type of local variables
1138 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1139 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1140 // you can only assign the whole variable as such.
1142 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1143 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1144 // one bit for each of its fields.
1146 // This class computes this `layout' for each type.
1148 public class TypeInfo
1150 public readonly Type Type;
1153 // Total number of bits a variable of this type consumes in the flow vector.
1155 public readonly int TotalLength;
1158 // Number of bits the simple fields of a variable of this type consume
1159 // in the flow vector.
1161 public readonly int Length;
1164 // This is only used by sub-structs.
1166 public readonly int Offset;
1169 // If this is a struct.
1171 public readonly bool IsStruct;
1174 // If this is a struct, all fields which are structs theirselves.
1176 public TypeInfo[] SubStructInfo;
1178 protected readonly StructInfo struct_info;
1179 private static Hashtable type_hash = new Hashtable ();
1181 public static TypeInfo GetTypeInfo (Type type)
1183 TypeInfo info = (TypeInfo) type_hash [type];
1187 info = new TypeInfo (type);
1188 type_hash.Add (type, info);
1192 public static TypeInfo GetTypeInfo (TypeContainer tc)
1194 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1198 info = new TypeInfo (tc);
1199 type_hash.Add (tc.TypeBuilder, info);
1203 private TypeInfo (Type type)
1207 struct_info = StructInfo.GetStructInfo (type);
1208 if (struct_info != null) {
1209 Length = struct_info.Length;
1210 TotalLength = struct_info.TotalLength;
1211 SubStructInfo = struct_info.StructFields;
1220 private TypeInfo (TypeContainer tc)
1222 this.Type = tc.TypeBuilder;
1224 struct_info = StructInfo.GetStructInfo (tc);
1225 if (struct_info != null) {
1226 Length = struct_info.Length;
1227 TotalLength = struct_info.TotalLength;
1228 SubStructInfo = struct_info.StructFields;
1237 protected TypeInfo (StructInfo struct_info, int offset)
1239 this.struct_info = struct_info;
1240 this.Offset = offset;
1241 this.Length = struct_info.Length;
1242 this.TotalLength = struct_info.TotalLength;
1243 this.SubStructInfo = struct_info.StructFields;
1244 this.Type = struct_info.Type;
1245 this.IsStruct = true;
1248 public int GetFieldIndex (string name)
1250 if (struct_info == null)
1253 return struct_info [name];
1256 public TypeInfo GetSubStruct (string name)
1258 if (struct_info == null)
1261 return struct_info.GetStructField (name);
1265 // A struct's constructor must always assign all fields.
1266 // This method checks whether it actually does so.
1268 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1270 if (struct_info == null)
1274 for (int i = 0; i < struct_info.Count; i++) {
1275 FieldInfo field = struct_info.Fields [i];
1277 if (!branching.IsFieldAssigned (vi, field.Name)) {
1278 Report.Error (171, loc,
1279 "Field `{0}' must be fully assigned before control leaves the constructor",
1280 TypeManager.GetFullNameSignature (field));
1288 public override string ToString ()
1290 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1291 Type, Offset, Length, TotalLength);
1294 protected class StructInfo {
1295 public readonly Type Type;
1296 public readonly FieldInfo[] Fields;
1297 public readonly TypeInfo[] StructFields;
1298 public readonly int Count;
1299 public readonly int CountPublic;
1300 public readonly int CountNonPublic;
1301 public readonly int Length;
1302 public readonly int TotalLength;
1303 public readonly bool HasStructFields;
1305 private static Hashtable field_type_hash = new Hashtable ();
1306 private Hashtable struct_field_hash;
1307 private Hashtable field_hash;
1309 protected bool InTransit = false;
1311 // Private constructor. To save memory usage, we only need to create one instance
1312 // of this class per struct type.
1313 private StructInfo (Type type)
1317 field_type_hash.Add (type, this);
1319 if (type is TypeBuilder) {
1320 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1322 ArrayList fields = null;
1326 ArrayList public_fields = new ArrayList ();
1327 ArrayList non_public_fields = new ArrayList ();
1329 if (fields != null) {
1330 foreach (FieldMember field in fields) {
1331 if ((field.ModFlags & Modifiers.STATIC) != 0)
1333 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1334 public_fields.Add (field.FieldBuilder);
1336 non_public_fields.Add (field.FieldBuilder);
1340 CountPublic = public_fields.Count;
1341 CountNonPublic = non_public_fields.Count;
1342 Count = CountPublic + CountNonPublic;
1344 Fields = new FieldInfo [Count];
1345 public_fields.CopyTo (Fields, 0);
1346 non_public_fields.CopyTo (Fields, CountPublic);
1348 } else if (type is GenericTypeParameterBuilder) {
1349 CountPublic = CountNonPublic = Count = 0;
1351 Fields = new FieldInfo [0];
1354 FieldInfo[] public_fields = type.GetFields (
1355 BindingFlags.Instance|BindingFlags.Public);
1356 FieldInfo[] non_public_fields = type.GetFields (
1357 BindingFlags.Instance|BindingFlags.NonPublic);
1359 CountPublic = public_fields.Length;
1360 CountNonPublic = non_public_fields.Length;
1361 Count = CountPublic + CountNonPublic;
1363 Fields = new FieldInfo [Count];
1364 public_fields.CopyTo (Fields, 0);
1365 non_public_fields.CopyTo (Fields, CountPublic);
1368 struct_field_hash = new Hashtable ();
1369 field_hash = new Hashtable ();
1372 StructFields = new TypeInfo [Count];
1373 StructInfo[] sinfo = new StructInfo [Count];
1377 for (int i = 0; i < Count; i++) {
1378 FieldInfo field = (FieldInfo) Fields [i];
1380 sinfo [i] = GetStructInfo (field.FieldType);
1381 if (sinfo [i] == null)
1382 field_hash.Add (field.Name, ++Length);
1383 else if (sinfo [i].InTransit) {
1384 Report.Error (523, String.Format (
1385 "Struct member `{0}.{1}' of type `{2}' causes " +
1386 "a cycle in the structure layout",
1387 type, field.Name, sinfo [i].Type));
1395 TotalLength = Length + 1;
1396 for (int i = 0; i < Count; i++) {
1397 FieldInfo field = (FieldInfo) Fields [i];
1399 if (sinfo [i] == null)
1402 field_hash.Add (field.Name, TotalLength);
1404 HasStructFields = true;
1405 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1406 struct_field_hash.Add (field.Name, StructFields [i]);
1407 TotalLength += sinfo [i].TotalLength;
1411 public int this [string name] {
1413 if (field_hash.Contains (name))
1414 return (int) field_hash [name];
1420 public TypeInfo GetStructField (string name)
1422 return (TypeInfo) struct_field_hash [name];
1425 public static StructInfo GetStructInfo (Type type)
1427 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1428 TypeManager.IsBuiltinType (type))
1431 StructInfo info = (StructInfo) field_type_hash [type];
1435 return new StructInfo (type);
1438 public static StructInfo GetStructInfo (TypeContainer tc)
1440 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1444 return new StructInfo (tc.TypeBuilder);
1450 // This is used by the flow analysis code to store information about a single local variable
1451 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1452 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1453 // it has been assigned or not, but for structs, we need this information for each of its fields.
1455 public class VariableInfo {
1456 public readonly string Name;
1457 public readonly TypeInfo TypeInfo;
1460 // The bit offset of this variable in the flow vector.
1462 public readonly int Offset;
1465 // The number of bits this variable needs in the flow vector.
1466 // The first bit always specifies whether the variable as such has been assigned while
1467 // the remaining bits contain this information for each of a struct's fields.
1469 public readonly int Length;
1472 // If this is a parameter of local variable.
1474 public readonly bool IsParameter;
1476 public readonly LocalInfo LocalInfo;
1477 public readonly int ParameterIndex;
1479 readonly VariableInfo Parent;
1480 VariableInfo[] sub_info;
1482 protected VariableInfo (string name, Type type, int offset)
1485 this.Offset = offset;
1486 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1488 Length = TypeInfo.TotalLength;
1493 protected VariableInfo (VariableInfo parent, TypeInfo type)
1495 this.Name = parent.Name;
1496 this.TypeInfo = type;
1497 this.Offset = parent.Offset + type.Offset;
1498 this.Parent = parent;
1499 this.Length = type.TotalLength;
1501 this.IsParameter = parent.IsParameter;
1502 this.LocalInfo = parent.LocalInfo;
1503 this.ParameterIndex = parent.ParameterIndex;
1508 protected void Initialize ()
1510 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1511 if (sub_fields != null) {
1512 sub_info = new VariableInfo [sub_fields.Length];
1513 for (int i = 0; i < sub_fields.Length; i++) {
1514 if (sub_fields [i] != null)
1515 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1518 sub_info = new VariableInfo [0];
1521 public VariableInfo (LocalInfo local_info, int offset)
1522 : this (local_info.Name, local_info.VariableType, offset)
1524 this.LocalInfo = local_info;
1525 this.IsParameter = false;
1528 public VariableInfo (string name, Type type, int param_idx, int offset)
1529 : this (name, type, offset)
1531 this.ParameterIndex = param_idx;
1532 this.IsParameter = true;
1535 public bool IsAssigned (EmitContext ec)
1537 return !ec.DoFlowAnalysis ||
1538 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1539 ec.CurrentBranching.IsAssigned (this);
1542 public bool IsAssigned (EmitContext ec, Location loc)
1544 if (IsAssigned (ec))
1547 Report.Error (165, loc,
1548 "Use of unassigned local variable `" + Name + "'");
1549 ec.CurrentBranching.SetAssigned (this);
1553 public bool IsAssigned (MyBitVector vector)
1558 if (vector [Offset])
1561 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1562 if (vector [parent.Offset])
1565 // Return unless this is a struct.
1566 if (!TypeInfo.IsStruct)
1569 // Ok, so each field must be assigned.
1570 for (int i = 0; i < TypeInfo.Length; i++) {
1571 if (!vector [Offset + i + 1])
1575 // Ok, now check all fields which are structs.
1576 for (int i = 0; i < sub_info.Length; i++) {
1577 VariableInfo sinfo = sub_info [i];
1581 if (!sinfo.IsAssigned (vector))
1585 vector [Offset] = true;
1589 public void SetAssigned (EmitContext ec)
1591 if (ec.DoFlowAnalysis)
1592 ec.CurrentBranching.SetAssigned (this);
1595 public void SetAssigned (MyBitVector vector)
1597 vector [Offset] = true;
1600 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1602 if (!ec.DoFlowAnalysis ||
1603 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1604 ec.CurrentBranching.IsFieldAssigned (this, name))
1607 Report.Error (170, loc,
1608 "Use of possibly unassigned field `" + name + "'");
1609 ec.CurrentBranching.SetFieldAssigned (this, name);
1613 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1615 int field_idx = TypeInfo.GetFieldIndex (field_name);
1620 return vector [Offset + field_idx];
1623 public void SetFieldAssigned (EmitContext ec, string name)
1625 if (ec.DoFlowAnalysis)
1626 ec.CurrentBranching.SetFieldAssigned (this, name);
1629 public void SetFieldAssigned (MyBitVector vector, string field_name)
1631 int field_idx = TypeInfo.GetFieldIndex (field_name);
1636 vector [Offset + field_idx] = true;
1639 public VariableInfo GetSubStruct (string name)
1641 TypeInfo type = TypeInfo.GetSubStruct (name);
1646 return new VariableInfo (this, type);
1649 public override string ToString ()
1651 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1652 Name, TypeInfo, Offset, Length, IsParameter);
1657 // This is used by the flow code to hold the `layout' of the flow vector for
1658 // all locals and all parameters (ie. we create one instance of this class for the
1659 // locals and another one for the params).
1661 public class VariableMap {
1663 // The number of variables in the map.
1665 public readonly int Count;
1668 // Total length of the flow vector for this map.
1670 public readonly int Length;
1674 public VariableMap (Parameters ip)
1676 Count = ip != null ? ip.Count : 0;
1678 // Dont bother allocating anything!
1684 for (int i = 0; i < Count; i++) {
1685 Parameter.Modifier mod = ip.ParameterModifier (i);
1687 if ((mod & Parameter.Modifier.OUT) != Parameter.Modifier.OUT)
1690 // Dont allocate till we find an out var.
1692 map = new VariableInfo [Count];
1694 map [i] = new VariableInfo (ip.ParameterName (i),
1695 TypeManager.GetElementType (ip.ParameterType (i)), i, Length);
1697 Length += map [i].Length;
1701 public VariableMap (LocalInfo[] locals)
1702 : this (null, locals)
1705 public VariableMap (VariableMap parent, LocalInfo[] locals)
1707 int offset = 0, start = 0;
1708 if (parent != null && parent.map != null) {
1709 offset = parent.Length;
1710 start = parent.Count;
1713 Count = locals.Length + start;
1718 map = new VariableInfo [Count];
1721 if (parent != null && parent.map != null) {
1722 parent.map.CopyTo (map, 0);
1725 for (int i = start; i < Count; i++) {
1726 LocalInfo li = locals [i-start];
1728 if (li.VariableType == null)
1731 map [i] = li.VariableInfo = new VariableInfo (li, Length);
1732 Length += map [i].Length;
1737 // Returns the VariableInfo for variable @index or null if we don't need to
1738 // compute assignment info for this variable.
1740 public VariableInfo this [int index] {
1749 public override string ToString ()
1751 return String.Format ("VariableMap ({0}:{1})", Count, Length);
1756 // This is a special bit vector which can inherit from another bit vector doing a
1757 // copy-on-write strategy. The inherited vector may have a smaller size than the
1760 public class MyBitVector {
1761 public readonly int Count;
1762 public static readonly MyBitVector Empty = new MyBitVector ();
1764 // Invariant: vector != null => vector.Count == Count
1765 // Invariant: vector == null || shared == null
1766 // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
1767 // The object in 'shared' cannot be modified, while 'vector' can be freely modified
1768 BitArray vector, shared;
1772 shared = new BitArray (0, false);
1775 public MyBitVector (MyBitVector InheritsFrom, int Count)
1777 if (InheritsFrom != null)
1778 shared = InheritsFrom.Shared;
1783 // Use this accessor to get a shareable copy of the underlying BitArray representation
1786 // Post-condition: vector == null
1787 if (shared == null) {
1796 // Get/set bit `index' in the bit vector.
1798 public bool this [int index] {
1801 throw new ArgumentOutOfRangeException ();
1804 return vector [index];
1807 if (index < shared.Count)
1808 return shared [index];
1813 // Only copy the vector if we're actually modifying it.
1814 if (this [index] != value) {
1816 initialize_vector ();
1817 vector [index] = value;
1823 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1824 // different size than the current one.
1826 private MyBitVector Or (MyBitVector new_vector)
1828 if (Count == 0 || new_vector.Count == 0)
1831 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1834 int n = new_vector.Count;
1836 for (int i = 0; i < n; ++i)
1844 if (Count == o.Count) {
1845 if (vector == null) {
1848 initialize_vector ();
1858 for (int i = 0; i < min; i++) {
1867 // Performs an `and' operation on the bit vector. The `new_vector' may have
1868 // a different size than the current one.
1870 private MyBitVector And (MyBitVector new_vector)
1875 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1878 for (int i = new_vector.Count; i < Count; ++i)
1888 if (Count == o.Count) {
1889 if (vector == null) {
1890 if (shared == null) {
1891 shared = new_vector.Shared;
1894 initialize_vector ();
1904 for (int i = 0; i < min; i++) {
1909 for (int i = min; i < Count; i++)
1915 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1923 if (a.Count > b.Count)
1924 return a.Clone ().And (b);
1926 return b.Clone ().And (a);
1929 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1934 return new MyBitVector (null, b.Count);
1936 return new MyBitVector (null, a.Count);
1937 if (a.Count > b.Count)
1938 return a.Clone ().Or (b);
1940 return b.Clone ().Or (a);
1943 public MyBitVector Clone ()
1945 return Count == 0 ? Empty : new MyBitVector (this, Count);
1948 public void SetAll (bool value)
1950 // Don't clobber Empty
1953 shared = value ? null : Empty.Shared;
1957 void initialize_vector ()
1959 // Post-condition: vector != null
1960 if (shared == null) {
1961 vector = new BitArray (Count, true);
1965 vector = new BitArray (shared);
1966 if (Count != vector.Count)
1967 vector.Length = Count;
1971 StringBuilder Dump (StringBuilder sb)
1973 BitArray dump = vector == null ? shared : vector;
1975 return sb.Append ("/");
1978 for (int i = 0; i < dump.Count; i++)
1979 sb.Append (dump [i] ? "1" : "0");
1983 public override string ToString ()
1985 return Dump (new StringBuilder ("{")).Append ("}").ToString ();