{"version":3,"sources":["../browser/src/persistence/SubjectTopoligicalSorter.ts"],"names":[],"mappings":"AAEA,OAAO,EAAE,YAAY,EAAE,MAAM,UAAU,CAAA;AAEvC;;;GAGG;AACH,MAAM,OAAO,wBAAwB;IAejC,4EAA4E;IAC5E,cAAc;IACd,4EAA4E;IAE5E,YAAY,QAAmB;QAC3B,IAAI,CAAC,QAAQ,GAAG,CAAC,GAAG,QAAQ,CAAC,CAAA,CAAC,kDAAkD;QAChF,IAAI,CAAC,SAAS,GAAG,IAAI,CAAC,kBAAkB,CAAC,IAAI,CAAC,QAAQ,CAAC,CAAA;IAC3D,CAAC;IAED,4EAA4E;IAC5E,iBAAiB;IACjB,4EAA4E;IAE5E;;OAEG;IACH,IAAI,CAAC,SAA8B;QAC/B,uGAAuG;QACvG,IAAI,CAAC,IAAI,CAAC,SAAS,CAAC,MAAM;YAAE,OAAO,IAAI,CAAC,QAAQ,CAAA;QAEhD,MAAM,cAAc,GAAc,EAAE,CAAA;QAEpC,sDAAsD;QACtD,wEAAwE;QACxE,IAAI,SAAS,KAAK,QAAQ,EAAE,CAAC;YACzB,MAAM,gBAAgB,GAAG,IAAI,CAAC,QAAQ,CAAC,MAAM,CACzC,CAAC,OAAO,EAAE,EAAE,CAAC,CAAC,OAAO,CAAC,MAAM,IAAI,CAAC,OAAO,CAAC,cAAc,CAC1D,CAAA;YACD,cAAc,CAAC,IAAI,CAAC,GAAG,gBAAgB,CAAC,CAAA;YACxC,IAAI,CAAC,mBAAmB,CAAC,gBAAgB,CAAC,CAAA;QAC9C,CAAC;QAED,8EAA8E;QAC9E,MAAM,uBAAuB,GAAG,IAAI,CAAC,0BAA0B,EAAE,CAAA;QACjE,IAAI,8BAA8B,GAAG,IAAI,CAAC,QAAQ,CAC9C,uBAAuB,CAC1B,CAAA;QACD,IAAI,SAAS,KAAK,QAAQ;YACtB,8BAA8B;gBAC1B,8BAA8B,CAAC,OAAO,EAAE,CAAA;QAEhD,qCAAqC;QACrC,0EAA0E;QAC1E,0EAA0E;QAC1E,8BAA8B,CAAC,OAAO,CAAC,CAAC,kBAAkB,EAAE,EAAE;YAC1D,MAAM,oBAAoB,GAAG,IAAI,CAAC,QAAQ,CAAC,MAAM,CAC7C,CAAC,OAAO,EAAE,EAAE,CACR,OAAO,CAAC,QAAQ,CAAC,UAAU,KAAK,kBAAkB;gBAClD,OAAO,CAAC,QAAQ,CAAC,eAAe,CAAC,IAAI,CACjC,CAAC,CAAC,EAAE,EAAE,CAAC,CAAC,CAAC,IAAI,KAAK,kBAAkB,CACvC,CACR,CAAA;YACD,cAAc,CAAC,IAAI,CAAC,GAAG,oBAAoB,CAAC,CAAA;YAC5C,IAAI,CAAC,mBAAmB,CAAC,oBAAoB,CAAC,CAAA;QAClD,CAAC,CAAC,CAAA;QAEF,+BAA+B;QAC/B,mDAAmD;QACnD,MAAM,iBAAiB,GAAe,IAAI,CAAC,eAAe,EAAE,CAAA;QAC5D,IAAI,wBAAwB,GAAG,IAAI,CAAC,QAAQ,CAAC,iBAAiB,CAAC,CAAA;QAC/D,IAAI,SAAS,KAAK,QAAQ;YACtB,wBAAwB,GAAG,wBAAwB,CAAC,OAAO,EAAE,CAAA;QAEjE,wBAAwB,CAAC,OAAO,CAAC,CAAC,kBAAkB,EAAE,EAAE;YACpD,MAAM,oBAAoB,GAAG,IAAI,CAAC,QAAQ,CAAC,MAAM,CAC7C,CAAC,OAAO,EAAE,EAAE,CAAC,OAAO,CAAC,QAAQ,CAAC,UAAU,KAAK,kBAAkB,CAClE,CAAA;YACD,cAAc,CAAC,IAAI,CAAC,GAAG,oBAAoB,CAAC,CAAA;YAC5C,IAAI,CAAC,mBAAmB,CAAC,oBAAoB,CAAC,CAAA;QAClD,CAAC,CAAC,CAAA;QAEF,6DAA6D;QAC7D,cAAc,CAAC,IAAI,CAAC,GAAG,IAAI,CAAC,QAAQ,CAAC,CAAA;QACrC,OAAO,cAAc,CAAA;IACzB,CAAC;IAED,4EAA4E;IAC5E,oBAAoB;IACpB,4EAA4E;IAE5E;;OAEG;IACO,mBAAmB,CAAC,QAAmB;QAC7C,QAAQ,CAAC,OAAO,CAAC,CAAC,OAAO,EAAE,EAAE;YACzB,IAAI,CAAC,QAAQ,CAAC,MAAM,CAAC,IAAI,CAAC,QAAQ,CAAC,OAAO,CAAC,OAAO,CAAC,EAAE,CAAC,CAAC,CAAA;QAC3D,CAAC,CAAC,CAAA;IACN,CAAC;IAED;;OAEG;IACO,kBAAkB,CAAC,QAAmB;QAC5C,MAAM,SAAS,GAAqB,EAAE,CAAA;QACtC,QAAQ,CAAC,OAAO,CAAC,CAAC,OAAO,EAAE,EAAE;YACzB,IAAI,SAAS,CAAC,OAAO,CAAC,OAAO,CAAC,QAAQ,CAAC,KAAK,CAAC,CAAC;gBAC1C,SAAS,CAAC,IAAI,CAAC,OAAO,CAAC,QAAQ,CAAC,CAAA;QACxC,CAAC,CAAC,CAAA;QACF,OAAO,SAAS,CAAA;IACpB,CAAC;IAED;;;OAGG;IACO,0BAA0B;QAChC,OAAO,IAAI,CAAC,SAAS,CAAC,MAAM,CAAC,CAAC,YAAY,EAAE,QAAQ,EAAE,EAAE;YACpD,QAAQ,CAAC,wBAAwB,CAAC,OAAO,CAAC,CAAC,QAAQ,EAAE,EAAE;gBACnD,IAAI,QAAQ,CAAC,UAAU;oBAAE,OAAM;gBAE/B,YAAY,CAAC,IAAI,CAAC;oBACd,QAAQ,CAAC,UAAU;oBACnB,QAAQ,CAAC,qBAAqB,CAAC,UAAU;iBAC5C,CAAC,CAAA;YACN,CAAC,CAAC,CAAA;YACF,OAAO,YAAY,CAAA;QACvB,CAAC,EAAE,EAAgB,CAAC,CAAA;IACxB,CAAC;IAED;;;OAGG;IACO,eAAe;QACrB,OAAO,IAAI,CAAC,SAAS,CAAC,MAAM,CAAC,CAAC,YAAY,EAAE,QAAQ,EAAE,EAAE;YACpD,QAAQ,CAAC,wBAAwB,CAAC,OAAO,CAAC,CAAC,QAAQ,EAAE,EAAE;gBACnD,4CAA4C;gBAC5C,IAAI,QAAQ,CAAC,qBAAqB,KAAK,QAAQ;oBAAE,OAAM;gBAEvD,YAAY,CAAC,IAAI,CAAC;oBACd,QAAQ,CAAC,UAAU;oBACnB,QAAQ,CAAC,qBAAqB,CAAC,UAAU;iBAC5C,CAAC,CAAA;YACN,CAAC,CAAC,CAAA;YACF,OAAO,YAAY,CAAA;QACvB,CAAC,EAAE,EAAgB,CAAC,CAAA;IACxB,CAAC;IAED;;;;OAIG;IACO,QAAQ,CAAC,KAAc;QAC7B,SAAS,WAAW,CAAC,GAAU;YAC3B,IAAI,GAAG,GAAG,EAAE,CAAA;YACZ,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,GAAG,GAAG,GAAG,CAAC,MAAM,EAAE,CAAC,GAAG,GAAG,EAAE,CAAC,EAAE,EAAE,CAAC;gBAC7C,IAAI,IAAI,GAAQ,GAAG,CAAC,CAAC,CAAC,CAAA;gBACtB,IAAI,GAAG,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC;oBAAE,GAAG,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,CAAA;gBAC/C,IAAI,GAAG,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC;oBAAE,GAAG,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,CAAA;YACnD,CAAC;YACD,OAAO,GAAG,CAAA;QACd,CAAC;QAED,MAAM,KAAK,GAAG,WAAW,CAAC,KAAK,CAAC,CAAA;QAChC,IAAI,MAAM,GAAG,KAAK,CAAC,MAAM,EACrB,MAAM,GAAG,IAAI,KAAK,CAAC,MAAM,CAAC,EAC1B,OAAO,GAAQ,EAAE,EACjB,CAAC,GAAG,MAAM,CAAA;QAEd,OAAO,CAAC,EAAE,EAAE,CAAC;YACT,IAAI,CAAC,OAAO,CAAC,CAAC,CAAC;gBAAE,KAAK,CAAC,KAAK,CAAC,CAAC,CAAC,EAAE,CAAC,EAAE,EAAE,CAAC,CAAA;QAC3C,CAAC;QAED,SAAS,KAAK,CAAC,IAAS,EAAE,CAAS,EAAE,YAAmB;YACpD,IAAI,YAAY,CAAC,OAAO,CAAC,IAAI,CAAC,IAAI,CAAC,EAAE,CAAC;gBAClC,MAAM,IAAI,YAAY,CAClB,qBAAqB,GAAG,IAAI,CAAC,SAAS,CAAC,IAAI,CAAC,CAC/C,CAAA,CAAC,qBAAqB;YAC3B,CAAC;YAED,IAAI,CAAC,CAAC,KAAK,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE,CAAC;gBACxB,MAAM,IAAI,YAAY,CAClB,8EAA8E;oBAC1E,IAAI,CAAC,SAAS,CAAC,IAAI,CAAC,CAC3B,CAAA;YACL,CAAC;YAED,IAAI,OAAO,CAAC,CAAC,CAAC;gBAAE,OAAM;YACtB,OAAO,CAAC,CAAC,CAAC,GAAG,IAAI,CAAA;YAEjB,iBAAiB;YACjB,IAAI,QAAQ,GAAG,KAAK,CAAC,MAAM,CAAC,UAAU,IAAI;gBACtC,OAAO,IAAI,CAAC,CAAC,CAAC,KAAK,IAAI,CAAA;YAC3B,CAAC,CAAC,CAAA;YACF,IAAI,CAAC,CAAC,GAAG,QAAQ,CAAC,MAAM,CAAC,EAAE,CAAC;gBACxB,IAAI,KAAK,GAAG,YAAY,CAAC,MAAM,CAAC,IAAI,CAAC,CAAA;gBACrC,GAAG,CAAC;oBACA,IAAI,KAAK,GAAG,QAAQ,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,CAAA;oBAC5B,KAAK,CAAC,KAAK,EAAE,KAAK,CAAC,OAAO,CAAC,KAAK,CAAC,EAAE,KAAK,CAAC,CAAA;gBAC7C,CAAC,QAAQ,CAAC,EAAC;YACf,CAAC;YAED,MAAM,CAAC,EAAE,MAAM,CAAC,GAAG,IAAI,CAAA;QAC3B,CAAC;QAED,OAAO,MAAM,CAAA;IACjB,CAAC;CACJ","file":"SubjectTopoligicalSorter.js","sourcesContent":["import { Subject } from \"./Subject\"\nimport { EntityMetadata } from \"../metadata/EntityMetadata\"\nimport { TypeORMError } from \"../error\"\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    // 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        // 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) 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(\n                (subject) => !subject.entity && !subject.databaseEntity,\n            )\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(\n            nonNullableDependencies,\n        )\n        if (direction === \"insert\")\n            sortedNonNullableEntityTargets =\n                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(\n                (subject) =>\n                    subject.metadata.targetName === sortedEntityTarget ||\n                    subject.metadata.inheritanceTree.some(\n                        (s) => s.name === sortedEntityTarget,\n                    ),\n            )\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(\n                (subject) => subject.metadata.targetName === sortedEntityTarget,\n            )\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) return\n\n                dependencies.push([\n                    metadata.targetName,\n                    relation.inverseEntityMetadata.targetName,\n                ])\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                // if relation is self-referenced we skip it\n                if (relation.inverseEntityMetadata === metadata) return\n\n                dependencies.push([\n                    metadata.targetName,\n                    relation.inverseEntityMetadata.targetName,\n                ])\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        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 TypeORMError(\n                    \"Cyclic dependency: \" + JSON.stringify(node),\n                ) // todo: better error\n            }\n\n            if (!~nodes.indexOf(node)) {\n                throw new TypeORMError(\n                    \"Found unknown node. Make sure to provided all involved nodes. Unknown node: \" +\n                        JSON.stringify(node),\n                )\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":".."}