path: root/toolkit/components/places/tests/queries/test_containersQueries_sorting.js

/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
/* vim:set ts=2 sw=2 sts=2 et: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/**
 * Testing behavior of bug 473157
 * "Want to sort history in container view without sorting the containers"
 * and regression bug 488783
 * Tags list no longer sorted (alphabetized).
 * This test is for global testing sorting containers queries.
 */

// Globals and Constants

var resultTypes = [
  {
    value: Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY,
    name: "RESULTS_AS_DATE_QUERY",
  },
  {
    value: Ci.nsINavHistoryQueryOptions.RESULTS_AS_SITE_QUERY,
    name: "RESULTS_AS_SITE_QUERY",
  },
  {
    value: Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY,
    name: "RESULTS_AS_DATE_SITE_QUERY",
  },
  {
    value: Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAGS_ROOT,
    name: "RESULTS_AS_TAGS_ROOT",
  },
];

var sortingModes = [
  {
    value: Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING,
    name: "SORT_BY_TITLE_ASCENDING",
  },
  {
    value: Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_DESCENDING,
    name: "SORT_BY_TITLE_DESCENDING",
  },
  {
    value: Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING,
    name: "SORT_BY_DATE_ASCENDING",
  },
  {
    value: Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING,
    name: "SORT_BY_DATE_DESCENDING",
  },
  {
    value: Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_ASCENDING,
    name: "SORT_BY_DATEADDED_ASCENDING",
  },
  {
    value: Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_DESCENDING,
    name: "SORT_BY_DATEADDED_DESCENDING",
  },
];

// These pages will be added from newest to oldest and from less visited to most
// visited.
var pages = [
  "http://www.mozilla.org/c/",
  "http://www.mozilla.org/a/",
  "http://www.mozilla.org/b/",
  "http://www.mozilla.com/c/",
  "http://www.mozilla.com/a/",
  "http://www.mozilla.com/b/",
];

var tags = ["mozilla", "Development", "test"];

// Test Runner

/**
 * Enumerates all the sequences of the cartesian product of the arrays contained
 * in aSequences.  Examples:
 *
 *   cartProd([[1, 2, 3], ["a", "b"]], callback);
 *   // callback is called 3 * 2 = 6 times with the following arrays:
 *   // [1, "a"], [1, "b"], [2, "a"], [2, "b"], [3, "a"], [3, "b"]
 *
 *   cartProd([["a"], [1, 2, 3], ["X", "Y"]], callback);
 *   // callback is called 1 * 3 * 2 = 6 times with the following arrays:
 *   // ["a", 1, "X"], ["a", 1, "Y"], ["a", 2, "X"], ["a", 2, "Y"],
 *   // ["a", 3, "X"], ["a", 3, "Y"]
 *
 *   cartProd([[1], [2], [3], [4]], callback);
 *   // callback is called 1 * 1 * 1 * 1 = 1 time with the following array:
 *   // [1, 2, 3, 4]
 *
 *   cartProd([], callback);
 *   // callback is 0 times
 *
 *   cartProd([[1, 2, 3, 4]], callback);
 *   // callback is called 4 times with the following arrays:
 *   // [1], [2], [3], [4]
 *
 * @param  aSequences
 *         an array that contains an arbitrary number of arrays
 * @param  aCallback
 *         a function that is passed each sequence of the product as it's
 *         computed
 * @return the total number of sequences in the product
 */
function cartProd(aSequences, aCallback) {
  if (aSequences.length === 0) {
    return 0;
  }

  // For each sequence in aSequences, we maintain a pointer (an array index,
  // really) to the element we're currently enumerating in that sequence
  var seqEltPtrs = aSequences.map(i => 0);

  var numProds = 0;
  var done = false;
  while (!done) {
    numProds++;

    // prod = sequence in product we're currently enumerating
    var prod = [];
    for (var i = 0; i < aSequences.length; i++) {
      prod.push(aSequences[i][seqEltPtrs[i]]);
    }
    aCallback(prod);

    // The next sequence in the product differs from the current one by just a
    // single element.  Determine which element that is.  We advance the
    // "rightmost" element pointer to the "right" by one.  If we move past the
    // end of that pointer's sequence, reset the pointer to the first element
    // in its sequence and then try the sequence to the "left", and so on.

    // seqPtr = index of rightmost input sequence whose element pointer is not
    // past the end of the sequence
    var seqPtr = aSequences.length - 1;
    while (!done) {
      // Advance the rightmost element pointer.
      seqEltPtrs[seqPtr]++;

      // The rightmost element pointer is past the end of its sequence.
      if (seqEltPtrs[seqPtr] >= aSequences[seqPtr].length) {
        seqEltPtrs[seqPtr] = 0;
        seqPtr--;

        // All element pointers are past the ends of their sequences.
        if (seqPtr < 0) {
          done = true;
        }
      } else {
        break;
      }
    }
  }
  return numProds;
}

