Not reviewed, trivial leak fix.
[WebKit-https.git] / WebCore / xml / XSLTUnicodeSort.cpp
1 /*
2  * Copyright (C) 2007 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) && USE(ICU_UNICODE)
33
34 #include <libxslt/templates.h>
35 #include <libxslt/xsltutils.h>
36 #include <unicode/ucnv.h>
37 #include <unicode/ucol.h>
38 #include <unicode/ustring.h>
39
40 #if PLATFORM(MAC)
41 #include "SoftLinking.h"
42 #endif
43
44 #if PLATFORM(MAC)
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 init_xsltTransformError(xsltTransformContextPtr ctxt, xsltStylesheetPtr style, xmlNodePtr node, const char *, ...) WTF_ATTRIBUTE_PRINTF(4, 5);
50 static void (*softLink_xsltTransformError)(xsltTransformContextPtr ctxt, xsltStylesheetPtr style, xmlNodePtr node, const char *, ...) = init_xsltTransformError;
51
52 static void init_xsltTransformError(xsltTransformContextPtr ctxt, xsltStylesheetPtr style, xmlNodePtr node, const char* msg, ...)
53 {
54     softLink_xsltTransformError = (void (*) (xsltTransformContextPtr ctxt, xsltStylesheetPtr style, xmlNodePtr node, const char *, ...))dlsym(libxsltLibrary(), "xsltTransformError");
55     ASSERT(softLink_xsltTransformError);
56
57     va_list args;
58     va_start(args, msg);
59 #if PLATFORM(WIN_OS)
60     char str[1024];
61     vsnprintf(str, sizeof(str) - 1, msg, args);
62 #else
63     char* str;
64     vasprintf(&str, msg, args);
65 #endif
66     va_end(args);
67
68     softLink_xsltTransformError(ctxt, style, node, "%s", str);
69
70 #if !PLATFORM(WIN_OS)
71     free(str);
72 #endif
73 }
74
75 inline void xsltTransformError(xsltTransformContextPtr ctxt, xsltStylesheetPtr style, xmlNodePtr node, const char* msg, ...) WTF_ATTRIBUTE_PRINTF(4, 5);
76
77 inline void xsltTransformError(xsltTransformContextPtr ctxt, xsltStylesheetPtr style, xmlNodePtr node, const char* msg, ...)
78 {
79     va_list args;
80     va_start(args, msg);
81 #if PLATFORM(WIN_OS)
82     char str[1024];
83     vsnprintf(str, sizeof(str) - 1, msg, args);
84 #else
85     char* str;
86     vasprintf(&str, msg, args);
87 #endif
88     va_end(args);
89
90     softLink_xsltTransformError(ctxt, style, node, "%s", str);
91
92 #if !PLATFORM(WIN_OS)
93     free(str);
94 #endif
95 }
96
97 #endif
98
99 namespace WebCore {
100
101 // Based on default implementation from libxslt 1.1.22 and xsltICUSort.c example.
102 void xsltUnicodeSortFunction(xsltTransformContextPtr ctxt, xmlNodePtr *sorts, int nbsorts)
103 {
104 #ifdef XSLT_REFACTORED
105     xsltStyleItemSortPtr comp;
106 #else
107     xsltStylePreCompPtr comp;
108 #endif
109     xmlXPathObjectPtr *resultsTab[XSLT_MAX_SORT];
110     xmlXPathObjectPtr *results = NULL, *res;
111     xmlNodeSetPtr list = NULL;
112     int descending, number, desc, numb;
113     int len = 0;
114     int i, j, incr;
115     int tst;
116     int depth;
117     xmlNodePtr node;
118     xmlXPathObjectPtr tmp;    
119     int tempstype[XSLT_MAX_SORT], temporder[XSLT_MAX_SORT];
120
121     /* Start ICU change */
122     UCollator *coll = 0;
123     UConverter *conv;
124     UErrorCode status;
125     UChar *target,*target2;
126     int targetlen, target2len;
127     /* End ICU change */
128
129     if ((ctxt == NULL) || (sorts == NULL) || (nbsorts <= 0) ||
130         (nbsorts >= XSLT_MAX_SORT))
131         return;
132     if (sorts[0] == NULL)
133         return;
134     comp = static_cast<xsltStylePreComp*>(sorts[0]->psvi);
135     if (comp == NULL)
136         return;
137
138     list = ctxt->nodeList;
139     if ((list == NULL) || (list->nodeNr <= 1))
140         return; /* nothing to do */
141
142     for (j = 0; j < nbsorts; j++) {
143         comp = static_cast<xsltStylePreComp*>(sorts[j]->psvi);
144         tempstype[j] = 0;
145         if ((comp->stype == NULL) && (comp->has_stype != 0)) {
146             comp->stype =
147                 xsltEvalAttrValueTemplate(ctxt, sorts[j],
148                                           (const xmlChar *) "data-type",
149                                           XSLT_NAMESPACE);
150             if (comp->stype != NULL) {
151                 tempstype[j] = 1;
152                 if (xmlStrEqual(comp->stype, (const xmlChar *) "text"))
153                     comp->number = 0;
154                 else if (xmlStrEqual(comp->stype, (const xmlChar *) "number"))
155                     comp->number = 1;
156                 else {
157                     xsltTransformError(ctxt, NULL, sorts[j],
158                           "xsltDoSortFunction: no support for data-type = %s\n",
159                                      comp->stype);
160                     comp->number = 0; /* use default */
161                 }
162             }
163         }
164         temporder[j] = 0;
165         if ((comp->order == NULL) && (comp->has_order != 0)) {
166             comp->order = xsltEvalAttrValueTemplate(ctxt, sorts[j],
167                                                     (const xmlChar *) "order",
168                                                     XSLT_NAMESPACE);
169             if (comp->order != NULL) {
170                 temporder[j] = 1;
171                 if (xmlStrEqual(comp->order, (const xmlChar *) "ascending"))
172                     comp->descending = 0;
173                 else if (xmlStrEqual(comp->order,
174                                      (const xmlChar *) "descending"))
175                     comp->descending = 1;
176                 else {
177                     xsltTransformError(ctxt, NULL, sorts[j],
178                              "xsltDoSortFunction: invalid value %s for order\n",
179                                      comp->order);
180                     comp->descending = 0; /* use default */
181                 }
182             }
183         }
184     }
185
186     len = list->nodeNr;
187
188     resultsTab[0] = xsltComputeSortResult(ctxt, sorts[0]);
189     for (i = 1;i < XSLT_MAX_SORT;i++)
190         resultsTab[i] = NULL;
191
192     results = resultsTab[0];
193
194     comp = static_cast<xsltStylePreComp*>(sorts[0]->psvi);
195     descending = comp->descending;
196     number = comp->number;
197     if (results == NULL)
198         return;
199
200     /* Start ICU change */
201     status = U_ZERO_ERROR;
202     conv = ucnv_open("UTF8", &status);
203     if (U_FAILURE(status))
204         xsltTransformError(ctxt, NULL, NULL, "xsltICUSortFunction: Error opening converter\n");
205
206     if (comp->has_lang) 
207         coll = ucol_open((const char*)comp->lang, &status);
208     if (U_FAILURE(status) || !comp->has_lang) {
209         status = U_ZERO_ERROR;
210         coll = ucol_open("en", &status);
211     }
212     if (U_FAILURE(status))
213         xsltTransformError(ctxt, NULL, NULL, "xsltICUSortFunction: Error opening collator\n");
214
215     if (comp->lower_first) 
216         ucol_setAttribute(coll,UCOL_CASE_FIRST,UCOL_LOWER_FIRST,&status);
217     else 
218         ucol_setAttribute(coll,UCOL_CASE_FIRST,UCOL_UPPER_FIRST,&status);
219     if (U_FAILURE(status))
220         xsltTransformError(ctxt, NULL, NULL, "xsltICUSortFunction: Error setting collator attribute\n");
221     /* End ICU change */
222
223     /* Shell's sort of node-set */
224     for (incr = len / 2; incr > 0; incr /= 2) {
225         for (i = incr; i < len; i++) {
226             j = i - incr;
227             if (results[i] == NULL)
228                 continue;
229             
230             while (j >= 0) {
231                 if (results[j] == NULL)
232                     tst = 1;
233                 else {
234                     if (number) {
235                         /* We make NaN smaller than number in accordance
236                            with XSLT spec */
237                         if (xmlXPathIsNaN(results[j]->floatval)) {
238                             if (xmlXPathIsNaN(results[j + incr]->floatval))
239                                 tst = 0;
240                             else
241                                 tst = -1;
242                         } else if (xmlXPathIsNaN(results[j + incr]->floatval))
243                             tst = 1;
244                         else if (results[j]->floatval ==
245                                 results[j + incr]->floatval)
246                             tst = 0;
247                         else if (results[j]->floatval > 
248                                 results[j + incr]->floatval)
249                             tst = 1;
250                         else tst = -1;
251                     } else {
252                         /* Start ICU change */
253                         targetlen = xmlStrlen(results[j]->stringval) * 2;
254                         target2len = xmlStrlen(results[j + incr]->stringval) * 2;
255                         target = (UChar*)xmlMalloc(targetlen * sizeof(UChar));
256                         target2 = (UChar*)xmlMalloc(target2len * sizeof(UChar));
257                         targetlen = ucnv_toUChars(conv, target, targetlen, (const char*)results[j]->stringval, -1, &status);
258                         target2len = ucnv_toUChars(conv, target2, target2len, (const char*)results[j+incr]->stringval, -1, &status);
259                         tst = ucol_strcoll(coll, target, u_strlen(target), target2, u_strlen(target2));
260                         xmlFree(target);
261                         xmlFree(target2);
262                         /* End ICU change */
263                     }
264                     if (descending)
265                         tst = -tst;
266                 }
267                 if (tst == 0) {
268                     /*
269                      * Okay we need to use multi level sorts
270                      */
271                     depth = 1;
272                     while (depth < nbsorts) {
273                         if (sorts[depth] == NULL)
274                             break;
275                         comp = static_cast<xsltStylePreComp*>(sorts[depth]->psvi);
276                         if (comp == NULL)
277                             break;
278                         desc = comp->descending;
279                         numb = comp->number;
280
281                         /*
282                          * Compute the result of the next level for the
283                          * full set, this might be optimized ... or not
284                          */
285                         if (resultsTab[depth] == NULL) 
286                             resultsTab[depth] = xsltComputeSortResult(ctxt,
287                                                         sorts[depth]);
288                         res = resultsTab[depth];
289                         if (res == NULL) 
290                             break;
291                         if (res[j] == NULL) {
292                             if (res[j+incr] != NULL)
293                                 tst = 1;
294                         } else {
295                             if (numb) {
296                                 /* We make NaN smaller than number in
297                                    accordance with XSLT spec */
298                                 if (xmlXPathIsNaN(res[j]->floatval)) {
299                                     if (xmlXPathIsNaN(res[j +
300                                                     incr]->floatval))
301                                         tst = 0;
302                                     else
303                                         tst = -1;
304                                 } else if (xmlXPathIsNaN(res[j + incr]->
305                                                 floatval))
306                                     tst = 1;
307                                 else if (res[j]->floatval == res[j + incr]->
308                                                 floatval)
309                                     tst = 0;
310                                 else if (res[j]->floatval > 
311                                         res[j + incr]->floatval)
312                                     tst = 1;
313                                 else tst = -1;
314                             } else {
315                                 /* Start ICU change */
316                                 targetlen = xmlStrlen(res[j]->stringval) * 2;
317                                 target2len = xmlStrlen(res[j + incr]->stringval) * 2;
318                                 target = (UChar*)xmlMalloc(targetlen * sizeof(UChar));
319                                 target2 = (UChar*)xmlMalloc(target2len * sizeof(UChar));
320                                 targetlen = ucnv_toUChars(conv, target, targetlen, (const char*)res[j]->stringval, -1, &status);
321                                 target2len = ucnv_toUChars(conv, target2, target2len, (const char*)res[j+incr]->stringval, -1, &status);
322                                 tst = ucol_strcoll(coll, target, u_strlen(target), target2, u_strlen(target2));
323                                 xmlFree(target);
324                                 xmlFree(target2);
325                                 /* End ICU change */
326                             }
327                             if (desc)
328                                 tst = -tst;
329                         }
330
331                         /*
332                          * if we still can't differenciate at this level
333                          * try one level deeper.
334                          */
335                         if (tst != 0)
336                             break;
337                         depth++;
338                     }
339                 }
340                 if (tst == 0) {
341                     tst = results[j]->index > results[j + incr]->index;
342                 }
343                 if (tst > 0) {
344                     tmp = results[j];
345                     results[j] = results[j + incr];
346                     results[j + incr] = tmp;
347                     node = list->nodeTab[j];
348                     list->nodeTab[j] = list->nodeTab[j + incr];
349                     list->nodeTab[j + incr] = node;
350                     depth = 1;
351                     while (depth < nbsorts) {
352                         if (sorts[depth] == NULL)
353                             break;
354                         if (resultsTab[depth] == NULL)
355                             break;
356                         res = resultsTab[depth];
357                         tmp = res[j];
358                         res[j] = res[j + incr];
359                         res[j + incr] = tmp;
360                         depth++;
361                     }
362                     j -= incr;
363                 } else
364                     break;
365             }
366         }
367     }
368
369     /* Start ICU change */
370     ucol_close(coll);
371     ucnv_close(conv);
372     /* End ICU change */
373
374     for (j = 0; j < nbsorts; j++) {
375         comp = static_cast<xsltStylePreComp*>(sorts[j]->psvi);
376         if (tempstype[j] == 1) {
377             /* The data-type needs to be recomputed each time */
378             xmlFree((void *)(comp->stype));
379             comp->stype = NULL;
380         }
381         if (temporder[j] == 1) {
382             /* The order needs to be recomputed each time */
383             xmlFree((void *)(comp->order));
384             comp->order = NULL;
385         }
386         if (resultsTab[j] != NULL) {
387             for (i = 0;i < len;i++)
388                 xmlXPathFreeObject(resultsTab[j][i]);
389             xmlFree(resultsTab[j]);
390         }
391     }
392 }
393
394 }
395
396 #endif