source: branches/2922-DataCompletenessChartPerf/HeuristicLab.ExtLibs/HeuristicLab.NRefactory/5.5.0/NRefactory.CSharp-5.5.0/Parser/mcs/flowanalysis.cs

//
// flowanalyis.cs: The control flow analysis code
//
// Authors:
//   Martin Baulig (martin@ximian.com)
//   Raja R Harinath (rharinath@novell.com)
//   Marek Safar (marek.safar@gmail.com)
//
// Copyright 2001, 2002, 2003 Ximian, Inc.
// Copyright 2003-2008 Novell, Inc.
// Copyright 2011 Xamarin, Inc.
//

using System;
using System.Text;
using System.Collections.Generic;

namespace Mono.CSharp
{
  // <summary>
  //   This is used by the flow analysis code to keep track of the type of local variables.
  //
  //   The flow code uses a BitVector to keep track of whether a variable has been assigned
  //   or not.  This is easy for fundamental types (int, char etc.) or reference types since
  //   you can only assign the whole variable as such.
  //
  //   For structs, we also need to keep track of all its fields.  To do this, we allocate one
  //   bit for the struct itself (it's used if you assign/access the whole struct) followed by
  //   one bit for each of its fields.
  //
  //   This class computes this `layout' for each type.
  // </summary>
  public class TypeInfo
  {
    // <summary>
    //   Total number of bits a variable of this type consumes in the flow vector.
    // </summary>
    public readonly int TotalLength;

    // <summary>
    //   Number of bits the simple fields of a variable of this type consume
    //   in the flow vector.
    // </summary>
    public readonly int Length;

    // <summary>
    //   This is only used by sub-structs.
    // </summary>
    public readonly int Offset;

    // <summary>
    //   If this is a struct.
    // </summary>
    public readonly bool IsStruct;

    // <summary>
    //   If this is a struct, all fields which are structs theirselves.
    // </summary>
    public TypeInfo[] SubStructInfo;

    readonly StructInfo struct_info;
    private static Dictionary<TypeSpec, TypeInfo> type_hash;

    static readonly TypeInfo simple_type = new TypeInfo (1);
    
    static TypeInfo ()
    {
      Reset ();
    }
    
    public static void Reset ()
    {
      type_hash = new Dictionary<TypeSpec, TypeInfo> ();
      StructInfo.field_type_hash = new Dictionary<TypeSpec, StructInfo> ();
    }

    TypeInfo (int totalLength)
    {
      this.TotalLength = totalLength;
    }
    
    TypeInfo (StructInfo struct_info, int offset)
    {
      this.struct_info = struct_info;
      this.Offset = offset;
      this.Length = struct_info.Length;
      this.TotalLength = struct_info.TotalLength;
      this.SubStructInfo = struct_info.StructFields;
      this.IsStruct = true;
    }
    
    public int GetFieldIndex (string name)
    {
      if (struct_info == null)
        return 0;

      return struct_info [name];
    }

    public TypeInfo GetStructField (string name)
    {
      if (struct_info == null)
        return null;

      return struct_info.GetStructField (name);
    }

    public static TypeInfo GetTypeInfo (TypeSpec type)
    {
      if (!type.IsStruct)
        return simple_type;

      TypeInfo info;
      if (type_hash.TryGetValue (type, out info))
        return info;

      var struct_info = StructInfo.GetStructInfo (type);
      if (struct_info != null) {
        info = new TypeInfo (struct_info, 0);
      } else {
        info = simple_type;
      }

      type_hash.Add (type, info);
      return info;
    }

    // <summary>
    //   A struct's constructor must always assign all fields.
    //   This method checks whether it actually does so.
    // </summary>
    public bool IsFullyInitialized (FlowAnalysisContext fc, VariableInfo vi, Location loc)
    {
      if (struct_info == null)
        return true;

      bool ok = true;
      for (int i = 0; i < struct_info.Count; i++) {
        var field = struct_info.Fields[i];

        if (!fc.IsStructFieldDefinitelyAssigned (vi, field.Name)) {
          var bf = field.MemberDefinition as Property.BackingField;
          if (bf != null) {
            if (bf.Initializer != null)
              continue;

            fc.Report.Error (843, loc,
              "An automatically implemented property `{0}' must be fully assigned before control leaves the constructor. Consider calling the default struct contructor from a constructor initializer",
              field.GetSignatureForError ());

            ok = false;
            continue;
          }

          fc.Report.Error (171, loc,
            "Field `{0}' must be fully assigned before control leaves the constructor",
            field.GetSignatureForError ());
          ok = false;
        }
      }

      return ok;
    }

