2 // flowanalyis.cs: The control flow analysis code
5 // Martin Baulig (martin@ximian.com)
6 // Raja R Harinath (rharinath@novell.com)
7 // Marek Safar (marek.safar@gmail.com)
9 // Copyright 2001, 2002, 2003 Ximian, Inc.
10 // Copyright 2003-2008 Novell, Inc.
11 // Copyright 2011 Xamarin, Inc.
16 using System.Collections.Generic;
21 // This is used by the flow analysis code to keep track of the type of local variables.
23 // The flow code uses a BitVector to keep track of whether a variable has been assigned
24 // or not. This is easy for fundamental types (int, char etc.) or reference types since
25 // you can only assign the whole variable as such.
27 // For structs, we also need to keep track of all its fields. To do this, we allocate one
28 // bit for the struct itself (it's used if you assign/access the whole struct) followed by
29 // one bit for each of its fields.
31 // This class computes this `layout' for each type.
36 // Total number of bits a variable of this type consumes in the flow vector.
38 public readonly int TotalLength;
41 // Number of bits the simple fields of a variable of this type consume
42 // in the flow vector.
44 public readonly int Length;
47 // This is only used by sub-structs.
49 public readonly int Offset;
52 // If this is a struct.
54 public readonly bool IsStruct;
57 // If this is a struct, all fields which are structs theirselves.
59 public TypeInfo[] SubStructInfo;
61 readonly StructInfo struct_info;
62 private static Dictionary<TypeSpec, TypeInfo> type_hash;
64 static readonly TypeInfo simple_type = new TypeInfo (1);
71 public static void Reset ()
73 type_hash = new Dictionary<TypeSpec, TypeInfo> ();
74 StructInfo.field_type_hash = new Dictionary<TypeSpec, StructInfo> ();
77 TypeInfo (int totalLength)
79 this.TotalLength = totalLength;
82 TypeInfo (StructInfo struct_info, int offset)
84 this.struct_info = struct_info;
86 this.Length = struct_info.Length;
87 this.TotalLength = struct_info.TotalLength;
88 this.SubStructInfo = struct_info.StructFields;
92 public int GetFieldIndex (string name)
94 if (struct_info == null)
97 return struct_info [name];
100 public TypeInfo GetStructField (string name)
102 if (struct_info == null)
105 return struct_info.GetStructField (name);
108 public static TypeInfo GetTypeInfo (TypeSpec type, IMemberContext context)
114 if (type_hash.TryGetValue (type, out info))
117 var struct_info = StructInfo.GetStructInfo (type, context);
118 if (struct_info != null) {
119 info = new TypeInfo (struct_info, 0);
124 type_hash.Add (type, info);
129 // A struct's constructor must always assign all fields.
130 // This method checks whether it actually does so.
132 public bool IsFullyInitialized (FlowAnalysisContext fc, VariableInfo vi, Location loc)
134 if (struct_info == null)
138 for (int i = 0; i < struct_info.Count; i++) {
139 var field = struct_info.Fields[i];
141 if (!fc.IsStructFieldDefinitelyAssigned (vi, field.Name)) {
142 var bf = field.MemberDefinition as Property.BackingFieldDeclaration;
144 if (bf.Initializer != null)
147 fc.Report.Error (843, loc,
148 "An automatically implemented property `{0}' must be fully assigned before control leaves the constructor. Consider calling the default struct contructor from a constructor initializer",
149 field.GetSignatureForError ());
155 fc.Report.Error (171, loc,
156 "Field `{0}' must be fully assigned before control leaves the constructor",
157 field.GetSignatureForError ());
165 public override string ToString ()
167 return String.Format ("TypeInfo ({0}:{1}:{2})",
168 Offset, Length, TotalLength);
173 readonly List<FieldSpec> fields;
174 public readonly TypeInfo[] StructFields;
175 public readonly int Length;
176 public readonly int TotalLength;
178 public static Dictionary<TypeSpec, StructInfo> field_type_hash;
179 private Dictionary<string, TypeInfo> struct_field_hash;
180 private Dictionary<string, int> field_hash;
185 // We only need one instance per type
187 StructInfo (TypeSpec type, IMemberContext context)
189 field_type_hash.Add (type, this);
191 fields = MemberCache.GetAllFieldsForDefiniteAssignment (type, context);
193 struct_field_hash = new Dictionary<string, TypeInfo> ();
194 field_hash = new Dictionary<string, int> (fields.Count);
196 StructFields = new TypeInfo[fields.Count];
197 StructInfo[] sinfo = new StructInfo[fields.Count];
201 for (int i = 0; i < fields.Count; i++) {
202 var field = fields [i];
204 if (field.MemberType.IsStruct)
205 sinfo [i] = GetStructInfo (field.MemberType, context);
207 if (sinfo [i] == null)
208 field_hash.Add (field.Name, ++Length);
209 else if (sinfo [i].InTransit) {
217 TotalLength = Length + 1;
218 for (int i = 0; i < fields.Count; i++) {
219 var field = fields [i];
221 if (sinfo [i] == null)
224 field_hash.Add (field.Name, TotalLength);
226 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
227 struct_field_hash.Add (field.Name, StructFields [i]);
228 TotalLength += sinfo [i].TotalLength;
238 public List<FieldSpec> Fields {
244 public int this [string name] {
247 if (!field_hash.TryGetValue (name, out val))
254 public TypeInfo GetStructField (string name)
257 if (struct_field_hash.TryGetValue (name, out ti))
263 public static StructInfo GetStructInfo (TypeSpec type, IMemberContext context)
265 if (type.BuiltinType > 0)
269 if (field_type_hash.TryGetValue (type, out info))
272 return new StructInfo (type, context);
278 // This is used by definite assignment analysis code to store information about a local variable
279 // or parameter. Depending on the variable's type, we need to allocate one or more elements
280 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
281 // it has been assigned or not, but for structs, we need this information for each of its fields.
283 public class VariableInfo
285 readonly string Name;
287 readonly TypeInfo TypeInfo;
290 // The bit offset of this variable in the flow vector.
295 // The number of bits this variable needs in the flow vector.
296 // The first bit always specifies whether the variable as such has been assigned while
297 // the remaining bits contain this information for each of a struct's fields.
302 // If this is a parameter of local variable.
304 public bool IsParameter;
306 VariableInfo[] sub_info;
308 VariableInfo (string name, TypeSpec type, int offset, IMemberContext context)
311 this.Offset = offset;
312 this.TypeInfo = TypeInfo.GetTypeInfo (type, context);
314 Length = TypeInfo.TotalLength;
319 VariableInfo (VariableInfo parent, TypeInfo type)
321 this.Name = parent.Name;
322 this.TypeInfo = type;
323 this.Offset = parent.Offset + type.Offset;
324 this.Length = type.TotalLength;
326 this.IsParameter = parent.IsParameter;
333 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
334 if (sub_fields != null) {
335 sub_info = new VariableInfo [sub_fields.Length];
336 for (int i = 0; i < sub_fields.Length; i++) {
337 if (sub_fields [i] != null)
338 sub_info [i] = new VariableInfo (this, sub_fields [i]);
341 sub_info = new VariableInfo [0];
344 public static VariableInfo Create (BlockContext bc, LocalVariable variable)
346 var info = new VariableInfo (variable.Name, variable.Type, bc.AssignmentInfoOffset, bc);
347 bc.AssignmentInfoOffset += info.Length;
351 public static VariableInfo Create (BlockContext bc, Parameter parameter)
353 var info = new VariableInfo (parameter.Name, parameter.Type, bc.AssignmentInfoOffset, bc) {
357 bc.AssignmentInfoOffset += info.Length;
361 public bool IsAssigned (DefiniteAssignmentBitSet vector)
369 // Unless this is a struct
370 if (!TypeInfo.IsStruct)
374 // Following case cannot be handled fully by SetStructFieldAssigned
375 // because we may encounter following case
378 // struct B { int value; }
380 // setting a.b.value is propagated only to B's vector and not upwards to possible parents
383 // Each field must be assigned
385 for (int i = Offset + 1; i <= TypeInfo.Length + Offset; i++) {
390 // Ok, now check all fields which are structs.
391 for (int i = 0; i < sub_info.Length; i++) {
392 VariableInfo sinfo = sub_info[i];
396 if (!sinfo.IsAssigned (vector))
404 public bool IsEverAssigned { get; set; }
406 public bool IsFullyInitialized (FlowAnalysisContext fc, Location loc)
408 return TypeInfo.IsFullyInitialized (fc, this, loc);
411 public bool IsStructFieldAssigned (DefiniteAssignmentBitSet vector, string field_name)
413 int field_idx = TypeInfo.GetFieldIndex (field_name);
418 return vector [Offset + field_idx];
421 public void SetAssigned (DefiniteAssignmentBitSet vector, bool generatedAssignment)
426 vector.Set (Offset, Length);
428 if (!generatedAssignment)
429 IsEverAssigned = true;
432 public void SetStructFieldAssigned (DefiniteAssignmentBitSet vector, string field_name)
437 int field_idx = TypeInfo.GetFieldIndex (field_name);
442 var complex_field = TypeInfo.GetStructField (field_name);
443 if (complex_field != null) {
444 vector.Set (Offset + complex_field.Offset, complex_field.TotalLength);
446 vector.Set (Offset + field_idx);
449 IsEverAssigned = true;
452 // Each field must be assigned before setting master bit
454 for (int i = Offset + 1; i < TypeInfo.TotalLength + Offset; i++) {
460 // Set master struct flag to assigned when all tested struct
461 // fields have been assigned
466 public VariableInfo GetStructFieldInfo (string fieldName)
468 TypeInfo type = TypeInfo.GetStructField (fieldName);
473 return new VariableInfo (this, type);
476 public override string ToString ()
478 return String.Format ("Name={0} Offset={1} Length={2} {3})", Name, Offset, Length, TypeInfo);
482 public struct Reachability
484 readonly bool unreachable;
486 Reachability (bool unreachable)
488 this.unreachable = unreachable;
491 public bool IsUnreachable {
497 public static Reachability CreateUnreachable ()
499 return new Reachability (true);
502 public static Reachability operator & (Reachability a, Reachability b)
504 return new Reachability (a.unreachable && b.unreachable);
507 public static Reachability operator | (Reachability a, Reachability b)
509 return new Reachability (a.unreachable | b.unreachable);
514 // Special version of bit array. Many operations can be simplified because
515 // we are always dealing with arrays of same sizes
517 public class DefiniteAssignmentBitSet
519 const uint copy_on_write_flag = 1u << 31;
523 // Used when bits overflows
526 public static readonly DefiniteAssignmentBitSet Empty = new DefiniteAssignmentBitSet (0);
528 public DefiniteAssignmentBitSet (int length)
531 large_bits = new int[(length + 31) / 32];
534 public DefiniteAssignmentBitSet (DefiniteAssignmentBitSet source)
536 if (source.large_bits != null) {
537 large_bits = source.large_bits;
538 bits = source.bits | copy_on_write_flag;
540 bits = source.bits & ~copy_on_write_flag;
544 public static DefiniteAssignmentBitSet operator & (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
549 DefiniteAssignmentBitSet res;
550 if (a.large_bits == null) {
551 res = new DefiniteAssignmentBitSet (a);
552 res.bits &= (b.bits & ~copy_on_write_flag);
556 res = new DefiniteAssignmentBitSet (a);
558 var dest = res.large_bits;
559 var src = b.large_bits;
560 for (int i = 0; i < dest.Length; ++i) {
567 public static DefiniteAssignmentBitSet operator | (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
572 DefiniteAssignmentBitSet res;
573 if (a.large_bits == null) {
574 res = new DefiniteAssignmentBitSet (a);
576 res.bits &= ~copy_on_write_flag;
580 res = new DefiniteAssignmentBitSet (a);
582 var dest = res.large_bits;
583 var src = b.large_bits;
585 for (int i = 0; i < dest.Length; ++i) {
592 public static DefiniteAssignmentBitSet And (List<DefiniteAssignmentBitSet> das)
595 throw new ArgumentException ("Empty das");
597 DefiniteAssignmentBitSet res = das[0];
598 for (int i = 1; i < das.Count; ++i) {
607 return (bits & copy_on_write_flag) != 0;
613 return large_bits == null ? 31 : large_bits.Length * 32;
617 public void Set (int index)
619 if (CopyOnWrite && !this[index])
625 public void Set (int index, int length)
627 for (int i = 0; i < length; ++i) {
628 if (CopyOnWrite && !this[index + i])
635 public bool this[int index] {
637 return GetBit (index);
641 public override string ToString ()
644 StringBuilder sb = new StringBuilder (length);
645 for (int i = 0; i < length; ++i) {
646 sb.Append (this[i] ? '1' : '0');
649 return sb.ToString ();
654 large_bits = (int[]) large_bits.Clone ();
657 bool GetBit (int index)
659 return large_bits == null ?
660 (bits & (1 << index)) != 0 :
661 (large_bits[index >> 5] & (1 << (index & 31))) != 0;
664 void SetBit (int index)
666 if (large_bits == null)
667 bits = (uint) ((int) bits | (1 << index));
669 large_bits[index >> 5] |= (1 << (index & 31));
672 public static bool AreEqual (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
674 if (a.large_bits == null)
675 return (a.bits & ~copy_on_write_flag) == (b.bits & ~copy_on_write_flag);
677 for (int i = 0; i < a.large_bits.Length; ++i) {
678 if (a.large_bits[i] != b.large_bits[i])