2 // flowanalyis.cs: The control flow analysis code
5 // Martin Baulig (martin@ximian.com)
6 // Raja R Harinath (rharinath@novell.com)
8 // Copyright 2001, 2002, 2003 Ximian, Inc.
9 // Copyright 2003-2008 Novell, Inc.
14 using System
.Collections
;
15 using System
.Reflection
;
16 using System
.Reflection
.Emit
;
17 using System
.Diagnostics
;
22 // A new instance of this class is created every time a new block is resolved
23 // and if there's branching in the block's control flow.
25 public abstract class FlowBranching
28 // The type of a FlowBranching.
30 public enum BranchingType
: byte {
31 // Normal (conditional or toplevel) block.
40 // The statement embedded inside a loop
43 // part of a block headed by a jump target
49 // TryFinally, Using, Lock, CollectionForeach
55 // The toplevel block of a function
63 // The type of one sibling of a branching.
65 public enum SiblingType
: byte {
74 public static FlowBranching
CreateBranching (FlowBranching parent
, BranchingType type
, Block block
, Location loc
)
77 case BranchingType
.Exception
:
78 case BranchingType
.Labeled
:
79 case BranchingType
.Toplevel
:
80 case BranchingType
.TryCatch
:
81 throw new InvalidOperationException ();
83 case BranchingType
.Switch
:
84 return new FlowBranchingBreakable (parent
, type
, SiblingType
.SwitchSection
, block
, loc
);
86 case BranchingType
.Block
:
87 return new FlowBranchingBlock (parent
, type
, SiblingType
.Block
, block
, loc
);
89 case BranchingType
.Loop
:
90 return new FlowBranchingBreakable (parent
, type
, SiblingType
.Conditional
, block
, loc
);
92 case BranchingType
.Embedded
:
93 return new FlowBranchingContinuable (parent
, type
, SiblingType
.Conditional
, block
, loc
);
96 return new FlowBranchingBlock (parent
, type
, SiblingType
.Conditional
, block
, loc
);
101 // The type of this flow branching.
103 public readonly BranchingType Type
;
106 // The block this branching is contained in. This may be null if it's not
107 // a top-level block and it doesn't declare any local variables.
109 public readonly Block Block
;
112 // The parent of this branching or null if this is the top-block.
114 public readonly FlowBranching Parent
;
117 // Start-Location of this flow branching.
119 public readonly Location Location
;
121 static int next_id
= 0;
125 // The vector contains a BitArray with information about which local variables
126 // and parameters are already initialized at the current code position.
128 public class UsageVector
{
130 // The type of this branching.
132 public readonly SiblingType Type
;
135 // Start location of this branching.
137 public Location Location
;
140 // This is only valid for SwitchSection, Try, Catch and Finally.
142 public readonly Block Block
;
145 // The number of locals in this block.
147 public readonly int CountLocals
;
150 // If not null, then we inherit our state from this vector and do a
151 // copy-on-write. If null, then we're the first sibling in a top-level
152 // block and inherit from the empty vector.
154 public readonly UsageVector InheritsFrom
;
157 // This is used to construct a list of UsageVector's.
159 public UsageVector Next
;
167 static int next_id
= 0;
171 // Normally, you should not use any of these constructors.
173 public UsageVector (SiblingType type
, UsageVector parent
, Block block
, Location loc
, int num_locals
)
178 this.InheritsFrom
= parent
;
179 this.CountLocals
= num_locals
;
181 locals
= num_locals
== 0
183 : new MyBitVector (parent
== null ? MyBitVector
.Empty
: parent
.locals
, num_locals
);
186 is_unreachable
= parent
.is_unreachable
;
192 public UsageVector (SiblingType type
, UsageVector parent
, Block block
, Location loc
)
193 : this (type
, parent
, block
, loc
, parent
.CountLocals
)
196 private UsageVector (MyBitVector locals
, bool is_unreachable
, Block block
, Location loc
)
198 this.Type
= SiblingType
.Block
;
202 this.is_unreachable
= is_unreachable
;
204 this.locals
= locals
;
211 // This does a deep copy of the usage vector.
213 public UsageVector
Clone ()
215 UsageVector retval
= new UsageVector (Type
, null, Block
, Location
, CountLocals
);
217 retval
.locals
= locals
.Clone ();
218 retval
.is_unreachable
= is_unreachable
;
223 public bool IsAssigned (VariableInfo
var, bool ignoreReachability
)
225 if (!ignoreReachability
&& !var.IsParameter
&& IsUnreachable
)
228 return var.IsAssigned (locals
);
231 public void SetAssigned (VariableInfo
var)
233 if (!var.IsParameter
&& IsUnreachable
)
236 var.SetAssigned (locals
);
239 public bool IsFieldAssigned (VariableInfo
var, string name
)
241 if (!var.IsParameter
&& IsUnreachable
)
244 return var.IsFieldAssigned (locals
, name
);
247 public void SetFieldAssigned (VariableInfo
var, string name
)
249 if (!var.IsParameter
&& IsUnreachable
)
252 var.SetFieldAssigned (locals
, name
);
255 public bool IsUnreachable
{
256 get { return is_unreachable; }
259 public void ResetBarrier ()
261 is_unreachable
= false;
266 is_unreachable
= true;
269 public static UsageVector
MergeSiblings (UsageVector sibling_list
, Location loc
)
271 if (sibling_list
.Next
== null)
274 MyBitVector locals
= null;
275 bool is_unreachable
= sibling_list
.is_unreachable
;
277 if (!sibling_list
.IsUnreachable
)
278 locals
&= sibling_list
.locals
;
280 for (UsageVector child
= sibling_list
.Next
; child
!= null; child
= child
.Next
) {
281 is_unreachable
&= child
.is_unreachable
;
283 if (!child
.IsUnreachable
)
284 locals
&= child
.locals
;
287 return new UsageVector (locals
, is_unreachable
, null, loc
);
291 // Merges a child branching.
293 public UsageVector
MergeChild (UsageVector child
, bool overwrite
)
295 Report
.Debug (2, " MERGING CHILD EFFECTS", this, child
, Type
);
297 bool new_isunr
= child
.is_unreachable
;
300 // We've now either reached the point after the branching or we will
301 // never get there since we always return or always throw an exception.
303 // If we can reach the point after the branching, mark all locals and
304 // parameters as initialized which have been initialized in all branches
305 // we need to look at (see above).
308 if ((Type
== SiblingType
.SwitchSection
) && !new_isunr
) {
309 Report
.Error (163, Location
,
310 "Control cannot fall through from one " +
311 "case label to another");
315 locals
|= child
.locals
;
317 // throw away un-necessary information about variables in child blocks
318 if (locals
.Count
!= CountLocals
)
319 locals
= new MyBitVector (locals
, CountLocals
);
322 is_unreachable
= new_isunr
;
324 is_unreachable
|= new_isunr
;
329 public void MergeOrigins (UsageVector o_vectors
)
331 Report
.Debug (1, " MERGING BREAK ORIGINS", this);
333 if (o_vectors
== null)
336 if (IsUnreachable
&& locals
!= null)
337 locals
.SetAll (true);
339 for (UsageVector vector
= o_vectors
; vector
!= null; vector
= vector
.Next
) {
340 Report
.Debug (1, " MERGING BREAK ORIGIN", vector
);
341 if (vector
.IsUnreachable
)
343 locals
&= vector
.locals
;
344 is_unreachable
&= vector
.is_unreachable
;
347 Report
.Debug (1, " MERGING BREAK ORIGINS DONE", this);
354 public override string ToString ()
356 return String
.Format ("Vector ({0},{1},{2}-{3})", Type
, id
, is_unreachable
, locals
);
361 // Creates a new flow branching which is contained in `parent'.
362 // You should only pass non-null for the `block' argument if this block
363 // introduces any new variables - in this case, we need to create a new
364 // usage vector with a different size than our parent's one.
366 protected FlowBranching (FlowBranching parent
, BranchingType type
, SiblingType stype
,
367 Block block
, Location loc
)
377 UsageVector parent_vector
= parent
!= null ? parent
.CurrentUsageVector
: null;
378 vector
= new UsageVector (stype
, parent_vector
, Block
, loc
, Block
.AssignableSlots
);
380 vector
= new UsageVector (stype
, Parent
.CurrentUsageVector
, null, loc
);
386 public abstract UsageVector CurrentUsageVector
{
391 // Creates a sibling of the current usage vector.
393 public virtual void CreateSibling (Block block
, SiblingType type
)
395 UsageVector vector
= new UsageVector (
396 type
, Parent
.CurrentUsageVector
, block
, Location
);
399 Report
.Debug (1, " CREATED SIBLING", CurrentUsageVector
);
402 public void CreateSibling ()
404 CreateSibling (null, SiblingType
.Conditional
);
407 protected abstract void AddSibling (UsageVector uv
);
409 protected abstract UsageVector
Merge ();
411 public UsageVector
MergeChild (FlowBranching child
)
413 return CurrentUsageVector
.MergeChild (child
.Merge (), true);
416 public virtual bool CheckRethrow (Location loc
)
418 return Parent
.CheckRethrow (loc
);
421 public virtual bool AddResumePoint (ResumableStatement stmt
, Location loc
, out int pc
)
423 return Parent
.AddResumePoint (stmt
, loc
, out pc
);
426 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
427 public virtual bool AddBreakOrigin (UsageVector vector
, Location loc
)
429 return Parent
.AddBreakOrigin (vector
, loc
);
432 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
433 public virtual bool AddContinueOrigin (UsageVector vector
, Location loc
)
435 return Parent
.AddContinueOrigin (vector
, loc
);
438 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
439 public virtual bool AddReturnOrigin (UsageVector vector
, ExitStatement stmt
)
441 return Parent
.AddReturnOrigin (vector
, stmt
);
444 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
445 public virtual bool AddGotoOrigin (UsageVector vector
, Goto goto_stmt
)
447 return Parent
.AddGotoOrigin (vector
, goto_stmt
);
450 public bool IsAssigned (VariableInfo vi
)
452 return CurrentUsageVector
.IsAssigned (vi
, false);
455 public bool IsFieldAssigned (VariableInfo vi
, string field_name
)
457 return CurrentUsageVector
.IsAssigned (vi
, false) || CurrentUsageVector
.IsFieldAssigned (vi
, field_name
);
460 public void SetAssigned (VariableInfo vi
)
462 CurrentUsageVector
.SetAssigned (vi
);
465 public void SetFieldAssigned (VariableInfo vi
, string name
)
467 CurrentUsageVector
.SetFieldAssigned (vi
, name
);
470 public override string ToString ()
472 StringBuilder sb
= new StringBuilder ();
473 sb
.Append (GetType ());
481 sb
.Append (Block
.ID
);
483 sb
.Append (Block
.StartLocation
);
486 // sb.Append (Siblings.Length);
487 // sb.Append (" - ");
488 sb
.Append (CurrentUsageVector
);
490 return sb
.ToString ();
494 get { return String.Format ("{0}
({1}
:{2}
:{3}
)", GetType (), id, Type, Location); }
498 public class FlowBranchingBlock : FlowBranching
500 UsageVector sibling_list = null;
502 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
503 SiblingType stype, Block block, Location loc)
504 : base (parent, type, stype, block, loc)
507 public override UsageVector CurrentUsageVector {
508 get { return sibling_list; }
511 protected override void AddSibling (UsageVector sibling)
513 if (sibling_list != null && sibling_list.Type == SiblingType.Block)
514 throw new InternalErrorException ("Blocks don
't have sibling flow paths");
515 sibling.Next = sibling_list;
516 sibling_list = sibling;
519 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
521 LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
523 return Parent.AddGotoOrigin (vector, goto_stmt);
526 goto_stmt.SetResolvedTarget (stmt);
527 stmt.AddUsageVector (vector);
531 public static void Error_UnknownLabel (Location loc, string label)
533 Report.Error(159, loc, "The label `{0}:' could not be found within the scope of the
goto statement
",
537 protected override UsageVector Merge ()
539 Report.Debug (2, " MERGING SIBLINGS
", Name);
540 UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
541 Report.Debug (2, " MERGING SIBLINGS DONE
", Name, vector);
546 public class FlowBranchingBreakable : FlowBranchingBlock
548 UsageVector break_origins;
550 public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
551 : base (parent, type, stype, block, loc)
554 public override bool AddBreakOrigin (UsageVector vector, Location loc)
556 vector = vector.Clone ();
557 vector.Next = break_origins;
558 break_origins = vector;
562 protected override UsageVector Merge ()
564 UsageVector vector = base.Merge ();
565 vector.MergeOrigins (break_origins);
570 public class FlowBranchingContinuable : FlowBranchingBlock
572 UsageVector continue_origins;
574 public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
575 : base (parent, type, stype, block, loc)
578 public override bool AddContinueOrigin (UsageVector vector, Location loc)
580 vector = vector.Clone ();
581 vector.Next = continue_origins;
582 continue_origins = vector;
586 protected override UsageVector Merge ()
588 UsageVector vector = base.Merge ();
589 vector.MergeOrigins (continue_origins);
594 public class FlowBranchingLabeled : FlowBranchingBlock
596 LabeledStatement stmt;
599 public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
600 : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
603 CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
604 actual = CurrentUsageVector.Clone ();
606 // stand-in for backward jumps
607 CurrentUsageVector.ResetBarrier ();
610 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
612 if (goto_stmt.Target != stmt.Name)
613 return Parent.AddGotoOrigin (vector, goto_stmt);
616 goto_stmt.SetResolvedTarget (stmt);
617 actual.MergeOrigins (vector.Clone ());
622 protected override UsageVector Merge ()
624 UsageVector vector = base.Merge ();
626 if (actual.IsUnreachable)
627 Report.Warning (162, 2, stmt.loc, "Unreachable code detected
");
629 actual.MergeChild (vector, false);
634 public class FlowBranchingIterator : FlowBranchingBlock
637 public FlowBranchingIterator (FlowBranching parent, Iterator iterator)
638 : base (parent, BranchingType.Iterator, SiblingType.Block, null, iterator.Location)
640 this.iterator = iterator;
643 public override bool AddResumePoint (ResumableStatement stmt, Location loc, out int pc)
645 pc = iterator.AddResumePoint (stmt);
650 public class FlowBranchingToplevel : FlowBranchingBlock
652 UsageVector return_origins;
654 public FlowBranchingToplevel (FlowBranching parent, ToplevelBlock stmt)
655 : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
659 public override bool CheckRethrow (Location loc)
661 Report.Error (156, loc, "A
throw statement with no arguments
is not allowed outside of a
catch clause
");
665 public override bool AddResumePoint (ResumableStatement stmt, Location loc, out int pc)
667 throw new InternalErrorException ("A
yield in a non
-iterator block
");
670 public override bool AddBreakOrigin (UsageVector vector, Location loc)
672 Report.Error (139, loc, "No enclosing loop
out of which to
break or
continue");
676 public override bool AddContinueOrigin (UsageVector vector, Location loc)
678 Report.Error (139, loc, "No enclosing loop
out of which to
break or
continue");
682 public override bool AddReturnOrigin (UsageVector vector, ExitStatement stmt)
684 vector = vector.Clone ();
685 vector.Location = stmt.loc;
686 vector.Next = return_origins;
687 return_origins = vector;
691 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
693 string name = goto_stmt.Target;
694 LabeledStatement s = Block.LookupLabel (name);
696 throw new InternalErrorException ("Shouldn
't get here");
698 if (Parent == null) {
699 Error_UnknownLabel (goto_stmt.loc, name);
703 int errors = Report.Errors;
704 Parent.AddGotoOrigin (vector, goto_stmt);
705 if (errors == Report.Errors)
706 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
710 protected override UsageVector Merge ()
712 for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
713 Block.Toplevel.CheckOutParameters (origin, origin.Location);
715 UsageVector vector = base.Merge ();
716 Block.Toplevel.CheckOutParameters (vector, Block.loc);
717 // Note: we _do_not_ merge in the return origins
723 return Merge ().IsUnreachable;
727 public class FlowBranchingTryCatch : FlowBranchingBlock
730 public FlowBranchingTryCatch (FlowBranching parent, TryCatch stmt)
731 : base (parent, BranchingType.Block, SiblingType.Try, null, stmt.loc)
736 public override bool CheckRethrow (Location loc)
738 return CurrentUsageVector.Next != null || Parent.CheckRethrow (loc);
741 public override bool AddResumePoint (ResumableStatement stmt, Location loc, out int pc)
743 int errors = Report.Errors;
744 Parent.AddResumePoint (stmt, loc, out pc);
745 if (errors == Report.Errors) {
746 if (CurrentUsageVector.Next == null)
747 Report.Error (1626, loc, "Cannot yield a value in the body of a try block with a catch clause");
749 Report.Error (1631, loc, "Cannot yield a value in the body of a catch clause");
754 public override bool AddBreakOrigin (UsageVector vector, Location loc)
756 Parent.AddBreakOrigin (vector, loc);
757 stmt.SomeCodeFollows ();
761 public override bool AddContinueOrigin (UsageVector vector, Location loc)
763 Parent.AddContinueOrigin (vector, loc);
764 stmt.SomeCodeFollows ();
768 public override bool AddReturnOrigin (UsageVector vector, ExitStatement exit_stmt)
770 Parent.AddReturnOrigin (vector, exit_stmt);
771 stmt.SomeCodeFollows ();
775 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
777 Parent.AddGotoOrigin (vector, goto_stmt);
782 public class FlowBranchingException : FlowBranching
784 ExceptionStatement stmt;
785 UsageVector current_vector;
786 UsageVector try_vector;
787 UsageVector finally_vector;
789 abstract class SavedOrigin {
790 public readonly SavedOrigin Next;
791 public readonly UsageVector Vector;
793 protected SavedOrigin (SavedOrigin next, UsageVector vector)
796 Vector = vector.Clone ();
799 protected abstract void DoPropagateFinally (FlowBranching parent);
800 public void PropagateFinally (UsageVector finally_vector, FlowBranching parent)
802 if (finally_vector != null)
803 Vector.MergeChild (finally_vector, false);
804 DoPropagateFinally (parent);
808 class BreakOrigin : SavedOrigin {
810 public BreakOrigin (SavedOrigin next, UsageVector vector, Location loc)
811 : base (next, vector)
816 protected override void DoPropagateFinally (FlowBranching parent)
818 parent.AddBreakOrigin (Vector, Loc);
822 class ContinueOrigin : SavedOrigin {
824 public ContinueOrigin (SavedOrigin next, UsageVector vector, Location loc)
825 : base (next, vector)
830 protected override void DoPropagateFinally (FlowBranching parent)
832 parent.AddContinueOrigin (Vector, Loc);
836 class ReturnOrigin : SavedOrigin {
837 public ExitStatement Stmt;
839 public ReturnOrigin (SavedOrigin next, UsageVector vector, ExitStatement stmt)
840 : base (next, vector)
845 protected override void DoPropagateFinally (FlowBranching parent)
847 parent.AddReturnOrigin (Vector, Stmt);
851 class GotoOrigin : SavedOrigin {
854 public GotoOrigin (SavedOrigin next, UsageVector vector, Goto stmt)
855 : base (next, vector)
860 protected override void DoPropagateFinally (FlowBranching parent)
862 parent.AddGotoOrigin (Vector, Stmt);
866 SavedOrigin saved_origins;
868 public FlowBranchingException (FlowBranching parent,
869 ExceptionStatement stmt)
870 : base (parent, BranchingType.Exception, SiblingType.Try,
876 protected override void AddSibling (UsageVector sibling)
878 switch (sibling.Type) {
879 case SiblingType.Try:
880 try_vector = sibling;
882 case SiblingType.Finally:
883 finally_vector = sibling;
886 throw new InvalidOperationException ();
888 current_vector = sibling;
891 public override UsageVector CurrentUsageVector {
892 get { return current_vector; }
895 public override bool CheckRethrow (Location loc)
897 if (!Parent.CheckRethrow (loc))
899 if (finally_vector == null)
901 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");
905 public override bool AddResumePoint (ResumableStatement stmt, Location loc, out int pc)
907 int errors = Report.Errors;
908 Parent.AddResumePoint (this.stmt, loc, out pc);
909 if (errors == Report.Errors) {
910 if (finally_vector == null)
911 this.stmt.AddResumePoint (stmt, pc);
913 Report.Error (1625, loc, "Cannot yield in the body of a finally clause");
918 public override bool AddBreakOrigin (UsageVector vector, Location loc)
920 if (finally_vector != null) {
921 int errors = Report.Errors;
922 Parent.AddBreakOrigin (vector, loc);
923 if (errors == Report.Errors)
924 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
926 saved_origins = new BreakOrigin (saved_origins, vector, loc);
929 // either the loop test or a back jump will follow code
930 stmt.SomeCodeFollows ();
934 public override bool AddContinueOrigin (UsageVector vector, Location loc)
936 if (finally_vector != null) {
937 int errors = Report.Errors;
938 Parent.AddContinueOrigin (vector, loc);
939 if (errors == Report.Errors)
940 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
942 saved_origins = new ContinueOrigin (saved_origins, vector, loc);
945 // either the loop test or a back jump will follow code
946 stmt.SomeCodeFollows ();
950 public override bool AddReturnOrigin (UsageVector vector, ExitStatement exit_stmt)
952 if (finally_vector != null) {
953 int errors = Report.Errors;
954 Parent.AddReturnOrigin (vector, exit_stmt);
955 if (errors == Report.Errors)
956 exit_stmt.Error_FinallyClause ();
958 saved_origins = new ReturnOrigin (saved_origins, vector, exit_stmt);
961 // sets ec.NeedReturnLabel()
962 stmt.SomeCodeFollows ();
966 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
968 LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
970 throw new InternalErrorException ("Shouldn't
get here
");
972 if (finally_vector != null) {
973 int errors = Report.Errors;
974 Parent.AddGotoOrigin (vector, goto_stmt);
975 if (errors == Report.Errors)
976 Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a
finally clause
");
978 saved_origins = new GotoOrigin (saved_origins, vector, goto_stmt);
983 protected override UsageVector Merge ()
985 UsageVector vector = try_vector.Clone ();
987 if (finally_vector != null)
988 vector.MergeChild (finally_vector, false);
990 for (SavedOrigin origin = saved_origins; origin != null; origin = origin.Next)
991 origin.PropagateFinally (finally_vector, Parent);
998 // This is used by the flow analysis code to keep track of the type of local variables
1001 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1002 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1003 // you can only assign the whole variable as such.
1005 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1006 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1007 // one bit for each of its fields.
1009 // This class computes this `layout' for each type.
1011 public class TypeInfo
1013 public readonly Type Type;
1016 // Total number of bits a variable of this type consumes in the flow vector.
1018 public readonly int TotalLength;
1021 // Number of bits the simple fields of a variable of this type consume
1022 // in the flow vector.
1024 public readonly int Length;
1027 // This is only used by sub-structs.
1029 public readonly int Offset;
1032 // If this is a struct.
1034 public readonly bool IsStruct;
1037 // If this is a struct, all fields which are structs theirselves.
1039 public TypeInfo[] SubStructInfo;
1041 protected readonly StructInfo struct_info;
1042 private static Hashtable type_hash = new Hashtable ();
1044 public static TypeInfo GetTypeInfo (Type type)
1046 TypeInfo info = (TypeInfo) type_hash [type];
1050 info = new TypeInfo (type);
1051 type_hash.Add (type, info);
1055 public static TypeInfo GetTypeInfo (TypeContainer tc)
1057 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1061 info = new TypeInfo (tc);
1062 type_hash.Add (tc.TypeBuilder, info);
1066 private TypeInfo (Type type)
1070 struct_info = StructInfo.GetStructInfo (type);
1071 if (struct_info != null) {
1072 Length = struct_info.Length;
1073 TotalLength = struct_info.TotalLength;
1074 SubStructInfo = struct_info.StructFields;
1083 private TypeInfo (TypeContainer tc)
1085 this.Type = tc.TypeBuilder;
1087 struct_info = StructInfo.GetStructInfo (tc);
1088 if (struct_info != null) {
1089 Length = struct_info.Length;
1090 TotalLength = struct_info.TotalLength;
1091 SubStructInfo = struct_info.StructFields;
1100 protected TypeInfo (StructInfo struct_info, int offset)
1102 this.struct_info = struct_info;
1103 this.Offset = offset;
1104 this.Length = struct_info.Length;
1105 this.TotalLength = struct_info.TotalLength;
1106 this.SubStructInfo = struct_info.StructFields;
1107 this.Type = struct_info.Type;
1108 this.IsStruct = true;
1111 public int GetFieldIndex (string name)
1113 if (struct_info == null)
1116 return struct_info [name];
1119 public TypeInfo GetSubStruct (string name)
1121 if (struct_info == null)
1124 return struct_info.GetStructField (name);
1128 // A struct's constructor must always assign all fields.
1129 // This method checks whether it actually does so.
1131 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1133 if (struct_info == null)
1137 for (int i = 0; i < struct_info.Count; i++) {
1138 FieldInfo field = struct_info.Fields [i];
1140 if (!branching.IsFieldAssigned (vi, field.Name)) {
1141 FieldBase fb = TypeManager.GetField (field);
1142 if (fb != null && (fb.ModFlags & Modifiers.BACKING_FIELD) != 0) {
1143 Report.Error (843, loc,
1144 "An automatically implemented property `{0}
' must be fully assigned before control leaves the constructor. Consider calling default contructor",
1145 fb.GetSignatureForError ());
1147 Report.Error (171, loc,
1148 "Field `{0}' must be fully assigned before control leaves the constructor
",
1149 TypeManager.GetFullNameSignature (field));
1158 public override string ToString ()
1160 return String.Format ("TypeInfo ({0}
:{1}
:{2}
:{3}
)",
1161 Type, Offset, Length, TotalLength);
1164 protected class StructInfo {
1165 public readonly Type Type;
1166 public readonly FieldInfo[] Fields;
1167 public readonly TypeInfo[] StructFields;
1168 public readonly int Count;
1169 public readonly int CountPublic;
1170 public readonly int CountNonPublic;
1171 public readonly int Length;
1172 public readonly int TotalLength;
1173 public readonly bool HasStructFields;
1175 private static Hashtable field_type_hash = new Hashtable ();
1176 private Hashtable struct_field_hash;
1177 private Hashtable field_hash;
1179 protected bool InTransit = false;
1181 // Private constructor. To save memory usage, we only need to create one instance
1182 // of this class per struct type.
1183 private StructInfo (Type type)
1187 field_type_hash.Add (type, this);
1189 if (type.Module == CodeGen.Module.Builder) {
1190 TypeContainer tc = TypeManager.LookupTypeContainer (TypeManager.DropGenericTypeArguments (type));
1192 ArrayList public_fields = new ArrayList ();
1193 ArrayList non_public_fields = new ArrayList ();
1196 // TODO: tc != null is needed because FixedBuffers are not cached
1199 ArrayList fields = tc.Fields;
1201 if (fields != null) {
1202 foreach (FieldBase field in fields) {
1203 if ((field.ModFlags & Modifiers.STATIC) != 0)
1205 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1206 public_fields.Add (field.FieldBuilder);
1208 non_public_fields.Add (field.FieldBuilder);
1212 if (tc.Events != null) {
1213 foreach (Event e in tc.Events) {
1214 if ((e.ModFlags & Modifiers.STATIC) != 0)
1217 EventField ef = e as EventField;
1221 if ((ef.ModFlags & Modifiers.PUBLIC) != 0)
1222 public_fields.Add (ef.FieldBuilder);
1224 non_public_fields.Add (ef.FieldBuilder);
1229 CountPublic = public_fields.Count;
1230 CountNonPublic = non_public_fields.Count;
1231 Count = CountPublic + CountNonPublic;
1233 Fields = new FieldInfo [Count];
1234 public_fields.CopyTo (Fields, 0);
1235 non_public_fields.CopyTo (Fields, CountPublic);
1237 } else if (type is GenericTypeParameterBuilder) {
1238 CountPublic = CountNonPublic = Count = 0;
1240 Fields = new FieldInfo [0];
1243 FieldInfo[] public_fields = type.GetFields (
1244 BindingFlags.Instance|BindingFlags.Public);
1245 FieldInfo[] non_public_fields = type.GetFields (
1246 BindingFlags.Instance|BindingFlags.NonPublic);
1248 CountPublic = public_fields.Length;
1249 CountNonPublic = non_public_fields.Length;
1250 Count = CountPublic + CountNonPublic;
1252 Fields = new FieldInfo [Count];
1253 public_fields.CopyTo (Fields, 0);
1254 non_public_fields.CopyTo (Fields, CountPublic);
1257 struct_field_hash = new Hashtable ();
1258 field_hash = new Hashtable ();
1261 StructFields = new TypeInfo [Count];
1262 StructInfo[] sinfo = new StructInfo [Count];
1266 for (int i = 0; i < Count; i++) {
1267 FieldInfo field = (FieldInfo) Fields [i];
1269 sinfo [i] = GetStructInfo (field.FieldType);
1270 if (sinfo [i] == null)
1271 field_hash.Add (field.Name, ++Length);
1272 else if (sinfo [i].InTransit) {
1273 Report.Error (523, String.Format (
1274 "Struct member `{0}
.{1}
' of type `{2}' causes
" +
1275 "a cycle
in the structure layout
",
1276 type, field.Name, sinfo [i].Type));
1284 TotalLength = Length + 1;
1285 for (int i = 0; i < Count; i++) {
1286 FieldInfo field = (FieldInfo) Fields [i];
1288 if (sinfo [i] == null)
1291 field_hash.Add (field.Name, TotalLength);
1293 HasStructFields = true;
1294 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1295 struct_field_hash.Add (field.Name, StructFields [i]);
1296 TotalLength += sinfo [i].TotalLength;
1300 public int this [string name] {
1302 if (field_hash.Contains (name))
1303 return (int) field_hash [name];
1309 public TypeInfo GetStructField (string name)
1311 return (TypeInfo) struct_field_hash [name];
1314 public static StructInfo GetStructInfo (Type type)
1316 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1317 TypeManager.IsBuiltinType (type))
1320 if (TypeManager.IsGenericParameter (type))
1323 StructInfo info = (StructInfo) field_type_hash [type];
1327 return new StructInfo (type);
1330 public static StructInfo GetStructInfo (TypeContainer tc)
1332 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1336 return new StructInfo (tc.TypeBuilder);
1342 // This is used by the flow analysis code to store information about a single local variable
1343 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1344 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1345 // it has been assigned or not, but for structs, we need this information for each of its fields.
1347 public class VariableInfo {
1348 public readonly string Name;
1349 public readonly TypeInfo TypeInfo;
1352 // The bit offset of this variable in the flow vector.
1354 public readonly int Offset;
1357 // The number of bits this variable needs in the flow vector.
1358 // The first bit always specifies whether the variable as such has been assigned while
1359 // the remaining bits contain this information for each of a struct's fields.
1361 public readonly int Length;
1364 // If this is a parameter of local variable.
1366 public readonly bool IsParameter;
1368 public readonly LocalInfo LocalInfo;
1370 readonly VariableInfo Parent;
1371 VariableInfo[] sub_info;
1373 bool is_ever_assigned;
1374 public bool IsEverAssigned {
1375 get { return is_ever_assigned; }
1378 protected VariableInfo (string name, Type type, int offset)
1381 this.Offset = offset;
1382 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1384 Length = TypeInfo.TotalLength;
1389 protected VariableInfo (VariableInfo parent, TypeInfo type)
1391 this.Name = parent.Name;
1392 this.TypeInfo = type;
1393 this.Offset = parent.Offset + type.Offset;
1394 this.Parent = parent;
1395 this.Length = type.TotalLength;
1397 this.IsParameter = parent.IsParameter;
1398 this.LocalInfo = parent.LocalInfo;
1403 protected void Initialize ()
1405 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1406 if (sub_fields != null) {
1407 sub_info = new VariableInfo [sub_fields.Length];
1408 for (int i = 0; i < sub_fields.Length; i++) {
1409 if (sub_fields [i] != null)
1410 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1413 sub_info = new VariableInfo [0];
1416 public VariableInfo (LocalInfo local_info, int offset)
1417 : this (local_info.Name, local_info.VariableType, offset)
1419 this.LocalInfo = local_info;
1420 this.IsParameter = false;
1423 public VariableInfo (Parameters ip, int i, int offset)
1424 : this (ip.FixedParameters [i].Name, ip.Types [i], offset)
1426 this.IsParameter = true;
1429 public bool IsAssigned (EmitContext ec)
1431 return !ec.DoFlowAnalysis ||
1432 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1433 ec.CurrentBranching.IsAssigned (this);
1436 public bool IsAssigned (EmitContext ec, Location loc)
1438 if (IsAssigned (ec))
1441 Report.Error (165, loc,
1442 "Use of unassigned local variable `
" + Name + "'");
1443 ec.CurrentBranching.SetAssigned (this);
1447 public bool IsAssigned (MyBitVector vector)
1452 if (vector [Offset])
1455 // FIXME: Fix SetFieldAssigned to set the whole range like SetAssigned below. Then, get rid of this stanza
1456 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent) {
1457 if (vector [parent.Offset]) {
1458 // 'parent
' is assigned, but someone forgot to note that all its components are assigned too
1459 parent.SetAssigned (vector);
1464 // Return unless this is a struct.
1465 if (!TypeInfo.IsStruct)
1468 // Ok, so each field must be assigned.
1469 for (int i = 0; i < TypeInfo.Length; i++) {
1470 if (!vector [Offset + i + 1])
1474 // Ok, now check all fields which are structs.
1475 for (int i = 0; i < sub_info.Length; i++) {
1476 VariableInfo sinfo = sub_info [i];
1480 if (!sinfo.IsAssigned (vector))
1484 vector [Offset] = true;
1485 is_ever_assigned = true;
1489 public void SetAssigned (EmitContext ec)
1491 if (ec.DoFlowAnalysis)
1492 ec.CurrentBranching.SetAssigned (this);
1495 public void SetAssigned (MyBitVector vector)
1498 vector [Offset] = true;
1500 vector.SetRange (Offset, Length);
1501 is_ever_assigned = true;
1504 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1506 if (!ec.DoFlowAnalysis ||
1507 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1508 ec.CurrentBranching.IsFieldAssigned (this, name))
1511 Report.Error (170, loc,
1512 "Use of possibly unassigned field `" + name + "'");
1513 ec.CurrentBranching.SetFieldAssigned (this, name);
1517 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1519 int field_idx = TypeInfo.GetFieldIndex (field_name);
1524 return vector [Offset + field_idx];
1527 public void SetFieldAssigned (EmitContext ec, string name)
1529 if (ec.DoFlowAnalysis)
1530 ec.CurrentBranching.SetFieldAssigned (this, name);
1533 public void SetFieldAssigned (MyBitVector vector, string field_name)
1535 int field_idx = TypeInfo.GetFieldIndex (field_name);
1540 vector [Offset + field_idx] = true;
1541 is_ever_assigned = true;
1544 public VariableInfo GetSubStruct (string name)
1546 TypeInfo type = TypeInfo.GetSubStruct (name);
1551 return new VariableInfo (this, type);
1554 public override string ToString ()
1556 return String.Format ("VariableInfo ({0}
:{1}
:{2}
:{3}
:{4}
)",
1557 Name, TypeInfo, Offset, Length, IsParameter);
1562 // This is a special bit vector which can inherit from another bit vector doing a
1563 // copy-on-write strategy. The inherited vector may have a smaller size than the
1566 public class MyBitVector {
1567 public readonly int Count;
1568 public static readonly MyBitVector Empty = new MyBitVector ();
1570 // Invariant: vector != null => vector.Count == Count
1571 // Invariant: vector == null || shared == null
1572 // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
1573 // The object in 'shared' cannot be modified, while 'vector' can be freely modified
1574 BitArray vector, shared;
1578 shared = new BitArray (0, false);
1581 public MyBitVector (MyBitVector InheritsFrom, int Count)
1583 if (InheritsFrom != null)
1584 shared = InheritsFrom.MakeShared (Count);
1589 BitArray MakeShared (int new_count)
1591 // Post-condition: vector == null
1593 // ensure we don't leak out dirty bits from the BitVector we inherited from
1594 if (new_count > Count &&
1595 ((shared != null && shared.Count > Count) ||
1596 (shared == null && vector == null)))
1597 initialize_vector ();
1599 if (vector != null) {
1608 // Get/set bit `index' in the bit vector.
1610 public bool this [int index] {
1613 throw new ArgumentOutOfRangeException ();
1616 return vector [index];
1619 if (index < shared.Count)
1620 return shared [index];
1625 // Only copy the vector if we're actually modifying it.
1626 if (this [index] != value) {
1628 initialize_vector ();
1629 vector [index] = value;
1635 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1636 // different size than the current one.
1638 private MyBitVector Or (MyBitVector new_vector)
1640 if (Count == 0 || new_vector.Count == 0)
1643 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1646 int n = new_vector.Count;
1648 for (int i = 0; i < n; ++i)
1656 if (Count == o.Count) {
1657 if (vector == null) {
1660 initialize_vector ();
1670 for (int i = 0; i < min; i++) {
1679 // Performs an `and' operation on the bit vector. The `new_vector' may have
1680 // a different size than the current one.
1682 private MyBitVector And (MyBitVector new_vector)
1687 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1690 for (int i = new_vector.Count; i < Count; ++i)
1700 if (Count == o.Count) {
1701 if (vector == null) {
1702 if (shared == null) {
1703 shared = new_vector.MakeShared (Count);
1706 initialize_vector ();
1716 for (int i = 0; i < min; i++) {
1721 for (int i = min; i < Count; i++)
1727 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1735 if (a.Count > b.Count)
1736 return a.Clone ().And (b);
1738 return b.Clone ().And (a);
1741 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1746 return new MyBitVector (null, b.Count);
1748 return new MyBitVector (null, a.Count);
1749 if (a.Count > b.Count)
1750 return a.Clone ().Or (b);
1752 return b.Clone ().Or (a);
1755 public MyBitVector Clone ()
1757 return Count == 0 ? Empty : new MyBitVector (this, Count);
1760 public void SetRange (int offset, int length)
1762 if (offset > Count || offset + length > Count)
1763 throw new ArgumentOutOfRangeException ();
1765 if (shared == null && vector == null)
1769 if (shared != null) {
1770 if (offset + length <= shared.Count) {
1771 for (; i < length; ++i)
1772 if (!shared [i+offset])
1777 initialize_vector ();
1779 for (; i < length; ++i)
1780 vector [i+offset] = true;
1784 public void SetAll (bool value)
1786 // Don't clobber Empty
1789 shared = value ? null : Empty.MakeShared (Count);
1793 void initialize_vector ()
1795 // Post-condition: vector != null
1796 if (shared == null) {
1797 vector = new BitArray (Count, true);
1801 vector = new BitArray (shared);
1802 if (Count != vector.Count)
1803 vector.Length = Count;
1807 StringBuilder Dump (StringBuilder sb)
1809 BitArray dump = vector == null ? shared : vector;
1811 return sb.Append ("/");
1814 for (int i = 0; i < dump.Count; i++)
1815 sb.Append (dump [i] ? "1" : "0");
1819 public override string ToString ()
1821 return Dump (new StringBuilder ("{")).Append ("}
").ToString ();