    public override string ToString ()
    {
      return String.Format ("TypeInfo ({0}:{1}:{2})",
                Offset, Length, TotalLength);
    }

    class StructInfo
    {
      readonly List<FieldSpec> fields;
      public readonly TypeInfo[] StructFields;
      public readonly int Length;
      public readonly int TotalLength;

      public static Dictionary<TypeSpec, StructInfo> field_type_hash;
      private Dictionary<string, TypeInfo> struct_field_hash;
      private Dictionary<string, int> field_hash;

      bool InTransit;

      //
      // We only need one instance per type
      //
      StructInfo (TypeSpec type)
      {
        field_type_hash.Add (type, this);

        fields = MemberCache.GetAllFieldsForDefiniteAssignment (type);

        struct_field_hash = new Dictionary<string, TypeInfo> ();
        field_hash = new Dictionary<string, int> (fields.Count);

        StructFields = new TypeInfo[fields.Count];
        StructInfo[] sinfo = new StructInfo[fields.Count];

        InTransit = true;

        for (int i = 0; i < fields.Count; i++) {
          var field = fields [i];

          if (field.MemberType.IsStruct)
            sinfo [i] = GetStructInfo (field.MemberType);

          if (sinfo [i] == null)
            field_hash.Add (field.Name, ++Length);
          else if (sinfo [i].InTransit) {
            sinfo [i] = null;
            return;
          }
        }

        InTransit = false;

        TotalLength = Length + 1;
        for (int i = 0; i < fields.Count; i++) {
          var field = fields [i];

          if (sinfo [i] == null)
            continue;

          field_hash.Add (field.Name, TotalLength);

          StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
          struct_field_hash.Add (field.Name, StructFields [i]);
          TotalLength += sinfo [i].TotalLength;
        }
      }

      public int Count {
        get {
          return fields.Count;
        }
      }

      public List<FieldSpec> Fields {
        get {
          return fields;
        }
      }

      public int this [string name] {
        get {
          int val;
          if (!field_hash.TryGetValue (name, out val))
            return 0;

          return val;
        }
      }

      public TypeInfo GetStructField (string name)
      {
        TypeInfo ti;
        if (struct_field_hash.TryGetValue (name, out ti))
          return ti;

        return null;
      }

      public static StructInfo GetStructInfo (TypeSpec type)
      {
        if (type.BuiltinType > 0)
          return null;

        StructInfo info;
        if (field_type_hash.TryGetValue (type, out info))
          return info;

        return new StructInfo (type);
      }
    }
  }

  //
  // This is used by definite assignment analysis code to store information about a local variable
  // or parameter.  Depending on the variable's type, we need to allocate one or more elements
  // in the BitVector - if it's a fundamental or reference type, we just need to know whether
  // it has been assigned or not, but for structs, we need this information for each of its fields.
  //
  public class VariableInfo
  {
    readonly string Name;

    readonly TypeInfo TypeInfo;

    // <summary>
    //   The bit offset of this variable in the flow vector.
    // </summary>
    readonly int Offset;

    // <summary>
    //   The number of bits this variable needs in the flow vector.
    //   The first bit always specifies whether the variable as such has been assigned while
    //   the remaining bits contain this information for each of a struct's fields.
    // </summary>
    readonly int Length;

    // <summary>
    //   If this is a parameter of local variable.
    // </summary>
    public bool IsParameter;

    VariableInfo[] sub_info;

    VariableInfo (string name, TypeSpec type, int offset)
    {
      this.Name = name;
      this.Offset = offset;
      this.TypeInfo = TypeInfo.GetTypeInfo (type);

      Length = TypeInfo.TotalLength;

      Initialize ();
    }

    VariableInfo (VariableInfo parent, TypeInfo type)
    {
      this.Name = parent.Name;
      this.TypeInfo = type;
      this.Offset = parent.Offset + type.Offset;
      this.Length = type.TotalLength;

      this.IsParameter = parent.IsParameter;

      Initialize ();
    }

