Restarted zeh build

taking a look at the commit order of the entities in CascadeRemoveOrderTest, they are reversed with this patch on the remove -> flush.

Ok, I've taken a deeper look at why CascadeRemoveOrderTest is failing, and it is as follows:

1. CascadeRemoveOrderEntityO has a nullable FK to CascadeRemoveOrderEntityG
2. CascadeRemoveOrderEntityG has a nullable FK to CascadeRemoveOrderEntityO

This results in the CommitOrderCalculator having a node list of
CascadeRemoveOrderEntityO -> CascadeRemoveOrderEntityG, weight 0
CascadeRemoveOrderEntityG -> CascadeRemoveOrderEntityO, weight 0.

i.e this graph as 2 valid commit orders. It just so happens that with the fix in this PR, the "wrong" one is chosen, but we have no way of knowing it's the wrong/right one.

It seems that CascadeRemoveOrderTest only passes currently on 2.6 by depending on the bug that a non defined nullable is treated as nullable=false.
Indeed, if you add @JoinColumn(nullable=true) to CascadeRemoveOrderEntityG::$ownerO, (essentially changing nothing), CascadeRemoveOrderTest will fail on 2.6/master.

So it seems we need to do something about the test. the fix in this PR seems valid.

Guidance appreciated @Ocramius @lcobucci @guilhermeblanco

I believe that the changes proposed in the PR are not enough to fix the problem, unfortunately.

With this PR applied, the code at https://gist.github.com/arnaud-lb/2ac4a3007bba08ca5f8fa78cfc353cf5 will generate the following graph:

<?php

$calc = new CommitOrderCalculator();

$calc->addNode('A', 'A');
$calc->addNode('B', 'B');
$calc->addNode('C', 'C');

// B referenced by A
$calc->addDependency('B', 'A', 1);

// A referenced by B (nullable)
$calc->addDependency('A', 'B', 0);

// A referenced by C
$calc->addDependency('A', 'C', 1);

The output of $calc->sort() is C, B, A. Since C has a non-nullable reference to A, trying to insert C will not work.

The problems seems to arise from the fact that we are trying to sort a cyclic graph topologically. When the execution reaches a state that shouldn't happen in the orignal algorithm (case self::IN_PROGRESS), the implementation doesn't abort, and nodes may be added to the sorted node list prematurely.

Ignoring the nullable references when building the graph seems to creates an acyclic graph in my case (Is a cycle of non-null references possible?), and the commit order is correct (on a quite complex schema). The order may not be optimal, though, and I don't know if it works for entity removal.

thanks for that @arnaud-lb.
I'll add failing test cases to this PR.

@bendavies I think that we might consider to have a more complicated logic to calculate the weight of the dependencies. I mean, the CommitOrderCalculator is flexible enough to deal with other values (not only 0 and 1) and we might be able to solve this issue by increasing the weight based on certain criteria, like:

$weight = 0;

if ($joinColumnIsNullable) {
    ++$weight;
}

if ($isSomethingElse) {
    ++$weight;
}

// ...

return $weight;

hah, i managed to hack in a fix for @arnaud-lb test/problem.

@lcobucci I'm thinking that CascadeRemoveOrderTest is unsolvable by the CommitOrderCalculator.
CascadeRemoveOrderEntityO has a nullable FK to CascadeRemoveOrderEntityG
CascadeRemoveOrderEntityG has a nullable FK to CascadeRemoveOrderEntityO

O's FK could be populated, which means we need to delete O first, then G.
G's FK could be populated, which means we need to delete G first, then O.
Both O's and G's FK could be populated, in which case neither can be deleted first - It must be a 2 phase flush.

EDIT: I've just seen that CascadeRemoveOrderEntityO has onDelete="SET NULL" on it's FK. Could the CommitOrderCalculator take that into account? However, if it didn't have onDelete="SET NULL", the problem goes back to being unsolvable?

