1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtXmlPatterns module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    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