Order of referenced child deletions not correct when referencing to itself #10348

Toflar · 2022-12-29T17:03:59Z

Bug Report

Q	A
BC Break	no
Version	2.14.0

Summary

The order in which the UoW wants to delete children is somehow missing a dependency when there is an association to the same class even if you specified cascade: ['remove'].
Given you have

Parent -> has an association to children with cascade: ['remove']
Child 1
Child 2 -> has an association to Child 1 with cascade: ['remove'].

Now you delete the parent.
Doctrine tries to remove Child 1 first instead of Child 2 causing a foreign constraint violation:

Uncaught PDOException: SQLSTATE[23000]: Integrity constraint violation: 1451 Cannot delete or update a parent row: a foreign key constraint fails (test.child_entities, CONSTRAINT FK_DAEB194156A273CC FOREIGN KEY (origin_id) REFERENCES child_entities (id))

How to reproduce

I've created a test setup because I'm not familiar with the internals of ORM at all. So here we go:

Clone https://github.com/Toflar/doctrine-orm-bug-reproducer
Run composer install
Adjust dummy mysql connection example in bootstrap.php.
Run bin/doctrine orm:schema-tool:drop --force && bin/doctrine orm:schema-tool:create
Run php test.php.

Expected behavior

It should not throw an exception. Doctrine should remove Child 2 first.

The text was updated successfully, but these errors were encountered:

simonberger · 2023-01-02T10:35:55Z

This test is based on @Toflar ' s reproducer and can be picked up:
simonberger@2abff4c
I could also create a PR if requested. It fails with mysql but works with sqlite. I didn't test further.
It is no new bug and happened also in 2.11.

Toflar · 2023-01-02T12:07:43Z

Thanks <3 Maybe sqlite is configured without foreign key support in the CI? 🤔

simonberger · 2023-01-02T12:15:36Z

I just tested local on mac. This could be the reason. Maybe it even fails in CI. :)
I am interested to know and created the PR. We can close it again after seeing the results.

EDIT:
Sqlite succeeds also in the CI. MariaDB, PostgreSQL and MySQL all fail.

mpdude · 2023-02-27T18:00:53Z

@Toflar could you please have a look at #10547?

I am not too confident it might fix this issue here, since I do not know if all the entities that need to be cascade-deleted are put into the \Doctrine\ORM\UnitOfWork::$entityDeletions list before the commit order is computed.

But anyway, you might want to give it a shot.

mpdude · 2023-02-28T09:14:27Z

Ah, maybe this is #10548?

Toflar · 2023-02-28T09:29:12Z

Hey @mpdude wow, the other PR is some impressive work! Maybe we can pick up @simonberger's reproducer (simonberger@2abff4c) in the CI as well, then we know if your PR fixes the problem :)

simonberger · 2023-03-05T19:27:52Z

@mpdude Looks good that this issue is covered by your fix. I ran the tests on your branch and it succeeded.
I created a PR on your branch or just add it manually if you like.
mpdude#2

mpdude · 2023-03-05T20:51:04Z

That's great news, although I am not sure if that's by incident. But I have this issue on my shortlist and think it can be fixed as well.

For the delete case, we need not look out for nullable associations (like we do at insert time), but find the associations that use SET NULL as candidates for breaking cycles.

simonberger · 2023-03-05T21:27:40Z

While I don't have much knowledge about the implementation, the test at least looked senseful to me and should have some validity.

mpdude · 2023-03-05T22:21:49Z

Definitely, it is! I did not want to put that into question, sorry if it sounded like that.

My thinking was that I see another problematic case pointed out by this issue here, and I think #10547 does not address this precisely enough. I’ll see if I can fine-tune the test a little to make it fail until that situation is addressed as well.

Thank you for the PR against my branch, that helps.

simonberger · 2023-03-05T22:29:23Z

I also didn't read it like this and the tests are from toflar, I just converted them to phpunit.

mpdude · 2023-03-06T08:15:01Z

I've taken a closer look at this and in fact, what you've found here is a variant of the deletion case from #10531:

graph LR;
    Child1 --> Parent;
    Child2 --> Parent;
    Child2 --> Child1;

