15219332477

Committed 23 May 2025 09:13PM UTC coverage: 17.216% (-59.1%) from 76.346%

Build # 15219332477

Build Type

Pull #11332

github

Committed by

naorpeled

Commit Message

cr comments - move if block

Pull Request Pull Request #11332: feat: add new undefined and null behavior flags

Run Details

1603 of 12759 branches covered (12.56%)

Branch coverage included in aggregate %.

0 of 31 new or added lines in 3 files covered. (0.0%)

14132 existing lines in 166 files now uncovered.

4731 of 24033 relevant lines covered (19.69%)

60.22 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

53.68

/src/persistence/SubjectTopologicalSorter.ts

import { Subject } from "./Subject"
import { EntityMetadata } from "../metadata/EntityMetadata"
import { TypeORMError } from "../error"

/**
 * Orders insert or remove subjects in proper order (using topological sorting)
 * to make sure insert or remove operations are executed in a proper order.
 */
export class SubjectTopologicalSorter {
    // -------------------------------------------------------------------------
    // Public Properties
    // -------------------------------------------------------------------------

    /**
     * Insert subjects needs to be sorted.
     */
    subjects: Subject[]

    /**
     * Unique list of entity metadatas of this subject.
     */
    metadatas: EntityMetadata[]

    // -------------------------------------------------------------------------
    // Constructor
    // -------------------------------------------------------------------------

    constructor(subjects: Subject[]) {
        this.subjects = [...subjects] // copy subjects to prevent changing of sent array
        this.metadatas = this.getUniqueMetadatas(this.subjects)
    }

    // -------------------------------------------------------------------------
    // Public Methods
    // -------------------------------------------------------------------------

    /**
     * Sorts (orders) subjects in their topological order.
     */
    sort(direction: "insert" | "delete"): Subject[] {
        // if there are no metadatas it probably mean there is no subjects... we don't have to do anything here
        if (!this.metadatas.length) return this.subjects

        const sortedSubjects: Subject[] = []

        // first if we sort for deletion all junction subjects
        // junction subjects are subjects without entity and database entity set
        if (direction === "delete") {
            const junctionSubjects = this.subjects.filter(
                (subject) => !subject.entity && !subject.databaseEntity,
            )
            sortedSubjects.push(...junctionSubjects)
            this.removeAlreadySorted(junctionSubjects)
        }

        // next we always insert entities with non-nullable relations, sort them first
        const nonNullableDependencies = this.getNonNullableDependencies()
        let sortedNonNullableEntityTargets = this.toposort(
            nonNullableDependencies,
        )
        if (direction === "insert")
            sortedNonNullableEntityTargets =
                sortedNonNullableEntityTargets.reverse()

        // so we have a sorted entity targets
        // go thought each of them and find all subjects with sorted entity target
        // add those sorted targets and remove them from original array of targets
        sortedNonNullableEntityTargets.forEach((sortedEntityTarget) => {
            const entityTargetSubjects = this.subjects.filter(
                (subject) =>
                    subject.metadata.targetName === sortedEntityTarget ||
                    subject.metadata.inheritanceTree.some(
                        (s) => s.name === sortedEntityTarget,
                    ),
            )
            sortedSubjects.push(...entityTargetSubjects)
            this.removeAlreadySorted(entityTargetSubjects)
        })

        // next sort all other entities
        // same process as in above but with other entities
        const otherDependencies: string[][] = this.getDependencies()
        let sortedOtherEntityTargets = this.toposort(otherDependencies)
        if (direction === "insert")
            sortedOtherEntityTargets = sortedOtherEntityTargets.reverse()

        sortedOtherEntityTargets.forEach((sortedEntityTarget) => {
            const entityTargetSubjects = this.subjects.filter(
                (subject) => subject.metadata.targetName === sortedEntityTarget,
            )
            sortedSubjects.push(...entityTargetSubjects)
            this.removeAlreadySorted(entityTargetSubjects)
        })

        // if we have something left in the subjects add them as well
        sortedSubjects.push(...this.subjects)
        return sortedSubjects
    }

