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 37 namespace WebCore { 38 39 inline 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. 46 void 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 WebCore 276
