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 // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
458 public virtual bool StealFinallyClauses (ref ArrayList list)
460 return Parent.StealFinallyClauses (ref list);
463 public bool IsAssigned (VariableInfo vi)
465 return CurrentUsageVector.IsAssigned (vi, false);
468 public bool IsFieldAssigned (VariableInfo vi, string field_name)
470 return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
473 public void SetAssigned (VariableInfo vi)
475 CurrentUsageVector.SetAssigned (vi);
478 public void SetFieldAssigned (VariableInfo vi, string name)
480 CurrentUsageVector.SetFieldAssigned (vi, name);
483 public override string ToString ()
485 StringBuilder sb = new StringBuilder ();
486 sb.Append (GetType ());
494 sb.Append (Block.ID);
496 sb.Append (Block.StartLocation);
499 // sb.Append (Siblings.Length);
500 // sb.Append (" - ");
501 sb.Append (CurrentUsageVector);
503 return sb.ToString ();
507 get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
511 public class FlowBranchingBlock : FlowBranching
513 UsageVector sibling_list = null;
515 public FlowBranchingBlock (FlowBranching parent, BranchingType type,
516 SiblingType stype, Block block, Location loc)
517 : base (parent, type, stype, block, loc)
520 public override UsageVector CurrentUsageVector {
521 get { return sibling_list; }
524 protected override void AddSibling (UsageVector sibling)
526 sibling.Next = sibling_list;
527 sibling_list = sibling;
530 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
532 LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
534 return Parent.AddGotoOrigin (vector, goto_stmt);
537 goto_stmt.SetResolvedTarget (stmt);
538 stmt.AddUsageVector (vector);
542 public static void Error_UnknownLabel (Location loc, string label)
544 Report.Error(159, loc, "The label `{0}:' could not be found within the scope of the goto statement",
548 protected override UsageVector Merge ()
550 Report.Debug (2, " MERGING SIBLINGS", Name);
551 UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
552 Report.Debug (2, " MERGING SIBLINGS DONE", Name, vector);
557 public class FlowBranchingBreakable : FlowBranchingBlock
559 UsageVector break_origins;
561 public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
562 : base (parent, type, stype, block, loc)
565 public override bool AddBreakOrigin (UsageVector vector, Location loc)
567 vector = vector.Clone ();
568 vector.Next = break_origins;
569 break_origins = vector;
573 protected override UsageVector Merge ()
575 UsageVector vector = base.Merge ();
576 vector.MergeOrigins (break_origins);
581 public class FlowBranchingContinuable : FlowBranchingBlock
583 UsageVector continue_origins;
585 public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
586 : base (parent, type, stype, block, loc)
589 public override bool AddContinueOrigin (UsageVector vector, Location loc)
591 vector = vector.Clone ();
592 vector.Next = continue_origins;
593 continue_origins = vector;
597 protected override UsageVector Merge ()
599 UsageVector vector = base.Merge ();
600 vector.MergeOrigins (continue_origins);
605 public class FlowBranchingLabeled : FlowBranchingBlock
607 LabeledStatement stmt;
610 public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
611 : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
614 CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
615 actual = CurrentUsageVector.Clone ();
617 // stand-in for backward jumps
618 CurrentUsageVector.ResetBarrier ();
621 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
623 if (goto_stmt.Target != stmt.Name)
624 return Parent.AddGotoOrigin (vector, goto_stmt);
627 goto_stmt.SetResolvedTarget (stmt);
628 actual.MergeOrigins (vector.Clone ());
633 protected override UsageVector Merge ()
635 UsageVector vector = base.Merge ();
637 if (actual.IsUnreachable)
638 Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
640 actual.MergeChild (vector, false);
645 public class FlowBranchingToplevel : FlowBranchingBlock
647 UsageVector return_origins;
649 public FlowBranchingToplevel (FlowBranching parent, ToplevelBlock stmt)
650 : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
654 public override bool InTryWithCatch ()
659 public override bool AddBreakOrigin (UsageVector vector, Location loc)
661 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
665 public override bool AddContinueOrigin (UsageVector vector, Location loc)
667 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
671 public override bool AddReturnOrigin (UsageVector vector, Location loc)
673 vector = vector.Clone ();
674 vector.Location = loc;
675 vector.Next = return_origins;
676 return_origins = vector;
680 public override bool StealFinallyClauses (ref ArrayList list)
685 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
687 string name = goto_stmt.Target;
688 LabeledStatement s = Block.LookupLabel (name);
690 throw new InternalErrorException ("Shouldn't get here");
692 if (Parent == null) {
693 Error_UnknownLabel (goto_stmt.loc, name);
697 int errors = Report.Errors;
698 Parent.AddGotoOrigin (vector, goto_stmt);
699 if (errors == Report.Errors)
700 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
704 protected override UsageVector Merge ()
706 for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
707 Block.Toplevel.CheckOutParameters (origin, origin.Location);
709 UsageVector vector = base.Merge ();
710 Block.Toplevel.CheckOutParameters (vector, Block.loc);
711 // Note: we _do_not_ merge in the return origins
717 return Merge ().IsUnreachable;
721 public class FlowBranchingException : FlowBranching
723 ExceptionStatement stmt;
724 UsageVector current_vector;
725 UsageVector catch_vectors;
726 UsageVector finally_vector;
728 UsageVector break_origins;
729 UsageVector continue_origins;
730 UsageVector return_origins;
731 GotoOrigin goto_origins;
734 public GotoOrigin Next;
735 public Goto GotoStmt;
736 public UsageVector Vector;
738 public GotoOrigin (UsageVector vector, Goto goto_stmt, GotoOrigin next)
741 GotoStmt = goto_stmt;
748 public FlowBranchingException (FlowBranching parent,
749 ExceptionStatement stmt)
750 : base (parent, BranchingType.Exception, SiblingType.Try,
754 this.emit_finally = true;
757 protected override void AddSibling (UsageVector sibling)
759 switch (sibling.Type) {
760 case SiblingType.Try:
761 case SiblingType.Catch:
762 sibling.Next = catch_vectors;
763 catch_vectors = sibling;
765 case SiblingType.Finally:
766 finally_vector = sibling;
769 throw new InvalidOperationException ();
771 current_vector = sibling;
774 public override UsageVector CurrentUsageVector {
775 get { return current_vector; }
778 public override bool InTryWithCatch ()
780 if (finally_vector == null) {
782 if (t != null && t.HasCatch)
786 return base.InTryWithCatch ();
789 public override bool AddBreakOrigin (UsageVector vector, Location loc)
791 vector = vector.Clone ();
792 if (finally_vector != null) {
793 vector.MergeChild (finally_vector, false);
794 int errors = Report.Errors;
795 Parent.AddBreakOrigin (vector, loc);
796 if (errors == Report.Errors)
797 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
799 vector.Location = loc;
800 vector.Next = break_origins;
801 break_origins = vector;
806 public override bool AddContinueOrigin (UsageVector vector, Location loc)
808 vector = vector.Clone ();
809 if (finally_vector != null) {
810 vector.MergeChild (finally_vector, false);
811 int errors = Report.Errors;
812 Parent.AddContinueOrigin (vector, loc);
813 if (errors == Report.Errors)
814 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
816 vector.Location = loc;
817 vector.Next = continue_origins;
818 continue_origins = vector;
823 public override bool AddReturnOrigin (UsageVector vector, Location loc)
825 vector = vector.Clone ();
826 if (finally_vector != null) {
827 vector.MergeChild (finally_vector, false);
828 int errors = Report.Errors;
829 Parent.AddReturnOrigin (vector, loc);
830 if (errors == Report.Errors)
831 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
833 vector.Location = loc;
834 vector.Next = return_origins;
835 return_origins = vector;
840 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
842 LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
844 throw new InternalErrorException ("Shouldn't get here");
846 vector = vector.Clone ();
847 if (finally_vector != null) {
848 vector.MergeChild (finally_vector, false);
849 int errors = Report.Errors;
850 Parent.AddGotoOrigin (vector, goto_stmt);
851 if (errors == Report.Errors)
852 Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
854 goto_origins = new GotoOrigin (vector, goto_stmt, goto_origins);
859 public override bool StealFinallyClauses (ref ArrayList list)
862 list = new ArrayList ();
864 emit_finally = false;
865 base.StealFinallyClauses (ref list);
869 public bool EmitFinally {
870 get { return emit_finally; }
873 protected override UsageVector Merge ()
875 Report.Debug (2, " MERGING TRY/CATCH", Name);
876 UsageVector vector = UsageVector.MergeSiblings (catch_vectors, Location);
877 Report.Debug (2, " MERGING TRY/CATCH DONE", vector);
879 if (finally_vector != null)
880 vector.MergeChild (finally_vector, false);
882 for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
883 if (finally_vector != null)
884 origin.MergeChild (finally_vector, false);
885 Parent.AddBreakOrigin (origin, origin.Location);
888 for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
889 if (finally_vector != null)
890 origin.MergeChild (finally_vector, false);
891 Parent.AddContinueOrigin (origin, origin.Location);
894 for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
895 if (finally_vector != null)
896 origin.MergeChild (finally_vector, false);
897 Parent.AddReturnOrigin (origin, origin.Location);
900 for (GotoOrigin origin = goto_origins; origin != null; origin = origin.Next) {
901 if (finally_vector != null)
902 origin.Vector.MergeChild (finally_vector, false);
903 Parent.AddGotoOrigin (origin.Vector, origin.GotoStmt);
911 // This is used by the flow analysis code to keep track of the type of local variables
914 // The flow code uses a BitVector to keep track of whether a variable has been assigned
915 // or not. This is easy for fundamental types (int, char etc.) or reference types since
916 // you can only assign the whole variable as such.
918 // For structs, we also need to keep track of all its fields. To do this, we allocate one
919 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
920 // one bit for each of its fields.
922 // This class computes this `layout' for each type.
924 public class TypeInfo
926 public readonly Type Type;
929 // Total number of bits a variable of this type consumes in the flow vector.
931 public readonly int TotalLength;
934 // Number of bits the simple fields of a variable of this type consume
935 // in the flow vector.
937 public readonly int Length;
940 // This is only used by sub-structs.
942 public readonly int Offset;
945 // If this is a struct.
947 public readonly bool IsStruct;
950 // If this is a struct, all fields which are structs theirselves.
952 public TypeInfo[] SubStructInfo;
954 protected readonly StructInfo struct_info;
955 private static Hashtable type_hash = new Hashtable ();
957 public static TypeInfo GetTypeInfo (Type type)
959 TypeInfo info = (TypeInfo) type_hash [type];
963 info = new TypeInfo (type);
964 type_hash.Add (type, info);
968 public static TypeInfo GetTypeInfo (TypeContainer tc)
970 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
974 info = new TypeInfo (tc);
975 type_hash.Add (tc.TypeBuilder, info);
979 private TypeInfo (Type type)
983 struct_info = StructInfo.GetStructInfo (type);
984 if (struct_info != null) {
985 Length = struct_info.Length;
986 TotalLength = struct_info.TotalLength;
987 SubStructInfo = struct_info.StructFields;
996 private TypeInfo (TypeContainer tc)
998 this.Type = tc.TypeBuilder;
1000 struct_info = StructInfo.GetStructInfo (tc);
1001 if (struct_info != null) {
1002 Length = struct_info.Length;
1003 TotalLength = struct_info.TotalLength;
1004 SubStructInfo = struct_info.StructFields;
1013 protected TypeInfo (StructInfo struct_info, int offset)
1015 this.struct_info = struct_info;
1016 this.Offset = offset;
1017 this.Length = struct_info.Length;
1018 this.TotalLength = struct_info.TotalLength;
1019 this.SubStructInfo = struct_info.StructFields;
1020 this.Type = struct_info.Type;
1021 this.IsStruct = true;
1024 public int GetFieldIndex (string name)
1026 if (struct_info == null)
1029 return struct_info [name];
1032 public TypeInfo GetSubStruct (string name)
1034 if (struct_info == null)
1037 return struct_info.GetStructField (name);
1041 // A struct's constructor must always assign all fields.
1042 // This method checks whether it actually does so.
1044 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1046 if (struct_info == null)
1050 for (int i = 0; i < struct_info.Count; i++) {
1051 FieldInfo field = struct_info.Fields [i];
1053 if (!branching.IsFieldAssigned (vi, field.Name)) {
1054 Report.Error (171, loc,
1055 "Field `{0}' must be fully assigned before control leaves the constructor",
1056 TypeManager.GetFullNameSignature (field));
1064 public override string ToString ()
1066 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1067 Type, Offset, Length, TotalLength);
1070 protected class StructInfo {
1071 public readonly Type Type;
1072 public readonly FieldInfo[] Fields;
1073 public readonly TypeInfo[] StructFields;
1074 public readonly int Count;
1075 public readonly int CountPublic;
1076 public readonly int CountNonPublic;
1077 public readonly int Length;
1078 public readonly int TotalLength;
1079 public readonly bool HasStructFields;
1081 private static Hashtable field_type_hash = new Hashtable ();
1082 private Hashtable struct_field_hash;
1083 private Hashtable field_hash;
1085 protected bool InTransit = false;
1087 // Private constructor. To save memory usage, we only need to create one instance
1088 // of this class per struct type.
1089 private StructInfo (Type type)
1093 field_type_hash.Add (type, this);
1095 if (type is TypeBuilder) {
1096 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1098 ArrayList fields = null;
1102 ArrayList public_fields = new ArrayList ();
1103 ArrayList non_public_fields = new ArrayList ();
1105 if (fields != null) {
1106 foreach (FieldBase field in fields) {
1107 if ((field.ModFlags & Modifiers.STATIC) != 0)
1109 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1110 public_fields.Add (field.FieldBuilder);
1112 non_public_fields.Add (field.FieldBuilder);
1116 CountPublic = public_fields.Count;
1117 CountNonPublic = non_public_fields.Count;
1118 Count = CountPublic + CountNonPublic;
1120 Fields = new FieldInfo [Count];
1121 public_fields.CopyTo (Fields, 0);
1122 non_public_fields.CopyTo (Fields, CountPublic);
1124 } else if (type is GenericTypeParameterBuilder) {
1125 CountPublic = CountNonPublic = Count = 0;
1127 Fields = new FieldInfo [0];
1130 FieldInfo[] public_fields = type.GetFields (
1131 BindingFlags.Instance|BindingFlags.Public);
1132 FieldInfo[] non_public_fields = type.GetFields (
1133 BindingFlags.Instance|BindingFlags.NonPublic);
1135 CountPublic = public_fields.Length;
1136 CountNonPublic = non_public_fields.Length;
1137 Count = CountPublic + CountNonPublic;
1139 Fields = new FieldInfo [Count];
1140 public_fields.CopyTo (Fields, 0);
1141 non_public_fields.CopyTo (Fields, CountPublic);
1144 struct_field_hash = new Hashtable ();
1145 field_hash = new Hashtable ();
1148 StructFields = new TypeInfo [Count];
1149 StructInfo[] sinfo = new StructInfo [Count];
1153 for (int i = 0; i < Count; i++) {
1154 FieldInfo field = (FieldInfo) Fields [i];
1156 sinfo [i] = GetStructInfo (field.FieldType);
1157 if (sinfo [i] == null)
1158 field_hash.Add (field.Name, ++Length);
1159 else if (sinfo [i].InTransit) {
1160 Report.Error (523, String.Format (
1161 "Struct member `{0}.{1}' of type `{2}' causes " +
1162 "a cycle in the structure layout",
1163 type, field.Name, sinfo [i].Type));
1171 TotalLength = Length + 1;
1172 for (int i = 0; i < Count; i++) {
1173 FieldInfo field = (FieldInfo) Fields [i];
1175 if (sinfo [i] == null)
1178 field_hash.Add (field.Name, TotalLength);
1180 HasStructFields = true;
1181 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1182 struct_field_hash.Add (field.Name, StructFields [i]);
1183 TotalLength += sinfo [i].TotalLength;
1187 public int this [string name] {
1189 if (field_hash.Contains (name))
1190 return (int) field_hash [name];
1196 public TypeInfo GetStructField (string name)
1198 return (TypeInfo) struct_field_hash [name];
1201 public static StructInfo GetStructInfo (Type type)
1203 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1204 TypeManager.IsBuiltinType (type))
1207 StructInfo info = (StructInfo) field_type_hash [type];
1211 return new StructInfo (type);
1214 public static StructInfo GetStructInfo (TypeContainer tc)
1216 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1220 return new StructInfo (tc.TypeBuilder);
1226 // This is used by the flow analysis code to store information about a single local variable
1227 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1228 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1229 // it has been assigned or not, but for structs, we need this information for each of its fields.
1231 public class VariableInfo {
1232 public readonly string Name;
1233 public readonly TypeInfo TypeInfo;
1236 // The bit offset of this variable in the flow vector.
1238 public readonly int Offset;
1241 // The number of bits this variable needs in the flow vector.
1242 // The first bit always specifies whether the variable as such has been assigned while
1243 // the remaining bits contain this information for each of a struct's fields.
1245 public readonly int Length;
1248 // If this is a parameter of local variable.
1250 public readonly bool IsParameter;
1252 public readonly LocalInfo LocalInfo;
1254 readonly VariableInfo Parent;
1255 VariableInfo[] sub_info;
1257 protected VariableInfo (string name, Type type, int offset)
1260 this.Offset = offset;
1261 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1263 Length = TypeInfo.TotalLength;
1268 protected VariableInfo (VariableInfo parent, TypeInfo type)
1270 this.Name = parent.Name;
1271 this.TypeInfo = type;
1272 this.Offset = parent.Offset + type.Offset;
1273 this.Parent = parent;
1274 this.Length = type.TotalLength;
1276 this.IsParameter = parent.IsParameter;
1277 this.LocalInfo = parent.LocalInfo;
1282 protected void Initialize ()
1284 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1285 if (sub_fields != null) {
1286 sub_info = new VariableInfo [sub_fields.Length];
1287 for (int i = 0; i < sub_fields.Length; i++) {
1288 if (sub_fields [i] != null)
1289 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1292 sub_info = new VariableInfo [0];
1295 public VariableInfo (LocalInfo local_info, int offset)
1296 : this (local_info.Name, local_info.VariableType, offset)
1298 this.LocalInfo = local_info;
1299 this.IsParameter = false;
1302 public VariableInfo (Parameters ip, int i, int offset)
1303 : this (ip.ParameterName (i), TypeManager.GetElementType (ip.ParameterType (i)), offset)
1305 this.IsParameter = true;
1308 public bool IsAssigned (EmitContext ec)
1310 return !ec.DoFlowAnalysis ||
1311 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1312 ec.CurrentBranching.IsAssigned (this);
1315 public bool IsAssigned (EmitContext ec, Location loc)
1317 if (IsAssigned (ec))
1320 Report.Error (165, loc,
1321 "Use of unassigned local variable `" + Name + "'");
1322 ec.CurrentBranching.SetAssigned (this);
1326 public bool IsAssigned (MyBitVector vector)
1331 if (vector [Offset])
1334 // FIXME: Fix SetFieldAssigned to set the whole range like SetAssigned below. Then, get rid of this stanza
1335 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent) {
1336 if (vector [parent.Offset]) {
1337 // 'parent' is assigned, but someone forgot to note that all its components are assigned too
1338 parent.SetAssigned (vector);
1343 // Return unless this is a struct.
1344 if (!TypeInfo.IsStruct)
1347 // Ok, so each field must be assigned.
1348 for (int i = 0; i < TypeInfo.Length; i++) {
1349 if (!vector [Offset + i + 1])
1353 // Ok, now check all fields which are structs.
1354 for (int i = 0; i < sub_info.Length; i++) {
1355 VariableInfo sinfo = sub_info [i];
1359 if (!sinfo.IsAssigned (vector))
1363 vector [Offset] = true;
1367 public void SetAssigned (EmitContext ec)
1369 if (ec.DoFlowAnalysis)
1370 ec.CurrentBranching.SetAssigned (this);
1373 public void SetAssigned (MyBitVector vector)
1376 vector [Offset] = true;
1378 vector.SetRange (Offset, Length);
1381 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1383 if (!ec.DoFlowAnalysis ||
1384 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1385 ec.CurrentBranching.IsFieldAssigned (this, name))
1388 Report.Error (170, loc,
1389 "Use of possibly unassigned field `" + name + "'");
1390 ec.CurrentBranching.SetFieldAssigned (this, name);
1394 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1396 int field_idx = TypeInfo.GetFieldIndex (field_name);
1401 return vector [Offset + field_idx];
1404 public void SetFieldAssigned (EmitContext ec, string name)
1406 if (ec.DoFlowAnalysis)
1407 ec.CurrentBranching.SetFieldAssigned (this, name);
1410 public void SetFieldAssigned (MyBitVector vector, string field_name)
1412 int field_idx = TypeInfo.GetFieldIndex (field_name);
1417 vector [Offset + field_idx] = true;
1420 public VariableInfo GetSubStruct (string name)
1422 TypeInfo type = TypeInfo.GetSubStruct (name);
1427 return new VariableInfo (this, type);
1430 public override string ToString ()
1432 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1433 Name, TypeInfo, Offset, Length, IsParameter);
1438 // This is a special bit vector which can inherit from another bit vector doing a
1439 // copy-on-write strategy. The inherited vector may have a smaller size than the
1442 public class MyBitVector {
1443 public readonly int Count;
1444 public static readonly MyBitVector Empty = new MyBitVector ();
1446 // Invariant: vector != null => vector.Count == Count
1447 // Invariant: vector == null || shared == null
1448 // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
1449 // The object in 'shared' cannot be modified, while 'vector' can be freely modified
1450 BitArray vector, shared;
1454 shared = new BitArray (0, false);
1457 public MyBitVector (MyBitVector InheritsFrom, int Count)
1459 if (InheritsFrom != null)
1460 shared = InheritsFrom.Shared;
1465 // Use this accessor to get a shareable copy of the underlying BitArray representation
1468 // Post-condition: vector == null
1469 if (shared == null) {
1478 // Get/set bit `index' in the bit vector.
1480 public bool this [int index] {
1483 throw new ArgumentOutOfRangeException ();
1486 return vector [index];
1489 if (index < shared.Count)
1490 return shared [index];
1495 // Only copy the vector if we're actually modifying it.
1496 if (this [index] != value) {
1498 initialize_vector ();
1499 vector [index] = value;
1505 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1506 // different size than the current one.
1508 private MyBitVector Or (MyBitVector new_vector)
1510 if (Count == 0 || new_vector.Count == 0)
1513 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1516 int n = new_vector.Count;
1518 for (int i = 0; i < n; ++i)
1526 if (Count == o.Count) {
1527 if (vector == null) {
1530 initialize_vector ();
1540 for (int i = 0; i < min; i++) {
1549 // Performs an `and' operation on the bit vector. The `new_vector' may have
1550 // a different size than the current one.
1552 private MyBitVector And (MyBitVector new_vector)
1557 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1560 for (int i = new_vector.Count; i < Count; ++i)
1570 if (Count == o.Count) {
1571 if (vector == null) {
1572 if (shared == null) {
1573 shared = new_vector.Shared;
1576 initialize_vector ();
1586 for (int i = 0; i < min; i++) {
1591 for (int i = min; i < Count; i++)
1597 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1605 if (a.Count > b.Count)
1606 return a.Clone ().And (b);
1608 return b.Clone ().And (a);
1611 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1616 return new MyBitVector (null, b.Count);
1618 return new MyBitVector (null, a.Count);
1619 if (a.Count > b.Count)
1620 return a.Clone ().Or (b);
1622 return b.Clone ().Or (a);
1625 public MyBitVector Clone ()
1627 return Count == 0 ? Empty : new MyBitVector (this, Count);
1630 public void SetRange (int offset, int length)
1632 if (offset > Count || offset + length > Count)
1633 throw new ArgumentOutOfRangeException ();
1635 if (shared == null && vector == null)
1639 if (shared != null) {
1640 if (offset + length <= shared.Count) {
1641 for (; i < length; ++i)
1642 if (!shared [i+offset])
1647 initialize_vector ();
1649 for (; i < length; ++i)
1650 vector [i+offset] = true;
1654 public void SetAll (bool value)
1656 // Don't clobber Empty
1659 shared = value ? null : Empty.Shared;
1663 void initialize_vector ()
1665 // Post-condition: vector != null
1666 if (shared == null) {
1667 vector = new BitArray (Count, true);
1671 vector = new BitArray (shared);
1672 if (Count != vector.Count)
1673 vector.Length = Count;
1677 StringBuilder Dump (StringBuilder sb)
1679 BitArray dump = vector == null ? shared : vector;
1681 return sb.Append ("/");
1684 for (int i = 0; i < dump.Count; i++)
1685 sb.Append (dump [i] ? "1" : "0");
1689 public override string ToString ()
1691 return Dump (new StringBuilder ("{")).Append ("}").ToString ();