2 // flowanalyis.cs: The control flow analysis code
5 // Martin Baulig (martin@ximian.com)
6 // Raja R Harinath (rharinath@novell.com)
7 // Marek Safar (marek.safar@gmail.com)
9 // Copyright 2001, 2002, 2003 Ximian, Inc.
10 // Copyright 2003-2008 Novell, Inc.
11 // Copyright 2011 Xamarin, Inc.
16 using System.Collections.Generic;
21 // A new instance of this class is created every time a new block is resolved
22 // and if there's branching in the block's control flow.
24 public abstract class FlowBranching
27 // The type of a FlowBranching.
29 public enum BranchingType : byte {
30 // Normal (conditional or toplevel) block.
39 // The statement embedded inside a loop
42 // part of a block headed by a jump target
48 // TryFinally, Using, Lock, CollectionForeach
54 // The toplevel block of a function
62 // The type of one sibling of a branching.
64 public enum SiblingType : byte {
73 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
76 case BranchingType.Exception:
77 case BranchingType.Labeled:
78 case BranchingType.Toplevel:
79 case BranchingType.TryCatch:
80 throw new InvalidOperationException ();
82 case BranchingType.Switch:
83 return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
85 case BranchingType.Block:
86 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
88 case BranchingType.Loop:
89 return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
91 case BranchingType.Embedded:
92 return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
95 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
100 // The type of this flow branching.
102 public readonly BranchingType Type;
105 // The block this branching is contained in. This may be null if it's not
106 // a top-level block and it doesn't declare any local variables.
108 public readonly Block Block;
111 // The parent of this branching or null if this is the top-block.
113 public readonly FlowBranching Parent;
116 // Start-Location of this flow branching.
118 public readonly Location Location;
120 static int next_id = 0;
124 // The vector contains a BitArray with information about which local variables
125 // and parameters are already initialized at the current code position.
127 public class UsageVector {
129 // The type of this branching.
131 public readonly SiblingType Type;
134 // Start location of this branching.
136 public Location Location;
139 // This is only valid for SwitchSection, Try, Catch and Finally.
141 public readonly Block Block;
144 // The number of locals in this block.
146 public readonly int CountLocals;
149 // If not null, then we inherit our state from this vector and do a
150 // copy-on-write. If null, then we're the first sibling in a top-level
151 // block and inherit from the empty vector.
153 public readonly UsageVector InheritsFrom;
156 // This is used to construct a list of UsageVector's.
158 public UsageVector Next;
166 static int next_id = 0;
170 // Normally, you should not use any of these constructors.
172 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc, int num_locals)
177 this.InheritsFrom = parent;
178 this.CountLocals = num_locals;
180 locals = num_locals == 0
182 : new MyBitVector (parent == null ? MyBitVector.Empty : parent.locals, num_locals);
185 is_unreachable = parent.is_unreachable;
191 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
192 : this (type, parent, block, loc, parent.CountLocals)
195 private UsageVector (MyBitVector locals, bool is_unreachable, Block block, Location loc)
197 this.Type = SiblingType.Block;
201 this.is_unreachable = is_unreachable;
203 this.locals = locals;
210 // This does a deep copy of the usage vector.
212 public UsageVector Clone ()
214 UsageVector retval = new UsageVector (Type, null, Block, Location, CountLocals);
216 retval.locals = locals.Clone ();
217 retval.is_unreachable = is_unreachable;
222 public bool IsAssigned (VariableInfo var, bool ignoreReachability)
224 if (!ignoreReachability && !var.IsParameter && IsUnreachable)
227 return var.IsAssigned (locals);
230 public void SetAssigned (VariableInfo var)
232 if (!var.IsParameter && IsUnreachable)
235 var.SetAssigned (locals);
238 public bool IsFieldAssigned (VariableInfo var, string name)
240 if (/*!var.IsParameter &&*/ IsUnreachable)
243 return var.IsStructFieldAssigned (locals, name);
246 public void SetFieldAssigned (VariableInfo var, string name)
248 if (/*!var.IsParameter &&*/ IsUnreachable)
251 var.SetStructFieldAssigned (locals, name);
254 public bool IsUnreachable {
256 return is_unreachable;
259 is_unreachable = value;
263 public void ResetBarrier ()
265 is_unreachable = false;
270 is_unreachable = true;
273 public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
275 if (sibling_list.Next == null)
278 MyBitVector locals = null;
279 bool is_unreachable = sibling_list.is_unreachable;
281 if (!sibling_list.IsUnreachable)
282 locals &= sibling_list.locals;
284 for (UsageVector child = sibling_list.Next; child != null; child = child.Next) {
285 is_unreachable &= child.is_unreachable;
287 if (!child.IsUnreachable)
288 locals &= child.locals;
291 return new UsageVector (locals, is_unreachable, null, loc);
295 // Merges a child branching.
297 public UsageVector MergeChild (UsageVector child, bool overwrite)
299 Report.Debug (2, " MERGING CHILD EFFECTS", this, child, Type);
301 bool new_isunr = child.is_unreachable;
304 // We've now either reached the point after the branching or we will
305 // never get there since we always return or always throw an exception.
307 // If we can reach the point after the branching, mark all locals and
308 // parameters as initialized which have been initialized in all branches
309 // we need to look at (see above).
312 if ((Type == SiblingType.SwitchSection) && !new_isunr) {
313 Report.Error (163, Location,
314 "Control cannot fall through from one " +
315 "case label to another");
319 locals |= child.locals;
321 // throw away un-necessary information about variables in child blocks
322 if (locals.Count != CountLocals)
323 locals = new MyBitVector (locals, CountLocals);
326 is_unreachable = new_isunr;
328 is_unreachable |= new_isunr;
333 public void MergeOrigins (UsageVector o_vectors)
335 Report.Debug (1, " MERGING BREAK ORIGINS", this);
337 if (o_vectors == null)
340 if (IsUnreachable && locals != null)
341 locals.SetAll (true);
343 for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
344 Report.Debug (1, " MERGING BREAK ORIGIN", vector);
345 if (vector.IsUnreachable)
347 locals &= vector.locals;
348 is_unreachable &= vector.is_unreachable;
351 Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
358 public override string ToString ()
360 return String.Format ("Vector ({0},{1},{2}-{3})", Type, id, is_unreachable, locals);
365 // Creates a new flow branching which is contained in `parent'.
366 // You should only pass non-null for the `block' argument if this block
367 // introduces any new variables - in this case, we need to create a new
368 // usage vector with a different size than our parent's one.
370 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
371 Block block, Location loc)
381 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
382 vector = new UsageVector (stype, parent_vector, Block, loc, Block.AssignableSlots);
384 vector = new UsageVector (stype, Parent.CurrentUsageVector, null, loc);
390 public abstract UsageVector CurrentUsageVector {
395 // Creates a sibling of the current usage vector.
397 public virtual void CreateSibling (Block block, SiblingType type)
399 UsageVector vector = new UsageVector (
400 type, Parent.CurrentUsageVector, block, Location);
403 Report.Debug (1, " CREATED SIBLING", CurrentUsageVector);
406 public void CreateSibling ()
408 CreateSibling (null, SiblingType.Conditional);
411 protected abstract void AddSibling (UsageVector uv);
413 protected abstract UsageVector Merge ();
415 public UsageVector MergeChild (FlowBranching child)
417 return CurrentUsageVector.MergeChild (child.Merge (), true);
420 public virtual bool CheckRethrow (Location loc)
422 return Parent.CheckRethrow (loc);
425 public virtual bool AddResumePoint (ResumableStatement stmt, out int pc)
427 return Parent.AddResumePoint (stmt, out pc);
430 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
431 public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
433 return Parent.AddBreakOrigin (vector, loc);
436 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
437 public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
439 return Parent.AddContinueOrigin (vector, loc);
442 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
443 public virtual bool AddReturnOrigin (UsageVector vector, ExitStatement stmt)
445 return Parent.AddReturnOrigin (vector, stmt);
448 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
449 public virtual bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
451 return Parent.AddGotoOrigin (vector, goto_stmt);
454 public bool IsAssigned (VariableInfo vi)
456 return CurrentUsageVector.IsAssigned (vi, false);
459 public bool IsStructFieldAssigned (VariableInfo vi, string field_name)
461 return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
464 protected static Report Report {
465 get { return RootContext.ToplevelTypes.Compiler.Report; }
468 public void SetAssigned (VariableInfo vi)
470 CurrentUsageVector.SetAssigned (vi);
473 public void SetFieldAssigned (VariableInfo vi, string name)
475 CurrentUsageVector.SetFieldAssigned (vi, name);
479 public override string ToString ()
481 StringBuilder sb = new StringBuilder ();
482 sb.Append (GetType ());
490 sb.Append (Block.ID);
492 sb.Append (Block.StartLocation);
495 // sb.Append (Siblings.Length);
496 // sb.Append (" - ");
497 sb.Append (CurrentUsageVector);
499 return sb.ToString ();
504 get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
508 public class FlowBranchingBlock : FlowBranching
510 UsageVector sibling_list = null;
512 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
513 SiblingType stype, Block block, Location loc)
514 : base (parent, type, stype, block, loc)
517 public override UsageVector CurrentUsageVector {
518 get { return sibling_list; }
521 protected override void AddSibling (UsageVector sibling)
523 if (sibling_list != null && sibling_list.Type == SiblingType.Block)
524 throw new InternalErrorException ("Blocks don't have sibling flow paths");
525 sibling.Next = sibling_list;
526 sibling_list = sibling;
529 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
531 LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
533 return Parent.AddGotoOrigin (vector, goto_stmt);
536 goto_stmt.SetResolvedTarget (stmt);
537 stmt.AddUsageVector (vector);
541 public static void Error_UnknownLabel (Location loc, string label, Report Report)
543 Report.Error(159, loc, "The label `{0}:' could not be found within the scope of the goto statement",
547 protected override UsageVector Merge ()
549 Report.Debug (2, " MERGING SIBLINGS", Name);
550 UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
551 Report.Debug (2, " MERGING SIBLINGS DONE", Name, vector);
556 public class FlowBranchingBreakable : FlowBranchingBlock
558 UsageVector break_origins;
560 public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
561 : base (parent, type, stype, block, loc)
564 public override bool AddBreakOrigin (UsageVector vector, Location loc)
566 vector = vector.Clone ();
567 vector.Next = break_origins;
568 break_origins = vector;
572 protected override UsageVector Merge ()
574 UsageVector vector = base.Merge ();
575 vector.MergeOrigins (break_origins);
580 public class FlowBranchingContinuable : FlowBranchingBlock
582 UsageVector continue_origins;
584 public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
585 : base (parent, type, stype, block, loc)
588 public override bool AddContinueOrigin (UsageVector vector, Location loc)
590 vector = vector.Clone ();
591 vector.Next = continue_origins;
592 continue_origins = vector;
596 protected override UsageVector Merge ()
598 UsageVector vector = base.Merge ();
599 vector.MergeOrigins (continue_origins);
604 public class FlowBranchingLabeled : FlowBranchingBlock
606 LabeledStatement stmt;
609 public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
610 : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
613 CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
614 actual = CurrentUsageVector.Clone ();
616 // stand-in for backward jumps
617 CurrentUsageVector.ResetBarrier ();
620 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
622 if (goto_stmt.Target != stmt.Name)
623 return Parent.AddGotoOrigin (vector, goto_stmt);
626 goto_stmt.SetResolvedTarget (stmt);
627 actual.MergeOrigins (vector.Clone ());
632 protected override UsageVector Merge ()
634 UsageVector vector = base.Merge ();
636 if (actual.IsUnreachable)
637 Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
639 actual.MergeChild (vector, false);
644 public class FlowBranchingIterator : FlowBranchingBlock
646 readonly Iterator iterator;
648 public FlowBranchingIterator (FlowBranching parent, Iterator iterator)
649 : base (parent, BranchingType.Iterator, SiblingType.Block, iterator.Block, iterator.Location)
651 this.iterator = iterator;
654 public override bool AddResumePoint (ResumableStatement stmt, out int pc)
656 pc = iterator.AddResumePoint (stmt);
661 public class FlowBranchingToplevel : FlowBranchingBlock
663 UsageVector return_origins;
665 public FlowBranchingToplevel (FlowBranching parent, ParametersBlock stmt)
666 : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
670 public override bool CheckRethrow (Location loc)
672 Report.Error (156, loc, "A throw statement with no arguments is not allowed outside of a catch clause");
676 public override bool AddResumePoint (ResumableStatement stmt, out int pc)
678 throw new InternalErrorException ("A yield in a non-iterator block");
681 public override bool AddBreakOrigin (UsageVector vector, Location loc)
683 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
687 public override bool AddContinueOrigin (UsageVector vector, Location loc)
689 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
693 public override bool AddReturnOrigin (UsageVector vector, ExitStatement stmt)
695 vector = vector.Clone ();
696 vector.Location = stmt.loc;
697 vector.Next = return_origins;
698 return_origins = vector;
702 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
704 string name = goto_stmt.Target;
705 LabeledStatement s = Block.LookupLabel (name);
707 throw new InternalErrorException ("Shouldn't get here");
709 if (Parent == null) {
710 Error_UnknownLabel (goto_stmt.loc, name, Report);
714 int errors = Report.Errors;
715 Parent.AddGotoOrigin (vector, goto_stmt);
716 if (errors == Report.Errors)
717 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
721 protected override UsageVector Merge ()
723 for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
724 Block.ParametersBlock.CheckOutParameters (origin);
726 UsageVector vector = base.Merge ();
727 Block.ParametersBlock.CheckOutParameters (vector);
728 // Note: we _do_not_ merge in the return origins
734 return Merge ().IsUnreachable;
738 public class FlowBranchingTryCatch : FlowBranchingBlock
740 readonly TryCatch tc;
742 public FlowBranchingTryCatch (FlowBranching parent, TryCatch stmt)
743 : base (parent, BranchingType.Block, SiblingType.Try, null, stmt.loc)
748 public override bool CheckRethrow (Location loc)
750 return CurrentUsageVector.Next != null || Parent.CheckRethrow (loc);
753 public override bool AddResumePoint (ResumableStatement stmt, out int pc)
755 int errors = Report.Errors;
756 Parent.AddResumePoint (tc.IsTryCatchFinally ? stmt : tc, out pc);
757 if (errors == Report.Errors) {
758 if (stmt is AwaitStatement) {
759 if (CurrentUsageVector.Next != null) {
760 Report.Error (1985, stmt.loc, "The `await' operator cannot be used in the body of a catch clause");
762 this.tc.AddResumePoint (stmt, pc);
765 if (CurrentUsageVector.Next == null)
766 Report.Error (1626, stmt.loc, "Cannot yield a value in the body of a try block with a catch clause");
768 Report.Error (1631, stmt.loc, "Cannot yield a value in the body of a catch clause");
775 public override bool AddBreakOrigin (UsageVector vector, Location loc)
777 Parent.AddBreakOrigin (vector, loc);
778 tc.SomeCodeFollows ();
782 public override bool AddContinueOrigin (UsageVector vector, Location loc)
784 Parent.AddContinueOrigin (vector, loc);
785 tc.SomeCodeFollows ();
789 public override bool AddReturnOrigin (UsageVector vector, ExitStatement exit_stmt)
791 Parent.AddReturnOrigin (vector, exit_stmt);
792 tc.SomeCodeFollows ();
796 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
798 Parent.AddGotoOrigin (vector, goto_stmt);
803 public class FlowBranchingAsync : FlowBranchingBlock
805 readonly AsyncInitializer async_init;
807 public FlowBranchingAsync (FlowBranching parent, AsyncInitializer async_init)
808 : base (parent, BranchingType.Block, SiblingType.Try, null, async_init.Location)
810 this.async_init = async_init;
813 public override bool CheckRethrow (Location loc)
815 return CurrentUsageVector.Next != null || Parent.CheckRethrow (loc);
818 public override bool AddResumePoint (ResumableStatement stmt, out int pc)
820 pc = async_init.AddResumePoint (stmt);
824 public override bool AddBreakOrigin (UsageVector vector, Location loc)
826 Parent.AddBreakOrigin (vector, loc);
830 public override bool AddContinueOrigin (UsageVector vector, Location loc)
832 Parent.AddContinueOrigin (vector, loc);
836 public override bool AddReturnOrigin (UsageVector vector, ExitStatement exit_stmt)
838 Parent.AddReturnOrigin (vector, exit_stmt);
842 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
844 Parent.AddGotoOrigin (vector, goto_stmt);
849 public class FlowBranchingTryFinally : FlowBranching
851 ExceptionStatement stmt;
852 UsageVector current_vector;
853 UsageVector try_vector;
854 UsageVector finally_vector;
856 abstract class SavedOrigin {
857 public readonly SavedOrigin Next;
858 public readonly UsageVector Vector;
860 protected SavedOrigin (SavedOrigin next, UsageVector vector)
863 Vector = vector.Clone ();
866 protected abstract void DoPropagateFinally (FlowBranching parent);
867 public void PropagateFinally (UsageVector finally_vector, FlowBranching parent)
869 if (finally_vector != null)
870 Vector.MergeChild (finally_vector, false);
871 DoPropagateFinally (parent);
875 class BreakOrigin : SavedOrigin {
877 public BreakOrigin (SavedOrigin next, UsageVector vector, Location loc)
878 : base (next, vector)
883 protected override void DoPropagateFinally (FlowBranching parent)
885 parent.AddBreakOrigin (Vector, Loc);
889 class ContinueOrigin : SavedOrigin {
891 public ContinueOrigin (SavedOrigin next, UsageVector vector, Location loc)
892 : base (next, vector)
897 protected override void DoPropagateFinally (FlowBranching parent)
899 parent.AddContinueOrigin (Vector, Loc);
903 class ReturnOrigin : SavedOrigin {
904 public ExitStatement Stmt;
906 public ReturnOrigin (SavedOrigin next, UsageVector vector, ExitStatement stmt)
907 : base (next, vector)
912 protected override void DoPropagateFinally (FlowBranching parent)
914 parent.AddReturnOrigin (Vector, Stmt);
918 class GotoOrigin : SavedOrigin {
921 public GotoOrigin (SavedOrigin next, UsageVector vector, Goto stmt)
922 : base (next, vector)
927 protected override void DoPropagateFinally (FlowBranching parent)
929 parent.AddGotoOrigin (Vector, Stmt);
933 SavedOrigin saved_origins;
935 public FlowBranchingTryFinally (FlowBranching parent,
936 ExceptionStatement stmt)
937 : base (parent, BranchingType.Exception, SiblingType.Try,
943 protected override void AddSibling (UsageVector sibling)
945 switch (sibling.Type) {
946 case SiblingType.Try:
947 try_vector = sibling;
949 case SiblingType.Finally:
950 finally_vector = sibling;
953 throw new InvalidOperationException ();
955 current_vector = sibling;
958 public override UsageVector CurrentUsageVector {
959 get { return current_vector; }
962 public override bool CheckRethrow (Location loc)
964 if (!Parent.CheckRethrow (loc))
966 if (finally_vector == null)
968 Report.Error (724, loc, "A throw statement with no arguments is not allowed inside of a finally clause nested inside of the innermost catch clause");
972 public override bool AddResumePoint (ResumableStatement stmt, out int pc)
974 int errors = Report.Errors;
975 Parent.AddResumePoint (this.stmt, out pc);
976 if (errors == Report.Errors) {
977 if (finally_vector == null)
978 this.stmt.AddResumePoint (stmt, pc);
980 if (stmt is AwaitStatement) {
981 Report.Error (1984, stmt.loc, "The `await' operator cannot be used in the body of a finally clause");
983 Report.Error (1625, stmt.loc, "Cannot yield in the body of a finally clause");
990 public override bool AddBreakOrigin (UsageVector vector, Location loc)
992 if (finally_vector != null) {
993 int errors = Report.Errors;
994 Parent.AddBreakOrigin (vector, loc);
995 if (errors == Report.Errors)
996 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
998 saved_origins = new BreakOrigin (saved_origins, vector, loc);
1001 // either the loop test or a back jump will follow code
1002 stmt.SomeCodeFollows ();
1006 public override bool AddContinueOrigin (UsageVector vector, Location loc)
1008 if (finally_vector != null) {
1009 int errors = Report.Errors;
1010 Parent.AddContinueOrigin (vector, loc);
1011 if (errors == Report.Errors)
1012 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
1014 saved_origins = new ContinueOrigin (saved_origins, vector, loc);
1017 // either the loop test or a back jump will follow code
1018 stmt.SomeCodeFollows ();
1022 public override bool AddReturnOrigin (UsageVector vector, ExitStatement exit_stmt)
1024 if (finally_vector != null) {
1025 int errors = Report.Errors;
1026 Parent.AddReturnOrigin (vector, exit_stmt);
1027 if (errors == Report.Errors)
1028 exit_stmt.Error_FinallyClause (Report);
1030 saved_origins = new ReturnOrigin (saved_origins, vector, exit_stmt);
1033 // sets ec.NeedReturnLabel()
1034 stmt.SomeCodeFollows ();
1038 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
1040 LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
1042 throw new InternalErrorException ("Shouldn't get here");
1044 if (finally_vector != null) {
1045 int errors = Report.Errors;
1046 Parent.AddGotoOrigin (vector, goto_stmt);
1047 if (errors == Report.Errors)
1048 Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
1050 saved_origins = new GotoOrigin (saved_origins, vector, goto_stmt);
1055 protected override UsageVector Merge ()
1057 UsageVector vector = try_vector.Clone ();
1059 if (finally_vector != null)
1060 vector.MergeChild (finally_vector, false);
1062 for (SavedOrigin origin = saved_origins; origin != null; origin = origin.Next)
1063 origin.PropagateFinally (finally_vector, Parent);
1070 // This is used by the flow analysis code to keep track of the type of local variables.
1072 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1073 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1074 // you can only assign the whole variable as such.
1076 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1077 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1078 // one bit for each of its fields.
1080 // This class computes this `layout' for each type.
1082 public class TypeInfo
1085 // Total number of bits a variable of this type consumes in the flow vector.
1087 public readonly int TotalLength;
1090 // Number of bits the simple fields of a variable of this type consume
1091 // in the flow vector.
1093 public readonly int Length;
1096 // This is only used by sub-structs.
1098 public readonly int Offset;
1101 // If this is a struct.
1103 public readonly bool IsStruct;
1106 // If this is a struct, all fields which are structs theirselves.
1108 public TypeInfo[] SubStructInfo;
1110 readonly StructInfo struct_info;
1111 private static Dictionary<TypeSpec, TypeInfo> type_hash;
1113 static readonly TypeInfo simple_type = new TypeInfo (1);
1120 public static void Reset ()
1122 type_hash = new Dictionary<TypeSpec, TypeInfo> ();
1123 StructInfo.field_type_hash = new Dictionary<TypeSpec, StructInfo> ();
1126 TypeInfo (int totalLength)
1128 this.TotalLength = totalLength;
1131 TypeInfo (StructInfo struct_info, int offset)
1133 this.struct_info = struct_info;
1134 this.Offset = offset;
1135 this.Length = struct_info.Length;
1136 this.TotalLength = struct_info.TotalLength;
1137 this.SubStructInfo = struct_info.StructFields;
1138 this.IsStruct = true;
1141 public int GetFieldIndex (string name)
1143 if (struct_info == null)
1146 return struct_info [name];
1149 public TypeInfo GetStructField (string name)
1151 if (struct_info == null)
1154 return struct_info.GetStructField (name);
1157 public static TypeInfo GetTypeInfo (TypeSpec type)
1163 if (type_hash.TryGetValue (type, out info))
1166 var struct_info = StructInfo.GetStructInfo (type);
1167 if (struct_info != null) {
1168 info = new TypeInfo (struct_info, 0);
1173 type_hash.Add (type, info);
1178 // A struct's constructor must always assign all fields.
1179 // This method checks whether it actually does so.
1181 public bool IsFullyInitialized (BlockContext ec, VariableInfo vi, Location loc)
1183 if (struct_info == null)
1187 FlowBranching branching = ec.CurrentBranching;
1188 for (int i = 0; i < struct_info.Count; i++) {
1189 var field = struct_info.Fields [i];
1191 if (!branching.IsStructFieldAssigned (vi, field.Name)) {
1192 if (field.MemberDefinition is Property.BackingField) {
1193 ec.Report.Error (843, loc,
1194 "An automatically implemented property `{0}' must be fully assigned before control leaves the constructor. Consider calling the default struct contructor from a constructor initializer",
1195 field.GetSignatureForError ());
1197 ec.Report.Error (171, loc,
1198 "Field `{0}' must be fully assigned before control leaves the constructor",
1199 field.GetSignatureForError ());
1208 public override string ToString ()
1210 return String.Format ("TypeInfo ({0}:{1}:{2})",
1211 Offset, Length, TotalLength);
1216 public readonly TypeSpec Type;
1217 readonly List<FieldSpec> fields;
1218 public readonly TypeInfo[] StructFields;
1219 public readonly int Length;
1220 public readonly int TotalLength;
1222 public static Dictionary<TypeSpec, StructInfo> field_type_hash;
1223 private Dictionary<string, TypeInfo> struct_field_hash;
1224 private Dictionary<string, int> field_hash;
1226 protected bool InTransit;
1228 // Private constructor. To save memory usage, we only need to create one instance
1229 // of this class per struct type.
1230 private StructInfo (TypeSpec type)
1234 field_type_hash.Add (type, this);
1236 fields = MemberCache.GetAllFieldsForDefiniteAssignment (type);
1238 struct_field_hash = new Dictionary<string, TypeInfo> ();
1239 field_hash = new Dictionary<string, int> (fields.Count);
1241 StructFields = new TypeInfo[fields.Count];
1242 StructInfo[] sinfo = new StructInfo[fields.Count];
1246 for (int i = 0; i < fields.Count; i++) {
1247 var field = fields [i];
1249 if (field.MemberType.IsStruct)
1250 sinfo [i] = GetStructInfo (field.MemberType);
1252 if (sinfo [i] == null)
1253 field_hash.Add (field.Name, ++Length);
1254 else if (sinfo [i].InTransit) {
1262 TotalLength = Length + 1;
1263 for (int i = 0; i < fields.Count; i++) {
1264 var field = fields [i];
1266 if (sinfo [i] == null)
1269 field_hash.Add (field.Name, TotalLength);
1271 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1272 struct_field_hash.Add (field.Name, StructFields [i]);
1273 TotalLength += sinfo [i].TotalLength;
1279 return fields.Count;
1283 public List<FieldSpec> Fields {
1289 public int this [string name] {
1292 if (!field_hash.TryGetValue (name, out val))
1299 public TypeInfo GetStructField (string name)
1302 if (struct_field_hash.TryGetValue (name, out ti))
1308 public static StructInfo GetStructInfo (TypeSpec type)
1310 if (type.BuiltinType > 0)
1314 if (field_type_hash.TryGetValue (type, out info))
1317 return new StructInfo (type);
1323 // This is used by the flow analysis code to store information about a single local variable
1324 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1325 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1326 // it has been assigned or not, but for structs, we need this information for each of its fields.
1328 public class VariableInfo {
1329 readonly string Name;
1330 public readonly TypeInfo TypeInfo;
1333 // The bit offset of this variable in the flow vector.
1335 readonly int Offset;
1338 // The number of bits this variable needs in the flow vector.
1339 // The first bit always specifies whether the variable as such has been assigned while
1340 // the remaining bits contain this information for each of a struct's fields.
1342 public readonly int Length;
1345 // If this is a parameter of local variable.
1347 public readonly bool IsParameter;
1349 VariableInfo[] sub_info;
1351 protected VariableInfo (string name, TypeSpec type, int offset)
1354 this.Offset = offset;
1355 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1357 Length = TypeInfo.TotalLength;
1362 protected VariableInfo (VariableInfo parent, TypeInfo type)
1364 this.Name = parent.Name;
1365 this.TypeInfo = type;
1366 this.Offset = parent.Offset + type.Offset;
1367 this.Length = type.TotalLength;
1369 this.IsParameter = parent.IsParameter;
1374 protected void Initialize ()
1376 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1377 if (sub_fields != null) {
1378 sub_info = new VariableInfo [sub_fields.Length];
1379 for (int i = 0; i < sub_fields.Length; i++) {
1380 if (sub_fields [i] != null)
1381 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1384 sub_info = new VariableInfo [0];
1387 public VariableInfo (LocalVariable local_info, int offset)
1388 : this (local_info.Name, local_info.Type, offset)
1390 this.IsParameter = false;
1393 public VariableInfo (ParametersCompiled ip, int i, int offset)
1394 : this (ip.FixedParameters [i].Name, ip.Types [i], offset)
1396 this.IsParameter = true;
1399 public bool IsAssigned (ResolveContext ec)
1401 return !ec.DoFlowAnalysis || ec.CurrentBranching.IsAssigned (this);
1404 public bool IsAssigned (MyBitVector vector)
1409 if (vector [Offset])
1412 // Unless this is a struct
1413 if (!TypeInfo.IsStruct)
1417 // Following case cannot be handled fully by SetStructFieldAssigned
1418 // because we may encounter following case
1421 // struct B { int value; }
1423 // setting a.b.value is propagated only to B's vector and not upwards to possible parents
1426 // Each field must be assigned
1428 for (int i = Offset + 1; i <= TypeInfo.Length + Offset; i++) {
1433 // Ok, now check all fields which are structs.
1434 for (int i = 0; i < sub_info.Length; i++) {
1435 VariableInfo sinfo = sub_info[i];
1439 if (!sinfo.IsAssigned (vector))
1443 vector [Offset] = true;
1447 public bool IsEverAssigned { get; set; }
1449 public bool IsStructFieldAssigned (ResolveContext ec, string name)
1451 return !ec.DoFlowAnalysis || ec.CurrentBranching.IsStructFieldAssigned (this, name);
1454 public bool IsStructFieldAssigned (MyBitVector vector, string field_name)
1456 int field_idx = TypeInfo.GetFieldIndex (field_name);
1461 return vector [Offset + field_idx];
1464 public void SetStructFieldAssigned (ResolveContext ec, string name)
1466 if (ec.DoFlowAnalysis)
1467 ec.CurrentBranching.SetFieldAssigned (this, name);
1470 public void SetAssigned (ResolveContext ec)
1472 if (ec.DoFlowAnalysis)
1473 ec.CurrentBranching.SetAssigned (this);
1476 public void SetAssigned (MyBitVector vector)
1479 vector[Offset] = true;
1481 vector.SetRange (Offset, Length);
1483 IsEverAssigned = true;
1486 public void SetStructFieldAssigned (MyBitVector vector, string field_name)
1491 int field_idx = TypeInfo.GetFieldIndex (field_name);
1496 var complex_field = TypeInfo.GetStructField (field_name);
1497 if (complex_field != null) {
1498 vector.SetRange (Offset + complex_field.Offset, complex_field.TotalLength);
1500 vector[Offset + field_idx] = true;
1503 IsEverAssigned = true;
1506 // Each field must be assigned
1508 for (int i = Offset + 1; i < TypeInfo.TotalLength + Offset; i++) {
1514 // Set master struct flag to assigned when all tested struct
1515 // fields have been assigned
1517 vector[Offset] = true;
1520 public VariableInfo GetStructFieldInfo (string fieldName)
1522 TypeInfo type = TypeInfo.GetStructField (fieldName);
1527 return new VariableInfo (this, type);
1530 public override string ToString ()
1532 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1533 Name, TypeInfo, Offset, Length, IsParameter);
1538 // This is a special bit vector which can inherit from another bit vector doing a
1539 // copy-on-write strategy. The inherited vector may have a smaller size than the
1542 public class MyBitVector {
1543 public readonly int Count;
1544 public static readonly MyBitVector Empty = new MyBitVector ();
1546 // Invariant: vector != null => vector.Count == Count
1547 // Invariant: vector == null || shared == null
1548 // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
1549 // The object in 'shared' cannot be modified, while 'vector' can be freely modified
1550 System.Collections.BitArray vector, shared;
1554 shared = new System.Collections.BitArray (0, false);
1557 public MyBitVector (MyBitVector InheritsFrom, int Count)
1559 if (InheritsFrom != null)
1560 shared = InheritsFrom.MakeShared (Count);
1565 System.Collections.BitArray MakeShared (int new_count)
1567 // Post-condition: vector == null
1569 // ensure we don't leak out dirty bits from the BitVector we inherited from
1570 if (new_count > Count &&
1571 ((shared != null && shared.Count > Count) ||
1572 (shared == null && vector == null)))
1573 initialize_vector ();
1575 if (vector != null) {
1584 // Get/set bit `index' in the bit vector.
1586 public bool this [int index] {
1589 // FIXME: Disabled due to missing anonymous method flow analysis
1590 // throw new ArgumentOutOfRangeException ();
1594 return vector [index];
1597 if (index < shared.Count)
1598 return shared [index];
1603 // Only copy the vector if we're actually modifying it.
1604 if (this [index] != value) {
1606 initialize_vector ();
1607 vector [index] = value;
1613 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1614 // different size than the current one.
1616 private MyBitVector Or (MyBitVector new_vector)
1618 if (Count == 0 || new_vector.Count == 0)
1621 var o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1624 int n = new_vector.Count;
1626 for (int i = 0; i < n; ++i)
1634 if (Count == o.Count) {
1635 if (vector == null) {
1638 initialize_vector ();
1648 for (int i = 0; i < min; i++) {
1657 // Performs an `and' operation on the bit vector. The `new_vector' may have
1658 // a different size than the current one.
1660 private MyBitVector And (MyBitVector new_vector)
1665 var o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1668 for (int i = new_vector.Count; i < Count; ++i)
1678 if (Count == o.Count) {
1679 if (vector == null) {
1680 if (shared == null) {
1681 shared = new_vector.MakeShared (Count);
1684 initialize_vector ();
1694 for (int i = 0; i < min; i++) {
1699 for (int i = min; i < Count; i++)
1705 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1713 if (a.Count > b.Count)
1714 return a.Clone ().And (b);
1716 return b.Clone ().And (a);
1719 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1724 return new MyBitVector (null, b.Count);
1726 return new MyBitVector (null, a.Count);
1727 if (a.Count > b.Count)
1728 return a.Clone ().Or (b);
1730 return b.Clone ().Or (a);
1733 public MyBitVector Clone ()
1735 return Count == 0 ? Empty : new MyBitVector (this, Count);
1738 public void SetRange (int offset, int length)
1740 if (offset > Count || offset + length > Count)
1741 throw new ArgumentOutOfRangeException ("flow-analysis");
1743 if (shared == null && vector == null)
1747 if (shared != null) {
1748 if (offset + length <= shared.Count) {
1749 for (; i < length; ++i)
1750 if (!shared [i+offset])
1755 initialize_vector ();
1757 for (; i < length; ++i)
1758 vector [i+offset] = true;
1762 public void SetAll (bool value)
1764 // Don't clobber Empty
1767 shared = value ? null : Empty.MakeShared (Count);
1771 void initialize_vector ()
1773 // Post-condition: vector != null
1774 if (shared == null) {
1775 vector = new System.Collections.BitArray (Count, true);
1779 vector = new System.Collections.BitArray (shared);
1780 if (Count != vector.Count)
1781 vector.Length = Count;
1785 StringBuilder Dump (StringBuilder sb)
1787 var dump = vector == null ? shared : vector;
1789 return sb.Append ("/");
1792 for (int i = 0; i < dump.Count; i++)
1793 sb.Append (dump [i] ? "1" : "0");
1797 public override string ToString ()
1799 return Dump (new StringBuilder ("{")).Append ("}").ToString ();