1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 This file provides the implementation for the sort service manager.
10 #include "nsCOMArray.h"
12 #include "nsIContent.h"
13 #include "nsGkAtoms.h"
14 #include "nsNameSpaceManager.h"
15 #include "nsXULContentUtils.h"
17 #include "nsWhitespaceTokenizer.h"
18 #include "nsXULSortService.h"
19 #include "nsXULElement.h"
21 #include "nsUnicharUtils.h"
23 #include "mozilla/dom/Element.h"
24 #include "mozilla/intl/Collator.h"
26 using mozilla::dom::Element
;
27 const unsigned long SORT_COMPARECASE
= 0x0001;
28 const unsigned long SORT_INTEGER
= 0x0100;
30 enum nsSortState_direction
{
31 nsSortState_descending
,
32 nsSortState_ascending
,
36 // the sort state holds info about the current sort
37 struct MOZ_STACK_CLASS nsSortState final
{
39 MOZ_INIT_OUTSIDE_CTOR
bool invertSort
;
43 MOZ_INIT_OUTSIDE_CTOR nsSortState_direction direction
;
45 nsTArray
<RefPtr
<nsAtom
>> sortKeys
;
47 nsCOMPtr
<nsIContent
> lastContainer
;
48 MOZ_INIT_OUTSIDE_CTOR
bool lastWasFirst
, lastWasLast
;
50 nsSortState() : initialized(false), sortHints(0) {}
53 // Information about a particular item to be sorted.
54 // Its lifecycle is bound to the 'SortContainer' function scope,
55 // so we can use raw pointers to avoid refcount noise during sorting.
56 struct contentSortInfo
{
62 * Set sortActive and sortDirection attributes on a tree column when a sort
63 * is done. The column to change is the one with a sort attribute that
64 * matches the sort key. The sort attributes are removed from the other
67 static void SetSortColumnHints(nsIContent
* content
,
68 const nsAString
& sortResource
,
69 const nsAString
& sortDirection
) {
70 // set sort info on current column. This ensures that the
71 // column header sort indicator is updated properly.
72 for (nsIContent
* child
= content
->GetFirstChild(); child
;
73 child
= child
->GetNextSibling()) {
74 if (child
->IsXULElement(nsGkAtoms::treecols
)) {
75 SetSortColumnHints(child
, sortResource
, sortDirection
);
76 } else if (child
->IsXULElement(nsGkAtoms::treecol
)) {
78 child
->AsElement()->GetAttr(nsGkAtoms::sort
, value
);
79 if (value
== sortResource
) {
80 child
->AsElement()->SetAttr(kNameSpaceID_None
, nsGkAtoms::sortActive
,
83 child
->AsElement()->SetAttr(kNameSpaceID_None
, nsGkAtoms::sortDirection
,
85 // Note: don't break out of loop; want to set/unset
86 // attribs on ALL sort columns
87 } else if (!value
.IsEmpty()) {
88 child
->AsElement()->UnsetAttr(kNameSpaceID_None
, nsGkAtoms::sortActive
,
90 child
->AsElement()->UnsetAttr(kNameSpaceID_None
,
91 nsGkAtoms::sortDirection
, true);
98 * Set sort and sortDirection attributes when a sort is done.
100 static void SetSortHints(Element
* aElement
, nsSortState
* aSortState
) {
101 // set sort and sortDirection attributes when is sort is done
102 aElement
->SetAttr(kNameSpaceID_None
, nsGkAtoms::sort
, aSortState
->sort
, true);
104 nsAutoString direction
;
105 if (aSortState
->direction
== nsSortState_descending
)
106 direction
.AssignLiteral("descending");
107 else if (aSortState
->direction
== nsSortState_ascending
)
108 direction
.AssignLiteral("ascending");
109 aElement
->SetAttr(kNameSpaceID_None
, nsGkAtoms::sortDirection
, direction
,
112 // for trees, also set the sort info on the currently sorted column
113 if (aElement
->IsXULElement(nsGkAtoms::tree
)) {
114 if (aSortState
->sortKeys
.Length() >= 1) {
115 nsAutoString sortkey
;
116 aSortState
->sortKeys
[0]->ToString(sortkey
);
117 SetSortColumnHints(aElement
, sortkey
, direction
);
123 * Determine the list of items which need to be sorted. This is determined
124 * in the following way:
125 * - for elements that have a content builder, get its list of generated
127 * - otherwise, for trees, get the child treeitems
128 * - otherwise, get the direct children
130 static nsresult
GetItemsToSort(nsIContent
* aContainer
,
131 nsTArray
<contentSortInfo
>& aSortItems
) {
132 // Get the children. For trees, get the treechildren element and
133 // use that as the parent
134 RefPtr
<Element
> treechildren
;
135 if (aContainer
->IsXULElement(nsGkAtoms::tree
)) {
136 nsXULContentUtils::FindChildByTag(aContainer
, kNameSpaceID_XUL
,
137 nsGkAtoms::treechildren
,
138 getter_AddRefs(treechildren
));
139 if (!treechildren
) return NS_OK
;
141 aContainer
= treechildren
;
144 for (nsIContent
* child
= aContainer
->GetFirstChild(); child
;
145 child
= child
->GetNextSibling()) {
146 contentSortInfo
* cinfo
= aSortItems
.AppendElement();
147 if (!cinfo
) return NS_ERROR_OUT_OF_MEMORY
;
149 cinfo
->content
= child
;
156 * Compares aLeft and aRight and returns < 0, 0, or > 0. The sort
157 * hints are checked for case matching and integer sorting.
159 static int32_t CompareValues(const nsAString
& aLeft
, const nsAString
& aRight
,
160 uint32_t aSortHints
) {
161 if (aSortHints
& SORT_INTEGER
) {
163 int32_t leftint
= PromiseFlatString(aLeft
).ToInteger(&err
);
164 if (NS_SUCCEEDED(err
)) {
165 int32_t rightint
= PromiseFlatString(aRight
).ToInteger(&err
);
166 if (NS_SUCCEEDED(err
)) {
167 return leftint
- rightint
;
170 // if they aren't integers, just fall through and compare strings
173 if (aSortHints
& SORT_COMPARECASE
) {
174 return ::Compare(aLeft
, aRight
);
177 using mozilla::intl::Collator
;
178 const Collator
* collator
= nsXULContentUtils::GetCollator();
180 return collator
->CompareStrings(aLeft
, aRight
);
183 return ::Compare(aLeft
, aRight
, nsCaseInsensitiveStringComparator
);
186 static int testSortCallback(const contentSortInfo
& left
,
187 const contentSortInfo
& right
,
188 nsSortState
& sortState
) {
189 int32_t sortOrder
= 0;
191 size_t length
= sortState
.sortKeys
.Length();
192 for (size_t t
= 0; t
< length
; t
++) {
193 // compare attributes. Ignore namespaces for now.
194 nsAutoString leftstr
, rightstr
;
195 if (left
.content
->IsElement()) {
196 left
.content
->AsElement()->GetAttr(sortState
.sortKeys
[t
], leftstr
);
198 if (right
.content
->IsElement()) {
199 right
.content
->AsElement()->GetAttr(sortState
.sortKeys
[t
], rightstr
);
202 sortOrder
= CompareValues(leftstr
, rightstr
, sortState
.sortHints
);
205 if (sortState
.direction
== nsSortState_descending
) sortOrder
= -sortOrder
;
211 * Given a list of sortable items, reverse the list. This is done
212 * when simply changing the sort direction for the same key.
214 static nsresult
InvertSortInfo(nsTArray
<contentSortInfo
>& aData
, int32_t aStart
,
217 // reverse the items in the array starting from aStart
218 int32_t upPoint
= (aNumItems
+ 1) / 2 + aStart
;
219 int32_t downPoint
= (aNumItems
- 2) / 2 + aStart
;
220 int32_t half
= aNumItems
/ 2;
222 std::swap(aData
[downPoint
--], aData
[upPoint
++]);
229 * Sort a container using the supplied sort state details.
231 static nsresult
SortContainer(nsIContent
* aContainer
, nsSortState
& aSortState
) {
232 nsTArray
<contentSortInfo
> items
;
233 nsresult rv
= GetItemsToSort(aContainer
, items
);
234 NS_ENSURE_SUCCESS(rv
, rv
);
236 uint32_t numResults
= items
.Length();
237 if (!numResults
) return NS_OK
;
241 // if the items are just being inverted, that is, just switching between
242 // ascending and descending, just reverse the list.
243 if (aSortState
.invertSort
) {
244 InvertSortInfo(items
, 0, numResults
);
246 items
.Sort([&aSortState
](auto left
, auto right
) {
247 return testSortCallback(left
, right
, aSortState
);
251 // first remove the items from the old positions
252 for (i
= 0; i
< numResults
; i
++) {
253 nsIContent
* child
= items
[i
].content
;
254 nsIContent
* parent
= child
->GetParent();
257 // remember the parent so that it can be reinserted back
258 // into the same parent. This is necessary as multiple rules
259 // may generate results which get placed in different locations.
260 items
[i
].parent
= parent
;
261 parent
->RemoveChildNode(child
, true);
265 // now add the items back in sorted order
266 for (i
= 0; i
< numResults
; i
++) {
267 nsIContent
* child
= items
[i
].content
;
268 nsIContent
* parent
= items
[i
].parent
;
270 parent
->AppendChildTo(child
, true, mozilla::IgnoreErrors());
272 // if it's a container in a tree or menu, find its children,
273 // and sort those also
274 if (!child
->IsElement() || !child
->AsElement()->AttrValueIs(
275 kNameSpaceID_None
, nsGkAtoms::container
,
276 nsGkAtoms::_true
, eCaseMatters
))
279 for (nsIContent
* grandchild
= child
->GetFirstChild(); grandchild
;
280 grandchild
= grandchild
->GetNextSibling()) {
281 mozilla::dom::NodeInfo
* ni
= grandchild
->NodeInfo();
282 nsAtom
* localName
= ni
->NameAtom();
283 if (ni
->NamespaceID() == kNameSpaceID_XUL
&&
284 (localName
== nsGkAtoms::treechildren
||
285 localName
== nsGkAtoms::menupopup
)) {
286 SortContainer(grandchild
, aSortState
);
296 * Initialize sort information from attributes specified on the container,
297 * the sort key and sort direction.
299 * @param aRootElement the element that contains sort attributes
300 * @param aContainer the container to sort, usually equal to aRootElement
301 * @param aSortKey space separated list of sort keys
302 * @param aSortDirection direction to sort in
303 * @param aSortState structure filled in with sort data
305 static nsresult
InitializeSortState(Element
* aRootElement
, Element
* aContainer
,
306 const nsAString
& aSortKey
,
307 const nsAString
& aSortHints
,
308 nsSortState
* aSortState
) {
309 // used as an optimization for the content builder
310 if (aContainer
!= aSortState
->lastContainer
.get()) {
311 aSortState
->lastContainer
= aContainer
;
312 aSortState
->lastWasFirst
= false;
313 aSortState
->lastWasLast
= false;
316 // The sort attribute is of the form: sort="key1 key2 ..."
317 nsAutoString
sort(aSortKey
);
318 aSortState
->sortKeys
.Clear();
319 nsWhitespaceTokenizer
tokenizer(sort
);
320 while (tokenizer
.hasMoreTokens()) {
321 RefPtr
<nsAtom
> keyatom
= NS_Atomize(tokenizer
.nextToken());
322 NS_ENSURE_TRUE(keyatom
, NS_ERROR_OUT_OF_MEMORY
);
323 aSortState
->sortKeys
.AppendElement(keyatom
);
326 aSortState
->sort
.Assign(sort
);
327 aSortState
->direction
= nsSortState_natural
;
329 bool noNaturalState
= false;
330 nsWhitespaceTokenizer
hintsTokenizer(aSortHints
);
331 while (hintsTokenizer
.hasMoreTokens()) {
332 const nsDependentSubstring
& token(hintsTokenizer
.nextToken());
333 if (token
.EqualsLiteral("comparecase"))
334 aSortState
->sortHints
|= SORT_COMPARECASE
;
335 else if (token
.EqualsLiteral("integer"))
336 aSortState
->sortHints
|= SORT_INTEGER
;
337 else if (token
.EqualsLiteral("descending"))
338 aSortState
->direction
= nsSortState_descending
;
339 else if (token
.EqualsLiteral("ascending"))
340 aSortState
->direction
= nsSortState_ascending
;
341 else if (token
.EqualsLiteral("twostate"))
342 noNaturalState
= true;
345 // if the twostate flag was set, the natural order is skipped and only
346 // ascending and descending are allowed
347 if (aSortState
->direction
== nsSortState_natural
&& noNaturalState
) {
348 aSortState
->direction
= nsSortState_ascending
;
351 // set up sort order info
352 aSortState
->invertSort
= false;
354 nsAutoString existingsort
;
355 aRootElement
->GetAttr(nsGkAtoms::sort
, existingsort
);
356 nsAutoString existingsortDirection
;
357 aRootElement
->GetAttr(nsGkAtoms::sortDirection
, existingsortDirection
);
359 // if just switching direction, set the invertSort flag
360 if (sort
.Equals(existingsort
)) {
361 if (aSortState
->direction
== nsSortState_descending
) {
362 if (existingsortDirection
.EqualsLiteral("ascending"))
363 aSortState
->invertSort
= true;
364 } else if (aSortState
->direction
== nsSortState_ascending
&&
365 existingsortDirection
.EqualsLiteral("descending")) {
366 aSortState
->invertSort
= true;
370 aSortState
->initialized
= true;
375 nsresult
mozilla::XULWidgetSort(Element
* aNode
, const nsAString
& aSortKey
,
376 const nsAString
& aSortHints
) {
377 nsSortState sortState
;
379 InitializeSortState(aNode
, aNode
, aSortKey
, aSortHints
, &sortState
);
380 NS_ENSURE_SUCCESS(rv
, rv
);
382 // store sort info in attributes on content
383 SetSortHints(aNode
, &sortState
);
384 rv
= SortContainer(aNode
, sortState
);