mcs/class/referencesource/System.Data.Entity/System/Data/Query/InternalTrees/Vars.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="Vars.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  Microsoft
   7 // @backupOwner Microsoft
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections;
  12 using System.Collections.Generic;
  13 using System.Data.Metadata.Edm;
  14 using System.Diagnostics;
  15 using System.Globalization;
  16 using System.Text;
  17
  18 namespace System.Data.Query.InternalTrees
  19 {
  20     /// <summary>
  21     /// Types of variable
  22     /// </summary>
  23     internal enum VarType
  24     {
  25         /// <summary>
  26         /// a parameter
  27         /// </summary>
  28         Parameter,
  29
  30         /// <summary>
  31         /// Column of a table
  32         /// </summary>
  33         Column,
  34
  35         /// <summary>
  36         /// A Computed var
  37         /// </summary>
  38         Computed,
  39
  40         /// <summary>
  41         /// Var for SetOps (Union, Intersect, Except)
  42         /// </summary>
  43         SetOp,
  44
  45         /// <summary>
  46         /// NotValid
  47         /// </summary>
  48         NotValid
  49     }
  50
  51     /// <summary>
  52     /// Same as a ValRef in SqlServer. I just like changing names :-)
  53     /// </summary>
  54     internal abstract class Var
  55     {
  56         int m_id;
  57         VarType m_varType;
  58         TypeUsage m_type;
  59
  60         internal Var(int id, VarType varType, TypeUsage type)
  61         {
  62             m_id = id;
  63             m_varType = varType;
  64             m_type = type;
  65         }
  66
  67         /// <summary>
  68         /// Id of this var
  69         /// </summary>
  70         internal int Id { get { return m_id; } }
  71
  72         /// <summary>
  73         /// Kind of Var
  74         /// </summary>
  75         internal VarType VarType { get { return m_varType; } }
  76
  77         /// <summary>
  78         /// Datatype of this Var
  79         /// </summary>
  80         internal TypeUsage Type { get { return m_type; } }
  81
  82         /// <summary>
  83         /// Try to get the name of this Var.
  84         /// </summary>
  85         /// <param name="name"></param>
  86         /// <returns></returns>
  87         internal virtual bool TryGetName(out string name)
  88         {
  89             name = null;
  90             return false;
  91         }
  92
  93         /// <summary>
  94         /// Debugging support
  95         /// </summary>
  96         /// <returns></returns>
  97         public override string ToString()
  98         {
  99             return String.Format(CultureInfo.InvariantCulture, "{0}", this.Id); ;
 100         }
 101     }
 102
 103     /// <summary>
 104     /// Describes a query parameter
 105     /// </summary>
 106     internal sealed class ParameterVar : Var
 107     {
 108         string m_paramName;
 109
 110         internal ParameterVar(int id, TypeUsage type, string paramName)
 111             : base(id, VarType.Parameter, type)
 112         {
 113             m_paramName = paramName;
 114         }
 115
 116         /// <summary>
 117         /// Name of the parameter
 118         /// </summary>
 119         internal string ParameterName { get { return m_paramName; } }
 120
 121         /// <summary>
 122         /// Get the name of this Var
 123         /// </summary>
 124         /// <param name="name"></param>
 125         /// <returns></returns>
 126         internal override bool TryGetName(out string name)
 127         {
 128             name = this.ParameterName;
 129             return true;
 130         }
 131     }
 132
 133     /// <summary>
 134     /// Describes a column of a table
 135     /// </summary>
 136     internal sealed class ColumnVar : Var
 137     {
 138         ColumnMD m_columnMetadata;
 139         Table m_table;
 140
 141         /// <summary>
 142         /// Constructor
 143         /// </summary>
 144         /// <param name="id"></param>
 145         /// <param name="table"></param>
 146         /// <param name="columnMetadata"></param>
 147         internal ColumnVar(int id, Table table, ColumnMD columnMetadata)
 148             : base(id, VarType.Column, columnMetadata.Type)
 149         {
 150             m_table = table;
 151             m_columnMetadata = columnMetadata;
 152         }
 153
 154         /// <summary>
 155         /// The table instance containing this column reference
 156         /// </summary>
 157         internal Table Table { get { return m_table; } }
 158
 159         /// <summary>
 160         /// The column metadata for this column
 161         /// </summary>
 162         internal ColumnMD ColumnMetadata { get { return m_columnMetadata; } }
 163
 164         /// <summary>
 165         /// Get the name of this column var
 166         /// </summary>
 167         /// <param name="name"></param>
 168         /// <returns></returns>
 169         internal override bool TryGetName(out string name)
 170         {
 171             name = m_columnMetadata.Name;
 172             return true;
 173         }
 174     }
 175
 176     /// <summary>
 177     /// A computed expression. Defined by a VarDefOp
 178     /// </summary>
 179     internal sealed class ComputedVar : Var
 180     {
 181         internal ComputedVar(int id, TypeUsage type) : base(id, VarType.Computed, type)
 182         {
 183         }
 184     }
 185
 186     /// <summary>
 187     /// A SetOp Var - used as the output var for set operations (Union, Intersect, Except)
 188     /// </summary>
 189     internal sealed class SetOpVar : Var
 190     {
 191         internal SetOpVar(int id, TypeUsage type) : base(id, VarType.SetOp, type) { }
 192     }
 193
 194     //
 195
 196     /// <summary>
 197     /// A VarVec is a compressed representation of a set of variables - with no duplicates
 198     /// and no ordering
 199     ///
 200     /// A VarVec should be used in many places where we expect a number of vars to be
 201     /// passed around; and we don't care particularly about the ordering of the vars
 202     ///
 203     /// This is obviously not suitable for representing sort keys, but is still
 204     /// reasonable for representing group by keys, and a variety of others.
 205     ///
 206     /// </summary>
 207     internal class VarVec : IEnumerable<Var>
 208     {
 209         #region Nested Classes
 210         /// <summary>
 211         /// A VarVec enumerator is a specialized enumerator for a VarVec.
 212         /// </summary>
 213         internal class VarVecEnumerator : IEnumerator<Var>, IDisposable
 214         {
 215             #region private state
 216             private int m_position;
 217             private Command m_command;
 218             private BitArray m_bitArray;
 219             #endregion
 220
 221             #region Constructors
 222             /// <summary>
 223             /// Constructs a new enumerator for the specified Vec
 224             /// </summary>
 225             /// <param name="vec"></param>
 226             internal VarVecEnumerator(VarVec vec)
 227             {
 228                 Init(vec);
 229             }
 230             #endregion
 231
 232             #region public surface
 233             /// <summary>
 234             /// Initialize the enumerator to enumerate over the supplied Vec
 235             /// </summary>
 236             /// <param name="vec"></param>
 237             internal void Init(VarVec vec)
 238             {
 239                 m_position = -1;
 240                 m_command = vec.m_command;
 241                 m_bitArray = vec.m_bitVector;
 242             }
 243             #endregion
 244
 245             #region IEnumerator<Var> Members
 246             /// <summary>
 247             /// Get the Var at the current position
 248             /// </summary>
 249             public Var Current
 250             {
 251                 get { return (m_position >= 0 && m_position < m_bitArray.Count) ? m_command.GetVar(m_position) : (Var)null; }
 252             }
 253             #endregion
 254
 255             #region IEnumerator Members
 256             object IEnumerator.Current
 257             {
 258                 get { return Current;}
 259             }
 260
 261             /// <summary>
 262             /// Move to the next position
 263             /// </summary>
 264             /// <returns></returns>
 265             public bool MoveNext()
 266             {
 267                 m_position++;
 268                 for (; m_position < m_bitArray.Count; m_position++)
 269                 {
 270                     if (m_bitArray[m_position])
 271                     {
 272                         return true;
 273                     }
 274                 }
 275                 return false;
 276             }
 277
 278             /// <summary>
 279             /// Reset enumerator to start off again
 280             /// </summary>
 281             public void Reset()
 282             {
 283                 m_position = -1;
 284             }
 285             #endregion
 286
 287             #region IDisposable Members
 288             /// <summary>
 289             /// Dispose of the current enumerator - return it to the Command
 290             /// </summary>
 291             public void Dispose()
 292             {
 293                 // Technically, calling GC.SuppressFinalize is not required because the class does not
 294                 // have a finalizer, but it does no harm, protects against the case where a finalizer is added
 295                 // in the future, and prevents an FxCop warning.
 296                 GC.SuppressFinalize(this);
 297                 m_bitArray = null;
 298                 m_command.ReleaseVarVecEnumerator(this);
 299             }
 300
 301             #endregion
 302         }
 303         #endregion
 304
 305         #region public methods
 306         internal void Clear()
 307         {
 308             m_bitVector.Length = 0;
 309         }
 310
 311         internal void And(VarVec other)
 312         {
 313             Align(other);
 314             m_bitVector.And(other.m_bitVector);
 315         }
 316
 317         internal void Or(VarVec other)
 318         {
 319             Align(other);
 320             m_bitVector.Or(other.m_bitVector);
 321         }
 322
 323         /// <summary>
 324         /// Computes (this Minus other) by performing (this And (Not(other)))
 325         /// A temp VarVec is used and released at the end of the operation
 326         /// </summary>
 327         /// <param name="other"></param>
 328         internal void Minus(VarVec other)
 329         {
 330             VarVec tmp = m_command.CreateVarVec(other);
 331             tmp.m_bitVector.Length = m_bitVector.Length;
 332             tmp.m_bitVector.Not();
 333             this.And(tmp);
 334             m_command.ReleaseVarVec(tmp);
 335         }
 336
 337         /// <summary>
 338         /// Does this have a non-zero overlap with the other vec
 339         /// </summary>
 340         /// <param name="other"></param>
 341         /// <returns></returns>
 342         internal bool Overlaps(VarVec other)
 343         {
 344             VarVec otherCopy = m_command.CreateVarVec(other);
 345             otherCopy.And(this);
 346             bool overlaps = !otherCopy.IsEmpty;
 347             m_command.ReleaseVarVec(otherCopy);
 348             return overlaps;
 349         }
 350
 351         /// <summary>
 352         /// Does this Vec include every var in the other vec?
 353         /// Written this way deliberately under the assumption that "other"
 354         /// is a relatively small vec
 355         /// </summary>
 356         /// <param name="other"></param>
 357         /// <returns></returns>
 358         internal bool Subsumes(VarVec other)
 359         {
 360             for (int i = 0; i < other.m_bitVector.Count; i++)
 361             {
 362                 if (other.m_bitVector[i] &&
 363                     ((i >= this.m_bitVector.Count) || !this.m_bitVector[i]))
 364                 {
 365                     return false;
 366                 }
 367             }
 368             return true;
 369         }
 370
 371         internal void InitFrom(VarVec other)
 372         {
 373             this.Clear();
 374             this.m_bitVector.Length = other.m_bitVector.Length;
 375             this.m_bitVector.Or(other.m_bitVector);
 376         }
 377
 378         internal void InitFrom(IEnumerable<Var> other)
 379         {
 380             InitFrom(other, false);
 381         }
 382
 383         internal void InitFrom(IEnumerable<Var> other, bool ignoreParameters)
 384         {
 385             this.Clear();
 386             foreach (Var v in other)
 387             {
 388                 if (!ignoreParameters || (v.VarType != VarType.Parameter))
 389                 {
 390                     this.Set(v);
 391                 }
 392             }
 393         }
 394
 395         /// <summary>
 396         /// The enumerator pattern
 397         /// </summary>
 398         /// <returns></returns>
 399         public IEnumerator<Var> GetEnumerator()
 400         {
 401             return m_command.GetVarVecEnumerator(this);
 402         }
 403
 404         IEnumerator IEnumerable.GetEnumerator()
 405         {
 406             return this.GetEnumerator();
 407         }
 408
 409         /// <summary>
 410         /// Number of vars in this set
 411         /// </summary>
 412         internal int Count
 413         {
 414             get
 415             {
 416                 int count = 0;
 417                 foreach (Var v in this)
 418                     count++;
 419                 return count;
 420             }
 421         }
 422
 423         internal bool IsSet(Var v)
 424         {
 425             Align(v.Id);
 426             return m_bitVector.Get(v.Id);
 427         }
 428         internal void Set(Var v)
 429         {
 430             Align(v.Id);
 431             m_bitVector.Set(v.Id, true);
 432         }
 433         internal void Clear(Var v)
 434         {
 435             Align(v.Id);
 436             m_bitVector.Set(v.Id, false);
 437         }
 438
 439         /// <summary>
 440         /// Is this Vec empty?
 441         /// </summary>
 442         internal bool IsEmpty
 443         {
 444             get { return this.First == null;}
 445         }
 446
 447         /// <summary>
 448         /// Get me the first var that is set
 449         /// </summary>
 450         internal Var First
 451         {
 452             get
 453             {
 454                 foreach (Var v in this)
 455                 {
 456                     return v;
 457                 }
 458                 return null;
 459             }
 460         }
 461
 462         /// <summary>
 463         /// Walk through the input varVec, replace any vars that have been "renamed" based
 464         /// on the input varMap, and return the new VarVec
 465         /// </summary>
 466         /// <param name="varMap">dictionary of renamed vars</param>
 467         /// <returns>a new VarVec</returns>
 468         internal VarVec Remap(Dictionary<Var, Var> varMap)
 469         {
 470             VarVec newVec = m_command.CreateVarVec();
 471             foreach (Var v in this)
 472             {
 473                 Var newVar;
 474                 if (!varMap.TryGetValue(v, out newVar))
 475                 {
 476                     newVar = v;
 477                 }
 478                 newVec.Set(newVar);
 479             }
 480             return newVec;
 481         }
 482
 483         #endregion
 484
 485         #region constructors
 486         internal VarVec(Command command)
 487         {
 488             m_bitVector = new BitArray(64);
 489             m_command = command;
 490         }
 491         #endregion
 492
 493         #region private methods
 494         private void Align(VarVec other)
 495         {
 496             if (other.m_bitVector.Count == this.m_bitVector.Count)
 497                 return;
 498             if (other.m_bitVector.Count > this.m_bitVector.Count)
 499             {
 500                 this.m_bitVector.Length = other.m_bitVector.Count;
 501             }
 502             else
 503             {
 504                 other.m_bitVector.Length = this.m_bitVector.Count;
 505             }
 506         }
 507         private void Align(int idx)
 508         {
 509             if (idx >= m_bitVector.Count)
 510             {
 511                 m_bitVector.Length = idx + 1;
 512             }
 513         }
 514
 515         /// <summary>
 516         /// Debugging support
 517         /// provide a string representation for debugging.
 518         /// <returns></returns>
 519         /// </summary>
 520         public override string ToString()
 521         {
 522             StringBuilder sb = new StringBuilder();
 523             string separator = String.Empty;
 524
 525             foreach (Var v in this)
 526             {
 527                 sb.AppendFormat(CultureInfo.InvariantCulture, "{0}{1}", separator, v.Id);
 528                 separator = ",";
 529             }
 530             return sb.ToString();
 531         }
 532         #endregion
 533
 534         #region private state
 535         private BitArray m_bitVector;
 536         private Command m_command;
 537         #endregion
 538
 539         #region Clone
 540         /// <summary>
 541         /// Create a clone of this vec
 542         /// </summary>
 543         /// <returns></returns>
 544         public VarVec Clone()
 545         {
 546             VarVec newVec = m_command.CreateVarVec();
 547             newVec.InitFrom(this);
 548             return newVec;
 549         }
 550
 551         #endregion
 552     }
 553
 554     /// <summary>
 555     /// An ordered list of Vars. Use this when you need an ordering.
 556     /// </summary>
 557     [DebuggerDisplay("{{{ToString()}}}")]
 558     internal class VarList : List<Var>
 559     {
 560         #region constructors
 561         /// <summary>
 562         /// Trivial constructor
 563         /// </summary>
 564         internal VarList() : base() { }
 565
 566         /// <summary>
 567         /// Not so trivial constructor
 568         /// </summary>
 569         /// <param name="vars"></param>
 570         internal VarList(IEnumerable<Var> vars) : base(vars) { }
 571         #endregion
 572
 573         #region public methods
 574
 575         /// <summary>
 576         /// Debugging support
 577         /// provide a string representation for debugging.
 578         /// <returns></returns>
 579         /// </summary>
 580         public override string ToString()
 581         {
 582             StringBuilder sb = new StringBuilder();
 583             string separator = String.Empty;
 584
 585             foreach (Var v in this)
 586             {
 587                 sb.AppendFormat(CultureInfo.InvariantCulture, "{0}{1}", separator, v.Id);
 588                 separator = ",";
 589             }
 590             return sb.ToString();
 591         }
 592
 593         #endregion
 594     }
 595
 596
 597     #region VarMap
 598     /// <summary>
 599     /// Helps map one variable to the next.
 600     /// </summary>
 601     internal class VarMap: Dictionary<Var, Var>
 602     {
 603         #region public surfaces
 604
 605         internal VarMap GetReverseMap()
 606         {
 607             VarMap reverseMap = new VarMap();
 608             foreach (KeyValuePair<Var, Var> kv in this)
 609             {
 610                 Var x;
 611                 // On the odd chance that a var is in the varMap more than once, the first one
 612                 // is going to be the one we want to use, because it might be the discriminator
 613                 // var;
 614                 if (!reverseMap.TryGetValue(kv.Value, out x))
 615                 {
 616                     reverseMap[kv.Value] = kv.Key;
 617                 }
 618             }
 619             return reverseMap;
 620         }
 621
 622         public override string ToString()
 623         {
 624             StringBuilder sb = new StringBuilder();
 625             string separator = string.Empty;
 626
 627             foreach (Var v in this.Keys)
 628             {
 629                 sb.AppendFormat(CultureInfo.InvariantCulture, "{0}({1},{2})", separator, v.Id, this[v].Id);
 630                 separator = ",";
 631             }
 632             return sb.ToString();
 633         }
 634
 635         #endregion
 636
 637         #region constructors
 638         internal VarMap() : base() { }
 639         #endregion
 640     }
 641     #endregion
 642 }