Both associations (from Child to Parent as well as from Child to Child) are cascade: delete, so trying to delete the Parent instance will setup the entire graph for deletion.

All associations are nullable in the database, but that's of no relevance for the delete case, since the ORM does not currently use an "extra update" before DELETE to break cycles.

There is no database-level ON DELETE SET NULL, so the ORM will have to find a valid deletion order by itself.

This is, in fact, possible by working through Child2, Child1, Parent. But, the current 2.14.x code only looks at associations at the table level, deleting child rows before parent. It does not honor that a particular order must be followed between the entities of the child table itself. This is the #10531 issue, and it will be fixed by #10547.

Co-authored-by: Matthias Pigulla <mp@webfactory.de>

Toflar · 2023-03-06T08:18:45Z

Wohoo! Thanks so much for the investigation and the awesome work - that PR seems to solve a lot of issues! Kudos @mpdude! Let's hope your work can make it to a release soon!

mpdude · 2023-03-06T08:21:01Z

Test case included at 3917692

mpdude · 2023-03-06T10:14:44Z

Indeed there is another bug regarding the delete order, which I have filed as #10566

Co-authored-by: Matthias Pigulla <mp@webfactory.de>

This is part of the series of issues fixed by doctrine#10547. In particular, the changes from doctrine#10566 were relevant. See doctrine#10348 for the bug description. Co-authored-by: Grégoire Paris <postmaster@greg0ire.fr>

Add a test case to show #10348 has been fixed

