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 "nsQuickSort.h"
18 #include "nsWhitespaceTokenizer.h"
19 #include "nsXULSortService.h"
20 #include "nsXULElement.h"
22 #include "nsUnicharUtils.h"
24 #include "mozilla/dom/Element.h"
25 #include "mozilla/intl/Collator.h"
27 using mozilla::dom::Element
;
28 const unsigned long SORT_COMPARECASE
= 0x0001;
29 const unsigned long SORT_INTEGER
= 0x0100;
31 enum nsSortState_direction
{
32 nsSortState_descending
,
33 nsSortState_ascending
,
37 // the sort state holds info about the current sort
38 struct MOZ_STACK_CLASS nsSortState final
{
40 MOZ_INIT_OUTSIDE_CTOR
bool invertSort
;
44 MOZ_INIT_OUTSIDE_CTOR nsSortState_direction direction
;
46 nsTArray
<RefPtr
<nsAtom
>> sortKeys
;
48 nsCOMPtr
<nsIContent
> lastContainer
;
49 MOZ_INIT_OUTSIDE_CTOR
bool lastWasFirst
, lastWasLast
;
51 nsSortState() : initialized(false), sortHints(0) {}
54 // information about a particular item to be sorted
55 struct contentSortInfo
{
56 nsCOMPtr
<nsIContent
> content
;
57 nsCOMPtr
<nsIContent
> parent
;
58 void swap(contentSortInfo
& other
) {
59 content
.swap(other
.content
);
60 parent
.swap(other
.parent
);
65 * Set sortActive and sortDirection attributes on a tree column when a sort
66 * is done. The column to change is the one with a sort attribute that
67 * matches the sort key. The sort attributes are removed from the other
70 static void SetSortColumnHints(nsIContent
* content
,
71 const nsAString
& sortResource
,
72 const nsAString
& sortDirection
) {
73 // set sort info on current column. This ensures that the
74 // column header sort indicator is updated properly.
75 for (nsIContent
* child
= content
->GetFirstChild(); child
;
76 child
= child
->GetNextSibling()) {
77 if (child
->IsXULElement(nsGkAtoms::treecols
)) {
78 SetSortColumnHints(child
, sortResource
, sortDirection
);
79 } else if (child
->IsXULElement(nsGkAtoms::treecol
)) {
81 child
->AsElement()->GetAttr(nsGkAtoms::sort
, value
);
82 if (value
== sortResource
) {
83 child
->AsElement()->SetAttr(kNameSpaceID_None
, nsGkAtoms::sortActive
,
86 child
->AsElement()->SetAttr(kNameSpaceID_None
, nsGkAtoms::sortDirection
,
88 // Note: don't break out of loop; want to set/unset
89 // attribs on ALL sort columns
90 } else if (!value
.IsEmpty()) {
91 child
->AsElement()->UnsetAttr(kNameSpaceID_None
, nsGkAtoms::sortActive
,
93 child
->AsElement()->UnsetAttr(kNameSpaceID_None
,
94 nsGkAtoms::sortDirection
, true);
101 * Set sort and sortDirection attributes when a sort is done.
103 static void SetSortHints(Element
* aElement
, nsSortState
* aSortState
) {
104 // set sort and sortDirection attributes when is sort is done
105 aElement
->SetAttr(kNameSpaceID_None
, nsGkAtoms::sort
, aSortState
->sort
, true);
107 nsAutoString direction
;
108 if (aSortState
->direction
== nsSortState_descending
)
109 direction
.AssignLiteral("descending");
110 else if (aSortState
->direction
== nsSortState_ascending
)
111 direction
.AssignLiteral("ascending");
112 aElement
->SetAttr(kNameSpaceID_None
, nsGkAtoms::sortDirection
, direction
,
115 // for trees, also set the sort info on the currently sorted column
116 if (aElement
->IsXULElement(nsGkAtoms::tree
)) {
117 if (aSortState
->sortKeys
.Length() >= 1) {
118 nsAutoString sortkey
;
119 aSortState
->sortKeys
[0]->ToString(sortkey
);
120 SetSortColumnHints(aElement
, sortkey
, direction
);
126 * Determine the list of items which need to be sorted. This is determined
127 * in the following way:
128 * - for elements that have a content builder, get its list of generated
130 * - otherwise, for trees, get the child treeitems
131 * - otherwise, get the direct children
133 static nsresult
GetItemsToSort(nsIContent
* aContainer
, nsSortState
* aSortState
,
134 nsTArray
<contentSortInfo
>& aSortItems
) {
135 // Get the children. For trees, get the treechildren element and
136 // use that as the parent
137 RefPtr
<Element
> treechildren
;
138 if (aContainer
->IsXULElement(nsGkAtoms::tree
)) {
139 nsXULContentUtils::FindChildByTag(aContainer
, kNameSpaceID_XUL
,
140 nsGkAtoms::treechildren
,
141 getter_AddRefs(treechildren
));
142 if (!treechildren
) return NS_OK
;
144 aContainer
= treechildren
;
147 for (nsIContent
* child
= aContainer
->GetFirstChild(); child
;
148 child
= child
->GetNextSibling()) {
149 contentSortInfo
* cinfo
= aSortItems
.AppendElement();
150 if (!cinfo
) return NS_ERROR_OUT_OF_MEMORY
;
152 cinfo
->content
= child
;
159 * Compares aLeft and aRight and returns < 0, 0, or > 0. The sort
160 * hints are checked for case matching and integer sorting.
162 static int32_t CompareValues(const nsAString
& aLeft
, const nsAString
& aRight
,
163 uint32_t aSortHints
) {
164 if (aSortHints
& SORT_INTEGER
) {
166 int32_t leftint
= PromiseFlatString(aLeft
).ToInteger(&err
);
167 if (NS_SUCCEEDED(err
)) {
168 int32_t rightint
= PromiseFlatString(aRight
).ToInteger(&err
);
169 if (NS_SUCCEEDED(err
)) {
170 return leftint
- rightint
;
173 // if they aren't integers, just fall through and compare strings
176 if (aSortHints
& SORT_COMPARECASE
) {
177 return ::Compare(aLeft
, aRight
);
180 using mozilla::intl::Collator
;
181 const Collator
* collator
= nsXULContentUtils::GetCollator();
183 return collator
->CompareStrings(aLeft
, aRight
);
186 return ::Compare(aLeft
, aRight
, nsCaseInsensitiveStringComparator
);
189 static int testSortCallback(const void* data1
, const void* data2
,
191 /// Note: testSortCallback is a small C callback stub for NS_QuickSort
192 contentSortInfo
* left
= (contentSortInfo
*)data1
;
193 contentSortInfo
* right
= (contentSortInfo
*)data2
;
194 nsSortState
* sortState
= (nsSortState
*)privateData
;
196 int32_t sortOrder
= 0;
198 int32_t length
= sortState
->sortKeys
.Length();
199 for (int32_t t
= 0; t
< length
; t
++) {
200 // compare attributes. Ignore namespaces for now.
201 nsAutoString leftstr
, rightstr
;
202 if (left
->content
->IsElement()) {
203 left
->content
->AsElement()->GetAttr(sortState
->sortKeys
[t
], leftstr
);
205 if (right
->content
->IsElement()) {
206 right
->content
->AsElement()->GetAttr(sortState
->sortKeys
[t
], rightstr
);
209 sortOrder
= CompareValues(leftstr
, rightstr
, sortState
->sortHints
);
212 if (sortState
->direction
== nsSortState_descending
) sortOrder
= -sortOrder
;
218 * Given a list of sortable items, reverse the list. This is done
219 * when simply changing the sort direction for the same key.
221 static nsresult
InvertSortInfo(nsTArray
<contentSortInfo
>& aData
, int32_t aStart
,
224 // reverse the items in the array starting from aStart
225 int32_t upPoint
= (aNumItems
+ 1) / 2 + aStart
;
226 int32_t downPoint
= (aNumItems
- 2) / 2 + aStart
;
227 int32_t half
= aNumItems
/ 2;
229 aData
[downPoint
--].swap(aData
[upPoint
++]);
236 * Sort a container using the supplied sort state details.
238 static nsresult
SortContainer(nsIContent
* aContainer
, nsSortState
* aSortState
) {
239 nsTArray
<contentSortInfo
> items
;
240 nsresult rv
= GetItemsToSort(aContainer
, aSortState
, items
);
241 NS_ENSURE_SUCCESS(rv
, rv
);
243 uint32_t numResults
= items
.Length();
244 if (!numResults
) return NS_OK
;
248 // if the items are just being inverted, that is, just switching between
249 // ascending and descending, just reverse the list.
250 if (aSortState
->invertSort
)
251 InvertSortInfo(items
, 0, numResults
);
253 NS_QuickSort((void*)items
.Elements(), numResults
, sizeof(contentSortInfo
),
254 testSortCallback
, (void*)aSortState
);
256 // first remove the items from the old positions
257 for (i
= 0; i
< numResults
; i
++) {
258 nsIContent
* child
= items
[i
].content
;
259 nsIContent
* parent
= child
->GetParent();
262 // remember the parent so that it can be reinserted back
263 // into the same parent. This is necessary as multiple rules
264 // may generate results which get placed in different locations.
265 items
[i
].parent
= parent
;
266 parent
->RemoveChildNode(child
, true);
270 // now add the items back in sorted order
271 for (i
= 0; i
< numResults
; i
++) {
272 nsIContent
* child
= items
[i
].content
;
273 nsIContent
* parent
= items
[i
].parent
;
275 parent
->AppendChildTo(child
, true, mozilla::IgnoreErrors());
277 // if it's a container in a tree or menu, find its children,
278 // and sort those also
279 if (!child
->IsElement() || !child
->AsElement()->AttrValueIs(
280 kNameSpaceID_None
, nsGkAtoms::container
,
281 nsGkAtoms::_true
, eCaseMatters
))
284 for (nsIContent
* grandchild
= child
->GetFirstChild(); grandchild
;
285 grandchild
= grandchild
->GetNextSibling()) {
286 mozilla::dom::NodeInfo
* ni
= grandchild
->NodeInfo();
287 nsAtom
* localName
= ni
->NameAtom();
288 if (ni
->NamespaceID() == kNameSpaceID_XUL
&&
289 (localName
== nsGkAtoms::treechildren
||
290 localName
== nsGkAtoms::menupopup
)) {
291 SortContainer(grandchild
, aSortState
);
301 * Initialize sort information from attributes specified on the container,
302 * the sort key and sort direction.
304 * @param aRootElement the element that contains sort attributes
305 * @param aContainer the container to sort, usually equal to aRootElement
306 * @param aSortKey space separated list of sort keys
307 * @param aSortDirection direction to sort in
308 * @param aSortState structure filled in with sort data
310 static nsresult
InitializeSortState(Element
* aRootElement
, Element
* aContainer
,
311 const nsAString
& aSortKey
,
312 const nsAString
& aSortHints
,
313 nsSortState
* aSortState
) {
314 // used as an optimization for the content builder
315 if (aContainer
!= aSortState
->lastContainer
.get()) {
316 aSortState
->lastContainer
= aContainer
;
317 aSortState
->lastWasFirst
= false;
318 aSortState
->lastWasLast
= false;
321 // The sort attribute is of the form: sort="key1 key2 ..."
322 nsAutoString
sort(aSortKey
);
323 aSortState
->sortKeys
.Clear();
324 nsWhitespaceTokenizer
tokenizer(sort
);
325 while (tokenizer
.hasMoreTokens()) {
326 RefPtr
<nsAtom
> keyatom
= NS_Atomize(tokenizer
.nextToken());
327 NS_ENSURE_TRUE(keyatom
, NS_ERROR_OUT_OF_MEMORY
);
328 aSortState
->sortKeys
.AppendElement(keyatom
);
331 aSortState
->sort
.Assign(sort
);
332 aSortState
->direction
= nsSortState_natural
;
334 bool noNaturalState
= false;
335 nsWhitespaceTokenizer
hintsTokenizer(aSortHints
);
336 while (hintsTokenizer
.hasMoreTokens()) {
337 const nsDependentSubstring
& token(hintsTokenizer
.nextToken());
338 if (token
.EqualsLiteral("comparecase"))
339 aSortState
->sortHints
|= SORT_COMPARECASE
;
340 else if (token
.EqualsLiteral("integer"))
341 aSortState
->sortHints
|= SORT_INTEGER
;
342 else if (token
.EqualsLiteral("descending"))
343 aSortState
->direction
= nsSortState_descending
;
344 else if (token
.EqualsLiteral("ascending"))
345 aSortState
->direction
= nsSortState_ascending
;
346 else if (token
.EqualsLiteral("twostate"))
347 noNaturalState
= true;
350 // if the twostate flag was set, the natural order is skipped and only
351 // ascending and descending are allowed
352 if (aSortState
->direction
== nsSortState_natural
&& noNaturalState
) {
353 aSortState
->direction
= nsSortState_ascending
;
356 // set up sort order info
357 aSortState
->invertSort
= false;
359 nsAutoString existingsort
;
360 aRootElement
->GetAttr(nsGkAtoms::sort
, existingsort
);
361 nsAutoString existingsortDirection
;
362 aRootElement
->GetAttr(nsGkAtoms::sortDirection
, existingsortDirection
);
364 // if just switching direction, set the invertSort flag
365 if (sort
.Equals(existingsort
)) {
366 if (aSortState
->direction
== nsSortState_descending
) {
367 if (existingsortDirection
.EqualsLiteral("ascending"))
368 aSortState
->invertSort
= true;
369 } else if (aSortState
->direction
== nsSortState_ascending
&&
370 existingsortDirection
.EqualsLiteral("descending")) {
371 aSortState
->invertSort
= true;
375 aSortState
->initialized
= true;
380 nsresult
mozilla::XULWidgetSort(Element
* aNode
, const nsAString
& aSortKey
,
381 const nsAString
& aSortHints
) {
382 nsSortState sortState
;
384 InitializeSortState(aNode
, aNode
, aSortKey
, aSortHints
, &sortState
);
385 NS_ENSURE_SUCCESS(rv
, rv
);
387 // store sort info in attributes on content
388 SetSortHints(aNode
, &sortState
);
389 rv
= SortContainer(aNode
, &sortState
);