content/xul/templates/src/nsXULSortService.cpp@6474c204b198
content/xul/templates/src/nsXULSortService.cpp
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
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 * This Original Code has been modified by IBM Corporation.
7 * Modifications made by IBM described herein are
8 * Copyright (c) International Business Machines
9 * Corporation, 2000
10 *
11 * Modifications to Mozilla code or documentation
12 * identified per MPL Section 3.3
13 *
14 * Date Modified by Description of modification
15 * 03/27/2000 IBM Corp. Added PR_CALLBACK for Optlink
16 * use in OS2
17 */
19 /*
20 This file provides the implementation for the sort service manager.
21 */
23 #include "nsCOMPtr.h"
24 #include "nsIContent.h"
25 #include "nsIDOMElement.h"
26 #include "nsIDOMNode.h"
27 #include "nsIServiceManager.h"
28 #include "nsGkAtoms.h"
29 #include "nsNameSpaceManager.h"
30 #include "nsXULContentUtils.h"
31 #include "nsString.h"
32 #include "nsQuickSort.h"
33 #include "nsWhitespaceTokenizer.h"
34 #include "nsXULSortService.h"
35 #include "nsIDOMXULElement.h"
36 #include "nsIXULTemplateBuilder.h"
37 #include "nsTemplateMatch.h"
38 #include "nsICollation.h"
39 #include "nsUnicharUtils.h"
41 NS_IMPL_ISUPPORTS(XULSortServiceImpl, nsIXULSortService)
43 void
44 XULSortServiceImpl::SetSortHints(nsIContent *aNode, nsSortState* aSortState)
45 {
46 // set sort and sortDirection attributes when is sort is done
47 aNode->SetAttr(kNameSpaceID_None, nsGkAtoms::sort,
48 aSortState->sort, true);
50 nsAutoString direction;
51 if (aSortState->direction == nsSortState_descending)
52 direction.AssignLiteral("descending");
53 else if (aSortState->direction == nsSortState_ascending)
54 direction.AssignLiteral("ascending");
55 aNode->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
56 direction, true);
58 // for trees, also set the sort info on the currently sorted column
59 if (aNode->NodeInfo()->Equals(nsGkAtoms::tree, kNameSpaceID_XUL)) {
60 if (aSortState->sortKeys.Count() >= 1) {
61 nsAutoString sortkey;
62 aSortState->sortKeys[0]->ToString(sortkey);
63 SetSortColumnHints(aNode, sortkey, direction);
64 }
65 }
66 }
68 void
69 XULSortServiceImpl::SetSortColumnHints(nsIContent *content,
70 const nsAString &sortResource,
71 const nsAString &sortDirection)
72 {
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();
76 child;
77 child = child->GetNextSibling()) {
78 if (child->IsXUL()) {
79 nsIAtom *tag = child->Tag();
81 if (tag == nsGkAtoms::treecols) {
82 SetSortColumnHints(child, sortResource, sortDirection);
83 } else if (tag == nsGkAtoms::treecol) {
84 nsAutoString value;
85 child->GetAttr(kNameSpaceID_None, nsGkAtoms::sort, value);
86 // also check the resource attribute for older code
87 if (value.IsEmpty())
88 child->GetAttr(kNameSpaceID_None, nsGkAtoms::resource, value);
89 if (value == sortResource) {
90 child->SetAttr(kNameSpaceID_None, nsGkAtoms::sortActive,
91 NS_LITERAL_STRING("true"), true);
92 child->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
93 sortDirection, true);
94 // Note: don't break out of loop; want to set/unset
95 // attribs on ALL sort columns
96 } else if (!value.IsEmpty()) {
97 child->UnsetAttr(kNameSpaceID_None, nsGkAtoms::sortActive,
98 true);
99 child->UnsetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
100 true);
101 }
102 }
103 }
104 }
105 }
107 nsresult
108 XULSortServiceImpl::GetItemsToSort(nsIContent *aContainer,
109 nsSortState* aSortState,
110 nsTArray<contentSortInfo>& aSortItems)
111 {
112 // if there is a template attached to the sort node, use the builder to get
113 // the items to be sorted
114 nsCOMPtr<nsIDOMXULElement> element = do_QueryInterface(aContainer);
115 if (element) {
116 nsCOMPtr<nsIXULTemplateBuilder> builder;
117 element->GetBuilder(getter_AddRefs(builder));
119 if (builder) {
120 nsresult rv = builder->GetQueryProcessor(getter_AddRefs(aSortState->processor));
121 if (NS_FAILED(rv) || !aSortState->processor)
122 return rv;
124 return GetTemplateItemsToSort(aContainer, builder, aSortState, aSortItems);
125 }
126 }
128 // if there is no template builder, just get the children. For trees,
129 // get the treechildren element as use that as the parent
130 nsCOMPtr<nsIContent> treechildren;
131 if (aContainer->NodeInfo()->Equals(nsGkAtoms::tree, kNameSpaceID_XUL)) {
132 nsXULContentUtils::FindChildByTag(aContainer,
133 kNameSpaceID_XUL,
134 nsGkAtoms::treechildren,
135 getter_AddRefs(treechildren));
136 if (!treechildren)
137 return NS_OK;
139 aContainer = treechildren;
140 }
142 for (nsIContent* child = aContainer->GetFirstChild();
143 child;
144 child = child->GetNextSibling()) {
145 contentSortInfo* cinfo = aSortItems.AppendElement();
146 if (!cinfo)
147 return NS_ERROR_OUT_OF_MEMORY;
149 cinfo->content = child;
150 }
152 return NS_OK;
153 }
156 nsresult
157 XULSortServiceImpl::GetTemplateItemsToSort(nsIContent* aContainer,
158 nsIXULTemplateBuilder* aBuilder,
159 nsSortState* aSortState,
160 nsTArray<contentSortInfo>& aSortItems)
161 {
162 for (nsIContent* child = aContainer->GetFirstChild();
163 child;
164 child = child->GetNextSibling()) {
166 nsCOMPtr<nsIDOMElement> childnode = do_QueryInterface(child);
168 nsCOMPtr<nsIXULTemplateResult> result;
169 nsresult rv = aBuilder->GetResultForContent(childnode, getter_AddRefs(result));
170 NS_ENSURE_SUCCESS(rv, rv);
172 if (result) {
173 contentSortInfo* cinfo = aSortItems.AppendElement();
174 if (!cinfo)
175 return NS_ERROR_OUT_OF_MEMORY;
177 cinfo->content = child;
178 cinfo->result = result;
179 }
180 else if (aContainer->Tag() != nsGkAtoms::_template) {
181 rv = GetTemplateItemsToSort(child, aBuilder, aSortState, aSortItems);
182 NS_ENSURE_SUCCESS(rv, rv);
183 }
184 }
186 return NS_OK;
187 }
189 int
190 testSortCallback(const void *data1, const void *data2, void *privateData)
191 {
192 /// Note: testSortCallback is a small C callback stub for NS_QuickSort
193 contentSortInfo *left = (contentSortInfo *)data1;
194 contentSortInfo *right = (contentSortInfo *)data2;
195 nsSortState* sortState = (nsSortState *)privateData;
197 int32_t sortOrder = 0;
199 if (sortState->direction == nsSortState_natural && sortState->processor) {
200 // sort in natural order
201 sortState->processor->CompareResults(left->result, right->result,
202 nullptr, sortState->sortHints, &sortOrder);
203 }
204 else {
205 int32_t length = sortState->sortKeys.Count();
206 for (int32_t t = 0; t < length; t++) {
207 // for templates, use the query processor to do sorting
208 if (sortState->processor) {
209 sortState->processor->CompareResults(left->result, right->result,
210 sortState->sortKeys[t],
211 sortState->sortHints, &sortOrder);
212 if (sortOrder)
213 break;
214 }
215 else {
216 // no template, so just compare attributes. Ignore namespaces for now.
217 nsAutoString leftstr, rightstr;
218 left->content->GetAttr(kNameSpaceID_None, sortState->sortKeys[t], leftstr);
219 right->content->GetAttr(kNameSpaceID_None, sortState->sortKeys[t], rightstr);
221 sortOrder = XULSortServiceImpl::CompareValues(leftstr, rightstr, sortState->sortHints);
222 }
223 }
224 }
226 if (sortState->direction == nsSortState_descending)
227 sortOrder = -sortOrder;
229 return sortOrder;
230 }
232 nsresult
233 XULSortServiceImpl::SortContainer(nsIContent *aContainer, nsSortState* aSortState)
234 {
235 nsTArray<contentSortInfo> items;
236 nsresult rv = GetItemsToSort(aContainer, aSortState, items);
237 NS_ENSURE_SUCCESS(rv, rv);
239 uint32_t numResults = items.Length();
240 if (!numResults)
241 return NS_OK;
243 uint32_t i;
245 // inbetweenSeparatorSort sorts the items between separators independently
246 if (aSortState->inbetweenSeparatorSort) {
247 uint32_t startIndex = 0;
248 for (i = 0; i < numResults; i++) {
249 if (i > startIndex + 1) {
250 nsAutoString type;
251 items[i].result->GetType(type);
252 if (type.EqualsLiteral("separator")) {
253 if (aSortState->invertSort)
254 InvertSortInfo(items, startIndex, i - startIndex);
255 else
256 NS_QuickSort((void *)(items.Elements() + startIndex), i - startIndex,
257 sizeof(contentSortInfo), testSortCallback, (void*)aSortState);
259 startIndex = i + 1;
260 }
261 }
262 }
264 if (i > startIndex + 1) {
265 if (aSortState->invertSort)
266 InvertSortInfo(items, startIndex, i - startIndex);
267 else
268 NS_QuickSort((void *)(items.Elements() + startIndex), i - startIndex,
269 sizeof(contentSortInfo), testSortCallback, (void*)aSortState);
270 }
271 } else {
272 // if the items are just being inverted, that is, just switching between
273 // ascending and descending, just reverse the list.
274 if (aSortState->invertSort)
275 InvertSortInfo(items, 0, numResults);
276 else
277 NS_QuickSort((void *)items.Elements(), numResults,
278 sizeof(contentSortInfo), testSortCallback, (void*)aSortState);
279 }
281 // first remove the items from the old positions
282 for (i = 0; i < numResults; i++) {
283 nsIContent* child = items[i].content;
284 nsIContent* parent = child->GetParent();
286 if (parent) {
287 // remember the parent so that it can be reinserted back
288 // into the same parent. This is necessary as multiple rules
289 // may generate results which get placed in different locations.
290 items[i].parent = parent;
291 int32_t index = parent->IndexOf(child);
292 parent->RemoveChildAt(index, true);
293 }
294 }
296 // now add the items back in sorted order
297 for (i = 0; i < numResults; i++)
298 {
299 nsIContent* child = items[i].content;
300 nsIContent* parent = items[i].parent;
301 if (parent) {
302 parent->AppendChildTo(child, true);
304 // if it's a container in a tree or menu, find its children,
305 // and sort those also
306 if (!child->AttrValueIs(kNameSpaceID_None, nsGkAtoms::container,
307 nsGkAtoms::_true, eCaseMatters))
308 continue;
310 for (nsIContent* grandchild = child->GetFirstChild();
311 grandchild;
312 grandchild = grandchild->GetNextSibling()) {
313 nsINodeInfo *ni = grandchild->NodeInfo();
314 nsIAtom *localName = ni->NameAtom();
315 if (ni->NamespaceID() == kNameSpaceID_XUL &&
316 (localName == nsGkAtoms::treechildren ||
317 localName == nsGkAtoms::menupopup)) {
318 SortContainer(grandchild, aSortState);
319 }
320 }
321 }
322 }
324 return NS_OK;
325 }
327 nsresult
328 XULSortServiceImpl::InvertSortInfo(nsTArray<contentSortInfo>& aData,
329 int32_t aStart, int32_t aNumItems)
330 {
331 if (aNumItems > 1) {
332 // reverse the items in the array starting from aStart
333 int32_t upPoint = (aNumItems + 1) / 2 + aStart;
334 int32_t downPoint = (aNumItems - 2) / 2 + aStart;
335 int32_t half = aNumItems / 2;
336 while (half-- > 0) {
337 aData[downPoint--].swap(aData[upPoint++]);
338 }
339 }
340 return NS_OK;
341 }
343 nsresult
344 XULSortServiceImpl::InitializeSortState(nsIContent* aRootElement,
345 nsIContent* aContainer,
346 const nsAString& aSortKey,
347 const nsAString& aSortHints,
348 nsSortState* aSortState)
349 {
350 // used as an optimization for the content builder
351 if (aContainer != aSortState->lastContainer.get()) {
352 aSortState->lastContainer = aContainer;
353 aSortState->lastWasFirst = false;
354 aSortState->lastWasLast = false;
355 }
357 // The attributes allowed are either:
358 // sort="key1 key2 ..."
359 // or sortResource="key1" sortResource2="key2"
360 // The latter is for backwards compatibility, and is equivalent to concatenating
361 // both values in the sort attribute
362 nsAutoString sort(aSortKey);
363 aSortState->sortKeys.Clear();
364 if (sort.IsEmpty()) {
365 nsAutoString sortResource, sortResource2;
366 aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sortResource, sortResource);
367 if (!sortResource.IsEmpty()) {
368 nsCOMPtr<nsIAtom> sortkeyatom = do_GetAtom(sortResource);
369 aSortState->sortKeys.AppendObject(sortkeyatom);
370 sort.Append(sortResource);
372 aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sortResource2, sortResource2);
373 if (!sortResource2.IsEmpty()) {
374 nsCOMPtr<nsIAtom> sortkeyatom2 = do_GetAtom(sortResource2);
375 aSortState->sortKeys.AppendObject(sortkeyatom2);
376 sort.AppendLiteral(" ");
377 sort.Append(sortResource2);
378 }
379 }
380 }
381 else {
382 nsWhitespaceTokenizer tokenizer(sort);
383 while (tokenizer.hasMoreTokens()) {
384 nsCOMPtr<nsIAtom> keyatom = do_GetAtom(tokenizer.nextToken());
385 NS_ENSURE_TRUE(keyatom, NS_ERROR_OUT_OF_MEMORY);
386 aSortState->sortKeys.AppendObject(keyatom);
387 }
388 }
390 aSortState->sort.Assign(sort);
391 aSortState->direction = nsSortState_natural;
393 bool noNaturalState = false;
394 nsWhitespaceTokenizer tokenizer(aSortHints);
395 while (tokenizer.hasMoreTokens()) {
396 const nsDependentSubstring& token(tokenizer.nextToken());
397 if (token.EqualsLiteral("comparecase"))
398 aSortState->sortHints |= nsIXULSortService::SORT_COMPARECASE;
399 else if (token.EqualsLiteral("integer"))
400 aSortState->sortHints |= nsIXULSortService::SORT_INTEGER;
401 else if (token.EqualsLiteral("descending"))
402 aSortState->direction = nsSortState_descending;
403 else if (token.EqualsLiteral("ascending"))
404 aSortState->direction = nsSortState_ascending;
405 else if (token.EqualsLiteral("twostate"))
406 noNaturalState = true;
407 }
409 // if the twostate flag was set, the natural order is skipped and only
410 // ascending and descending are allowed
411 if (aSortState->direction == nsSortState_natural && noNaturalState) {
412 aSortState->direction = nsSortState_ascending;
413 }
415 // set up sort order info
416 aSortState->invertSort = false;
418 nsAutoString existingsort;
419 aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sort, existingsort);
420 nsAutoString existingsortDirection;
421 aRootElement->GetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection, existingsortDirection);
423 // if just switching direction, set the invertSort flag
424 if (sort.Equals(existingsort)) {
425 if (aSortState->direction == nsSortState_descending) {
426 if (existingsortDirection.EqualsLiteral("ascending"))
427 aSortState->invertSort = true;
428 }
429 else if (aSortState->direction == nsSortState_ascending &&
430 existingsortDirection.EqualsLiteral("descending")) {
431 aSortState->invertSort = true;
432 }
433 }
435 // sort items between separators independently
436 aSortState->inbetweenSeparatorSort =
437 aRootElement->AttrValueIs(kNameSpaceID_None, nsGkAtoms::sortSeparators,
438 nsGkAtoms::_true, eCaseMatters);
440 // sort static content (non template generated nodes) after generated content
441 aSortState->sortStaticsLast = aRootElement->AttrValueIs(kNameSpaceID_None,
442 nsGkAtoms::sortStaticsLast,
443 nsGkAtoms::_true, eCaseMatters);
445 aSortState->initialized = true;
447 return NS_OK;
448 }
450 int32_t
451 XULSortServiceImpl::CompareValues(const nsAString& aLeft,
452 const nsAString& aRight,
453 uint32_t aSortHints)
454 {
455 if (aSortHints & SORT_INTEGER) {
456 nsresult err;
457 int32_t leftint = PromiseFlatString(aLeft).ToInteger(&err);
458 if (NS_SUCCEEDED(err)) {
459 int32_t rightint = PromiseFlatString(aRight).ToInteger(&err);
460 if (NS_SUCCEEDED(err)) {
461 return leftint - rightint;
462 }
463 }
464 // if they aren't integers, just fall through and compare strings
465 }
467 if (aSortHints & SORT_COMPARECASE) {
468 return ::Compare(aLeft, aRight);
469 }
471 nsICollation* collation = nsXULContentUtils::GetCollation();
472 if (collation) {
473 int32_t result;
474 collation->CompareString(nsICollation::kCollationCaseInSensitive,
475 aLeft, aRight, &result);
476 return result;
477 }
479 return ::Compare(aLeft, aRight, nsCaseInsensitiveStringComparator());
480 }
482 NS_IMETHODIMP
483 XULSortServiceImpl::Sort(nsIDOMNode* aNode,
484 const nsAString& aSortKey,
485 const nsAString& aSortHints)
486 {
487 // get root content node
488 nsCOMPtr<nsIContent> sortNode = do_QueryInterface(aNode);
489 if (!sortNode)
490 return NS_ERROR_FAILURE;
492 nsSortState sortState;
493 nsresult rv = InitializeSortState(sortNode, sortNode,
494 aSortKey, aSortHints, &sortState);
495 NS_ENSURE_SUCCESS(rv, rv);
497 // store sort info in attributes on content
498 SetSortHints(sortNode, &sortState);
499 rv = SortContainer(sortNode, &sortState);
501 sortState.processor = nullptr; // don't hang on to this reference
502 return rv;
503 }
505 nsresult
506 NS_NewXULSortService(nsIXULSortService** sortService)
507 {
508 *sortService = new XULSortServiceImpl();
509 if (!*sortService)
510 return NS_ERROR_OUT_OF_MEMORY;
512 NS_ADDREF(*sortService);
513 return NS_OK;
514 }