    // -------------------------------------------------------------------------
    // Protected Methods
    // -------------------------------------------------------------------------

    /**
     * Removes already sorted subjects from this.subjects list of subjects.
     */
    protected removeAlreadySorted(subjects: Subject[]) {
        subjects.forEach((subject) => {
            this.subjects.splice(this.subjects.indexOf(subject), 1)
        })
    }

    /**
     * Extracts all unique metadatas from the given subjects.
     */
    protected getUniqueMetadatas(subjects: Subject[]) {
        const metadatas: EntityMetadata[] = []
        subjects.forEach((subject) => {
            if (metadatas.indexOf(subject.metadata) === -1)
                metadatas.push(subject.metadata)
        })
        return metadatas
    }

    /**
     * Gets dependency tree for all entity metadatas with non-nullable relations.
     * We need to execute insertions first for entities which non-nullable relations.
     */
    protected getNonNullableDependencies(): string[][] {
        return this.metadatas.reduce((dependencies, metadata) => {
            metadata.relationsWithJoinColumns.forEach((relation) => {
                if (relation.isNullable) return

                dependencies.push([
                    metadata.targetName,
                    relation.inverseEntityMetadata.targetName,
                ])
            })
            return dependencies
        }, [] as string[][])
    }

    /**
     * Gets dependency tree for all entity metadatas with non-nullable relations.
     * We need to execute insertions first for entities which non-nullable relations.
     */
    protected getDependencies(): string[][] {
        return this.metadatas.reduce((dependencies, metadata) => {
            metadata.relationsWithJoinColumns.forEach((relation) => {
                // if relation is self-referenced we skip it
                if (relation.inverseEntityMetadata === metadata) return

                dependencies.push([
                    metadata.targetName,
                    relation.inverseEntityMetadata.targetName,
                ])
            })
            return dependencies
        }, [] as string[][])
    }

    /**
     * Sorts given graph using topological sorting algorithm.
     *
     * Algorithm is kindly taken from https://github.com/marcelklehr/toposort repository.
     */
    protected toposort(edges: any[][]) {
        function uniqueNodes(arr: any[]) {
            const res = []
            for (let i = 0, len = arr.length; i < len; i++) {
                const edge: any = arr[i]
                if (res.indexOf(edge[0]) < 0) res.push(edge[0])
                if (res.indexOf(edge[1]) < 0) res.push(edge[1])
            }
            return res
        }

        const nodes = uniqueNodes(edges)
        let cursor = nodes.length,
            sorted = new Array(cursor),
            visited: any = {},
            i = cursor

        while (i--) {
            if (!visited[i]) visit(nodes[i], i, [])
        }

        function visit(node: any, i: number, predecessors: any[]) {
            if (predecessors.indexOf(node) >= 0) {
                throw new TypeORMError(
                    "Cyclic dependency: " + JSON.stringify(node),
                ) // todo: better error
            }

            if (!~nodes.indexOf(node)) {
                throw new TypeORMError(
                    "Found unknown node. Make sure to provided all involved nodes. Unknown node: " +
                        JSON.stringify(node),
                )
            }

            if (visited[i]) return
            visited[i] = true

            // outgoing edges
            const outgoing = edges.filter(function (edge) {
                return edge[0] === node
            })
            if ((i = outgoing.length)) {
                const preds = predecessors.concat(node)
                do {
                    const child = outgoing[--i][1]
                    visit(child, nodes.indexOf(child), preds)
                } while (i)
            }

            sorted[--cursor] = node
        }

        return sorted
    }
}