/**
 * Test a query based on passed-in options.
 *
 * @param aSequence
 *        array of options we will use to query.
 */
function test_query_callback(aSequence) {
  Assert.equal(aSequence.length, 2);
  var resultType = aSequence[0];
  var sortingMode = aSequence[1];
  print(
    "\n\n*** Testing default sorting for resultType (" +
      resultType.name +
      ") and sortingMode (" +
      sortingMode.name +
      ")"
  );

  // Skip invalid combinations sorting queries by none.
  if (
    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAGS_ROOT &&
    (sortingMode.value == Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING ||
      sortingMode.value == Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING)
  ) {
    // This is a bookmark query, we can't sort by visit date.
    sortingMode.value = Ci.nsINavHistoryQueryOptions.SORT_BY_NONE;
  }
  if (
    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY ||
    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_SITE_QUERY ||
    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
  ) {
    // This is an history query, we can't sort by date added.
    if (
      sortingMode.value ==
        Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_ASCENDING ||
      sortingMode.value ==
        Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_DESCENDING
    ) {
      sortingMode.value = Ci.nsINavHistoryQueryOptions.SORT_BY_NONE;
    }
  }

  // Create a new query with required options.
  var query = PlacesUtils.history.getNewQuery();
  var options = PlacesUtils.history.getNewQueryOptions();
  options.resultType = resultType.value;
  options.sortingMode = sortingMode.value;

  // Compare resultset with expectedData.
  var result = PlacesUtils.history.executeQuery(query, options);
  var root = result.root;
  root.containerOpen = true;

  if (
    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY ||
    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
  ) {
    // Date containers are always sorted by date descending.
    check_children_sorting(
      root,
      Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING
    );
  } else {
    check_children_sorting(root, sortingMode.value);
  }

  // Now Check sorting of the first child container.
  var container = root
    .getChild(0)
    .QueryInterface(Ci.nsINavHistoryContainerResultNode);
  container.containerOpen = true;

  if (
    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
  ) {
    // Has more than one level of containers, first we check the sorting of
    // the first level (site containers), those won't inherit sorting...
    check_children_sorting(
      container,
      Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING
    );
    // ...then we check sorting of the contained urls, we can't inherit sorting
    // since the above level does not inherit it, so they will be sorted by
    // title ascending.
    let innerContainer = container
      .getChild(0)
      .QueryInterface(Ci.nsINavHistoryContainerResultNode);
    innerContainer.containerOpen = true;
    check_children_sorting(
      innerContainer,
      Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING
    );
    innerContainer.containerOpen = false;
  } else if (
    resultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAGS_ROOT
  ) {
    // Sorting mode for tag contents is hardcoded for now, to allow for faster
    // duplicates filtering.
    check_children_sorting(
      container,
      Ci.nsINavHistoryQueryOptions.SORT_BY_NONE
    );
  } else {
    check_children_sorting(container, sortingMode.value);
  }

  container.containerOpen = false;
  root.containerOpen = false;

  test_result_sortingMode_change(result, resultType, sortingMode);
}

/**
 * Sets sortingMode on aResult and checks for correct sorting of children.
 * Containers should not change their sorting, while contained uri nodes should.
 *
 * @param aResult
 *        nsINavHistoryResult generated by our query.
 * @param aResultType
 *        required result type.
 * @param aOriginalSortingMode
 *        the sorting mode from query's options.
 */
