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