(#6096) - clean up and reduce memory usage of mapreduce
diff --git a/packages/node_modules/pouchdb-collate/src/index.js b/packages/node_modules/pouchdb-collate/src/index.js
index 049a5fe..cca89b8 100644
--- a/packages/node_modules/pouchdb-collate/src/index.js
+++ b/packages/node_modules/pouchdb-collate/src/index.js
@@ -20,14 +20,11 @@
if ((ai - bi) !== 0) {
return ai - bi;
}
- if (a === null) {
- return 0;
- }
switch (typeof a) {
case 'number':
return a - b;
case 'boolean':
- return a === b ? 0 : (a < b ? -1 : 1);
+ return a < b ? -1 : 1;
case 'string':
return stringCollate(a, b);
}
diff --git a/packages/node_modules/pouchdb-for-coverage/src/index.js b/packages/node_modules/pouchdb-for-coverage/src/index.js
index 51d340a..1fc76a2 100644
--- a/packages/node_modules/pouchdb-for-coverage/src/index.js
+++ b/packages/node_modules/pouchdb-for-coverage/src/index.js
@@ -2,9 +2,11 @@
import ajax from 'pouchdb-ajax';
import utils from './utils';
import errors from './errors';
+import * as collate from 'pouchdb-collate';
PouchDB.ajax = ajax;
PouchDB.utils = utils;
PouchDB.Errors = errors;
+PouchDB.collate = collate;
export default PouchDB;
diff --git a/packages/node_modules/pouchdb-mapreduce/src/index.js b/packages/node_modules/pouchdb-mapreduce/src/index.js
index 0ff29ae..af8b634 100644
--- a/packages/node_modules/pouchdb-mapreduce/src/index.js
+++ b/packages/node_modules/pouchdb-mapreduce/src/index.js
@@ -31,7 +31,7 @@
NotFoundError,
BuiltInError
} from './errors';
-import { Map } from 'pouchdb-collections';
+import { Map, Set } from 'pouchdb-collections';
import Promise from 'pouchdb-promise';
import sum from './sum';
@@ -356,8 +356,8 @@
var metaDocId = '_local/doc_' + docId;
var defaultMetaDoc = {_id: metaDocId, keys: []};
var docData = docIdsToChangesAndEmits.get(docId);
- var indexableKeysToKeyValues = docData.indexableKeysToKeyValues;
- var changes = docData.changes;
+ var indexableKeysToKeyValues = docData[0];
+ var changes = docData[1];
function getMetaDoc() {
if (isGenOne(changes)) {
@@ -379,9 +379,9 @@
});
}
- function processKvDocs(metaDoc, kvDocsRes) {
+ function processKeyValueDocs(metaDoc, kvDocsRes) {
var kvDocs = [];
- var oldKeysMap = {};
+ var oldKeys = new Set();
for (var i = 0, len = kvDocsRes.rows.length; i < len; i++) {
var row = kvDocsRes.rows[i];
@@ -390,24 +390,23 @@
continue;
}
kvDocs.push(doc);
- oldKeysMap[doc._id] = true;
- doc._deleted = !indexableKeysToKeyValues[doc._id];
+ oldKeys.add(doc._id);
+ doc._deleted = !indexableKeysToKeyValues.has(doc._id);
if (!doc._deleted) {
- var keyValue = indexableKeysToKeyValues[doc._id];
+ var keyValue = indexableKeysToKeyValues.get(doc._id);
if ('value' in keyValue) {
doc.value = keyValue.value;
}
}
}
-
- var newKeys = Object.keys(indexableKeysToKeyValues);
+ var newKeys = mapToKeysArray(indexableKeysToKeyValues);
newKeys.forEach(function (key) {
- if (!oldKeysMap[key]) {
+ if (!oldKeys.has(key)) {
// new doc
var kvDoc = {
_id: key
};
- var keyValue = indexableKeysToKeyValues[key];
+ var keyValue = indexableKeysToKeyValues.get(key);
if ('value' in keyValue) {
kvDoc.value = keyValue.value;
}
@@ -422,7 +421,7 @@
return getMetaDoc().then(function (metaDoc) {
return getKeyValueDocs(metaDoc).then(function (kvDocsRes) {
- return processKvDocs(metaDoc, kvDocsRes);
+ return processKeyValueDocs(metaDoc, kvDocsRes);
});
});
}
@@ -505,48 +504,59 @@
style: 'all_docs',
since: currentSeq,
limit: CHANGES_BATCH_SIZE
- }).then(function (response) {
- var results = response.results;
- if (!results.length) {
- return;
- }
- var docIdsToChangesAndEmits = new Map();
- for (var i = 0, l = results.length; i < l; i++) {
- var change = results[i];
- if (change.doc._id[0] !== '_') {
- mapResults = [];
- doc = change.doc;
+ }).then(processBatch);
+ }
- if (!doc._deleted) {
- tryMap(view.sourceDB, mapFun, doc);
- }
- mapResults.sort(sortByKeyThenValue);
+ function processBatch(response) {
+ var results = response.results;
+ if (!results.length) {
+ return;
+ }
+ var docIdsToChangesAndEmits = createDocIdsToChangesAndEmits(results);
+ queue.add(processChange(docIdsToChangesAndEmits, currentSeq));
+ if (results.length < CHANGES_BATCH_SIZE) {
+ return;
+ }
+ return processNextBatch();
+ }
- var indexableKeysToKeyValues = {};
- var lastKey;
- for (var j = 0, jl = mapResults.length; j < jl; j++) {
- var obj = mapResults[j];
- var complexKey = [obj.key, obj.id];
- if (collate(obj.key, lastKey) === 0) {
- complexKey.push(j); // dup key+id, so make it unique
- }
- var indexableKey = toIndexableString(complexKey);
- indexableKeysToKeyValues[indexableKey] = obj;
- lastKey = obj.key;
- }
- docIdsToChangesAndEmits.set(change.doc._id, {
- indexableKeysToKeyValues: indexableKeysToKeyValues,
- changes: change.changes
- });
+ function createDocIdsToChangesAndEmits(results) {
+ var docIdsToChangesAndEmits = new Map();
+ for (var i = 0, len = results.length; i < len; i++) {
+ var change = results[i];
+ if (change.doc._id[0] !== '_') {
+ mapResults = [];
+ doc = change.doc;
+
+ if (!doc._deleted) {
+ tryMap(view.sourceDB, mapFun, doc);
}
- currentSeq = change.seq;
+ mapResults.sort(sortByKeyThenValue);
+
+ var indexableKeysToKeyValues = createIndexableKeysToKeyValues(mapResults);
+ docIdsToChangesAndEmits.set(change.doc._id, [
+ indexableKeysToKeyValues,
+ change.changes
+ ]);
}
- queue.add(processChange(docIdsToChangesAndEmits, currentSeq));
- if (results.length < CHANGES_BATCH_SIZE) {
- return;
+ currentSeq = change.seq;
+ }
+ return docIdsToChangesAndEmits;
+ }
+
+ function createIndexableKeysToKeyValues(mapResults) {
+ var indexableKeysToKeyValues = new Map();
+ var lastKey;
+ for (var i = 0, len = mapResults.length; i < len; i++) {
+ var emittedKeyValue = mapResults[i];
+ var complexKey = [emittedKeyValue.key, emittedKeyValue.id];
+ if (i > 0 && collate(emittedKeyValue.key, lastKey) === 0) {
+ complexKey.push(i); // dup key+id, so make it unique
}
- return processNextBatch();
- });
+ indexableKeysToKeyValues.set(toIndexableString(complexKey), emittedKeyValue);
+ lastKey = emittedKeyValue.key;
+ }
+ return indexableKeysToKeyValues;
}
return processNextBatch().then(function () {
diff --git a/tests/mapreduce/test.mapreduce.js b/tests/mapreduce/test.mapreduce.js
index abb22fa..a69ed49 100644
--- a/tests/mapreduce/test.mapreduce.js
+++ b/tests/mapreduce/test.mapreduce.js
@@ -426,6 +426,505 @@
});
});
+ it('Test complex key collation', function () {
+ var map = function () {
+ emit(null);
+ emit(false);
+ emit(true);
+ emit(1);
+ emit(2);
+ emit(3);
+ emit(4);
+ emit("a");
+ emit("aa");
+ emit("b");
+ emit("ba");
+ emit("bb");
+ emit(["a"]);
+ emit(["b"]);
+ emit(["b","c"]);
+ emit(["b","c","a"]);
+ emit(["b","d"]);
+ emit(["b","d","e"]);
+ emit({"a":1});
+ emit({"a":2});
+ emit({"b":1});
+ emit({"b":2});
+ emit({"b":2,"a":1});
+ emit({"b":2,"c":2});
+ };
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, { map: map });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { id: '1', key: null, value: null },
+ { id: '2', key: null, value: null },
+ { id: '1', key: false, value: null },
+ { id: '2', key: false, value: null },
+ { id: '1', key: true, value: null },
+ { id: '2', key: true, value: null },
+ { id: '1', key: 1, value: null },
+ { id: '2', key: 1, value: null },
+ { id: '1', key: 2, value: null },
+ { id: '2', key: 2, value: null },
+ { id: '1', key: 3, value: null },
+ { id: '2', key: 3, value: null },
+ { id: '1', key: 4, value: null },
+ { id: '2', key: 4, value: null },
+ { id: '1', key: 'a', value: null },
+ { id: '2', key: 'a', value: null },
+ { id: '1', key: 'aa', value: null },
+ { id: '2', key: 'aa', value: null },
+ { id: '1', key: 'b', value: null },
+ { id: '2', key: 'b', value: null },
+ { id: '1', key: 'ba', value: null },
+ { id: '2', key: 'ba', value: null },
+ { id: '1', key: 'bb', value: null },
+ { id: '2', key: 'bb', value: null },
+ { id: '1', key: [ 'a' ], value: null },
+ { id: '2', key: [ 'a' ], value: null },
+ { id: '1', key: [ 'b' ], value: null },
+ { id: '2', key: [ 'b' ], value: null },
+ { id: '1', key: [ 'b', 'c' ], value: null },
+ { id: '2', key: [ 'b', 'c' ], value: null },
+ { id: '1', key: [ 'b', 'c', 'a' ], value: null },
+ { id: '2', key: [ 'b', 'c', 'a' ], value: null },
+ { id: '1', key: [ 'b', 'd' ], value: null },
+ { id: '2', key: [ 'b', 'd' ], value: null },
+ { id: '1', key: [ 'b', 'd', 'e' ], value: null },
+ { id: '2', key: [ 'b', 'd', 'e' ], value: null },
+ { id: '1', key: { a: 1 }, value: null },
+ { id: '2', key: { a: 1 }, value: null },
+ { id: '1', key: { a: 2 }, value: null },
+ { id: '2', key: { a: 2 }, value: null },
+ { id: '1', key: { b: 1 }, value: null },
+ { id: '2', key: { b: 1 }, value: null },
+ { id: '1', key: { b: 2 }, value: null },
+ { id: '2', key: { b: 2 }, value: null },
+ { id: '1', key: { b: 2, a: 1 }, value: null },
+ { id: '2', key: { b: 2, a: 1 }, value: null },
+ { id: '1', key: { b: 2, c: 2 }, value: null },
+ { id: '2', key: { b: 2, c: 2 }, value: null }
+ ]);
+ });
+ });
+ });
+
+ it('Test duplicate collation of objects', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit({ a: 'a' }, { b: 'b' });
+ emit({ a: 'a' }, { b: 'b' });
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": { "a": "a" }, "value": { b: 'b' }},
+ { "id": "1", "key": { "a": "a" }, "value": { b: 'b' }},
+ { "id": "2", "key": { "a": "a" }, "value": { b: 'b' }},
+ { "id": "2", "key": { "a": "a" }, "value": { b: 'b' }}
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of undefined/null', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit();
+ emit(null);
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": null, "value": null},
+ { "id": "1", "key": null, "value": null},
+ { "id": "2", "key": null, "value": null},
+ { "id": "2", "key": null, "value": null}
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of null/undefined', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit(null);
+ emit();
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": null, "value": null},
+ { "id": "1", "key": null, "value": null},
+ { "id": "2", "key": null, "value": null},
+ { "id": "2", "key": null, "value": null}
+ ]);
+ });
+ });
+ });
+
+ it('Test duplicate collation of nulls', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit(null);
+ emit(null);
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": null, "value": null},
+ { "id": "1", "key": null, "value": null},
+ { "id": "2", "key": null, "value": null},
+ { "id": "2", "key": null, "value": null}
+ ]);
+ });
+ });
+ });
+
+ it('Test duplicate collation of booleans', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit(true);
+ emit(true);
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": true, "value": null},
+ { "id": "1", "key": true, "value": null},
+ { "id": "2", "key": true, "value": null},
+ { "id": "2", "key": true, "value": null}
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of different objects', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit({ a: 'b' }, { a: 'a' });
+ emit({ a: 'a' }, { b: 'b' });
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": { "a": "a" }, "value": { "b": "b" } },
+ { "id": "2", "key": { "a": "a" }, "value": { "b": "b" } },
+ { "id": "1", "key": { "a": "b" }, "value": { "a": "a" } },
+ { "id": "2", "key": { "a": "b" }, "value": { "a": "a" } }
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of different objects 2', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit({ a: 'b', b: 'c' }, { a: 'a' });
+ emit({ a: 'a' }, { b: 'b' });
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": { "a": "a" }, "value": { "b": "b" } },
+ { "id": "2", "key": { "a": "a" }, "value": { "b": "b" } },
+ { "id": "1", "key": { "a": "b", "b": "c" }, "value": { "a": "a" } },
+ { "id": "2", "key": { "a": "b", "b": "c" }, "value": { "a": "a" } }
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of different objects 3', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit({ a: 'a' }, { b: 'b' });
+ emit({ a: 'b'}, { a: 'a' });
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": { "a": "a" }, "value": { "b": "b" } },
+ { "id": "2", "key": { "a": "a" }, "value": { "b": "b" } },
+ { "id": "1", "key": { "a": "b" }, "value": { "a": "a" } },
+ { "id": "2", "key": { "a": "b" }, "value": { "a": "a" } }
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of different objects 4', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit({ a: 'a'});
+ emit({ b: 'b'});
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": { "a": "a" }, "value": null },
+ { "id": "2", "key": { "a": "a" }, "value": null },
+ { "id": "1", "key": { "b": "b" }, "value": null },
+ { "id": "2", "key": { "b": "b" }, "value": null }
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of different objects 5', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit({ a: 'a'});
+ emit({ a: 'a', b: 'b'});
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": { "a": "a" }, "value": null },
+ { "id": "2", "key": { "a": "a" }, "value": null },
+ { "id": "1", "key": { "a": "a", "b": "b" }, "value": null },
+ { "id": "2", "key": { "a": "a", "b": "b" }, "value": null }
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of different objects 6', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit({ a: 'a'});
+ emit({ a: 'a', b: 'b'});
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": { "a": "a" }, "value": null },
+ { "id": "2", "key": { "a": "a" }, "value": null },
+ { "id": "1", "key": { "a": "a", "b": "b" }, "value": null },
+ { "id": "2", "key": { "a": "a", "b": "b" }, "value": null }
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of different booleans', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit(true);
+ emit(false);
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": false, "value": null },
+ { "id": "2", "key": false, "value": null },
+ { "id": "1", "key": true, "value": null },
+ { "id": "2", "key": true, "value": null }
+ ]);
+ });
+ });
+ });
+
+ it('Test collation of different booleans 2', function () {
+ var db = new PouchDB(dbName);
+ return db.bulkDocs([
+ { _id: '1' },
+ { _id: '2' }
+ ]).then(function () {
+ return createView(db, {
+ map: function () {
+ emit(false);
+ emit(true);
+ }
+ });
+ }).then(function (queryFun) {
+ return db.query(queryFun).then(function (res) {
+ var rows = res.rows.map(function (x) {
+ return {
+ id: x.id,
+ key: x.key,
+ value: x.value
+ };
+ });
+ assert.deepEqual(rows, [
+ { "id": "1", "key": false, "value": null },
+ { "id": "2", "key": false, "value": null },
+ { "id": "1", "key": true, "value": null },
+ { "id": "2", "key": true, "value": null }
+ ]);
+ });
+ });
+ });
+
it("Test joins", function () {
var db = new PouchDB(dbName);
return createView(db, {
diff --git a/tests/unit/test.collate.js b/tests/unit/test.collate.js
new file mode 100644
index 0000000..922821f
--- /dev/null
+++ b/tests/unit/test.collate.js
@@ -0,0 +1,469 @@
+'use strict';
+
+var PouchDB = require('../../packages/node_modules/pouchdb-for-coverage');
+var should = require('chai').should();
+var pouchCollate = PouchDB.collate;
+var collate = pouchCollate.collate;
+var normalizeKey = pouchCollate.normalizeKey;
+var toIndexableString = pouchCollate.toIndexableString;
+var parseIndexableString = pouchCollate.parseIndexableString;
+
+function stringLexCompare(a, b) {
+
+ var aLen = a.length;
+ var bLen = b.length;
+
+ var i;
+ for (i = 0; i < aLen; i++) {
+ if (i === bLen) {
+ // b is shorter substring of a
+ return 1;
+ }
+ var aChar = a.charAt(i);
+ var bChar = b.charAt(i);
+ if (aChar !== bChar) {
+ return aChar < bChar ? -1 : 1;
+ }
+ }
+
+ if (aLen < bLen) {
+ // a is shorter substring of b
+ return -1;
+ }
+
+ return 0;
+}
+
+/*
+ * returns the decimal form for the given integer, i.e. writes
+ * out all the digits (in base-10) instead of using scientific notation
+ */
+function intToDecimalForm(int) {
+
+ var isNeg = int < 0;
+ var result = '';
+
+ do {
+ var remainder = isNeg ? -Math.ceil(int % 10) : Math.floor(int % 10);
+
+ result = remainder + result;
+ int = isNeg ? Math.ceil(int / 10) : Math.floor(int / 10);
+ } while (int);
+
+
+ if (isNeg && result !== '0') {
+ result = '-' + result;
+ }
+
+ return result;
+}
+
+var verifyLexicalKeysSort = function (keys) {
+ var lexical = keys.map(function (key) {
+ return [key, pouchCollate.toIndexableString(key)];
+ });
+ lexical.sort(function (a, b) {
+ return stringLexCompare(a[1], b[1]);
+ });
+ keys.sort(pouchCollate.collate);
+
+ keys.forEach(function (expected, i) {
+ var actual = lexical[i][0];
+
+ should.equal(actual, expected, 'expect ' + JSON.stringify(actual) +
+ ' is ' + JSON.stringify(expected));
+ });
+};
+
+
+describe('test.collate.js', function () {
+ var a = {
+ array: [1, 2, 3],
+ bool: true,
+ string: '123',
+ object: {
+ a: 3,
+ b: 2
+ },
+ number: 1
+ };
+ var b = {
+ array: ['a', 'b'],
+ bool: false,
+ string: 'ab',
+ object: {
+ c: 1,
+ b: 3
+ },
+ number: 2
+ };
+ var c = {
+ object: {
+ a: 1,
+ b: 2,
+ c: 3
+ },
+ array: [1, 2]
+ };
+ it('compare array to itself', function () {
+ collate(a.array, a.array).should.equal(0);
+ collate(b.array, b.array).should.equal(0);
+ collate(c.array, c.array).should.equal(0);
+ });
+ it('compare boolean to itself', function () {
+ collate(a.bool, a.bool).should.equal(0);
+ collate(b.bool, b.bool).should.equal(0);
+ });
+ it('compare string to itself', function () {
+ collate(a.string, a.string).should.equal(0);
+ collate(b.string, b.string).should.equal(0);
+ });
+ it('compare number to itself', function () {
+ collate(a.number, a.number).should.equal(0);
+ collate(b.number, b.number).should.equal(0);
+ });
+ it('compare null to itself', function () {
+ collate(null, null).should.equal(0);
+ });
+ it('compare object to itself', function () {
+ collate(a.object, a.object).should.equal(0);
+ collate(b.object, b.object).should.equal(0);
+ collate(c.object, c.object).should.equal(0);
+ });
+ it('compare array to array', function () {
+ collate(a.array, b.array).should.equal(-1);
+ collate(b.array, a.array).should.equal(1);
+ collate(c.array, b.array).should.equal(-1);
+ collate(b.array, c.array).should.equal(1);
+ collate(a.array, c.array).should.equal(1);
+ collate(c.array, a.array).should.equal(-1);
+ });
+ it('compare array to array', function () {
+ collate([a.array], [b.array]).should.equal(-1);
+ collate([b.array], [a.array]).should.equal(1);
+ });
+ it('compare boolean to boolean', function () {
+ collate(a.bool, b.bool).should.equal(1);
+ collate(b.bool, a.bool).should.equal(-1);
+ });
+ it('compare string to string', function () {
+ collate(a.string, b.string).should.equal(-1);
+ collate(b.string, a.string).should.equal(1);
+ });
+ it('compare number to number', function () {
+ collate(a.number, b.number).should.equal(-1);
+ collate(b.number, a.number).should.equal(1);
+ });
+ it('compare object to object', function () {
+ collate(a.object, b.object).should.equal(-1);
+ collate(b.object, a.object).should.equal(1);
+ collate(c.object, b.object).should.equal(-1);
+ collate(b.object, c.object).should.equal(1);
+ collate(c.object, a.object).should.be.below(0);
+ collate(a.object, c.object).should.be.above(0);
+ });
+ it('objects differing only in num of keys', function () {
+ collate({1: 1}, {1: 1, 2: 2}).should.equal(-1);
+ collate({1: 1, 2: 2}, {1: 1}).should.equal(1);
+ });
+ it('compare number to null', function () {
+ collate(a.number, null).should.be.above(0);
+ });
+ it('compare number to function', function () {
+ collate(a.number, function () {
+ }).should.not.equal(collate(a.number, function () {}));
+ collate(b.number, function () {
+ }).should.not.equal(collate(b.number, function () {}));
+ collate(function () {
+ }, a.number).should.not.equal(collate(function () {}, a.number));
+ collate(function () {
+ }, b.number).should.not.equal(collate(function () {}, b.number));
+ });
+
+});
+
+describe('normalizeKey', function () {
+
+ it('verify key normalizations', function () {
+ var normalizations = [
+ [null, null],
+ [NaN, null],
+ [undefined, null],
+ [Infinity, null],
+ [-Infinity, null],
+ ['', ''],
+ ['foo', 'foo'],
+ ['0', '0'],
+ ['1', '1'],
+ [0, 0],
+ [1, 1],
+ [Number.MAX_VALUE, Number.MAX_VALUE],
+ [new Date('1982-11-30T00:00:00.000Z'), '1982-11-30T00:00:00.000Z'] // Thriller release date
+ ];
+
+ normalizations.forEach(function (normalization) {
+ var original = normalization[0];
+ var expected = normalization[1];
+ var normalized = normalizeKey(original);
+
+ var message = 'check normalization of ' + JSON.stringify(original) +
+ ' to ' + JSON.stringify(expected) +
+ ', got ' + JSON.stringify(normalized);
+ should.equal(normalized, expected, message);
+ });
+ });
+});
+
+describe('indexableString', function () {
+
+ it('verify intToDecimalForm', function () {
+ intToDecimalForm(0).should.equal('0');
+ intToDecimalForm(Number.MIN_VALUE).should.equal('0');
+ intToDecimalForm(-Number.MIN_VALUE).should.equal('0');
+
+ var maxValueStr = '1797693134862316800886484642206468426866682428440286464' +
+ '42228680066046004606080400844208228060084840044686866242482868202680268' +
+ '82040288406280040662242886466688240606642242682208668042640440204020242' +
+ '48802248082808208888442866208026644060866608420408868240026826626668642' +
+ '46642840408646468824200860804260804068888';
+
+ intToDecimalForm(Number.MAX_VALUE).should.equal(maxValueStr);
+ intToDecimalForm(-Number.MAX_VALUE).should.equal('-' + maxValueStr);
+
+ var simpleNums = [-3000, 3000, 322, 2308, -32, -1, 0, 1, 2, -2, -10, 10, -100, 100];
+
+ simpleNums.forEach(function (simpleNum) {
+ intToDecimalForm(simpleNum).should.equal(simpleNum.toString());
+ });
+ });
+
+ it('verify toIndexableString()', function () {
+ var keys = [
+ null,
+ false,
+ true,
+ -Number.MAX_VALUE,
+ -300,
+ -200,
+ -100,
+ -10,
+ -2.5,
+ -2,
+ -1.5,
+ -1,
+ -0.5,
+ -0.0001,
+ -Number.MIN_VALUE,
+ 0,
+ Number.MIN_VALUE,
+ 0.0001,
+ 0.1,
+ 0.5,
+ 1,
+ 1.5,
+ 2,
+ 3,
+ 10,
+ 15,
+ 100,
+ 200,
+ 300,
+ Number.MAX_VALUE,
+ '',
+ '1',
+ '10',
+ '100',
+ '2',
+ '20',
+ '[]',
+ //'é',
+ 'foo',
+ 'mo',
+ 'moe',
+ //'moé',
+ //'moët et chandon',
+ 'moz',
+ 'mozilla',
+ 'mozilla with a super long string see how far it can go',
+ 'mozzy',
+ [],
+ [ null ],
+ [ null, null ],
+ [ null, 'foo' ],
+ [ false ],
+ [ false, 100 ],
+ [ true ],
+ [ true, 100 ],
+ [ 0 ],
+ [ 0, null ],
+ [ 0, 1 ],
+ [ 0, '' ],
+ [ 0, 'foo' ],
+ [ '', '' ],
+ [ 'foo' ],
+ [ 'foo', 1 ],
+ {},
+ { '0': null },
+ { '0': false },
+ { '0': true },
+ { '0': 0 },
+ { '0': 1 },
+ { '0': 'bar' },
+ { '0': 'foo' },
+ { '0': 'foo', '1': false },
+ { '0': 'foo', '1': true },
+ { '0': 'foo', '1': 0 },
+ { '0': 'foo', '1': '0' },
+ { '0': 'foo', '1': 'bar' },
+ { '0': 'quux' },
+ { '1': 'foo' }
+ //{ '1': 'foo', '0' : 'foo' } // key order actually matters, but node sorts them
+ ];
+ verifyLexicalKeysSort(keys);
+ });
+
+ it('verify toIndexableString()', function () {
+ var keys = [
+ ['test', 'test'],
+ ['test\u0000']
+ ];
+ verifyLexicalKeysSort(keys);
+ });
+
+ it('verify deep normalization', function () {
+ var a = {
+ list : [undefined, '1982-11-30T00:00:00.000Z'],
+ obj : {
+ foo: null,
+ date: '1982-11-30T00:00:00.000Z'
+ },
+ brokenList : [undefined, 1, 2, undefined, 3, 4, 5, undefined]
+ };
+ var b = {
+ list : [null, new Date('1982-11-30T00:00:00.000Z')],
+ obj : {
+ foo: NaN,
+ date: new Date('1982-11-30T00:00:00.000Z')
+ },
+ ignoredParam : undefined,
+ brokenList : [null, 1, 2, null, 3, 4, 5, null]
+ };
+
+ // sanity check
+ JSON.stringify(a).should.equal(JSON.stringify(b), 'stringify a,b');
+
+ toIndexableString(a).should.equal(toIndexableString(b), 'string a,b');
+ toIndexableString(a).should.equal(toIndexableString(b), 'string a,a');
+ toIndexableString(b).should.equal(toIndexableString(b), 'string b,b');
+
+ normalizeKey(a).should.deep.equal(normalizeKey(b), 'normalize a,b');
+ normalizeKey(a).should.deep.equal(normalizeKey(a), 'normalize a,a');
+ normalizeKey(b).should.deep.equal(normalizeKey(b), 'normalize b,b');
+
+ collate(a, b).should.equal(0, 'collate a,b');
+ collate(a, a).should.equal(0, 'collate a,a');
+ collate(b, b).should.equal(0, 'collate b,b');
+ });
+
+ it('verify parseIndexableString', function () {
+ var keys = [null, false, true, 0, 1, -1, 9, -9, 10, -10, 0.1, -0.1, -0.01,
+ 100, 200, 20, -20, -200, -30, Number.MAX_VALUE, Number.MIN_VALUE,
+ 'foo', '', '\u0000', '\u0001', '\u0002', [1], {foo: true},
+ {foo: 'bar', 'baz': 'quux', foobaz: {bar: 'bar', baz: 'baz', quux: {foo: 'bar'}}},
+ {foo: {bar: true}},
+ [{foo: 'bar'}, {bar: 'baz'}, {}, ['foo', 'bar', 'baz']],
+ [[[['foo']], [], [['bar']]]],
+ -Number.MAX_VALUE,
+ -300,
+ -200,
+ -100,
+ -10,
+ -2.5,
+ -2,
+ -1.5,
+ -1,
+ -0.5,
+ -0.0001,
+ -Number.MIN_VALUE,
+ 0,
+ Number.MIN_VALUE,
+ 0.0001,
+ 0.1,
+ 0.5,
+ 1,
+ 1.5,
+ 2,
+ 3,
+ 10,
+ 15,
+ 100,
+ 200,
+ 300,
+ Number.MAX_VALUE,
+ '',
+ '1',
+ '10',
+ '100',
+ '2',
+ '20',
+ '[]',
+ //'é',
+ 'foo',
+ 'mo',
+ 'moe',
+ //'moé',
+ //'moët et chandon',
+ 'moz',
+ 'mozilla',
+ 'mozilla with a super long string see how far it can go',
+ 'mozzy',
+ [],
+ [ null ],
+ [ null, null ],
+ [ null, 'foo' ],
+ [ false ],
+ [ false, 100 ],
+ [ true ],
+ [ true, 100 ],
+ [ 0 ],
+ [ 0, null ],
+ [ 0, 1 ],
+ [ 0, '' ],
+ [ 0, 'foo' ],
+ [ '', '' ],
+ [ 'foo' ],
+ [ 'foo', 1 ],
+ {},
+ { '0': null },
+ { '0': false },
+ { '0': true },
+ { '0': 0 },
+ { '0': 1 },
+ { '0': 'bar' },
+ { '0': 'foo' },
+ { '0': 'foo', '1': false },
+ { '0': 'foo', '1': true },
+ { '0': 'foo', '1': 0 },
+ { '0': 'foo', '1': '0' },
+ { '0': 'foo', '1': 'bar' },
+ { '0': 'quux' },
+ { '1': 'foo' }
+ ];
+
+ keys.forEach(function (key) {
+ var indexableString = toIndexableString(key);
+ JSON.stringify(parseIndexableString(indexableString)).should.equal(
+ JSON.stringify(key), 'check parseIndexableString for key: ' + key +
+ '(indexable string is: ' + indexableString + ')');
+ });
+ });
+ it('throws error in parseIndexableString on invalid input', function () {
+
+ try {
+ parseIndexableString('');
+ should.fail("didn't expect to parse correctly");
+ } catch (err) {
+ should.exist(err);
+ }
+ });
+});
\ No newline at end of file
