tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

nsXULSortService.cpp (13388B)

      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 "nsXULSortService.h"
     11 
     12 #include "mozilla/dom/Element.h"
     13 #include "mozilla/intl/Collator.h"
     14 #include "nsCOMArray.h"
     15 #include "nsCOMPtr.h"
     16 #include "nsGkAtoms.h"
     17 #include "nsIContent.h"
     18 #include "nsNameSpaceManager.h"
     19 #include "nsString.h"
     20 #include "nsTArray.h"
     21 #include "nsUnicharUtils.h"
     22 #include "nsWhitespaceTokenizer.h"
     23 #include "nsXULContentUtils.h"
     24 #include "nsXULElement.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 }