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 @@ -16,14 +16,7 @@ const queries = await Promise.map(access_strategies, strategy => strategy.getRestrictingQuery(context) ); - if (queries.some(query => query instanceof Query.DenyAll)) { - return new Query.DenyAll(); - } - const aggregated_pipeline = queries.reduce( - (acc, query) => acc.concat(query.toPipeline()), - [] - ); - return Query.fromCustomPipeline(aggregated_pipeline); + return new Query.And(...queries); }, 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,14 @@ const collections = [ { + name: + "collection-and(nested-and(allow, public), nested-or(allow, noone))", + 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 +86,16 @@ } } + it("return everything for collection-and(nested-and(allow, public), nested-or(allow, noone))", () => + with_running_app(async ({ app }) => { + await setup(app); + return get_collection_as({ + collection: + "collection-and(nested-and(allow, public), nested-or(allow, noone))", + 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/or.js b/lib/app/base-chips/access-strategy-types/or.js --- a/lib/app/base-chips/access-strategy-types/or.js +++ b/lib/app/base-chips/access-strategy-types/or.js @@ -20,14 +20,7 @@ if (queries.some(query => query instanceof Query.AllowAll)) { return new Query.AllowAll(); } - return Promise.reduce( - queries, - async (aggregated, query) => { - aggregated.addQuery(query); - return aggregated; - }, - new Query.Or() - ); + return new Query.Or(...queries); }, item_sensitive: function(params) { const access_strategies = parse_params(app, params); 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,11 @@ const collections = [ { - name: "collection-or(complex-allow-pipeline, noone)", + name: + "collection-or(nested-or(allow, noone), nested-and(allow, public))", strategies: [ ["or", ["complex-allow-pipeline", "noone"]], - ["or", ["complex-allow-pipeline", "noone"]], + ["and", ["complex-allow-pipeline", "public"]], ], }, { @@ -85,11 +86,12 @@ } } - it("returns everything for wrapped or(complex-allow-pipeline, noone)", () => + it("returns everything for collection-or(nested-or(allow, noone), nested-and(allow, public))", () => with_running_app(async ({ app }) => { await setup(app); return get_collection_as({ - collection: "collection-or(complex-allow-pipeline, noone)", + collection: + "collection-or(nested-or(allow, noone), nested-and(allow, public))", 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,164 @@ +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.adjacency_matrix[i][j] = 1; + } + _getIndexesOfNodePair(id_i, id_j) { + return [this.node_ids.indexOf(id_i), this.node_ids.indexOf(id_j)]; + } + 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 = []; + 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); + } + } + 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; + } + _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, + best_priority = Infinity, + current_mean, + best_mean = Infinity; + for (const candidate of candidates) { + if (this.nodes[candidate].priority < best_priority) { + best_priority = this.nodes[candidate].priority; + best_mean = this._meanPriorityOfSuccessors(candidate); + next_node = candidate; + if (this.nodes[candidate].priority === Graph.MAX_PRIORITY) { + break; + } + } else if (this.nodes[candidate].priority === best_priority) { + current_mean = this._meanPriorityOfSuccessors(candidate); + if (current_mean < best_mean) { + best_mean = current_mean; + next_node = candidate; + } + } + } + return { + index: next_node, + priority: best_priority, + mean_priority_of_succcessors: best_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-step.js b/lib/datastore/query-step.js new file mode 100644 --- /dev/null +++ b/lib/datastore/query-step.js @@ -0,0 +1,95 @@ +const object_hash = require("object-hash"); + +class QueryStep { + constructor(body) { + this.body = body; + } + hash() { + return QueryStep.hashBody(this.body); + } + static fromStage(stage, unwind = true) { + if (stage.$lookup) { + const clonedStageBody = Object.assign({}, stage.$lookup); + clonedStageBody.unwind = unwind; + return [new QueryStep.Lookup(clonedStageBody)]; + } else if (stage.$match) { + return Object.keys(stage.$match).map( + field => new QueryStep.Match({ [field]: stage.$match[field] }) + ); + } + throw new Error("Unsupported stage: " + stage); + } + pushDump(dumps) { + dumps.push(this.body); + return dumps; + } + static hashBody(body) { + return object_hash(body, { + algorithm: "md5", + excludeKeys: key => key === "as", + }); + } + getUsedFields() { + throw new Error("Cannot be used on base QueryStep class"); + } +} + +QueryStep.Lookup = class extends QueryStep { + constructor(body) { + const cleared_body = { + from: body.from, + localField: body.localField, + foreignField: body.foreignField, + }; + cleared_body.as = QueryStep.hashBody(cleared_body); + super(cleared_body); + this.unwind = body.unwind; + } + hash() { + return this.body.as; + } + pushStage(pipeline) { + pipeline.push({ $lookup: this.body }); + if (this.unwind) { + pipeline.push({ $unwind: "$" + this.body.as }); + } + return pipeline; + } + getUsedFields() { + return this.body.localField.split("."); + } + getCost() { + return 8; + } +}; + +QueryStep.Match = class extends QueryStep { + pushStage(pipeline) { + pipeline.push({ $match: this.body }); + return pipeline; + } + getUsedFields() { + return getAllKeys(this.body) + .map(path => path.split(".")) + .reduce((acc, fields) => + acc.concat(fields.filter(field => !field.startsWith("$"))) + ); + } + getCost() { + return this.body.$or ? 2 : 0; + } +}; + +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 = QueryStep; diff --git a/lib/datastore/query.js b/lib/datastore/query.js --- a/lib/datastore/query.js +++ b/lib/datastore/query.js @@ -1,56 +1,93 @@ "use strict"; -const Promise = require("bluebird"); -const hash_item = value => - require("object-hash")(value, { - algorithm: "md5", - excludeKeys: key => key === "as", - }); +const object_hash = require("object-hash"); +const QueryStep = require("./query-step.js"); +const transformObject = require("../utils/transform-object.js"); class Query { constructor() { - this.stages = []; + this.steps = []; } - lookup(body, unwind = true) { - body.as = hash_item(body); - this.stages.push({ $lookup: body, unwinds: unwind }); - return body.as; + lookup(body) { + const lookup_step = new QueryStep.Lookup(body); + this.steps.push(lookup_step); + return lookup_step.hash(); } match(body) { - this.stages.push({ $match: body }); - return this; + for (let key of Object.keys(body)) { + this.steps.push(new QueryStep.Match({ [key]: body[key] })); + } } dump() { - return this.stages; + return this.steps; } toPipeline() { - return this.stages.reduce( - (acc, stage) => this._pushToPipeline(acc, stage), + return this.steps.reduce( + (pipeline, query_step) => query_step.pushStage(pipeline), [] ); } - _pushToPipeline(pipeline, stage) { - if (!stage.$lookup) { - pipeline.push(stage); - } else { - pipeline.push({ $lookup: stage.$lookup }); - if (stage.unwinds) { - pipeline.push({ $unwind: "$" + stage.$lookup.as }); - } - } - return pipeline; - } 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; + let steps; + const field_as_to_hash = {}; + for (let i = 0; i < stages.length; ++i) { + if (stages[i].$unwind) { + continue; + } + const stage = transformObject( + stages[i], + prop => { + if (prop.startsWith("$")) { + return prop; + } + const fields = prop.split("."); + return fields + .map(field => field_as_to_hash[field] || field) + .join("."); + }, + (prop, value) => { + let fields; + if (typeof value !== "string") { + return value; + } + if (prop === "localField") { + fields = value.split("."); + } else if (value.startsWith("$")) { + fields = value.substring(1).split("."); + } else { + return value; + } + return fields + .map(field => field_as_to_hash[field] || field) + .join("."); + } + ); + steps = QueryStep.fromStage(stage, query._isUnwindStage(stages, i)); + if (stage.$lookup) { + const field_as = stage.$lookup.as; + field_as_to_hash[field_as] = steps[0].hash(); + } + + query.steps.push(...steps); + } return query; } + _isUnwindStage(stages, i) { + if (!stages[i].$lookup) { + return false; + } + return stages[i + 1] && stages[i + 1].$unwind; + } } +module.exports = Query; + Query.DenyAll = class extends Query { constructor() { super(); @@ -77,46 +114,6 @@ } }; -Query.Or = class extends Query { - constructor(...queries) { - super(); - this.lookups = {}; - this.matches = []; - for (let query of queries) { - this.addQuery(query); - } - } - 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)); - } - } - } - _lookup(stage) { - const id = stage.$lookup.as; - this.lookups[id] = stage; - } - _match(stage) { - this.matches.push(stage); - } - dump() { - return Object.values(this.lookups).concat({ - $match: { $or: this.matches.map(stage => stage.$match) }, - }); - } - toPipeline() { - return Object.values(this.lookups) - .reduce((acc, stage) => this._pushToPipeline(acc, stage), []) - .concat({ - $match: { $or: this.matches.map(stage => stage.$match) }, - }); - } -}; +Query.Or = require("./query_or.js"); -module.exports = Query; +Query.And = require("./query_and.js"); 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,317 @@ +const Query = require("./query.js"); +const assert = require("assert"); +const QueryStep = require("./query-step.js"); + +describe("Query", () => { + describe("Query general", () => { + it("Creates correct query from custom pipeline", () => { + const pipeline = [ + { $match: { title: { $ne: "The Joy of PHP" }, edition: 1 } }, + { + $lookup: { + from: "authors", + localField: "author", + foreignField: "_id", + as: "author_item", + }, + }, + { + $unwind: "$author_item", + }, + { $match: { "author_item.name": { $regex: "some_regex" } } }, + { + $lookup: { + from: "states", + localField: "author.state", + foreignField: "_id", + as: "state_item", + }, + }, + { $unwind: "$state_item" }, + { + $match: { + $or: [ + { "author_item.age": { $le: 30 } }, + { edition: { $gt: 3 } }, + ], + "state_item.abbrevation": { $eq: "PL" }, + }, + }, + ]; + + const query = Query.fromCustomPipeline(pipeline); + + const authors_hash = hashLookup(pipeline[1]); + const states_hash = hashLookup(pipeline[4]); + const expected_pipeline = [ + { $match: { title: { $ne: "The Joy of PHP" } } }, + { $match: { edition: 1 } }, + { + $lookup: { + from: "authors", + localField: "author", + foreignField: "_id", + as: authors_hash, + }, + }, + { + $unwind: "$" + authors_hash, + }, + { + $match: { + [`${authors_hash}.name`]: { + $regex: "some_regex", + }, + }, + }, + { + $lookup: { + from: "states", + localField: "author.state", + foreignField: "_id", + as: states_hash, + }, + }, + { $unwind: "$" + states_hash }, + { + $match: { + $or: [ + { [`${authors_hash}.age`]: { $le: 30 } }, + { edition: { $gt: 3 } }, + ], + }, + }, + { $match: { [`${states_hash}.abbrevation`]: { $eq: "PL" } } }, + ]; + + assert.deepEqual(query.toPipeline(), expected_pipeline); + }); + }); + describe("Query.Or", () => { + it("Returns correct pipeline stages", () => { + const queries = []; + + const M1 = { + title: { $ne: "The Joy of PHP" }, + }; + queries.push(Query.fromSingleMatch(M1)); + + let query = new Query(); + const L2 = { + from: "authors", + localField: "author", + foreignField: "_id", + unwind: true, + }; + const L2_id = query.lookup(L2); + const M3 = { + [`${L2_id}.last_name`]: { $in: ["Scott", "Dostoyevsky"] }, + }; + query.match(M3); + queries.push(query); + + const or = new Query.Or(...queries); + + const expected_pipeline = [ + { + $lookup: { + from: L2.from, + localField: L2.localField, + foreignField: L2.foreignField, + as: L2_id, + }, + }, + { $unwind: `$${L2_id}` }, + { $match: { $or: [M1, M3] } }, + ]; + assert.deepEqual(or.toPipeline(), expected_pipeline); + }); + }); + 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", + unwind: true, + }; + 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)); + + const 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.steps = query.steps.concat(stage.dump()); + } 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", + unwind: true, + }; + const L1_id = query.lookup(L1); + + const L2 = { + from: "publisher", + localField: `${L1_id}.publisher`, + foreignField: "publisher_id", + unwind: true, + }; + const L2_id = query.lookup(L2); + + const M3_4 = { + [`${L2_id}.city`]: { $in: ["A", "B"] }, + $or: [ + { [`${L1_id}.first_name`]: "Ann" }, + { [`${L2_id}.income`]: { $gt: 1000 } }, + ], + }; + 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", + unwind: true, + }; + 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", + unwind: true, + }; + 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, O6, L1, L2, M3_4], + and.toPipeline() + ); + }); + it("Returns deny all pipeline when provided Query.DenyAll", () => { + const queries = []; + let query = new Query(); + + const L1 = { + from: "authors", + localField: "author", + foreignField: "_id", + unwind: true, + }; + const L1_id = query.lookup(L1); + const M2 = { + [`${L1_id}.last_name`]: { $in: ["Christie", "Rowling"] }, + }; + query.match(M2); + queries.push(query); + + const deny_all_query = new Query.DenyAll(); + queries.push(deny_all_query); + + const M3 = { + title: { $ne: "The Joy of PHP" }, + }; + queries.push(Query.fromSingleMatch(M3)); + + const and = new Query.And(...queries); + assert.deepEqual(and.toPipeline(), deny_all_query.toPipeline()); + }); + }); +}); + +function hashLookup({ $lookup }) { + const { as, ...lookup_without_as } = $lookup; + return QueryStep.hashBody(lookup_without_as); +} diff --git a/lib/datastore/query_and.js b/lib/datastore/query_and.js new file mode 100644 --- /dev/null +++ b/lib/datastore/query_and.js @@ -0,0 +1,76 @@ +const Query = require("./query.js"); +const QueryStep = require("./query-step.js"); +const Graph = require("./graph.js"); + +module.exports = class extends Query { + constructor(...queries) { + super(); + this._reset(); + for (let query of queries) { + this.addQuery(query); + } + } + _reset() { + this.graph = new Graph(); + this.aggregation_steps = {}; + this.received_deny_all = false; + } + addQuery(query) { + if (this.received_deny_all) { + return; + } + if (query instanceof Query.DenyAll) { + this._reset(); + this.received_deny_all = true; + } + const steps = query.dump(); + for (let step of steps) { + const id = step.hash(); + if (this._isInGraph(id)) { + continue; + } + + this._addToAggregationSteps(id, step); + this._addDependenciesInGraph(id, step); + } + } + _isInGraph(key) { + return key.length === 32 && this.graph.node_ids.includes(key); + } + _addToAggregationSteps(id, step) { + this.graph.addNode(id, step.getCost()); + this.aggregation_steps[id] = step; + } + _addDependenciesInGraph(id, step) { + let dependencies = step + .getUsedFields() + .filter(field => this._isInGraph(field)); + + if (step instanceof QueryStep.Match) { + dependencies = dependencies.filter(d1 => + this._isNotDependencyForAnyInGroup(d1, dependencies) + ); + } + + for (let dependency of dependencies) { + this.graph.addEdge(dependency, id); + } + } + _isNotDependencyForAnyInGroup(id, nodeGroup) { + return !nodeGroup.some( + node => id !== node && this.graph.pathExists(id, node) + ); + } + 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]) { + step.pushStage(pipeline); + } + return pipeline; + } + return this.aggregation_steps[id].pushStage(pipeline); + }, []); + } +}; diff --git a/lib/datastore/query_or.js b/lib/datastore/query_or.js new file mode 100644 --- /dev/null +++ b/lib/datastore/query_or.js @@ -0,0 +1,36 @@ +const Query = require("./query.js"); +const QueryStep = require("./query-step.js"); + +module.exports = class extends Query { + constructor(...queries) { + super(); + for (let query of queries) { + this.addQuery(query); + } + } + addQuery(query) { + const steps = query.dump(); + this.steps.push(...steps); + } + dump() { + const lookup_steps = this.steps.filter( + step => step instanceof QueryStep.Lookup + ); + + return lookup_steps.concat( + new QueryStep.Match({ $or: this._getMatchExpressions() }) + ); + } + toPipeline() { + const lookups = this.steps + .filter(step => step instanceof QueryStep.Lookup) + .reduce((acc, step) => step.pushStage(acc), []); + + return lookups.concat({ $match: { $or: this._getMatchExpressions() } }); + } + _getMatchExpressions() { + return this.steps + .filter(step => step instanceof QueryStep.Match) + .reduce((acc, step) => step.pushDump(acc), []); + } +}; diff --git a/lib/utils/transform-object.js b/lib/utils/transform-object.js new file mode 100644 --- /dev/null +++ b/lib/utils/transform-object.js @@ -0,0 +1,13 @@ +function transformObject(obj, prop_tranformer, value_transformer) { + return Object.keys(obj).reduce((new_obj, prop) => { + let new_prop = prop_tranformer(prop); + new_obj[new_prop] = + obj[prop] instanceof Object + ? transformObject(obj[prop], prop_tranformer, value_transformer) + : value_transformer(prop, obj[prop]); + + return new_obj; + }, Array.isArray(obj) ? [] : {}); +} + +module.exports = transformObject; 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();