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