Code:
/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / Structures / JoinTreeNode.cs / 2 / JoinTreeNode.cs
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....]
// @backupOwner [....]
//---------------------------------------------------------------------
using System.Data.Common.Utils;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Globalization;
using System.Data.Metadata.Edm;
namespace System.Data.Mapping.ViewGeneration.Structures {
// JoinTreeNode represents a node in the tree that represents the FROM
// part of a cell query. It stores information such as whether the node
// is optional, whether the node joined, etc
internal abstract class JoinTreeNode : InternalBase {
#region Enums
///
/// How many times does a particular attribute node occur
/// E.g., for compositions, it can be Zero .. Many
///
internal enum Occurrences {
Zero,
Once,
Many
}
#endregion
#region Constructors/Factories
// effects: A private constructor where all the fields are initalized
protected JoinTreeNode(bool isOptional, IEnumerable children, MetadataWorkspace workspace) {
Debug.Assert(children != null, "Cannot have a null children list");
Debug.Assert(workspace != null, "MetadataWorkspace should never be null");
// m_memberPath is left as null. It will be cached when MemberPath is first called
m_isOptional = isOptional;
m_children = new List(children);
m_workspace = workspace;
// Set the parent field in each child
foreach (JoinTreeNode child in m_children) {
Debug.Assert(child.m_parent == null, "Child already has parent");
child.m_parent = this;
}
}
#endregion
#region Fields
// A cached path for optimization
private MemberPath m_memberPath;
// The nodes emanating from this node, e.g., if p is this node, a
// child could be p.pid or p.addrs
// All the children are members - so strongly type that
private List m_children;
// Reference to parent for easy navigation up and member path determination -- root has this as null
private JoinTreeNode m_parent;
// Whether the node restricts the number of tuples of its parent
// (isOptional is false iff restriction)
private bool m_isOptional;
private MetadataWorkspace m_workspace;
#endregion
#region Properties
// effects: Returns the full metadata path from the root extent to
// this node, e.g., Person.Adrs.zip
internal MemberPath MemberPath {
get {
MemberPath result = m_memberPath;
EntitySetBase extent = null;
if (m_memberPath == null) {
List path = new List();
JoinTreeNode node = this;
// Go up the parent chain and then reverse the result
while (node != null) {
MemberJoinTreeNode memberNode = node as MemberJoinTreeNode;
if (memberNode != null) {
path.Add(memberNode.Member);
} else {
// We are at the root and node better correspond to an extent!
ExtentJoinTreeNode extentNode = (ExtentJoinTreeNode) node;
extent = extentNode.Extent;
Debug.Assert(extent != null && node.m_parent == null,
"Non-member node better be extent and its parent needs to be null");
}
node = node.m_parent;
}
path.Reverse();
Debug.Assert(extent != null, "Tree must contain extent at root");
result = new MemberPath(extent, path, this.MetadataWorkspace);
}
Debug.Assert(m_memberPath == null || MemberPath.EqualityComparer.Equals(result, m_memberPath),
"Cached memberPath not the same as the current position of the node in the tree?");
m_memberPath = result;
return m_memberPath;
}
}
// effects: Returns the minimum number of times that this node occurs
// in its parent
internal static Occurrences MinOccurs {
// CHANGE_[....]_FEATURE_COMPOSITION: Fix for composition and nested collections
get {return Occurrences.Once;}
}
// effects: Returns the edm type of this node
internal abstract EdmType NodeType { get;}
// effects: Returns the name of the context, i.e., member name or extentname
protected abstract string ContextName { get;}
internal MetadataWorkspace MetadataWorkspace { get { return m_workspace; } }
#endregion
#region Methods
// effects: Returns true if the second reporesent the same
// extent/member as this
protected abstract bool IsSameContext(JoinTreeNode second);
// effects: Creates an empty JoinTreeNode from this's Context and nodeIsOptional
protected abstract JoinTreeNode CreateNodeFromContext(bool nodeIsOptional, List children);
// effects: Determines all the identifiers used in this and adds them to identifiers
internal abstract void GetIdentifiers(CqlIdentifiers identifiers);
// requires: member is a child of "this.MemberPath"
// effects: Creates a join tree node corresponding to member as a child
// node of this and returns the child -- if it is already present,
// returns the existing node
internal JoinTreeNode CreateAttributeNode(EdmMember member) {
Debug.Assert(member != null, "Bad member object");
// Check whether this child is already in the tree
foreach (MemberJoinTreeNode child in m_children) {
if (member.Equals(child.Member)) {
return child; // already present
}
}
MemberJoinTreeNode result = new MemberJoinTreeNode(member, false /* not optional */, new MemberJoinTreeNode[] { }, m_workspace);
Add(result); // The parent pointer is automatically set
return result;
}
// effects: Collects all the slots in the tree rooted at this and adds them to slots
internal void GatherDescendantSlots(List slots) {
slots.Add(new JoinTreeSlot(this));
foreach (JoinTreeNode child in m_children) {
child.GatherDescendantSlots(slots);
}
}
// requires: node1 and node2
// effects: Given that node1 and node2 are currently connected using
// operator "opType", merges them into a single node and returns the
// merged node. Modifies remap to hold information about remapping
// different slots in the node.
// Modifies g1 (g2) such that it evaluates to true if a tuple
// originates from node1 (node2).
// If node1 and node2 do not have the same Value, no merge
// occurs and null is returned
internal JoinTreeNode TryMergeNode(JoinTreeNode node2, CellTreeOpType opType,
ref BoolExpression g1, ref BoolExpression g2,
Dictionary remap, MemberDomainMap memberDomainMap) {
JoinTreeNode node1 = this;
Debug.Assert(node1.m_parent == null && node2.m_parent == null ||
MemberPath.EqualityComparer.Equals(node1.m_parent.MemberPath, node2.m_parent.MemberPath),
"MergeNode on nodes that do not match till parent");
if (node1.IsSameContext(node2) == false) {
return null; // cannot merge
}
Debug.Assert(opType == CellTreeOpType.FOJ || opType == CellTreeOpType.LOJ ||
opType == CellTreeOpType.IJ || opType == CellTreeOpType.Union ||
opType == CellTreeOpType.LASJ,
"Unexpected operator type");
// IsOptional appearing in the join tree distinguishes between inner
// and left outer join (n is the node for S):
// R loj S: n.IsOptional = true
// R join S: n.IsOptional = false
//
// We have the following algebraic equivalences:
// (R loj T) JOIN (S loj T) = (R join S) Loj T
// (R loj T) JOIN (S join T) = (R join S) Join T
// (R join T) JOIN (S loj T) = (R join S) Join T
// (R join T) JOIN (S join T) = (R join S) Join T
// (R loj T) LOJ (S loj T) = (R loj S) Loj T
// (R loj T) LOJ (S join T) = (R loj S) Loj T
// (R join T) LOJ (S loj T) = (R loj S) Join T
// (R join T) LOJ (S join T) = (R loj S) Join T
// (R loj T) FOJ (S loj T) = (R foj S) Loj S
// (R loj T) FOJ (S join T) = (R foj S) Loj T
// (R join T) FOJ (S loj T) = (R foj S) Loj T
// (R join T) FOJ (S join T) = (R foj S) Join T
// CHANGE_[....]_IMPROVE: Convert to actual declarative calls
bool nodeIsOptional = false;
// The following values are obtained from the above table.
// opType is the operator in upper case in the above table
// We are currently at the node for "T" (i.e., node1 and node2
// correspond to T) in both join trees. We are trying to merge
// them to get the right side, i.e., get the capitalized operator on
// the right for T
switch (opType) {
case CellTreeOpType.IJ: // If both are optional
nodeIsOptional = node1.m_isOptional && node2.m_isOptional;
break;
case CellTreeOpType.LOJ: // The right side's optionality is ignored
case CellTreeOpType.LASJ:
nodeIsOptional = node1.m_isOptional;
break;
case CellTreeOpType.FOJ: // Optional if either one is optional
case CellTreeOpType.Union:
nodeIsOptional = node1.m_isOptional || node2.m_isOptional;
break;
}
JoinTreeNode node = node1.CreateNodeFromContext(nodeIsOptional, new List());
// Essentially, evey boolean in the cell query needs to be true
// when a tuple comes from its corresponding cell. Since we are
// merging two cells, we need to change the booleans accordingly.
// g1 and g2 help us in doing that
// Note: We choose node1.VarIfThisJoined in g1 and g2 -- we could
// have chosen node2.VarIfThisJoined. The reason we do not choose
// node.VarIfThisJoined is that we need to remap later -- so all
// expressions must use the old nodes!
if (node.m_isOptional && !node2.m_isOptional) {
// If right side is non-optional, set g2 to keep track of
// this, i.e., when we produce an expression, we will place a
// value in the right side's SELECT so that we can identify
// where this tuple came from
IfJoinedCondition node2IfJoined = new IfJoinedCondition(node2);
g2 = BoolExpression.CreateAnd(g2, BoolExpression.CreateLiteral(node2IfJoined, memberDomainMap));
}
if (node.m_isOptional && !node1.m_isOptional) {
// This will only happen in FOJ for us
IfJoinedCondition node1IfJoined = new IfJoinedCondition(node1);
g1 = BoolExpression.CreateAnd(g1, BoolExpression.CreateLiteral(node1IfJoined, memberDomainMap));
}
// Bitmaps to keep track of which children in node1 and node2
// were found
bool[] matched1 = new bool[node1.m_children.Count];
bool[] matched2 = new bool[node2.m_children.Count];
// Process children that match and merge them
for (int i = 0; i < node1.m_children.Count; i++) {
MemberJoinTreeNode child1 = node1.m_children[i];
// Find the matching child for child1 in node2 if any
for (int j = 0; j < node2.m_children.Count; j++) {
MemberJoinTreeNode child2 = node2.m_children[j];
if (child1.Member.Equals(child2.Member)) {
// Matching child found -- merge the two children -- we will always get back a member node
MemberJoinTreeNode newChild = (MemberJoinTreeNode) child1.TryMergeNode(child2, opType,
ref g1, ref g2, remap, memberDomainMap);
Debug.Assert(newChild != null, "Merge node cannot fail for same values");
node.Add(newChild);
Debug.Assert(false == matched1[i] && false == matched2[j],
"Nodes match multiple time?");
matched1[i] = true;
matched2[j] = true;
}
}
}
// Process unmatched children of node1 and node2
// Note: For node1 (node2), we pass g2 (g1) since an unmatched
// child can produce extra children that requires g2(g1) to be modified
g2 = ProcessUnmergedChildren(node, node1, g2, remap, matched1, opType, memberDomainMap);
g1 = ProcessUnmergedChildren(node, node2, g1, remap, matched2, opType, memberDomainMap);
remap[node1] = node;
remap[node2] = node;
return node;
}
///
/// effects: Processes the unmatched children of node (given by
/// matched) by adding them as children of mergedNode. opType
/// indicates the operation that is being used to connect the two join trees
/// Modifies remap with the old to new mapping. Returns a boolean
/// expression (that augments g) such that it evaluates to true if
/// node adds extra tuples to the output
///
private static BoolExpression
ProcessUnmergedChildren(JoinTreeNode mergedNode, JoinTreeNode node,
BoolExpression g, Dictionary remap,
bool[] matched, CellTreeOpType opType, MemberDomainMap memberDomainMap) {
for (int j = 0; j < node.m_children.Count; j++) {
if (matched[j]) {
continue;
}
// Recall: optional = true means LOJ; else it means JOIN
// The table below says: make unmatched child non-optional if
// op=join and the child is non-optional. Otherwise, it's
// optional
// g2 needs to be adjusted in two cases marked below (where
// join becomes loj). Similarly, for g1
// (R) JOIN (R loj S) = (R loj S)
// (R) JOIN (R join S) = (R join S)
// (R) LOJ (R loj S) = (R loj S)
// (R) LOJ (R join S) = (R loj S) // adjust g2
// (R) FOJ (R loj S) = (R loj S)
// (R) FOJ (R join S) = (R loj S) // adjust g2
// childCopy refers to S. Essentially, S is only present on
// one join tree and not the other. S's optionality is
// determined from the table above (opType is capitalized
// operator above)
// Make a copy of this unmatched child and it merged node
JoinTreeNode child = node.m_children[j];
// Set IsOptional to true according to table AND only if
// child can occur zero times
bool newIsOptional = !(opType == CellTreeOpType.IJ && false == child.m_isOptional)
&& JoinTreeNode.MinOccurs == Occurrences.Zero;
MemberJoinTreeNode childCopy = (MemberJoinTreeNode) child.DeepClone(newIsOptional, remap);
mergedNode.Add(childCopy);
// Adjust g only for the cases where the optionality changed
// (as shown in the table above)
bool ifAdjustG = childCopy.m_isOptional != child.m_isOptional;
if (ifAdjustG) {
// For node1: T1 (left side) possibly adds extra tuples to the
// result of T (node); update g2 so we can identify T2
// (node2) tuples. Similarly for node2.
// Note: We choose child.VarIfThisJoined in g -- we do not choose
// the new node since we need to remap later -- so all
// expressions must use the old nodes!
IfJoinedCondition childIfJoined = new IfJoinedCondition(child);
g = BoolExpression.CreateAnd(g, BoolExpression.CreateLiteral(childIfJoined, memberDomainMap));
}
}
return g;
}
// effects: Adds node as a child of this node (sets parent field as well)
private void Add(MemberJoinTreeNode node) {
Debug.Assert(node.m_parent == null, "Attempt to add node that already belongs to some parent");
m_children.Add(node);
node.m_parent = this;
}
// effects: Asserts if this node or its children are malformed (for
// debugging only)
[Conditional("DEBUG")]
internal void Validate() {
EdmType nodeType = NodeType;
foreach (MemberJoinTreeNode child in m_children) {
Debug.Assert(child != null, "Null child");
EdmMember member = child.Member;
Debug.Assert(member is EdmProperty || member is RelationshipEndMember,
"Malformed join tree: MemberMetadata in a non-root JoinTreeNode must be either property or relation end");
child.Validate();
}
}
// effects: Performs a deep clone of JoinTreeNode while modifying
// remap to store a mapping from the old nodes to the new nodes
private JoinTreeNode DeepClone(bool isOptionalForNode, Dictionary remap) {
List children = new List();
// Clone the children first
foreach (MemberJoinTreeNode child in m_children) {
children.Add((MemberJoinTreeNode)child.DeepClone(child.m_isOptional, remap));
}
// Now create a copy of the node and update remap
JoinTreeNode newNode = CreateNodeFromContext(isOptionalForNode, children);
remap[this] = newNode;
return newNode;
}
#endregion
#region String methods
// effects: Converts the tree rooted at this into string form
// (modifies stringBuilder)
internal override void ToFullString(StringBuilder builder) {
builder.Append(ContextName);
if (m_isOptional) {
builder.Append('?');
}
bool first = true;
foreach (MemberJoinTreeNode child in m_children) {
if (first) {
builder.Append('<');
first = false;
} else {
builder.Append(", ");
}
child.ToFullString(builder);
}
if (!first) {
builder.Append('>');
}
}
internal override void ToCompactString(StringBuilder builder) {
MemberPath.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.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Globalization;
using System.Data.Metadata.Edm;
namespace System.Data.Mapping.ViewGeneration.Structures {
// JoinTreeNode represents a node in the tree that represents the FROM
// part of a cell query. It stores information such as whether the node
// is optional, whether the node joined, etc
internal abstract class JoinTreeNode : InternalBase {
#region Enums
///
/// How many times does a particular attribute node occur
/// E.g., for compositions, it can be Zero .. Many
///
internal enum Occurrences {
Zero,
Once,
Many
}
#endregion
#region Constructors/Factories
// effects: A private constructor where all the fields are initalized
protected JoinTreeNode(bool isOptional, IEnumerable children, MetadataWorkspace workspace) {
Debug.Assert(children != null, "Cannot have a null children list");
Debug.Assert(workspace != null, "MetadataWorkspace should never be null");
// m_memberPath is left as null. It will be cached when MemberPath is first called
m_isOptional = isOptional;
m_children = new List(children);
m_workspace = workspace;
// Set the parent field in each child
foreach (JoinTreeNode child in m_children) {
Debug.Assert(child.m_parent == null, "Child already has parent");
child.m_parent = this;
}
}
#endregion
#region Fields
// A cached path for optimization
private MemberPath m_memberPath;
// The nodes emanating from this node, e.g., if p is this node, a
// child could be p.pid or p.addrs
// All the children are members - so strongly type that
private List m_children;
// Reference to parent for easy navigation up and member path determination -- root has this as null
private JoinTreeNode m_parent;
// Whether the node restricts the number of tuples of its parent
// (isOptional is false iff restriction)
private bool m_isOptional;
private MetadataWorkspace m_workspace;
#endregion
#region Properties
// effects: Returns the full metadata path from the root extent to
// this node, e.g., Person.Adrs.zip
internal MemberPath MemberPath {
get {
MemberPath result = m_memberPath;
EntitySetBase extent = null;
if (m_memberPath == null) {
List path = new List();
JoinTreeNode node = this;
// Go up the parent chain and then reverse the result
while (node != null) {
MemberJoinTreeNode memberNode = node as MemberJoinTreeNode;
if (memberNode != null) {
path.Add(memberNode.Member);
} else {
// We are at the root and node better correspond to an extent!
ExtentJoinTreeNode extentNode = (ExtentJoinTreeNode) node;
extent = extentNode.Extent;
Debug.Assert(extent != null && node.m_parent == null,
"Non-member node better be extent and its parent needs to be null");
}
node = node.m_parent;
}
path.Reverse();
Debug.Assert(extent != null, "Tree must contain extent at root");
result = new MemberPath(extent, path, this.MetadataWorkspace);
}
Debug.Assert(m_memberPath == null || MemberPath.EqualityComparer.Equals(result, m_memberPath),
"Cached memberPath not the same as the current position of the node in the tree?");
m_memberPath = result;
return m_memberPath;
}
}
// effects: Returns the minimum number of times that this node occurs
// in its parent
internal static Occurrences MinOccurs {
// CHANGE_[....]_FEATURE_COMPOSITION: Fix for composition and nested collections
get {return Occurrences.Once;}
}
// effects: Returns the edm type of this node
internal abstract EdmType NodeType { get;}
// effects: Returns the name of the context, i.e., member name or extentname
protected abstract string ContextName { get;}
internal MetadataWorkspace MetadataWorkspace { get { return m_workspace; } }
#endregion
#region Methods
// effects: Returns true if the second reporesent the same
// extent/member as this
protected abstract bool IsSameContext(JoinTreeNode second);
// effects: Creates an empty JoinTreeNode from this's Context and nodeIsOptional
protected abstract JoinTreeNode CreateNodeFromContext(bool nodeIsOptional, List children);
// effects: Determines all the identifiers used in this and adds them to identifiers
internal abstract void GetIdentifiers(CqlIdentifiers identifiers);
// requires: member is a child of "this.MemberPath"
// effects: Creates a join tree node corresponding to member as a child
// node of this and returns the child -- if it is already present,
// returns the existing node
internal JoinTreeNode CreateAttributeNode(EdmMember member) {
Debug.Assert(member != null, "Bad member object");
// Check whether this child is already in the tree
foreach (MemberJoinTreeNode child in m_children) {
if (member.Equals(child.Member)) {
return child; // already present
}
}
MemberJoinTreeNode result = new MemberJoinTreeNode(member, false /* not optional */, new MemberJoinTreeNode[] { }, m_workspace);
Add(result); // The parent pointer is automatically set
return result;
}
// effects: Collects all the slots in the tree rooted at this and adds them to slots
internal void GatherDescendantSlots(List slots) {
slots.Add(new JoinTreeSlot(this));
foreach (JoinTreeNode child in m_children) {
child.GatherDescendantSlots(slots);
}
}
// requires: node1 and node2
// effects: Given that node1 and node2 are currently connected using
// operator "opType", merges them into a single node and returns the
// merged node. Modifies remap to hold information about remapping
// different slots in the node.
// Modifies g1 (g2) such that it evaluates to true if a tuple
// originates from node1 (node2).
// If node1 and node2 do not have the same Value, no merge
// occurs and null is returned
internal JoinTreeNode TryMergeNode(JoinTreeNode node2, CellTreeOpType opType,
ref BoolExpression g1, ref BoolExpression g2,
Dictionary remap, MemberDomainMap memberDomainMap) {
JoinTreeNode node1 = this;
Debug.Assert(node1.m_parent == null && node2.m_parent == null ||
MemberPath.EqualityComparer.Equals(node1.m_parent.MemberPath, node2.m_parent.MemberPath),
"MergeNode on nodes that do not match till parent");
if (node1.IsSameContext(node2) == false) {
return null; // cannot merge
}
Debug.Assert(opType == CellTreeOpType.FOJ || opType == CellTreeOpType.LOJ ||
opType == CellTreeOpType.IJ || opType == CellTreeOpType.Union ||
opType == CellTreeOpType.LASJ,
"Unexpected operator type");
// IsOptional appearing in the join tree distinguishes between inner
// and left outer join (n is the node for S):
// R loj S: n.IsOptional = true
// R join S: n.IsOptional = false
//
// We have the following algebraic equivalences:
// (R loj T) JOIN (S loj T) = (R join S) Loj T
// (R loj T) JOIN (S join T) = (R join S) Join T
// (R join T) JOIN (S loj T) = (R join S) Join T
// (R join T) JOIN (S join T) = (R join S) Join T
// (R loj T) LOJ (S loj T) = (R loj S) Loj T
// (R loj T) LOJ (S join T) = (R loj S) Loj T
// (R join T) LOJ (S loj T) = (R loj S) Join T
// (R join T) LOJ (S join T) = (R loj S) Join T
// (R loj T) FOJ (S loj T) = (R foj S) Loj S
// (R loj T) FOJ (S join T) = (R foj S) Loj T
// (R join T) FOJ (S loj T) = (R foj S) Loj T
// (R join T) FOJ (S join T) = (R foj S) Join T
// CHANGE_[....]_IMPROVE: Convert to actual declarative calls
bool nodeIsOptional = false;
// The following values are obtained from the above table.
// opType is the operator in upper case in the above table
// We are currently at the node for "T" (i.e., node1 and node2
// correspond to T) in both join trees. We are trying to merge
// them to get the right side, i.e., get the capitalized operator on
// the right for T
switch (opType) {
case CellTreeOpType.IJ: // If both are optional
nodeIsOptional = node1.m_isOptional && node2.m_isOptional;
break;
case CellTreeOpType.LOJ: // The right side's optionality is ignored
case CellTreeOpType.LASJ:
nodeIsOptional = node1.m_isOptional;
break;
case CellTreeOpType.FOJ: // Optional if either one is optional
case CellTreeOpType.Union:
nodeIsOptional = node1.m_isOptional || node2.m_isOptional;
break;
}
JoinTreeNode node = node1.CreateNodeFromContext(nodeIsOptional, new List());
// Essentially, evey boolean in the cell query needs to be true
// when a tuple comes from its corresponding cell. Since we are
// merging two cells, we need to change the booleans accordingly.
// g1 and g2 help us in doing that
// Note: We choose node1.VarIfThisJoined in g1 and g2 -- we could
// have chosen node2.VarIfThisJoined. The reason we do not choose
// node.VarIfThisJoined is that we need to remap later -- so all
// expressions must use the old nodes!
if (node.m_isOptional && !node2.m_isOptional) {
// If right side is non-optional, set g2 to keep track of
// this, i.e., when we produce an expression, we will place a
// value in the right side's SELECT so that we can identify
// where this tuple came from
IfJoinedCondition node2IfJoined = new IfJoinedCondition(node2);
g2 = BoolExpression.CreateAnd(g2, BoolExpression.CreateLiteral(node2IfJoined, memberDomainMap));
}
if (node.m_isOptional && !node1.m_isOptional) {
// This will only happen in FOJ for us
IfJoinedCondition node1IfJoined = new IfJoinedCondition(node1);
g1 = BoolExpression.CreateAnd(g1, BoolExpression.CreateLiteral(node1IfJoined, memberDomainMap));
}
// Bitmaps to keep track of which children in node1 and node2
// were found
bool[] matched1 = new bool[node1.m_children.Count];
bool[] matched2 = new bool[node2.m_children.Count];
// Process children that match and merge them
for (int i = 0; i < node1.m_children.Count; i++) {
MemberJoinTreeNode child1 = node1.m_children[i];
// Find the matching child for child1 in node2 if any
for (int j = 0; j < node2.m_children.Count; j++) {
MemberJoinTreeNode child2 = node2.m_children[j];
if (child1.Member.Equals(child2.Member)) {
// Matching child found -- merge the two children -- we will always get back a member node
MemberJoinTreeNode newChild = (MemberJoinTreeNode) child1.TryMergeNode(child2, opType,
ref g1, ref g2, remap, memberDomainMap);
Debug.Assert(newChild != null, "Merge node cannot fail for same values");
node.Add(newChild);
Debug.Assert(false == matched1[i] && false == matched2[j],
"Nodes match multiple time?");
matched1[i] = true;
matched2[j] = true;
}
}
}
// Process unmatched children of node1 and node2
// Note: For node1 (node2), we pass g2 (g1) since an unmatched
// child can produce extra children that requires g2(g1) to be modified
g2 = ProcessUnmergedChildren(node, node1, g2, remap, matched1, opType, memberDomainMap);
g1 = ProcessUnmergedChildren(node, node2, g1, remap, matched2, opType, memberDomainMap);
remap[node1] = node;
remap[node2] = node;
return node;
}
///
/// effects: Processes the unmatched children of node (given by
/// matched) by adding them as children of mergedNode. opType
/// indicates the operation that is being used to connect the two join trees
/// Modifies remap with the old to new mapping. Returns a boolean
/// expression (that augments g) such that it evaluates to true if
/// node adds extra tuples to the output
///
private static BoolExpression
ProcessUnmergedChildren(JoinTreeNode mergedNode, JoinTreeNode node,
BoolExpression g, Dictionary remap,
bool[] matched, CellTreeOpType opType, MemberDomainMap memberDomainMap) {
for (int j = 0; j < node.m_children.Count; j++) {
if (matched[j]) {
continue;
}
// Recall: optional = true means LOJ; else it means JOIN
// The table below says: make unmatched child non-optional if
// op=join and the child is non-optional. Otherwise, it's
// optional
// g2 needs to be adjusted in two cases marked below (where
// join becomes loj). Similarly, for g1
// (R) JOIN (R loj S) = (R loj S)
// (R) JOIN (R join S) = (R join S)
// (R) LOJ (R loj S) = (R loj S)
// (R) LOJ (R join S) = (R loj S) // adjust g2
// (R) FOJ (R loj S) = (R loj S)
// (R) FOJ (R join S) = (R loj S) // adjust g2
// childCopy refers to S. Essentially, S is only present on
// one join tree and not the other. S's optionality is
// determined from the table above (opType is capitalized
// operator above)
// Make a copy of this unmatched child and it merged node
JoinTreeNode child = node.m_children[j];
// Set IsOptional to true according to table AND only if
// child can occur zero times
bool newIsOptional = !(opType == CellTreeOpType.IJ && false == child.m_isOptional)
&& JoinTreeNode.MinOccurs == Occurrences.Zero;
MemberJoinTreeNode childCopy = (MemberJoinTreeNode) child.DeepClone(newIsOptional, remap);
mergedNode.Add(childCopy);
// Adjust g only for the cases where the optionality changed
// (as shown in the table above)
bool ifAdjustG = childCopy.m_isOptional != child.m_isOptional;
if (ifAdjustG) {
// For node1: T1 (left side) possibly adds extra tuples to the
// result of T (node); update g2 so we can identify T2
// (node2) tuples. Similarly for node2.
// Note: We choose child.VarIfThisJoined in g -- we do not choose
// the new node since we need to remap later -- so all
// expressions must use the old nodes!
IfJoinedCondition childIfJoined = new IfJoinedCondition(child);
g = BoolExpression.CreateAnd(g, BoolExpression.CreateLiteral(childIfJoined, memberDomainMap));
}
}
return g;
}
// effects: Adds node as a child of this node (sets parent field as well)
private void Add(MemberJoinTreeNode node) {
Debug.Assert(node.m_parent == null, "Attempt to add node that already belongs to some parent");
m_children.Add(node);
node.m_parent = this;
}
// effects: Asserts if this node or its children are malformed (for
// debugging only)
[Conditional("DEBUG")]
internal void Validate() {
EdmType nodeType = NodeType;
foreach (MemberJoinTreeNode child in m_children) {
Debug.Assert(child != null, "Null child");
EdmMember member = child.Member;
Debug.Assert(member is EdmProperty || member is RelationshipEndMember,
"Malformed join tree: MemberMetadata in a non-root JoinTreeNode must be either property or relation end");
child.Validate();
}
}
// effects: Performs a deep clone of JoinTreeNode while modifying
// remap to store a mapping from the old nodes to the new nodes
private JoinTreeNode DeepClone(bool isOptionalForNode, Dictionary remap) {
List children = new List();
// Clone the children first
foreach (MemberJoinTreeNode child in m_children) {
children.Add((MemberJoinTreeNode)child.DeepClone(child.m_isOptional, remap));
}
// Now create a copy of the node and update remap
JoinTreeNode newNode = CreateNodeFromContext(isOptionalForNode, children);
remap[this] = newNode;
return newNode;
}
#endregion
#region String methods
// effects: Converts the tree rooted at this into string form
// (modifies stringBuilder)
internal override void ToFullString(StringBuilder builder) {
builder.Append(ContextName);
if (m_isOptional) {
builder.Append('?');
}
bool first = true;
foreach (MemberJoinTreeNode child in m_children) {
if (first) {
builder.Append('<');
first = false;
} else {
builder.Append(", ");
}
child.ToFullString(builder);
}
if (!first) {
builder.Append('>');
}
}
internal override void ToCompactString(StringBuilder builder) {
MemberPath.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
- ToolStripItem.cs
- CharUnicodeInfo.cs
- ClientTarget.cs
- UInt16Storage.cs
- Currency.cs
- HttpCacheParams.cs
- AnonymousIdentificationModule.cs
- XmlCDATASection.cs
- ReferencedAssemblyResolver.cs
- Hex.cs
- MembershipValidatePasswordEventArgs.cs
- SplayTreeNode.cs
- BuilderPropertyEntry.cs
- XmlDeclaration.cs
- ApplicationException.cs
- XsltLoader.cs
- GridItemCollection.cs
- SqlInternalConnectionTds.cs
- SafeNativeMethods.cs
- XmlFileEditor.cs
- ToolStripPanel.cs
- WindowsIdentity.cs
- FontClient.cs
- HtmlTableRowCollection.cs
- OptionalColumn.cs
- ApplicationSettingsBase.cs
- ConfigurationFileMap.cs
- TreeNodeCollection.cs
- TableLayoutStyleCollection.cs
- ObjectStateFormatter.cs
- OutArgumentConverter.cs
- AutoGeneratedFieldProperties.cs
- DesignSurfaceEvent.cs
- safemediahandle.cs
- RelatedView.cs
- ListSortDescriptionCollection.cs
- MapPathBasedVirtualPathProvider.cs
- SmtpCommands.cs
- UInt16.cs
- GPPOINT.cs
- dataSvcMapFileLoader.cs
- DisableDpiAwarenessAttribute.cs
- StreamHelper.cs
- SafeFileMappingHandle.cs
- ControlAdapter.cs
- Soap.cs
- ApplicationSecurityInfo.cs
- Zone.cs
- Pair.cs
- XPathAncestorQuery.cs
- StructuredProperty.cs
- PingReply.cs
- ManagementDateTime.cs
- JoinCqlBlock.cs
- SrgsGrammar.cs
- RootBrowserWindowAutomationPeer.cs
- ReadOnlyState.cs
- SByteConverter.cs
- XmlTypeAttribute.cs
- InvalidDataException.cs
- DataSourceConverter.cs
- BaseUriWithWildcard.cs
- ObjectDataSourceView.cs
- AccessorTable.cs
- SecureStringHasher.cs
- PopOutPanel.cs
- TemplateManager.cs
- SmiEventSink.cs
- MsmqIntegrationBindingCollectionElement.cs
- XmlAnyElementAttribute.cs
- ListViewHitTestInfo.cs
- InputLanguageEventArgs.cs
- WebControl.cs
- EdmMember.cs
- ExpressionConverter.cs
- TypeDescriptionProvider.cs
- InlinedAggregationOperator.cs
- SqlUtils.cs
- DataGridViewAccessibleObject.cs
- Types.cs
- PathFigureCollection.cs
- ResumeStoryboard.cs
- DesignerOptionService.cs
- DecimalConverter.cs
- Hashtable.cs
- PlanCompilerUtil.cs
- TemplateControlBuildProvider.cs
- GeometryGroup.cs
- XmlStringTable.cs
- Pool.cs
- DefaultAsyncDataDispatcher.cs
- CodeCompiler.cs
- WindowsGraphicsCacheManager.cs
- DataGridViewCellEventArgs.cs
- SchemaImporterExtension.cs
- ToolstripProfessionalRenderer.cs
- ValueSerializerAttribute.cs
- Stylesheet.cs
- DocumentApplicationJournalEntry.cs
- FormViewUpdatedEventArgs.cs