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;
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
54 // The toplevel block of a function
59 // The type of one sibling of a branching.
61 public enum SiblingType : byte {
70 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
73 case BranchingType.Exception:
74 case BranchingType.Labeled:
75 case BranchingType.Toplevel:
76 throw new InvalidOperationException ();
78 case BranchingType.Switch:
79 return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
81 case BranchingType.SwitchSection:
82 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
84 case BranchingType.Block:
85 return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
87 case BranchingType.Loop:
88 return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
90 case BranchingType.Embedded:
91 return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
94 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
99 // The type of this flow branching.
101 public readonly BranchingType Type;
104 // The block this branching is contained in. This may be null if it's not
105 // a top-level block and it doesn't declare any local variables.
107 public readonly Block Block;
110 // The parent of this branching or null if this is the top-block.
112 public readonly FlowBranching Parent;
115 // Start-Location of this flow branching.
117 public readonly Location Location;
119 static int next_id = 0;
123 // The vector contains a BitArray with information about which local variables
124 // and parameters are already initialized at the current code position.
126 public class UsageVector {
128 // The type of this branching.
130 public readonly SiblingType Type;
133 // Start location of this branching.
135 public Location Location;
138 // This is only valid for SwitchSection, Try, Catch and Finally.
140 public readonly Block Block;
143 // The number of locals in this block.
145 public readonly int CountLocals;
148 // If not null, then we inherit our state from this vector and do a
149 // copy-on-write. If null, then we're the first sibling in a top-level
150 // block and inherit from the empty vector.
152 public readonly UsageVector InheritsFrom;
155 // This is used to construct a list of UsageVector's.
157 public UsageVector Next;
165 static int next_id = 0;
169 // Normally, you should not use any of these constructors.
171 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc, int num_locals)
176 this.InheritsFrom = parent;
177 this.CountLocals = num_locals;
179 locals = num_locals == 0
181 : new MyBitVector (parent == null ? MyBitVector.Empty : parent.locals, num_locals);
184 is_unreachable = parent.is_unreachable;
190 public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
191 : this (type, parent, block, loc, parent.CountLocals)
194 private UsageVector (MyBitVector locals, bool is_unreachable, Block block, Location loc)
196 this.Type = SiblingType.Block;
200 this.is_unreachable = is_unreachable;
202 this.locals = locals;
209 // This does a deep copy of the usage vector.
211 public UsageVector Clone ()
213 UsageVector retval = new UsageVector (Type, null, Block, Location, CountLocals);
215 retval.locals = locals.Clone ();
216 retval.is_unreachable = is_unreachable;
221 public bool IsAssigned (VariableInfo var, bool ignoreReachability)
223 if (!ignoreReachability && !var.IsParameter && IsUnreachable)
226 return var.IsAssigned (locals);
229 public void SetAssigned (VariableInfo var)
231 if (!var.IsParameter && IsUnreachable)
234 var.SetAssigned (locals);
237 public bool IsFieldAssigned (VariableInfo var, string name)
239 if (!var.IsParameter && IsUnreachable)
242 return var.IsFieldAssigned (locals, name);
245 public void SetFieldAssigned (VariableInfo var, string name)
247 if (!var.IsParameter && IsUnreachable)
250 var.SetFieldAssigned (locals, name);
253 public bool IsUnreachable {
254 get { return is_unreachable; }
257 public void ResetBarrier ()
259 is_unreachable = false;
264 is_unreachable = true;
267 public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
269 if (sibling_list.Next == null)
272 MyBitVector locals = null;
273 bool is_unreachable = sibling_list.is_unreachable;
275 if (!sibling_list.IsUnreachable)
276 locals &= sibling_list.locals;
278 for (UsageVector child = sibling_list.Next; child != null; child = child.Next) {
279 is_unreachable &= child.is_unreachable;
281 if (!child.IsUnreachable)
282 locals &= child.locals;
285 return new UsageVector (locals, is_unreachable, null, loc);
289 // Merges a child branching.
291 public UsageVector MergeChild (UsageVector child, bool overwrite)
293 Report.Debug (2, " MERGING CHILD EFFECTS", this, child, Type);
295 bool new_isunr = child.is_unreachable;
298 // We've now either reached the point after the branching or we will
299 // never get there since we always return or always throw an exception.
301 // If we can reach the point after the branching, mark all locals and
302 // parameters as initialized which have been initialized in all branches
303 // we need to look at (see above).
306 if ((Type == SiblingType.SwitchSection) && !new_isunr) {
307 Report.Error (163, Location,
308 "Control cannot fall through from one " +
309 "case label to another");
313 locals |= child.locals;
316 is_unreachable = new_isunr;
318 is_unreachable |= new_isunr;
323 public void MergeOrigins (UsageVector o_vectors)
325 Report.Debug (1, " MERGING BREAK ORIGINS", this);
327 if (o_vectors == null)
330 if (IsUnreachable && locals != null)
331 locals.SetAll (true);
333 for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
334 Report.Debug (1, " MERGING BREAK ORIGIN", vector);
335 if (vector.IsUnreachable)
337 locals &= vector.locals;
338 is_unreachable &= vector.is_unreachable;
341 Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
348 public override string ToString ()
350 return String.Format ("Vector ({0},{1},{2}-{3})", Type, id, is_unreachable, locals);
355 // Creates a new flow branching which is contained in `parent'.
356 // You should only pass non-null for the `block' argument if this block
357 // introduces any new variables - in this case, we need to create a new
358 // usage vector with a different size than our parent's one.
360 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
361 Block block, Location loc)
371 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
372 vector = new UsageVector (stype, parent_vector, Block, loc, Block.AssignableSlots);
374 vector = new UsageVector (stype, Parent.CurrentUsageVector, null, loc);
380 public abstract UsageVector CurrentUsageVector {
385 // Creates a sibling of the current usage vector.
387 public virtual void CreateSibling (Block block, SiblingType type)
389 UsageVector vector = new UsageVector (
390 type, Parent.CurrentUsageVector, block, Location);
393 Report.Debug (1, " CREATED SIBLING", CurrentUsageVector);
396 public void CreateSibling ()
398 CreateSibling (null, SiblingType.Conditional);
401 protected abstract void AddSibling (UsageVector uv);
403 protected abstract UsageVector Merge ();
406 // Merge a child branching.
408 public UsageVector MergeChild (FlowBranching child)
410 bool overwrite = false;
412 switch (child.Type) {
413 case BranchingType.Labeled:
416 case BranchingType.Block:
417 if (child.Block != null && child.Block != child.Block.Explicit)
422 Report.Debug (2, " MERGING CHILD", this, child);
423 UsageVector result = CurrentUsageVector.MergeChild (child.Merge (), overwrite);
424 Report.Debug (2, " MERGING CHILD DONE", this, result);
428 public virtual bool InTryWithCatch ()
430 return Parent.InTryWithCatch ();
433 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
434 public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
436 return Parent.AddBreakOrigin (vector, loc);
439 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
440 public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
442 return Parent.AddContinueOrigin (vector, loc);
445 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
446 public virtual bool AddReturnOrigin (UsageVector vector, Location loc)
448 return Parent.AddReturnOrigin (vector, loc);
451 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
452 public virtual bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
454 return Parent.AddGotoOrigin (vector, goto_stmt);
457 public virtual void StealFinallyClauses (ref ArrayList list)
459 Parent.StealFinallyClauses (ref list);
462 public bool IsAssigned (VariableInfo vi)
464 return CurrentUsageVector.IsAssigned (vi, false);
467 public bool IsFieldAssigned (VariableInfo vi, string field_name)
469 return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
472 public void SetAssigned (VariableInfo vi)
474 CurrentUsageVector.SetAssigned (vi);
477 public void SetFieldAssigned (VariableInfo vi, string name)
479 CurrentUsageVector.SetFieldAssigned (vi, name);
482 public override string ToString ()
484 StringBuilder sb = new StringBuilder ();
485 sb.Append (GetType ());
493 sb.Append (Block.ID);
495 sb.Append (Block.StartLocation);
498 // sb.Append (Siblings.Length);
499 // sb.Append (" - ");
500 sb.Append (CurrentUsageVector);
502 return sb.ToString ();
506 get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
510 public class FlowBranchingBlock : FlowBranching
512 UsageVector sibling_list = null;
514 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
515 SiblingType stype, Block block, Location loc)
516 : base (parent, type, stype, block, loc)
519 public override UsageVector CurrentUsageVector {
520 get { return sibling_list; }
523 protected override void AddSibling (UsageVector sibling)
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)
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 FlowBranchingToplevel : FlowBranchingBlock
646 UsageVector return_origins;
648 public FlowBranchingToplevel (FlowBranching parent, ToplevelBlock stmt)
649 : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
653 public override bool InTryWithCatch ()
658 public override bool AddBreakOrigin (UsageVector vector, Location loc)
660 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
664 public override bool AddContinueOrigin (UsageVector vector, Location loc)
666 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
670 public override bool AddReturnOrigin (UsageVector vector, Location loc)
672 vector = vector.Clone ();
673 vector.Location = loc;
674 vector.Next = return_origins;
675 return_origins = vector;
679 public override void StealFinallyClauses (ref ArrayList list)
684 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
686 string name = goto_stmt.Target;
687 LabeledStatement s = Block.LookupLabel (name);
689 throw new InternalErrorException ("Shouldn't get here");
691 if (Parent == null) {
692 Error_UnknownLabel (goto_stmt.loc, name);
696 int errors = Report.Errors;
697 Parent.AddGotoOrigin (vector, goto_stmt);
698 if (errors == Report.Errors)
699 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
703 protected override UsageVector Merge ()
705 for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
706 Block.Toplevel.CheckOutParameters (origin, origin.Location);
708 UsageVector vector = base.Merge ();
709 Block.Toplevel.CheckOutParameters (vector, Block.loc);
710 // Note: we _do_not_ merge in the return origins
716 return Merge ().IsUnreachable;
720 public class FlowBranchingException : FlowBranching
722 ExceptionStatement stmt;
723 UsageVector current_vector;
724 UsageVector catch_vectors;
725 UsageVector finally_vector;
727 UsageVector break_origins;
728 UsageVector continue_origins;
729 UsageVector return_origins;
730 GotoOrigin goto_origins;
733 public GotoOrigin Next;
734 public Goto GotoStmt;
735 public UsageVector Vector;
737 public GotoOrigin (UsageVector vector, Goto goto_stmt, GotoOrigin next)
740 GotoStmt = goto_stmt;
747 public FlowBranchingException (FlowBranching parent,
748 ExceptionStatement stmt)
749 : base (parent, BranchingType.Exception, SiblingType.Try,
753 this.emit_finally = true;
756 protected override void AddSibling (UsageVector sibling)
758 switch (sibling.Type) {
759 case SiblingType.Try:
760 case SiblingType.Catch:
761 sibling.Next = catch_vectors;
762 catch_vectors = sibling;
764 case SiblingType.Finally:
765 finally_vector = sibling;
768 throw new InvalidOperationException ();
770 current_vector = sibling;
773 public override UsageVector CurrentUsageVector {
774 get { return current_vector; }
777 public override bool InTryWithCatch ()
779 if (finally_vector == null) {
781 if (t != null && t.HasCatch)
785 return base.InTryWithCatch ();
788 public override bool AddBreakOrigin (UsageVector vector, Location loc)
790 vector = vector.Clone ();
791 if (finally_vector != null) {
792 vector.MergeChild (finally_vector, false);
793 int errors = Report.Errors;
794 Parent.AddBreakOrigin (vector, loc);
795 if (errors == Report.Errors)
796 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
798 vector.Location = loc;
799 vector.Next = break_origins;
800 break_origins = vector;
805 public override bool AddContinueOrigin (UsageVector vector, Location loc)
807 vector = vector.Clone ();
808 if (finally_vector != null) {
809 vector.MergeChild (finally_vector, false);
810 int errors = Report.Errors;
811 Parent.AddContinueOrigin (vector, loc);
812 if (errors == Report.Errors)
813 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
815 vector.Location = loc;
816 vector.Next = continue_origins;
817 continue_origins = vector;
822 public override bool AddReturnOrigin (UsageVector vector, Location loc)
824 vector = vector.Clone ();
825 if (finally_vector != null) {
826 vector.MergeChild (finally_vector, false);
827 int errors = Report.Errors;
828 Parent.AddReturnOrigin (vector, loc);
829 if (errors == Report.Errors)
830 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
832 vector.Location = loc;
833 vector.Next = return_origins;
834 return_origins = vector;
839 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
841 LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
843 throw new InternalErrorException ("Shouldn't get here");
845 vector = vector.Clone ();
846 if (finally_vector != null) {
847 vector.MergeChild (finally_vector, false);
848 int errors = Report.Errors;
849 Parent.AddGotoOrigin (vector, goto_stmt);
850 if (errors == Report.Errors)
851 Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
853 goto_origins = new GotoOrigin (vector, goto_stmt, goto_origins);
858 public override void StealFinallyClauses (ref ArrayList list)
861 list = new ArrayList ();
863 emit_finally = false;
864 base.StealFinallyClauses (ref list);
867 public bool EmitFinally {
868 get { return emit_finally; }
871 protected override UsageVector Merge ()
873 Report.Debug (2, " MERGING TRY/CATCH", Name);
874 UsageVector vector = UsageVector.MergeSiblings (catch_vectors, Location);
875 Report.Debug (2, " MERGING TRY/CATCH DONE", vector);
877 if (finally_vector != null)
878 vector.MergeChild (finally_vector, false);
880 for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
881 if (finally_vector != null)
882 origin.MergeChild (finally_vector, false);
883 Parent.AddBreakOrigin (origin, origin.Location);
886 for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
887 if (finally_vector != null)
888 origin.MergeChild (finally_vector, false);
889 Parent.AddContinueOrigin (origin, origin.Location);
892 for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
893 if (finally_vector != null)
894 origin.MergeChild (finally_vector, false);
895 Parent.AddReturnOrigin (origin, origin.Location);
898 for (GotoOrigin origin = goto_origins; origin != null; origin = origin.Next) {
899 if (finally_vector != null)
900 origin.Vector.MergeChild (finally_vector, false);
901 Parent.AddGotoOrigin (origin.Vector, origin.GotoStmt);
909 // This is used by the flow analysis code to keep track of the type of local variables
912 // The flow code uses a BitVector to keep track of whether a variable has been assigned
913 // or not. This is easy for fundamental types (int, char etc.) or reference types since
914 // you can only assign the whole variable as such.
916 // For structs, we also need to keep track of all its fields. To do this, we allocate one
917 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
918 // one bit for each of its fields.
920 // This class computes this `layout' for each type.
922 public class TypeInfo
924 public readonly Type Type;
927 // Total number of bits a variable of this type consumes in the flow vector.
929 public readonly int TotalLength;
932 // Number of bits the simple fields of a variable of this type consume
933 // in the flow vector.
935 public readonly int Length;
938 // This is only used by sub-structs.
940 public readonly int Offset;
943 // If this is a struct.
945 public readonly bool IsStruct;
948 // If this is a struct, all fields which are structs theirselves.
950 public TypeInfo[] SubStructInfo;
952 protected readonly StructInfo struct_info;
953 private static Hashtable type_hash = new Hashtable ();
955 public static TypeInfo GetTypeInfo (Type type)
957 TypeInfo info = (TypeInfo) type_hash [type];
961 info = new TypeInfo (type);
962 type_hash.Add (type, info);
966 public static TypeInfo GetTypeInfo (TypeContainer tc)
968 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
972 info = new TypeInfo (tc);
973 type_hash.Add (tc.TypeBuilder, info);
977 private TypeInfo (Type type)
981 struct_info = StructInfo.GetStructInfo (type);
982 if (struct_info != null) {
983 Length = struct_info.Length;
984 TotalLength = struct_info.TotalLength;
985 SubStructInfo = struct_info.StructFields;
994 private TypeInfo (TypeContainer tc)
996 this.Type = tc.TypeBuilder;
998 struct_info = StructInfo.GetStructInfo (tc);
999 if (struct_info != null) {
1000 Length = struct_info.Length;
1001 TotalLength = struct_info.TotalLength;
1002 SubStructInfo = struct_info.StructFields;
1011 protected TypeInfo (StructInfo struct_info, int offset)
1013 this.struct_info = struct_info;
1014 this.Offset = offset;
1015 this.Length = struct_info.Length;
1016 this.TotalLength = struct_info.TotalLength;
1017 this.SubStructInfo = struct_info.StructFields;
1018 this.Type = struct_info.Type;
1019 this.IsStruct = true;
1022 public int GetFieldIndex (string name)
1024 if (struct_info == null)
1027 return struct_info [name];
1030 public TypeInfo GetSubStruct (string name)
1032 if (struct_info == null)
1035 return struct_info.GetStructField (name);
1039 // A struct's constructor must always assign all fields.
1040 // This method checks whether it actually does so.
1042 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1044 if (struct_info == null)
1048 for (int i = 0; i < struct_info.Count; i++) {
1049 FieldInfo field = struct_info.Fields [i];
1051 if (!branching.IsFieldAssigned (vi, field.Name)) {
1052 Report.Error (171, loc,
1053 "Field `{0}' must be fully assigned before control leaves the constructor",
1054 TypeManager.GetFullNameSignature (field));
1062 public override string ToString ()
1064 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1065 Type, Offset, Length, TotalLength);
1068 protected class StructInfo {
1069 public readonly Type Type;
1070 public readonly FieldInfo[] Fields;
1071 public readonly TypeInfo[] StructFields;
1072 public readonly int Count;
1073 public readonly int CountPublic;
1074 public readonly int CountNonPublic;
1075 public readonly int Length;
1076 public readonly int TotalLength;
1077 public readonly bool HasStructFields;
1079 private static Hashtable field_type_hash = new Hashtable ();
1080 private Hashtable struct_field_hash;
1081 private Hashtable field_hash;
1083 protected bool InTransit = false;
1085 // Private constructor. To save memory usage, we only need to create one instance
1086 // of this class per struct type.
1087 private StructInfo (Type type)
1091 field_type_hash.Add (type, this);
1093 if (type is TypeBuilder) {
1094 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1096 ArrayList fields = null;
1100 ArrayList public_fields = new ArrayList ();
1101 ArrayList non_public_fields = new ArrayList ();
1103 if (fields != null) {
1104 foreach (FieldBase field in fields) {
1105 if ((field.ModFlags & Modifiers.STATIC) != 0)
1107 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1108 public_fields.Add (field.FieldBuilder);
1110 non_public_fields.Add (field.FieldBuilder);
1114 CountPublic = public_fields.Count;
1115 CountNonPublic = non_public_fields.Count;
1116 Count = CountPublic + CountNonPublic;
1118 Fields = new FieldInfo [Count];
1119 public_fields.CopyTo (Fields, 0);
1120 non_public_fields.CopyTo (Fields, CountPublic);
1122 } else if (type is GenericTypeParameterBuilder) {
1123 CountPublic = CountNonPublic = Count = 0;
1125 Fields = new FieldInfo [0];
1128 FieldInfo[] public_fields = type.GetFields (
1129 BindingFlags.Instance|BindingFlags.Public);
1130 FieldInfo[] non_public_fields = type.GetFields (
1131 BindingFlags.Instance|BindingFlags.NonPublic);
1133 CountPublic = public_fields.Length;
1134 CountNonPublic = non_public_fields.Length;
1135 Count = CountPublic + CountNonPublic;
1137 Fields = new FieldInfo [Count];
1138 public_fields.CopyTo (Fields, 0);
1139 non_public_fields.CopyTo (Fields, CountPublic);
1142 struct_field_hash = new Hashtable ();
1143 field_hash = new Hashtable ();
1146 StructFields = new TypeInfo [Count];
1147 StructInfo[] sinfo = new StructInfo [Count];
1151 for (int i = 0; i < Count; i++) {
1152 FieldInfo field = (FieldInfo) Fields [i];
1154 sinfo [i] = GetStructInfo (field.FieldType);
1155 if (sinfo [i] == null)
1156 field_hash.Add (field.Name, ++Length);
1157 else if (sinfo [i].InTransit) {
1158 Report.Error (523, String.Format (
1159 "Struct member `{0}.{1}' of type `{2}' causes " +
1160 "a cycle in the structure layout",
1161 type, field.Name, sinfo [i].Type));
1169 TotalLength = Length + 1;
1170 for (int i = 0; i < Count; i++) {
1171 FieldInfo field = (FieldInfo) Fields [i];
1173 if (sinfo [i] == null)
1176 field_hash.Add (field.Name, TotalLength);
1178 HasStructFields = true;
1179 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1180 struct_field_hash.Add (field.Name, StructFields [i]);
1181 TotalLength += sinfo [i].TotalLength;
1185 public int this [string name] {
1187 if (field_hash.Contains (name))
1188 return (int) field_hash [name];
1194 public TypeInfo GetStructField (string name)
1196 return (TypeInfo) struct_field_hash [name];
1199 public static StructInfo GetStructInfo (Type type)
1201 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1202 TypeManager.IsBuiltinType (type))
1205 StructInfo info = (StructInfo) field_type_hash [type];
1209 return new StructInfo (type);
1212 public static StructInfo GetStructInfo (TypeContainer tc)
1214 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1218 return new StructInfo (tc.TypeBuilder);
1224 // This is used by the flow analysis code to store information about a single local variable
1225 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1226 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1227 // it has been assigned or not, but for structs, we need this information for each of its fields.
1229 public class VariableInfo {
1230 public readonly string Name;
1231 public readonly TypeInfo TypeInfo;
1234 // The bit offset of this variable in the flow vector.
1236 public readonly int Offset;
1239 // The number of bits this variable needs in the flow vector.
1240 // The first bit always specifies whether the variable as such has been assigned while
1241 // the remaining bits contain this information for each of a struct's fields.
1243 public readonly int Length;
1246 // If this is a parameter of local variable.
1248 public readonly bool IsParameter;
1250 public readonly LocalInfo LocalInfo;
1252 readonly VariableInfo Parent;
1253 VariableInfo[] sub_info;
1255 protected VariableInfo (string name, Type type, int offset)
1258 this.Offset = offset;
1259 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1261 Length = TypeInfo.TotalLength;
1266 protected VariableInfo (VariableInfo parent, TypeInfo type)
1268 this.Name = parent.Name;
1269 this.TypeInfo = type;
1270 this.Offset = parent.Offset + type.Offset;
1271 this.Parent = parent;
1272 this.Length = type.TotalLength;
1274 this.IsParameter = parent.IsParameter;
1275 this.LocalInfo = parent.LocalInfo;
1280 protected void Initialize ()
1282 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1283 if (sub_fields != null) {
1284 sub_info = new VariableInfo [sub_fields.Length];
1285 for (int i = 0; i < sub_fields.Length; i++) {
1286 if (sub_fields [i] != null)
1287 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1290 sub_info = new VariableInfo [0];
1293 public VariableInfo (LocalInfo local_info, int offset)
1294 : this (local_info.Name, local_info.VariableType, offset)
1296 this.LocalInfo = local_info;
1297 this.IsParameter = false;
1300 public VariableInfo (Parameters ip, int i, int offset)
1301 : this (ip.ParameterName (i), TypeManager.GetElementType (ip.ParameterType (i)), offset)
1303 this.IsParameter = true;
1306 public bool IsAssigned (EmitContext ec)
1308 return !ec.DoFlowAnalysis ||
1309 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1310 ec.CurrentBranching.IsAssigned (this);
1313 public bool IsAssigned (EmitContext ec, Location loc)
1315 if (IsAssigned (ec))
1318 Report.Error (165, loc,
1319 "Use of unassigned local variable `" + Name + "'");
1320 ec.CurrentBranching.SetAssigned (this);
1324 public bool IsAssigned (MyBitVector vector)
1329 if (vector [Offset])
1332 // FIXME: Fix SetFieldAssigned to set the whole range like SetAssigned below. Then, get rid of this stanza
1333 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent) {
1334 if (vector [parent.Offset]) {
1335 // 'parent' is assigned, but someone forgot to note that all its components are assigned too
1336 parent.SetAssigned (vector);
1341 // Return unless this is a struct.
1342 if (!TypeInfo.IsStruct)
1345 // Ok, so each field must be assigned.
1346 for (int i = 0; i < TypeInfo.Length; i++) {
1347 if (!vector [Offset + i + 1])
1351 // Ok, now check all fields which are structs.
1352 for (int i = 0; i < sub_info.Length; i++) {
1353 VariableInfo sinfo = sub_info [i];
1357 if (!sinfo.IsAssigned (vector))
1361 vector [Offset] = true;
1365 public void SetAssigned (EmitContext ec)
1367 if (ec.DoFlowAnalysis)
1368 ec.CurrentBranching.SetAssigned (this);
1371 public void SetAssigned (MyBitVector vector)
1374 vector [Offset] = true;
1376 vector.SetRange (Offset, Length);
1379 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1381 if (!ec.DoFlowAnalysis ||
1382 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1383 ec.CurrentBranching.IsFieldAssigned (this, name))
1386 Report.Error (170, loc,
1387 "Use of possibly unassigned field `" + name + "'");
1388 ec.CurrentBranching.SetFieldAssigned (this, name);
1392 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1394 int field_idx = TypeInfo.GetFieldIndex (field_name);
1399 return vector [Offset + field_idx];
1402 public void SetFieldAssigned (EmitContext ec, string name)
1404 if (ec.DoFlowAnalysis)
1405 ec.CurrentBranching.SetFieldAssigned (this, name);
1408 public void SetFieldAssigned (MyBitVector vector, string field_name)
1410 int field_idx = TypeInfo.GetFieldIndex (field_name);
1415 vector [Offset + field_idx] = true;
1418 public VariableInfo GetSubStruct (string name)
1420 TypeInfo type = TypeInfo.GetSubStruct (name);
1425 return new VariableInfo (this, type);
1428 public override string ToString ()
1430 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1431 Name, TypeInfo, Offset, Length, IsParameter);
1436 // This is a special bit vector which can inherit from another bit vector doing a
1437 // copy-on-write strategy. The inherited vector may have a smaller size than the
1440 public class MyBitVector {
1441 public readonly int Count;
1442 public static readonly MyBitVector Empty = new MyBitVector ();
1444 // Invariant: vector != null => vector.Count == Count
1445 // Invariant: vector == null || shared == null
1446 // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
1447 // The object in 'shared' cannot be modified, while 'vector' can be freely modified
1448 BitArray vector, shared;
1452 shared = new BitArray (0, false);
1455 public MyBitVector (MyBitVector InheritsFrom, int Count)
1457 if (InheritsFrom != null)
1458 shared = InheritsFrom.Shared;
1463 // Use this accessor to get a shareable copy of the underlying BitArray representation
1466 // Post-condition: vector == null
1467 if (shared == null) {
1476 // Get/set bit `index' in the bit vector.
1478 public bool this [int index] {
1481 throw new ArgumentOutOfRangeException ();
1484 return vector [index];
1487 if (index < shared.Count)
1488 return shared [index];
1493 // Only copy the vector if we're actually modifying it.
1494 if (this [index] != value) {
1496 initialize_vector ();
1497 vector [index] = value;
1503 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1504 // different size than the current one.
1506 private MyBitVector Or (MyBitVector new_vector)
1508 if (Count == 0 || new_vector.Count == 0)
1511 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1514 int n = new_vector.Count;
1516 for (int i = 0; i < n; ++i)
1524 if (Count == o.Count) {
1525 if (vector == null) {
1528 initialize_vector ();
1538 for (int i = 0; i < min; i++) {
1547 // Performs an `and' operation on the bit vector. The `new_vector' may have
1548 // a different size than the current one.
1550 private MyBitVector And (MyBitVector new_vector)
1555 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1558 for (int i = new_vector.Count; i < Count; ++i)
1568 if (Count == o.Count) {
1569 if (vector == null) {
1570 if (shared == null) {
1571 shared = new_vector.Shared;
1574 initialize_vector ();
1584 for (int i = 0; i < min; i++) {
1589 for (int i = min; i < Count; i++)
1595 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1603 if (a.Count > b.Count)
1604 return a.Clone ().And (b);
1606 return b.Clone ().And (a);
1609 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1614 return new MyBitVector (null, b.Count);
1616 return new MyBitVector (null, a.Count);
1617 if (a.Count > b.Count)
1618 return a.Clone ().Or (b);
1620 return b.Clone ().Or (a);
1623 public MyBitVector Clone ()
1625 return Count == 0 ? Empty : new MyBitVector (this, Count);
1628 public void SetRange (int offset, int length)
1630 if (offset > Count || offset + length > Count)
1631 throw new ArgumentOutOfRangeException ();
1633 if (shared == null && vector == null)
1637 if (shared != null) {
1638 if (offset + length <= shared.Count) {
1639 for (; i < length; ++i)
1640 if (!shared [i+offset])
1645 initialize_vector ();
1647 for (; i < length; ++i)
1648 vector [i+offset] = true;
1652 public void SetAll (bool value)
1654 // Don't clobber Empty
1657 shared = value ? null : Empty.Shared;
1661 void initialize_vector ()
1663 // Post-condition: vector != null
1664 if (shared == null) {
1665 vector = new BitArray (Count, true);
1669 vector = new BitArray (shared);
1670 if (Count != vector.Count)
1671 vector.Length = Count;
1675 StringBuilder Dump (StringBuilder sb)
1677 BitArray dump = vector == null ? shared : vector;
1679 return sb.Append ("/");
1682 for (int i = 0; i < dump.Count; i++)
1683 sb.Append (dump [i] ? "1" : "0");
1687 public override string ToString ()
1689 return Dump (new StringBuilder ("{")).Append ("}").ToString ();