1 //------------------------------------------------------------
2 // Copyright (c) Microsoft Corporation.  All rights reserved.
3 //------------------------------------------------------------
4 namespace System.ServiceModel.Dispatcher
5 {
6     using System.Runtime;
7 
8     class QueryTreeBuilder
9     {
10         Diverger diverger;
11         Opcode lastOpcode;
12 
QueryTreeBuilder()13         internal QueryTreeBuilder()
14         {
15         }
16 
17         internal Opcode LastOpcode
18         {
19             get
20             {
21                 return this.lastOpcode;
22             }
23         }
24 
Build(Opcode tree, OpcodeBlock newBlock)25         internal Opcode Build(Opcode tree, OpcodeBlock newBlock)
26         {
27             if (null == tree)
28             {
29                 this.lastOpcode = newBlock.Last;
30                 return newBlock.First;
31             }
32 
33             this.diverger = new Diverger(tree, newBlock.First);
34 
35             if (!this.diverger.Find())
36             {
37                 // The opcodes in newBlock already have equivalents or identical opcodes
38                 // in the query tree that can do the job
39                 Fx.Assert(this.diverger.TreePath.Count > 0, "");
40                 this.lastOpcode = this.diverger.TreePath[this.diverger.TreePath.Count - 1];
41                 return tree;
42             }
43 
44             Fx.Assert(this.diverger.TreePath.Count == this.diverger.InsertPath.Count, "");
45 
46             // We can reuse opcodes upto this.diverger.TreePath[this.diverger.TreePath.Count - 1]
47             // The remainder of the code in newBlock must be executed as is...
48             if (null == this.diverger.TreeOpcode)
49             {
50                 // We reached a leaf in the query tree
51                 // Simply add the remainder of the inserted code to the end of the tree path..
52                 this.diverger.TreePath[this.diverger.TreePath.Count - 1].Attach(this.diverger.InsertOpcode);
53             }
54             else
55             {
56                 // Merge in the remaider of the new code block into the query tree
57                 // The first diverging opcodes follow the last entry in each path
58                 this.diverger.TreeOpcode.Add(this.diverger.InsertOpcode);
59             }
60 
61             this.lastOpcode = newBlock.Last;
62             if (this.diverger.InsertOpcode.IsMultipleResult())
63             {
64                 // The complete new block was merged in, except for the the actual result opcode, which never
65                 // automatically merges. This means that the new block found all of its opcodes in common with
66                 // the tree
67                 if (OpcodeID.Branch == this.diverger.TreeOpcode.ID)
68                 {
69                     OpcodeList branches = (((BranchOpcode) this.diverger.TreeOpcode).Branches);
70                     for (int i = 0, count = branches.Count; i < count; ++i)
71                     {
72                         if (branches[i].IsMultipleResult())
73                         {
74                             this.lastOpcode = branches[i];
75                             break;
76                         }
77                     }
78                 }
79                 else if (this.diverger.TreeOpcode.IsMultipleResult())
80                 {
81                     this.lastOpcode = this.diverger.TreeOpcode;
82                 }
83             }
84 
85             // Since we'll be diverging, any jumps that preceeded and leapt past the divergence point
86             // will have to be branched
87             this.FixupJumps();
88 
89             return tree;
90         }
91 
FixupJumps()92         void FixupJumps()
93         {
94             QueryBuffer<Opcode> treePath = this.diverger.TreePath;
95             QueryBuffer<Opcode> insertPath = this.diverger.InsertPath;
96 
97             for (int i = 0; i < insertPath.Count; ++i)
98             {
99                 if (insertPath[i].TestFlag(OpcodeFlags.Jump))
100                 {
101                     Fx.Assert(treePath[i].ID == insertPath[i].ID, "");
102                     JumpOpcode insertJump = (JumpOpcode) insertPath[i];
103                     // Opcodes in 'insertPath' have equivalent opcodes in the query tree: i.e. the query tree contains an
104                     // an equivalent execution path (upto the point of divergence naturally) that will produce in an identical
105                     // result. The remainder of the query tree (anything that lies beyond the point of divergence) represents
106                     // a distinct execution path and is grafted onto the tree as a new branch. In fact, we simply break off
107                     // the remainder from the query being inserted and graft it onto the query tree.
108                     // If there are jumps on the insert path that jump to opcodes NOT in the insert path, then the jumps
109                     // will reach opcodes in the new branch we will add(see above). However, because the actual jump opcodes
110                     // are shared (used as is from the query tree), the actual jump must also be branched. One jump will
111                     // continue to jump to the original opcode and the second new one will jump to an opcode in the grafted branch.
112                     if (-1 == insertPath.IndexOf(insertJump.Jump, i + 1))
113                     {
114                         Fx.Assert(insertJump.Jump.ID == OpcodeID.BlockEnd, "");
115 
116                         BlockEndOpcode jumpTo = (BlockEndOpcode) insertJump.Jump;
117                         // no longer jumping from insertJump to jumpTo
118                         insertJump.RemoveJump(jumpTo);
119 
120                         // Instead, jumping from treePath[i] to jumpTo
121                         JumpOpcode treeJump = (JumpOpcode) treePath[i];
122                         treeJump.AddJump(jumpTo);
123                     }
124                 }
125             }
126         }
127 
128         // Can handle queries being merged into trees but not trees merged into trees.
129         // In other words, no branch opcodes in the query being inserted
130         internal struct Diverger
131         {
132             Opcode treeOpcode;
133             QueryBuffer<Opcode> treePath;
134             QueryBuffer<Opcode> insertPath;
135             Opcode insertOpcode;
136 
DivergerSystem.ServiceModel.Dispatcher.QueryTreeBuilder.Diverger137             internal Diverger(Opcode tree, Opcode insert)
138             {
139                 this.treePath = new QueryBuffer<Opcode>(16);
140                 this.insertPath = new QueryBuffer<Opcode>(16);
141                 this.treeOpcode = tree;
142                 this.insertOpcode = insert;
143             }
144 
145             internal Opcode InsertOpcode
146             {
147                 get
148                 {
149                     return this.insertOpcode;
150                 }
151             }
152 
153             internal QueryBuffer<Opcode> InsertPath
154             {
155                 get
156                 {
157                     return this.insertPath;
158                 }
159             }
160 
161             internal Opcode TreeOpcode
162             {
163                 get
164                 {
165                     return this.treeOpcode;
166                 }
167             }
168 
169             internal QueryBuffer<Opcode> TreePath
170             {
171                 get
172                 {
173                     return this.treePath;
174                 }
175             }
176 
177             // Stops at the last common node on each
FindSystem.ServiceModel.Dispatcher.QueryTreeBuilder.Diverger178             internal bool Find()
179             {
180                 Opcode treeNext = null;
181                 while (true)
182                 {
183                     if (null == this.treeOpcode && null == this.insertOpcode)
184                     {
185                         return false; // no diverge. both ran out at the same time
186                     }
187                     if (null == this.insertOpcode)
188                     {
189                         return false; // Ran out before tree did. No divergence.
190                     }
191                     if (null == this.treeOpcode)
192                     {
193                         return true; // tree ran out before insert. Divergence
194                     }
195                     if (this.treeOpcode.TestFlag(OpcodeFlags.Branch))
196                     {
197                         treeNext = this.treeOpcode.Locate(this.insertOpcode);
198                         if (null == treeNext)
199                         {
200                             return true; // divergence
201                         }
202                         this.treeOpcode = treeNext;
203                         treeNext = treeNext.Next;
204                     }
205                     else
206                     {
207                         if (!this.treeOpcode.Equals(this.insertOpcode))
208                         {
209                             return true; // divergence, obviously
210                         }
211                         treeNext = this.treeOpcode.Next;
212                     }
213                     // No divergence. Add to paths
214                     this.treePath.Add(this.treeOpcode);
215                     this.insertPath.Add(this.insertOpcode);
216                     this.insertOpcode = this.insertOpcode.Next;
217                     this.treeOpcode = treeNext;
218                 }
219             }
220         }
221     }
222 }
223