1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtXmlPatterns module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include <QtAlgorithms>
41
42#include "qcommonsequencetypes_p.h"
43#include "qnodebuilder_p.h"
44#include "qschemanumeric_p.h"
45#include "qpatternistlocale_p.h"
46#include "qreturnorderby_p.h"
47#include "qsorttuple_p.h"
48#include "qsequencemappingiterator_p.h"
49
50#include "qorderby_p.h"
51
52#include <algorithm>
53#include <functional>
54
55QT_BEGIN_NAMESPACE
56
57using namespace QPatternist;
58
59OrderBy::OrderBy(const Stability stability,
60 const OrderSpec::Vector &aOrderSpecs,
61 const Expression::Ptr &op,
62 ReturnOrderBy *const returnOrderBy) : SingleContainer(op)
63 , m_stability(stability)
64 , m_orderSpecs(aOrderSpecs)
65 , m_returnOrderBy(returnOrderBy)
66{
67 Q_ASSERT(m_returnOrderBy);
68}
69
70void OrderBy::OrderSpec::prepare(const Expression::Ptr &source,
71 const StaticContext::Ptr &context)
72{
73 m_expr = source;
74 const ItemType::Ptr t(source->staticType()->itemType());
75 prepareComparison(c: fetchComparator(t1: t, t2: t, context));
76}
77
78/**
79 * @short Functor used by Qt's qSort() and qStableSort(). Used for FLWOR's
80 * <tt>order by</tt> expression.
81 *
82 * This must be in the std namespace, since it is specializing std::less(), which
83 * is in the std namespace. Hence it can't be in QPatternist.
84 */
85
86QT_END_NAMESPACE
87
88QT_USE_NAMESPACE
89
90namespace std {
91template<>
92struct less<Item::List>
93{
94private:
95
96 static inline bool isNaN(const Item &i)
97 {
98 return BuiltinTypes::xsDouble->xdtTypeMatches(other: i.type()) &&
99 i.as<Numeric>()->isNaN();
100 }
101
102public:
103 inline less(const OrderBy::OrderSpec::Vector &orderspecs,
104 const DynamicContext::Ptr &context) : m_orderSpecs(orderspecs)
105 , m_context(context)
106 {
107 Q_ASSERT(!m_orderSpecs.isEmpty());
108 Q_ASSERT(context);
109 }
110
111 inline bool operator()(const Item &item1, const Item &item2) const
112 {
113 const SortTuple *const s1 = item1.as<SortTuple>();
114 const SortTuple *const s2 = item2.as<SortTuple>();
115
116 const Item::Vector &sortKeys1 = s1->sortKeys();
117 const Item::Vector &sortKeys2 = s2->sortKeys();
118 const int len = sortKeys1.count();
119 Q_ASSERT(sortKeys1.count() == sortKeys2.count());
120
121 for(int i = 0; i < len; ++i)
122 {
123 const Item &i1 = sortKeys1.at(i);
124 const Item &i2 = sortKeys2.at(i);
125 const OrderBy::OrderSpec &orderSpec = m_orderSpecs.at(i);
126
127 if(!i1)
128 {
129 if(i2 && !isNaN(i: i2))
130 {
131 /* We got ((), item()). */
132 return orderSpec.orderingEmptySequence == StaticContext::Least ? orderSpec.direction == OrderBy::OrderSpec::Ascending
133 : orderSpec.direction != OrderBy::OrderSpec::Ascending;
134 }
135 else
136 return false;
137 }
138
139 if(!i2)
140 {
141 if(i1 && !isNaN(i: i1))
142 /* We got (item(), ()). */
143 return orderSpec.orderingEmptySequence == StaticContext::Greatest ? orderSpec.direction == OrderBy::OrderSpec::Ascending
144 : orderSpec.direction != OrderBy::OrderSpec::Ascending;
145 else
146 return false;
147 }
148
149 Q_ASSERT(orderSpec.direction == OrderBy::OrderSpec::Ascending ||
150 orderSpec.direction == OrderBy::OrderSpec::Descending);
151 const AtomicComparator::ComparisonResult result = orderSpec.detailedFlexibleCompare(it1: i1, it2: i2, context: m_context);
152
153 switch(result)
154 {
155 case AtomicComparator::LessThan:
156 return orderSpec.direction == OrderBy::OrderSpec::Ascending;
157 case AtomicComparator::GreaterThan:
158 return orderSpec.direction != OrderBy::OrderSpec::Ascending;
159 case AtomicComparator::Equal:
160 continue;
161 case AtomicComparator::Incomparable:
162 Q_ASSERT_X(false, Q_FUNC_INFO, "This code path assume values are always comparable.");
163 }
164 }
165
166 return false;
167 }
168
169private:
170 /* Yes, we store references here. */
171 const OrderBy::OrderSpec::Vector & m_orderSpecs;
172 const DynamicContext::Ptr & m_context;
173};
174} // namespace std
175
176QT_BEGIN_NAMESPACE
177
178Item::Iterator::Ptr OrderBy::mapToSequence(const Item &i,
179 const DynamicContext::Ptr &) const
180{
181 return i.as<SortTuple>()->value();
182}
183
184Item::Iterator::Ptr OrderBy::evaluateSequence(const DynamicContext::Ptr &context) const
185{
186 Item::List tuples(m_operand->evaluateSequence(context)->toList());
187
188 const std::less<Item::List> sorter(m_orderSpecs, context);
189
190 Q_ASSERT(m_stability == StableOrder || m_stability == UnstableOrder);
191
192 /* On one hand we could just disregard stability and always use qStableSort(), but maybe qSort()
193 * is a bit faster? */
194 if(m_stability == StableOrder)
195 std::stable_sort(first: tuples.begin(), last: tuples.end(), comp: sorter);
196 else
197 {
198 Q_ASSERT(m_stability == UnstableOrder);
199 std::sort(first: tuples.begin(), last: tuples.end(), comp: sorter);
200 }
201
202 return makeSequenceMappingIterator<Item>(mapper: ConstPtr(this),
203 source: makeListIterator(list: tuples),
204 context);
205}
206
207Expression::Ptr OrderBy::typeCheck(const StaticContext::Ptr &context,
208 const SequenceType::Ptr &reqType)
209{
210 m_returnOrderBy->setStay(true);
211
212 /* It's important we do the typeCheck() before calling OrderSpec::prepare(), since
213 * atomizers must first be inserted. */
214 const Expression::Ptr me(SingleContainer::typeCheck(context, reqType));
215
216 const Expression::List ops(m_returnOrderBy->operands());
217 const int len = ops.count();
218 Q_ASSERT(ops.count() > 1);
219 Q_ASSERT(m_orderSpecs.count() == ops.count() - 1);
220
221 for(int i = 1; i < len; ++i)
222 m_orderSpecs[i - 1].prepare(source: ops.at(i), context);
223
224 return me;
225
226 /* It's not meaningful to sort a single item or less, so rewrite ourselves
227 * away if that is the case. This is an optimization. */
228 /* TODO: How do we remove ReturnOrderBy?
229 if(Cardinality::zeroOrOne().isMatch(m_operand->staticType()->cardinality()))
230 return m_operand->typeCheck(context, reqType);
231 else
232 return SingleContainer::typeCheck(context, reqType);
233 */
234}
235
236Expression::Properties OrderBy::properties() const
237{
238 return m_operand->properties() & DisableElimination;
239}
240
241Expression::Ptr OrderBy::compress(const StaticContext::Ptr &context)
242{
243 /* If we only will produce one item, there's no point in sorting. */
244 if(m_operand->staticType()->cardinality().allowsMany())
245 return SingleContainer::compress(context);
246 else
247 {
248 m_returnOrderBy->setStay(false);
249 return m_operand->compress(context);
250 }
251}
252
253SequenceType::Ptr OrderBy::staticType() const
254{
255 return m_operand->staticType();
256}
257
258SequenceType::List OrderBy::expectedOperandTypes() const
259{
260 SequenceType::List result;
261 result.append(t: CommonSequenceTypes::ZeroOrMoreItems);
262 return result;
263}
264
265ExpressionVisitorResult::Ptr
266OrderBy::accept(const ExpressionVisitor::Ptr &visitor) const
267{
268 return visitor->visit(this);
269}
270
271QT_END_NAMESPACE
272

source code of qtxmlpatterns/src/xmlpatterns/expr/qorderby.cpp