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 "nsWhitespaceTokenizer.h"
  18 #include "nsXULSortService.h"
  19 #include "nsXULElement.h"
  20 #include "nsTArray.h"
  21 #include "nsUnicharUtils.h"
  22
  23 #include "mozilla/dom/Element.h"
  24 #include "mozilla/intl/Collator.h"
  25
  26 using mozilla::dom::Element;
  27 const unsigned long SORT_COMPARECASE = 0x0001;
  28 const unsigned long SORT_INTEGER = 0x0100;
  29
  30 enum nsSortState_direction {
  31   nsSortState_descending,
  32   nsSortState_ascending,
  33   nsSortState_natural
  34 };
  35
  36 // the sort state holds info about the current sort
  37 struct MOZ_STACK_CLASS nsSortState final {
  38   bool initialized;
  39   MOZ_INIT_OUTSIDE_CTOR bool invertSort;
  40
  41   uint32_t sortHints;
  42
  43   MOZ_INIT_OUTSIDE_CTOR nsSortState_direction direction;
  44   nsAutoString sort;
  45   nsTArray<RefPtr<nsAtom>> sortKeys;
  46
  47   nsCOMPtr<nsIContent> lastContainer;
  48   MOZ_INIT_OUTSIDE_CTOR bool lastWasFirst, lastWasLast;
  49
  50   nsSortState() : initialized(false), sortHints(0) {}
  51 };
  52
  53 // Information about a particular item to be sorted.
  54 // Its lifecycle is bound to the 'SortContainer' function scope,
  55 // so we can use raw pointers to avoid refcount noise during sorting.
  56 struct contentSortInfo {
  57   nsIContent* content;
  58   nsIContent* parent;
  59 };
  60
  61 /**
  62  * Set sortActive and sortDirection attributes on a tree column when a sort
  63  * is done. The column to change is the one with a sort attribute that
  64  * matches the sort key. The sort attributes are removed from the other
  65  * columns.
  66  */
  67 static void SetSortColumnHints(nsIContent* content,
  68                                const nsAString& sortResource,
  69                                const nsAString& sortDirection) {
  70   // set sort info on current column. This ensures that the
  71   // column header sort indicator is updated properly.
  72   for (nsIContent* child = content->GetFirstChild(); child;
  73        child = child->GetNextSibling()) {
  74     if (child->IsXULElement(nsGkAtoms::treecols)) {
  75       SetSortColumnHints(child, sortResource, sortDirection);
  76     } else if (child->IsXULElement(nsGkAtoms::treecol)) {
  77       nsAutoString value;
  78       child->AsElement()->GetAttr(nsGkAtoms::sort, value);
  79       if (value == sortResource) {
  80         child->AsElement()->SetAttr(kNameSpaceID_None, nsGkAtoms::sortActive,
  81                                     u"true"_ns, true);
  82
  83         child->AsElement()->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection,
  84                                     sortDirection, true);
  85         // Note: don't break out of loop; want to set/unset
  86         // attribs on ALL sort columns
  87       } else if (!value.IsEmpty()) {
  88         child->AsElement()->UnsetAttr(kNameSpaceID_None, nsGkAtoms::sortActive,
  89                                       true);
  90         child->AsElement()->UnsetAttr(kNameSpaceID_None,
  91                                       nsGkAtoms::sortDirection, true);
  92       }
  93     }
  94   }
  95 }
  96
  97 /**
  98  * Set sort and sortDirection attributes when a sort is done.
  99  */
 100 static void SetSortHints(Element* aElement, nsSortState* aSortState) {
 101   // set sort and sortDirection attributes when is sort is done
 102   aElement->SetAttr(kNameSpaceID_None, nsGkAtoms::sort, aSortState->sort, true);
 103
 104   nsAutoString direction;
 105   if (aSortState->direction == nsSortState_descending)
 106     direction.AssignLiteral("descending");
 107   else if (aSortState->direction == nsSortState_ascending)
 108     direction.AssignLiteral("ascending");
 109   aElement->SetAttr(kNameSpaceID_None, nsGkAtoms::sortDirection, direction,
 110                     true);
 111
 112   // for trees, also set the sort info on the currently sorted column
 113   if (aElement->IsXULElement(nsGkAtoms::tree)) {
 114     if (aSortState->sortKeys.Length() >= 1) {
 115       nsAutoString sortkey;
 116       aSortState->sortKeys[0]->ToString(sortkey);
 117       SetSortColumnHints(aElement, sortkey, direction);
 118     }
 119   }
 120 }
 121
 122 /**
 123  * Determine the list of items which need to be sorted. This is determined
 124  * in the following way:
 125  *   - for elements that have a content builder, get its list of generated
 126  *     results
 127  *   - otherwise, for trees, get the child treeitems
 128  *   - otherwise, get the direct children
 129  */
 130 static nsresult GetItemsToSort(nsIContent* aContainer,
 131                                nsTArray<contentSortInfo>& aSortItems) {
 132   // Get the children. For trees, get the treechildren element and
 133   // use that as the parent
 134   RefPtr<Element> treechildren;
 135   if (aContainer->IsXULElement(nsGkAtoms::tree)) {
 136     nsXULContentUtils::FindChildByTag(aContainer, kNameSpaceID_XUL,
 137                                       nsGkAtoms::treechildren,
 138                                       getter_AddRefs(treechildren));
 139     if (!treechildren) return NS_OK;
 140
 141     aContainer = treechildren;
 142   }
 143
 144   for (nsIContent* child = aContainer->GetFirstChild(); child;
 145        child = child->GetNextSibling()) {
 146     contentSortInfo* cinfo = aSortItems.AppendElement();
 147     if (!cinfo) return NS_ERROR_OUT_OF_MEMORY;
 148
 149     cinfo->content = child;
 150   }
 151
 152   return NS_OK;
 153 }
 154
 155 /**
 156  * Compares aLeft and aRight and returns < 0, 0, or > 0. The sort
 157  * hints are checked for case matching and integer sorting.
 158  */
 159 static int32_t CompareValues(const nsAString& aLeft, const nsAString& aRight,
 160                              uint32_t aSortHints) {
 161   if (aSortHints & SORT_INTEGER) {
 162     nsresult err;
 163     int32_t leftint = PromiseFlatString(aLeft).ToInteger(&err);
 164     if (NS_SUCCEEDED(err)) {
 165       int32_t rightint = PromiseFlatString(aRight).ToInteger(&err);
 166       if (NS_SUCCEEDED(err)) {
 167         return leftint - rightint;
 168       }
 169     }
 170     // if they aren't integers, just fall through and compare strings
 171   }
 172
 173   if (aSortHints & SORT_COMPARECASE) {
 174     return ::Compare(aLeft, aRight);
 175   }
 176
 177   using mozilla::intl::Collator;
 178   const Collator* collator = nsXULContentUtils::GetCollator();
 179   if (collator) {
 180     return collator->CompareStrings(aLeft, aRight);
 181   }
 182
 183   return ::Compare(aLeft, aRight, nsCaseInsensitiveStringComparator);
 184 }
 185
 186 static int testSortCallback(const contentSortInfo& left,
 187                             const contentSortInfo& right,
 188                             nsSortState& sortState) {
 189   int32_t sortOrder = 0;
 190
 191   size_t length = sortState.sortKeys.Length();
 192   for (size_t t = 0; t < length; t++) {
 193     // compare attributes. Ignore namespaces for now.
 194     nsAutoString leftstr, rightstr;
 195     if (left.content->IsElement()) {
 196       left.content->AsElement()->GetAttr(sortState.sortKeys[t], leftstr);
 197     }
 198     if (right.content->IsElement()) {
 199       right.content->AsElement()->GetAttr(sortState.sortKeys[t], rightstr);
 200     }
 201
 202     sortOrder = CompareValues(leftstr, rightstr, sortState.sortHints);
 203   }
 204
 205   if (sortState.direction == nsSortState_descending) sortOrder = -sortOrder;
 206
 207   return sortOrder;
 208 }
 209
 210 /**
 211  * Given a list of sortable items, reverse the list. This is done
 212  * when simply changing the sort direction for the same key.
 213  */
 214 static nsresult InvertSortInfo(nsTArray<contentSortInfo>& aData, int32_t aStart,
 215                                int32_t aNumItems) {
 216   if (aNumItems > 1) {
 217     // reverse the items in the array starting from aStart
 218     int32_t upPoint = (aNumItems + 1) / 2 + aStart;
 219     int32_t downPoint = (aNumItems - 2) / 2 + aStart;
 220     int32_t half = aNumItems / 2;
 221     while (half-- > 0) {
 222       std::swap(aData[downPoint--], aData[upPoint++]);
 223     }
 224   }
 225   return NS_OK;
 226 }
 227
 228 /**
 229  * Sort a container using the supplied sort state details.
 230  */
 231 static nsresult SortContainer(nsIContent* aContainer, nsSortState& aSortState) {
 232   nsTArray<contentSortInfo> items;
 233   nsresult rv = GetItemsToSort(aContainer, items);
 234   NS_ENSURE_SUCCESS(rv, rv);
 235
 236   uint32_t numResults = items.Length();
 237   if (!numResults) return NS_OK;
 238
 239   uint32_t i;
 240
 241   // if the items are just being inverted, that is, just switching between
 242   // ascending and descending, just reverse the list.
 243   if (aSortState.invertSort) {
 244     InvertSortInfo(items, 0, numResults);
 245   } else {
 246     items.Sort([&aSortState](auto left, auto right) {
 247       return testSortCallback(left, right, aSortState);
 248     });
 249   }
 250
 251   // first remove the items from the old positions
 252   for (i = 0; i < numResults; i++) {
 253     nsIContent* child = items[i].content;
 254     nsIContent* parent = child->GetParent();
 255
 256     if (parent) {
 257       // remember the parent so that it can be reinserted back
 258       // into the same parent. This is necessary as multiple rules
 259       // may generate results which get placed in different locations.
 260       items[i].parent = parent;
 261       parent->RemoveChildNode(child, true);
 262     }
 263   }
 264
 265   // now add the items back in sorted order
 266   for (i = 0; i < numResults; i++) {
 267     nsIContent* child = items[i].content;
 268     nsIContent* parent = items[i].parent;
 269     if (parent) {
 270       parent->AppendChildTo(child, true, mozilla::IgnoreErrors());
 271
 272       // if it's a container in a tree or menu, find its children,
 273       // and sort those also
 274       if (!child->IsElement() || !child->AsElement()->AttrValueIs(
 275                                      kNameSpaceID_None, nsGkAtoms::container,
 276                                      nsGkAtoms::_true, eCaseMatters))
 277         continue;
 278
 279       for (nsIContent* grandchild = child->GetFirstChild(); grandchild;
 280            grandchild = grandchild->GetNextSibling()) {
 281         mozilla::dom::NodeInfo* ni = grandchild->NodeInfo();
 282         nsAtom* localName = ni->NameAtom();
 283         if (ni->NamespaceID() == kNameSpaceID_XUL &&
 284             (localName == nsGkAtoms::treechildren ||
 285              localName == nsGkAtoms::menupopup)) {
 286           SortContainer(grandchild, aSortState);
 287         }
 288       }
 289     }
 290   }
 291
 292   return NS_OK;
 293 }
 294
 295 /**
 296  * Initialize sort information from attributes specified on the container,
 297  * the sort key and sort direction.
 298  *
 299  * @param aRootElement the element that contains sort attributes
 300  * @param aContainer the container to sort, usually equal to aRootElement
 301  * @param aSortKey space separated list of sort keys
 302  * @param aSortDirection direction to sort in
 303  * @param aSortState structure filled in with sort data
 304  */
 305 static nsresult InitializeSortState(Element* aRootElement, Element* aContainer,
 306                                     const nsAString& aSortKey,
 307                                     const nsAString& aSortHints,
 308                                     nsSortState* aSortState) {
 309   // used as an optimization for the content builder
 310   if (aContainer != aSortState->lastContainer.get()) {
 311     aSortState->lastContainer = aContainer;
 312     aSortState->lastWasFirst = false;
 313     aSortState->lastWasLast = false;
 314   }
 315
 316   // The sort attribute is of the form: sort="key1 key2 ..."
 317   nsAutoString sort(aSortKey);
 318   aSortState->sortKeys.Clear();
 319   nsWhitespaceTokenizer tokenizer(sort);
 320   while (tokenizer.hasMoreTokens()) {
 321     RefPtr<nsAtom> keyatom = NS_Atomize(tokenizer.nextToken());
 322     NS_ENSURE_TRUE(keyatom, NS_ERROR_OUT_OF_MEMORY);
 323     aSortState->sortKeys.AppendElement(keyatom);
 324   }
 325
 326   aSortState->sort.Assign(sort);
 327   aSortState->direction = nsSortState_natural;
 328
 329   bool noNaturalState = false;
 330   nsWhitespaceTokenizer hintsTokenizer(aSortHints);
 331   while (hintsTokenizer.hasMoreTokens()) {
 332     const nsDependentSubstring& token(hintsTokenizer.nextToken());
 333     if (token.EqualsLiteral("comparecase"))
 334       aSortState->sortHints |= SORT_COMPARECASE;
 335     else if (token.EqualsLiteral("integer"))
 336       aSortState->sortHints |= SORT_INTEGER;
 337     else if (token.EqualsLiteral("descending"))
 338       aSortState->direction = nsSortState_descending;
 339     else if (token.EqualsLiteral("ascending"))
 340       aSortState->direction = nsSortState_ascending;
 341     else if (token.EqualsLiteral("twostate"))
 342       noNaturalState = true;
 343   }
 344
 345   // if the twostate flag was set, the natural order is skipped and only
 346   // ascending and descending are allowed
 347   if (aSortState->direction == nsSortState_natural && noNaturalState) {
 348     aSortState->direction = nsSortState_ascending;
 349   }
 350
 351   // set up sort order info
 352   aSortState->invertSort = false;
 353
 354   nsAutoString existingsort;
 355   aRootElement->GetAttr(nsGkAtoms::sort, existingsort);
 356   nsAutoString existingsortDirection;
 357   aRootElement->GetAttr(nsGkAtoms::sortDirection, existingsortDirection);
 358
 359   // if just switching direction, set the invertSort flag
 360   if (sort.Equals(existingsort)) {
 361     if (aSortState->direction == nsSortState_descending) {
 362       if (existingsortDirection.EqualsLiteral("ascending"))
 363         aSortState->invertSort = true;
 364     } else if (aSortState->direction == nsSortState_ascending &&
 365                existingsortDirection.EqualsLiteral("descending")) {
 366       aSortState->invertSort = true;
 367     }
 368   }
 369
 370   aSortState->initialized = true;
 371
 372   return NS_OK;
 373 }
 374
 375 nsresult mozilla::XULWidgetSort(Element* aNode, const nsAString& aSortKey,
 376                                 const nsAString& aSortHints) {
 377   nsSortState sortState;
 378   nsresult rv =
 379       InitializeSortState(aNode, aNode, aSortKey, aSortHints, &sortState);
 380   NS_ENSURE_SUCCESS(rv, rv);
 381
 382   // store sort info in attributes on content
 383   SetSortHints(aNode, &sortState);
 384   rv = SortContainer(aNode, sortState);
 385
 386   return rv;
 387 }