Part 2 of removing PlatformString.h, remove PlatformString.h
[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 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 <libxslt/templates.h>
35 #include <libxslt/xsltutils.h>
36 #include <wtf/text/WTFString.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
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.
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