1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/xul/templates/src/nsXULSortService.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,514 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/.
1.8 + *
1.9 + * This Original Code has been modified by IBM Corporation.
1.10 + * Modifications made by IBM described herein are
1.11 + * Copyright (c) International Business Machines
1.12 + * Corporation, 2000
1.13 + *
1.14 + * Modifications to Mozilla code or documentation
1.15 + * identified per MPL Section 3.3
1.16 + *
1.17 + * Date Modified by Description of modification
1.18 + * 03/27/2000 IBM Corp. Added PR_CALLBACK for Optlink
1.19 + * use in OS2
1.20 + */
1.21 +
1.22 +/*
1.23 + This file provides the implementation for the sort service manager.
1.24 + */
1.25 +
1.26 +#include "nsCOMPtr.h"
1.27 +#include "nsIContent.h"
1.28 +#include "nsIDOMElement.h"
1.29 +#include "nsIDOMNode.h"
1.30 +#include "nsIServiceManager.h"
1.31 +#include "nsGkAtoms.h"
1.32 +#include "nsNameSpaceManager.h"
1.33 +#include "nsXULContentUtils.h"
1.34 +#include "nsString.h"
1.35 +#include "nsQuickSort.h"
1.36 +#include "nsWhitespaceTokenizer.h"
1.37 +#include "nsXULSortService.h"
1.38 +#include "nsIDOMXULElement.h"
1.39 +#include "nsIXULTemplateBuilder.h"
1.40 +#include "nsTemplateMatch.h"
1.41 +#include "nsICollation.h"
1.42 +#include "nsUnicharUtils.h"
1.43 +
1.44 +NS_IMPL_ISUPPORTS(XULSortServiceImpl, nsIXULSortService)
1.45 +
1.46 +void
1.47 +XULSortServiceImpl::SetSortHints(nsIContent *aNode, nsSortState* aSortState)
1.48 +{
1.49 + // set sort and sortDirection attributes when is sort is done
1.50 + aNode->SetAttr(kNameSpaceID_None, nsGkAtoms::sort,
1.51 + aSortState->sort, true);
1.52 +
1.53 + nsAutoString direction;
1.54 + if (aSortState->direction == nsSortState_descending)
1.55 + direction.AssignLiteral("descending");
1.56 + else if (aSortState->direction == nsSortState_ascending)
1.57 + direction.AssignLiteral("ascending");
1.58 + aNode->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
1.59 + direction, true);
1.60 +
1.61 + // for trees, also set the sort info on the currently sorted column
1.62 + if (aNode->NodeInfo()->Equals(nsGkAtoms::tree, kNameSpaceID_XUL)) {
1.63 + if (aSortState->sortKeys.Count() >= 1) {
1.64 + nsAutoString sortkey;
1.65 + aSortState->sortKeys[0]->ToString(sortkey);
1.66 + SetSortColumnHints(aNode, sortkey, direction);
1.67 + }
1.68 + }
1.69 +}
1.70 +
1.71 +void
1.72 +XULSortServiceImpl::SetSortColumnHints(nsIContent *content,
1.73 + const nsAString &sortResource,
1.74 + const nsAString &sortDirection)
1.75 +{
1.76 + // set sort info on current column. This ensures that the
1.77 + // column header sort indicator is updated properly.
1.78 + for (nsIContent* child = content->GetFirstChild();
1.79 + child;
1.80 + child = child->GetNextSibling()) {
1.81 + if (child->IsXUL()) {
1.82 + nsIAtom *tag = child->Tag();
1.83 +
1.84 + if (tag == nsGkAtoms::treecols) {
1.85 + SetSortColumnHints(child, sortResource, sortDirection);
1.86 + } else if (tag == nsGkAtoms::treecol) {
1.87 + nsAutoString value;
1.88 + child->GetAttr(kNameSpaceID_None, nsGkAtoms::sort, value);
1.89 + // also check the resource attribute for older code
1.90 + if (value.IsEmpty())
1.91 + child->GetAttr(kNameSpaceID_None, nsGkAtoms::resource, value);
1.92 + if (value == sortResource) {
1.93 + child->SetAttr(kNameSpaceID_None, nsGkAtoms::sortActive,
1.94 + NS_LITERAL_STRING("true"), true);
1.95 + child->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
1.96 + sortDirection, true);
1.97 + // Note: don't break out of loop; want to set/unset
1.98 + // attribs on ALL sort columns
1.99 + } else if (!value.IsEmpty()) {
1.100 + child->UnsetAttr(kNameSpaceID_None, nsGkAtoms::sortActive,
1.101 + true);
1.102 + child->UnsetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
1.103 + true);
1.104 + }
1.105 + }
1.106 + }
1.107 + }
1.108 +}
1.109 +
1.110 +nsresult
1.111 +XULSortServiceImpl::GetItemsToSort(nsIContent *aContainer,
1.112 + nsSortState* aSortState,
1.113 + nsTArray<contentSortInfo>& aSortItems)
1.114 +{
1.115 + // if there is a template attached to the sort node, use the builder to get
1.116 + // the items to be sorted
1.117 + nsCOMPtr<nsIDOMXULElement> element = do_QueryInterface(aContainer);
1.118 + if (element) {
1.119 + nsCOMPtr<nsIXULTemplateBuilder> builder;
1.120 + element->GetBuilder(getter_AddRefs(builder));
1.121 +
1.122 + if (builder) {
1.123 + nsresult rv = builder->GetQueryProcessor(getter_AddRefs(aSortState->processor));
1.124 + if (NS_FAILED(rv) || !aSortState->processor)
1.125 + return rv;
1.126 +
1.127 + return GetTemplateItemsToSort(aContainer, builder, aSortState, aSortItems);
1.128 + }
1.129 + }
1.130 +
1.131 + // if there is no template builder, just get the children. For trees,
1.132 + // get the treechildren element as use that as the parent
1.133 + nsCOMPtr<nsIContent> treechildren;
1.134 + if (aContainer->NodeInfo()->Equals(nsGkAtoms::tree, kNameSpaceID_XUL)) {
1.135 + nsXULContentUtils::FindChildByTag(aContainer,
1.136 + kNameSpaceID_XUL,
1.137 + nsGkAtoms::treechildren,
1.138 + getter_AddRefs(treechildren));
1.139 + if (!treechildren)
1.140 + return NS_OK;
1.141 +
1.142 + aContainer = treechildren;
1.143 + }
1.144 +
1.145 + for (nsIContent* child = aContainer->GetFirstChild();
1.146 + child;
1.147 + child = child->GetNextSibling()) {
1.148 + contentSortInfo* cinfo = aSortItems.AppendElement();
1.149 + if (!cinfo)
1.150 + return NS_ERROR_OUT_OF_MEMORY;
1.151 +
1.152 + cinfo->content = child;
1.153 + }
1.154 +
1.155 + return NS_OK;
1.156 +}
1.157 +
1.158 +
1.159 +nsresult
1.160 +XULSortServiceImpl::GetTemplateItemsToSort(nsIContent* aContainer,
1.161 + nsIXULTemplateBuilder* aBuilder,
1.162 + nsSortState* aSortState,
1.163 + nsTArray<contentSortInfo>& aSortItems)
1.164 +{
1.165 + for (nsIContent* child = aContainer->GetFirstChild();
1.166 + child;
1.167 + child = child->GetNextSibling()) {
1.168 +
1.169 + nsCOMPtr<nsIDOMElement> childnode = do_QueryInterface(child);
1.170 +
1.171 + nsCOMPtr<nsIXULTemplateResult> result;
1.172 + nsresult rv = aBuilder->GetResultForContent(childnode, getter_AddRefs(result));
1.173 + NS_ENSURE_SUCCESS(rv, rv);
1.174 +
1.175 + if (result) {
1.176 + contentSortInfo* cinfo = aSortItems.AppendElement();
1.177 + if (!cinfo)
1.178 + return NS_ERROR_OUT_OF_MEMORY;
1.179 +
1.180 + cinfo->content = child;
1.181 + cinfo->result = result;
1.182 + }
1.183 + else if (aContainer->Tag() != nsGkAtoms::_template) {
1.184 + rv = GetTemplateItemsToSort(child, aBuilder, aSortState, aSortItems);
1.185 + NS_ENSURE_SUCCESS(rv, rv);
1.186 + }
1.187 + }
1.188 +
1.189 + return NS_OK;
1.190 +}
1.191 +
1.192 +int
1.193 +testSortCallback(const void *data1, const void *data2, void *privateData)
1.194 +{
1.195 + /// Note: testSortCallback is a small C callback stub for NS_QuickSort
1.196 + contentSortInfo *left = (contentSortInfo *)data1;
1.197 + contentSortInfo *right = (contentSortInfo *)data2;
1.198 + nsSortState* sortState = (nsSortState *)privateData;
1.199 +
1.200 + int32_t sortOrder = 0;
1.201 +
1.202 + if (sortState->direction == nsSortState_natural && sortState->processor) {
1.203 + // sort in natural order
1.204 + sortState->processor->CompareResults(left->result, right->result,
1.205 + nullptr, sortState->sortHints, &sortOrder);
1.206 + }
1.207 + else {
1.208 + int32_t length = sortState->sortKeys.Count();
1.209 + for (int32_t t = 0; t < length; t++) {
1.210 + // for templates, use the query processor to do sorting
1.211 + if (sortState->processor) {
1.212 + sortState->processor->CompareResults(left->result, right->result,
1.213 + sortState->sortKeys[t],
1.214 + sortState->sortHints, &sortOrder);
1.215 + if (sortOrder)
1.216 + break;
1.217 + }
1.218 + else {
1.219 + // no template, so just compare attributes. Ignore namespaces for now.
1.220 + nsAutoString leftstr, rightstr;
1.221 + left->content->GetAttr(kNameSpaceID_None, sortState->sortKeys[t], leftstr);
1.222 + right->content->GetAttr(kNameSpaceID_None, sortState->sortKeys[t], rightstr);
1.223 +
1.224 + sortOrder = XULSortServiceImpl::CompareValues(leftstr, rightstr, sortState->sortHints);
1.225 + }
1.226 + }
1.227 + }
1.228 +
1.229 + if (sortState->direction == nsSortState_descending)
1.230 + sortOrder = -sortOrder;
1.231 +
1.232 + return sortOrder;
1.233 +}
1.234 +
1.235 +nsresult
1.236 +XULSortServiceImpl::SortContainer(nsIContent *aContainer, nsSortState* aSortState)
1.237 +{
1.238 + nsTArray<contentSortInfo> items;
1.239 + nsresult rv = GetItemsToSort(aContainer, aSortState, items);
1.240 + NS_ENSURE_SUCCESS(rv, rv);
1.241 +
1.242 + uint32_t numResults = items.Length();
1.243 + if (!numResults)
1.244 + return NS_OK;
1.245 +
1.246 + uint32_t i;
1.247 +
1.248 + // inbetweenSeparatorSort sorts the items between separators independently
1.249 + if (aSortState->inbetweenSeparatorSort) {
1.250 + uint32_t startIndex = 0;
1.251 + for (i = 0; i < numResults; i++) {
1.252 + if (i > startIndex + 1) {
1.253 + nsAutoString type;
1.254 + items[i].result->GetType(type);
1.255 + if (type.EqualsLiteral("separator")) {
1.256 + if (aSortState->invertSort)
1.257 + InvertSortInfo(items, startIndex, i - startIndex);
1.258 + else
1.259 + NS_QuickSort((void *)(items.Elements() + startIndex), i - startIndex,
1.260 + sizeof(contentSortInfo), testSortCallback, (void*)aSortState);
1.261 +
1.262 + startIndex = i + 1;
1.263 + }
1.264 + }
1.265 + }
1.266 +
1.267 + if (i > startIndex + 1) {
1.268 + if (aSortState->invertSort)
1.269 + InvertSortInfo(items, startIndex, i - startIndex);
1.270 + else
1.271 + NS_QuickSort((void *)(items.Elements() + startIndex), i - startIndex,
1.272 + sizeof(contentSortInfo), testSortCallback, (void*)aSortState);
1.273 + }
1.274 + } else {
1.275 + // if the items are just being inverted, that is, just switching between
1.276 + // ascending and descending, just reverse the list.
1.277 + if (aSortState->invertSort)
1.278 + InvertSortInfo(items, 0, numResults);
1.279 + else
1.280 + NS_QuickSort((void *)items.Elements(), numResults,
1.281 + sizeof(contentSortInfo), testSortCallback, (void*)aSortState);
1.282 + }
1.283 +
1.284 + // first remove the items from the old positions
1.285 + for (i = 0; i < numResults; i++) {
1.286 + nsIContent* child = items[i].content;
1.287 + nsIContent* parent = child->GetParent();
1.288 +
1.289 + if (parent) {
1.290 + // remember the parent so that it can be reinserted back
1.291 + // into the same parent. This is necessary as multiple rules
1.292 + // may generate results which get placed in different locations.
1.293 + items[i].parent = parent;
1.294 + int32_t index = parent->IndexOf(child);
1.295 + parent->RemoveChildAt(index, true);
1.296 + }
1.297 + }
1.298 +
1.299 + // now add the items back in sorted order
1.300 + for (i = 0; i < numResults; i++)
1.301 + {
1.302 + nsIContent* child = items[i].content;
1.303 + nsIContent* parent = items[i].parent;
1.304 + if (parent) {
1.305 + parent->AppendChildTo(child, true);
1.306 +
1.307 + // if it's a container in a tree or menu, find its children,
1.308 + // and sort those also
1.309 + if (!child->AttrValueIs(kNameSpaceID_None, nsGkAtoms::container,
1.310 + nsGkAtoms::_true, eCaseMatters))
1.311 + continue;
1.312 +
1.313 + for (nsIContent* grandchild = child->GetFirstChild();
1.314 + grandchild;
1.315 + grandchild = grandchild->GetNextSibling()) {
1.316 + nsINodeInfo *ni = grandchild->NodeInfo();
1.317 + nsIAtom *localName = ni->NameAtom();
1.318 + if (ni->NamespaceID() == kNameSpaceID_XUL &&
1.319 + (localName == nsGkAtoms::treechildren ||
1.320 + localName == nsGkAtoms::menupopup)) {
1.321 + SortContainer(grandchild, aSortState);
1.322 + }
1.323 + }
1.324 + }
1.325 + }
1.326 +
1.327 + return NS_OK;
1.328 +}
1.329 +
1.330 +nsresult
1.331 +XULSortServiceImpl::InvertSortInfo(nsTArray<contentSortInfo>& aData,
1.332 + int32_t aStart, int32_t aNumItems)
1.333 +{
1.334 + if (aNumItems > 1) {
1.335 + // reverse the items in the array starting from aStart
1.336 + int32_t upPoint = (aNumItems + 1) / 2 + aStart;
1.337 + int32_t downPoint = (aNumItems - 2) / 2 + aStart;
1.338 + int32_t half = aNumItems / 2;
1.339 + while (half-- > 0) {
1.340 + aData[downPoint--].swap(aData[upPoint++]);
1.341 + }
1.342 + }
1.343 + return NS_OK;
1.344 +}
1.345 +
1.346 +nsresult
1.347 +XULSortServiceImpl::InitializeSortState(nsIContent* aRootElement,
1.348 + nsIContent* aContainer,
1.349 + const nsAString& aSortKey,
1.350 + const nsAString& aSortHints,
1.351 + nsSortState* aSortState)
1.352 +{
1.353 + // used as an optimization for the content builder
1.354 + if (aContainer != aSortState->lastContainer.get()) {
1.355 + aSortState->lastContainer = aContainer;
1.356 + aSortState->lastWasFirst = false;
1.357 + aSortState->lastWasLast = false;
1.358 + }
1.359 +
1.360 + // The attributes allowed are either:
1.361 + // sort="key1 key2 ..."
1.362 + // or sortResource="key1" sortResource2="key2"
1.363 + // The latter is for backwards compatibility, and is equivalent to concatenating
1.364 + // both values in the sort attribute
1.365 + nsAutoString sort(aSortKey);
1.366 + aSortState->sortKeys.Clear();
1.367 + if (sort.IsEmpty()) {
1.368 + nsAutoString sortResource, sortResource2;
1.369 + aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sortResource, sortResource);
1.370 + if (!sortResource.IsEmpty()) {
1.371 + nsCOMPtr<nsIAtom> sortkeyatom = do_GetAtom(sortResource);
1.372 + aSortState->sortKeys.AppendObject(sortkeyatom);
1.373 + sort.Append(sortResource);
1.374 +
1.375 + aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sortResource2, sortResource2);
1.376 + if (!sortResource2.IsEmpty()) {
1.377 + nsCOMPtr<nsIAtom> sortkeyatom2 = do_GetAtom(sortResource2);
1.378 + aSortState->sortKeys.AppendObject(sortkeyatom2);
1.379 + sort.AppendLiteral(" ");
1.380 + sort.Append(sortResource2);
1.381 + }
1.382 + }
1.383 + }
1.384 + else {
1.385 + nsWhitespaceTokenizer tokenizer(sort);
1.386 + while (tokenizer.hasMoreTokens()) {
1.387 + nsCOMPtr<nsIAtom> keyatom = do_GetAtom(tokenizer.nextToken());
1.388 + NS_ENSURE_TRUE(keyatom, NS_ERROR_OUT_OF_MEMORY);
1.389 + aSortState->sortKeys.AppendObject(keyatom);
1.390 + }
1.391 + }
1.392 +
1.393 + aSortState->sort.Assign(sort);
1.394 + aSortState->direction = nsSortState_natural;
1.395 +
1.396 + bool noNaturalState = false;
1.397 + nsWhitespaceTokenizer tokenizer(aSortHints);
1.398 + while (tokenizer.hasMoreTokens()) {
1.399 + const nsDependentSubstring& token(tokenizer.nextToken());
1.400 + if (token.EqualsLiteral("comparecase"))
1.401 + aSortState->sortHints |= nsIXULSortService::SORT_COMPARECASE;
1.402 + else if (token.EqualsLiteral("integer"))
1.403 + aSortState->sortHints |= nsIXULSortService::SORT_INTEGER;
1.404 + else if (token.EqualsLiteral("descending"))
1.405 + aSortState->direction = nsSortState_descending;
1.406 + else if (token.EqualsLiteral("ascending"))
1.407 + aSortState->direction = nsSortState_ascending;
1.408 + else if (token.EqualsLiteral("twostate"))
1.409 + noNaturalState = true;
1.410 + }
1.411 +
1.412 + // if the twostate flag was set, the natural order is skipped and only
1.413 + // ascending and descending are allowed
1.414 + if (aSortState->direction == nsSortState_natural && noNaturalState) {
1.415 + aSortState->direction = nsSortState_ascending;
1.416 + }
1.417 +
1.418 + // set up sort order info
1.419 + aSortState->invertSort = false;
1.420 +
1.421 + nsAutoString existingsort;
1.422 + aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sort, existingsort);
1.423 + nsAutoString existingsortDirection;
1.424 + aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection, existingsortDirection);
1.425 +
1.426 + // if just switching direction, set the invertSort flag
1.427 + if (sort.Equals(existingsort)) {
1.428 + if (aSortState->direction == nsSortState_descending) {
1.429 + if (existingsortDirection.EqualsLiteral("ascending"))
1.430 + aSortState->invertSort = true;
1.431 + }
1.432 + else if (aSortState->direction == nsSortState_ascending &&
1.433 + existingsortDirection.EqualsLiteral("descending")) {
1.434 + aSortState->invertSort = true;
1.435 + }
1.436 + }
1.437 +
1.438 + // sort items between separators independently
1.439 + aSortState->inbetweenSeparatorSort =
1.440 + aRootElement->AttrValueIs(kNameSpaceID_None, nsGkAtoms::sortSeparators,
1.441 + nsGkAtoms::_true, eCaseMatters);
1.442 +
1.443 + // sort static content (non template generated nodes) after generated content
1.444 + aSortState->sortStaticsLast = aRootElement->AttrValueIs(kNameSpaceID_None,
1.445 + nsGkAtoms::sortStaticsLast,
1.446 + nsGkAtoms::_true, eCaseMatters);
1.447 +
1.448 + aSortState->initialized = true;
1.449 +
1.450 + return NS_OK;
1.451 +}
1.452 +
1.453 +int32_t
1.454 +XULSortServiceImpl::CompareValues(const nsAString& aLeft,
1.455 + const nsAString& aRight,
1.456 + uint32_t aSortHints)
1.457 +{
1.458 + if (aSortHints & SORT_INTEGER) {
1.459 + nsresult err;
1.460 + int32_t leftint = PromiseFlatString(aLeft).ToInteger(&err);
1.461 + if (NS_SUCCEEDED(err)) {
1.462 + int32_t rightint = PromiseFlatString(aRight).ToInteger(&err);
1.463 + if (NS_SUCCEEDED(err)) {
1.464 + return leftint - rightint;
1.465 + }
1.466 + }
1.467 + // if they aren't integers, just fall through and compare strings
1.468 + }
1.469 +
1.470 + if (aSortHints & SORT_COMPARECASE) {
1.471 + return ::Compare(aLeft, aRight);
1.472 + }
1.473 +
1.474 + nsICollation* collation = nsXULContentUtils::GetCollation();
1.475 + if (collation) {
1.476 + int32_t result;
1.477 + collation->CompareString(nsICollation::kCollationCaseInSensitive,
1.478 + aLeft, aRight, &result);
1.479 + return result;
1.480 + }
1.481 +
1.482 + return ::Compare(aLeft, aRight, nsCaseInsensitiveStringComparator());
1.483 +}
1.484 +
1.485 +NS_IMETHODIMP
1.486 +XULSortServiceImpl::Sort(nsIDOMNode* aNode,
1.487 + const nsAString& aSortKey,
1.488 + const nsAString& aSortHints)
1.489 +{
1.490 + // get root content node
1.491 + nsCOMPtr<nsIContent> sortNode = do_QueryInterface(aNode);
1.492 + if (!sortNode)
1.493 + return NS_ERROR_FAILURE;
1.494 +
1.495 + nsSortState sortState;
1.496 + nsresult rv = InitializeSortState(sortNode, sortNode,
1.497 + aSortKey, aSortHints, &sortState);
1.498 + NS_ENSURE_SUCCESS(rv, rv);
1.499 +
1.500 + // store sort info in attributes on content
1.501 + SetSortHints(sortNode, &sortState);
1.502 + rv = SortContainer(sortNode, &sortState);
1.503 +
1.504 + sortState.processor = nullptr; // don't hang on to this reference
1.505 + return rv;
1.506 +}
1.507 +
1.508 +nsresult
1.509 +NS_NewXULSortService(nsIXULSortService** sortService)
1.510 +{
1.511 + *sortService = new XULSortServiceImpl();
1.512 + if (!*sortService)
1.513 + return NS_ERROR_OUT_OF_MEMORY;
1.514 +
1.515 + NS_ADDREF(*sortService);
1.516 + return NS_OK;
1.517 +}