The only think i can think of (but i'm not very familiar with UOW) is to add scheduleExtraUpdate support for nullable foreign keys when removing entities, so you first null the FK, then remove the entity. I'm sure someone more experienced can tell me why that's a stupid idea.

hah, i managed to hack in a fix for @arnaud-lb test/problem.

Awesome! Will it handle cycles involving more than 2 nodes, though?

Sure, here is a new failing test with a 3 nodes cycle: arnaud-lb@c7facac

Thanks @arnaud-ld. What is the correct commit order for that, to save me trying to work it out?

F, E, D, G would work as a commit order. Removing the addDependency() call when $joinColumnsNullable is true yields this order. However, I believe that doing this would cause more scheduleExtraUpdate than necessary with real world entities.

@bendavies I think that we might consider to have a more complicated logic to calculate the weight of the dependencies. I mean, the CommitOrderCalculator is flexible enough to deal with other values (not only 0 and 1)

@lcobucci that opens a can of worms IMO, as we start defining weights without having a clear idea of what the weights actually are.

It must be a 2 phase flush.

These are scenarios in which the ORM should probably kick in at metadata validation time... Would be interesting to see how far we can go with defining the commit order before runtime: possibly a completely different project?

EDIT: I've just seen that CascadeRemoveOrderEntityO has onDelete="SET NULL" on it's FK. Could the CommitOrderCalculator take that into account? However, if it didn't have onDelete="SET NULL", the problem goes back to being unsolvable?

In short: no. Not all RDBMSs in use support onDelete or foreign keys in general. To take a simple one: MySQL's onDelete is already limited to 16 cascades, so it can't really be safely relied upon. We can't rely on that for now, sorry.

@Ocramius thanks for that. Do you have any opinion on CascadeRemoveOrderTest specifically? I still don't think the commit order calculator can determine the correct order for the classes in that test from class metadata alone, as it stands.

Do you have any opinion on CascadeRemoveOrderTest specifically?

It seems like the test was faulty due to missing explicit nullable=true there. Not much to do there: we simply unveiled a hidden issue here. I don't think it should be changed for now, as users might be affected.

I've taken in @arnaud-lb failing tests and added the same scenario to the commit order calculator.
The graph is this:

It's obvious what the path should be from looking at it: F, E, D, G. The commit order calculator isn't currently clever enough to work this out.

As above, at the moment the CommitOrderCalculator is too naive to work out some quite simple graphs.
I have a POC that fixes the above issues and improves the CommitOrderCalculator so that it solves the above graph and more complex ones.

Basically:

1. Find the Minimum spanning tree of the Graph.
2. Perform a Topological Sort of this graph to get your commit order.

Edit: I'm not sure this is appropriate actually. MST is for unidirected graphs while ours is directed.

However, there is a slight complication in that the CommitOrderCalculator could contain multiple unconnected graphs. MST requires a connected graph to perform on.
So before performing MST and sort, the distinct graphs need to be identified, and the above steps performed on each graph.

The sorts of these unconnected graphs can then be returned in any order as they are not dependent.

The above is a not a trivial undertaking so I don't want pursue it if someone thinks it's a bad idea or can see a really simple fix to the current impl that I've overlooked.

If @guilhermeblanco could provide some feedback before I try and take this any further, that would be great, since he implemented the CommitOrderCalculator in its current form.

The commit order calculator isn't currently clever enough to work this out.

@bendavies @Ocramius the commit order calculator knows only about the weight, it wasn't designed to know about the association mapping:

https://github.com/doctrine/doctrine2/blob/77e3e5c96c1beec7b28443c5b59145eeadbc0baf/lib/Doctrine/ORM/Internal/CommitOrderCalculator.php#L143-L148

It may indeed open a can of worms, but if we have issues with the logic which is sending data to the commit order calculator we shouldn't simply change the class (CommitOrderCalculator) but rather that logic.

@lcobucci i think the data provided to the calculator is fine. This graph is simple but isn't solved correctly: #7180 (comment)

What's the status of this bug ? @bendavies you seemed to be on the right path.

My solution wasn't good because MST is for unidirected graphs while ours is directed.

I was waiting for @guilhermeblanco's feedback/help, really.

maybe fixed by #7260

rebased after #7260 was merged

thought i'd take a look at how hibernate handles this. They do it a bit differently.

Doctrine deduces table insert ordering from class metadata, while hibernate orders the inserted entities themselves.

@bendavies how did you go with this?

no further sorry. I think the proper fix would be to copy Hibernate.

Doctrine deduces table insert ordering from class metadata, while hibernate orders the inserted entities themselves.

Still remember what you did 5 years ago? If so, maybe you can help to review #10547.