…ion (#10913) In order to resolve #10348, some changes were included in #10547 to improve the computed _delete_ order for entities. One assumption was that foreign key references with `ON DELETE SET NULL` or `... CASCADE` need not need to be taken into consideration when planning the deletion order, since the RDBMS would unset or cascade-delete such associations by itself when necessary. Only associations that do _not_ use RDBMS-level cascade handling would be sequenced, to make sure the referring entity is deleted before the referred-to one. This assumption is wrong for `ON DELETE CASCADE`. The following examples give reasons why we need to also consider such associations, and in addition, we need to be able to deal with cycles formed by them. In the following diagrams, `odc` means `ON DELETE CASCADE`, and `ref` is a regular foreign key with no extra `ON DELETE` semantics. ```mermaid graph LR; C-->|ref| B; B-->|odc| A; ``` In this example, C must be removed before B and A. If we ignore the B->A dependency in the delete order computation, the result may not to be correct. ACB is not a working solution. ```mermaid graph LR; A-->|odc| B; B-->|odc| A; C-->|ref| B; ``` This is the situation in #10912. We have to deal with a cycle in the graph. C must be removed before A as well as B. If we ignore the B->A dependency (e.g. because we set it to "optional" to get away with the cycle), we might end up with an incorrect order ACB. ```mermaid graph LR; A-->|odc| B; B-->|odc| A; A-->|ref| C; C-->|ref| B; ``` This example has no possible remove order. But, if we treat `odc` edges as optional, A -> C -> B would wrongly be deemed suitable. ```mermaid graph LR; A-->|ref| B; B-->|odc| C; C-->|odc| B; D-->|ref| C; ``` Here, we must first remove A and D in any order; then, B and C in any order. If we treat one of the `odc` edges as optional, we might find the invalid solutions ABDC or DCAB. #### Solution implemented in this PR First, build a graph with a node for every to-be-removed entity, and edges for `ON DELETE CASCADE` associations between those entities. Then, use [Tarjan's algorithm](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) to find strongly connected components (SCCs) in this graph. The significance of SCCs is that whenever we remove one of the entities in a SCC from the database (no matter which one), the DBMS will immediately remove _all_ the other entities of that group as well. For every SCC, pick one (arbitrary) entity from the group to represent all entities of that group. Then, build a second graph. Again we have nodes for all entities that are to be removed. This time, we insert edges for all regular (foreign key) associations and those with `ON DELETE CASCADE`. `ON DELETE SET NULL` can be left out. The edges are not added between the entities themselves, but between the entities representing the respective SCCs. Also, for all non-trivial SCCs (those containing more than a single entity), add dependency edges to indicate that all entities of the SCC shall be processed _after_ the entity representing the group. This is to make sure we do not remove a SCC inadvertedly by removing one of its entities too early. Run a topological sort on the second graph to get the actual delete order. Cycles in this second graph are a problem, there is no delete order. Fixes #10912.

derrabus added the Bug label Dec 29, 2022

simonberger mentioned this issue Jan 2, 2023

Reproduce exception when deleting entity with same class relation #10358

Closed

simonberger mentioned this issue Jan 29, 2023

Fail to load entity that has enum as primary key via ManyToOne association #10471

Closed

mpdude mentioned this issue Feb 27, 2023

Compute the commit order (inserts/deletes) on the entity level #10547

Merged

21 tasks

mpdude added a commit to mpdude/doctrine2 that referenced this issue Mar 6, 2023

Include a functional test for issue doctrine#10348

3917692

Co-authored-by: Matthias Pigulla <mp@webfactory.de>

mpdude added a commit to mpdude/doctrine2 that referenced this issue Mar 11, 2023

Include a functional test for issue doctrine#10348

523e25b

Co-authored-by: Matthias Pigulla <mp@webfactory.de>

mpdude added a commit to mpdude/doctrine2 that referenced this issue Mar 11, 2023

Include a functional test for issue doctrine#10348

95a612a

Co-authored-by: Matthias Pigulla <mp@webfactory.de>

mpdude added a commit to mpdude/doctrine2 that referenced this issue May 31, 2023

Add a test case to show doctrine#10348 has been fixed by doctrine#10566

972b529

mpdude mentioned this issue May 31, 2023

Add a test case to show #10348 has been fixed #10732

Merged

greg0ire added a commit that referenced this issue Jun 2, 2023

Merge pull request #10732 from mpdude/10348-fixed

b5595ca

Add a test case to show #10348 has been fixed

greg0ire closed this as completed Aug 1, 2023

mpdude mentioned this issue Aug 13, 2023

Creation order parent-children inversed #10864

Closed

mpdude mentioned this issue Aug 21, 2023

Include ON DELETE CASCADE associations in the delete order computation #10913

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Order of referenced child deletions not correct when referencing to itself #10348

Order of referenced child deletions not correct when referencing to itself #10348

Toflar commented Dec 29, 2022

simonberger commented Jan 2, 2023 •

edited

Loading

Toflar commented Jan 2, 2023

simonberger commented Jan 2, 2023 •

edited

Loading

mpdude commented Feb 27, 2023

mpdude commented Feb 28, 2023

Toflar commented Feb 28, 2023

simonberger commented Mar 5, 2023 •

edited

Loading

mpdude commented Mar 5, 2023

simonberger commented Mar 5, 2023

mpdude commented Mar 5, 2023

simonberger commented Mar 5, 2023

mpdude commented Mar 6, 2023

Toflar commented Mar 6, 2023

mpdude commented Mar 6, 2023

mpdude commented Mar 6, 2023

Order of referenced child deletions not correct when referencing to itself #10348

Order of referenced child deletions not correct when referencing to itself #10348

Comments

Toflar commented Dec 29, 2022

Bug Report

Summary

How to reproduce

Expected behavior

simonberger commented Jan 2, 2023 • edited Loading

Toflar commented Jan 2, 2023

simonberger commented Jan 2, 2023 • edited Loading

mpdude commented Feb 27, 2023

mpdude commented Feb 28, 2023

Toflar commented Feb 28, 2023

simonberger commented Mar 5, 2023 • edited Loading

mpdude commented Mar 5, 2023

simonberger commented Mar 5, 2023

mpdude commented Mar 5, 2023

simonberger commented Mar 5, 2023

mpdude commented Mar 6, 2023

Toflar commented Mar 6, 2023

mpdude commented Mar 6, 2023

mpdude commented Mar 6, 2023

simonberger commented Jan 2, 2023 •

edited

Loading

simonberger commented Jan 2, 2023 •

edited

Loading

simonberger commented Mar 5, 2023 •

edited

Loading