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;
63 static readonly TypeInfo simple_type = new TypeInfo (1);
70 public static void Reset ()
72 StructInfo.field_type_hash = new Dictionary<TypeSpec, StructInfo> ();
75 TypeInfo (int totalLength)
77 this.TotalLength = totalLength;
80 TypeInfo (StructInfo struct_info, int offset)
82 this.struct_info = struct_info;
84 this.Length = struct_info.Length;
85 this.TotalLength = struct_info.TotalLength;
86 this.SubStructInfo = struct_info.StructFields;
90 public int GetFieldIndex (string name)
92 if (struct_info == null)
95 return struct_info [name];
98 public TypeInfo GetStructField (string name)
100 if (struct_info == null)
103 return struct_info.GetStructField (name);
106 public static TypeInfo GetTypeInfo (TypeSpec type, IMemberContext context)
112 Dictionary<TypeSpec, TypeInfo> type_hash;
113 if (type.BuiltinType > 0) {
114 // Don't cache built-in types, they are null in most cases except for
115 // corlib compilation when we need to distinguish between declaration
119 type_hash = context.Module.TypeInfoCache;
120 if (type_hash.TryGetValue (type, out info))
124 var struct_info = StructInfo.GetStructInfo (type, context);
125 if (struct_info != null) {
126 info = new TypeInfo (struct_info, 0);
131 if (type_hash != null)
132 type_hash.Add (type, info);
138 // A struct's constructor must always assign all fields.
139 // This method checks whether it actually does so.
141 public bool IsFullyInitialized (FlowAnalysisContext fc, VariableInfo vi, Location loc)
143 if (struct_info == null)
147 for (int i = 0; i < struct_info.Count; i++) {
148 var field = struct_info.Fields[i];
150 if (!fc.IsStructFieldDefinitelyAssigned (vi, field.Name)) {
151 var bf = field.MemberDefinition as Property.BackingFieldDeclaration;
153 if (bf.Initializer != null)
156 fc.Report.Error (843, loc,
157 "An automatically implemented property `{0}' must be fully assigned before control leaves the constructor. Consider calling the default struct contructor from a constructor initializer",
158 field.GetSignatureForError ());
164 fc.Report.Error (171, loc,
165 "Field `{0}' must be fully assigned before control leaves the constructor",
166 field.GetSignatureForError ());
174 public override string ToString ()
176 return String.Format ("TypeInfo ({0}:{1}:{2})",
177 Offset, Length, TotalLength);
182 readonly List<FieldSpec> fields;
183 public readonly TypeInfo[] StructFields;
184 public readonly int Length;
185 public readonly int TotalLength;
187 public static Dictionary<TypeSpec, StructInfo> field_type_hash;
188 private Dictionary<string, TypeInfo> struct_field_hash;
189 private Dictionary<string, int> field_hash;
194 // We only need one instance per type
196 StructInfo (TypeSpec type, IMemberContext context)
198 field_type_hash.Add (type, this);
200 fields = MemberCache.GetAllFieldsForDefiniteAssignment (type, context);
202 struct_field_hash = new Dictionary<string, TypeInfo> ();
203 field_hash = new Dictionary<string, int> (fields.Count);
205 StructFields = new TypeInfo[fields.Count];
206 StructInfo[] sinfo = new StructInfo[fields.Count];
210 for (int i = 0; i < fields.Count; i++) {
211 var field = fields [i];
213 if (field.MemberType.IsStruct)
214 sinfo [i] = GetStructInfo (field.MemberType, context);
216 if (sinfo [i] == null)
217 field_hash.Add (field.Name, ++Length);
218 else if (sinfo [i].InTransit) {
226 TotalLength = Length + 1;
227 for (int i = 0; i < fields.Count; i++) {
228 var field = fields [i];
230 if (sinfo [i] == null)
233 field_hash.Add (field.Name, TotalLength);
235 StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
236 struct_field_hash.Add (field.Name, StructFields [i]);
237 TotalLength += sinfo [i].TotalLength;
247 public List<FieldSpec> Fields {
253 public int this [string name] {
256 if (!field_hash.TryGetValue (name, out val))
263 public TypeInfo GetStructField (string name)
266 if (struct_field_hash.TryGetValue (name, out ti))
272 public static StructInfo GetStructInfo (TypeSpec type, IMemberContext context)
274 if (type.BuiltinType > 0 && type != context.CurrentType)
278 if (field_type_hash.TryGetValue (type, out info))
281 return new StructInfo (type, context);
287 // This is used by definite assignment analysis code to store information about a local variable
288 // or parameter. Depending on the variable's type, we need to allocate one or more elements
289 // in the BitVector - if it's a fundamental or reference type, we just need to know whether
290 // it has been assigned or not, but for structs, we need this information for each of its fields.
292 public class VariableInfo
294 readonly string Name;
296 readonly TypeInfo TypeInfo;
299 // The bit offset of this variable in the flow vector.
304 // The number of bits this variable needs in the flow vector.
305 // The first bit always specifies whether the variable as such has been assigned while
306 // the remaining bits contain this information for each of a struct's fields.
311 // If this is a parameter of local variable.
313 public bool IsParameter;
315 VariableInfo[] sub_info;
317 VariableInfo (string name, TypeSpec type, int offset, IMemberContext context)
320 this.Offset = offset;
321 this.TypeInfo = TypeInfo.GetTypeInfo (type, context);
323 Length = TypeInfo.TotalLength;
328 VariableInfo (VariableInfo parent, TypeInfo type)
330 this.Name = parent.Name;
331 this.TypeInfo = type;
332 this.Offset = parent.Offset + type.Offset;
333 this.Length = type.TotalLength;
335 this.IsParameter = parent.IsParameter;
342 TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
343 if (sub_fields != null) {
344 sub_info = new VariableInfo [sub_fields.Length];
345 for (int i = 0; i < sub_fields.Length; i++) {
346 if (sub_fields [i] != null)
347 sub_info [i] = new VariableInfo (this, sub_fields [i]);
350 sub_info = new VariableInfo [0];
353 public static VariableInfo Create (BlockContext bc, LocalVariable variable)
355 var info = new VariableInfo (variable.Name, variable.Type, bc.AssignmentInfoOffset, bc);
356 bc.AssignmentInfoOffset += info.Length;
360 public static VariableInfo Create (BlockContext bc, Parameter parameter)
362 var info = new VariableInfo (parameter.Name, parameter.Type, bc.AssignmentInfoOffset, bc) {
366 bc.AssignmentInfoOffset += info.Length;
370 public bool IsAssigned (DefiniteAssignmentBitSet vector)
378 // Unless this is a struct
379 if (!TypeInfo.IsStruct)
383 // Following case cannot be handled fully by SetStructFieldAssigned
384 // because we may encounter following case
387 // struct B { int value; }
389 // setting a.b.value is propagated only to B's vector and not upwards to possible parents
392 // Each field must be assigned
394 for (int i = Offset + 1; i <= TypeInfo.Length + Offset; i++) {
399 // Ok, now check all fields which are structs.
400 for (int i = 0; i < sub_info.Length; i++) {
401 VariableInfo sinfo = sub_info[i];
405 if (!sinfo.IsAssigned (vector))
413 public bool IsEverAssigned { get; set; }
415 public bool IsFullyInitialized (FlowAnalysisContext fc, Location loc)
417 return TypeInfo.IsFullyInitialized (fc, this, loc);
420 public bool IsStructFieldAssigned (DefiniteAssignmentBitSet vector, string field_name)
422 int field_idx = TypeInfo.GetFieldIndex (field_name);
427 return vector [Offset + field_idx];
430 public void SetAssigned (DefiniteAssignmentBitSet vector, bool generatedAssignment)
435 vector.Set (Offset, Length);
437 if (!generatedAssignment)
438 IsEverAssigned = true;
441 public void SetStructFieldAssigned (DefiniteAssignmentBitSet vector, string field_name)
446 int field_idx = TypeInfo.GetFieldIndex (field_name);
451 var complex_field = TypeInfo.GetStructField (field_name);
452 if (complex_field != null) {
453 vector.Set (Offset + complex_field.Offset, complex_field.TotalLength);
455 vector.Set (Offset + field_idx);
458 IsEverAssigned = true;
461 // Each field must be assigned before setting master bit
463 for (int i = Offset + 1; i < TypeInfo.TotalLength + Offset; i++) {
469 // Set master struct flag to assigned when all tested struct
470 // fields have been assigned
475 public VariableInfo GetStructFieldInfo (string fieldName)
477 TypeInfo type = TypeInfo.GetStructField (fieldName);
482 return new VariableInfo (this, type);
485 public override string ToString ()
487 return String.Format ("Name={0} Offset={1} Length={2} {3})", Name, Offset, Length, TypeInfo);
491 public struct Reachability
493 readonly bool unreachable;
495 Reachability (bool unreachable)
497 this.unreachable = unreachable;
500 public bool IsUnreachable {
506 public static Reachability CreateUnreachable ()
508 return new Reachability (true);
511 public static Reachability operator & (Reachability a, Reachability b)
513 return new Reachability (a.unreachable && b.unreachable);
516 public static Reachability operator | (Reachability a, Reachability b)
518 return new Reachability (a.unreachable | b.unreachable);
523 // Special version of bit array. Many operations can be simplified because
524 // we are always dealing with arrays of same sizes
526 public class DefiniteAssignmentBitSet
528 const uint copy_on_write_flag = 1u << 31;
532 // Used when bits overflows
535 public static readonly DefiniteAssignmentBitSet Empty = new DefiniteAssignmentBitSet (0);
537 public DefiniteAssignmentBitSet (int length)
540 large_bits = new int[(length + 31) / 32];
543 public DefiniteAssignmentBitSet (DefiniteAssignmentBitSet source)
545 if (source.large_bits != null) {
546 large_bits = source.large_bits;
547 bits = source.bits | copy_on_write_flag;
549 bits = source.bits & ~copy_on_write_flag;
553 public static DefiniteAssignmentBitSet operator & (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
558 DefiniteAssignmentBitSet res;
559 if (a.large_bits == null) {
560 res = new DefiniteAssignmentBitSet (a);
561 res.bits &= (b.bits & ~copy_on_write_flag);
565 res = new DefiniteAssignmentBitSet (a);
567 var dest = res.large_bits;
568 var src = b.large_bits;
569 for (int i = 0; i < dest.Length; ++i) {
576 public static DefiniteAssignmentBitSet operator | (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
581 DefiniteAssignmentBitSet res;
582 if (a.large_bits == null) {
583 res = new DefiniteAssignmentBitSet (a);
585 res.bits &= ~copy_on_write_flag;
589 res = new DefiniteAssignmentBitSet (a);
591 var dest = res.large_bits;
592 var src = b.large_bits;
594 for (int i = 0; i < dest.Length; ++i) {
601 public static DefiniteAssignmentBitSet And (List<DefiniteAssignmentBitSet> das)
604 throw new ArgumentException ("Empty das");
606 DefiniteAssignmentBitSet res = das[0];
607 for (int i = 1; i < das.Count; ++i) {
616 return (bits & copy_on_write_flag) != 0;
622 return large_bits == null ? 31 : large_bits.Length * 32;
626 public void Set (int index)
628 if (CopyOnWrite && !this[index])
634 public void Set (int index, int length)
636 for (int i = 0; i < length; ++i) {
637 if (CopyOnWrite && !this[index + i])
644 public bool this[int index] {
646 return GetBit (index);
650 public override string ToString ()
653 StringBuilder sb = new StringBuilder (length);
654 for (int i = 0; i < length; ++i) {
655 sb.Append (this[i] ? '1' : '0');
658 return sb.ToString ();
663 large_bits = (int[]) large_bits.Clone ();
666 bool GetBit (int index)
668 return large_bits == null ?
669 (bits & (1 << index)) != 0 :
670 (large_bits[index >> 5] & (1 << (index & 31))) != 0;
673 void SetBit (int index)
675 if (large_bits == null)
676 bits = (uint) ((int) bits | (1 << index));
678 large_bits[index >> 5] |= (1 << (index & 31));
681 static bool IsEqual (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
683 if (a.large_bits == null)
684 return (a.bits & ~copy_on_write_flag) == (b.bits & ~copy_on_write_flag);
686 for (int i = 0; i < a.large_bits.Length; ++i) {
687 if (a.large_bits[i] != b.large_bits[i])
694 public static bool IsIncluded (DefiniteAssignmentBitSet set, DefiniteAssignmentBitSet test)
696 var set_bits = set.large_bits;
697 if (set_bits == null)
698 return (set.bits & test.bits & ~copy_on_write_flag) == (set.bits & ~copy_on_write_flag);
700 var test_bits = test.large_bits;
701 for (int i = 0; i < set_bits.Length; ++i) {
702 if ((set_bits[i] & test_bits[i]) != set_bits[i])