dom/xul/nsXULSortService.cpp

   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 "nsTArray.h"
  22 #include "nsUnicharUtils.h"
  23
  24 #include "mozilla/dom/Element.h"
  25 #include "mozilla/intl/Collator.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(nsGkAtoms::sort, value);
  82       if (value == sortResource) {
  83         child->AsElement()->SetAttr(kNameSpaceID_None, nsGkAtoms::sortActive,
  84                                     u"true"_ns, 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   using mozilla::intl::Collator;
 181   const Collator* collator = nsXULContentUtils::GetCollator();
 182   if (collator) {
 183     return collator->CompareStrings(aLeft, aRight);
 184   }
 185
 186   return ::Compare(aLeft, aRight, nsCaseInsensitiveStringComparator);
 187 }
 188
 189 static int testSortCallback(const void* data1, const void* data2,
 190                             void* privateData) {
 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;
 195
 196   int32_t sortOrder = 0;
 197
 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);
 204     }
 205     if (right->content->IsElement()) {
 206       right->content->AsElement()->GetAttr(sortState->sortKeys[t], rightstr);
 207     }
 208
 209     sortOrder = CompareValues(leftstr, rightstr, sortState->sortHints);
 210   }
 211
 212   if (sortState->direction == nsSortState_descending) sortOrder = -sortOrder;
 213
 214   return sortOrder;
 215 }
 216
 217 /**
 218  * Given a list of sortable items, reverse the list. This is done
 219  * when simply changing the sort direction for the same key.
 220  */
 221 static nsresult InvertSortInfo(nsTArray<contentSortInfo>& aData, int32_t aStart,
 222                                int32_t aNumItems) {
 223   if (aNumItems > 1) {
 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;
 228     while (half-- > 0) {
 229       aData[downPoint--].swap(aData[upPoint++]);
 230     }
 231   }
 232   return NS_OK;
 233 }
 234
 235 /**
 236  * Sort a container using the supplied sort state details.
 237  */
 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);
 242
 243   uint32_t numResults = items.Length();
 244   if (!numResults) return NS_OK;
 245
 246   uint32_t i;
 247
 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);
 252   else
 253     NS_QuickSort((void*)items.Elements(), numResults, sizeof(contentSortInfo),
 254                  testSortCallback, (void*)aSortState);
 255
 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();
 260
 261     if (parent) {
 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);
 267     }
 268   }
 269
 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;
 274     if (parent) {
 275       parent->AppendChildTo(child, true, mozilla::IgnoreErrors());
 276
 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))
 282         continue;
 283
 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);
 292         }
 293       }
 294     }
 295   }
 296
 297   return NS_OK;
 298 }
 299
 300 /**
 301  * Initialize sort information from attributes specified on the container,
 302  * the sort key and sort direction.
 303  *
 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
 309  */
 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;
 319   }
 320
 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);
 329   }
 330
 331   aSortState->sort.Assign(sort);
 332   aSortState->direction = nsSortState_natural;
 333
 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;
 348   }
 349
 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;
 354   }
 355
 356   // set up sort order info
 357   aSortState->invertSort = false;
 358
 359   nsAutoString existingsort;
 360   aRootElement->GetAttr(nsGkAtoms::sort, existingsort);
 361   nsAutoString existingsortDirection;
 362   aRootElement->GetAttr(nsGkAtoms::sortDirection, existingsortDirection);
 363
 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;
 372     }
 373   }
 374
 375   aSortState->initialized = true;
 376
 377   return NS_OK;
 378 }
 379
 380 nsresult mozilla::XULWidgetSort(Element* aNode, const nsAString& aSortKey,
 381                                 const nsAString& aSortHints) {
 382   nsSortState sortState;
 383   nsresult rv =
 384       InitializeSortState(aNode, aNode, aSortKey, aSortHints, &sortState);
 385   NS_ENSURE_SUCCESS(rv, rv);
 386
 387   // store sort info in attributes on content
 388   SetSortHints(aNode, &sortState);
 389   rv = SortContainer(aNode, &sortState);
 390
 391   return rv;
 392 }