1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** All rights reserved.
5 ** Contact: Nokia Corporation (qt-info@nokia.com)
7 ** This file is part of the QtXmlPatterns module of the Qt Toolkit.
9 ** $QT_BEGIN_LICENSE:LGPL$
10 ** GNU Lesser General Public License Usage
11 ** This file may be used under the terms of the GNU Lesser General Public
12 ** License version 2.1 as published by the Free Software Foundation and
13 ** appearing in the file LICENSE.LGPL included in the packaging of this
14 ** file. Please review the following information to ensure the GNU Lesser
15 ** General Public License version 2.1 requirements will be met:
16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
18 ** In addition, as a special exception, Nokia gives you certain additional
19 ** rights. These rights are described in the Nokia Qt LGPL Exception
20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
22 ** GNU General Public License Usage
23 ** Alternatively, this file may be used under the terms of the GNU General
24 ** Public License version 3.0 as published by the Free Software Foundation
25 ** and appearing in the file LICENSE.GPL included in the packaging of this
26 ** file. Please review the following information to ensure the GNU General
27 ** Public License version 3.0 requirements will be met:
28 ** http://www.gnu.org/copyleft/gpl.html.
31 ** Alternatively, this file may be used in accordance with the terms and
32 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
42 #include <QtAlgorithms>
44 #include "qcommonsequencetypes_p.h"
45 #include "qnodebuilder_p.h"
46 #include "qschemanumeric_p.h"
47 #include "qpatternistlocale_p.h"
48 #include "qreturnorderby_p.h"
49 #include "qsorttuple_p.h"
50 #include "qsequencemappingiterator_p.h"
52 #include "qorderby_p.h"
56 using namespace QPatternist;
58 OrderBy::OrderBy(const Stability stability,
59 const OrderSpec::Vector &aOrderSpecs,
60 const Expression::Ptr &op,
61 ReturnOrderBy *const returnOrderBy) : SingleContainer(op)
62 , m_stability(stability)
63 , m_orderSpecs(aOrderSpecs)
64 , m_returnOrderBy(returnOrderBy)
66 Q_ASSERT(m_returnOrderBy);
69 void OrderBy::OrderSpec::prepare(const Expression::Ptr &source,
70 const StaticContext::Ptr &context)
73 const ItemType::Ptr t(source->staticType()->itemType());
74 prepareComparison(fetchComparator(t, t, context));
78 * @short Functor used by Qt's qSort() and qStableSort(). Used for FLWOR's
79 * <tt>order by</tt> expression.
81 * This must be in the global namespace, since it is specializing qLess(), which
82 * is in the global namespace. Hence it can't be in QPatternist.
85 class qLess<Item::List>
89 static inline bool isNaN(const Item &i)
91 return BuiltinTypes::xsDouble->xdtTypeMatches(i.type()) &&
92 i.as<Numeric>()->isNaN();
96 inline qLess(const OrderBy::OrderSpec::Vector &orderspecs,
97 const DynamicContext::Ptr &context) : m_orderSpecs(orderspecs)
100 Q_ASSERT(!m_orderSpecs.isEmpty());
104 inline bool operator()(const Item &item1, const Item &item2) const
106 const SortTuple *const s1 = item1.as<SortTuple>();
107 const SortTuple *const s2 = item2.as<SortTuple>();
109 const Item::Vector &sortKeys1 = s1->sortKeys();
110 const Item::Vector &sortKeys2 = s2->sortKeys();
111 const int len = sortKeys1.count();
112 Q_ASSERT(sortKeys1.count() == sortKeys2.count());
114 for(int i = 0; i < len; ++i)
116 const Item &i1 = sortKeys1.at(i);
117 const Item &i2 = sortKeys2.at(i);
118 const OrderBy::OrderSpec &orderSpec = m_orderSpecs.at(i);
124 /* We got ((), item()). */
125 return orderSpec.orderingEmptySequence == StaticContext::Least ? orderSpec.direction == OrderBy::OrderSpec::Ascending
126 : orderSpec.direction != OrderBy::OrderSpec::Ascending;
135 /* We got (item(), ()). */
136 return orderSpec.orderingEmptySequence == StaticContext::Greatest ? orderSpec.direction == OrderBy::OrderSpec::Ascending
137 : orderSpec.direction != OrderBy::OrderSpec::Ascending;
142 Q_ASSERT(orderSpec.direction == OrderBy::OrderSpec::Ascending ||
143 orderSpec.direction == OrderBy::OrderSpec::Descending);
144 const AtomicComparator::ComparisonResult result = orderSpec.detailedFlexibleCompare(i1, i2, m_context);
148 case AtomicComparator::LessThan:
149 return orderSpec.direction == OrderBy::OrderSpec::Ascending;
150 case AtomicComparator::GreaterThan:
151 return orderSpec.direction != OrderBy::OrderSpec::Ascending;
152 case AtomicComparator::Equal:
154 case AtomicComparator::Incomparable:
155 Q_ASSERT_X(false, Q_FUNC_INFO, "This code path assume values are always comparable.");
163 /* Yes, we store references here. */
164 const OrderBy::OrderSpec::Vector & m_orderSpecs;
165 const DynamicContext::Ptr & m_context;
168 Item::Iterator::Ptr OrderBy::mapToSequence(const Item &i,
169 const DynamicContext::Ptr &) const
171 return i.as<SortTuple>()->value();
174 Item::Iterator::Ptr OrderBy::evaluateSequence(const DynamicContext::Ptr &context) const
176 Item::List tuples(m_operand->evaluateSequence(context)->toList());
178 const qLess<Item::List> sorter(m_orderSpecs, context);
180 Q_ASSERT(m_stability == StableOrder || m_stability == UnstableOrder);
182 /* On one hand we could just disregard stability and always use qStableSort(), but maybe qSort()
183 * is a bit faster? */
184 if(m_stability == StableOrder)
185 qStableSort(tuples.begin(), tuples.end(), sorter);
188 Q_ASSERT(m_stability == UnstableOrder);
189 qSort(tuples.begin(), tuples.end(), sorter);
192 return makeSequenceMappingIterator<Item>(ConstPtr(this),
193 makeListIterator(tuples),
197 Expression::Ptr OrderBy::typeCheck(const StaticContext::Ptr &context,
198 const SequenceType::Ptr &reqType)
200 m_returnOrderBy->setStay(true);
202 /* It's important we do the typeCheck() before calling OrderSpec::prepare(), since
203 * atomizers must first be inserted. */
204 const Expression::Ptr me(SingleContainer::typeCheck(context, reqType));
206 const Expression::List ops(m_returnOrderBy->operands());
207 const int len = ops.count();
208 Q_ASSERT(ops.count() > 1);
209 Q_ASSERT(m_orderSpecs.count() == ops.count() - 1);
211 for(int i = 1; i < len; ++i)
212 m_orderSpecs[i - 1].prepare(ops.at(i), context);
216 /* It's not meaningful to sort a single item or less, so rewrite ourselves
217 * away if that is the case. This is an optimization. */
218 /* TODO: How do we remove ReturnOrderBy?
219 if(Cardinality::zeroOrOne().isMatch(m_operand->staticType()->cardinality()))
220 return m_operand->typeCheck(context, reqType);
222 return SingleContainer::typeCheck(context, reqType);
226 Expression::Properties OrderBy::properties() const
228 return m_operand->properties() & DisableElimination;
231 Expression::Ptr OrderBy::compress(const StaticContext::Ptr &context)
233 /* If we only will produce one item, there's no point in sorting. */
234 if(m_operand->staticType()->cardinality().allowsMany())
235 return SingleContainer::compress(context);
238 m_returnOrderBy->setStay(false);
239 return m_operand->compress(context);
243 SequenceType::Ptr OrderBy::staticType() const
245 return m_operand->staticType();
248 SequenceType::List OrderBy::expectedOperandTypes() const
250 SequenceType::List result;
251 result.append(CommonSequenceTypes::ZeroOrMoreItems);
255 ExpressionVisitorResult::Ptr
256 OrderBy::accept(const ExpressionVisitor::Ptr &visitor) const
258 return visitor->visit(this);