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 "PlatformString.h" 35 #include <libxslt/templates.h> 36 #include <libxslt/xsltutils.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 323
