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
])