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)
654 // Check whether all `out' parameters have been assigned.
656 void CheckOutParameters (UsageVector vector, Location loc)
658 if (vector.IsUnreachable)
660 VariableInfo [] param_map = Block.Toplevel.ParameterMap;
661 if (param_map == null)
663 for (int i = 0; i < param_map.Length; i++) {
664 VariableInfo var = param_map [i];
669 if (vector.IsAssigned (var, false))
672 Report.Error (177, loc, "The out parameter `{0}' must be assigned to before control leaves the current method",
677 public override bool InTryWithCatch ()
682 public override bool AddBreakOrigin (UsageVector vector, Location loc)
684 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
688 public override bool AddContinueOrigin (UsageVector vector, Location loc)
690 Report.Error (139, loc, "No enclosing loop out of which to break or continue");
694 public override bool AddReturnOrigin (UsageVector vector, Location loc)
696 vector = vector.Clone ();
697 vector.Location = loc;
698 vector.Next = return_origins;
699 return_origins = vector;
703 public override void StealFinallyClauses (ref ArrayList list)
708 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
710 string name = goto_stmt.Target;
711 LabeledStatement s = Block.LookupLabel (name);
713 throw new InternalErrorException ("Shouldn't get here");
715 if (Parent == null) {
716 Error_UnknownLabel (goto_stmt.loc, name);
720 int errors = Report.Errors;
721 Parent.AddGotoOrigin (vector, goto_stmt);
722 if (errors == Report.Errors)
723 Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
727 protected override UsageVector Merge ()
729 for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
730 CheckOutParameters (origin, origin.Location);
732 UsageVector vector = base.Merge ();
733 CheckOutParameters (vector, Block.loc);
734 // Note: we _do_not_ merge in the return origins
740 return Merge ().IsUnreachable;
744 public class FlowBranchingException : FlowBranching
746 ExceptionStatement stmt;
747 UsageVector current_vector;
748 UsageVector catch_vectors;
749 UsageVector finally_vector;
751 UsageVector break_origins;
752 UsageVector continue_origins;
753 UsageVector return_origins;
754 GotoOrigin goto_origins;
757 public GotoOrigin Next;
758 public Goto GotoStmt;
759 public UsageVector Vector;
761 public GotoOrigin (UsageVector vector, Goto goto_stmt, GotoOrigin next)
764 GotoStmt = goto_stmt;
771 public FlowBranchingException (FlowBranching parent,
772 ExceptionStatement stmt)
773 : base (parent, BranchingType.Exception, SiblingType.Try,
777 this.emit_finally = true;
780 protected override void AddSibling (UsageVector sibling)
782 switch (sibling.Type) {
783 case SiblingType.Try:
784 case SiblingType.Catch:
785 sibling.Next = catch_vectors;
786 catch_vectors = sibling;
788 case SiblingType.Finally:
789 finally_vector = sibling;
792 throw new InvalidOperationException ();
794 current_vector = sibling;
797 public override UsageVector CurrentUsageVector {
798 get { return current_vector; }
801 public override bool InTryWithCatch ()
803 if (finally_vector == null) {
805 if (t != null && t.HasCatch)
809 return base.InTryWithCatch ();
812 public override bool AddBreakOrigin (UsageVector vector, Location loc)
814 vector = vector.Clone ();
815 if (finally_vector != null) {
816 vector.MergeChild (finally_vector, false);
817 int errors = Report.Errors;
818 Parent.AddBreakOrigin (vector, loc);
819 if (errors == Report.Errors)
820 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
822 vector.Location = loc;
823 vector.Next = break_origins;
824 break_origins = vector;
829 public override bool AddContinueOrigin (UsageVector vector, Location loc)
831 vector = vector.Clone ();
832 if (finally_vector != null) {
833 vector.MergeChild (finally_vector, false);
834 int errors = Report.Errors;
835 Parent.AddContinueOrigin (vector, loc);
836 if (errors == Report.Errors)
837 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
839 vector.Location = loc;
840 vector.Next = continue_origins;
841 continue_origins = vector;
846 public override bool AddReturnOrigin (UsageVector vector, Location loc)
848 vector = vector.Clone ();
849 if (finally_vector != null) {
850 vector.MergeChild (finally_vector, false);
851 int errors = Report.Errors;
852 Parent.AddReturnOrigin (vector, loc);
853 if (errors == Report.Errors)
854 Report.Error (157, loc, "Control cannot leave the body of a finally clause");
856 vector.Location = loc;
857 vector.Next = return_origins;
858 return_origins = vector;
863 public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
865 LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
867 throw new InternalErrorException ("Shouldn't get here");
869 vector = vector.Clone ();
870 if (finally_vector != null) {
871 vector.MergeChild (finally_vector, false);
872 int errors = Report.Errors;
873 Parent.AddGotoOrigin (vector, goto_stmt);
874 if (errors == Report.Errors)
875 Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
877 goto_origins = new GotoOrigin (vector, goto_stmt, goto_origins);
882 public override void StealFinallyClauses (ref ArrayList list)
885 list = new ArrayList ();
887 emit_finally = false;
888 base.StealFinallyClauses (ref list);
891 public bool EmitFinally {
892 get { return emit_finally; }
895 protected override UsageVector Merge ()
897 Report.Debug (2, " MERGING TRY/CATCH", Name);
898 UsageVector vector = UsageVector.MergeSiblings (catch_vectors, Location);
899 Report.Debug (2, " MERGING TRY/CATCH DONE", vector);
901 if (finally_vector != null)
902 vector.MergeChild (finally_vector, false);
904 for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
905 if (finally_vector != null)
906 origin.MergeChild (finally_vector, false);
907 Parent.AddBreakOrigin (origin, origin.Location);
910 for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
911 if (finally_vector != null)
912 origin.MergeChild (finally_vector, false);
913 Parent.AddContinueOrigin (origin, origin.Location);
916 for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
917 if (finally_vector != null)
918 origin.MergeChild (finally_vector, false);
919 Parent.AddReturnOrigin (origin, origin.Location);
922 for (GotoOrigin origin = goto_origins; origin != null; origin = origin.Next) {
923 if (finally_vector != null)
924 origin.Vector.MergeChild (finally_vector, false);
925 Parent.AddGotoOrigin (origin.Vector, origin.GotoStmt);
933 // This is used by the flow analysis code to keep track of the type of local variables
936 // The flow code uses a BitVector to keep track of whether a variable has been assigned
937 // or not. This is easy for fundamental types (int, char etc.) or reference types since
938 // you can only assign the whole variable as such.
940 // For structs, we also need to keep track of all its fields. To do this, we allocate one
941 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
942 // one bit for each of its fields.
944 // This class computes this `layout' for each type.
946 public class TypeInfo
948 public readonly Type Type;
951 // Total number of bits a variable of this type consumes in the flow vector.
953 public readonly int TotalLength;
956 // Number of bits the simple fields of a variable of this type consume
957 // in the flow vector.
959 public readonly int Length;
962 // This is only used by sub-structs.
964 public readonly int Offset;
967 // If this is a struct.
969 public readonly bool IsStruct;
972 // If this is a struct, all fields which are structs theirselves.
974 public TypeInfo[] SubStructInfo;
976 protected readonly StructInfo struct_info;
977 private static Hashtable type_hash = new Hashtable ();
979 public static TypeInfo GetTypeInfo (Type type)
981 TypeInfo info = (TypeInfo) type_hash [type];
985 info = new TypeInfo (type);
986 type_hash.Add (type, info);
990 public static TypeInfo GetTypeInfo (TypeContainer tc)
992 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
996 info = new TypeInfo (tc);
997 type_hash.Add (tc.TypeBuilder, info);
1001 private TypeInfo (Type type)
1005 struct_info = StructInfo.GetStructInfo (type);
1006 if (struct_info != null) {
1007 Length = struct_info.Length;
1008 TotalLength = struct_info.TotalLength;
1009 SubStructInfo = struct_info.StructFields;
1018 private TypeInfo (TypeContainer tc)
1020 this.Type = tc.TypeBuilder;
1022 struct_info = StructInfo.GetStructInfo (tc);
1023 if (struct_info != null) {
1024 Length = struct_info.Length;
1025 TotalLength = struct_info.TotalLength;
1026 SubStructInfo = struct_info.StructFields;
1035 protected TypeInfo (StructInfo struct_info, int offset)
1037 this.struct_info = struct_info;
1038 this.Offset = offset;
1039 this.Length = struct_info.Length;
1040 this.TotalLength = struct_info.TotalLength;
1041 this.SubStructInfo = struct_info.StructFields;
1042 this.Type = struct_info.Type;
1043 this.IsStruct = true;
1046 public int GetFieldIndex (string name)
1048 if (struct_info == null)
1051 return struct_info [name];
1054 public TypeInfo GetSubStruct (string name)
1056 if (struct_info == null)
1059 return struct_info.GetStructField (name);
1063 // A struct's constructor must always assign all fields.
1064 // This method checks whether it actually does so.
1066 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1068 if (struct_info == null)
1072 for (int i = 0; i < struct_info.Count; i++) {
1073 FieldInfo field = struct_info.Fields [i];
1075 if (!branching.IsFieldAssigned (vi, field.Name)) {
1076 Report.Error (171, loc,
1077 "Field `{0}' must be fully assigned before control leaves the constructor",
1078 TypeManager.GetFullNameSignature (field));
1086 public override string ToString ()
1088 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1089 Type, Offset, Length, TotalLength);
1092 protected class StructInfo {
1093 public readonly Type Type;
1094 public readonly FieldInfo[] Fields;
1095 public readonly TypeInfo[] StructFields;
1096 public readonly int Count;
1097 public readonly int CountPublic;
1098 public readonly int CountNonPublic;
1099 public readonly int Length;
1100 public readonly int TotalLength;
1101 public readonly bool HasStructFields;
1103 private static Hashtable field_type_hash = new Hashtable ();
1104 private Hashtable struct_field_hash;
1105 private Hashtable field_hash;
1107 protected bool InTransit = false;
1109 // Private constructor. To save memory usage, we only need to create one instance
1110 // of this class per struct type.
1111 private StructInfo (Type type)
1115 field_type_hash.Add (type, this);
1117 if (type is TypeBuilder) {
1118 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1120 ArrayList fields = null;
1124 ArrayList public_fields = new ArrayList ();
1125 ArrayList non_public_fields = new ArrayList ();
1127 if (fields != null) {
1128 foreach (FieldBase field in fields) {
1129 if ((field.ModFlags & Modifiers.STATIC) != 0)
1131 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1132 public_fields.Add (field.FieldBuilder);
1134 non_public_fields.Add (field.FieldBuilder);
1138 CountPublic = public_fields.Count;
1139 CountNonPublic = non_public_fields.Count;
1140 Count = CountPublic + CountNonPublic;
1142 Fields = new FieldInfo [Count];
1143 public_fields.CopyTo (Fields, 0);
1144 non_public_fields.CopyTo (Fields, CountPublic);
1146 } else if (type is GenericTypeParameterBuilder) {
1147 CountPublic = CountNonPublic = Count = 0;
1149 Fields = new FieldInfo [0];
1152 FieldInfo[] public_fields = type.GetFields (
1153 BindingFlags.Instance|BindingFlags.Public);
1154 FieldInfo[] non_public_fields = type.GetFields (
1155 BindingFlags.Instance|BindingFlags.NonPublic);
1157 CountPublic = public_fields.Length;
1158 CountNonPublic = non_public_fields.Length;
1159 Count = CountPublic + CountNonPublic;
1161 Fields = new FieldInfo [Count];
1162 public_fields.CopyTo (Fields, 0);
1163 non_public_fields.CopyTo (Fields, CountPublic);
1166 struct_field_hash = new Hashtable ();
1167 field_hash = new Hashtable ();
1170 StructFields = new TypeInfo [Count];
1171 StructInfo[] sinfo = new StructInfo [Count];
1175 for (int i = 0; i < Count; i++) {
1176 FieldInfo field = (FieldInfo) Fields [i];
1178 sinfo [i] = GetStructInfo (field.FieldType);
1179 if (sinfo [i] == null)
1180 field_hash.Add (field.Name, ++Length);
1181 else if (sinfo [i].InTransit) {
1182 Report.Error (523, String.Format (
1183 "Struct member `{0}.{1}' of type `{2}' causes " +
1184 "a cycle in the structure layout",
1185 type, field.Name, sinfo [i].Type));
1193 TotalLength = Length + 1;
1194 for (int i = 0; i < Count; i++) {
1195 FieldInfo field = (FieldInfo) Fields [i];
1197 if (sinfo [i] == null)
1200 field_hash.Add (field.Name, TotalLength);
1202 HasStructFields = true;
1203 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1204 struct_field_hash.Add (field.Name, StructFields [i]);
1205 TotalLength += sinfo [i].TotalLength;
1209 public int this [string name] {
1211 if (field_hash.Contains (name))
1212 return (int) field_hash [name];
1218 public TypeInfo GetStructField (string name)
1220 return (TypeInfo) struct_field_hash [name];
1223 public static StructInfo GetStructInfo (Type type)
1225 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1226 TypeManager.IsBuiltinType (type))
1229 StructInfo info = (StructInfo) field_type_hash [type];
1233 return new StructInfo (type);
1236 public static StructInfo GetStructInfo (TypeContainer tc)
1238 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1242 return new StructInfo (tc.TypeBuilder);
1248 // This is used by the flow analysis code to store information about a single local variable
1249 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1250 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1251 // it has been assigned or not, but for structs, we need this information for each of its fields.
1253 public class VariableInfo {
1254 public readonly string Name;
1255 public readonly TypeInfo TypeInfo;
1258 // The bit offset of this variable in the flow vector.
1260 public readonly int Offset;
1263 // The number of bits this variable needs in the flow vector.
1264 // The first bit always specifies whether the variable as such has been assigned while
1265 // the remaining bits contain this information for each of a struct's fields.
1267 public readonly int Length;
1270 // If this is a parameter of local variable.
1272 public readonly bool IsParameter;
1274 public readonly LocalInfo LocalInfo;
1276 readonly VariableInfo Parent;
1277 VariableInfo[] sub_info;
1279 protected VariableInfo (string name, Type type, int offset)
1282 this.Offset = offset;
1283 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1285 Length = TypeInfo.TotalLength;
1290 protected VariableInfo (VariableInfo parent, TypeInfo type)
1292 this.Name = parent.Name;
1293 this.TypeInfo = type;
1294 this.Offset = parent.Offset + type.Offset;
1295 this.Parent = parent;
1296 this.Length = type.TotalLength;
1298 this.IsParameter = parent.IsParameter;
1299 this.LocalInfo = parent.LocalInfo;
1304 protected void Initialize ()
1306 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1307 if (sub_fields != null) {
1308 sub_info = new VariableInfo [sub_fields.Length];
1309 for (int i = 0; i < sub_fields.Length; i++) {
1310 if (sub_fields [i] != null)
1311 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1314 sub_info = new VariableInfo [0];
1317 public VariableInfo (LocalInfo local_info, int offset)
1318 : this (local_info.Name, local_info.VariableType, offset)
1320 this.LocalInfo = local_info;
1321 this.IsParameter = false;
1324 public VariableInfo (Parameters ip, int i, int offset)
1325 : this (ip.ParameterName (i), TypeManager.GetElementType (ip.ParameterType (i)), offset)
1327 this.IsParameter = true;
1330 public bool IsAssigned (EmitContext ec)
1332 return !ec.DoFlowAnalysis ||
1333 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1334 ec.CurrentBranching.IsAssigned (this);
1337 public bool IsAssigned (EmitContext ec, Location loc)
1339 if (IsAssigned (ec))
1342 Report.Error (165, loc,
1343 "Use of unassigned local variable `" + Name + "'");
1344 ec.CurrentBranching.SetAssigned (this);
1348 public bool IsAssigned (MyBitVector vector)
1353 if (vector [Offset])
1356 // FIXME: Fix SetFieldAssigned to set the whole range like SetAssigned below. Then, get rid of this stanza
1357 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent) {
1358 if (vector [parent.Offset]) {
1359 // 'parent' is assigned, but someone forgot to note that all its components are assigned too
1360 parent.SetAssigned (vector);
1365 // Return unless this is a struct.
1366 if (!TypeInfo.IsStruct)
1369 // Ok, so each field must be assigned.
1370 for (int i = 0; i < TypeInfo.Length; i++) {
1371 if (!vector [Offset + i + 1])
1375 // Ok, now check all fields which are structs.
1376 for (int i = 0; i < sub_info.Length; i++) {
1377 VariableInfo sinfo = sub_info [i];
1381 if (!sinfo.IsAssigned (vector))
1385 vector [Offset] = true;
1389 public void SetAssigned (EmitContext ec)
1391 if (ec.DoFlowAnalysis)
1392 ec.CurrentBranching.SetAssigned (this);
1395 public void SetAssigned (MyBitVector vector)
1398 vector [Offset] = true;
1400 vector.SetRange (Offset, Length);
1403 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1405 if (!ec.DoFlowAnalysis ||
1406 ec.OmitStructFlowAnalysis && TypeInfo.IsStruct ||
1407 ec.CurrentBranching.IsFieldAssigned (this, name))
1410 Report.Error (170, loc,
1411 "Use of possibly unassigned field `" + name + "'");
1412 ec.CurrentBranching.SetFieldAssigned (this, name);
1416 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1418 int field_idx = TypeInfo.GetFieldIndex (field_name);
1423 return vector [Offset + field_idx];
1426 public void SetFieldAssigned (EmitContext ec, string name)
1428 if (ec.DoFlowAnalysis)
1429 ec.CurrentBranching.SetFieldAssigned (this, name);
1432 public void SetFieldAssigned (MyBitVector vector, string field_name)
1434 int field_idx = TypeInfo.GetFieldIndex (field_name);
1439 vector [Offset + field_idx] = true;
1442 public VariableInfo GetSubStruct (string name)
1444 TypeInfo type = TypeInfo.GetSubStruct (name);
1449 return new VariableInfo (this, type);
1452 public override string ToString ()
1454 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1455 Name, TypeInfo, Offset, Length, IsParameter);
1460 // This is a special bit vector which can inherit from another bit vector doing a
1461 // copy-on-write strategy. The inherited vector may have a smaller size than the
1464 public class MyBitVector {
1465 public readonly int Count;
1466 public static readonly MyBitVector Empty = new MyBitVector ();
1468 // Invariant: vector != null => vector.Count == Count
1469 // Invariant: vector == null || shared == null
1470 // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
1471 // The object in 'shared' cannot be modified, while 'vector' can be freely modified
1472 BitArray vector, shared;
1476 shared = new BitArray (0, false);
1479 public MyBitVector (MyBitVector InheritsFrom, int Count)
1481 if (InheritsFrom != null)
1482 shared = InheritsFrom.Shared;
1487 // Use this accessor to get a shareable copy of the underlying BitArray representation
1490 // Post-condition: vector == null
1491 if (shared == null) {
1500 // Get/set bit `index' in the bit vector.
1502 public bool this [int index] {
1505 throw new ArgumentOutOfRangeException ();
1508 return vector [index];
1511 if (index < shared.Count)
1512 return shared [index];
1517 // Only copy the vector if we're actually modifying it.
1518 if (this [index] != value) {
1520 initialize_vector ();
1521 vector [index] = value;
1527 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1528 // different size than the current one.
1530 private MyBitVector Or (MyBitVector new_vector)
1532 if (Count == 0 || new_vector.Count == 0)
1535 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1538 int n = new_vector.Count;
1540 for (int i = 0; i < n; ++i)
1548 if (Count == o.Count) {
1549 if (vector == null) {
1552 initialize_vector ();
1562 for (int i = 0; i < min; i++) {
1571 // Performs an `and' operation on the bit vector. The `new_vector' may have
1572 // a different size than the current one.
1574 private MyBitVector And (MyBitVector new_vector)
1579 BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
1582 for (int i = new_vector.Count; i < Count; ++i)
1592 if (Count == o.Count) {
1593 if (vector == null) {
1594 if (shared == null) {
1595 shared = new_vector.Shared;
1598 initialize_vector ();
1608 for (int i = 0; i < min; i++) {
1613 for (int i = min; i < Count; i++)
1619 public static MyBitVector operator & (MyBitVector a, MyBitVector b)
1627 if (a.Count > b.Count)
1628 return a.Clone ().And (b);
1630 return b.Clone ().And (a);
1633 public static MyBitVector operator | (MyBitVector a, MyBitVector b)
1638 return new MyBitVector (null, b.Count);
1640 return new MyBitVector (null, a.Count);
1641 if (a.Count > b.Count)
1642 return a.Clone ().Or (b);
1644 return b.Clone ().Or (a);
1647 public MyBitVector Clone ()
1649 return Count == 0 ? Empty : new MyBitVector (this, Count);
1652 public void SetRange (int offset, int length)
1654 if (offset > Count || offset + length > Count)
1655 throw new ArgumentOutOfRangeException ();
1657 if (shared == null && vector == null)
1661 if (shared != null) {
1662 if (offset + length <= shared.Count) {
1663 for (; i < length; ++i)
1664 if (!shared [i+offset])
1669 initialize_vector ();
1671 for (; i < length; ++i)
1672 vector [i+offset] = true;
1676 public void SetAll (bool value)
1678 // Don't clobber Empty
1681 shared = value ? null : Empty.Shared;
1685 void initialize_vector ()
1687 // Post-condition: vector != null
1688 if (shared == null) {
1689 vector = new BitArray (Count, true);
1693 vector = new BitArray (shared);
1694 if (Count != vector.Count)
1695 vector.Length = Count;
1699 StringBuilder Dump (StringBuilder sb)
1701 BitArray dump = vector == null ? shared : vector;
1703 return sb.Append ("/");
1706 for (int i = 0; i < dump.Count; i++)
1707 sb.Append (dump [i] ? "1" : "0");
1711 public override string ToString ()
1713 return Dump (new StringBuilder ("{")).Append ("}").ToString ();