1	import { Subject } from "./Subject"
2	import { EntityMetadata } from "../metadata/EntityMetadata"
3	import { TypeORMError } from "../error"	1✔
4
5	/**
6	* Orders insert or remove subjects in proper order (using topological sorting)
7	* to make sure insert or remove operations are executed in a proper order.
8	*/
9	export class SubjectTopologicalSorter {	1✔
10	// -------------------------------------------------------------------------
11	// Public Properties
12	// -------------------------------------------------------------------------
13
14	/**
15	* Insert subjects needs to be sorted.
16	*/
17	subjects: Subject[]
18
19	/**
20	* Unique list of entity metadatas of this subject.
21	*/
22	metadatas: EntityMetadata[]
23
24	// -------------------------------------------------------------------------
25	// Constructor
26	// -------------------------------------------------------------------------
27
28	constructor(subjects: Subject[]) {
29	this.subjects = [...subjects] // copy subjects to prevent changing of sent array	222✔
30	this.metadatas = this.getUniqueMetadatas(this.subjects)	222✔
31	}
32
33	// -------------------------------------------------------------------------
34	// Public Methods
35	// -------------------------------------------------------------------------
36
37	/**
38	* Sorts (orders) subjects in their topological order.
39	*/
40	sort(direction: "insert" \| "delete"): Subject[] {
41	// if there are no metadatas it probably mean there is no subjects... we don't have to do anything here
42	if (!this.metadatas.length) return this.subjects	222✔
43
44	const sortedSubjects: Subject[] = []	96✔
45
46	// first if we sort for deletion all junction subjects
47	// junction subjects are subjects without entity and database entity set
48	if (direction === "delete") {	96✔
49	const junctionSubjects = this.subjects.filter(	4✔
50	(subject) => !subject.entity && !subject.databaseEntity,	4!
51	)
52	sortedSubjects.push(...junctionSubjects)	4✔
53	this.removeAlreadySorted(junctionSubjects)	4✔
54	}
55
56	// next we always insert entities with non-nullable relations, sort them first
57	const nonNullableDependencies = this.getNonNullableDependencies()	96✔
58	let sortedNonNullableEntityTargets = this.toposort(	96✔
59	nonNullableDependencies,
60	)
61	if (direction === "insert")	96✔
62	sortedNonNullableEntityTargets =	92✔
63	sortedNonNullableEntityTargets.reverse()
64
65	// so we have a sorted entity targets
66	// go thought each of them and find all subjects with sorted entity target
67	// add those sorted targets and remove them from original array of targets
68	sortedNonNullableEntityTargets.forEach((sortedEntityTarget) => {	96✔
UNCOV 69	const entityTargetSubjects = this.subjects.filter(	×
70	(subject) =>
UNCOV 71	subject.metadata.targetName === sortedEntityTarget \|\|	×
72	subject.metadata.inheritanceTree.some(
UNCOV 73	(s) => s.name === sortedEntityTarget,	×
74	),
75	)
UNCOV 76	sortedSubjects.push(...entityTargetSubjects)	×
UNCOV 77	this.removeAlreadySorted(entityTargetSubjects)	×
78	})
79
80	// next sort all other entities
81	// same process as in above but with other entities
82	const otherDependencies: string[][] = this.getDependencies()	96✔
83	let sortedOtherEntityTargets = this.toposort(otherDependencies)	96✔
84	if (direction === "insert")	96✔
85	sortedOtherEntityTargets = sortedOtherEntityTargets.reverse()	92✔
86
87	sortedOtherEntityTargets.forEach((sortedEntityTarget) => {	96✔
UNCOV 88	const entityTargetSubjects = this.subjects.filter(	×
UNCOV 89	(subject) => subject.metadata.targetName === sortedEntityTarget,	×
90	)
UNCOV 91	sortedSubjects.push(...entityTargetSubjects)	×
UNCOV 92	this.removeAlreadySorted(entityTargetSubjects)	×
93	})
94
95	// if we have something left in the subjects add them as well
96	sortedSubjects.push(...this.subjects)	96✔
97	return sortedSubjects	96✔
98	}
99
100	// -------------------------------------------------------------------------
101	// Protected Methods
102	// -------------------------------------------------------------------------
103
104	/**
105	* Removes already sorted subjects from this.subjects list of subjects.
106	*/
107	protected removeAlreadySorted(subjects: Subject[]) {
108	subjects.forEach((subject) => {	4✔
UNCOV 109	this.subjects.splice(this.subjects.indexOf(subject), 1)	×
110	})
111	}
112
113	/**
114	* Extracts all unique metadatas from the given subjects.
115	*/
116	protected getUniqueMetadatas(subjects: Subject[]) {
117	const metadatas: EntityMetadata[] = []	222✔
118	subjects.forEach((subject) => {	222✔
119	if (metadatas.indexOf(subject.metadata) === -1)	256✔
120	metadatas.push(subject.metadata)	96✔
121	})
122	return metadatas	222✔
123	}
124
125	/**
126	* Gets dependency tree for all entity metadatas with non-nullable relations.
127	* We need to execute insertions first for entities which non-nullable relations.
128	*/
129	protected getNonNullableDependencies(): string[][] {
130	return this.metadatas.reduce((dependencies, metadata) => {	96✔
131	metadata.relationsWithJoinColumns.forEach((relation) => {	96✔
UNCOV 132	if (relation.isNullable) return	×
133
UNCOV 134	dependencies.push([	×
135	metadata.targetName,
136	relation.inverseEntityMetadata.targetName,
137	])
138	})
139	return dependencies	96✔
140	}, [] as string[][])
141	}
142
143	/**
144	* Gets dependency tree for all entity metadatas with non-nullable relations.
145	* We need to execute insertions first for entities which non-nullable relations.
146	*/
147	protected getDependencies(): string[][] {
148	return this.metadatas.reduce((dependencies, metadata) => {	96✔
149	metadata.relationsWithJoinColumns.forEach((relation) => {	96✔
150	// if relation is self-referenced we skip it
UNCOV 151	if (relation.inverseEntityMetadata === metadata) return	×
152
UNCOV 153	dependencies.push([	×
154	metadata.targetName,
155	relation.inverseEntityMetadata.targetName,
156	])
157	})
158	return dependencies	96✔
159	}, [] as string[][])
160	}
161
162	/**
163	* Sorts given graph using topological sorting algorithm.
164	*
165	* Algorithm is kindly taken from https://github.com/marcelklehr/toposort repository.
166	*/
167	protected toposort(edges: any[][]) {
168	function uniqueNodes(arr: any[]) {
169	const res = []	192✔
170	for (let i = 0, len = arr.length; i < len; i++) {	192✔
UNCOV 171	const edge: any = arr[i]	×
UNCOV 172	if (res.indexOf(edge[0]) < 0) res.push(edge[0])	×
UNCOV 173	if (res.indexOf(edge[1]) < 0) res.push(edge[1])	×
174	}
175	return res	192✔
176	}
177
178	const nodes = uniqueNodes(edges)	192✔
179	let cursor = nodes.length,	192✔
180	sorted = new Array(cursor),	192✔
181	visited: any = {},	192✔
182	i = cursor	192✔
183
184	while (i--) {	192✔
UNCOV 185	if (!visited[i]) visit(nodes[i], i, [])	×
186	}
187
188	function visit(node: any, i: number, predecessors: any[]) {
UNCOV 189	if (predecessors.indexOf(node) >= 0) {	×
190	throw new TypeORMError(	×
191	"Cyclic dependency: " + JSON.stringify(node),
192	) // todo: better error
193	}
194
UNCOV 195	if (!~nodes.indexOf(node)) {	×
196	throw new TypeORMError(	×
197	"Found unknown node. Make sure to provided all involved nodes. Unknown node: " +
198	JSON.stringify(node),
199	)
200	}
201
UNCOV 202	if (visited[i]) return	×
UNCOV 203	visited[i] = true	×
204
205	// outgoing edges
UNCOV 206	const outgoing = edges.filter(function (edge) {	×
UNCOV 207	return edge[0] === node	×
208	})
UNCOV 209	if ((i = outgoing.length)) {	×
UNCOV 210	const preds = predecessors.concat(node)	×
UNCOV 211	do {	×
UNCOV 212	const child = outgoing[--i][1]	×
UNCOV 213	visit(child, nodes.indexOf(child), preds)	×
214	} while (i)
215	}
216
UNCOV 217	sorted[--cursor] = node	×
218	}
219
220	return sorted	192✔
221	}
222	}

typeorm / typeorm / 15219332477

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous