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