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 "XSLTUnicodeSort.h"
31
32 #if ENABLE(XSLT)
33
34 #include "PlatformString.h"
35 #include <libxslt/templates.h>
36 #include <libxslt/xsltutils.h>
37 #include <wtf/unicode/Collator.h>
38
39 #if PLATFORM(MAC)
40 #include "SoftLinking.h"
41 #endif
42
43 #if PLATFORM(MAC)
44
45 SOFT_LINK_LIBRARY(libxslt)
46 SOFT_LINK(libxslt, xsltComputeSortResult, xmlXPathObjectPtr*, (xsltTransformContextPtr ctxt, xmlNodePtr sort), (ctxt, sort))
47 SOFT_LINK(libxslt, xsltEvalAttrValueTemplate, xmlChar*, (xsltTransformContextPtr ctxt, xmlNodePtr node, const xmlChar *name, const xmlChar *ns), (ctxt, node, name, ns))
48
49 static void xsltTransformErrorTrampoline(xsltTransformContextPtr, xsltStylesheetPtr, xmlNodePtr, const char* message, ...) WTF_ATTRIBUTE_PRINTF(4, 5);
50
xsltTransformErrorTrampoline(xsltTransformContextPtr context,xsltStylesheetPtr style,xmlNodePtr node,const char * message,...)51 void xsltTransformErrorTrampoline(xsltTransformContextPtr context, xsltStylesheetPtr style, xmlNodePtr node, const char* message, ...)
52 {
53 va_list args;
54 va_start(args, message);
55 char* messageWithArgs;
56 vasprintf(&messageWithArgs, message, args);
57 va_end(args);
58
59 static void (*xsltTransformErrorPointer)(xsltTransformContextPtr, xsltStylesheetPtr, xmlNodePtr, const char*, ...) WTF_ATTRIBUTE_PRINTF(4, 5)
60 = reinterpret_cast<void (*)(xsltTransformContextPtr, xsltStylesheetPtr, xmlNodePtr, const char*, ...)>(dlsym(libxsltLibrary(), "xsltTransformError"));
61 xsltTransformErrorPointer(context, style, node, "%s", messageWithArgs);
62
63 free(messageWithArgs);
64 }
65
66 #define xsltTransformError xsltTransformErrorTrampoline
67
68 #endif
69
70 namespace WebCore {
71
72 // Based on default implementation from libxslt 1.1.22 and xsltICUSort.c example.
xsltUnicodeSortFunction(xsltTransformContextPtr ctxt,xmlNodePtr * sorts,int nbsorts)73 void xsltUnicodeSortFunction(xsltTransformContextPtr ctxt, xmlNodePtr *sorts, int nbsorts)
74 {
75 #ifdef XSLT_REFACTORED
76 xsltStyleItemSortPtr comp;
77 #else
78 xsltStylePreCompPtr comp;
79 #endif
80 xmlXPathObjectPtr *resultsTab[XSLT_MAX_SORT];
81 xmlXPathObjectPtr *results = NULL, *res;
82 xmlNodeSetPtr list = NULL;
83 int descending, number, desc, numb;
84 int len = 0;
85 int i, j, incr;
86 int tst;
87 int depth;
88 xmlNodePtr node;
89 xmlXPathObjectPtr tmp;
90 int tempstype[XSLT_MAX_SORT], temporder[XSLT_MAX_SORT];
91
92 if ((ctxt == NULL) || (sorts == NULL) || (nbsorts <= 0) ||
93 (nbsorts >= XSLT_MAX_SORT))
94 return;
95 if (sorts[0] == NULL)
96 return;
97 comp = static_cast<xsltStylePreComp*>(sorts[0]->psvi);
98 if (comp == NULL)
99 return;
100
101 list = ctxt->nodeList;
102 if ((list == NULL) || (list->nodeNr <= 1))
103 return; /* nothing to do */
104
105 for (j = 0; j < nbsorts; j++) {
106 comp = static_cast<xsltStylePreComp*>(sorts[j]->psvi);
107 tempstype[j] = 0;
108 if ((comp->stype == NULL) && (comp->has_stype != 0)) {
109 comp->stype =
110 xsltEvalAttrValueTemplate(ctxt, sorts[j],
111 (const xmlChar *) "data-type",
112 XSLT_NAMESPACE);
113 if (comp->stype != NULL) {
114 tempstype[j] = 1;
115 if (xmlStrEqual(comp->stype, (const xmlChar *) "text"))
116 comp->number = 0;
117 else if (xmlStrEqual(comp->stype, (const xmlChar *) "number"))
118 comp->number = 1;
119 else {
120 xsltTransformError(ctxt, NULL, sorts[j],
121 "xsltDoSortFunction: no support for data-type = %s\n",
122 comp->stype);
123 comp->number = 0; /* use default */
124 }
125 }
126 }
127 temporder[j] = 0;
128 if ((comp->order == NULL) && (comp->has_order != 0)) {
129 comp->order = xsltEvalAttrValueTemplate(ctxt, sorts[j],
130 (const xmlChar *) "order",
131 XSLT_NAMESPACE);
132 if (comp->order != NULL) {
133 temporder[j] = 1;
134 if (xmlStrEqual(comp->order, (const xmlChar *) "ascending"))
135 comp->descending = 0;
136 else if (xmlStrEqual(comp->order,
137 (const xmlChar *) "descending"))
138 comp->descending = 1;
139 else {
140 xsltTransformError(ctxt, NULL, sorts[j],
141 "xsltDoSortFunction: invalid value %s for order\n",
142 comp->order);
143 comp->descending = 0; /* use default */
144 }
145 }
146 }
147 }
148
149 len = list->nodeNr;
150
151 resultsTab[0] = xsltComputeSortResult(ctxt, sorts[0]);
152 for (i = 1;i < XSLT_MAX_SORT;i++)
153 resultsTab[i] = NULL;
154
155 results = resultsTab[0];
156
157 comp = static_cast<xsltStylePreComp*>(sorts[0]->psvi);
158 descending = comp->descending;
159 number = comp->number;
160 if (results == NULL)
161 return;
162
163 // We are passing a language identifier to a function that expects a locale identifier.
164 // The implementation of Collator should be lenient, and accept both "en-US" and "en_US", for example.
165 // This lets an author to really specify sorting rules, e.g. "de_DE@collation=phonebook", which isn't
166 // possible with language alone.
167 Collator collator(comp->has_lang ? (const char*)comp->lang : "en");
168 collator.setOrderLowerFirst(comp->lower_first);
169
170 /* Shell's sort of node-set */
171 for (incr = len / 2; incr > 0; incr /= 2) {
172 for (i = incr; i < len; i++) {
173 j = i - incr;
174 if (results[i] == NULL)
175 continue;
176
177 while (j >= 0) {
178 if (results[j] == NULL)
179 tst = 1;
180 else {
181 if (number) {
182 /* We make NaN smaller than number in accordance
183 with XSLT spec */
184 if (xmlXPathIsNaN(results[j]->floatval)) {
185 if (xmlXPathIsNaN(results[j + incr]->floatval))
186 tst = 0;
187 else
188 tst = -1;
189 } else if (xmlXPathIsNaN(results[j + incr]->floatval))
190 tst = 1;
191 else if (results[j]->floatval ==
192 results[j + incr]->floatval)
193 tst = 0;
194 else if (results[j]->floatval >
195 results[j + incr]->floatval)
196 tst = 1;
197 else tst = -1;
198 } else {
199 String str1 = String::fromUTF8((const char*)results[j]->stringval);
200 String str2 = String::fromUTF8((const char*)results[j + incr]->stringval);
201 tst = collator.collate(str1.characters(), str1.length(), str2.characters(), str2.length());
202 }
203 if (descending)
204 tst = -tst;
205 }
206 if (tst == 0) {
207 /*
208 * Okay we need to use multi level sorts
209 */
210 depth = 1;
211 while (depth < nbsorts) {
212 if (sorts[depth] == NULL)
213 break;
214 comp = static_cast<xsltStylePreComp*>(sorts[depth]->psvi);
215 if (comp == NULL)
216 break;
217 desc = comp->descending;
218 numb = comp->number;
219
220 /*
221 * Compute the result of the next level for the
222 * full set, this might be optimized ... or not
223 */
224 if (resultsTab[depth] == NULL)
225 resultsTab[depth] = xsltComputeSortResult(ctxt,
226 sorts[depth]);
227 res = resultsTab[depth];
228 if (res == NULL)
229 break;
230 if (res[j] == NULL) {
231 if (res[j+incr] != NULL)
232 tst = 1;
233 } else {
234 if (numb) {
235 /* We make NaN smaller than number in
236 accordance with XSLT spec */
237 if (xmlXPathIsNaN(res[j]->floatval)) {
238 if (xmlXPathIsNaN(res[j +
239 incr]->floatval))
240 tst = 0;
241 else
242 tst = -1;
243 } else if (xmlXPathIsNaN(res[j + incr]->
244 floatval))
245 tst = 1;
246 else if (res[j]->floatval == res[j + incr]->
247 floatval)
248 tst = 0;
249 else if (res[j]->floatval >
250 res[j + incr]->floatval)
251 tst = 1;
252 else tst = -1;
253 } else {
254 String str1 = String::fromUTF8((const char*)res[j]->stringval);
255 String str2 = String::fromUTF8((const char*)res[j + incr]->stringval);
256 tst = collator.collate(str1.characters(), str1.length(), str2.characters(), str2.length());
257 }
258 if (desc)
259 tst = -tst;
260 }
261
262 /*
263 * if we still can't differenciate at this level
264 * try one level deeper.
265 */
266 if (tst != 0)
267 break;
268 depth++;
269 }
270 }
271 if (tst == 0) {
272 tst = results[j]->index > results[j + incr]->index;
273 }
274 if (tst > 0) {
275 tmp = results[j];
276 results[j] = results[j + incr];
277 results[j + incr] = tmp;
278 node = list->nodeTab[j];
279 list->nodeTab[j] = list->nodeTab[j + incr];
280 list->nodeTab[j + incr] = node;
281 depth = 1;
282 while (depth < nbsorts) {
283 if (sorts[depth] == NULL)
284 break;
285 if (resultsTab[depth] == NULL)
286 break;
287 res = resultsTab[depth];
288 tmp = res[j];
289 res[j] = res[j + incr];
290 res[j + incr] = tmp;
291 depth++;
292 }
293 j -= incr;
294 } else
295 break;
296 }
297 }
298 }
299
300 for (j = 0; j < nbsorts; j++) {
301 comp = static_cast<xsltStylePreComp*>(sorts[j]->psvi);
302 if (tempstype[j] == 1) {
303 /* The data-type needs to be recomputed each time */
304 xmlFree((void *)(comp->stype));
305 comp->stype = NULL;
306 }
307 if (temporder[j] == 1) {
308 /* The order needs to be recomputed each time */
309 xmlFree((void *)(comp->order));
310 comp->order = NULL;
311 }
312 if (resultsTab[j] != NULL) {
313 for (i = 0;i < len;i++)
314 xmlXPathFreeObject(resultsTab[j][i]);
315 xmlFree(resultsTab[j]);
316 }
317 }
318 }
319
320 }
321
322 #endif
323