function test_result_sortingMode_change(
  aResult,
  aResultType,
  aOriginalSortingMode
) {
  var root = aResult.root;
  // Now we set sortingMode on the result and check that containers are not
  // sorted while children are.
  sortingModes.forEach(function sortingModeChecker(aForcedSortingMode) {
    print(
      "\n* Test setting sortingMode (" +
        aForcedSortingMode.name +
        ") " +
        "on result with resultType (" +
        aResultType.name +
        ") " +
        "currently sorted as (" +
        aOriginalSortingMode.name +
        ")"
    );

    aResult.sortingMode = aForcedSortingMode.value;
    root.containerOpen = true;

    if (
      aResultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY ||
      aResultType.value ==
        Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
    ) {
      // Date containers are always sorted by date descending.
      check_children_sorting(
        root,
        Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING
      );
    } else if (
      aResultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_SITE_QUERY &&
      (aOriginalSortingMode.value ==
        Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING ||
        aOriginalSortingMode.value ==
          Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING)
    ) {
      // Site containers don't have a good time property to sort by.
      check_children_sorting(root, Ci.nsINavHistoryQueryOptions.SORT_BY_NONE);
    } else {
      check_children_sorting(root, aOriginalSortingMode.value);
    }

    // Now Check sorting of the first child container.
    var container = root
      .getChild(0)
      .QueryInterface(Ci.nsINavHistoryContainerResultNode);
    container.containerOpen = true;

    if (
      aResultType.value ==
      Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY
    ) {
      // Has more than one level of containers, first we check the sorting of
      // the first level (site containers), those won't be sorted...
      check_children_sorting(
        container,
        Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING
      );
      // ...then we check sorting of the second level of containers, result
      // will sort them through recursiveSort.
      let innerContainer = container
        .getChild(0)
        .QueryInterface(Ci.nsINavHistoryContainerResultNode);
      innerContainer.containerOpen = true;
      check_children_sorting(innerContainer, aForcedSortingMode.value);
      innerContainer.containerOpen = false;
    } else {
      if (
        aResultType.value ==
          Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY ||
        aResultType.value ==
          Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_SITE_QUERY ||
        aResultType.value == Ci.nsINavHistoryQueryOptions.RESULTS_AS_SITE_QUERY
      ) {
        // Date containers are always sorted by date descending.
        check_children_sorting(root, Ci.nsINavHistoryQueryOptions.SORT_BY_NONE);
      } else {
        check_children_sorting(root, aOriginalSortingMode.value);
      }

      // Children should always be sorted.
      check_children_sorting(container, aForcedSortingMode.value);
    }

    container.containerOpen = false;
    root.containerOpen = false;
  });
}

/**
 * Test if children of aRootNode are correctly sorted.
 * @param aRootNode
 *        already opened root node from our query's result.
 * @param aExpectedSortingMode
 *        The sortingMode we expect results to be.
 */
function check_children_sorting(aRootNode, aExpectedSortingMode) {
  var results = [];
  print("Found children:");
  for (let i = 0; i < aRootNode.childCount; i++) {
    results[i] = aRootNode.getChild(i);
    print(i + " " + results[i].title);
  }

  // Helper for case insensitive string comparison.
  function caseInsensitiveStringComparator(a, b) {
    var aLC = a.toLowerCase();
    var bLC = b.toLowerCase();
    if (aLC < bLC) {
      return -1;
    }
    if (aLC > bLC) {
      return 1;
    }
    return 0;
  }

  // Get a comparator based on expected sortingMode.
  var comparator;
  switch (aExpectedSortingMode) {
    case Ci.nsINavHistoryQueryOptions.SORT_BY_NONE:
      comparator = function (a, b) {
        return 0;
      };
      break;
    case Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING:
      comparator = function (a, b) {
        return caseInsensitiveStringComparator(a.title, b.title);
      };
      break;
    case Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_DESCENDING:
      comparator = function (a, b) {
        return -caseInsensitiveStringComparator(a.title, b.title);
      };
      break;
    case Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_ASCENDING:
      comparator = function (a, b) {
        return a.time - b.time;
      };
      break;
    case Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING:
      comparator = function (a, b) {
        return b.time - a.time;
      };
    // fall through - we shouldn't do this, see bug 1572437.
    case Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_ASCENDING:
      comparator = function (a, b) {
        return a.dateAdded - b.dateAdded;
      };
      break;
    case Ci.nsINavHistoryQueryOptions.SORT_BY_DATEADDED_DESCENDING:
      comparator = function (a, b) {
        return b.dateAdded - a.dateAdded;
      };
      break;
    default:
      do_throw("Unknown sorting type: " + aExpectedSortingMode);
  }

  // Make an independent copy of the results array and sort it.
  var sortedResults = results.slice();
  sortedResults.sort(comparator);
  // Actually compare returned children with our sorted array.
  for (let i = 0; i < sortedResults.length; i++) {
    if (sortedResults[i].title != results[i].title) {
      print(
        i +
          " index wrong, expected " +
          sortedResults[i].title +
          " found " +
          results[i].title
      );
    }
    Assert.equal(sortedResults[i].title, results[i].title);
  }
}

// Main

add_task(async function test_containersQueries_sorting() {
  // Add visits, bookmarks and tags to our database.
  var timeInMilliseconds = Date.now();
  var visitCount = 0;
  var dayOffset = 0;
  var visits = [];
  pages.forEach(aPageUrl =>
    visits.push({
      isVisit: true,
      isBookmark: true,
      transType: Ci.nsINavHistoryService.TRANSITION_TYPED,
      uri: aPageUrl,
      title: aPageUrl,
      // subtract 5 hours per iteration, to expose more than one day container.
      lastVisit: (timeInMilliseconds - 18000 * 1000 * dayOffset++) * 1000,
      visitCount: visitCount++,
      isTag: true,
      tagArray: tags,
      isInQuery: true,
    })
  );
  await task_populateDB(visits);

  cartProd([resultTypes, sortingModes], test_query_callback);
});