    void Initialize ()
    {
      TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
      if (sub_fields != null) {
        sub_info = new VariableInfo [sub_fields.Length];
        for (int i = 0; i < sub_fields.Length; i++) {
          if (sub_fields [i] != null)
            sub_info [i] = new VariableInfo (this, sub_fields [i]);
        }
      } else
        sub_info = new VariableInfo [0];
    }

    public static VariableInfo Create (BlockContext bc, LocalVariable variable)
    {
      var info = new VariableInfo (variable.Name, variable.Type, bc.AssignmentInfoOffset);
      bc.AssignmentInfoOffset += info.Length;
      return info;
    }

    public static VariableInfo Create (BlockContext bc, Parameter parameter)
    {
      var info = new VariableInfo (parameter.Name, parameter.Type, bc.AssignmentInfoOffset) {
        IsParameter = true
      };

      bc.AssignmentInfoOffset += info.Length;
      return info;
    }

    public bool IsAssigned (DefiniteAssignmentBitSet vector)
    {
      if (vector == null)
        return true;

      if (vector [Offset])
        return true;

      // Unless this is a struct
      if (!TypeInfo.IsStruct)
        return false;

      //
      // Following case cannot be handled fully by SetStructFieldAssigned
      // because we may encounter following case
      // 
      // struct A { B b }
      // struct B { int value; }
      //
      // setting a.b.value is propagated only to B's vector and not upwards to possible parents
      //
      //
      // Each field must be assigned
      //
      for (int i = Offset + 1; i <= TypeInfo.Length + Offset; i++) {
        if (!vector[i])
          return false;
      }

      // Ok, now check all fields which are structs.
      for (int i = 0; i < sub_info.Length; i++) {
        VariableInfo sinfo = sub_info[i];
        if (sinfo == null)
          continue;

        if (!sinfo.IsAssigned (vector))
          return false;
      }
      
      vector.Set (Offset);
      return true;
    }

    public bool IsEverAssigned { get; set; }

    public bool IsFullyInitialized (FlowAnalysisContext fc, Location loc)
    {
      return TypeInfo.IsFullyInitialized (fc, this, loc);
    }

    public bool IsStructFieldAssigned (DefiniteAssignmentBitSet vector, string field_name)
    {
      int field_idx = TypeInfo.GetFieldIndex (field_name);

      if (field_idx == 0)
        return true;

      return vector [Offset + field_idx];
    }

    public void SetAssigned (DefiniteAssignmentBitSet vector, bool generatedAssignment)
    {
      if (Length == 1)
        vector.Set (Offset);
      else
        vector.Set (Offset, Length);

      if (!generatedAssignment)
        IsEverAssigned = true;
    }

    public void SetStructFieldAssigned (DefiniteAssignmentBitSet vector, string field_name)
    {
      if (vector [Offset])
        return;

      int field_idx = TypeInfo.GetFieldIndex (field_name);

      if (field_idx == 0)
        return;

      var complex_field = TypeInfo.GetStructField (field_name);
      if (complex_field != null) {
        vector.Set (Offset + complex_field.Offset, complex_field.TotalLength);
      } else {
        vector.Set (Offset + field_idx);
      }

      IsEverAssigned = true;

      //
      // Each field must be assigned before setting master bit
      //
      for (int i = Offset + 1; i < TypeInfo.TotalLength + Offset; i++) {
        if (!vector[i])
          return;
      }

      //
      // Set master struct flag to assigned when all tested struct
      // fields have been assigned
      //
      vector.Set (Offset);
    }

    public VariableInfo GetStructFieldInfo (string fieldName)
    {
      TypeInfo type = TypeInfo.GetStructField (fieldName);

      if (type == null)
        return null;

      return new VariableInfo (this, type);
    }

    public override string ToString ()
    {
      return String.Format ("Name={0} Offset={1} Length={2} {3})", Name, Offset, Length, TypeInfo);
    }
  }

  public struct Reachability
  {
    readonly bool unreachable;

    Reachability (bool unreachable)
    {
      this.unreachable = unreachable;
    }

    public bool IsUnreachable {
      get {
        return unreachable;
      }
    }

    public static Reachability CreateUnreachable ()
    {
      return new Reachability (true);
    }

    public static Reachability operator & (Reachability a, Reachability b)
    {
        return new Reachability (a.unreachable && b.unreachable);
    }

