2 // flowanalyis.cs: The control flow analysis code
5 // Martin Baulig (martin@ximian.com)
7 // (C) 2001, 2002, 2003 Ximian, Inc.
12 using System.Collections;
13 using System.Reflection;
14 using System.Reflection.Emit;
15 using System.Diagnostics;
20 // A new instance of this class is created every time a new block is resolved
21 // and if there's branching in the block's control flow.
23 public abstract class FlowBranching
26 // The type of a FlowBranching.
28 public enum BranchingType {
29 // Normal (conditional or toplevel) block.
46 // The type of one sibling of a branching.
48 public enum SiblingType {
57 // This is used in the control flow analysis code to specify whether the
58 // current code block may return to its enclosing block before reaching
61 public enum FlowReturns {
64 // It can never return.
67 // This means that the block contains a conditional return statement
71 // The code always returns, ie. there's an unconditional return / break
75 // The code always throws an exception.
78 // The current code block is unreachable. This happens if it's immediately
79 // following a FlowReturns.Always block.
83 public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
86 case BranchingType.Exception:
87 return new FlowBranchingException (parent, type, block, loc);
89 case BranchingType.Switch:
90 return new FlowBranchingBlock (parent, type, SiblingType.SwitchSection, block, loc);
93 return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
98 // The type of this flow branching.
100 public readonly BranchingType Type;
103 // The block this branching is contained in. This may be null if it's not
104 // a top-level block and it doesn't declare any local variables.
106 public readonly Block Block;
109 // The parent of this branching or null if this is the top-block.
111 public readonly FlowBranching Parent;
114 // Start-Location of this flow branching.
116 public readonly Location Location;
119 // If this is an infinite loop.
121 public bool Infinite;
124 // If we may leave the current loop.
126 public bool MayLeaveLoop;
131 VariableMap param_map, local_map;
133 static int next_id = 0;
137 // Performs an `And' operation on the FlowReturns status
138 // (for instance, a block only returns Always if all its siblings
141 public static FlowReturns AndFlowReturns (FlowReturns a, FlowReturns b)
143 if (a == FlowReturns.Undefined)
145 if (b == FlowReturns.Unreachable)
149 case FlowReturns.Never:
150 if (b == FlowReturns.Never)
151 return FlowReturns.Never;
153 return FlowReturns.Sometimes;
155 case FlowReturns.Sometimes:
156 return FlowReturns.Sometimes;
158 case FlowReturns.Always:
159 if ((b == FlowReturns.Always) || (b == FlowReturns.Exception))
160 return FlowReturns.Always;
162 return FlowReturns.Sometimes;
164 case FlowReturns.Exception:
165 if (b == FlowReturns.Exception)
166 return FlowReturns.Exception;
167 else if (b == FlowReturns.Always)
168 return FlowReturns.Always;
170 return FlowReturns.Sometimes;
177 // The vector contains a BitArray with information about which local variables
178 // and parameters are already initialized at the current code position.
180 public class UsageVector {
182 // The type of this branching.
184 public readonly SiblingType Type;
187 // Start location of this branching.
189 public readonly Location Location;
192 // If this is true, then the usage vector has been modified and must be
193 // merged when we're done with this branching.
198 // The number of parameters in this block.
200 public readonly int CountParameters;
203 // The number of locals in this block.
205 public readonly int CountLocals;
208 // If not null, then we inherit our state from this vector and do a
209 // copy-on-write. If null, then we're the first sibling in a top-level
210 // block and inherit from the empty vector.
212 public readonly UsageVector InheritsFrom;
217 MyBitVector locals, parameters;
218 FlowReturns RealReturns, RealBreaks, RealReachable;
221 static int next_id = 0;
225 // Normally, you should not use any of these constructors.
227 public UsageVector (SiblingType type, UsageVector parent, Location loc, int num_params, int num_locals)
231 this.InheritsFrom = parent;
232 this.CountParameters = num_params;
233 this.CountLocals = num_locals;
234 this.RealReturns = FlowReturns.Never;
235 this.RealBreaks = FlowReturns.Never;
236 this.RealReachable = FlowReturns.Always;
238 if (parent != null) {
239 locals = new MyBitVector (parent.locals, CountLocals);
241 parameters = new MyBitVector (parent.parameters, num_params);
242 RealReturns = parent.Returns;
243 RealBreaks = parent.Breaks;
245 locals = new MyBitVector (null, CountLocals);
247 parameters = new MyBitVector (null, num_params);
253 public UsageVector (SiblingType type, UsageVector parent, Location loc)
254 : this (type, parent, loc, parent.CountParameters, parent.CountLocals)
258 // This does a deep copy of the usage vector.
260 public UsageVector Clone ()
262 UsageVector retval = new UsageVector (Type, null, Location, CountParameters, CountLocals);
264 retval.locals = locals.Clone ();
265 if (parameters != null)
266 retval.parameters = parameters.Clone ();
267 retval.RealReturns = RealReturns;
268 retval.RealBreaks = RealBreaks;
269 retval.RealReachable = RealReachable;
274 public bool IsAssigned (VariableInfo var)
276 if (!var.IsParameter && AlwaysBreaks)
279 return var.IsAssigned (var.IsParameter ? parameters : locals);
282 public void SetAssigned (VariableInfo var)
284 if (!var.IsParameter && AlwaysBreaks)
287 var.SetAssigned (var.IsParameter ? parameters : locals);
290 public bool IsFieldAssigned (VariableInfo var, string name)
292 if (!var.IsParameter && AlwaysBreaks)
295 return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
298 public void SetFieldAssigned (VariableInfo var, string name)
300 if (!var.IsParameter && AlwaysBreaks)
303 var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
307 // Specifies when the current block returns.
308 // If this is FlowReturns.Unreachable, then control can never reach the
309 // end of the method (so that we don't need to emit a return statement).
310 // The same applies for FlowReturns.Exception, but in this case the return
311 // value will never be used.
313 public FlowReturns Returns {
320 // Specifies whether control may return to our containing block
321 // before reaching the end of this block. This happens if there
322 // is a break/continue/goto/return in it.
323 // This can also be used to find out whether the statement immediately
324 // following the current block may be reached or not.
326 public FlowReturns Breaks {
332 public FlowReturns Reachable {
334 return RealReachable;
338 public bool AlwaysBreaks {
340 return (Breaks == FlowReturns.Always) ||
341 (Breaks == FlowReturns.Exception) ||
342 (Breaks == FlowReturns.Unreachable);
346 public bool MayBreak {
348 return Breaks != FlowReturns.Never;
352 public bool AlwaysReturns {
354 return (Returns == FlowReturns.Always) ||
355 (Returns == FlowReturns.Exception);
359 public bool MayReturn {
361 return (Returns == FlowReturns.Sometimes) ||
362 (Returns == FlowReturns.Always);
368 RealBreaks = FlowReturns.Always;
371 public void Return ()
373 RealReturns = FlowReturns.Always;
376 public bool IsUnreachable {
378 return (Reachable == FlowReturns.Exception) ||
379 (Reachable == FlowReturns.Unreachable);
383 public void Unreachable ()
385 // If we're already unreachable, don't modify the reason why.
387 RealReachable = FlowReturns.Unreachable;
390 public void NeverReachable ()
392 // If we're already unreachable, don't modify the reason why.
394 RealReachable = FlowReturns.Never;
399 // If we're already unreachable, don't modify the reason why.
401 RealReachable = FlowReturns.Exception;
405 // Merges a child branching.
407 public FlowReturns MergeChild (MyBitVector new_params, MyBitVector new_locals,
408 FlowReturns new_returns, FlowReturns new_breaks,
409 FlowReturns new_reachable)
411 Report.Debug (2, "MERGING CHILD", this, new_params, new_locals, new_returns, new_breaks,
414 RealReturns = new_returns;
415 RealBreaks = new_breaks;
416 RealReachable = new_reachable;
419 // We've now either reached the point after the branching or we will
420 // never get there since we always return or always throw an exception.
422 // If we can reach the point after the branching, mark all locals and
423 // parameters as initialized which have been initialized in all branches
424 // we need to look at (see above).
427 Report.Debug (2, "MERGING CHILD #1", this, Returns, Breaks, Reachable, new_locals, new_params);
429 if ((Reachable == FlowReturns.Always) || (Reachable == FlowReturns.Sometimes) ||
430 (Reachable == FlowReturns.Never)) {
431 if ((Returns == FlowReturns.Always) || (Breaks == FlowReturns.Always))
432 RealReachable = FlowReturns.Never;
433 if ((Type == SiblingType.SwitchSection) && (Reachable != FlowReturns.Never)) {
434 Report.Error (163, Location, "Control cannot fall through from one " +
435 "case label to another");
438 if (new_locals != null)
439 locals.Or (new_locals);
441 if (new_params != null)
442 parameters.Or (new_params);
445 Report.Debug (2, "MERGING CHILD DONE", this);
451 // Tells control flow analysis that the current code position may be reached with
452 // a forward jump from any of the origins listed in `origin_vectors' which is a
453 // list of UsageVectors.
455 // This is used when resolving forward gotos - in the following example, the
456 // variable `a' is uninitialized in line 8 becase this line may be reached via
457 // the goto in line 4:
467 // 8 Console.WriteLine (a);
470 public void MergeJumpOrigins (ICollection origin_vectors)
472 Report.Debug (1, "MERGING JUMP ORIGIN", this);
474 RealBreaks = FlowReturns.Never;
475 RealReturns = FlowReturns.Never;
476 if (Reachable != FlowReturns.Always)
477 RealReachable = FlowReturns.Always;
479 if (origin_vectors == null)
482 foreach (UsageVector vector in origin_vectors) {
483 Report.Debug (1, " MERGING JUMP ORIGIN", vector);
485 locals.And (vector.locals);
486 if (parameters != null)
487 parameters.And (vector.parameters);
488 RealBreaks = AndFlowReturns (RealBreaks, vector.Breaks);
489 RealReturns = AndFlowReturns (RealReturns, vector.Returns);
490 RealReachable = AndFlowReturns (RealReachable, vector.Reachable);
493 Report.Debug (1, "MERGING JUMP ORIGIN DONE", this);
497 // This is used at the beginning of a finally block if there were
498 // any return statements in the try block or one of the catch blocks.
500 public void MergeFinallyOrigins (ICollection finally_vectors)
502 Report.Debug (1, "MERGING FINALLY ORIGIN", this);
504 RealBreaks = FlowReturns.Never;
506 foreach (UsageVector vector in finally_vectors) {
507 Report.Debug (1, " MERGING FINALLY ORIGIN", vector);
509 if (parameters != null)
510 parameters.And (vector.parameters);
511 RealBreaks = AndFlowReturns (Breaks, vector.Breaks);
516 Report.Debug (1, "MERGING FINALLY ORIGIN DONE", this);
519 public void CheckOutParameters (FlowBranching branching)
521 if (parameters != null)
522 branching.CheckOutParameters (parameters, branching.Location);
526 // Performs an `or' operation on the locals and the parameters.
528 public void Or (UsageVector new_vector)
530 locals.Or (new_vector.locals);
531 if (parameters != null)
532 parameters.Or (new_vector.parameters);
536 // Performs an `and' operation on the locals.
538 public void AndLocals (UsageVector new_vector)
540 locals.And (new_vector.locals);
543 public bool HasParameters {
545 return parameters != null;
549 public bool HasLocals {
551 return locals != null;
556 // Returns a deep copy of the parameters.
558 public MyBitVector Parameters {
560 if (parameters != null)
561 return parameters.Clone ();
568 // Returns a deep copy of the locals.
570 public MyBitVector Locals {
572 return locals.Clone ();
576 public MyBitVector ParameterVector {
582 public MyBitVector LocalVector {
592 public override string ToString ()
594 StringBuilder sb = new StringBuilder ();
596 sb.Append ("Vector (");
603 sb.Append (Reachable);
604 if (parameters != null) {
606 sb.Append (parameters);
612 return sb.ToString ();
617 // Creates a new flow branching which is contained in `parent'.
618 // You should only pass non-null for the `block' argument if this block
619 // introduces any new variables - in this case, we need to create a new
620 // usage vector with a different size than our parent's one.
622 protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
623 Block block, Location loc)
633 param_map = Block.ParameterMap;
634 local_map = Block.LocalMap;
636 UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
637 vector = new UsageVector (stype, parent_vector, loc, param_map.Length, local_map.Length);
639 param_map = Parent.param_map;
640 local_map = Parent.local_map;
641 vector = new UsageVector (stype, Parent.CurrentUsageVector, loc);
647 public abstract UsageVector CurrentUsageVector {
652 // Creates a sibling of the current usage vector.
654 public virtual void CreateSibling (SiblingType type)
656 AddSibling (new UsageVector (type, Parent.CurrentUsageVector, Location));
658 Report.Debug (1, "CREATED SIBLING", CurrentUsageVector);
661 protected abstract void AddSibling (UsageVector uv);
663 public abstract void Break ();
664 public abstract void Return ();
665 public abstract void Goto ();
666 public abstract void Throw ();
667 public abstract void Label (ArrayList origin_vectors);
670 // Check whether all `out' parameters have been assigned.
672 public void CheckOutParameters (MyBitVector parameters, Location loc)
674 for (int i = 0; i < param_map.Count; i++) {
675 VariableInfo var = param_map [i];
680 if (var.IsAssigned (parameters))
683 Report.Error (177, loc, "The out parameter `" +
684 param_map.VariableNames [i] + "' must be " +
685 "assigned before control leave the current method.");
689 protected class MergeResult
691 public MyBitVector Parameters;
692 public MyBitVector Locals;
693 public FlowReturns Returns;
694 public FlowReturns Breaks;
695 public FlowReturns Reachable;
696 public bool MayLeaveLoop;
698 public MergeResult (MyBitVector parameters, MyBitVector locals, FlowReturns returns, FlowReturns breaks,
699 FlowReturns reachable, bool may_leave_loop)
701 this.Parameters = parameters;
702 this.Locals = locals;
703 this.Returns = returns;
704 this.Breaks = breaks;
705 this.Reachable = reachable;
706 this.MayLeaveLoop = may_leave_loop;
710 protected MergeResult Merge (ArrayList children)
712 MyBitVector locals = null;
713 MyBitVector parameters = null;
715 FlowReturns returns = FlowReturns.Undefined;
716 FlowReturns breaks = FlowReturns.Undefined;
717 FlowReturns reachable = FlowReturns.Undefined;
719 Report.Debug (2, "MERGING CHILDREN", this, Type, children.Count);
721 foreach (UsageVector child in children) {
722 Report.Debug (2, " MERGING CHILD", child, child.AlwaysBreaks, child.AlwaysReturns,
723 child.IsUnreachable, child.Locals, child.Parameters,
724 child.Returns, child.Breaks, child.Reachable);
726 reachable = AndFlowReturns (reachable, child.Reachable);
728 // Ignore unreachable children.
729 if (child.IsUnreachable)
732 returns = AndFlowReturns (returns, child.Returns);
733 breaks = AndFlowReturns (breaks, child.Breaks);
735 // A local variable is initialized after a flow branching if it
736 // has been initialized in all its branches which do neither
737 // always return or always throw an exception.
739 // If a branch may return, but does not always return, then we
740 // can treat it like a never-returning branch here: control will
741 // only reach the code position after the branching if we did not
744 // It's important to distinguish between always and sometimes
745 // returning branches here:
748 // 2 if (something) {
752 // 6 Console.WriteLine (a);
754 // The if block in lines 3-4 always returns, so we must not look
755 // at the initialization of `a' in line 4 - thus it'll still be
756 // uninitialized in line 6.
758 // On the other hand, the following is allowed:
765 // 6 Console.WriteLine (a);
767 // Here, `a' is initialized in line 3 and we must not look at
768 // line 5 since it always returns.
770 if (!child.AlwaysReturns && !child.AlwaysBreaks)
771 MyBitVector.And (ref locals, child.LocalVector);
773 // An `out' parameter must be assigned in all branches which do
774 // not always throw an exception.
775 if ((child.Type != SiblingType.Catch) &&
776 (child.ParameterVector != null) && (child.Breaks != FlowReturns.Exception))
777 MyBitVector.And (ref parameters, child.ParameterVector);
780 Report.Debug (2, "MERGING CHILDREN DONE", Type, parameters, locals, returns, breaks, reachable,
781 Infinite, MayLeaveLoop, this);
783 if (Infinite && !MayLeaveLoop) {
784 Report.Debug (1, "INFINITE", returns, breaks, this);
786 if (returns == FlowReturns.Never) {
787 // We're actually infinite.
788 breaks = FlowReturns.Unreachable;
789 returns = FlowReturns.Unreachable;
790 } else if ((returns == FlowReturns.Sometimes) || (returns == FlowReturns.Always)) {
791 // If we're an infinite loop and do not break, the code after
792 // the loop can never be reached. However, if we may return
793 // from the loop, then we do always return (or stay in the loop
795 returns = FlowReturns.Always;
799 if (returns == FlowReturns.Undefined)
800 returns = FlowReturns.Never;
801 if (breaks == FlowReturns.Undefined)
802 breaks = FlowReturns.Never;
804 return new MergeResult (parameters, locals, returns, breaks, reachable, MayLeaveLoop);
807 protected abstract MergeResult Merge ();
810 // Merge a child branching.
812 public FlowReturns MergeChild (FlowBranching child)
814 MergeResult result = child.Merge ();
816 CurrentUsageVector.MergeChild (
817 result.Parameters, result.Locals, result.Returns, result.Breaks, result.Reachable);
819 if ((child.Type != BranchingType.LoopBlock) && (child.Type != BranchingType.SwitchSection))
820 MayLeaveLoop |= child.MayLeaveLoop;
822 if (result.Reachable == FlowReturns.Exception)
823 return FlowReturns.Exception;
825 return result.Returns;
829 // Does the toplevel merging.
831 public FlowReturns MergeTopBlock ()
833 if ((Type != BranchingType.Block) || (Block == null))
834 throw new NotSupportedException ();
836 UsageVector vector = new UsageVector (
837 SiblingType.Conditional, null, Location, param_map.Length, local_map.Length);
839 MergeResult result = Merge ();
840 vector.MergeChild (result.Parameters, result.Locals, result.Returns, result.Breaks, result.Reachable);
842 if (vector.Reachable != FlowReturns.Exception)
843 CheckOutParameters (vector.Parameters, Location);
845 return FlowReturns.Exception;
847 return result.Returns;
850 public virtual bool InTryBlock ()
853 return Parent.InTryBlock ();
858 public virtual void AddFinallyVector (UsageVector vector)
861 Parent.AddFinallyVector (vector);
863 throw new NotSupportedException ();
866 public bool IsAssigned (VariableInfo vi)
868 return CurrentUsageVector.IsAssigned (vi);
871 public bool IsFieldAssigned (VariableInfo vi, string field_name)
873 if (CurrentUsageVector.IsAssigned (vi))
876 return CurrentUsageVector.IsFieldAssigned (vi, field_name);
879 public void SetAssigned (VariableInfo vi)
881 CurrentUsageVector.SetAssigned (vi);
884 public void SetFieldAssigned (VariableInfo vi, string name)
886 CurrentUsageVector.SetFieldAssigned (vi, name);
889 public override string ToString ()
891 StringBuilder sb = new StringBuilder ();
892 sb.Append (GetType ());
900 sb.Append (Block.ID);
902 sb.Append (Block.StartLocation);
905 // sb.Append (Siblings.Length);
906 // sb.Append (" - ");
907 sb.Append (CurrentUsageVector);
909 return sb.ToString ();
913 public class FlowBranchingBlock : FlowBranching
915 UsageVector current_vector;
916 ArrayList siblings = new ArrayList ();
918 public FlowBranchingBlock (FlowBranching parent, BranchingType type, SiblingType stype,
919 Block block, Location loc)
920 : base (parent, type, stype, block, loc)
923 public override UsageVector CurrentUsageVector {
924 get { return current_vector; }
927 protected override void AddSibling (UsageVector sibling)
929 siblings.Add (sibling);
930 current_vector = sibling;
933 public override void Break ()
935 if (Type == BranchingType.SwitchSection)
936 CurrentUsageVector.NeverReachable ();
938 if (Type == BranchingType.LoopBlock)
940 CurrentUsageVector.Break ();
944 public override void Return ()
946 CurrentUsageVector.Return ();
949 public override void Goto ()
951 CurrentUsageVector.Unreachable ();
954 public override void Throw ()
956 CurrentUsageVector.Throw ();
959 public override void Label (ArrayList origin_vectors)
961 CurrentUsageVector.MergeJumpOrigins (origin_vectors);
964 protected override MergeResult Merge ()
966 MergeResult result = Merge (siblings);
967 if (Type == BranchingType.LoopBlock)
968 result.MayLeaveLoop = false;
973 public class FlowBranchingException : FlowBranching
975 ArrayList finally_vectors;
978 UsageVector current_vector;
979 UsageVector try_vector;
980 ArrayList catch_vectors = new ArrayList ();
981 UsageVector finally_vector;
983 public FlowBranchingException (FlowBranching parent, BranchingType type, Block block, Location loc)
984 : base (parent, type, SiblingType.Try, block, loc)
986 finally_vectors = new ArrayList ();
987 has_params = current_vector.HasParameters;
990 protected override void AddSibling (UsageVector sibling)
992 if (sibling.Type == SiblingType.Try) {
993 try_vector = sibling;
994 catch_vectors.Add (sibling);
995 } else if (sibling.Type == SiblingType.Catch)
996 catch_vectors.Add (sibling);
997 else if (sibling.Type == SiblingType.Finally) {
998 // sibling.MergeFinallyOrigins (finally_vectors);
999 finally_vector = sibling;
1001 throw new InvalidOperationException ();
1003 current_vector = sibling;
1006 public override UsageVector CurrentUsageVector {
1007 get { return current_vector; }
1010 public override bool InTryBlock ()
1015 public override void AddFinallyVector (UsageVector vector)
1017 finally_vectors.Add (vector.Clone ());
1020 public override void Break ()
1022 CurrentUsageVector.Break ();
1025 public override void Return ()
1027 CurrentUsageVector.Return ();
1030 public override void Goto ()
1032 CurrentUsageVector.Unreachable ();
1035 public override void Throw ()
1037 CurrentUsageVector.Throw ();
1040 public override void Label (ArrayList origin_vectors)
1042 CurrentUsageVector.MergeJumpOrigins (origin_vectors);
1045 protected void MergeFinally (MyBitVector f_params, ref MergeResult result)
1047 foreach (UsageVector vector in finally_vectors) {
1048 MyBitVector temp_params = f_params.Clone ();
1049 temp_params.Or (vector.Parameters);
1051 CheckOutParameters (temp_params, Location);
1055 protected override MergeResult Merge ()
1057 MergeResult result = Merge (catch_vectors);
1060 if (finally_vector != null) {
1061 MergeFinally (finally_vector.Parameters, ref result);
1062 MyBitVector.Or (ref result.Parameters, finally_vector.ParameterVector);
1064 MergeFinally (result.Parameters, ref result);
1067 if (finally_vector != null)
1068 MyBitVector.Or (ref result.Locals, finally_vector.LocalVector);
1075 // This is used by the flow analysis code to keep track of the type of local variables
1078 // The flow code uses a BitVector to keep track of whether a variable has been assigned
1079 // or not. This is easy for fundamental types (int, char etc.) or reference types since
1080 // you can only assign the whole variable as such.
1082 // For structs, we also need to keep track of all its fields. To do this, we allocate one
1083 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
1084 // one bit for each of its fields.
1086 // This class computes this `layout' for each type.
1088 public class TypeInfo
1090 public readonly Type Type;
1093 // Total number of bits a variable of this type consumes in the flow vector.
1095 public readonly int TotalLength;
1098 // Number of bits the simple fields of a variable of this type consume
1099 // in the flow vector.
1101 public readonly int Length;
1104 // This is only used by sub-structs.
1106 public readonly int Offset;
1109 // If this is a struct.
1111 public readonly bool IsStruct;
1114 // If this is a struct, all fields which are structs theirselves.
1116 public TypeInfo[] SubStructInfo;
1118 protected readonly StructInfo struct_info;
1119 private static Hashtable type_hash = new Hashtable ();
1121 public static TypeInfo GetTypeInfo (Type type)
1123 TypeInfo info = (TypeInfo) type_hash [type];
1127 info = new TypeInfo (type);
1128 type_hash.Add (type, info);
1132 public static TypeInfo GetTypeInfo (TypeContainer tc)
1134 TypeInfo info = (TypeInfo) type_hash [tc.TypeBuilder];
1138 info = new TypeInfo (tc);
1139 type_hash.Add (tc.TypeBuilder, info);
1143 private TypeInfo (Type type)
1147 struct_info = StructInfo.GetStructInfo (type);
1148 if (struct_info != null) {
1149 Length = struct_info.Length;
1150 TotalLength = struct_info.TotalLength;
1151 SubStructInfo = struct_info.StructFields;
1160 private TypeInfo (TypeContainer tc)
1162 this.Type = tc.TypeBuilder;
1164 struct_info = StructInfo.GetStructInfo (tc);
1165 if (struct_info != null) {
1166 Length = struct_info.Length;
1167 TotalLength = struct_info.TotalLength;
1168 SubStructInfo = struct_info.StructFields;
1177 protected TypeInfo (StructInfo struct_info, int offset)
1179 this.struct_info = struct_info;
1180 this.Offset = offset;
1181 this.Length = struct_info.Length;
1182 this.TotalLength = struct_info.TotalLength;
1183 this.SubStructInfo = struct_info.StructFields;
1184 this.Type = struct_info.Type;
1185 this.IsStruct = true;
1188 public int GetFieldIndex (string name)
1190 if (struct_info == null)
1193 return struct_info [name];
1196 public TypeInfo GetSubStruct (string name)
1198 if (struct_info == null)
1201 return struct_info.GetStructField (name);
1205 // A struct's constructor must always assign all fields.
1206 // This method checks whether it actually does so.
1208 public bool IsFullyInitialized (FlowBranching branching, VariableInfo vi, Location loc)
1210 if (struct_info == null)
1214 for (int i = 0; i < struct_info.Count; i++) {
1215 FieldInfo field = struct_info.Fields [i];
1217 if (!branching.IsFieldAssigned (vi, field.Name)) {
1218 Report.Error (171, loc,
1219 "Field `" + TypeManager.CSharpName (Type) +
1220 "." + field.Name + "' must be fully initialized " +
1221 "before control leaves the constructor");
1229 public override string ToString ()
1231 return String.Format ("TypeInfo ({0}:{1}:{2}:{3})",
1232 Type, Offset, Length, TotalLength);
1235 protected class StructInfo {
1236 public readonly Type Type;
1237 public readonly FieldInfo[] Fields;
1238 public readonly TypeInfo[] StructFields;
1239 public readonly int Count;
1240 public readonly int CountPublic;
1241 public readonly int CountNonPublic;
1242 public readonly int Length;
1243 public readonly int TotalLength;
1244 public readonly bool HasStructFields;
1246 private static Hashtable field_type_hash = new Hashtable ();
1247 private Hashtable struct_field_hash;
1248 private Hashtable field_hash;
1250 protected bool InTransit = false;
1252 // Private constructor. To save memory usage, we only need to create one instance
1253 // of this class per struct type.
1254 private StructInfo (Type type)
1258 field_type_hash.Add (type, this);
1260 if (type is TypeBuilder) {
1261 TypeContainer tc = TypeManager.LookupTypeContainer (type);
1263 ArrayList fields = tc.Fields;
1265 ArrayList public_fields = new ArrayList ();
1266 ArrayList non_public_fields = new ArrayList ();
1268 if (fields != null) {
1269 foreach (Field field in fields) {
1270 if ((field.ModFlags & Modifiers.STATIC) != 0)
1272 if ((field.ModFlags & Modifiers.PUBLIC) != 0)
1273 public_fields.Add (field.FieldBuilder);
1275 non_public_fields.Add (field.FieldBuilder);
1279 CountPublic = public_fields.Count;
1280 CountNonPublic = non_public_fields.Count;
1281 Count = CountPublic + CountNonPublic;
1283 Fields = new FieldInfo [Count];
1284 public_fields.CopyTo (Fields, 0);
1285 non_public_fields.CopyTo (Fields, CountPublic);
1287 FieldInfo[] public_fields = type.GetFields (
1288 BindingFlags.Instance|BindingFlags.Public);
1289 FieldInfo[] non_public_fields = type.GetFields (
1290 BindingFlags.Instance|BindingFlags.NonPublic);
1292 CountPublic = public_fields.Length;
1293 CountNonPublic = non_public_fields.Length;
1294 Count = CountPublic + CountNonPublic;
1296 Fields = new FieldInfo [Count];
1297 public_fields.CopyTo (Fields, 0);
1298 non_public_fields.CopyTo (Fields, CountPublic);
1301 struct_field_hash = new Hashtable ();
1302 field_hash = new Hashtable ();
1305 StructFields = new TypeInfo [Count];
1306 StructInfo[] sinfo = new StructInfo [Count];
1310 for (int i = 0; i < Count; i++) {
1311 FieldInfo field = (FieldInfo) Fields [i];
1313 sinfo [i] = GetStructInfo (field.FieldType);
1314 if (sinfo [i] == null)
1315 field_hash.Add (field.Name, ++Length);
1316 else if (sinfo [i].InTransit) {
1317 Report.Error (523, String.Format (
1318 "Struct member '{0}.{1}' of type '{2}' causes " +
1319 "a cycle in the structure layout",
1320 type, field.Name, sinfo [i].Type));
1328 TotalLength = Length + 1;
1329 for (int i = 0; i < Count; i++) {
1330 FieldInfo field = (FieldInfo) Fields [i];
1332 if (sinfo [i] == null)
1335 field_hash.Add (field.Name, TotalLength);
1337 HasStructFields = true;
1338 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
1339 struct_field_hash.Add (field.Name, StructFields [i]);
1340 TotalLength += sinfo [i].TotalLength;
1344 public int this [string name] {
1346 if (field_hash.Contains (name))
1347 return (int) field_hash [name];
1353 public TypeInfo GetStructField (string name)
1355 return (TypeInfo) struct_field_hash [name];
1358 public static StructInfo GetStructInfo (Type type)
1360 if (!TypeManager.IsValueType (type) || TypeManager.IsEnumType (type) ||
1361 TypeManager.IsBuiltinType (type))
1364 StructInfo info = (StructInfo) field_type_hash [type];
1368 return new StructInfo (type);
1371 public static StructInfo GetStructInfo (TypeContainer tc)
1373 StructInfo info = (StructInfo) field_type_hash [tc.TypeBuilder];
1377 return new StructInfo (tc.TypeBuilder);
1383 // This is used by the flow analysis code to store information about a single local variable
1384 // or parameter. Depending on the variable's type, we need to allocate one or more elements
1385 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
1386 // it has been assigned or not, but for structs, we need this information for each of its fields.
1388 public class VariableInfo {
1389 public readonly string Name;
1390 public readonly TypeInfo TypeInfo;
1393 // The bit offset of this variable in the flow vector.
1395 public readonly int Offset;
1398 // The number of bits this variable needs in the flow vector.
1399 // The first bit always specifies whether the variable as such has been assigned while
1400 // the remaining bits contain this information for each of a struct's fields.
1402 public readonly int Length;
1405 // If this is a parameter of local variable.
1407 public readonly bool IsParameter;
1409 public readonly LocalInfo LocalInfo;
1410 public readonly int ParameterIndex;
1412 readonly VariableInfo Parent;
1413 VariableInfo[] sub_info;
1415 protected VariableInfo (string name, Type type, int offset)
1418 this.Offset = offset;
1419 this.TypeInfo = TypeInfo.GetTypeInfo (type);
1421 Length = TypeInfo.TotalLength;
1426 protected VariableInfo (VariableInfo parent, TypeInfo type)
1428 this.Name = parent.Name;
1429 this.TypeInfo = type;
1430 this.Offset = parent.Offset + type.Offset;
1431 this.Parent = parent;
1432 this.Length = type.TotalLength;
1434 this.IsParameter = parent.IsParameter;
1435 this.LocalInfo = parent.LocalInfo;
1436 this.ParameterIndex = parent.ParameterIndex;
1441 protected void Initialize ()
1443 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
1444 if (sub_fields != null) {
1445 sub_info = new VariableInfo [sub_fields.Length];
1446 for (int i = 0; i < sub_fields.Length; i++) {
1447 if (sub_fields [i] != null)
1448 sub_info [i] = new VariableInfo (this, sub_fields [i]);
1451 sub_info = new VariableInfo [0];
1454 public VariableInfo (LocalInfo local_info, int offset)
1455 : this (local_info.Name, local_info.VariableType, offset)
1457 this.LocalInfo = local_info;
1458 this.IsParameter = false;
1461 public VariableInfo (string name, Type type, int param_idx, int offset)
1462 : this (name, type, offset)
1464 this.ParameterIndex = param_idx;
1465 this.IsParameter = true;
1468 public bool IsAssigned (EmitContext ec)
1470 return !ec.DoFlowAnalysis || ec.CurrentBranching.IsAssigned (this);
1473 public bool IsAssigned (EmitContext ec, Location loc)
1475 if (IsAssigned (ec))
1478 Report.Error (165, loc,
1479 "Use of unassigned local variable `" + Name + "'");
1480 ec.CurrentBranching.SetAssigned (this);
1484 public bool IsAssigned (MyBitVector vector)
1486 if (vector [Offset])
1489 for (VariableInfo parent = Parent; parent != null; parent = parent.Parent)
1490 if (vector [parent.Offset])
1493 // Return unless this is a struct.
1494 if (!TypeInfo.IsStruct)
1497 // Ok, so each field must be assigned.
1498 for (int i = 0; i < TypeInfo.Length; i++) {
1499 if (!vector [Offset + i + 1])
1503 // Ok, now check all fields which are structs.
1504 for (int i = 0; i < sub_info.Length; i++) {
1505 VariableInfo sinfo = sub_info [i];
1509 if (!sinfo.IsAssigned (vector))
1513 vector [Offset] = true;
1517 public void SetAssigned (EmitContext ec)
1519 if (ec.DoFlowAnalysis)
1520 ec.CurrentBranching.SetAssigned (this);
1523 public void SetAssigned (MyBitVector vector)
1525 vector [Offset] = true;
1528 public bool IsFieldAssigned (EmitContext ec, string name, Location loc)
1530 if (!ec.DoFlowAnalysis || ec.CurrentBranching.IsFieldAssigned (this, name))
1533 Report.Error (170, loc,
1534 "Use of possibly unassigned field `" + name + "'");
1535 ec.CurrentBranching.SetFieldAssigned (this, name);
1539 public bool IsFieldAssigned (MyBitVector vector, string field_name)
1541 int field_idx = TypeInfo.GetFieldIndex (field_name);
1546 return vector [Offset + field_idx];
1549 public void SetFieldAssigned (EmitContext ec, string name)
1551 if (ec.DoFlowAnalysis)
1552 ec.CurrentBranching.SetFieldAssigned (this, name);
1555 public void SetFieldAssigned (MyBitVector vector, string field_name)
1557 int field_idx = TypeInfo.GetFieldIndex (field_name);
1562 vector [Offset + field_idx] = true;
1565 public VariableInfo GetSubStruct (string name)
1567 TypeInfo type = TypeInfo.GetSubStruct (name);
1572 return new VariableInfo (this, type);
1575 public override string ToString ()
1577 return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
1578 Name, TypeInfo, Offset, Length, IsParameter);
1583 // This is used by the flow code to hold the `layout' of the flow vector for
1584 // all locals and all parameters (ie. we create one instance of this class for the
1585 // locals and another one for the params).
1587 public class VariableMap {
1589 // The number of variables in the map.
1591 public readonly int Count;
1594 // Total length of the flow vector for this map.
1596 public readonly int Length;
1599 // Type and name of all the variables.
1600 // Note that this is null for variables for which we do not need to compute
1603 public readonly Type[] VariableTypes;
1604 public readonly string[] VariableNames;
1608 public VariableMap (InternalParameters ip)
1610 Count = ip != null ? ip.Count : 0;
1611 map = new VariableInfo [Count];
1612 VariableNames = new string [Count];
1613 VariableTypes = new Type [Count];
1616 for (int i = 0; i < Count; i++) {
1617 Parameter.Modifier mod = ip.ParameterModifier (i);
1619 if ((mod & Parameter.Modifier.OUT) == 0)
1622 VariableNames [i] = ip.ParameterName (i);
1623 VariableTypes [i] = TypeManager.GetElementType (ip.ParameterType (i));
1625 map [i] = new VariableInfo (VariableNames [i], VariableTypes [i], i, Length);
1626 Length += map [i].Length;
1630 public VariableMap (LocalInfo[] locals)
1631 : this (null, locals)
1634 public VariableMap (VariableMap parent, LocalInfo[] locals)
1636 int offset = 0, start = 0;
1637 if (parent != null) {
1638 offset = parent.Length;
1639 start = parent.Count;
1642 Count = locals.Length + start;
1643 map = new VariableInfo [Count];
1644 VariableNames = new string [Count];
1645 VariableTypes = new Type [Count];
1648 if (parent != null) {
1649 parent.map.CopyTo (map, 0);
1650 parent.VariableNames.CopyTo (VariableNames, 0);
1651 parent.VariableTypes.CopyTo (VariableTypes, 0);
1654 for (int i = start; i < Count; i++) {
1655 LocalInfo li = locals [i-start];
1657 if (li.VariableType == null)
1660 VariableNames [i] = li.Name;
1661 VariableTypes [i] = li.VariableType;
1663 map [i] = li.VariableInfo = new VariableInfo (li, Length);
1664 Length += map [i].Length;
1669 // Returns the VariableInfo for variable @index or null if we don't need to
1670 // compute assignment info for this variable.
1672 public VariableInfo this [int index] {
1678 public override string ToString ()
1680 return String.Format ("VariableMap ({0}:{1})", Count, Length);
1685 // This is a special bit vector which can inherit from another bit vector doing a
1686 // copy-on-write strategy. The inherited vector may have a smaller size than the
1689 public class MyBitVector {
1690 public readonly int Count;
1691 public readonly MyBitVector InheritsFrom;
1696 public MyBitVector (int Count)
1697 : this (null, Count)
1700 public MyBitVector (MyBitVector InheritsFrom, int Count)
1702 this.InheritsFrom = InheritsFrom;
1707 // Checks whether this bit vector has been modified. After setting this to true,
1708 // we won't use the inherited vector anymore, but our own copy of it.
1710 public bool IsDirty {
1717 initialize_vector ();
1722 // Get/set bit `index' in the bit vector.
1724 public bool this [int index]
1728 throw new ArgumentOutOfRangeException ();
1730 // We're doing a "copy-on-write" strategy here; as long
1731 // as nobody writes to the array, we can use our parent's
1732 // copy instead of duplicating the vector.
1735 return vector [index];
1736 else if (InheritsFrom != null) {
1737 BitArray inherited = InheritsFrom.Vector;
1739 if (index < inherited.Count)
1740 return inherited [index];
1749 throw new ArgumentOutOfRangeException ();
1751 // Only copy the vector if we're actually modifying it.
1753 if (this [index] != value) {
1754 initialize_vector ();
1756 vector [index] = value;
1762 // If you explicitly convert the MyBitVector to a BitArray, you will get a deep
1763 // copy of the bit vector.
1765 public static explicit operator BitArray (MyBitVector vector)
1767 vector.initialize_vector ();
1768 return vector.Vector;
1772 // Performs an `or' operation on the bit vector. The `new_vector' may have a
1773 // different size than the current one.
1775 public void Or (MyBitVector new_vector)
1777 BitArray new_array = new_vector.Vector;
1779 initialize_vector ();
1782 if (vector.Count < new_array.Count)
1783 upper = vector.Count;
1785 upper = new_array.Count;
1787 for (int i = 0; i < upper; i++)
1788 vector [i] = vector [i] | new_array [i];
1792 // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
1793 // a different size than the current one.
1795 public void And (MyBitVector new_vector)
1797 BitArray new_array = new_vector.Vector;
1799 initialize_vector ();
1802 if (vector.Count < new_array.Count)
1803 lower = upper = vector.Count;
1805 lower = new_array.Count;
1806 upper = vector.Count;
1809 for (int i = 0; i < lower; i++)
1810 vector [i] = vector [i] & new_array [i];
1812 for (int i = lower; i < upper; i++)
1816 public static void And (ref MyBitVector target, MyBitVector vector)
1819 target.And (vector);
1821 target = vector.Clone ();
1824 public static void Or (ref MyBitVector target, MyBitVector vector)
1829 target = vector.Clone ();
1833 // This does a deep copy of the bit vector.
1835 public MyBitVector Clone ()
1837 MyBitVector retval = new MyBitVector (Count);
1839 retval.Vector = Vector;
1848 else if (!is_dirty && (InheritsFrom != null))
1849 return InheritsFrom.Vector;
1851 initialize_vector ();
1857 initialize_vector ();
1859 for (int i = 0; i < System.Math.Min (vector.Count, value.Count); i++)
1860 vector [i] = value [i];
1864 void initialize_vector ()
1869 vector = new BitArray (Count, false);
1870 if (InheritsFrom != null)
1871 Vector = InheritsFrom.Vector;
1876 public override string ToString ()
1878 StringBuilder sb = new StringBuilder ("MyBitVector (");
1880 BitArray vector = Vector;
1884 sb.Append ("INHERITED - ");
1885 for (int i = 0; i < vector.Count; i++) {
1888 sb.Append (vector [i]);
1892 return sb.ToString ();