1 /*
2 * Copyright (C) 2007, 2008, 2009 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14 * its contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "config.h"
30 #include "core/xml/XSLTUnicodeSort.h"
31
32 #include "wtf/text/WTFString.h"
33 #include "wtf/unicode/Collator.h"
34 #include <libxslt/templates.h>
35 #include <libxslt/xsltutils.h>
36
37 namespace WebCore {
38
toXMLChar(const char * string)39 inline const xmlChar* toXMLChar(const char* string)
40 {
41 return reinterpret_cast<const xmlChar*>(string);
42 }
43
44 // Based on default implementation from libxslt 1.1.22 and xsltICUSort.c
45 // example.
xsltUnicodeSortFunction(xsltTransformContextPtr ctxt,xmlNodePtr * sorts,int nbsorts)46 void xsltUnicodeSortFunction(xsltTransformContextPtr ctxt, xmlNodePtr *sorts, int nbsorts)
47 {
48 #ifdef XSLT_REFACTORED
49 xsltStyleItemSortPtr comp;
50 #else
51 xsltStylePreCompPtr comp;
52 #endif
53 xmlXPathObjectPtr* resultsTab[XSLT_MAX_SORT];
54 xmlXPathObjectPtr* results = 0;
55 xmlNodeSetPtr list = 0;
56 int depth;
57 xmlNodePtr node;
58 int tempstype[XSLT_MAX_SORT], temporder[XSLT_MAX_SORT];
59
60 if (!ctxt || !sorts || nbsorts <= 0 || nbsorts >= XSLT_MAX_SORT)
61 return;
62 if (!sorts[0])
63 return;
64 comp = static_cast<xsltStylePreComp*>(sorts[0]->psvi);
65 if (!comp)
66 return;
67
68 list = ctxt->nodeList;
69 if (!list || list->nodeNr <= 1)
70 return; // Nothing to do.
71
72 for (int j = 0; j < nbsorts; ++j) {
73 comp = static_cast<xsltStylePreComp*>(sorts[j]->psvi);
74 tempstype[j] = 0;
75 if (!comp->stype && comp->has_stype) {
76 comp->stype = xsltEvalAttrValueTemplate(ctxt, sorts[j], toXMLChar("data-type"), XSLT_NAMESPACE);
77 if (comp->stype) {
78 tempstype[j] = 1;
79 if (xmlStrEqual(comp->stype, toXMLChar("text"))) {
80 comp->number = 0;
81 } else if (xmlStrEqual(comp->stype, toXMLChar("number"))) {
82 comp->number = 1;
83 } else {
84 xsltTransformError(ctxt, 0, sorts[j], "xsltDoSortFunction: no support for data-type = %s\n", comp->stype);
85 comp->number = 0; // Use default.
86 }
87 }
88 }
89 temporder[j] = 0;
90 if (!comp->order && comp->has_order) {
91 comp->order = xsltEvalAttrValueTemplate(ctxt, sorts[j], toXMLChar("order"), XSLT_NAMESPACE);
92 if (comp->order) {
93 temporder[j] = 1;
94 if (xmlStrEqual(comp->order, toXMLChar("ascending"))) {
95 comp->descending = 0;
96 } else if (xmlStrEqual(comp->order, toXMLChar("descending"))) {
97 comp->descending = 1;
98 } else {
99 xsltTransformError(ctxt, 0, sorts[j], "xsltDoSortFunction: invalid value %s for order\n", comp->order);
100 comp->descending = 0; // Use default.
101 }
102 }
103 }
104 }
105
106 int len = list->nodeNr;
107
108 resultsTab[0] = xsltComputeSortResult(ctxt, sorts[0]);
109 for (int i = 1; i < XSLT_MAX_SORT; ++i)
110 resultsTab[i] = 0;
111
112 results = resultsTab[0];
113
114 comp = static_cast<xsltStylePreComp*>(sorts[0]->psvi);
115 int descending = comp->descending;
116 int number = comp->number;
117 if (!results)
118 return;
119
120 // We are passing a language identifier to a function that expects a locale
121 // identifier. The implementation of Collator should be lenient, and accept
122 // both "en-US" and "en_US", for example. This lets an author to really
123 // specify sorting rules, e.g. "de_DE@collation=phonebook", which isn't
124 // possible with language alone.
125 Collator collator(comp->has_lang ? reinterpret_cast<const char*>(comp->lang) : "en");
126 collator.setOrderLowerFirst(comp->lower_first);
127
128 // Shell's sort of node-set.
129 for (int incr = len / 2; incr > 0; incr /= 2) {
130 for (int i = incr; i < len; ++i) {
131 int j = i - incr;
132 if (!results[i])
133 continue;
134
135 while (j >= 0) {
136 int tst;
137 if (!results[j]) {
138 tst = 1;
139 } else {
140 if (number) {
141 // We make NaN smaller than number in accordance with
142 // XSLT spec.
143 if (xmlXPathIsNaN(results[j]->floatval)) {
144 if (xmlXPathIsNaN(results[j + incr]->floatval))
145 tst = 0;
146 else
147 tst = -1;
148 } else if (xmlXPathIsNaN(results[j + incr]->floatval)) {
149 tst = 1;
150 } else if (results[j]->floatval == results[j + incr]->floatval) {
151 tst = 0;
152 } else if (results[j]->floatval > results[j + incr]->floatval) {
153 tst = 1;
154 } else {
155 tst = -1;
156 }
157 } else {
158 Vector<UChar> string1;
159 Vector<UChar> string2;
160 String::fromUTF8(reinterpret_cast<const char*>(results[j]->stringval)).appendTo(string1);
161 String::fromUTF8(reinterpret_cast<const char*>(results[j + incr]->stringval)).appendTo(string2);
162 tst = collator.collate(string1.data(), string1.size(), string2.data(), string2.size());
163 }
164 if (descending)
165 tst = -tst;
166 }
167 if (tst == 0) {
168 // Okay we need to use multi level sorts.
169 depth = 1;
170 while (depth < nbsorts) {
171 if (!sorts[depth])
172 break;
173 comp = static_cast<xsltStylePreComp*>(sorts[depth]->psvi);
174 if (!comp)
175 break;
176 int desc = comp->descending;
177 int numb = comp->number;
178
179 // Compute the result of the next level for the full
180 // set, this might be optimized ... or not
181 if (!resultsTab[depth])
182 resultsTab[depth] = xsltComputeSortResult(ctxt, sorts[depth]);
183 xmlXPathObjectPtr* res = resultsTab[depth];
184 if (!res)
185 break;
186 if (!res[j]) {
187 if (res[j + incr])
188 tst = 1;
189 } else {
190 if (numb) {
191 // We make NaN smaller than number in accordance
192 // with XSLT spec.
193 if (xmlXPathIsNaN(res[j]->floatval)) {
194 if (xmlXPathIsNaN(res[j + incr]->floatval))
195 tst = 0;
196 else
197 tst = -1;
198 } else if (xmlXPathIsNaN(res[j + incr]->floatval)) {
199 tst = 1;
200 } else if (res[j]->floatval == res[j + incr]->floatval) {
201 tst = 0;
202 } else if (res[j]->floatval > res[j + incr]->floatval) {
203 tst = 1;
204 } else {
205 tst = -1;
206 }
207 } else {
208 Vector<UChar> string1;
209 Vector<UChar> string2;
210 String::fromUTF8(reinterpret_cast<const char*>(res[j]->stringval)).appendTo(string1);
211 String::fromUTF8(reinterpret_cast<const char*>(res[j + incr]->stringval)).appendTo(string2);
212 tst = collator.collate(string1.data(), string1.size(), string2.data(), string2.size());
213 }
214 if (desc)
215 tst = -tst;
216 }
217
218 // if we still can't differenciate at this level try one
219 // level deeper.
220 if (tst != 0)
221 break;
222 depth++;
223 }
224 }
225 if (tst == 0) {
226 tst = results[j]->index > results[j + incr]->index;
227 }
228 if (tst > 0) {
229 xmlXPathObjectPtr tmp = results[j];
230 results[j] = results[j + incr];
231 results[j + incr] = tmp;
232 node = list->nodeTab[j];
233 list->nodeTab[j] = list->nodeTab[j + incr];
234 list->nodeTab[j + incr] = node;
235 depth = 1;
236 while (depth < nbsorts) {
237 if (!sorts[depth])
238 break;
239 if (!resultsTab[depth])
240 break;
241 xmlXPathObjectPtr* res = resultsTab[depth];
242 tmp = res[j];
243 res[j] = res[j + incr];
244 res[j + incr] = tmp;
245 depth++;
246 }
247 j -= incr;
248 } else {
249 break;
250 }
251 }
252 }
253 }
254
255 for (int j = 0; j < nbsorts; ++j) {
256 comp = static_cast<xsltStylePreComp*>(sorts[j]->psvi);
257 if (tempstype[j] == 1) {
258 // The data-type needs to be recomputed each time.
259 xmlFree(const_cast<xmlChar*>(comp->stype));
260 comp->stype = 0;
261 }
262 if (temporder[j] == 1) {
263 // The order needs to be recomputed each time.
264 xmlFree(const_cast<xmlChar*>(comp->order));
265 comp->order = 0;
266 }
267 if (resultsTab[j]) {
268 for (int i = 0; i < len; ++i)
269 xmlXPathFreeObject(resultsTab[j][i]);
270 xmlFree(resultsTab[j]);
271 }
272 }
273 }
274
275 } // namespace WebCore
276