EquivalenceClass.cs

Go to the documentation of this file.

// -------------------------------------------------------------------------- //
// Project rROTOR                                                             //
// -------------------------------------------------------------------------- //
// File: EquivalenceClass.cs                                                        //
// Author: Francisco Ortin-  francisco.ortin@gmail.com                        //
// Description:                                                               //
//    Represents a equivalence class of type varariables [Aho].              //
// -------------------------------------------------------------------------- //
// Create date: 03-04-2007                                                    //
//visto
using System;
using System.Collections.Generic;
using System.Text;
using Tools;
using TypeSystem.Operations;

namespace TypeSystem {
    public class EquivalenceClass {
        #region Fields
        private IDictionary<int, TypeVariable> typeVariables = new Dictionary<int, TypeVariable>();

        private TypeExpression substitution;
        #endregion

        #region Properties
        public IDictionary<int, TypeVariable> TypeVariables {
            get { return typeVariables; }
        }

        public TypeExpression Substitution {
            get { return substitution; }
        }
        #endregion


        #region Constructors
        public EquivalenceClass() { }

        public EquivalenceClass(TypeExpression te) {
            if (!(te is TypeVariable))
                throw new ArgumentException("I need a type variable, not a " + te);
            add(te, SortOfUnification.Equivalent, new List<Pair<TypeExpression, TypeExpression>>());
        }
        #endregion

        private static int numero = 0;
        #region Add
        public bool add(TypeExpression te, SortOfUnification unification, IList<Pair<TypeExpression, TypeExpression>> previouslyUnified) {
            TypeVariable tv = te as TypeVariable;
            if (tv != null) { // * Another type variable
                // * Tries to add its substitution
                if (tv.Substitution != null) // * If it has a substitution 
                    if (!this.add(tv.EquivalenceClass.Substitution, unification, previouslyUnified)) // * We try to add it to ourselves
                        return false; // * Both susbstitutions are not the same
                // * If no error, we add it to the equivalence class
                this.typeVariables[tv.Variable] = tv;
                if (tv.EquivalenceClass != null) {  // * The parameter already has a equivalence class
                    IList<int> keys = new List<int>(tv.EquivalenceClass.TypeVariables.Keys);
                    foreach (int pairKey in keys) {
                        if (!this.typeVariables.ContainsKey(pairKey)) {
                            // * We recursively add all the element of the equivalence class
                            this.typeVariables[pairKey] = tv.EquivalenceClass.TypeVariables[pairKey];
                            this.add(tv.EquivalenceClass.TypeVariables[pairKey], unification, previouslyUnified);
                        }
                    }
                }
                // * Finally, we update the equivalence class of tv
                tv.EquivalenceClass = this;
                return true;
            }
            // * te is not a type variable
            if (this.substitution != null) {
                // * A substitution already exists
                if (unification == SortOfUnification.Equivalent) {
                    // * They must be equivalent
                    if ( !(bool)this.substitution.AcceptOperation(new EquivalentOperation(te), null) )
                        return false;
                    if (te.HasTypeVariables())
                        // var1=Array(int) must be unified to Array(var1)
                        return te.Unify(this.substitution, unification, previouslyUnified);
                    return true;
                }
                if (unification == SortOfUnification.Incremental) {
                    // * The incremental behaviour implies a union of all the types
                    this.substitution = UnionType.collect(this.substitution, te);
                    return true;
                }
                // * Override unification (the susbstitution is overridden)
                this.substitution = te;
                return true;
            }
            // * We set the type as a susbstitution
            substitution = te;
            return true;
        }
        #endregion

        private string cachedToString = "";
        #region ToString()
        public override string ToString() {
            StringBuilder sb = new StringBuilder("{");
            ICollection<int> keys = typeVariables.Keys;
            int i = 0;
            foreach (int key in keys)
            {
                sb.Append(key);
                if (i < keys.Count - 1)
                    sb.Append(",");
                i++;
            }
            sb.Append("}");
            return sb.ToString();            
        }
        #endregion



        #region UpdateEquivalenceClass()
        public void UpdateEquivalenceClass(IDictionary<TypeVariable, TypeVariable> typeVariableMappings) {
            // * Creates a new equivalence class
            EquivalenceClass newEquivalenceClass = new EquivalenceClass();
            // * We take the existing substitution...
            newEquivalenceClass.substitution = this.substitution;
            //   ... changing old type variables for new ones
            if (newEquivalenceClass.substitution != null)
                newEquivalenceClass.substitution.ReplaceTypeVariables(typeVariableMappings);
            // * We update all the appropiate type variables
            newEquivalenceClass.typeVariables = new Dictionary<int, TypeVariable>();
            foreach (KeyValuePair<int, TypeVariable> oldPair in this.typeVariables) {
                // * Is there a new type variable for the existing one?
                if (typeVariableMappings.ContainsKey(oldPair.Value)) {
                    // * We create a new entry with the new one...
                    TypeVariable newTypeVariable = typeVariableMappings[oldPair.Value];
                    newEquivalenceClass.typeVariables[newTypeVariable.Variable] = newTypeVariable;
                    // * ... and updates the class equivalence of the new type variable
                    newTypeVariable.EquivalenceClass = newEquivalenceClass;
                    newTypeVariable.ValidTypeExpression = false;
                }
                else // * Otherwise, the old one is kept
                    newEquivalenceClass.typeVariables[oldPair.Key] = oldPair.Value;
            }
            // * Finally, we update all the equivalence classes of the substitution if its exists
            if (newEquivalenceClass.substitution != null)
                newEquivalenceClass.substitution.UpdateEquivalenceClass(typeVariableMappings, new List<TypeExpression>());
        }
        #endregion

        // SSA

        #region CloneTypeVariables()
        internal void CloneTypeVariables(IDictionary<int, TypeVariable> clonedTypeVariables, IList<EquivalenceClass> equivalenceClasses, MethodType methodAnalyzed) {
            // * Checks if the equivalence class has been already cloned
            if (equivalenceClasses.Contains(this))
                return;
            // * Adds class equivalence
            equivalenceClasses.Add(this);
            // * Clones, but not updates, the substitution
            if (this.substitution!=null)
                this.substitution.Clone(clonedTypeVariables, equivalenceClasses, methodAnalyzed);
            // * Clones all the type variables in the equivalence class
            foreach (KeyValuePair<int, TypeVariable> pair in this.typeVariables)
                pair.Value.Clone(clonedTypeVariables, equivalenceClasses, methodAnalyzed);
        }
        #endregion

        // Loop Detection

        public bool Remove(TypeVariable toRemove) {
            return this.typeVariables.Remove(toRemove.Variable);
        }
    }
}