Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / Simplifier.cs / 1 / Simplifier.cs
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....]
// @backupOwner [....]
//---------------------------------------------------------------------
using System.Data.Common.Utils;
using System.Data.Mapping.ViewGeneration.Structures;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Data.Metadata.Edm;
using System.Linq;
namespace System.Data.Mapping.ViewGeneration {
// This class simplifies an extent's view. Given a view, runs the TM/SP
// rules to remove unnecessary self-joins or self-unions
internal class Simplifier : InternalBase {
#region Constructor
private Simplifier(CellNormalizer normalizer) {
m_normalizer = normalizer;
}
#endregion
#region Fields
private CellNormalizer m_normalizer;
#endregion
#region Exposed Methods
// effects: see CellTreeNode.Simplify below
internal static CellTreeNode Simplify(CellTreeNode rootNode, bool canBooleansOverlap) {
Simplifier simplifier = new Simplifier(rootNode.CellNormalizer);
return simplifier.SimplifyTree(rootNode, canBooleansOverlap);
}
// effects: Simplifies the tree rooted at rootNode and returns a new
// tree -- it ensures that the returned tree has at most one node for
// any particular extent unless the tree has nodes of the same extent
// embedded two leaves below LASJ or LOJ, e.g., if we have a tree
// (where Ni indicates a node for extent i - one Ni can be different
// from anohter Ni:
// [N0 IJ N1] LASJ N0 --> This will not be simplified
// canBooleansOverlap indicates whether an original input cell
// contributes to multiple nodes in this tree, e.g., V1 IJ V2 UNION V2 IJ V3
private CellTreeNode SimplifyTree(CellTreeNode rootNode, bool canBooleansOverlap) {
if (rootNode is LeafCellTreeNode) { // View already simple!
return rootNode;
}
Debug.Assert(rootNode.OpType == CellTreeOpType.LOJ || rootNode.OpType == CellTreeOpType.IJ ||
rootNode.OpType == CellTreeOpType.FOJ || rootNode.OpType == CellTreeOpType.Union ||
rootNode.OpType == CellTreeOpType.LASJ,
"Only handle these operations");
// Before we apply any rule, check if we can improve the opportunity to
// collapse the nodes
rootNode = RestructureTreeForMerges(rootNode);
List children = rootNode.Children;
Debug.Assert(children.Count > 0, "OpCellTreeNode has no children?");
// Apply recursively
for (int i = 0; i < children.Count; i++) {
children[i] = SimplifyTree(children[i], canBooleansOverlap);
}
// Essentially, we have a node with IJ, LOJ, U or FOJ type that
// has some children. Check if some of the children can be merged
// with one another using the corresponding TM/SP rule
// Ops such as IJ, Union and FOJ are associative, i.e., A op (B
// op C) is the same as (A op B) op C. This is not true for LOJ
// and LASJ
bool isAssociativeOp = CellTreeNode.IsAssociativeOp(rootNode.OpType);
if (isAssociativeOp) {
// Group all the leaf cells of an extent together so that we can
// later simply run through them without running nested loops
// We do not do this for LOJ/LASJ nodes since LOJ (LASJ) is not commutative
// (or associative);
children = GroupLeafChildrenByExtent(children);
} else {
children = GroupNonAssociativeLeafChildren(children);
}
// childrenSet keeps track of the children that need to be procesed/partitioned
OpCellTreeNode newNode = new OpCellTreeNode(m_normalizer, rootNode.OpType);
CellTreeNode lastChild = null;
bool skipRest = false;
foreach (CellTreeNode child in children) {
if (lastChild == null) {
// First time in the loop. Just set lastChild
lastChild = child;
continue;
}
bool mergedOk = false;
// try to merge lastChild and child
if (false == skipRest && lastChild.OpType == CellTreeOpType.Leaf &&
child.OpType == CellTreeOpType.Leaf) {
// Both are cell queries. Can try to merge them
// We do not add lastChild since it could merge
// further. It will be added in a later loop or outside the loop
mergedOk = TryMergeCellQueries(rootNode.OpType, canBooleansOverlap, ref lastChild, child);
}
if (false == mergedOk) {
// No merge occurred. Simply add the previous child as it
// is (Note lastChild will be added in the next loop or if
// the loop finishes, outside the loop
newNode.Add(lastChild);
lastChild = child;
if (false == isAssociativeOp) {
// LOJ is not associative:
// (P loj PA) loj PO != P loj (PA loj PO). The RHS does not have
// Persons who have orders but no addresses
skipRest = true;
}
}
}
newNode.Add(lastChild);
CellTreeNode result = newNode.AssociativeFlatten();
return result;
}
#endregion
#region Private Methods
// effects: Restructure tree so that it is better positioned for merges
private CellTreeNode RestructureTreeForMerges(CellTreeNode rootNode) {
List children = rootNode.Children;
if (CellTreeNode.IsAssociativeOp(rootNode.OpType) == false || children.Count <= 1) {
return rootNode;
}
// If this node's operator is associative and each child's
// operator is also associative, check if there is a common set
// of leaf nodes across all grandchildren
Set commonGrandChildren = GetCommonGrandChildren(children);
if (commonGrandChildren == null) {
return rootNode;
}
CellTreeOpType commonChildOpType = children[0].OpType;
// We do have the structure that we are looking for
// (common op2 gc2) op1 (common op2 gc3) op1 (common op2 gc4) becomes
// common op2 (gc2 op1 gc3 op1 gc4)
// e.g., (A IJ B IJ X IJ Y) UNION (A IJ B IJ Y IJ Z) UNION (A IJ B IJ R IJ S)
// becomes A IJ B IJ ((X IJ Y) UNION (Y IJ Z) UNION (R IJ S))
// From each child in children, get the nodes other than commonGrandChildren - these are gc2, gc3, ...
// Each gc2 must be connected by op2 as before, i.e., ABC + ACD = A(BC + CD)
// All children must be OpCellTreeNodes!
List newChildren = new List(children.Count);
foreach (OpCellTreeNode child in children) {
// Remove all children in child that belong to commonGrandChildren
// All grandChildren must be leaf nodes at this point
List newGrandChildren = new List(child.Children.Count);
foreach (LeafCellTreeNode grandChild in child.Children) {
if (commonGrandChildren.Contains(grandChild) == false) {
newGrandChildren.Add(grandChild);
}
}
// In the above example, child.OpType is IJ
Debug.Assert(child.OpType == commonChildOpType);
OpCellTreeNode newChild = new OpCellTreeNode(m_normalizer, child.OpType,
Helpers.AsSuperTypeList(newGrandChildren));
newChildren.Add(newChild);
}
// Connect gc2 op1 gc3 op1 gc4 - op1 is UNION in this
// ((X IJ Y) UNION (Y IJ Z) UNION (R IJ S))
// rootNode.Type is UNION
CellTreeNode remainingNodes = new OpCellTreeNode(m_normalizer, rootNode.OpType,
Helpers.AsSuperTypeList(newChildren));
// Take the common grandchildren and connect via commonChildType
// i.e., A IJ B
CellTreeNode commonNodes = new OpCellTreeNode(m_normalizer, commonChildOpType,
Helpers.AsSuperTypeList(commonGrandChildren));
// Connect both by commonChildType
CellTreeNode result = new OpCellTreeNode(m_normalizer, commonChildOpType,
new CellTreeNode[] { commonNodes, remainingNodes });
result = result.AssociativeFlatten();
return result;
}
// effects: Given a set of nodes, determines if all nodes are the exact same associative opType AND
// there are leaf children that are common across the children "nodes". If there are any,
// returns them. Else return null
private static Set GetCommonGrandChildren(List nodes) {
Set commonLeaves = null;
// We could make this general and apply recursively but we don't for now
// Look for a tree of the form: (common op2 gc2) op1 (common op2 gc3) op1 (common op2 gc4)
// e.g., (A IJ B IJ X IJ Y) UNION (A IJ B IJ Y IJ Z) UNION (A IJ B IJ R IJ S)
// Where op1 and op2 are associative and common, gc2 etc are leaf nodes
CellTreeOpType commonChildOpType = CellTreeOpType.Leaf;
foreach (CellTreeNode node in nodes) {
OpCellTreeNode opNode = node as OpCellTreeNode;
if (opNode == null) {
return null;
}
Debug.Assert(opNode.OpType != CellTreeOpType.Leaf, "Leaf type for op cell node?");
// Now check for whether the op is associative and the same as the previous one
if (commonChildOpType == CellTreeOpType.Leaf) {
commonChildOpType = opNode.OpType;
} else if (CellTreeNode.IsAssociativeOp(opNode.OpType) == false || commonChildOpType != opNode.OpType) {
return null;
}
// Make sure all the children are leaf children
Set nodeChildrenSet = new Set(LeafCellTreeNode.EqualityComparer);
foreach (CellTreeNode grandChild in opNode.Children) {
LeafCellTreeNode leafGrandChild = grandChild as LeafCellTreeNode;
if (leafGrandChild == null) {
return null;
}
nodeChildrenSet.Add(leafGrandChild);
}
if (commonLeaves == null) {
commonLeaves = nodeChildrenSet;
} else {
commonLeaves.Intersect(nodeChildrenSet);
}
}
if (commonLeaves.Count == 0) {
// No restructuring possible
return null;
}
return commonLeaves;
}
// effects: Given a list of node, produces a new list in which all
// leaf nodes of the same extent are adjacent to each other. Non-leaf
// nodes are also adjacent to each other. CHANGE_[....]_IMPROVE: Merge with GroupByRightExtent
private static List GroupLeafChildrenByExtent(List nodes) {
// Keep track of leaf cells for each extent
KeyToListMap extentMap =
new KeyToListMap(EqualityComparer.Default);
List newNodes = new List();
foreach (CellTreeNode node in nodes) {
LeafCellTreeNode leafNode = node as LeafCellTreeNode;
// All non-leaf nodes are added to the result now
// leaf nodes are added outside the loop
if (leafNode != null) {
extentMap.Add(leafNode.RightCellQuery.Extent, leafNode);
} else {
newNodes.Add(node);
}
}
// Go through the map and add the leaf children
newNodes.AddRange(extentMap.AllValues);
return newNodes;
}
// effects: A restrictive version of GroupLeafChildrenByExtent --
// only for LASJ and LOJ nodes (works for LOJ only when A LOJ B LOJ C
// s.t., B and C are subsets of A -- in our case that is how LOJs are constructed
private static List GroupNonAssociativeLeafChildren(List nodes) {
// Keep track of leaf cells for each extent ignoring the 0th child
KeyToListMap extentMap =
new KeyToListMap(EqualityComparer.Default);
List newNodes = new List();
List nonLeafNodes = new List();
// Add the 0th child
newNodes.Add(nodes[0]);
for (int i = 1; i < nodes.Count; i++) {
CellTreeNode node = nodes[i];
LeafCellTreeNode leafNode = node as LeafCellTreeNode;
// All non-leaf nodes are added to the result now
// leaf nodes are added outside the loop
if (leafNode != null) {
extentMap.Add(leafNode.RightCellQuery.Extent, leafNode);
} else {
nonLeafNodes.Add(node);
}
}
// Go through the map and add the leaf children
// If a group of nodes exists for the 0th node's extent -- place
// that group first
LeafCellTreeNode firstNode = nodes[0] as LeafCellTreeNode;
if (firstNode != null) {
EntitySetBase firstExtent = firstNode.RightCellQuery.Extent;
if (extentMap.ContainsKey(firstExtent)) {
newNodes.AddRange(extentMap.ListForKey(firstExtent));
// Remove this set from the map
extentMap.RemoveKey(firstExtent);
}
}
newNodes.AddRange(extentMap.AllValues);
newNodes.AddRange(nonLeafNodes);
return newNodes;
}
// requires: node1 and node2 are two children of the same parent
// connected by opType
// effects: Given two cell tree nodes, node1 and node2, runs the
// TM/SP rule on them to merge them (if they belong to the same
// extent). Returns true if the merge succeeds
private bool TryMergeCellQueries(CellTreeOpType opType, bool canBooleansOverlap, ref CellTreeNode node1,
CellTreeNode node2) {
LeafCellTreeNode leaf1 = node1 as LeafCellTreeNode;
LeafCellTreeNode leaf2 = node2 as LeafCellTreeNode;
Debug.Assert(leaf1 != null, "Merge only possible on leaf nodes (1)");
Debug.Assert(leaf2 != null, "Merge only possible on leaf nodes (2)");
CellQuery node1Query = leaf1.RightCellQuery;
CellQuery node2Query = leaf2.RightCellQuery;
// Try to merge them using the TM/SP rule for opType
CellQuery mergedCellQuery;
// Since we are always simplifying the cell queries of the right
// side, we need to get the rightdomainmap
if (false == node1Query.TryMerge(node2Query, opType, canBooleansOverlap, m_normalizer.MemberMaps.RightDomainMap, out mergedCellQuery)) {
return false;
}
// Create a temporary node and add the two children
// so that we can get the merged selectiondomains and attributes
// Note that temp.SelectionDomain below determines the domain
// based on the opType, e.g., for IJ, it intersects the
// multiconstants of all the children
OpCellTreeNode temp = new OpCellTreeNode(m_normalizer, opType);
temp.Add(node1);
temp.Add(node2);
// Note: We are losing the original cell number information here and the line number information
// But we will not raise any
// We do not create CellExpressions with LOJ, FOJ - canBooleansOverlap is true for validation
CellTreeOpType inputOpType = opType;
if (canBooleansOverlap == false && (opType == CellTreeOpType.FOJ || opType == CellTreeOpType.LOJ)) {
inputOpType = CellTreeOpType.IJ;
}
LeftCellWrapper wrapper = new LeftCellWrapper(leaf1.LeftCellWrapper.SchemaContext, temp.Attributes,
temp.LeftFragmentQuery,
mergedCellQuery, m_normalizer.MemberMaps,
leaf1.LeftCellWrapper.Cells.Concat(leaf2.LeftCellWrapper.Cells));
node1 = new LeafCellTreeNode(m_normalizer, wrapper, temp.RightFragmentQuery);
return true;
}
#endregion
#region String methods
internal override void ToCompactString(StringBuilder builder) {
m_normalizer.MemberMaps.ProjectedSlotMap.ToCompactString(builder);
}
#endregion
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....]
// @backupOwner [....]
//---------------------------------------------------------------------
using System.Data.Common.Utils;
using System.Data.Mapping.ViewGeneration.Structures;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Data.Metadata.Edm;
using System.Linq;
namespace System.Data.Mapping.ViewGeneration {
// This class simplifies an extent's view. Given a view, runs the TM/SP
// rules to remove unnecessary self-joins or self-unions
internal class Simplifier : InternalBase {
#region Constructor
private Simplifier(CellNormalizer normalizer) {
m_normalizer = normalizer;
}
#endregion
#region Fields
private CellNormalizer m_normalizer;
#endregion
#region Exposed Methods
// effects: see CellTreeNode.Simplify below
internal static CellTreeNode Simplify(CellTreeNode rootNode, bool canBooleansOverlap) {
Simplifier simplifier = new Simplifier(rootNode.CellNormalizer);
return simplifier.SimplifyTree(rootNode, canBooleansOverlap);
}
// effects: Simplifies the tree rooted at rootNode and returns a new
// tree -- it ensures that the returned tree has at most one node for
// any particular extent unless the tree has nodes of the same extent
// embedded two leaves below LASJ or LOJ, e.g., if we have a tree
// (where Ni indicates a node for extent i - one Ni can be different
// from anohter Ni:
// [N0 IJ N1] LASJ N0 --> This will not be simplified
// canBooleansOverlap indicates whether an original input cell
// contributes to multiple nodes in this tree, e.g., V1 IJ V2 UNION V2 IJ V3
private CellTreeNode SimplifyTree(CellTreeNode rootNode, bool canBooleansOverlap) {
if (rootNode is LeafCellTreeNode) { // View already simple!
return rootNode;
}
Debug.Assert(rootNode.OpType == CellTreeOpType.LOJ || rootNode.OpType == CellTreeOpType.IJ ||
rootNode.OpType == CellTreeOpType.FOJ || rootNode.OpType == CellTreeOpType.Union ||
rootNode.OpType == CellTreeOpType.LASJ,
"Only handle these operations");
// Before we apply any rule, check if we can improve the opportunity to
// collapse the nodes
rootNode = RestructureTreeForMerges(rootNode);
List children = rootNode.Children;
Debug.Assert(children.Count > 0, "OpCellTreeNode has no children?");
// Apply recursively
for (int i = 0; i < children.Count; i++) {
children[i] = SimplifyTree(children[i], canBooleansOverlap);
}
// Essentially, we have a node with IJ, LOJ, U or FOJ type that
// has some children. Check if some of the children can be merged
// with one another using the corresponding TM/SP rule
// Ops such as IJ, Union and FOJ are associative, i.e., A op (B
// op C) is the same as (A op B) op C. This is not true for LOJ
// and LASJ
bool isAssociativeOp = CellTreeNode.IsAssociativeOp(rootNode.OpType);
if (isAssociativeOp) {
// Group all the leaf cells of an extent together so that we can
// later simply run through them without running nested loops
// We do not do this for LOJ/LASJ nodes since LOJ (LASJ) is not commutative
// (or associative);
children = GroupLeafChildrenByExtent(children);
} else {
children = GroupNonAssociativeLeafChildren(children);
}
// childrenSet keeps track of the children that need to be procesed/partitioned
OpCellTreeNode newNode = new OpCellTreeNode(m_normalizer, rootNode.OpType);
CellTreeNode lastChild = null;
bool skipRest = false;
foreach (CellTreeNode child in children) {
if (lastChild == null) {
// First time in the loop. Just set lastChild
lastChild = child;
continue;
}
bool mergedOk = false;
// try to merge lastChild and child
if (false == skipRest && lastChild.OpType == CellTreeOpType.Leaf &&
child.OpType == CellTreeOpType.Leaf) {
// Both are cell queries. Can try to merge them
// We do not add lastChild since it could merge
// further. It will be added in a later loop or outside the loop
mergedOk = TryMergeCellQueries(rootNode.OpType, canBooleansOverlap, ref lastChild, child);
}
if (false == mergedOk) {
// No merge occurred. Simply add the previous child as it
// is (Note lastChild will be added in the next loop or if
// the loop finishes, outside the loop
newNode.Add(lastChild);
lastChild = child;
if (false == isAssociativeOp) {
// LOJ is not associative:
// (P loj PA) loj PO != P loj (PA loj PO). The RHS does not have
// Persons who have orders but no addresses
skipRest = true;
}
}
}
newNode.Add(lastChild);
CellTreeNode result = newNode.AssociativeFlatten();
return result;
}
#endregion
#region Private Methods
// effects: Restructure tree so that it is better positioned for merges
private CellTreeNode RestructureTreeForMerges(CellTreeNode rootNode) {
List children = rootNode.Children;
if (CellTreeNode.IsAssociativeOp(rootNode.OpType) == false || children.Count <= 1) {
return rootNode;
}
// If this node's operator is associative and each child's
// operator is also associative, check if there is a common set
// of leaf nodes across all grandchildren
Set commonGrandChildren = GetCommonGrandChildren(children);
if (commonGrandChildren == null) {
return rootNode;
}
CellTreeOpType commonChildOpType = children[0].OpType;
// We do have the structure that we are looking for
// (common op2 gc2) op1 (common op2 gc3) op1 (common op2 gc4) becomes
// common op2 (gc2 op1 gc3 op1 gc4)
// e.g., (A IJ B IJ X IJ Y) UNION (A IJ B IJ Y IJ Z) UNION (A IJ B IJ R IJ S)
// becomes A IJ B IJ ((X IJ Y) UNION (Y IJ Z) UNION (R IJ S))
// From each child in children, get the nodes other than commonGrandChildren - these are gc2, gc3, ...
// Each gc2 must be connected by op2 as before, i.e., ABC + ACD = A(BC + CD)
// All children must be OpCellTreeNodes!
List newChildren = new List(children.Count);
foreach (OpCellTreeNode child in children) {
// Remove all children in child that belong to commonGrandChildren
// All grandChildren must be leaf nodes at this point
List newGrandChildren = new List(child.Children.Count);
foreach (LeafCellTreeNode grandChild in child.Children) {
if (commonGrandChildren.Contains(grandChild) == false) {
newGrandChildren.Add(grandChild);
}
}
// In the above example, child.OpType is IJ
Debug.Assert(child.OpType == commonChildOpType);
OpCellTreeNode newChild = new OpCellTreeNode(m_normalizer, child.OpType,
Helpers.AsSuperTypeList(newGrandChildren));
newChildren.Add(newChild);
}
// Connect gc2 op1 gc3 op1 gc4 - op1 is UNION in this
// ((X IJ Y) UNION (Y IJ Z) UNION (R IJ S))
// rootNode.Type is UNION
CellTreeNode remainingNodes = new OpCellTreeNode(m_normalizer, rootNode.OpType,
Helpers.AsSuperTypeList(newChildren));
// Take the common grandchildren and connect via commonChildType
// i.e., A IJ B
CellTreeNode commonNodes = new OpCellTreeNode(m_normalizer, commonChildOpType,
Helpers.AsSuperTypeList(commonGrandChildren));
// Connect both by commonChildType
CellTreeNode result = new OpCellTreeNode(m_normalizer, commonChildOpType,
new CellTreeNode[] { commonNodes, remainingNodes });
result = result.AssociativeFlatten();
return result;
}
// effects: Given a set of nodes, determines if all nodes are the exact same associative opType AND
// there are leaf children that are common across the children "nodes". If there are any,
// returns them. Else return null
private static Set GetCommonGrandChildren(List nodes) {
Set commonLeaves = null;
// We could make this general and apply recursively but we don't for now
// Look for a tree of the form: (common op2 gc2) op1 (common op2 gc3) op1 (common op2 gc4)
// e.g., (A IJ B IJ X IJ Y) UNION (A IJ B IJ Y IJ Z) UNION (A IJ B IJ R IJ S)
// Where op1 and op2 are associative and common, gc2 etc are leaf nodes
CellTreeOpType commonChildOpType = CellTreeOpType.Leaf;
foreach (CellTreeNode node in nodes) {
OpCellTreeNode opNode = node as OpCellTreeNode;
if (opNode == null) {
return null;
}
Debug.Assert(opNode.OpType != CellTreeOpType.Leaf, "Leaf type for op cell node?");
// Now check for whether the op is associative and the same as the previous one
if (commonChildOpType == CellTreeOpType.Leaf) {
commonChildOpType = opNode.OpType;
} else if (CellTreeNode.IsAssociativeOp(opNode.OpType) == false || commonChildOpType != opNode.OpType) {
return null;
}
// Make sure all the children are leaf children
Set nodeChildrenSet = new Set(LeafCellTreeNode.EqualityComparer);
foreach (CellTreeNode grandChild in opNode.Children) {
LeafCellTreeNode leafGrandChild = grandChild as LeafCellTreeNode;
if (leafGrandChild == null) {
return null;
}
nodeChildrenSet.Add(leafGrandChild);
}
if (commonLeaves == null) {
commonLeaves = nodeChildrenSet;
} else {
commonLeaves.Intersect(nodeChildrenSet);
}
}
if (commonLeaves.Count == 0) {
// No restructuring possible
return null;
}
return commonLeaves;
}
// effects: Given a list of node, produces a new list in which all
// leaf nodes of the same extent are adjacent to each other. Non-leaf
// nodes are also adjacent to each other. CHANGE_[....]_IMPROVE: Merge with GroupByRightExtent
private static List GroupLeafChildrenByExtent(List nodes) {
// Keep track of leaf cells for each extent
KeyToListMap extentMap =
new KeyToListMap(EqualityComparer.Default);
List newNodes = new List();
foreach (CellTreeNode node in nodes) {
LeafCellTreeNode leafNode = node as LeafCellTreeNode;
// All non-leaf nodes are added to the result now
// leaf nodes are added outside the loop
if (leafNode != null) {
extentMap.Add(leafNode.RightCellQuery.Extent, leafNode);
} else {
newNodes.Add(node);
}
}
// Go through the map and add the leaf children
newNodes.AddRange(extentMap.AllValues);
return newNodes;
}
// effects: A restrictive version of GroupLeafChildrenByExtent --
// only for LASJ and LOJ nodes (works for LOJ only when A LOJ B LOJ C
// s.t., B and C are subsets of A -- in our case that is how LOJs are constructed
private static List GroupNonAssociativeLeafChildren(List nodes) {
// Keep track of leaf cells for each extent ignoring the 0th child
KeyToListMap extentMap =
new KeyToListMap(EqualityComparer.Default);
List newNodes = new List();
List nonLeafNodes = new List();
// Add the 0th child
newNodes.Add(nodes[0]);
for (int i = 1; i < nodes.Count; i++) {
CellTreeNode node = nodes[i];
LeafCellTreeNode leafNode = node as LeafCellTreeNode;
// All non-leaf nodes are added to the result now
// leaf nodes are added outside the loop
if (leafNode != null) {
extentMap.Add(leafNode.RightCellQuery.Extent, leafNode);
} else {
nonLeafNodes.Add(node);
}
}
// Go through the map and add the leaf children
// If a group of nodes exists for the 0th node's extent -- place
// that group first
LeafCellTreeNode firstNode = nodes[0] as LeafCellTreeNode;
if (firstNode != null) {
EntitySetBase firstExtent = firstNode.RightCellQuery.Extent;
if (extentMap.ContainsKey(firstExtent)) {
newNodes.AddRange(extentMap.ListForKey(firstExtent));
// Remove this set from the map
extentMap.RemoveKey(firstExtent);
}
}
newNodes.AddRange(extentMap.AllValues);
newNodes.AddRange(nonLeafNodes);
return newNodes;
}
// requires: node1 and node2 are two children of the same parent
// connected by opType
// effects: Given two cell tree nodes, node1 and node2, runs the
// TM/SP rule on them to merge them (if they belong to the same
// extent). Returns true if the merge succeeds
private bool TryMergeCellQueries(CellTreeOpType opType, bool canBooleansOverlap, ref CellTreeNode node1,
CellTreeNode node2) {
LeafCellTreeNode leaf1 = node1 as LeafCellTreeNode;
LeafCellTreeNode leaf2 = node2 as LeafCellTreeNode;
Debug.Assert(leaf1 != null, "Merge only possible on leaf nodes (1)");
Debug.Assert(leaf2 != null, "Merge only possible on leaf nodes (2)");
CellQuery node1Query = leaf1.RightCellQuery;
CellQuery node2Query = leaf2.RightCellQuery;
// Try to merge them using the TM/SP rule for opType
CellQuery mergedCellQuery;
// Since we are always simplifying the cell queries of the right
// side, we need to get the rightdomainmap
if (false == node1Query.TryMerge(node2Query, opType, canBooleansOverlap, m_normalizer.MemberMaps.RightDomainMap, out mergedCellQuery)) {
return false;
}
// Create a temporary node and add the two children
// so that we can get the merged selectiondomains and attributes
// Note that temp.SelectionDomain below determines the domain
// based on the opType, e.g., for IJ, it intersects the
// multiconstants of all the children
OpCellTreeNode temp = new OpCellTreeNode(m_normalizer, opType);
temp.Add(node1);
temp.Add(node2);
// Note: We are losing the original cell number information here and the line number information
// But we will not raise any
// We do not create CellExpressions with LOJ, FOJ - canBooleansOverlap is true for validation
CellTreeOpType inputOpType = opType;
if (canBooleansOverlap == false && (opType == CellTreeOpType.FOJ || opType == CellTreeOpType.LOJ)) {
inputOpType = CellTreeOpType.IJ;
}
LeftCellWrapper wrapper = new LeftCellWrapper(leaf1.LeftCellWrapper.SchemaContext, temp.Attributes,
temp.LeftFragmentQuery,
mergedCellQuery, m_normalizer.MemberMaps,
leaf1.LeftCellWrapper.Cells.Concat(leaf2.LeftCellWrapper.Cells));
node1 = new LeafCellTreeNode(m_normalizer, wrapper, temp.RightFragmentQuery);
return true;
}
#endregion
#region String methods
internal override void ToCompactString(StringBuilder builder) {
m_normalizer.MemberMaps.ProjectedSlotMap.ToCompactString(builder);
}
#endregion
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- GPRECTF.cs
- ReachPageContentCollectionSerializerAsync.cs
- WebContext.cs
- DataGridViewRowDividerDoubleClickEventArgs.cs
- DataGridViewCheckBoxColumn.cs
- SettingsProviderCollection.cs
- UIElement3DAutomationPeer.cs
- GACIdentityPermission.cs
- TargetException.cs
- _AutoWebProxyScriptEngine.cs
- SetStoryboardSpeedRatio.cs
- DeflateEmulationStream.cs
- TextTreeTextNode.cs
- ControlPaint.cs
- SoapIncludeAttribute.cs
- EntityConnectionStringBuilder.cs
- CollectionEditor.cs
- NullableFloatMinMaxAggregationOperator.cs
- SpotLight.cs
- ReflectionServiceProvider.cs
- Events.cs
- Interop.cs
- FrameworkReadOnlyPropertyMetadata.cs
- EventDescriptor.cs
- ImageIndexConverter.cs
- ScopedKnownTypes.cs
- SystemIPInterfaceProperties.cs
- followingquery.cs
- XmlSerializerNamespaces.cs
- ResolvedKeyFrameEntry.cs
- DuplicateWaitObjectException.cs
- MissingMethodException.cs
- TextTrailingCharacterEllipsis.cs
- CqlBlock.cs
- DocumentViewerConstants.cs
- Light.cs
- TargetControlTypeAttribute.cs
- JsonEnumDataContract.cs
- CriticalHandle.cs
- StateWorkerRequest.cs
- DesignerRegionCollection.cs
- NonSerializedAttribute.cs
- InputElement.cs
- DeploymentSectionCache.cs
- RtfToken.cs
- DynamicArgumentDesigner.xaml.cs
- TextEditorParagraphs.cs
- ActiveXHelper.cs
- TemplateKeyConverter.cs
- SynchronizationLockException.cs
- ButtonField.cs
- ContextInformation.cs
- ToolStripDropDown.cs
- XamlBuildProvider.cs
- DesignerActionItem.cs
- SetterBase.cs
- BeginGetFileNameFromUserRequest.cs
- TreeBuilderXamlTranslator.cs
- ClientTargetSection.cs
- BamlLocalizableResourceKey.cs
- DataGridRowDetailsEventArgs.cs
- RangeBaseAutomationPeer.cs
- DataGridLinkButton.cs
- ValidationResults.cs
- GridViewSortEventArgs.cs
- ApplicationInfo.cs
- TemporaryBitmapFile.cs
- HyperLink.cs
- OleTxTransaction.cs
- CodeCommentStatement.cs
- SrgsSubset.cs
- SystemThemeKey.cs
- WebPartEditVerb.cs
- TransactionFlowAttribute.cs
- IndentedWriter.cs
- AnimationClock.cs
- EntityViewGenerationConstants.cs
- StylusButtonEventArgs.cs
- QuaternionRotation3D.cs
- ConsoleCancelEventArgs.cs
- Match.cs
- OnOperation.cs
- DataListGeneralPage.cs
- PlatformCulture.cs
- XmlQueryType.cs
- UpdatePanelTrigger.cs
- SQLSingle.cs
- AssemblyCache.cs
- TextBoxAutoCompleteSourceConverter.cs
- CapabilitiesPattern.cs
- GuidelineSet.cs
- FileSystemEventArgs.cs
- Encoder.cs
- Int32.cs
- HttpPostedFileBase.cs
- DataGridState.cs
- SecurityTokenSerializer.cs
- SQLGuid.cs
- AsyncCompletedEventArgs.cs
- DbModificationCommandTree.cs