Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /* This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #include "txNodeSorter.h"
7 : #include "txExecutionState.h"
8 : #include "txXPathResultComparator.h"
9 : #include "nsGkAtoms.h"
10 : #include "txNodeSetContext.h"
11 : #include "txExpr.h"
12 : #include "txStringUtils.h"
13 : #include "nsQuickSort.h"
14 :
15 : #include "mozilla/CheckedInt.h"
16 : #include "mozilla/UniquePtrExtensions.h"
17 :
18 : using mozilla::CheckedUint32;
19 : using mozilla::MakeUniqueFallible;
20 :
21 : /*
22 : * Sorts Nodes as specified by the W3C XSLT 1.0 Recommendation
23 : */
24 :
25 0 : txNodeSorter::txNodeSorter() : mNKeys(0)
26 : {
27 0 : }
28 :
29 0 : txNodeSorter::~txNodeSorter()
30 : {
31 0 : txListIterator iter(&mSortKeys);
32 0 : while (iter.hasNext()) {
33 0 : SortKey* key = (SortKey*)iter.next();
34 0 : delete key->mComparator;
35 : delete key;
36 : }
37 0 : }
38 :
39 : nsresult
40 0 : txNodeSorter::addSortElement(Expr* aSelectExpr, Expr* aLangExpr,
41 : Expr* aDataTypeExpr, Expr* aOrderExpr,
42 : Expr* aCaseOrderExpr, txIEvalContext* aContext)
43 : {
44 0 : nsAutoPtr<SortKey> key(new SortKey);
45 0 : nsresult rv = NS_OK;
46 :
47 : // Select
48 0 : key->mExpr = aSelectExpr;
49 :
50 : // Order
51 0 : bool ascending = true;
52 0 : if (aOrderExpr) {
53 0 : nsAutoString attrValue;
54 0 : rv = aOrderExpr->evaluateToString(aContext, attrValue);
55 0 : NS_ENSURE_SUCCESS(rv, rv);
56 :
57 0 : if (TX_StringEqualsAtom(attrValue, nsGkAtoms::descending)) {
58 0 : ascending = false;
59 : }
60 0 : else if (!TX_StringEqualsAtom(attrValue, nsGkAtoms::ascending)) {
61 : // XXX ErrorReport: unknown value for order attribute
62 0 : return NS_ERROR_XSLT_BAD_VALUE;
63 : }
64 : }
65 :
66 :
67 : // Create comparator depending on datatype
68 0 : nsAutoString dataType;
69 0 : if (aDataTypeExpr) {
70 0 : rv = aDataTypeExpr->evaluateToString(aContext, dataType);
71 0 : NS_ENSURE_SUCCESS(rv, rv);
72 : }
73 :
74 0 : if (!aDataTypeExpr || TX_StringEqualsAtom(dataType, nsGkAtoms::text)) {
75 : // Text comparator
76 :
77 : // Language
78 0 : nsAutoString lang;
79 0 : if (aLangExpr) {
80 0 : rv = aLangExpr->evaluateToString(aContext, lang);
81 0 : NS_ENSURE_SUCCESS(rv, rv);
82 : }
83 :
84 : // Case-order
85 0 : bool upperFirst = false;
86 0 : if (aCaseOrderExpr) {
87 0 : nsAutoString attrValue;
88 :
89 0 : rv = aCaseOrderExpr->evaluateToString(aContext, attrValue);
90 0 : NS_ENSURE_SUCCESS(rv, rv);
91 :
92 0 : if (TX_StringEqualsAtom(attrValue, nsGkAtoms::upperFirst)) {
93 0 : upperFirst = true;
94 : }
95 0 : else if (!TX_StringEqualsAtom(attrValue,
96 : nsGkAtoms::lowerFirst)) {
97 : // XXX ErrorReport: unknown value for case-order attribute
98 0 : return NS_ERROR_XSLT_BAD_VALUE;
99 : }
100 : }
101 :
102 0 : key->mComparator = new txResultStringComparator(ascending,
103 : upperFirst,
104 0 : lang);
105 : }
106 0 : else if (TX_StringEqualsAtom(dataType, nsGkAtoms::number)) {
107 : // Number comparator
108 0 : key->mComparator = new txResultNumberComparator(ascending);
109 : }
110 : else {
111 : // XXX ErrorReport: unknown data-type
112 0 : return NS_ERROR_XSLT_BAD_VALUE;
113 : }
114 :
115 : // mSortKeys owns key now.
116 0 : rv = mSortKeys.add(key);
117 0 : NS_ENSURE_SUCCESS(rv, rv);
118 :
119 0 : key.forget();
120 0 : mNKeys++;
121 :
122 0 : return NS_OK;
123 : }
124 :
125 : nsresult
126 0 : txNodeSorter::sortNodeSet(txNodeSet* aNodes, txExecutionState* aEs,
127 : txNodeSet** aResult)
128 : {
129 0 : if (mNKeys == 0 || aNodes->isEmpty()) {
130 0 : RefPtr<txNodeSet> ref(aNodes);
131 0 : ref.forget(aResult);
132 :
133 0 : return NS_OK;
134 : }
135 :
136 0 : *aResult = nullptr;
137 :
138 0 : RefPtr<txNodeSet> sortedNodes;
139 0 : nsresult rv = aEs->recycler()->getNodeSet(getter_AddRefs(sortedNodes));
140 0 : NS_ENSURE_SUCCESS(rv, rv);
141 :
142 0 : txNodeSetContext* evalContext = new txNodeSetContext(aNodes, aEs);
143 0 : NS_ENSURE_TRUE(evalContext, NS_ERROR_OUT_OF_MEMORY);
144 :
145 0 : rv = aEs->pushEvalContext(evalContext);
146 0 : NS_ENSURE_SUCCESS(rv, rv);
147 :
148 : // Create and set up memoryblock for sort-values and indexarray
149 0 : CheckedUint32 len = aNodes->size();
150 0 : CheckedUint32 numSortValues = len * mNKeys;
151 0 : CheckedUint32 sortValuesSize = numSortValues * sizeof(txObject*);
152 0 : if (!sortValuesSize.isValid()) {
153 0 : return NS_ERROR_OUT_OF_MEMORY;
154 : }
155 :
156 0 : auto indexes = MakeUniqueFallible<uint32_t[]>(len.value());
157 0 : auto sortValues = MakeUniqueFallible<txObject*[]>(numSortValues.value());
158 0 : if (!indexes || !sortValues) {
159 0 : return NS_ERROR_OUT_OF_MEMORY;
160 : }
161 :
162 : uint32_t i;
163 0 : for (i = 0; i < len.value(); ++i) {
164 0 : indexes[i] = i;
165 : }
166 0 : memset(sortValues.get(), 0, sortValuesSize.value());
167 :
168 : // Sort the indexarray
169 : SortData sortData;
170 0 : sortData.mNodeSorter = this;
171 0 : sortData.mContext = evalContext;
172 0 : sortData.mSortValues = sortValues.get();
173 0 : sortData.mRv = NS_OK;
174 0 : NS_QuickSort(indexes.get(), len.value(), sizeof(uint32_t), compareNodes, &sortData);
175 :
176 : // Delete these here so we don't have to deal with them at every possible
177 : // failurepoint
178 0 : for (i = 0; i < numSortValues.value(); ++i) {
179 0 : delete sortValues[i];
180 : }
181 :
182 0 : if (NS_FAILED(sortData.mRv)) {
183 : // The txExecutionState owns the evalcontext so no need to handle it
184 0 : return sortData.mRv;
185 : }
186 :
187 : // Insert nodes in sorted order in new nodeset
188 0 : for (i = 0; i < len.value(); ++i) {
189 0 : rv = sortedNodes->append(aNodes->get(indexes[i]));
190 0 : if (NS_FAILED(rv)) {
191 : // The txExecutionState owns the evalcontext so no need to handle it
192 0 : return rv;
193 : }
194 : }
195 :
196 0 : delete aEs->popEvalContext();
197 :
198 0 : sortedNodes.forget(aResult);
199 :
200 0 : return NS_OK;
201 : }
202 :
203 : // static
204 : int
205 0 : txNodeSorter::compareNodes(const void* aIndexA, const void* aIndexB,
206 : void* aSortData)
207 : {
208 0 : SortData* sortData = static_cast<SortData*>(aSortData);
209 0 : NS_ENSURE_SUCCESS(sortData->mRv, -1);
210 :
211 0 : txListIterator iter(&sortData->mNodeSorter->mSortKeys);
212 0 : uint32_t indexA = *static_cast<const uint32_t*>(aIndexA);
213 0 : uint32_t indexB = *static_cast<const uint32_t*>(aIndexB);
214 0 : txObject** sortValuesA = sortData->mSortValues +
215 0 : indexA * sortData->mNodeSorter->mNKeys;
216 0 : txObject** sortValuesB = sortData->mSortValues +
217 0 : indexB * sortData->mNodeSorter->mNKeys;
218 :
219 : unsigned int i;
220 : // Step through each key until a difference is found
221 0 : for (i = 0; i < sortData->mNodeSorter->mNKeys; ++i) {
222 0 : SortKey* key = (SortKey*)iter.next();
223 : // Lazy create sort values
224 0 : if (!sortValuesA[i] &&
225 0 : !calcSortValue(sortValuesA[i], key, sortData, indexA)) {
226 0 : return -1;
227 : }
228 0 : if (!sortValuesB[i] &&
229 0 : !calcSortValue(sortValuesB[i], key, sortData, indexB)) {
230 0 : return -1;
231 : }
232 :
233 : // Compare node values
234 0 : int compRes = key->mComparator->compareValues(sortValuesA[i],
235 0 : sortValuesB[i]);
236 0 : if (compRes != 0)
237 0 : return compRes;
238 : }
239 : // All keys have the same value for these nodes
240 :
241 0 : return indexA - indexB;
242 : }
243 :
244 : //static
245 : bool
246 0 : txNodeSorter::calcSortValue(txObject*& aSortValue, SortKey* aKey,
247 : SortData* aSortData, uint32_t aNodeIndex)
248 : {
249 0 : aSortData->mContext->setPosition(aNodeIndex + 1); // position is 1-based
250 :
251 0 : nsresult rv = aKey->mComparator->createSortableValue(aKey->mExpr,
252 0 : aSortData->mContext,
253 0 : aSortValue);
254 0 : if (NS_FAILED(rv)) {
255 0 : aSortData->mRv = rv;
256 0 : return false;
257 : }
258 :
259 0 : return true;
260 : }
|
