1 /*
2 * Copyright 2006-2008 The FLWOR Foundation.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #include "stdafx.h"
17
18 #include "zorbautils/fatal.h"
19 #include "diagnostics/assert.h"
20 #include "diagnostics/util_macros.h"
21 #include "diagnostics/xquery_diagnostics.h"
22 #include "zorbautils/checked_vector.h"
23
24 #include "system/globalenv.h"
25
26 #include "context/dynamic_context.h"
27 #include "context/static_context.h"
28
29 #include "compiler/api/compilercb.h"
30
31 #include "runtime/visitors/planiter_visitor.h"
32 #include "runtime/booleans/BooleanImpl.h"
33 #include "runtime/core/gflwor/orderby_iterator.h"
34 #include "runtime/core/gflwor/common.h"
35 #include "runtime/core/gflwor/comp_function.h"
36
37 #include <vector>
38 #include <algorithm>
39
40 using namespace zorba;
41
42 namespace zorba
43 {
44
45 namespace flwor
46 {
47
48 SERIALIZABLE_CLASS_VERSIONS(OrderByIterator)
49
SERIALIZABLE_CLASS_VERSIONS(OrderSpec)50 SERIALIZABLE_CLASS_VERSIONS(OrderSpec)
51
52
53 /////////////////////////////////////////////////////////////////////////////////
54 // //
55 // OrderSpec //
56 // //
57 /////////////////////////////////////////////////////////////////////////////////
58
59
60 OrderSpec::OrderSpec (
61 PlanIter_t domainIter,
62 bool emptyLeast,
63 bool descending,
64 bool nativeCompare,
65 const std::string& collation)
66 :
67 theDomainIter(domainIter),
68 theEmptyLeast(emptyLeast),
69 theDescending(descending),
70 theNativeCompare(nativeCompare),
71 theCollation(collation),
72 theCollator(0)
73 {
74 }
75
76
serialize(::zorba::serialization::Archiver & ar)77 void OrderSpec::serialize(::zorba::serialization::Archiver& ar)
78 {
79 ar & theDomainIter;
80 ar & theEmptyLeast;
81 ar & theDescending;
82 ar & theNativeCompare;
83 ar & theCollation;
84 ar & theCollator;
85 }
86
87
accept(PlanIterVisitor & v) const88 void OrderSpec::accept(PlanIterVisitor& v) const
89 {
90 v.beginVisitOrderBySpec(*theDomainIter);
91 v.endVisitOrderBySpec(*theDomainIter);
92 }
93
94
getStateSizeOfSubtree() const95 uint32_t OrderSpec::getStateSizeOfSubtree() const
96 {
97 return theDomainIter->getStateSizeOfSubtree();
98 }
99
100
open(PlanState & aPlanState,uint32_t & offset) const101 void OrderSpec::open(PlanState& aPlanState, uint32_t& offset) const
102 {
103 theDomainIter->open(aPlanState, offset);
104 }
105
106
reset(PlanState & aPlanState) const107 void OrderSpec::reset(PlanState& aPlanState) const
108 {
109 theDomainIter->reset(aPlanState);
110 }
111
112
close(PlanState & aPlanState) const113 void OrderSpec::close(PlanState& aPlanState) const
114 {
115 theDomainIter->close(aPlanState);
116 }
117
118
119
120 /////////////////////////////////////////////////////////////////////////////////
121 // //
122 // OrderByState //
123 // //
124 /////////////////////////////////////////////////////////////////////////////////
125
126
OrderByState()127 OrderByState::OrderByState()
128 :
129 theNumTuples(0),
130 theCurTuplePos(0)
131 {
132 }
133
134
~OrderByState()135 OrderByState::~OrderByState()
136 {
137 clearSortTable();
138 }
139
140
init(PlanState & planState,std::vector<OrderSpec> * orderSpecs)141 void OrderByState::init(PlanState& planState, std::vector<OrderSpec>* orderSpecs)
142 {
143 PlanIteratorState::init(planState);
144
145 theNumTuples = 0;
146 theCurTuplePos = 0;
147 }
148
149
reset(PlanState & planState)150 void OrderByState::reset(PlanState& planState)
151 {
152 PlanIteratorState::reset(planState);
153
154 clearSortTable();
155 theDataTable.clear();
156 theNumTuples = 0;
157 theCurTuplePos = 0;
158 }
159
160
clearSortTable()161 void OrderByState::clearSortTable()
162 {
163 ulong numTuples = (ulong)theSortTable.size();
164
165 for (ulong i = 0; i < numTuples; ++i)
166 {
167 theSortTable[i].clear();
168 }
169
170 theSortTable.clear();
171 }
172
173
174 /////////////////////////////////////////////////////////////////////////////////
175 // //
176 // OrderByIterator //
177 // //
178 /////////////////////////////////////////////////////////////////////////////////
179
180
OrderByIterator(static_context * sctx,const QueryLoc & aLoc,bool stable,std::vector<OrderSpec> & orderSpecs,PlanIter_t tupleIterator,std::vector<ForVarIter_t> & inputForVars,std::vector<LetVarIter_t> & inputLetVars,std::vector<std::vector<PlanIter_t>> & outputForVarsRefs,std::vector<std::vector<PlanIter_t>> & outputLetVarsRefs)181 OrderByIterator::OrderByIterator (
182 static_context* sctx,
183 const QueryLoc& aLoc,
184 bool stable,
185 std::vector<OrderSpec>& orderSpecs,
186 PlanIter_t tupleIterator,
187 std::vector<ForVarIter_t>& inputForVars,
188 std::vector<LetVarIter_t>& inputLetVars,
189 std::vector<std::vector<PlanIter_t> >& outputForVarsRefs,
190 std::vector<std::vector<PlanIter_t> >& outputLetVarsRefs)
191 :
192 Batcher<OrderByIterator>(sctx, aLoc),
193 theStable(stable),
194 theOrderSpecs(orderSpecs),
195 theTupleIter(tupleIterator),
196 theInputForVars(inputForVars),
197 theInputLetVars(inputLetVars),
198 theOutputForVarsRefs(outputForVarsRefs),
199 theOutputLetVarsRefs(outputLetVarsRefs)
200 {
201 }
202
203
~OrderByIterator()204 OrderByIterator::~OrderByIterator()
205 {
206 }
207
208
serialize(::zorba::serialization::Archiver & ar)209 void OrderByIterator::serialize(::zorba::serialization::Archiver& ar)
210 {
211 serialize_baseclass(ar, (Batcher<OrderByIterator>*)this);
212 ar & theStable;
213 ar & theOrderSpecs;
214 ar & theTupleIter;
215
216 ar & theInputForVars;
217 ar & theInputLetVars;
218 ar & theOutputForVarsRefs;
219 ar & theOutputLetVarsRefs;
220 }
221
222
getStateSize() const223 uint32_t OrderByIterator::getStateSize() const
224 {
225 return sizeof(OrderByState);
226 }
227
228
getStateSizeOfSubtree() const229 uint32_t OrderByIterator::getStateSizeOfSubtree() const
230 {
231 int32_t lSize = this->getStateSize();
232 lSize += theTupleIter->getStateSizeOfSubtree();
233 lSize += getStateSizeOfSubtreeVector<OrderSpec> ( theOrderSpecs );
234 lSize += getStateSizeOfSubtreeVectorPtr<ForVarIter_t> ( theInputForVars );
235 lSize += getStateSizeOfSubtreeVectorPtr<LetVarIter_t> ( theInputLetVars );
236 return lSize;
237 }
238
239
accept(PlanIterVisitor & v) const240 void OrderByIterator::accept(PlanIterVisitor& v) const
241 {
242 v.beginVisit(*this);
243
244 ulong numVars = (ulong)theInputForVars.size();
245 for (ulong i = 0; i < numVars; ++i)
246 {
247 v.beginVisitOrderByForVariable(theInputForVars[i], theOutputForVarsRefs[i]);
248 v.endVisitOrderByForVariable();
249 }
250
251 numVars = (ulong)theInputLetVars.size();
252 for (ulong i = 0; i < numVars; ++i)
253 {
254 v.beginVisitOrderByLetVariable(theInputLetVars[i], theOutputLetVarsRefs[i]);
255 v.endVisitOrderByLetVariable();
256 }
257
258 callAcceptVector(theOrderSpecs, v);
259
260 theTupleIter->accept(v);
261
262 v.endVisit(*this);
263 }
264
265
openImpl(PlanState & planState,uint32_t & aOffset)266 void OrderByIterator::openImpl(PlanState& planState, uint32_t& aOffset)
267 {
268 StateTraitsImpl<OrderByState>::createState(planState, theStateOffset, aOffset);
269
270 OrderByState* iterState = StateTraitsImpl<OrderByState>::getState(planState,
271 theStateOffset);
272
273 // Do a manual pass to set the Collator
274 ulong numSpecs = (ulong)theOrderSpecs.size();
275 for (ulong i = 0; i < numSpecs; ++i)
276 {
277 theOrderSpecs[i].open(planState, aOffset);
278
279 if (! theOrderSpecs[i].theCollation.empty())
280 {
281 theOrderSpecs[i].theCollator =
282 theSctx->get_collator(theOrderSpecs[i].theCollation, loc);
283 }
284 }
285
286 iterState->init(planState, &theOrderSpecs);
287
288 theTupleIter->open(planState, aOffset);
289
290 openVectorPtr<ForVarIter_t>(theInputForVars, planState, aOffset);
291 openVectorPtr<LetVarIter_t>(theInputLetVars, planState, aOffset);
292 }
293
294
resetImpl(PlanState & planState) const295 void OrderByIterator::resetImpl(PlanState& planState) const
296 {
297 OrderByState* iterState = StateTraitsImpl<OrderByState>::getState(planState,
298 theStateOffset);
299 iterState->reset(planState);
300
301 theTupleIter->reset(planState);
302 resetVector<OrderSpec>(theOrderSpecs, planState);
303 resetVectorPtr<ForVarIter_t >(theInputForVars, planState);
304 resetVectorPtr<LetVarIter_t >(theInputLetVars, planState);
305 }
306
307
closeImpl(PlanState & planState)308 void OrderByIterator::closeImpl(PlanState& planState)
309 {
310 theTupleIter->close(planState);
311 closeVector<OrderSpec>(theOrderSpecs, planState);
312 closeVectorPtr<ForVarIter_t>(theInputForVars, planState);
313 closeVectorPtr<LetVarIter_t>(theInputLetVars, planState);
314
315 StateTraitsImpl<OrderByState>::destroyState(planState, theStateOffset);
316 }
317
318
319
nextImpl(store::Item_t & result,PlanState & planState) const320 bool OrderByIterator::nextImpl(store::Item_t& result, PlanState& planState) const
321 {
322 OrderByState* iterState;
323 DEFAULT_STACK_INIT(OrderByState, iterState, planState);
324
325 while (consumeNext(result, theTupleIter, planState))
326 {
327 materializeResultForSort(iterState, planState);
328 }
329
330 {
331 SortTupleCmp cmp(loc,
332 planState.theLocalDynCtx,
333 theSctx->get_typemanager(),
334 &theOrderSpecs);
335
336 if (theStable)
337 {
338 std::stable_sort(iterState->theSortTable.begin(),
339 iterState->theSortTable.end(),
340 cmp);
341 }
342 else
343 {
344 std::sort(iterState->theSortTable.begin(),
345 iterState->theSortTable.end(),
346 cmp);
347 }
348 }
349
350 iterState->theCurTuplePos = 0;
351 iterState->theNumTuples = (ulong)iterState->theSortTable.size();
352
353 while(iterState->theCurTuplePos < iterState->theNumTuples)
354 {
355 bindOrderBy(iterState, planState);
356
357 STACK_PUSH(true, iterState);
358
359 ++(iterState->theCurTuplePos);
360 }
361
362 STACK_PUSH(false, iterState);
363 STACK_END(iterState);
364 }
365
366
367 /***************************************************************************//**
368 All FOR and LET vars are bound when this method is called. The method computes
369 the order-by tuple T and the return-clause sequence R for the current var
370 bindings. Then, it inserts the pair (T, I(R)) into theOrderMap (where I is
371 an iterator over the temp seq storing R).
372 ********************************************************************************/
materializeResultForSort(OrderByState * iterState,PlanState & planState) const373 void OrderByIterator::materializeResultForSort(
374 OrderByState* iterState,
375 PlanState& planState) const
376 {
377 OrderByState::SortTable& sortTable = iterState->theSortTable;
378 OrderByState::DataTable& dataTable = iterState->theDataTable;
379
380 csize numTuples = sortTable.size();
381 sortTable.resize(numTuples + 1);
382 dataTable.resize(numTuples + 1);
383
384 // Create the sort tuple
385
386 csize numSpecs = theOrderSpecs.size();
387
388 std::vector<store::Item*>& sortKey = sortTable[numTuples].theKeyValues;
389 sortKey.resize(numSpecs);
390
391 for (csize i = 0; i < numSpecs; ++i)
392 {
393 store::Item_t sortKeyItem;
394 if (consumeNext(sortKeyItem, theOrderSpecs[i].theDomainIter, planState))
395 {
396 sortKey[i] = sortKeyItem.release();
397
398 store::Item_t temp;
399 if (consumeNext(temp, theOrderSpecs[i].theDomainIter, planState))
400 {
401 RAISE_ERROR(err::XPTY0004, loc,
402 ERROR_PARAMS(ZED(SingletonExpected_2o)));
403 }
404 }
405 else
406 {
407 sortKey[i] = NULL;
408 }
409
410 theOrderSpecs[i].theDomainIter->reset(planState);
411 }
412
413 sortTable[numTuples].theDataPos = numTuples;
414
415 // create the data tuple
416
417 csize numForVars = theInputForVars.size();
418 csize numLetVars = theInputLetVars.size();
419
420 StreamTuple& streamTuple = dataTable[numTuples];
421 streamTuple.theItems.resize(numForVars);
422 streamTuple.theSequences.resize(numLetVars);
423
424 for (csize i = 0; i < numForVars; ++i)
425 {
426 store::Item_t forItem;
427 consumeNext(forItem, theInputForVars[i], planState);
428
429 streamTuple.theItems[i].transfer(forItem);
430
431 theInputForVars[i]->reset(planState);
432 }
433
434 for (csize i = 0; i < numLetVars; ++i)
435 {
436 store::TempSeq_t letTempSeq;
437 createTempSeq(letTempSeq, theInputLetVars[i], planState, false);
438
439 streamTuple.theSequences[i].transfer(letTempSeq);
440
441 theInputLetVars[i]->reset(planState);
442 }
443 }
444
445
bindOrderBy(OrderByState * iterState,PlanState & planState) const446 void OrderByIterator::bindOrderBy(
447 OrderByState* iterState,
448 PlanState& planState) const
449 {
450 StreamTuple& streamTuple =
451 iterState->theDataTable[iterState->theSortTable[iterState->theCurTuplePos].theDataPos];
452
453 ulong numForVarsRefs = (ulong)theOutputForVarsRefs.size();
454 for (ulong i = 0; i < numForVarsRefs; ++i)
455 {
456 bindVariables(streamTuple.theItems[i], theOutputForVarsRefs[i], planState);
457 }
458
459 ulong numLetVarsRefs = (ulong)theOutputLetVarsRefs.size();
460 for(ulong i = 0; i < numLetVarsRefs; ++i)
461 {
462 bindVariables(streamTuple.theSequences[i], theOutputLetVarsRefs[i], planState);
463 }
464 }
465
466
467 } //Namespace flwor
468 } //Namespace zorba
469 /* vim:set et sw=2 ts=2: */
470