mcs/class/referencesource/System.Data.Entity/System/Data/Query/PlanCompiler/VarRefManager.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="VarRefManager.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  [....]
   7 // @backupOwner [....]
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections.Generic;
  12 using System.Globalization;
  13 using System.Diagnostics;
  14 using System.Data.Query.InternalTrees;
  15
  16 namespace System.Data.Query.PlanCompiler
  17 {
  18     /// <summary>
  19     /// This is a halper module for <see cref="JoinElimination"/>
  20     /// The VarRefManager keeps track of the child-parent relationships in order to be able
  21     /// to decide whether a given var is referenced by children on right-side relatives of a given node.
  22     /// It is used in JoinElimination when deciding whether it is possible to eliminate the child table participating
  23     /// in a left-outer join when there is a 1 - 0..1 FK relationship.
  24     /// </summary>
  25     internal class VarRefManager
  26     {
  27         #region Internal State
  28         private Dictionary<Node, Node> m_nodeToParentMap;   //child-parent mapping
  29         private Dictionary<Node, int> m_nodeToSiblingNumber;   //the index of the given node among its siblings, i.e. 0 for a first child
  30         Command m_command;
  31         #endregion
  32
  33         #region Constructor
  34         /// <summary>
  35         /// Constructs a new VarRefManager given a command.
  36         /// </summary>
  37         /// <param name="command"></param>
  38         internal VarRefManager(Command command)
  39         {
  40             m_nodeToParentMap = new Dictionary<Node, Node>();
  41             m_nodeToSiblingNumber = new Dictionary<Node, int>();
  42             m_command = command;
  43         }
  44         #endregion
  45
  46         #region Public Methods
  47
  48         /// <summary>
  49         /// Tracks the information that the given node is a parent of its children (one level only)
  50         /// </summary>
  51         /// <param name="parent"></param>
  52         internal void AddChildren(Node parent)
  53         {
  54             for(int i=0; i< parent.Children.Count; i++)
  55             {
  56                 //We do not use add on purpose, we may be updating a child's parent after join elimination in a subtree
  57                 m_nodeToParentMap[parent.Children[i]] = parent;
  58                 m_nodeToSiblingNumber[parent.Children[i]] = i;
  59             }
  60         }
  61
  62         /// <summary>
  63         /// Determines whether any var from a given list of keys is referenced by any of defining node's right relatives,
  64         /// with the exception of the relatives brunching at the given targetJoinNode.
  65         /// </summary>
  66         /// <param name="keys">A list of vars to check for</param>
  67         /// <param name="definingNode">The node considered to be the defining node</param>
  68         /// <param name="targetJoinNode">The relatives branching at this node are skipped</param>
  69         /// <returns>False, only it can determine that not a single var from a given list of keys is referenced by any
  70         /// of defining node's right relatives, with the exception of the relatives brunching at the given targetJoinNode. </returns>
  71         internal bool HasKeyReferences(VarVec keys, Node definingNode, Node targetJoinNode)
  72         {
  73             Node currentChild = definingNode;
  74             Node parent;
  75             bool continueUp = true;
  76
  77             while (continueUp & m_nodeToParentMap.TryGetValue(currentChild, out parent))
  78             {
  79                 if (parent != targetJoinNode)
  80                 {
  81                     // Check the parent
  82                     if (HasVarReferencesShallow(parent, keys, m_nodeToSiblingNumber[currentChild], out continueUp))
  83                     {
  84                         return true;
  85                     }
  86
  87                     //Check all the siblings to the right
  88                     for (int i = m_nodeToSiblingNumber[currentChild] + 1; i < parent.Children.Count; i++)
  89                     {
  90                         if (parent.Children[i].GetNodeInfo(m_command).ExternalReferences.Overlaps(keys))
  91                         {
  92                             return true;
  93                         }
  94                     }
  95                 }
  96                 currentChild = parent;
  97             }
  98             return false;
  99         }
 100
 101         #endregion
 102
 103         #region Private Methods
 104         /// <summary>
 105         /// Checks whether the given node has references to any of the vars in the given VarVec.
 106         /// It only checks the given node, not its children.
 107         /// </summary>
 108         /// <param name="node">The node to check</param>
 109         /// <param name="vars">The list of vars to check for</param>
 110         /// <param name="childIndex">The index of the node's subree from which this var is coming.
 111         /// This is used for SetOp-s, to be able to locate the appropriate var map that will give the
 112         /// vars corresponding to the given once</param>
 113         /// <param name="continueUp">If the OpType of the node's Op is such that it 'hides' the input, i.e.
 114         /// the decision of whether the given vars are referenced can be made on this level, it returns true,
 115         /// false otherwise</param>
 116         /// <returns>True if the given node has references to any of the vars in the given VarVec, false otherwise</returns>
 117         private static bool HasVarReferencesShallow(Node node, VarVec vars, int childIndex, out bool continueUp)
 118         {
 119             switch (node.Op.OpType)
 120             {
 121                 case OpType.ConstrainedSort:
 122                 case OpType.Sort:
 123                     continueUp = true;
 124                     return HasVarReferences(((SortBaseOp)node.Op).Keys, vars);
 125
 126                 case OpType.Distinct:
 127                     continueUp = false;
 128                     return HasVarReferences(((DistinctOp)node.Op).Keys, vars);
 129
 130                 case OpType.Except:
 131                 case OpType.Intersect:
 132                 case OpType.UnionAll:
 133                     continueUp = false;
 134                     return HasVarReferences((SetOp)node.Op, vars, childIndex);
 135
 136                 case OpType.GroupBy:
 137                     continueUp = false;
 138                     return HasVarReferences(((GroupByOp)node.Op).Keys, vars);
 139
 140                 case OpType.PhysicalProject:
 141                     continueUp = false;
 142                     return HasVarReferences(((PhysicalProjectOp)node.Op).Outputs, vars);
 143
 144                 case OpType.Project:
 145                     continueUp = false;
 146                     return HasVarReferences(((ProjectOp)node.Op).Outputs, vars);
 147
 148                 default:
 149                     continueUp = true;
 150                     return false;
 151             }
 152         }
 153
 154         /// <summary>
 155         /// Does the gvien VarList overlap with the given VarVec
 156         /// </summary>
 157         /// <param name="listToCheck"></param>
 158         /// <param name="vars"></param>
 159         /// <returns></returns>
 160         private static bool HasVarReferences(VarList listToCheck, VarVec vars)
 161         {
 162             foreach (Var var in vars)
 163             {
 164                 if (listToCheck.Contains(var))
 165                 {
 166                     return true;
 167                 }
 168             }
 169             return false;
 170         }
 171
 172         /// <summary>
 173         /// Do the two given varVecs overlap
 174         /// </summary>
 175         /// <param name="listToCheck"></param>
 176         /// <param name="vars"></param>
 177         /// <returns></returns>
 178         private static bool HasVarReferences(VarVec listToCheck, VarVec vars)
 179         {
 180             return listToCheck.Overlaps(vars);
 181         }
 182
 183         /// <summary>
 184         /// Does the given list of sort keys contain a key with a var that is the given VarVec
 185         /// </summary>
 186         /// <param name="listToCheck"></param>
 187         /// <param name="vars"></param>
 188         /// <returns></returns>
 189         private static bool HasVarReferences(List<InternalTrees.SortKey> listToCheck, VarVec vars)
 190         {
 191             foreach (InternalTrees.SortKey key in listToCheck)
 192             {
 193                 if (vars.IsSet(key.Var))
 194                 {
 195                     return true;
 196                 }
 197             }
 198             return false;
 199         }
 200
 201         /// <summary>
 202         /// Does the list of outputs of the given SetOp contain a var
 203         /// from the given VarVec defined by the SetOp's child with the given index
 204         /// </summary>
 205         /// <param name="op"></param>
 206         /// <param name="vars"></param>
 207         /// <param name="index"></param>
 208         /// <returns></returns>
 209         private static bool HasVarReferences(SetOp op, VarVec vars, int index)
 210         {
 211             foreach (Var var in op.VarMap[index].Values)
 212             {
 213                 if (vars.IsSet(var))
 214                 {
 215                     return true;
 216                 }
 217             }
 218             return false;
 219         }
 220         #endregion
 221     }
 222 }