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)
114 if (type_hash.TryGetValue (type, out info))
117 var struct_info = StructInfo.GetStructInfo (type);
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 if (field.MemberDefinition is Property.BackingField) {
143 fc.Report.Error (843, loc,
144 "An automatically implemented property `{0}' must be fully assigned before control leaves the constructor. Consider calling the default struct contructor from a constructor initializer",
145 field.GetSignatureForError ());
147 fc.Report.Error (171, loc,
148 "Field `{0}' must be fully assigned before control leaves the constructor",
149 field.GetSignatureForError ());
158 public override string ToString ()
160 return String.Format ("TypeInfo ({0}:{1}:{2})",
161 Offset, Length, TotalLength);
166 readonly List<FieldSpec> fields;
167 public readonly TypeInfo[] StructFields;
168 public readonly int Length;
169 public readonly int TotalLength;
171 public static Dictionary<TypeSpec, StructInfo> field_type_hash;
172 private Dictionary<string, TypeInfo> struct_field_hash;
173 private Dictionary<string, int> field_hash;
178 // We only need one instance per type
180 StructInfo (TypeSpec type)
182 field_type_hash.Add (type, this);
184 fields = MemberCache.GetAllFieldsForDefiniteAssignment (type);
186 struct_field_hash = new Dictionary<string, TypeInfo> ();
187 field_hash = new Dictionary<string, int> (fields.Count);
189 StructFields = new TypeInfo[fields.Count];
190 StructInfo[] sinfo = new StructInfo[fields.Count];
194 for (int i = 0; i < fields.Count; i++) {
195 var field = fields [i];
197 if (field.MemberType.IsStruct)
198 sinfo [i] = GetStructInfo (field.MemberType);
200 if (sinfo [i] == null)
201 field_hash.Add (field.Name, ++Length);
202 else if (sinfo [i].InTransit) {
210 TotalLength = Length + 1;
211 for (int i = 0; i < fields.Count; i++) {
212 var field = fields [i];
214 if (sinfo [i] == null)
217 field_hash.Add (field.Name, TotalLength);
219 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
220 struct_field_hash.Add (field.Name, StructFields [i]);
221 TotalLength += sinfo [i].TotalLength;
231 public List<FieldSpec> Fields {
237 public int this [string name] {
240 if (!field_hash.TryGetValue (name, out val))
247 public TypeInfo GetStructField (string name)
250 if (struct_field_hash.TryGetValue (name, out ti))
256 public static StructInfo GetStructInfo (TypeSpec type)
258 if (type.BuiltinType > 0)
262 if (field_type_hash.TryGetValue (type, out info))
265 return new StructInfo (type);
271 // This is used by definite assignment analysis code to store information about a local variable
272 // or parameter. Depending on the variable's type, we need to allocate one or more elements
273 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
274 // it has been assigned or not, but for structs, we need this information for each of its fields.
276 public class VariableInfo
278 readonly string Name;
280 readonly TypeInfo TypeInfo;
283 // The bit offset of this variable in the flow vector.
288 // The number of bits this variable needs in the flow vector.
289 // The first bit always specifies whether the variable as such has been assigned while
290 // the remaining bits contain this information for each of a struct's fields.
295 // If this is a parameter of local variable.
297 public bool IsParameter;
299 VariableInfo[] sub_info;
301 VariableInfo (string name, TypeSpec type, int offset)
304 this.Offset = offset;
305 this.TypeInfo = TypeInfo.GetTypeInfo (type);
307 Length = TypeInfo.TotalLength;
312 VariableInfo (VariableInfo parent, TypeInfo type)
314 this.Name = parent.Name;
315 this.TypeInfo = type;
316 this.Offset = parent.Offset + type.Offset;
317 this.Length = type.TotalLength;
319 this.IsParameter = parent.IsParameter;
326 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
327 if (sub_fields != null) {
328 sub_info = new VariableInfo [sub_fields.Length];
329 for (int i = 0; i < sub_fields.Length; i++) {
330 if (sub_fields [i] != null)
331 sub_info [i] = new VariableInfo (this, sub_fields [i]);
334 sub_info = new VariableInfo [0];
337 public static VariableInfo Create (BlockContext bc, LocalVariable variable)
339 var info = new VariableInfo (variable.Name, variable.Type, bc.AssignmentInfoOffset);
340 bc.AssignmentInfoOffset += info.Length;
344 public static VariableInfo Create (BlockContext bc, Parameter parameter)
346 var info = new VariableInfo (parameter.Name, parameter.Type, bc.AssignmentInfoOffset) {
350 bc.AssignmentInfoOffset += info.Length;
354 public bool IsAssigned (DefiniteAssignmentBitSet vector)
362 // Unless this is a struct
363 if (!TypeInfo.IsStruct)
367 // Following case cannot be handled fully by SetStructFieldAssigned
368 // because we may encounter following case
371 // struct B { int value; }
373 // setting a.b.value is propagated only to B's vector and not upwards to possible parents
376 // Each field must be assigned
378 for (int i = Offset + 1; i <= TypeInfo.Length + Offset; i++) {
383 // Ok, now check all fields which are structs.
384 for (int i = 0; i < sub_info.Length; i++) {
385 VariableInfo sinfo = sub_info[i];
389 if (!sinfo.IsAssigned (vector))
397 public bool IsEverAssigned { get; set; }
399 public bool IsFullyInitialized (FlowAnalysisContext fc, Location loc)
401 return TypeInfo.IsFullyInitialized (fc, this, loc);
404 public bool IsStructFieldAssigned (DefiniteAssignmentBitSet vector, string field_name)
406 int field_idx = TypeInfo.GetFieldIndex (field_name);
411 return vector [Offset + field_idx];
414 public void SetAssigned (DefiniteAssignmentBitSet vector, bool generatedAssignment)
419 vector.Set (Offset, Length);
421 if (!generatedAssignment)
422 IsEverAssigned = true;
425 public void SetStructFieldAssigned (DefiniteAssignmentBitSet vector, string field_name)
430 int field_idx = TypeInfo.GetFieldIndex (field_name);
435 var complex_field = TypeInfo.GetStructField (field_name);
436 if (complex_field != null) {
437 vector.Set (Offset + complex_field.Offset, complex_field.TotalLength);
439 vector.Set (Offset + field_idx);
442 IsEverAssigned = true;
445 // Each field must be assigned before setting master bit
447 for (int i = Offset + 1; i < TypeInfo.TotalLength + Offset; i++) {
453 // Set master struct flag to assigned when all tested struct
454 // fields have been assigned
459 public VariableInfo GetStructFieldInfo (string fieldName)
461 TypeInfo type = TypeInfo.GetStructField (fieldName);
466 return new VariableInfo (this, type);
469 public override string ToString ()
471 return String.Format ("Name={0} Offset={1} Length={2} {3})", Name, Offset, Length, TypeInfo);
475 public struct Reachability
477 readonly bool unreachable;
479 Reachability (bool unreachable)
481 this.unreachable = unreachable;
484 public bool IsUnreachable {
490 public static Reachability CreateUnreachable ()
492 return new Reachability (true);
495 public static Reachability operator & (Reachability a, Reachability b)
497 return new Reachability (a.unreachable && b.unreachable);
500 public static Reachability operator | (Reachability a, Reachability b)
502 return new Reachability (a.unreachable | b.unreachable);
507 // Special version of bit array. Many operations can be simplified because
508 // we are always dealing with arrays of same sizes
510 public class DefiniteAssignmentBitSet
512 const uint copy_on_write_flag = 1u << 31;
516 // Used when bits overflows
519 public static readonly DefiniteAssignmentBitSet Empty = new DefiniteAssignmentBitSet (0);
521 public DefiniteAssignmentBitSet (int length)
524 large_bits = new int[(length + 31) / 32];
527 public DefiniteAssignmentBitSet (DefiniteAssignmentBitSet source)
529 if (source.large_bits != null) {
530 large_bits = source.large_bits;
531 bits = source.bits | copy_on_write_flag;
533 bits = source.bits & ~copy_on_write_flag;
537 public static DefiniteAssignmentBitSet operator & (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
542 DefiniteAssignmentBitSet res;
543 if (a.large_bits == null) {
544 res = new DefiniteAssignmentBitSet (a);
545 res.bits &= (b.bits & ~copy_on_write_flag);
549 res = new DefiniteAssignmentBitSet (a);
551 var dest = res.large_bits;
552 var src = b.large_bits;
553 for (int i = 0; i < dest.Length; ++i) {
560 public static DefiniteAssignmentBitSet operator | (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
565 DefiniteAssignmentBitSet res;
566 if (a.large_bits == null) {
567 res = new DefiniteAssignmentBitSet (a);
569 res.bits &= ~copy_on_write_flag;
573 res = new DefiniteAssignmentBitSet (a);
575 var dest = res.large_bits;
576 var src = b.large_bits;
578 for (int i = 0; i < dest.Length; ++i) {
585 public static DefiniteAssignmentBitSet And (List<DefiniteAssignmentBitSet> das)
588 throw new ArgumentException ("Empty das");
590 DefiniteAssignmentBitSet res = das[0];
591 for (int i = 1; i < das.Count; ++i) {
600 return (bits & copy_on_write_flag) != 0;
606 return large_bits == null ? 31 : large_bits.Length * 32;
610 public void Set (int index)
612 if (CopyOnWrite && !this[index])
618 public void Set (int index, int length)
620 for (int i = 0; i < length; ++i) {
621 if (CopyOnWrite && !this[index + i])
628 public bool this[int index] {
630 return GetBit (index);
634 public override string ToString ()
637 StringBuilder sb = new StringBuilder (length);
638 for (int i = 0; i < length; ++i) {
639 sb.Append (this[i] ? '1' : '0');
642 return sb.ToString ();
647 large_bits = (int[]) large_bits.Clone ();
650 bool GetBit (int index)
652 return large_bits == null ?
653 (bits & (1 << index)) != 0 :
654 (large_bits[index >> 5] & (1 << (index & 31))) != 0;
657 void SetBit (int index)
659 if (large_bits == null)
660 bits = (uint) ((int) bits | (1 << index));
662 large_bits[index >> 5] |= (1 << (index & 31));
665 static bool AreEqual (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
667 if (a.large_bits == null)
668 return (a.bits & ~copy_on_write_flag) == (b.bits & ~copy_on_write_flag);
670 for (int i = 0; i < a.large_bits.Length; ++i) {
671 if (a.large_bits[i] != b.large_bits[i])