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
45SOFT_LINK_LIBRARY(libxslt)
46SOFT_LINK(libxslt, xsltComputeSortResult, xmlXPathObjectPtr*, (xsltTransformContextPtr ctxt, xmlNodePtr sort), (ctxt, sort))
47SOFT_LINK(libxslt, xsltEvalAttrValueTemplate, xmlChar*, (xsltTransformContextPtr ctxt, xmlNodePtr node, const xmlChar *name, const xmlChar *ns), (ctxt, node, name, ns))
48
49static void xsltTransformErrorTrampoline(xsltTransformContextPtr, xsltStylesheetPtr, xmlNodePtr, const char* message, ...) WTF_ATTRIBUTE_PRINTF(4, 5);
50
51void 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
70namespace WebCore {
71
72// Based on default implementation from libxslt 1.1.22 and xsltICUSort.c example.
73void 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