{"version":3,"sources":["../browser/src/persistence/SubjectTopoligicalSorter.ts"],"names":[],"mappings":";AAGA;;;GAGG;AACH;IAgBI,4EAA4E;IAC5E,cAAc;IACd,4EAA4E;IAE5E,kCAAY,QAAmB;QAC3B,IAAI,CAAC,QAAQ,oBAAO,QAAQ,CAAC,CAAC,CAAC,kDAAkD;QACjF,IAAI,CAAC,SAAS,GAAG,IAAI,CAAC,kBAAkB,CAAC,IAAI,CAAC,QAAQ,CAAC,CAAC;IAC5D,CAAC;IAED,4EAA4E;IAC5E,iBAAiB;IACjB,4EAA4E;IAE5E;;OAEG;IACH,uCAAI,GAAJ,UAAK,SAA4B;QAAjC,iBA+CC;QA7CG,uGAAuG;QACvG,IAAI,CAAC,IAAI,CAAC,SAAS,CAAC,MAAM;YACtB,OAAO,IAAI,CAAC,QAAQ,CAAC;QAEzB,IAAM,cAAc,GAAc,EAAE,CAAC;QAErC,sDAAsD;QACtD,wEAAwE;QACxE,IAAI,SAAS,KAAK,QAAQ,EAAE;YACxB,IAAM,gBAAgB,GAAG,IAAI,CAAC,QAAQ,CAAC,MAAM,CAAC,UAAA,OAAO,IAAI,OAAA,CAAC,OAAO,CAAC,MAAM,IAAI,CAAC,OAAO,CAAC,cAAc,EAA1C,CAA0C,CAAC,CAAC;YACrG,cAAc,CAAC,IAAI,OAAnB,cAAc,mBAAS,gBAAgB,GAAE;YACzC,IAAI,CAAC,mBAAmB,CAAC,gBAAgB,CAAC,CAAC;SAC9C;QAED,8EAA8E;QAC9E,IAAM,uBAAuB,GAAG,IAAI,CAAC,0BAA0B,EAAE,CAAC;QAClE,IAAI,8BAA8B,GAAG,IAAI,CAAC,QAAQ,CAAC,uBAAuB,CAAC,CAAC;QAC5E,IAAI,SAAS,KAAK,QAAQ;YACtB,8BAA8B,GAAG,8BAA8B,CAAC,OAAO,EAAE,CAAC;QAE9E,qCAAqC;QACrC,0EAA0E;QAC1E,0EAA0E;QAC1E,8BAA8B,CAAC,OAAO,CAAC,UAAA,kBAAkB;YACrD,IAAM,oBAAoB,GAAG,KAAI,CAAC,QAAQ,CAAC,MAAM,CAAC,UAAA,OAAO,IAAI,OAAA,OAAO,CAAC,QAAQ,CAAC,UAAU,KAAK,kBAAkB,EAAlD,CAAkD,CAAC,CAAC;YACjH,cAAc,CAAC,IAAI,OAAnB,cAAc,mBAAS,oBAAoB,GAAE;YAC7C,KAAI,CAAC,mBAAmB,CAAC,oBAAoB,CAAC,CAAC;QACnD,CAAC,CAAC,CAAC;QAEH,+BAA+B;QAC/B,mDAAmD;QACnD,IAAM,iBAAiB,GAAe,IAAI,CAAC,eAAe,EAAE,CAAC;QAC7D,IAAI,wBAAwB,GAAG,IAAI,CAAC,QAAQ,CAAC,iBAAiB,CAAC,CAAC;QAChE,IAAI,SAAS,KAAK,QAAQ;YACtB,wBAAwB,GAAG,wBAAwB,CAAC,OAAO,EAAE,CAAC;QAElE,wBAAwB,CAAC,OAAO,CAAC,UAAA,kBAAkB;YAC/C,IAAM,oBAAoB,GAAG,KAAI,CAAC,QAAQ,CAAC,MAAM,CAAC,UAAA,OAAO,IAAI,OAAA,OAAO,CAAC,QAAQ,CAAC,UAAU,KAAK,kBAAkB,EAAlD,CAAkD,CAAC,CAAC;YACjH,cAAc,CAAC,IAAI,OAAnB,cAAc,mBAAS,oBAAoB,GAAE;YAC7C,KAAI,CAAC,mBAAmB,CAAC,oBAAoB,CAAC,CAAC;QACnD,CAAC,CAAC,CAAC;QAEH,6DAA6D;QAC7D,cAAc,CAAC,IAAI,OAAnB,cAAc,mBAAS,IAAI,CAAC,QAAQ,GAAE;QACtC,OAAO,cAAc,CAAC;IAC1B,CAAC;IAED,4EAA4E;IAC5E,oBAAoB;IACpB,4EAA4E;IAE5E;;OAEG;IACO,sDAAmB,GAA7B,UAA8B,QAAmB;QAAjD,iBAIC;QAHG,QAAQ,CAAC,OAAO,CAAC,UAAA,OAAO;YACpB,KAAI,CAAC,QAAQ,CAAC,MAAM,CAAC,KAAI,CAAC,QAAQ,CAAC,OAAO,CAAC,OAAO,CAAC,EAAE,CAAC,CAAC,CAAC;QAC5D,CAAC,CAAC,CAAC;IACP,CAAC;IAED;;OAEG;IACO,qDAAkB,GAA5B,UAA6B,QAAmB;QAC5C,IAAM,SAAS,GAAqB,EAAE,CAAC;QACvC,QAAQ,CAAC,OAAO,CAAC,UAAA,OAAO;YACpB,IAAI,SAAS,CAAC,OAAO,CAAC,OAAO,CAAC,QAAQ,CAAC,KAAK,CAAC,CAAC;gBAC1C,SAAS,CAAC,IAAI,CAAC,OAAO,CAAC,QAAQ,CAAC,CAAC;QACzC,CAAC,CAAC,CAAC;QACH,OAAO,SAAS,CAAC;IACrB,CAAC;IAED;;;OAGG;IACO,6DAA0B,GAApC;QACI,OAAO,IAAI,CAAC,SAAS,CAAC,MAAM,CAAC,UAAC,YAAY,EAAE,QAAQ;YAChD,QAAQ,CAAC,wBAAwB,CAAC,OAAO,CAAC,UAAA,QAAQ;gBAC9C,IAAI,QAAQ,CAAC,UAAU;oBACnB,OAAO;gBAEX,YAAY,CAAC,IAAI,CAAC,CAAC,QAAQ,CAAC,UAAU,EAAE,QAAQ,CAAC,qBAAqB,CAAC,UAAU,CAAC,CAAC,CAAC;YACxF,CAAC,CAAC,CAAC;YACH,OAAO,YAAY,CAAC;QACxB,CAAC,EAAE,EAAgB,CAAC,CAAC;IACzB,CAAC;IAED;;;OAGG;IACO,kDAAe,GAAzB;QACI,OAAO,IAAI,CAAC,SAAS,CAAC,MAAM,CAAC,UAAC,YAAY,EAAE,QAAQ;YAChD,QAAQ,CAAC,wBAAwB,CAAC,OAAO,CAAC,UAAA,QAAQ;gBAE9C,4CAA4C;gBAC5C,IAAI,QAAQ,CAAC,qBAAqB,KAAK,QAAQ;oBAC3C,OAAO;gBAEX,YAAY,CAAC,IAAI,CAAC,CAAC,QAAQ,CAAC,UAAU,EAAE,QAAQ,CAAC,qBAAqB,CAAC,UAAU,CAAC,CAAC,CAAC;YACxF,CAAC,CAAC,CAAC;YACH,OAAO,YAAY,CAAC;QACxB,CAAC,EAAE,EAAgB,CAAC,CAAC;IACzB,CAAC;IAED;;;;OAIG;IACO,2CAAQ,GAAlB,UAAmB,KAAc;QAE7B,SAAS,WAAW,CAAC,GAAU;YAC3B,IAAI,GAAG,GAAG,EAAE,CAAC;YACb,KAAK,IAAI,GAAC,GAAG,CAAC,EAAE,GAAG,GAAG,GAAG,CAAC,MAAM,EAAE,GAAC,GAAG,GAAG,EAAE,GAAC,EAAE,EAAE;gBAC5C,IAAI,IAAI,GAAQ,GAAG,CAAC,GAAC,CAAC,CAAC;gBACvB,IAAI,GAAG,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC;oBAAE,GAAG,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC;gBAChD,IAAI,GAAG,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC;oBAAE,GAAG,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC;aACnD;YACD,OAAO,GAAG,CAAC;QACf,CAAC;QAED,IAAM,KAAK,GAAG,WAAW,CAAC,KAAK,CAAC,CAAC;QACjC,IAAI,MAAM,GAAG,KAAK,CAAC,MAAM,EACnB,MAAM,GAAG,IAAI,KAAK,CAAC,MAAM,CAAC,EAC1B,OAAO,GAAQ,EAAE,EACjB,CAAC,GAAG,MAAM,CAAC;QAEjB,OAAO,CAAC,EAAE,EAAE;YACR,IAAI,CAAC,OAAO,CAAC,CAAC,CAAC;gBAAE,KAAK,CAAC,KAAK,CAAC,CAAC,CAAC,EAAE,CAAC,EAAE,EAAE,CAAC,CAAC;SAC3C;QAED,SAAS,KAAK,CAAC,IAAS,EAAE,CAAS,EAAE,YAAmB;YACpD,IAAI,YAAY,CAAC,OAAO,CAAC,IAAI,CAAC,IAAI,CAAC,EAAE;gBACjC,MAAM,IAAI,KAAK,CAAC,qBAAqB,GAAG,IAAI,CAAC,SAAS,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,qBAAqB;aACvF;YAED,IAAI,CAAC,CAAC,KAAK,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;gBACvB,MAAM,IAAI,KAAK,CAAC,8EAA8E,GAAG,IAAI,CAAC,SAAS,CAAC,IAAI,CAAC,CAAC,CAAC;aAC1H;YAED,IAAI,OAAO,CAAC,CAAC,CAAC;gBAAE,OAAO;YACvB,OAAO,CAAC,CAAC,CAAC,GAAG,IAAI,CAAC;YAElB,iBAAiB;YACjB,IAAI,QAAQ,GAAG,KAAK,CAAC,MAAM,CAAC,UAAS,IAAI;gBACrC,OAAO,IAAI,CAAC,CAAC,CAAC,KAAK,IAAI,CAAC;YAC5B,CAAC,CAAC,CAAC;YACH,IAAI,CAAC,GAAG,QAAQ,CAAC,MAAM,EAAE;gBACrB,IAAI,KAAK,GAAG,YAAY,CAAC,MAAM,CAAC,IAAI,CAAC,CAAC;gBACtC,GAAG;oBACC,IAAI,KAAK,GAAG,QAAQ,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;oBAC7B,KAAK,CAAC,KAAK,EAAE,KAAK,CAAC,OAAO,CAAC,KAAK,CAAC,EAAE,KAAK,CAAC,CAAC;iBAC7C,QAAQ,CAAC,EAAE;aACf;YAED,MAAM,CAAC,EAAE,MAAM,CAAC,GAAG,IAAI,CAAC;QAC5B,CAAC;QAED,OAAO,MAAM,CAAC;IAClB,CAAC;IAEL,+BAAC;AAAD,CArMA,AAqMC,IAAA","file":"SubjectTopoligicalSorter.js","sourcesContent":["import {Subject} from \"./Subject\";\nimport {EntityMetadata} from \"../metadata/EntityMetadata\";\n\n/**\n * Orders insert or remove subjects in proper order (using topological sorting)\n * to make sure insert or remove operations are executed in a proper order.\n */\nexport class SubjectTopoligicalSorter {\n\n // -------------------------------------------------------------------------\n // Public Properties\n // -------------------------------------------------------------------------\n\n /**\n * Insert subjects needs to be sorted.\n */\n subjects: Subject[];\n\n /**\n * Unique list of entity metadatas of this subject.\n */\n metadatas: EntityMetadata[];\n\n // -------------------------------------------------------------------------\n // Constructor\n // -------------------------------------------------------------------------\n\n constructor(subjects: Subject[]) {\n this.subjects = [...subjects]; // copy subjects to prevent changing of sent array\n this.metadatas = this.getUniqueMetadatas(this.subjects);\n }\n\n // -------------------------------------------------------------------------\n // Public Methods\n // -------------------------------------------------------------------------\n\n /**\n * Sorts (orders) subjects in their topological order.\n */\n sort(direction: \"insert\"|\"delete\"): Subject[] {\n\n // if there are no metadatas it probably mean there is no subjects... we don't have to do anything here\n if (!this.metadatas.length)\n return this.subjects;\n\n const sortedSubjects: Subject[] = [];\n\n // first if we sort for deletion all junction subjects\n // junction subjects are subjects without entity and database entity set\n if (direction === \"delete\") {\n const junctionSubjects = this.subjects.filter(subject => !subject.entity && !subject.databaseEntity);\n sortedSubjects.push(...junctionSubjects);\n this.removeAlreadySorted(junctionSubjects);\n }\n\n // next we always insert entities with non-nullable relations, sort them first\n const nonNullableDependencies = this.getNonNullableDependencies();\n let sortedNonNullableEntityTargets = this.toposort(nonNullableDependencies);\n if (direction === \"insert\")\n sortedNonNullableEntityTargets = sortedNonNullableEntityTargets.reverse();\n\n // so we have a sorted entity targets\n // go thought each of them and find all subjects with sorted entity target\n // add those sorted targets and remove them from original array of targets\n sortedNonNullableEntityTargets.forEach(sortedEntityTarget => {\n const entityTargetSubjects = this.subjects.filter(subject => subject.metadata.targetName === sortedEntityTarget);\n sortedSubjects.push(...entityTargetSubjects);\n this.removeAlreadySorted(entityTargetSubjects);\n });\n\n // next sort all other entities\n // same process as in above but with other entities\n const otherDependencies: string[][] = this.getDependencies();\n let sortedOtherEntityTargets = this.toposort(otherDependencies);\n if (direction === \"insert\")\n sortedOtherEntityTargets = sortedOtherEntityTargets.reverse();\n\n sortedOtherEntityTargets.forEach(sortedEntityTarget => {\n const entityTargetSubjects = this.subjects.filter(subject => subject.metadata.targetName === sortedEntityTarget);\n sortedSubjects.push(...entityTargetSubjects);\n this.removeAlreadySorted(entityTargetSubjects);\n });\n\n // if we have something left in the subjects add them as well\n sortedSubjects.push(...this.subjects);\n return sortedSubjects;\n }\n\n // -------------------------------------------------------------------------\n // Protected Methods\n // -------------------------------------------------------------------------\n\n /**\n * Removes already sorted subjects from this.subjects list of subjects.\n */\n protected removeAlreadySorted(subjects: Subject[]) {\n subjects.forEach(subject => {\n this.subjects.splice(this.subjects.indexOf(subject), 1);\n });\n }\n\n /**\n * Extracts all unique metadatas from the given subjects.\n */\n protected getUniqueMetadatas(subjects: Subject[]) {\n const metadatas: EntityMetadata[] = [];\n subjects.forEach(subject => {\n if (metadatas.indexOf(subject.metadata) === -1)\n metadatas.push(subject.metadata);\n });\n return metadatas;\n }\n\n /**\n * Gets dependency tree for all entity metadatas with non-nullable relations.\n * We need to execute insertions first for entities which non-nullable relations.\n */\n protected getNonNullableDependencies(): string[][] {\n return this.metadatas.reduce((dependencies, metadata) => {\n metadata.relationsWithJoinColumns.forEach(relation => {\n if (relation.isNullable)\n return;\n\n dependencies.push([metadata.targetName, relation.inverseEntityMetadata.targetName]);\n });\n return dependencies;\n }, [] as string[][]);\n }\n\n /**\n * Gets dependency tree for all entity metadatas with non-nullable relations.\n * We need to execute insertions first for entities which non-nullable relations.\n */\n protected getDependencies(): string[][] {\n return this.metadatas.reduce((dependencies, metadata) => {\n metadata.relationsWithJoinColumns.forEach(relation => {\n\n // if relation is self-referenced we skip it\n if (relation.inverseEntityMetadata === metadata)\n return;\n\n dependencies.push([metadata.targetName, relation.inverseEntityMetadata.targetName]);\n });\n return dependencies;\n }, [] as string[][]);\n }\n\n /**\n * Sorts given graph using topological sorting algorithm.\n *\n * Algorithm is kindly taken from https://github.com/marcelklehr/toposort repository.\n */\n protected toposort(edges: any[][]) {\n\n function uniqueNodes(arr: any[]) {\n let res = [];\n for (let i = 0, len = arr.length; i < len; i++) {\n let edge: any = arr[i];\n if (res.indexOf(edge[0]) < 0) res.push(edge[0]);\n if (res.indexOf(edge[1]) < 0) res.push(edge[1]);\n }\n return res;\n }\n\n const nodes = uniqueNodes(edges);\n let cursor = nodes.length\n , sorted = new Array(cursor)\n , visited: any = {}\n , i = cursor;\n\n while (i--) {\n if (!visited[i]) visit(nodes[i], i, []);\n }\n\n function visit(node: any, i: number, predecessors: any[]) {\n if (predecessors.indexOf(node) >= 0) {\n throw new Error(\"Cyclic dependency: \" + JSON.stringify(node)); // todo: better error\n }\n\n if (!~nodes.indexOf(node)) {\n throw new Error(\"Found unknown node. Make sure to provided all involved nodes. Unknown node: \" + JSON.stringify(node));\n }\n\n if (visited[i]) return;\n visited[i] = true;\n\n // outgoing edges\n let outgoing = edges.filter(function(edge) {\n return edge[0] === node;\n });\n if (i = outgoing.length) {\n let preds = predecessors.concat(node);\n do {\n let child = outgoing[--i][1];\n visit(child, nodes.indexOf(child), preds);\n } while (i);\n }\n\n sorted[--cursor] = node;\n }\n\n return sorted;\n }\n\n}"],"sourceRoot":".."}
|
