Fixed file list sorting

Now using a natural sort algorithm that is more consistent between JS
and PHP (although not perfect in some corner cases)

- added OC.Util.naturalSortComparator that uses the same algo that was
  used for the user list
- changed user list and files list to use OC.Util.naturalSortComparator
- removed toLowerCase() and changed the comparator to use
  String.localeCompare()
- added unit tests
- added OC_NaturalSort that is used by OCP\Util::naturalSortCompare()

3 files changed, 206 insertions, 1 deletions

diff --git a/core/js/js.js b/core/js/js.js
index 60f9cc11a58..b6bfa01d0d5 100644
--- a/core/js/js.js
+++ b/core/js/js.js
@@ -1365,8 +1365,56 @@ OC.Util = {
 		// FIXME: likely to break when crossing DST
 		// would be better to use a library like momentJS
 		return new Date(date.getFullYear(), date.getMonth(), date.getDate());
+	},
+
+	_chunkify: function(t) {
+		// Adapted from http://my.opera.com/GreyWyvern/blog/show.dml/1671288
+		var tz = [], x = 0, y = -1, n = 0, code, c;
+
+		while (x < t.length) {
+			c = t.charAt(x);
+			var m = (c === '.' || (c >= '0' && c <= '9'));
+			if (m !== n) {
+				// next chunk
+				y++;
+				tz[y] = '';
+				n = m;
+			}
+			tz[y] += c;
+			x++;
+		}
+		return tz;
+	},
+	/**
+	 * Compare two strings to provide a natural sort
+	 * @param a first string to compare
+	 * @param b second string to compare
+	 * @return -1 if b comes before a, 1 if a comes before b
+	 * or 0 if the strings are identical
+	 */
+	naturalSortCompare: function(a, b) {
+		var aa = OC.Util._chunkify(a);
+		var bb = OC.Util._chunkify(b);
+
+		for (x = 0; aa[x] && bb[x]; x++) {
+			if (aa[x] !== bb[x]) {
+				var aNum = Number(aa[x]), bNum = Number(bb[x]);
+				// note: == is correct here
+				if (aNum == aa[x] && bNum == bb[x]) {
+					return aNum - bNum;
+				} else {
+					// Forcing 'en' locale to match the server-side locale which is
+					// always 'en'.
+					//
+					// Note: This setting isn't supported by all browsers but for the ones
+					// that do there will be more consistency between client-server sorting
+					return aa[x].localeCompare(bb[x], 'en');
+				}
+			}
+		}
+		return aa.length - bb.length;
 	}
-};
+}
 
 /**
  * Utility class for the history API,
diff --git a/core/js/tests/specHelper.js b/core/js/tests/specHelper.js
index 3d208d9ef3f..7745b82a999 100644
--- a/core/js/tests/specHelper.js
+++ b/core/js/tests/specHelper.js
@@ -77,6 +77,8 @@ window.Snap.prototype = {
 	close: function() {}
 };
 
+window.isPhantom = /phantom/i.test(navigator.userAgent);
+
 // global setup for all tests
 (function setupTests() {
 	var fakeServer = null,
diff --git a/core/js/tests/specs/coreSpec.js b/core/js/tests/specs/coreSpec.js
index 166210d0312..265b9deac39 100644
--- a/core/js/tests/specs/coreSpec.js
+++ b/core/js/tests/specs/coreSpec.js
@@ -473,5 +473,160 @@ describe('Core base tests', function() {
 			});
 		});
 	});
+	describe('naturalSortCompare', function() {
+		// cit() will skip tests if running on PhantomJS because it has issues with
+		// localeCompare(). See https://github.com/ariya/phantomjs/issues/11063
+		//
+		// Please make sure to run these tests in Chrome/Firefox manually
+		// to make sure they run.
+		var cit = window.isPhantom?xit:it;
+
+		// must provide the same results as \OC_Util::naturalSortCompare
+		it('sorts alphabetically', function() {
+			var a = [
+				'def',
+				'xyz',
+				'abc'
+			];
+			a.sort(OC.Util.naturalSortCompare);
+			expect(a).toEqual([
+				'abc',
+				'def',
+				'xyz'
+			]);
+		});
+		cit('sorts with different casing', function() {
+			var a = [
+				'aaa',
+				'bbb',
+				'BBB',
+				'AAA'
+			];
+			a.sort(OC.Util.naturalSortCompare);
+			expect(a).toEqual([
+				'aaa',
+				'AAA',
+				'bbb',
+				'BBB'
+			]);
+		});
+		it('sorts with numbers', function() {
+			var a = [
+				'124.txt',
+				'abc1',
+				'123.txt',
+				'abc',
+				'abc2',
+				'def (2).txt',
+				'ghi 10.txt',
+				'abc12',
+				'def.txt',
+				'def (1).txt',
+				'ghi 2.txt',
+				'def (10).txt',
+				'abc10',
+				'def (12).txt',
+				'z',
+				'ghi.txt',
+				'za',
+				'ghi 1.txt',
+				'ghi 12.txt',
+				'zz'
+			];
+			a.sort(OC.Util.naturalSortCompare);
+			expect(a).toEqual([
+				'123.txt',
+				'124.txt',
+				'abc',
+				'abc1',
+				'abc2',
+				'abc10',
+				'abc12',
+				'def.txt',
+				'def (1).txt',
+				'def (2).txt',
+				'def (10).txt',
+				'def (12).txt',
+				'ghi.txt',
+				'ghi 1.txt',
+				'ghi 2.txt',
+				'ghi 10.txt',
+				'ghi 12.txt',
+				'z',
+				'za',
+				'zz'
+			]);
+		});
+		it('sorts with chinese characters', function() {
+			var a = [
+				'十.txt',
+				'一.txt',
+				'二.txt',
+				'十 2.txt',
+				'三.txt',
+				'四.txt',
+				'abc.txt',
+				'五.txt',
+				'七.txt',
+				'八.txt',
+				'九.txt',
+				'六.txt',
+				'十一.txt',
+				'波.txt',
+				'破.txt',
+				'莫.txt',
+				'啊.txt',
+				'123.txt'
+			];
+			a.sort(OC.Util.naturalSortCompare);
+			expect(a).toEqual([
+				'123.txt',
+				'abc.txt',
+				'一.txt',
+				'七.txt',
+				'三.txt',
+				'九.txt',
+				'二.txt',
+				'五.txt',
+				'八.txt',
+				'六.txt',
+				'十.txt',
+				'十 2.txt',
+				'十一.txt',
+				'啊.txt',
+				'四.txt',
+				'波.txt',
+				'破.txt',
+				'莫.txt'
+			]);
+		});
+		cit('sorts with umlauts', function() {
+			var a = [
+				'öh.txt',
+				'Äh.txt',
+				'oh.txt',
+				'Üh 2.txt',
+				'Üh.txt',
+				'ah.txt',
+				'Öh.txt',
+				'uh.txt',
+				'üh.txt',
+				'äh.txt'
+			];
+			a.sort(OC.Util.naturalSortCompare);
+			expect(a).toEqual([
+				'ah.txt',
+				'äh.txt',
+				'Äh.txt',
+				'oh.txt',
+				'öh.txt',
+				'Öh.txt',
+				'uh.txt',
+				'üh.txt',
+				'Üh.txt',
+				'Üh 2.txt'
+			]);
+		});
+	});
 });