diff --git a/lib/app/base-chips/access-strategy-types/and.js b/lib/app/base-chips/access-strategy-types/and.js --- a/lib/app/base-chips/access-strategy-types/and.js +++ b/lib/app/base-chips/access-strategy-types/and.js @@ -19,11 +19,15 @@ if (queries.some(query => query instanceof Query.DenyAll)) { return new Query.DenyAll(); } - const aggregated_pipeline = queries.reduce( - (acc, query) => acc.concat(query.toPipeline()), - [] + + return Promise.reduce( + queries, + async (aggregated, query) => { + aggregated.addQuery(query); + return aggregated; + }, + new Query.And() ); - return Query.fromCustomPipeline(aggregated_pipeline); }, item_sensitive: function(params) { const access_strategies = parse_params(app, params); diff --git a/lib/app/base-chips/access-strategy-types/and.subtest.js b/lib/app/base-chips/access-strategy-types/and.subtest.js --- a/lib/app/base-chips/access-strategy-types/and.subtest.js +++ b/lib/app/base-chips/access-strategy-types/and.subtest.js @@ -26,6 +26,13 @@ const collections = [ { + name: "collection-and(nested-and, nested-or)", + strategies: [ + ["and", ["complex-allow-pipeline", "public"]], + ["or", ["complex-allow-pipeline", "noone"]], + ], + }, + { name: "collection-and(complex-allow-pipeline, noone)", strategies: ["complex-allow-pipeline", "noone"], }, @@ -78,6 +85,15 @@ } } + it("return everything for collection-and(nested-and, nested-or)", () => + with_running_app(async ({ app }) => { + await setup(app); + return get_collection_as({ + collection: "collection-and(nested-and, nested-or)", + port, + }).then(data => assert.equal(data.length, 3)); + })); + it("returns nothing for and(complex-allow-pipeline, noone)", () => with_running_app(async ({ app }) => { await setup(app); diff --git a/lib/app/base-chips/access-strategy-types/and_or_strategy_helpers.js b/lib/app/base-chips/access-strategy-types/and_or_strategy_helpers.js new file mode 100644 --- /dev/null +++ b/lib/app/base-chips/access-strategy-types/and_or_strategy_helpers.js @@ -0,0 +1,13 @@ +"use strict"; + +const locreq = require("locreq")(__dirname); +const AccessStrategy = locreq("lib/chip-types/access-strategy.js"); +const Promise = require("bluebird"); + +const helpers = { + parse_params: function(app, params) { + return Object.keys(params).map(i => new AccessStrategy(app, params[i])); + }, +}; + +module.exports = helpers; diff --git a/lib/app/base-chips/access-strategy-types/or.subtest.js b/lib/app/base-chips/access-strategy-types/or.subtest.js --- a/lib/app/base-chips/access-strategy-types/or.subtest.js +++ b/lib/app/base-chips/access-strategy-types/or.subtest.js @@ -26,10 +26,10 @@ const collections = [ { - name: "collection-or(complex-allow-pipeline, noone)", + name: "collection-or(nested-or, nested-and)", strategies: [ ["or", ["complex-allow-pipeline", "noone"]], - ["or", ["complex-allow-pipeline", "noone"]], + ["and", ["complex-allow-pipeline", "public"]], ], }, { @@ -85,11 +85,11 @@ } } - it("returns everything for wrapped or(complex-allow-pipeline, noone)", () => + it("returns everything for collection-or(nested-or, nested-and)", () => with_running_app(async ({ app }) => { await setup(app); return get_collection_as({ - collection: "collection-or(complex-allow-pipeline, noone)", + collection: "collection-or(nested-or, nested-and)", port, }).then(data => assert.equal(data.length, 3)); })); diff --git a/lib/app/base-chips/access-strategy-types/user-referenced-in-field.js b/lib/app/base-chips/access-strategy-types/user-referenced-in-field.js --- a/lib/app/base-chips/access-strategy-types/user-referenced-in-field.js +++ b/lib/app/base-chips/access-strategy-types/user-referenced-in-field.js @@ -2,7 +2,7 @@ name: "user-referenced-in-field", getRestrictingQuery: async (context, field_name) => { if (!context.user_id) return new app.Query.DenyAll(); - return new app.Query().match({ + return app.Query.fromSingleMatch({ [`body.${field_name}`]: context.user_id, }); }, diff --git a/lib/datastore/graph.js b/lib/datastore/graph.js new file mode 100644 --- /dev/null +++ b/lib/datastore/graph.js @@ -0,0 +1,170 @@ +class Graph { + constructor() { + this.adjacency_matrix = []; + this.node_ids = []; + this.nodes = []; + this.indexes = []; + } + addNode(id, priority) { + this.adjacency_matrix.push(Array(this.getNoOfNodes()).fill(0)); + for (const row of this.adjacency_matrix) { + row.push(0); + } + this.node_ids.push(id); + this.nodes.push({ id, priority }); + this.indexes.push(this.nodes.length - 1); + } + getNoOfNodes() { + return this.nodes.length; + } + addEdge(id_i, id_j) { + const [i, j] = this._getIndexesOfNodePair(id_i, id_j); + this._addEdge(i, j); + } + _getIndexesOfNodePair(id_i, id_j) { + return [this.node_ids.indexOf(id_i), this.node_ids.indexOf(id_j)]; + } + _addEdge(i, j) { + this.adjacency_matrix[i][j] = 1; + } + pathExists(id_i, id_j) { + const [i, j] = this._getIndexesOfNodePair(id_i, id_j); + return this._pathExists(i, j); + } + _pathExists(i, j) { + if (this.adjacency_matrix[i][j]) { + return true; + } + for (let k = 0; k < this.getNoOfNodes(); ++k) { + if (this.adjacency_matrix[i][k]) { + return this._pathExists(k, j); + } + } + return false; + } + bestFirstSearch() { + this.front = []; + this.visited = []; + this._bestFirstSearch(); + return this.visited.map(i => this.nodes[i].id); + } + _areAllSuccessorsVisited(i) { + for (let j = 0; j < this.nodes.length; ++j) { + if (this.adjacency_matrix[i][j] && !this._isVisited(j)) { + return false; + } + } + return true; + } + _isVisited(i) { + return this.visited.includes(i); + } + _isNodeWithoutPredecessors(i) { + for (let j = 0; j < this.nodes.length; ++j) { + if (this.adjacency_matrix[j][i]) { + return false; + } + } + return true; + } + _bestFirstSearch() { + while (this.visited.length < this.nodes.length) { + const { front_node, next_node } = this._getNextNode(); + this.visited.push(next_node); + + if (front_node !== null) { + if (this._areAllSuccessorsVisited(front_node)) { + const index = this.front.indexOf(front_node); + this.front.splice(index, 1); + } + } + + if (!this._areAllSuccessorsVisited(next_node)) { + this.front.push(next_node); + } + } + } + _getNextNode() { + const nodesWithoutPredecessorsYetToBeVisited = this.indexes.filter( + i => this._isNodeWithoutPredecessors(i) && !this._isVisited(i) + ); + + const candidate1 = this._lookForNextNodeInCandidates( + nodesWithoutPredecessorsYetToBeVisited + ); + if (candidate1.priority === Graph.MAX_PRIORITY) { + return { front_node: null, next_node: candidate1.index }; + } + + const successorsYetToBeVisited = this.front.reduce((successors, i) => { + this.indexes + .filter(j => this.adjacency_matrix[i][j] && !this._isVisited(j)) + .map(j => successors.add(j)); + return successors; + }, new Set()); + + const candidate2 = this._lookForNextNodeInCandidates( + successorsYetToBeVisited + ); + + if (candidate1.priority < candidate2.priority) { + return { front_node: null, next_node: candidate1.index }; + } + + if (candidate1.priority === candidate2.priority) { + if ( + candidate1.mean_priority_of_succcessors < + candidate2.mean_priority_of_succcessors + ) { + return { front_node: null, next_node: candidate1.index }; + } + } + + const front_node = this.indexes.find( + i => this.adjacency_matrix[i][candidate2.index] + ); + return { front_node, next_node: candidate2.index }; + } + _lookForNextNodeInCandidates(candidates) { + let next_node = null, + highest_priority = Infinity, + current_mean, + highest_mean = Infinity; + for (const candidate of candidates) { + if (this.nodes[candidate].priority < highest_priority) { + highest_priority = this.nodes[candidate].priority; + highest_mean = this._meanPriorityOfSuccessors(candidate); + next_node = candidate; + if (this.nodes[candidate].priority === Graph.MAX_PRIORITY) { + break; + } + } else if (this.nodes[candidate].priority === highest_priority) { + current_mean = this._meanPriorityOfSuccessors(candidate); + if (current_mean < highest_mean) { + highest_mean = current_mean; + next_node = candidate; + } + } + } + return { + index: next_node, + priority: highest_priority, + mean_priority_of_succcessors: highest_mean, + }; + } + _meanPriorityOfSuccessors(i) { + let sum = 0, + length = 0; + for (let j of this.indexes) { + if (this.adjacency_matrix[i][j] && !this._isVisited(j)) { + sum += this.nodes[j].priority; + ++length; + } + } + return length > 0 ? sum / length : 0; + } +} + +Graph.MAX_PRIORITY = 0; + +module.exports = Graph; diff --git a/lib/datastore/graph.test.js b/lib/datastore/graph.test.js new file mode 100644 --- /dev/null +++ b/lib/datastore/graph.test.js @@ -0,0 +1,123 @@ +const Graph = require("./graph.js"); +const assert = require("assert"); + +describe("graph", () => { + let graph; + beforeEach(() => { + graph = new Graph(); + }); + + it("Adding nodes and edges works correctly", () => { + graph.addNode(1, 0); + graph.addNode(2, 0); + graph.addNode(3, 0); + graph.addNode(4, 0); + graph.addNode(5, 1); + graph.addNode(6, 1); + graph.addNode(7, 0); + graph.addEdge(2, 3); + graph.addEdge(2, 4); + graph.addEdge(4, 5); + graph.addEdge(6, 7); + + assert.deepEqual(graph.adjacency_matrix, [ + [0, 0, 0, 0, 0, 0, 0], + [0, 0, 1, 1, 0, 0, 0], + [0, 0, 0, 0, 0, 0, 0], + [0, 0, 0, 0, 1, 0, 0], + [0, 0, 0, 0, 0, 0, 0], + [0, 0, 0, 0, 0, 0, 1], + [0, 0, 0, 0, 0, 0, 0], + ]); + }); + + // L1 M3 +----L4----+ + // + | | + // | | | + // v v v + // M2 L5 M6 + // + + // | + // v + // M7 + + it("Correctly runs best-first search on simple graph", () => { + graph.addNode("L1", 1); + graph.addNode("M2", 0); + graph.addNode("M3", 0); + graph.addNode("L4", 1); + graph.addNode("L5", 1); + graph.addNode("M6", 0); + graph.addNode("M7", 0); + graph.addEdge("L1", "M2"); + graph.addEdge("L4", "L5"); + graph.addEdge("L4", "M6"); + graph.addEdge("M6", "M7"); + + assert.deepEqual( + ["M3", "L1", "M2", "L4", "M6", "M7", "L5"], + graph.bestFirstSearch() + ); + }); + + // L1 M5 L6 +-----L12----+ + // + + | | + // | | | | + // v v v v + // +-----L2----+ +-----O7-----+ M13 L14 + // | | | | + + // | | | | | + // v v v v v + // M3 M4 +---L8---+ M11 M15 + // | | + // v v + // M9 M10 + + it("Correctly runs best-first search on complex graph", () => { + graph.addNode("L1", 1); + graph.addNode("L2", 1); + graph.addNode("M3", 0); + graph.addNode("M4", 0); + graph.addNode("M5", 0); + graph.addNode("L6", 1); + graph.addNode("O7", 2); + graph.addNode("L8", 1); + graph.addNode("M9", 0); + graph.addNode("M10", 0); + graph.addNode("M11", 0); + graph.addNode("L12", 1); + graph.addNode("M13", 0); + graph.addNode("L14", 1); + graph.addNode("M15", 0); + graph.addEdge("L1", "L2"); + graph.addEdge("L2", "M3"); + graph.addEdge("L2", "M4"); + graph.addEdge("L6", "O7"); + graph.addEdge("O7", "L8"); + graph.addEdge("L8", "M9"); + graph.addEdge("L8", "M10"); + graph.addEdge("O7", "M11"); + graph.addEdge("L12", "M13"); + graph.addEdge("L12", "L14"); + graph.addEdge("L14", "M15"); + + const expectedOrder = [ + "M5", + "L12", + "M13", + "L14", + "M15", + "L1", + "L2", + "M3", + "M4", + "L6", + "O7", + "M11", + "L8", + "M9", + "M10", + ]; + assert.deepEqual(expectedOrder, graph.bestFirstSearch()); + }); +}); diff --git a/lib/datastore/query.js b/lib/datastore/query.js --- a/lib/datastore/query.js +++ b/lib/datastore/query.js @@ -1,8 +1,10 @@ "use strict"; const Promise = require("bluebird"); +const Graph = require("./graph.js"); +const object_hash = require("object-hash"); const hash_item = value => - require("object-hash")(value, { + object_hash(value, { algorithm: "md5", excludeKeys: key => key === "as", }); @@ -18,7 +20,6 @@ } match(body) { this.stages.push({ $match: body }); - return this; } dump() { return this.stages; @@ -42,13 +43,25 @@ } static fromSingleMatch(body) { const query = new Query(); - return query.match(body); + query.match(body); + return query; } static fromCustomPipeline(stages) { const query = new Query(); query.stages = stages; return query; } + _addStages(stages) { + for (let stage of stages) { + if (stage.$match) { + this._match(stage); + } else if (stage.$lookup) { + this._lookup(stage); + } else { + throw new Error("Unsupported query: " + Object.keys(stage)); + } + } + } } Query.DenyAll = class extends Query { @@ -87,16 +100,8 @@ } } addQuery(query) { - let stages = query.dump(); - for (let stage of stages) { - if (stage.$lookup) { - this._lookup(stage); - } else if (stage.$match) { - this._match(stage); - } else { - throw new Error("Unsupported query: " + Object.keys(stage)); - } - } + const stages = query.dump(); + this._addStages(stages); } _lookup(stage) { const id = stage.$lookup.as; @@ -119,4 +124,114 @@ } }; +Query.And = class extends Query { + constructor(...queries) { + super(); + this.graph = new Graph(); + this.aggregation_steps = {}; + for (let query of queries) { + this.addQuery(query); + } + } + addQuery(query) { + const stages = query.dump(); + if (query instanceof Query.Or) { + this._addOrPipeline(stages); + return; + } + this._addStages(stages); + } + _addOrPipeline(pipeline) { + const id = hash_item(pipeline); + const priority = this._evaluateOrPipelinePriority(pipeline); + this._addToAggregationSteps(id, pipeline, priority); + } + _evaluateOrPipelinePriority(pipeline) { + return pipeline[0].$match ? 2 : 16; + } + _match(stage) { + for (let key of Object.keys(stage.$match)) { + const step = { $match: { [key]: stage.$match[key] } }; + const id = hash_item(step.$match); + if (this.graph.node_ids.includes(id)) { + return; + } + + this._addToAggregationSteps(id, step, Graph.MAX_PRIORITY); + + const paths = getAllKeys(step.$match); + const dependencies = paths + .map(path => path.split(".")) + .reduce((acc, fields) => { + return acc.concat( + fields.filter(field => this._isInGraph(field)) + ); + }, []); + this._addDependenciesOnlyFromFinalNodes(id, dependencies); + } + } + + _isInGraph(key) { + return ( + !key.startsWith("$") && + key.length === 32 && + this.graph.node_ids.includes(key) + ); + } + _addDependenciesOnlyFromFinalNodes(id, candidates) { + candidates + .filter(d1 => this._isNotDependencyForAnyInGroup(d1, candidates)) + .forEach(dependency => this.graph.addEdge(dependency, id)); + } + _isNotDependencyForAnyInGroup(id, nodeGroup) { + return !nodeGroup.some( + node => id !== node && this.graph.pathExists(id, node) + ); + } + _lookup(stage) { + const id = stage.$lookup.as; + + if (this.graph.node_ids.includes(id)) { + return; + } + + this._addToAggregationSteps(id, stage, 8); + const candidatesForDependencies = stage.$lookup.localField.split("."); + for (let candidate of candidatesForDependencies) { + if (this._isInGraph(candidate)) { + this.graph.addEdge(candidate, id); + } + } + } + + _addToAggregationSteps(id, step, priority) { + this.graph.addNode(id, priority); + this.aggregation_steps[id] = step; + } + toPipeline() { + const sortedStepIds = this.graph.bestFirstSearch(); + return sortedStepIds.reduce((pipeline, id) => { + if (Array.isArray(this.aggregation_steps[id])) { + for (let step of this.aggregation_steps[id]) { + this._pushToPipeline(pipeline, step); + } + return pipeline; + } + return this._pushToPipeline(pipeline, this.aggregation_steps[id]); + }, []); + } +}; + +function getAllKeys(obj) { + return Object.keys(obj).reduce((acc, key) => { + if (obj[key] instanceof Object) { + acc.push(...getAllKeys(obj[key])); + } + if (!Array.isArray(obj)) { + acc.push(key); + } + return acc; + }, []); +} + module.exports = Query; diff --git a/lib/datastore/query.test.js b/lib/datastore/query.test.js new file mode 100644 --- /dev/null +++ b/lib/datastore/query.test.js @@ -0,0 +1,154 @@ +const Query = require("./query.js"); +const assert = require("assert"); + +describe("Query", () => { + describe("Query.And", () => { + it("Returns pipeline stages in correct order for simple case", () => { + const queries = []; + let query = new Query(); + + const L1 = { + from: "authors", + localField: "author", + foreignField: "_id", + }; + const L1_id = query.lookup(L1); + const M2 = { + [`${L1_id}.last_name`]: { $in: ["Christie", "Rowling"] }, + }; + query.match(M2); + queries.push(query); + + const M3 = { + title: { $ne: "The Joy of PHP" }, + }; + queries.push(Query.fromSingleMatch(M3)); + + let and = new Query.And(...queries); + assertStagesAreCorrectlyOrdered([M3, L1, M2], and.toPipeline()); + }); + + function assertStagesAreCorrectlyOrdered( + expectedRawPipeline, + actualPipeline + ) { + const query = new Query(); + for (let i = 0; i < expectedRawPipeline.length; ++i) { + const stage = expectedRawPipeline[i]; + if (stage instanceof Query) { + query.stages = query.stages.concat(stage.toPipeline()); + } else if (stage.from) { + query.lookup(stage); + } else { + for (let step of Object.keys(stage)) { + query.match({ [step]: stage[step] }); + } + } + } + assert.deepEqual(actualPipeline, query.toPipeline()); + } + + it("Returns pipeline stages in correct order for complex case", () => { + const queries = []; + let query = new Query(); + + const L1 = { + from: "authors", + localField: "author", + foreignField: "_id", + }; + const L1_id = query.lookup(L1); + + const L2 = { + from: "publisher", + localField: `${L1_id}.publisher`, + foreignField: "publisher_id", + }; + const L2_id = query.lookup(L2); + + const M3_4 = { + $or: [ + { [`${L1_id}.first_name`]: "Ann" }, + { [`${L2_id}.income`]: { $gt: 1000 } }, + ], + [`${L2_id}.city`]: { $in: ["A", "B"] }, + }; + query.match(M3_4); + queries.push(query); + + query = new Query(); + const M5 = { + title: { $ne: "The Joy of PHP" }, + }; + query.match(M5); + queries.push(query); + + let subquery1 = new Query(); + const O6_L1 = { + from: "libraries", + localField: "first_library", + foreignField: "library_id", + }; + const O6_L1_id = subquery1.lookup(O6_L1); + + const O6_M1 = { + [`${O6_L1_id}.street`]: { $in: ["A street", "B street"] }, + [`${O6_L1_id}.open_at_night`]: { $eq: true }, + }; + subquery1.match(O6_M1); + + const O6_M2 = { + books_count: { $lte: 30 }, + }; + let subquery2 = Query.fromSingleMatch(O6_M2); + const O6 = new Query.Or(subquery1, subquery2); + queries.push(O6); + + const O7_M1 = { + title: { + $in: ["PHP - Python Has Power", "The Good Parts of JS"], + }, + }; + const O7_M2 = O6_M2; + const O7 = new Query.Or( + Query.fromSingleMatch(O7_M1), + Query.fromSingleMatch(O7_M2) + ); + queries.push(O7); + + query = new Query(); + const L8 = { + from: "cover_types", + localField: "cover", + foreignField: "cover_type_id", + }; + const L8_id = query.lookup(L8); + + const M9 = { + [`${L8_id}.name`]: { $ne: "hard" }, + }; + query.match(M9); + queries.push(query); + + query = new Query(); + // check if hashing is order insensitive + const L10 = { + localField: "cover", + from: "cover_types", + foreignField: "cover_type_id", + }; + const L10_id = query.lookup(L10); + const M11 = { + [`${L10_id}.name`]: { $ne: "no_cover" }, + }; + query.match(M11); + queries.push(query); + + let and = new Query.And(...queries); + assertStagesAreCorrectlyOrdered( + [M5, O7, L8, M9, M11, L1, L2, M3_4, O6], + and.toPipeline() + ); + }); + }); +}); diff --git a/package.json b/package.json --- a/package.json +++ b/package.json @@ -5,15 +5,13 @@ "description": "A declarative framework for fast & easy app development.", "main": "./lib/main.js", "scripts": { - "test": "mocha setup-test.js lib/**/*.test.js" + "test": "mocha setup-test.js \"./lib/**/*.test.js\"" }, "repository": { "type": "git", "url": "https://github.com/sealcode/sealious" }, - "keywords": [ - "sealious" - ], + "keywords": ["sealious"], "author": "The Sealious team (http://github.com/Sealious)", "license": "BSD-2-Clause", "bugs": { diff --git a/test_utils/access-strategy-types/create_strategies_with_complex_pipeline.js b/test_utils/access-strategy-types/create_strategies_with_complex_pipeline.js --- a/test_utils/access-strategy-types/create_strategies_with_complex_pipeline.js +++ b/test_utils/access-strategy-types/create_strategies_with_complex_pipeline.js @@ -17,11 +17,12 @@ localField: "body.number", foreignField: "sealious_id", }); - return query.match({ + query.match({ [`${id}._id`]: { $exists: strategy === "complex-allow-pipeline", }, }); + return query; }, checker_function: function() { return Promise.resolve();