Source code

Revision control

Other Tools

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/. */
5
6
/*
7
This file provides the implementation for the sort service manager.
8
*/
9
10
#include "nsCOMArray.h"
11
#include "nsCOMPtr.h"
12
#include "nsIContent.h"
13
#include "nsGkAtoms.h"
14
#include "nsNameSpaceManager.h"
15
#include "nsXULContentUtils.h"
16
#include "nsString.h"
17
#include "nsQuickSort.h"
18
#include "nsWhitespaceTokenizer.h"
19
#include "nsXULSortService.h"
20
#include "nsXULElement.h"
21
#include "nsICollation.h"
22
#include "nsTArray.h"
23
#include "nsUnicharUtils.h"
24
25
#include "mozilla/dom/Element.h"
26
27
using mozilla::dom::Element;
28
const unsigned long SORT_COMPARECASE = 0x0001;
29
const unsigned long SORT_INTEGER = 0x0100;
30
31
enum nsSortState_direction {
32
nsSortState_descending,
33
nsSortState_ascending,
34
nsSortState_natural
35
};
36
37
// the sort state holds info about the current sort
38
struct MOZ_STACK_CLASS nsSortState final {
39
bool initialized;
40
MOZ_INIT_OUTSIDE_CTOR bool invertSort;
41
42
uint32_t sortHints;
43
44
MOZ_INIT_OUTSIDE_CTOR nsSortState_direction direction;
45
nsAutoString sort;
46
nsTArray<RefPtr<nsAtom>> sortKeys;
47
48
nsCOMPtr<nsIContent> lastContainer;
49
MOZ_INIT_OUTSIDE_CTOR bool lastWasFirst, lastWasLast;
50
51
nsSortState() : initialized(false), sortHints(0) {}
52
};
53
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);
61
}
62
};
63
64
/**
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
68
* columns.
69
*/
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)) {
80
nsAutoString value;
81
child->AsElement()->GetAttr(kNameSpaceID_None, nsGkAtoms::sort, value);
82
if (value == sortResource) {
83
child->AsElement()->SetAttr(kNameSpaceID_None, nsGkAtoms::sortActive,
84
NS_LITERAL_STRING("true"), true);
85
86
child->AsElement()->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
87
sortDirection, true);
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,
92
true);
93
child->AsElement()->UnsetAttr(kNameSpaceID_None,
94
nsGkAtoms::sortDirection, true);
95
}
96
}
97
}
98
}
99
100
/**
101
* Set sort and sortDirection attributes when a sort is done.
102
*/
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);
106
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,
113
true);
114
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);
121
}
122
}
123
}
124
125
/**
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
129
* results
130
* - otherwise, for trees, get the child treeitems
131
* - otherwise, get the direct children
132
*/
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;
143
144
aContainer = treechildren;
145
}
146
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;
151
152
cinfo->content = child;
153
}
154
155
return NS_OK;
156
}
157
158
/**
159
* Compares aLeft and aRight and returns < 0, 0, or > 0. The sort
160
* hints are checked for case matching and integer sorting.
161
*/
162
static int32_t CompareValues(const nsAString& aLeft, const nsAString& aRight,
163
uint32_t aSortHints) {
164
if (aSortHints & SORT_INTEGER) {
165
nsresult err;
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;
171
}
172
}
173
// if they aren't integers, just fall through and compare strings
174
}
175
176
if (aSortHints & SORT_COMPARECASE) {
177
return ::Compare(aLeft, aRight);
178
}
179
180
nsICollation* collation = nsXULContentUtils::GetCollation();
181
if (collation) {
182
int32_t result;
183
collation->CompareString(nsICollation::kCollationCaseInSensitive, aLeft,
184
aRight, &result);
185
return result;
186
}
187
188
return ::Compare(aLeft, aRight, nsCaseInsensitiveStringComparator());
189
}
190
191
static int testSortCallback(const void* data1, const void* data2,
192
void* privateData) {
193
/// Note: testSortCallback is a small C callback stub for NS_QuickSort
194
contentSortInfo* left = (contentSortInfo*)data1;
195
contentSortInfo* right = (contentSortInfo*)data2;
196
nsSortState* sortState = (nsSortState*)privateData;
197
198
int32_t sortOrder = 0;
199
200
int32_t length = sortState->sortKeys.Length();
201
for (int32_t t = 0; t < length; t++) {
202
// compare attributes. Ignore namespaces for now.
203
nsAutoString leftstr, rightstr;
204
if (left->content->IsElement()) {
205
left->content->AsElement()->GetAttr(kNameSpaceID_None,
206
sortState->sortKeys[t], leftstr);
207
}
208
if (right->content->IsElement()) {
209
right->content->AsElement()->GetAttr(kNameSpaceID_None,
210
sortState->sortKeys[t], rightstr);
211
}
212
213
sortOrder = CompareValues(leftstr, rightstr, sortState->sortHints);
214
}
215
216
if (sortState->direction == nsSortState_descending) sortOrder = -sortOrder;
217
218
return sortOrder;
219
}
220
221
/**
222
* Given a list of sortable items, reverse the list. This is done
223
* when simply changing the sort direction for the same key.
224
*/
225
static nsresult InvertSortInfo(nsTArray<contentSortInfo>& aData, int32_t aStart,
226
int32_t aNumItems) {
227
if (aNumItems > 1) {
228
// reverse the items in the array starting from aStart
229
int32_t upPoint = (aNumItems + 1) / 2 + aStart;
230
int32_t downPoint = (aNumItems - 2) / 2 + aStart;
231
int32_t half = aNumItems / 2;
232
while (half-- > 0) {
233
aData[downPoint--].swap(aData[upPoint++]);
234
}
235
}
236
return NS_OK;
237
}
238
239
/**
240
* Sort a container using the supplied sort state details.
241
*/
242
static nsresult SortContainer(nsIContent* aContainer, nsSortState* aSortState) {
243
nsTArray<contentSortInfo> items;
244
nsresult rv = GetItemsToSort(aContainer, aSortState, items);
245
NS_ENSURE_SUCCESS(rv, rv);
246
247
uint32_t numResults = items.Length();
248
if (!numResults) return NS_OK;
249
250
uint32_t i;
251
252
// if the items are just being inverted, that is, just switching between
253
// ascending and descending, just reverse the list.
254
if (aSortState->invertSort)
255
InvertSortInfo(items, 0, numResults);
256
else
257
NS_QuickSort((void*)items.Elements(), numResults, sizeof(contentSortInfo),
258
testSortCallback, (void*)aSortState);
259
260
// first remove the items from the old positions
261
for (i = 0; i < numResults; i++) {
262
nsIContent* child = items[i].content;
263
nsIContent* parent = child->GetParent();
264
265
if (parent) {
266
// remember the parent so that it can be reinserted back
267
// into the same parent. This is necessary as multiple rules
268
// may generate results which get placed in different locations.
269
items[i].parent = parent;
270
parent->RemoveChildNode(child, true);
271
}
272
}
273
274
// now add the items back in sorted order
275
for (i = 0; i < numResults; i++) {
276
nsIContent* child = items[i].content;
277
nsIContent* parent = items[i].parent;
278
if (parent) {
279
parent->AppendChildTo(child, true);
280
281
// if it's a container in a tree or menu, find its children,
282
// and sort those also
283
if (!child->IsElement() || !child->AsElement()->AttrValueIs(
284
kNameSpaceID_None, nsGkAtoms::container,
285
nsGkAtoms::_true, eCaseMatters))
286
continue;
287
288
for (nsIContent* grandchild = child->GetFirstChild(); grandchild;
289
grandchild = grandchild->GetNextSibling()) {
290
mozilla::dom::NodeInfo* ni = grandchild->NodeInfo();
291
nsAtom* localName = ni->NameAtom();
292
if (ni->NamespaceID() == kNameSpaceID_XUL &&
293
(localName == nsGkAtoms::treechildren ||
294
localName == nsGkAtoms::menupopup)) {
295
SortContainer(grandchild, aSortState);
296
}
297
}
298
}
299
}
300
301
return NS_OK;
302
}
303
304
/**
305
* Initialize sort information from attributes specified on the container,
306
* the sort key and sort direction.
307
*
308
* @param aRootElement the element that contains sort attributes
309
* @param aContainer the container to sort, usually equal to aRootElement
310
* @param aSortKey space separated list of sort keys
311
* @param aSortDirection direction to sort in
312
* @param aSortState structure filled in with sort data
313
*/
314
static nsresult InitializeSortState(Element* aRootElement, Element* aContainer,
315
const nsAString& aSortKey,
316
const nsAString& aSortHints,
317
nsSortState* aSortState) {
318
// used as an optimization for the content builder
319
if (aContainer != aSortState->lastContainer.get()) {
320
aSortState->lastContainer = aContainer;
321
aSortState->lastWasFirst = false;
322
aSortState->lastWasLast = false;
323
}
324
325
// The sort attribute is of the form: sort="key1 key2 ..."
326
nsAutoString sort(aSortKey);
327
aSortState->sortKeys.Clear();
328
nsWhitespaceTokenizer tokenizer(sort);
329
while (tokenizer.hasMoreTokens()) {
330
RefPtr<nsAtom> keyatom = NS_Atomize(tokenizer.nextToken());
331
NS_ENSURE_TRUE(keyatom, NS_ERROR_OUT_OF_MEMORY);
332
aSortState->sortKeys.AppendElement(keyatom);
333
}
334
335
aSortState->sort.Assign(sort);
336
aSortState->direction = nsSortState_natural;
337
338
bool noNaturalState = false;
339
nsWhitespaceTokenizer hintsTokenizer(aSortHints);
340
while (hintsTokenizer.hasMoreTokens()) {
341
const nsDependentSubstring& token(hintsTokenizer.nextToken());
342
if (token.EqualsLiteral("comparecase"))
343
aSortState->sortHints |= SORT_COMPARECASE;
344
else if (token.EqualsLiteral("integer"))
345
aSortState->sortHints |= SORT_INTEGER;
346
else if (token.EqualsLiteral("descending"))
347
aSortState->direction = nsSortState_descending;
348
else if (token.EqualsLiteral("ascending"))
349
aSortState->direction = nsSortState_ascending;
350
else if (token.EqualsLiteral("twostate"))
351
noNaturalState = true;
352
}
353
354
// if the twostate flag was set, the natural order is skipped and only
355
// ascending and descending are allowed
356
if (aSortState->direction == nsSortState_natural && noNaturalState) {
357
aSortState->direction = nsSortState_ascending;
358
}
359
360
// set up sort order info
361
aSortState->invertSort = false;
362
363
nsAutoString existingsort;
364
aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sort, existingsort);
365
nsAutoString existingsortDirection;
366
aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
367
existingsortDirection);
368
369
// if just switching direction, set the invertSort flag
370
if (sort.Equals(existingsort)) {
371
if (aSortState->direction == nsSortState_descending) {
372
if (existingsortDirection.EqualsLiteral("ascending"))
373
aSortState->invertSort = true;
374
} else if (aSortState->direction == nsSortState_ascending &&
375
existingsortDirection.EqualsLiteral("descending")) {
376
aSortState->invertSort = true;
377
}
378
}
379
380
aSortState->initialized = true;
381
382
return NS_OK;
383
}
384
385
nsresult mozilla::XULWidgetSort(Element* aNode, const nsAString& aSortKey,
386
const nsAString& aSortHints) {
387
nsSortState sortState;
388
nsresult rv =
389
InitializeSortState(aNode, aNode, aSortKey, aSortHints, &sortState);
390
NS_ENSURE_SUCCESS(rv, rv);
391
392
// store sort info in attributes on content
393
SetSortHints(aNode, &sortState);
394
rv = SortContainer(aNode, &sortState);
395
396
return rv;
397
}