From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- dom/xul/nsXULSortService.cpp | 395 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 395 insertions(+) create mode 100644 dom/xul/nsXULSortService.cpp (limited to 'dom/xul/nsXULSortService.cpp') diff --git a/dom/xul/nsXULSortService.cpp b/dom/xul/nsXULSortService.cpp new file mode 100644 index 0000000000..e73a6c2a1c --- /dev/null +++ b/dom/xul/nsXULSortService.cpp @@ -0,0 +1,395 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* + This file provides the implementation for the sort service manager. + */ + +#include "nsCOMArray.h" +#include "nsCOMPtr.h" +#include "nsIContent.h" +#include "nsGkAtoms.h" +#include "nsNameSpaceManager.h" +#include "nsXULContentUtils.h" +#include "nsString.h" +#include "nsQuickSort.h" +#include "nsWhitespaceTokenizer.h" +#include "nsXULSortService.h" +#include "nsXULElement.h" +#include "nsTArray.h" +#include "nsUnicharUtils.h" + +#include "mozilla/dom/Element.h" +#include "mozilla/intl/Collator.h" + +using mozilla::dom::Element; +const unsigned long SORT_COMPARECASE = 0x0001; +const unsigned long SORT_INTEGER = 0x0100; + +enum nsSortState_direction { + nsSortState_descending, + nsSortState_ascending, + nsSortState_natural +}; + +// the sort state holds info about the current sort +struct MOZ_STACK_CLASS nsSortState final { + bool initialized; + MOZ_INIT_OUTSIDE_CTOR bool invertSort; + + uint32_t sortHints; + + MOZ_INIT_OUTSIDE_CTOR nsSortState_direction direction; + nsAutoString sort; + nsTArray> sortKeys; + + nsCOMPtr lastContainer; + MOZ_INIT_OUTSIDE_CTOR bool lastWasFirst, lastWasLast; + + nsSortState() : initialized(false), sortHints(0) {} +}; + +// information about a particular item to be sorted +struct contentSortInfo { + nsCOMPtr content; + nsCOMPtr parent; + void swap(contentSortInfo& other) { + content.swap(other.content); + parent.swap(other.parent); + } +}; + +/** + * Set sortActive and sortDirection attributes on a tree column when a sort + * is done. The column to change is the one with a sort attribute that + * matches the sort key. The sort attributes are removed from the other + * columns. + */ +static void SetSortColumnHints(nsIContent* content, + const nsAString& sortResource, + const nsAString& sortDirection) { + // set sort info on current column. This ensures that the + // column header sort indicator is updated properly. + for (nsIContent* child = content->GetFirstChild(); child; + child = child->GetNextSibling()) { + if (child->IsXULElement(nsGkAtoms::treecols)) { + SetSortColumnHints(child, sortResource, sortDirection); + } else if (child->IsXULElement(nsGkAtoms::treecol)) { + nsAutoString value; + child->AsElement()->GetAttr(kNameSpaceID_None, nsGkAtoms::sort, value); + if (value == sortResource) { + child->AsElement()->SetAttr(kNameSpaceID_None, nsGkAtoms::sortActive, + u"true"_ns, true); + + child->AsElement()->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection, + sortDirection, true); + // Note: don't break out of loop; want to set/unset + // attribs on ALL sort columns + } else if (!value.IsEmpty()) { + child->AsElement()->UnsetAttr(kNameSpaceID_None, nsGkAtoms::sortActive, + true); + child->AsElement()->UnsetAttr(kNameSpaceID_None, + nsGkAtoms::sortDirection, true); + } + } + } +} + +/** + * Set sort and sortDirection attributes when a sort is done. + */ +static void SetSortHints(Element* aElement, nsSortState* aSortState) { + // set sort and sortDirection attributes when is sort is done + aElement->SetAttr(kNameSpaceID_None, nsGkAtoms::sort, aSortState->sort, true); + + nsAutoString direction; + if (aSortState->direction == nsSortState_descending) + direction.AssignLiteral("descending"); + else if (aSortState->direction == nsSortState_ascending) + direction.AssignLiteral("ascending"); + aElement->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection, direction, + true); + + // for trees, also set the sort info on the currently sorted column + if (aElement->IsXULElement(nsGkAtoms::tree)) { + if (aSortState->sortKeys.Length() >= 1) { + nsAutoString sortkey; + aSortState->sortKeys[0]->ToString(sortkey); + SetSortColumnHints(aElement, sortkey, direction); + } + } +} + +/** + * Determine the list of items which need to be sorted. This is determined + * in the following way: + * - for elements that have a content builder, get its list of generated + * results + * - otherwise, for trees, get the child treeitems + * - otherwise, get the direct children + */ +static nsresult GetItemsToSort(nsIContent* aContainer, nsSortState* aSortState, + nsTArray& aSortItems) { + // Get the children. For trees, get the treechildren element and + // use that as the parent + RefPtr treechildren; + if (aContainer->IsXULElement(nsGkAtoms::tree)) { + nsXULContentUtils::FindChildByTag(aContainer, kNameSpaceID_XUL, + nsGkAtoms::treechildren, + getter_AddRefs(treechildren)); + if (!treechildren) return NS_OK; + + aContainer = treechildren; + } + + for (nsIContent* child = aContainer->GetFirstChild(); child; + child = child->GetNextSibling()) { + contentSortInfo* cinfo = aSortItems.AppendElement(); + if (!cinfo) return NS_ERROR_OUT_OF_MEMORY; + + cinfo->content = child; + } + + return NS_OK; +} + +/** + * Compares aLeft and aRight and returns < 0, 0, or > 0. The sort + * hints are checked for case matching and integer sorting. + */ +static int32_t CompareValues(const nsAString& aLeft, const nsAString& aRight, + uint32_t aSortHints) { + if (aSortHints & SORT_INTEGER) { + nsresult err; + int32_t leftint = PromiseFlatString(aLeft).ToInteger(&err); + if (NS_SUCCEEDED(err)) { + int32_t rightint = PromiseFlatString(aRight).ToInteger(&err); + if (NS_SUCCEEDED(err)) { + return leftint - rightint; + } + } + // if they aren't integers, just fall through and compare strings + } + + if (aSortHints & SORT_COMPARECASE) { + return ::Compare(aLeft, aRight); + } + + using mozilla::intl::Collator; + const Collator* collator = nsXULContentUtils::GetCollator(); + if (collator) { + return collator->CompareStrings(aLeft, aRight); + } + + return ::Compare(aLeft, aRight, nsCaseInsensitiveStringComparator); +} + +static int testSortCallback(const void* data1, const void* data2, + void* privateData) { + /// Note: testSortCallback is a small C callback stub for NS_QuickSort + contentSortInfo* left = (contentSortInfo*)data1; + contentSortInfo* right = (contentSortInfo*)data2; + nsSortState* sortState = (nsSortState*)privateData; + + int32_t sortOrder = 0; + + int32_t length = sortState->sortKeys.Length(); + for (int32_t t = 0; t < length; t++) { + // compare attributes. Ignore namespaces for now. + nsAutoString leftstr, rightstr; + if (left->content->IsElement()) { + left->content->AsElement()->GetAttr(kNameSpaceID_None, + sortState->sortKeys[t], leftstr); + } + if (right->content->IsElement()) { + right->content->AsElement()->GetAttr(kNameSpaceID_None, + sortState->sortKeys[t], rightstr); + } + + sortOrder = CompareValues(leftstr, rightstr, sortState->sortHints); + } + + if (sortState->direction == nsSortState_descending) sortOrder = -sortOrder; + + return sortOrder; +} + +/** + * Given a list of sortable items, reverse the list. This is done + * when simply changing the sort direction for the same key. + */ +static nsresult InvertSortInfo(nsTArray& aData, int32_t aStart, + int32_t aNumItems) { + if (aNumItems > 1) { + // reverse the items in the array starting from aStart + int32_t upPoint = (aNumItems + 1) / 2 + aStart; + int32_t downPoint = (aNumItems - 2) / 2 + aStart; + int32_t half = aNumItems / 2; + while (half-- > 0) { + aData[downPoint--].swap(aData[upPoint++]); + } + } + return NS_OK; +} + +/** + * Sort a container using the supplied sort state details. + */ +static nsresult SortContainer(nsIContent* aContainer, nsSortState* aSortState) { + nsTArray items; + nsresult rv = GetItemsToSort(aContainer, aSortState, items); + NS_ENSURE_SUCCESS(rv, rv); + + uint32_t numResults = items.Length(); + if (!numResults) return NS_OK; + + uint32_t i; + + // if the items are just being inverted, that is, just switching between + // ascending and descending, just reverse the list. + if (aSortState->invertSort) + InvertSortInfo(items, 0, numResults); + else + NS_QuickSort((void*)items.Elements(), numResults, sizeof(contentSortInfo), + testSortCallback, (void*)aSortState); + + // first remove the items from the old positions + for (i = 0; i < numResults; i++) { + nsIContent* child = items[i].content; + nsIContent* parent = child->GetParent(); + + if (parent) { + // remember the parent so that it can be reinserted back + // into the same parent. This is necessary as multiple rules + // may generate results which get placed in different locations. + items[i].parent = parent; + parent->RemoveChildNode(child, true); + } + } + + // now add the items back in sorted order + for (i = 0; i < numResults; i++) { + nsIContent* child = items[i].content; + nsIContent* parent = items[i].parent; + if (parent) { + parent->AppendChildTo(child, true, mozilla::IgnoreErrors()); + + // if it's a container in a tree or menu, find its children, + // and sort those also + if (!child->IsElement() || !child->AsElement()->AttrValueIs( + kNameSpaceID_None, nsGkAtoms::container, + nsGkAtoms::_true, eCaseMatters)) + continue; + + for (nsIContent* grandchild = child->GetFirstChild(); grandchild; + grandchild = grandchild->GetNextSibling()) { + mozilla::dom::NodeInfo* ni = grandchild->NodeInfo(); + nsAtom* localName = ni->NameAtom(); + if (ni->NamespaceID() == kNameSpaceID_XUL && + (localName == nsGkAtoms::treechildren || + localName == nsGkAtoms::menupopup)) { + SortContainer(grandchild, aSortState); + } + } + } + } + + return NS_OK; +} + +/** + * Initialize sort information from attributes specified on the container, + * the sort key and sort direction. + * + * @param aRootElement the element that contains sort attributes + * @param aContainer the container to sort, usually equal to aRootElement + * @param aSortKey space separated list of sort keys + * @param aSortDirection direction to sort in + * @param aSortState structure filled in with sort data + */ +static nsresult InitializeSortState(Element* aRootElement, Element* aContainer, + const nsAString& aSortKey, + const nsAString& aSortHints, + nsSortState* aSortState) { + // used as an optimization for the content builder + if (aContainer != aSortState->lastContainer.get()) { + aSortState->lastContainer = aContainer; + aSortState->lastWasFirst = false; + aSortState->lastWasLast = false; + } + + // The sort attribute is of the form: sort="key1 key2 ..." + nsAutoString sort(aSortKey); + aSortState->sortKeys.Clear(); + nsWhitespaceTokenizer tokenizer(sort); + while (tokenizer.hasMoreTokens()) { + RefPtr keyatom = NS_Atomize(tokenizer.nextToken()); + NS_ENSURE_TRUE(keyatom, NS_ERROR_OUT_OF_MEMORY); + aSortState->sortKeys.AppendElement(keyatom); + } + + aSortState->sort.Assign(sort); + aSortState->direction = nsSortState_natural; + + bool noNaturalState = false; + nsWhitespaceTokenizer hintsTokenizer(aSortHints); + while (hintsTokenizer.hasMoreTokens()) { + const nsDependentSubstring& token(hintsTokenizer.nextToken()); + if (token.EqualsLiteral("comparecase")) + aSortState->sortHints |= SORT_COMPARECASE; + else if (token.EqualsLiteral("integer")) + aSortState->sortHints |= SORT_INTEGER; + else if (token.EqualsLiteral("descending")) + aSortState->direction = nsSortState_descending; + else if (token.EqualsLiteral("ascending")) + aSortState->direction = nsSortState_ascending; + else if (token.EqualsLiteral("twostate")) + noNaturalState = true; + } + + // if the twostate flag was set, the natural order is skipped and only + // ascending and descending are allowed + if (aSortState->direction == nsSortState_natural && noNaturalState) { + aSortState->direction = nsSortState_ascending; + } + + // set up sort order info + aSortState->invertSort = false; + + nsAutoString existingsort; + aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sort, existingsort); + nsAutoString existingsortDirection; + aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection, + existingsortDirection); + + // if just switching direction, set the invertSort flag + if (sort.Equals(existingsort)) { + if (aSortState->direction == nsSortState_descending) { + if (existingsortDirection.EqualsLiteral("ascending")) + aSortState->invertSort = true; + } else if (aSortState->direction == nsSortState_ascending && + existingsortDirection.EqualsLiteral("descending")) { + aSortState->invertSort = true; + } + } + + aSortState->initialized = true; + + return NS_OK; +} + +nsresult mozilla::XULWidgetSort(Element* aNode, const nsAString& aSortKey, + const nsAString& aSortHints) { + nsSortState sortState; + nsresult rv = + InitializeSortState(aNode, aNode, aSortKey, aSortHints, &sortState); + NS_ENSURE_SUCCESS(rv, rv); + + // store sort info in attributes on content + SetSortHints(aNode, &sortState); + rv = SortContainer(aNode, &sortState); + + return rv; +} -- cgit v1.2.3