    public static Reachability operator | (Reachability a, Reachability b)
    {
      return new Reachability (a.unreachable | b.unreachable);
    }
  }

  //
  // Special version of bit array. Many operations can be simplified because
  // we are always dealing with arrays of same sizes
  //
  public class DefiniteAssignmentBitSet
  {
    const uint copy_on_write_flag = 1u << 31;

    uint bits;

    // Used when bits overflows
    int[] large_bits;

    public static readonly DefiniteAssignmentBitSet Empty = new DefiniteAssignmentBitSet (0);

    public DefiniteAssignmentBitSet (int length)
    {
      if (length > 31)
        large_bits = new int[(length + 31) / 32];
    }

    public DefiniteAssignmentBitSet (DefiniteAssignmentBitSet source)
    {
      if (source.large_bits != null) {
        large_bits = source.large_bits;
        bits = source.bits | copy_on_write_flag;
      } else {
        bits = source.bits & ~copy_on_write_flag;
      }
    }

    public static DefiniteAssignmentBitSet operator & (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
    {
      if (AreEqual (a, b))
        return a;

      DefiniteAssignmentBitSet res;
      if (a.large_bits == null) {
        res = new DefiniteAssignmentBitSet (a);
        res.bits &= (b.bits & ~copy_on_write_flag);
        return res;
      }

      res = new DefiniteAssignmentBitSet (a);
      res.Clone ();
      var dest = res.large_bits;
      var src = b.large_bits;
      for (int i = 0; i < dest.Length; ++i) {
        dest[i] &= src[i];
      }

      return res;
    }

    public static DefiniteAssignmentBitSet operator | (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
    {
      if (AreEqual (a, b))
        return a;

      DefiniteAssignmentBitSet res;
      if (a.large_bits == null) {
        res = new DefiniteAssignmentBitSet (a);
        res.bits |= b.bits;
        res.bits &= ~copy_on_write_flag;
        return res;
      }

      res = new DefiniteAssignmentBitSet (a);
      res.Clone ();
      var dest = res.large_bits;
      var src = b.large_bits;

      for (int i = 0; i < dest.Length; ++i) {
        dest[i] |= src[i];
      }

      return res;
    }

    public static DefiniteAssignmentBitSet And (List<DefiniteAssignmentBitSet> das)
    {
      if (das.Count == 0)
        throw new ArgumentException ("Empty das");

      DefiniteAssignmentBitSet res = das[0];
      for (int i = 1; i < das.Count; ++i) {
        res &= das[i];
      }

      return res;
    }

    bool CopyOnWrite {
      get {
        return (bits & copy_on_write_flag) != 0;
      }
    }

    int Length {
      get {
        return large_bits == null ? 31 : large_bits.Length * 32;
      }
    }

    public void Set (int index)
    {
      if (CopyOnWrite && !this[index])
        Clone ();

      SetBit (index);
    }

    public void Set (int index, int length)
    {
      for (int i = 0; i < length; ++i) {
        if (CopyOnWrite && !this[index + i])
          Clone ();

        SetBit (index + i);
      }
    }

    public bool this[int index] {
      get {
        return GetBit (index);
      }
    }

    public override string ToString ()
    {
      var length = Length;
      StringBuilder sb = new StringBuilder (length);
      for (int i = 0; i < length; ++i) {
        sb.Append (this[i] ? '1' : '0');
      }

      return sb.ToString ();
    }

    void Clone ()
    {
      large_bits = (int[]) large_bits.Clone ();
    }

    bool GetBit (int index)
    {
      return large_bits == null ?
        (bits & (1 << index)) != 0 :
        (large_bits[index >> 5] & (1 << (index & 31))) != 0;
    }

    void SetBit (int index)
    {
      if (large_bits == null)
        bits = (uint) ((int) bits | (1 << index));
      else
        large_bits[index >> 5] |= (1 << (index & 31));
    }

    static bool AreEqual (DefiniteAssignmentBitSet a, DefiniteAssignmentBitSet b)
    {
      if (a.large_bits == null)
        return (a.bits & ~copy_on_write_flag) == (b.bits & ~copy_on_write_flag);

      for (int i = 0; i < a.large_bits.Length; ++i) {
        if (a.large_bits[i] != b.large_bits[i])
          return false;
      }

      return true;
    }
  }
}