src/xmlpatterns/expr/qorderby.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtXmlPatterns module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include <QtAlgorithms>
  43
  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"
  51
  52 #include "qorderby_p.h"
  53
  54 QT_BEGIN_NAMESPACE
  55
  56 using namespace QPatternist;
  57
  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)
  65 {
  66     Q_ASSERT(m_returnOrderBy);
  67 }
  68
  69 void OrderBy::OrderSpec::prepare(const Expression::Ptr &source,
  70                                  const StaticContext::Ptr &context)
  71 {
  72     m_expr = source;
  73     const ItemType::Ptr t(source->staticType()->itemType());
  74     prepareComparison(fetchComparator(t, t, context));
  75 }
  76
  77 /**
  78  * @short Functor used by Qt's qSort() and qStableSort(). Used for FLWOR's
  79  * <tt>order by</tt> expression.
  80  *
  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.
  83  */
  84 template<>
  85 class qLess<Item::List>
  86 {
  87 private:
  88
  89     static inline bool isNaN(const Item &i)
  90     {
  91         return BuiltinTypes::xsDouble->xdtTypeMatches(i.type()) &&
  92                i.as<Numeric>()->isNaN();
  93     }
  94
  95 public:
  96     inline qLess(const OrderBy::OrderSpec::Vector &orderspecs,
  97                  const DynamicContext::Ptr &context) : m_orderSpecs(orderspecs)
  98                                                      , m_context(context)
  99     {
 100         Q_ASSERT(!m_orderSpecs.isEmpty());
 101         Q_ASSERT(context);
 102     }
 103
 104     inline bool operator()(const Item &item1, const Item &item2) const
 105     {
 106         const SortTuple *const s1 = item1.as<SortTuple>();
 107         const SortTuple *const s2 = item2.as<SortTuple>();
 108
 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());
 113
 114         for(int i = 0; i < len; ++i)
 115         {
 116             const Item &i1 = sortKeys1.at(i);
 117             const Item &i2 = sortKeys2.at(i);
 118             const OrderBy::OrderSpec &orderSpec = m_orderSpecs.at(i);
 119
 120             if(!i1)
 121             {
 122                 if(i2 && !isNaN(i2))
 123                 {
 124                     /* We got ((), item()). */
 125                     return orderSpec.orderingEmptySequence == StaticContext::Least ? orderSpec.direction == OrderBy::OrderSpec::Ascending
 126                                                                                    : orderSpec.direction != OrderBy::OrderSpec::Ascending;
 127                 }
 128                 else
 129                     return false;
 130             }
 131
 132             if(!i2)
 133             {
 134                 if(i1 && !isNaN(i1))
 135                     /* We got (item(), ()). */
 136                     return orderSpec.orderingEmptySequence == StaticContext::Greatest ? orderSpec.direction == OrderBy::OrderSpec::Ascending
 137                                                                                       : orderSpec.direction != OrderBy::OrderSpec::Ascending;
 138                 else
 139                     return false;
 140             }
 141
 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);
 145
 146             switch(result)
 147             {
 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:
 153                     continue;
 154                 case AtomicComparator::Incomparable:
 155                     Q_ASSERT_X(false, Q_FUNC_INFO, "This code path assume values are always comparable.");
 156             }
 157         }
 158
 159         return false;
 160     }
 161
 162 private:
 163     /* Yes, we store references here. */
 164     const OrderBy::OrderSpec::Vector & m_orderSpecs;
 165     const DynamicContext::Ptr & m_context;
 166 };
 167
 168 Item::Iterator::Ptr OrderBy::mapToSequence(const Item &i,
 169                                            const DynamicContext::Ptr &) const
 170 {
 171     return i.as<SortTuple>()->value();
 172 }
 173
 174 Item::Iterator::Ptr OrderBy::evaluateSequence(const DynamicContext::Ptr &context) const
 175 {
 176     Item::List tuples(m_operand->evaluateSequence(context)->toList());
 177
 178     const qLess<Item::List> sorter(m_orderSpecs, context);
 179
 180     Q_ASSERT(m_stability == StableOrder || m_stability == UnstableOrder);
 181
 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);
 186     else
 187     {
 188         Q_ASSERT(m_stability == UnstableOrder);
 189         qSort(tuples.begin(), tuples.end(), sorter);
 190     }
 191
 192     return makeSequenceMappingIterator<Item>(ConstPtr(this),
 193                                              makeListIterator(tuples),
 194                                              context);
 195 }
 196
 197 Expression::Ptr OrderBy::typeCheck(const StaticContext::Ptr &context,
 198                                    const SequenceType::Ptr &reqType)
 199 {
 200     m_returnOrderBy->setStay(true);
 201
 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));
 205
 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);
 210
 211     for(int i = 1; i < len; ++i)
 212         m_orderSpecs[i - 1].prepare(ops.at(i), context);
 213
 214     return me;
 215
 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);
 221     else
 222         return SingleContainer::typeCheck(context, reqType);
 223      */
 224 }
 225
 226 Expression::Properties OrderBy::properties() const
 227 {
 228     return m_operand->properties() & DisableElimination;
 229 }
 230
 231 Expression::Ptr OrderBy::compress(const StaticContext::Ptr &context)
 232 {
 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);
 236     else
 237     {
 238         m_returnOrderBy->setStay(false);
 239         return m_operand->compress(context);
 240     }
 241 }
 242
 243 SequenceType::Ptr OrderBy::staticType() const
 244 {
 245     return m_operand->staticType();
 246 }
 247
 248 SequenceType::List OrderBy::expectedOperandTypes() const
 249 {
 250     SequenceType::List result;
 251     result.append(CommonSequenceTypes::ZeroOrMoreItems);
 252     return result;
 253 }
 254
 255 ExpressionVisitorResult::Ptr
 256 OrderBy::accept(const ExpressionVisitor::Ptr &visitor) const
 257 {
 258     return visitor->visit(this);
 259 }
 260
 261 QT_END_NAMESPACE