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