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);
1347 } else if (type is GenericTypeParameterBuilder) {
1348 CountPublic = CountNonPublic = Count = 0;
1350 Fields = new FieldInfo [0];
1352 FieldInfo[] public_fields = type.GetFields (
1353 BindingFlags.Instance|BindingFlags.Public);
1354 FieldInfo[] non_public_fields = type.GetFields (
1355 BindingFlags.Instance|BindingFlags.NonPublic);
1357 CountPublic = public_fields.Length;
1358 CountNonPublic = non_public_fields.Length;
1359 Count = CountPublic + CountNonPublic;
1361 Fields = new FieldInfo [Count];
1362 public_fields.CopyTo (Fields, 0);
1363 non_public_fields.CopyTo (Fields, CountPublic);
1366 struct_field_hash = new Hashtable ();
1367 field_hash = new Hashtable ();
1370 StructFields = new TypeInfo [Count];
1371 StructInfo[] sinfo = new StructInfo [Count];
1375 for (int i = 0; i < Count; i++) {
1376 FieldInfo field = (FieldInfo) Fields [i];
1378 sinfo [i] = GetStructInfo (field.FieldType);
1379 if (sinfo [i] == null)
1380 field_hash.Add (field.Name, ++Length);
1381 else if (sinfo [i].InTransit) {
1382 Report.Error (523, String.Format (
1383 "Struct member `{0}.{1}' of type `{2}' causes " +
1384 "a cycle in the structure layout",
1385 type, field.Name, sinfo [i].Type));
1393 TotalLength = Length + 1;
1394 for (int i = 0; i < Count; i++) {
1395 FieldInfo field = (FieldInfo) Fields [i];
1397 if (sinfo [i] == null)
1400 field_hash.Add (field.Name, TotalLength);
1402 HasStructFields = true;
1403 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1404 struct_field_hash.Add (field.Name, StructFields [i]);
1405 TotalLength += sinfo [i].TotalLength;
1409 public int this [string name] {
1411 if (field_hash.Contains (name))
1412 return (int) field_hash [name];
1418 public TypeInfo GetStructField (string name)
1420 return (TypeInfo) struct_field_hash [name];
1423 public static StructInfo GetStructInfo (Type type)
1425 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1426 TypeManager.IsBuiltinType (type))
1429 StructInfo info = (StructInfo) field_type_hash [type];
1433 return new StructInfo (type);
1436 public static StructInfo GetStructInfo (TypeContainer tc)
1438 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1442 return new StructInfo (tc.TypeBuilder);
1448 // This is used by the flow analysis code to store information about a single local variable
1449 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1450 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1451 // it has been assigned or not, but for structs, we need this information for each of its fields.
1453 public class VariableInfo {
1454 public readonly string Name;
1455 public readonly TypeInfo TypeInfo;
1458 // The bit offset of this variable in the flow vector.
1460 public readonly int Offset;
1463 // The number of bits this variable needs in the flow vector.
1464 // The first bit always specifies whether the variable as such has been assigned while
1465 // the remaining bits contain this information for each of a struct's fields.
1467 public readonly int Length;
1470 // If this is a parameter of local variable.
1472 public readonly bool IsParameter;
1474 public readonly LocalInfo LocalInfo;
1475 public readonly int ParameterIndex;
1477 readonly VariableInfo Parent;
1478 VariableInfo[] sub_info;
1480 protected VariableInfo (string name, Type type, int offset)
1483 this.Offset = offset;
1484 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1486 Length = TypeInfo.TotalLength;
1491 protected VariableInfo (VariableInfo parent, TypeInfo type)
1493 this.Name = parent.Name;
1494 this.TypeInfo = type;
1495 this.Offset = parent.Offset + type.Offset;
1496 this.Parent = parent;
1497 this.Length = type.TotalLength;
1499 this.IsParameter = parent.IsParameter;
1500 this.LocalInfo = parent.LocalInfo;
1501 this.ParameterIndex = parent.ParameterIndex;
1506 protected void Initialize ()
1508 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1509 if (sub_fields != null) {
1510 sub_info = new VariableInfo [sub_fields.Length];
1511 for (int i = 0; i < sub_fields.Length; i++) {
1512 if (sub_fields [i] != null)
1513 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1516 sub_info = new VariableInfo [0];
1519 public VariableInfo (LocalInfo local_info, int offset)
1520 : this (local_info.Name, local_info.VariableType, offset)
1522 this.LocalInfo = local_info;
1523 this.IsParameter = false;
1526 public VariableInfo (string name, Type type, int param_idx, int offset)
1527 : this (name, type, offset)
1529 this.ParameterIndex = param_idx;
1530 this.IsParameter = true;
1533 public bool IsAssigned (EmitContext ec)
1535 return !ec.DoFlowAnalysis ||
1536 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1537 ec.CurrentBranching.IsAssigned (this);
1540 public bool IsAssigned (EmitContext ec, Location loc)
1542 if (IsAssigned (ec))
1545 Report.Error (165, loc,
1546 "Use of unassigned local variable `" + Name + "'");
1547 ec.CurrentBranching.SetAssigned (this);
1551 public bool IsAssigned (MyBitVector vector)
1556 if (vector [Offset])
1559 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1560 if (vector [parent.Offset])
1563 // Return unless this is a struct.
1564 if (!TypeInfo.IsStruct)
1567 // Ok, so each field must be assigned.
1568 for (int i = 0; i < TypeInfo.Length; i++) {
1569 if (!vector [Offset + i + 1])
1573 // Ok, now check all fields which are structs.
1574 for (int i = 0; i < sub_info.Length; i++) {
1575 VariableInfo sinfo = sub_info [i];
1579 if (!sinfo.IsAssigned (vector))
1583 vector [Offset] = true;
1587 public void SetAssigned (EmitContext ec)
1589 if (ec.DoFlowAnalysis)
1590 ec.CurrentBranching.SetAssigned (this);
1593 public void SetAssigned (MyBitVector vector)
1595 vector [Offset] = true;
1598 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1600 if (!ec.DoFlowAnalysis ||
1601 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1602 ec.CurrentBranching.IsFieldAssigned (this, name))
1605 Report.Error (170, loc,
1606 "Use of possibly unassigned field `" + name + "'");
1607 ec.CurrentBranching.SetFieldAssigned (this, name);
1611 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1613 int field_idx = TypeInfo.GetFieldIndex (field_name);
1618 return vector [Offset + field_idx];
1621 public void SetFieldAssigned (EmitContext ec, string name)
1623 if (ec.DoFlowAnalysis)
1624 ec.CurrentBranching.SetFieldAssigned (this, name);
1627 public void SetFieldAssigned (MyBitVector vector, string field_name)
1629 int field_idx = TypeInfo.GetFieldIndex (field_name);
1634 vector [Offset + field_idx] = true;
1637 public VariableInfo GetSubStruct (string name)
1639 TypeInfo type = TypeInfo.GetSubStruct (name);
1644 return new VariableInfo (this, type);
1647 public override string ToString ()
1649 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1650 Name, TypeInfo, Offset, Length, IsParameter);
1655 // This is used by the flow code to hold the `layout' of the flow vector for
1656 // all locals and all parameters (ie. we create one instance of this class for the
1657 // locals and another one for the params).
1659 public class VariableMap {
1661 // The number of variables in the map.
1663 public readonly int Count;
1666 // Total length of the flow vector for this map.
1668 public readonly int Length;
1672 public VariableMap (Parameters ip)
1674 Count = ip != null ? ip.Count : 0;
1676 // Dont bother allocating anything!
1682 for (int i = 0; i < Count; i++) {
1683 Parameter.Modifier mod = ip.ParameterModifier (i);
1685 if ((mod & Parameter.Modifier.OUT) != Parameter.Modifier.OUT)
1688 // Dont allocate till we find an out var.
1690 map = new VariableInfo [Count];
1692 map [i] = new VariableInfo (ip.ParameterName (i),
1693 TypeManager.GetElementType (ip.ParameterType (i)), i, Length);
1695 Length += map [i].Length;
1699 public VariableMap (LocalInfo[] locals)
1700 : this (null, locals)
1703 public VariableMap (VariableMap parent, LocalInfo[] locals)
1705 int offset = 0, start = 0;
1706 if (parent != null && parent.map != null) {
1707 offset = parent.Length;
1708 start = parent.Count;
1711 Count = locals.Length + start;
1716 map = new VariableInfo [Count];
1719 if (parent != null && parent.map != null) {
1720 parent.map.CopyTo (map, 0);
1723 for (int i = start; i < Count; i++) {
1724 LocalInfo li = locals [i-start];
1726 if (li.VariableType == null)
1729 map [i] = li.VariableInfo = new VariableInfo (li, Length);
1730 Length += map [i].Length;
1735 // Returns the VariableInfo for variable @index or null if we don't need to
1736 // compute assignment info for this variable.
1738 public VariableInfo this [int index] {
1747 public override string ToString ()
1749 return String.Format ("VariableMap ({0}:{1})", Count, Length);
1754 // This is a special bit vector which can inherit from another bit vector doing a
1755 // copy-on-write strategy. The inherited vector may have a smaller size than the
1758 public class MyBitVector {
1759 public readonly int Count;
1760 public static readonly MyBitVector Empty = new MyBitVector ();
1762 BitArray vector, shared;
1767 shared = new BitArray (0, false);
1771 public MyBitVector (MyBitVector InheritsFrom, int Count)
1774 shared = InheritsFrom == null ? null : InheritsFrom.Shared;
1780 if (shared == null) {
1789 // Get/set bit `index' in the bit vector.
1791 public bool this [int index] {
1794 throw new ArgumentOutOfRangeException ();
1797 return vector [index];
1800 if (index < shared.Count)
1801 return shared [index];
1806 // Only copy the vector if we're actually modifying it.
1807 if (this [index] != value) {
1809 initialize_vector ();
1810 vector [index] = value;
1816 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1817 // different size than the current one.
1819 private MyBitVector Or (MyBitVector new_vector)
1821 int min = new_vector.Count;
1825 for (int i = 0; i < min; i++)
1826 this [i] |= new_vector [i];
1832 // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
1833 // a different size than the current one.
1835 private MyBitVector And (MyBitVector new_vector)
1837 int min = new_vector.Count;
1841 for (int i = 0; i < min; i++)
1842 this [i] &= new_vector [i];
1844 for (int i = min; i < Count; i++)
1850 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1852 if (a == null && b == null)
1858 if (a.Count > b.Count)
1859 return a.Clone ().And (b);
1861 return b.Clone ().And (a);
1864 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1866 if (a == null && b == null)
1869 return new MyBitVector (null, b.Count);
1871 return new MyBitVector (null, a.Count);
1872 if (a.Count > b.Count)
1873 return a.Clone ().Or (b);
1875 return b.Clone ().Or (a);
1878 public MyBitVector Clone ()
1880 return Count == 0 ? Empty : new MyBitVector (this, Count);
1883 public void SetAll (bool value)
1885 // Don't clobber Empty
1888 shared = value ? null : Empty.Shared;
1892 void initialize_vector ()
1894 if (shared == null) {
1895 vector = new BitArray (Count, true);
1899 vector = new BitArray (Count, false);
1901 int min = shared.Count;
1905 for (int i = 0; i < min; i++)
1906 vector [i] = shared [i];
1911 StringBuilder Dump (StringBuilder sb)
1913 BitArray dump = vector == null ? shared : vector;
1915 return sb.Append ("/");
1918 for (int i = 0; i < dump.Count; i++)
1919 sb.Append (dump [i] ? "1" : "0");
1923 public override string ToString ()
1925 return Dump (new StringBuilder ("{")).Append ("}").ToString ();