Author: clr
Date: Tue Jul 17 16:56:45 2007
New Revision: 557089
URL: http://svn.apache.org/viewvc?view=rev&rev=557089
Log:
OPENJPA-235 break-nullable-patch contributed by Markus Fuchs
Added:
openjpa/trunk/openjpa-lib/src/main/resources/org/apache/openjpa/lib/graph/
openjpa/trunk/openjpa-lib/src/main/resources/org/apache/openjpa/lib/graph/localizer.properties
(with props)
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityE.java
(with props)
Modified:
openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java
openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/schema/ForeignKey.java
openjpa/trunk/openjpa-jdbc/src/main/resources/org/apache/openjpa/jdbc/kernel/localizer.properties
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityB.java
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityC.java
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityD.java
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/TestNoForeignKeyViolation.java
Modified:
openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java
(original)
+++
openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/kernel/ConstraintUpdateManager.java
Tue Jul 17 16:56:45 2007
@@ -24,6 +24,7 @@
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
+import java.util.List;
import java.util.Map;
import org.apache.openjpa.jdbc.meta.ClassMapping;
@@ -43,6 +44,7 @@
import org.apache.openjpa.lib.util.Localizer;
import org.apache.openjpa.util.InternalException;
import org.apache.openjpa.util.OpenJPAException;
+import org.apache.openjpa.util.UserException;
/**
* <p>Standard update manager, capable of foreign key constraint
evaluation.</p>
@@ -163,7 +165,7 @@
row2 = getInsertRow(insertMap, rowMgr, row);
if (row2 != null) {
ignoreUpdates = false;
- graphs[1] = addEdge(graphs[1], row, (PrimaryRow) row2,
null);
+ graphs[1] = addEdge(graphs[1], (PrimaryRow) row2, row,
null);
}
// now check this row's fks against other deletes
@@ -180,7 +182,7 @@
row2 = rowMgr.getRow(fks[j].getPrimaryKeyTable(),
Row.ACTION_DELETE, fkVal, false);
if (row2 != null && row2.isValid() && row2 != row)
- graphs[1] = addEdge(graphs[1], row, (PrimaryRow)
row2,
+ graphs[1] = addEdge(graphs[1], (PrimaryRow) row2,
row,
fks[j]);
}
}
@@ -249,7 +251,7 @@
Row.ACTION_INSERT, row.getForeignKeySet(fks[j]),
false);
if (row2 != null && row2.isValid() && (row2 != row
|| fks[j].isDeferred() || fks[j].isLogical()))
- graph = addEdge(graph, (PrimaryRow) row2, row,
fks[j]);
+ graph = addEdge(graph, row, (PrimaryRow) row2,
fks[j]);
}
// see if there are any relation id columns dependent on
@@ -263,7 +265,7 @@
row2 = rowMgr.getRow(getBaseTable(sm), Row.ACTION_INSERT,
sm, false);
if (row2 != null && row2.isValid())
- graph = addEdge(graph, (PrimaryRow) row2, row,
cols[j]);
+ graph = addEdge(graph, row, (PrimaryRow) row2,
cols[j]);
}
}
return graph;
@@ -318,80 +320,205 @@
return;
DepthFirstAnalysis dfa = newDepthFirstAnalysis(graph,
autoAssign);
+ Collection insertUpdates = new LinkedList();
+ Collection deleteUpdates = new LinkedList();
+ boolean recalculate;
+
+ // Handle circular constraints:
+ // - if deleted row A has a ciricular fk to deleted row B,
+ // then use an update statement to null A's fk to B before
flushing,
+ // and then flush
+ // - if inserted row A has a circular fk to updated/inserted row
B,
+ // then null the fk in the B row object, then flush,
+ // and after flushing, use an update to set the fk back to A
+ // Depending on where circular dependencies are broken, the
+ // topological order of the graph nodes has to be re-calculated.
+ recalculate = resolveCycles(graph, dfa.getEdges(Edge.TYPE_BACK),
+ deleteUpdates, insertUpdates);
+ recalculate |= resolveCycles(graph, dfa.getEdges(
Edge.TYPE_FORWARD),
+ deleteUpdates, insertUpdates);
+
+ if (recalculate) {
+ dfa = recalculateDepthFirstAnalysis(graph, autoAssign);
+ }
+
+ // flush delete updates to null fks, then all rows in order, then
+ // the insert updates to set circular fk values
+ flush(deleteUpdates, psMgr);
Collection nodes = dfa.getSortedNodes();
- Collection backs = dfa.getEdges(Edge.TYPE_BACK);
+ for (Iterator itr = nodes.iterator(); itr.hasNext();)
+ psMgr.flush((RowImpl) itr.next());
+ flush(insertUpdates, psMgr);
+ }
- // handle circular constraints:
- // - if deleted row A has a ciricular fk to deleted row B, then
use an
- // update statement to null A's fk to B
- // - if inserted row A has a circular fk to updated/inserted row
B,
- // then null the fk in the B row object, and after flushing,
use
- // an update to set the fk to back to A
- Collection insertUpdates = null;
- Collection deleteUpdates = null;
+ /**
+ * Break a circular dependency caused by delete operations.
+ * If deleted row A has a ciricular fk to deleted row B, then use an
update
+ * statement to null A's fk to B before deleting B, then delete A.
+ * @param edge Edge in the dependency graph corresponding to a
foreign key
+ * constraint. This dependency is broken by nullifying the foreign
key.
+ * @param deleteUpdates Collection of update statements that are
executed
+ * before the delete operations are flushed
+ */
+ private void addDeleteUpdate(Edge edge, Collection deleteUpdates)
+ throws SQLException {
PrimaryRow row;
RowImpl update;
- Edge edge;
+ ForeignKey fk;
+
+ // copy where conditions into new update that nulls the fk
+ row = (PrimaryRow) edge.getTo();
+ update = new PrimaryRow(row.getTable(), Row.ACTION_UPDATE, null);
+ row.copyInto(update, true);
+ if (edge.getUserObject() instanceof ForeignKey) {
+ fk = (ForeignKey) edge.getUserObject();
+ update.setForeignKey(fk, row.getForeignKeyIO(fk), null);
+ } else
+ update.setNull((Column) edge.getUserObject());
+
+ deleteUpdates.add(update);
+ }
+
+ /**
+ * Break a circular dependency caused by insert operations.
+ * If inserted row A has a circular fk to updated/inserted row B,
+ * then null the fk in the B row object, then flush,
+ * and after flushing, use an update to set the fk back to A.
+ * @param row Row to be flushed
+ * @param edge Edge in the dependency graph corresponding to a
foreign key
+ * constraint. This dependency is broken by nullifying the foreign
key.
+ * @param insertUpdates Collection of update statements that are
executed
+ * after the insert/update operations are flushed
+ */
+ private void addInsertUpdate(PrimaryRow row, Edge edge,
+ Collection insertUpdates) throws SQLException {
+ RowImpl update;
ForeignKey fk;
Column col;
- for (Iterator itr = backs.iterator(); itr.hasNext();) {
- edge = (Edge) itr.next();
- if (edge.getUserObject() == null)
- throw new InternalException(_loc.get("del-ins-cycle"));
-
- // use a primary row update to prevent setting pk and fk
values
- // until after flush, to get latest auto-increment values
- row = (PrimaryRow) edge.getTo();
- if (row.getAction() == Row.ACTION_DELETE) {
- // copy where conditions into new update that nulls the
fk
- row = (PrimaryRow) edge.getFrom();
- update = new PrimaryRow(row.getTable(), Row.ACTION_UPDATE
,null);
- row.copyInto(update, true);
- if (edge.getUserObject() instanceof ForeignKey) {
- fk = (ForeignKey) edge.getUserObject();
- update.setForeignKey(fk, row.getForeignKeyIO(fk),
null);
- } else
- update.setNull((Column) edge.getUserObject());
-
- if (deleteUpdates == null)
- deleteUpdates = new LinkedList();
- deleteUpdates.add(update);
- } else {
- // copy where conditions into new update that sets the fk
- update = new PrimaryRow(row.getTable(), Row.ACTION_UPDATE
,null);
- if (row.getAction() == Row.ACTION_INSERT) {
- if (row.getPrimaryKey() == null)
- throw new
InternalException(_loc.get("ref-cycle"));
- update.wherePrimaryKey(row.getPrimaryKey());
- } else
- row.copyInto(update, true);
- if (edge.getUserObject() instanceof ForeignKey) {
- fk = (ForeignKey) edge.getUserObject();
- update.setForeignKey(fk, row.getForeignKeyIO(fk),
- row.getForeignKeySet(fk));
- row.clearForeignKey(fk);
- } else {
- col = (Column) edge.getUserObject();
- update.setRelationId(col, row.getRelationIdSet(col),
- row.getRelationIdCallback(col));
- row.clearRelationId(col);
- }
- if (insertUpdates == null)
- insertUpdates = new LinkedList();
- insertUpdates.add(update);
+ // copy where conditions into new update that sets the fk
+ update = new PrimaryRow(row.getTable(), Row.ACTION_UPDATE, null);
+ if (row.getAction() == Row.ACTION_INSERT) {
+ if (row.getPrimaryKey() == null)
+ throw new InternalException(_loc.get("ref-cycle"));
+ update.wherePrimaryKey(row.getPrimaryKey());
+ } else {
+ // Row.ACTION_UPDATE
+ row.copyInto(update, true);
+ }
+ if (edge.getUserObject() instanceof ForeignKey) {
+ fk = (ForeignKey) edge.getUserObject();
+ update.setForeignKey(fk, row.getForeignKeyIO(fk),
+ row.getForeignKeySet(fk));
+ row.clearForeignKey(fk);
+ } else {
+ col = (Column) edge.getUserObject();
+ update.setRelationId(col, row.getRelationIdSet(col),
+ row.getRelationIdCallback(col));
+ row.clearRelationId(col);
+ }
+
+ insertUpdates.add(update);
+ }
+
+ /**
+ * Finds a nullable foreign key by walking the dependency cycle.
+ * Circular dependencies can be broken at this point.
+ * @param cycle Cycle in the dependency graph.
+ * @return Edge corresponding to a nullable foreign key.
+ */
+ private Edge findBreakableLink(List cycle) {
+ Edge breakableLink = null;
+ for (Iterator iter = cycle.iterator(); iter.hasNext(); ) {
+ Edge edge = (Edge) iter.next();
+ Object userObject = edge.getUserObject();
+ if (userObject instanceof ForeignKey) {
+ if (!((ForeignKey) userObject).hasNotNullColumns()) {
+ breakableLink = edge;
+ break;
+ }
+ } else if (userObject instanceof Column) {
+ if (!((Column) userObject).isNotNull()) {
+ breakableLink = edge;
+ break;
+ }
}
}
+ return breakableLink;
+ }
- // flush delete updates to null fks, then all rows in order, then
- // the insert updates to set circular fk values
- if (deleteUpdates != null)
- flush(deleteUpdates, psMgr);
- for (Iterator itr = nodes.iterator(); itr.hasNext();)
- psMgr.flush((RowImpl) itr.next());
- if (insertUpdates != null)
- flush(insertUpdates, psMgr);
- }
+ /**
+ * Re-calculates the DepthFirstSearch analysis of the graph
+ * after some of the edges have been removed. Ensures
+ * that the dependency graph is cycle free.
+ * @param graph The graph of statements to be walked
+ * @param autoAssign Whether any of the rows in the graph have any
+ * auto-assign constraints
+ */
+ private DepthFirstAnalysis recalculateDepthFirstAnalysis(Graph graph,
+ boolean autoAssign) {
+ DepthFirstAnalysis dfa;
+ // clear previous traversal data
+ graph.clearTraversal();
+ dfa = newDepthFirstAnalysis(graph, autoAssign);
+ // make sure that the graph is non-cyclic now
+ assert (dfa.hasNoCycles()): _loc.get("graph-not-cycle-free");
+ return dfa;
+ }
+
+ /**
+ * Resolve circular dependencies by identifying and breaking
+ * a nullable foreign key.
+ * @param graph Dependency graph.
+ * @param edges Collection of edges. Each edge indicates a possible
+ * circular dependency
+ * @param deleteUpdates Collection of update operations (nullifying
+ * foreign keys) to be filled. These updates will be executed before
+ * the rows in the dependency graph are flushed
+ * @param insertUpdates CCollection of update operations (nullifying
+ * foreign keys) to be filled. These updates will be executed after
+ * the rows in the dependency graph are flushed
+ * @return Depending on where circular dependencies are broken, the
+ * topological order of the graph nodes has to be re-calculated.
+ */
+ private boolean resolveCycles(Graph graph, Collection edges,
+ Collection deleteUpdates, Collection insertUpdates)
+ throws SQLException {
+ boolean recalculate = false;
+ for (Iterator itr = edges.iterator(); itr.hasNext();) {
+ Edge edge = (Edge) itr.next();
+ List cycle = edge.getCycle();
+
+ if (cycle != null) {
+ // find a nullable foreign key
+ Edge breakableLink = findBreakableLink(cycle);
+ if (breakableLink == null) {
+ throw new UserException(_loc.get("no-nullable-fk"));
+ }
+
+ // topologic node order must be re-calculated, if the
+ // breakable link is different from the edge where
+ // the circular dependency was originally detected
+ if (edge != breakableLink) {
+ recalculate = true;
+ }
+
+ if (!breakableLink.isRemovedFromGraph()) {
+
+ // use a primary row update to prevent setting pk and
fk values
+ // until after flush, to get latest auto-increment
values
+ PrimaryRow row = (PrimaryRow) breakableLink.getFrom
();
+ if (row.getAction() == Row.ACTION_DELETE) {
+ addDeleteUpdate(breakableLink, deleteUpdates);
+ } else {
+ addInsertUpdate(row, breakableLink,
insertUpdates);
+ }
+ graph.removeEdge(breakableLink);
+ }
+ }
+ }
+ return recalculate;
+ }
/**
* Create a new [EMAIL PROTECTED] DepthFirstAnalysis} suitable for the
given
graph
Modified:
openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/schema/ForeignKey.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/schema/ForeignKey.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/schema/ForeignKey.java
(original)
+++
openjpa/trunk/openjpa-jdbc/src/main/java/org/apache/openjpa/jdbc/schema/ForeignKey.java
Tue Jul 17 16:56:45 2007
@@ -701,6 +701,19 @@
&& match(getPrimaryKeyColumns(), fkPKCols);
}
+ /**
+ * Checks for non-nullable local columns.
+ */
+ public boolean hasNotNullColumns() {
+ Column[] columns = getColumns();
+ for (int j = 0; j < columns.length; j++) {
+ if (columns[j].isNotNull()) {
+ return true;
+ }
+ }
+ return false;
+ }
+
private static boolean match(Column[] cols, Column[] fkCols) {
if (cols.length != fkCols.length)
return false;
Modified:
openjpa/trunk/openjpa-jdbc/src/main/resources/org/apache/openjpa/jdbc/kernel/localizer.properties
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-jdbc/src/main/resources/org/apache/openjpa/jdbc/kernel/localizer.properties?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-jdbc/src/main/resources/org/apache/openjpa/jdbc/kernel/localizer.properties
(original)
+++
openjpa/trunk/openjpa-jdbc/src/main/resources/org/apache/openjpa/jdbc/kernel/localizer.properties
Tue Jul 17 16:56:45 2007
@@ -98,7 +98,15 @@
\t[-properties/-p <properties file or resource>]\n\
\t[-<property name> <property value>]*
bad-level: Invalid isolation level. Valid levels are -1, \
- Connection.TRANSACTION_NONE, Connection.TRANSACTION_READ_UNCOMMITTED,
\
+ Connection.TRANSACTION_NONE, Connection.TRANSACTION_READ_UNCOMMITTED,
\
Connection.TRANSACTION_READ_COMMITTED, \
Connection.TRANSACTION_REPEATABLE_READ, or \
Connection.TRANSACTION_SERIALIZABLE. Specified value: {0}.
+no-nullable-fk: No nullable foreign key found to resolve circular
flush\n\
+ dependency. During flush processing, changes to instances, new\n\
+ instances, and deleted instances must be processed in a specific
sequence\n\
+ to avoid foreign key constraint violations. The changes required
in this\n\
+ transaction cannot be reordered because none of the foreign key
constraints\n\
+ is nullable (optional).
+graph-not-cycle-free: A circular flush dependency has been found after
all \
+ circular dependencies should have been resolved.
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
(original)
+++
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/DepthFirstAnalysis.java
Tue Jul 17 16:56:45 2007
@@ -18,6 +18,8 @@
*/
package org.apache.openjpa.lib.graph;
+import org.apache.openjpa.lib.util.Localizer;
+
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
@@ -26,6 +28,7 @@
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
+import java.util.LinkedList;
import java.util.List;
import java.util.Map;
@@ -42,6 +45,9 @@
*/
public class DepthFirstAnalysis {
+ private static final Localizer _loc = Localizer.forPackage
+ (DepthFirstAnalysis.class);
+
private final Graph _graph;
private final Map _nodeInfo = new HashMap();
private Comparator _comp;
@@ -65,14 +71,15 @@
node = itr.next();
info = (NodeInfo) _nodeInfo.get(node);
if (info.color == NodeInfo.COLOR_WHITE)
- visit(graph, node, info, 0);
+ visit(graph, node, info, 0, new LinkedList());
}
}
/**
* Visit a node. See Introduction to Algorithms book for details.
*/
- private int visit(Graph graph, Object node, NodeInfo info, int time)
{
+ private int visit(Graph graph, Object node, NodeInfo info, int time,
+ List path) {
// discover node
info.color = NodeInfo.COLOR_GRAY;
@@ -89,14 +96,24 @@
otherInfo = (NodeInfo) _nodeInfo.get(other);
if (otherInfo.color == NodeInfo.COLOR_WHITE) {
// undiscovered node; recurse into it
- childTime = visit(graph, other, otherInfo, time);
+ path.add(edge);
+ childTime = visit(graph, other, otherInfo, time, path);
+ path.remove(edge);
edge.setType(Edge.TYPE_TREE);
} else if (otherInfo.color == NodeInfo.COLOR_GRAY) {
childTime = -1;
edge.setType(Edge.TYPE_BACK);
+ // calculate the cycle including this edge
+ edge.setCycle(cycleForBackEdge(edge, path));
} else {
childTime = otherInfo.finished;
edge.setType(Edge.TYPE_FORWARD);
+ // find the cycle including this edge
+ List cycle = new LinkedList();
+ cycle.add(edge);
+ if (cycleForForwardEdge(graph, other, node, cycle)) {
+ edge.setCycle(cycle);
+ }
}
maxChildTime = Math.max(maxChildTime, childTime);
}
@@ -134,7 +151,7 @@
/**
* Return all edges of the given type. This method can be used to
* discover all edges that cause cycles in the graph by passing it
- * the [EMAIL PROTECTED] #EDGE_BACK} edge type.
+ * the [EMAIL PROTECTED] Edge#TYPE_BACK} or [EMAIL PROTECTED]
Edge#TYPE_FORWARD} edge type.
*/
public Collection getEdges(int type) {
Collection typed = null;
@@ -167,6 +184,132 @@
}
/**
+ * Returns a list of graph edges forming a cycle. The cycle begins
+ * with a type [EMAIL PROTECTED] Edge#TYPE_BACK} edge.
+ * @param backEdge "Starting" edge of the cycle
+ * @param path Continuous list of graph edges, may be null
+ * @param pos Index of the first edge in path continuing the cycle
+ * @return Cycle starting with a type [EMAIL PROTECTED] Edge#TYPE_BACK}
edge
+ */
+ private List buildCycle(Edge backEdge, List path, int pos) {
+ int length = path != null ? path.size() - pos : 0;
+ List cycle = new ArrayList(length + 1);
+ cycle.add(0, backEdge);
+ for (int i = 0; i < length; i++) {
+ cycle.add(i + 1, path.get(pos + i));
+ }
+ return cycle;
+ }
+
+ /**
+ * Computes the list of edges forming a cycle. The cycle always
exists for
+ * a type [EMAIL PROTECTED] Edge#TYPE_BACK} edge. This method should only
be
called
+ * for type [EMAIL PROTECTED] Edge#TYPE_BACK} edges.
+ * @param edge Edge where the cycle was detected
+ * @param path Path consisting of edges to the edge's starting node
+ * @return Cycle starting with a type [EMAIL PROTECTED] Edge#TYPE_BACK}
edge
+ */
+ private List cycleForBackEdge(Edge edge, List path) {
+ if (edge.getType() != Edge.TYPE_BACK) {
+ return null;
+ }
+
+ List cycle;
+ int pos = 0;
+ if (path != null && edge.getFrom() != edge.getTo()) {
+ // Not a single edge loop
+ pos = findNodeInPath(edge.getTo(), path);
+ assert (pos >= 0): _loc.get("node-not-on-path", edge,
edge.getTo());
+ } else {
+ assert (edge.getFrom() == edge.getTo()):
+ _loc.get("edge-no-loop", edge).getMessage();
+ path = null;
+ }
+ cycle = buildCycle(edge, path, pos);
+ assert (cycle != null): _loc.get("cycle-null",
edge).getMessage();
+ return cycle;
+ }
+
+ /**
+ * Computes the cycle of edges including node cycleTo. The cycle must
not
+ * necessarily exist. This method should only be called for type
+ * [EMAIL PROTECTED] Edge#TYPE_FORWARD} edges.
+ * @param graph Graph
+ * @param node Current node
+ * @param cycleTo End node for loop
+ * @param path Path from loop end node to current node
+ * @return True if a cycle has been found. The cycle will be
contained in
+ * the <code>path</code> parameter.
+ */
+ private boolean cycleForForwardEdge(Graph graph, Object node,
+ Object cycleTo, List path) {
+ boolean found = false;
+ Collection edges = graph.getEdgesFrom(node);
+ for (Iterator itr = edges.iterator(); !found && itr.hasNext();) {
+ Edge edge = (Edge) itr.next();
+ Object other = edge.getOther(node);
+ // Single edge loops are ignored
+ if (node != other) {
+ if (other == cycleTo) {
+ // Cycle complete
+ path.add(edge);
+ found = true;
+ } else if (!path.contains(edge)){
+ // Walk this edge
+ path.add(edge);
+ found = cycleForForwardEdge(graph, other, cycleTo,
path);
+ if (!found) {
+ // Remove edge again
+ path.remove(edge);
+ }
+ }
+ }
+ }
+ return found;
+ }
+
+ /**
+ * Finds the position of the edge starting from a particular node in
the
+ * continuous list of edges.
+ * @param node Node on the cycle.
+ * @param path Continuous list of graph edges.
+ * @return Edge index if found, -1 otherwise.
+ */
+ private int findNodeInPath(Object node, List path) {
+ int pos = -1;
+ if (path != null) {
+ for (int i = 0; i < path.size(); i++) {
+ if (((Edge)path.get(i)).getFrom() == node) {
+ pos = i;
+ }
+ }
+ }
+ return pos;
+ }
+
+ /**
+ * Test, if the analysis didn't find cycles.
+ */
+ public boolean hasNoCycles() {
+ // a) there must not be any back edges
+ if (!getEdges(Edge.TYPE_BACK).isEmpty()) {
+ return false;
+ }
+ // b) there might be forward edges
+ // make sure these don't indicate cycles
+ Collection edges = getEdges(Edge.TYPE_FORWARD);
+ if (!edges.isEmpty()) {
+ for (Iterator itr = edges.iterator(); itr.hasNext();) {
+ Edge edge = (Edge) itr.next();
+ if (edge.getCycle() != null) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ /**
* Comparator for toplogically sorting entries in the node info map.
*/
private static class NodeInfoComparator
@@ -184,8 +327,8 @@
NodeInfo n1 = (NodeInfo) e1.getValue();
NodeInfo n2 = (NodeInfo) e2.getValue();
- // reverse finished order
- int ret = n2.finished - n1.finished;
+ // sort by finished order
+ int ret = n1.finished - n2.finished;
if (ret == 0 && _subComp != null)
ret = _subComp.compare(e1.getKey(), e2.getKey());
return ret;
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
(original)
+++
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/graph/Edge.java
Tue Jul 17 16:56:45 2007
@@ -18,6 +18,8 @@
*/
package org.apache.openjpa.lib.graph;
+import java.util.List;
+
/**
* <p>A graph edge. Includes the from and to nodes, an arbitrary user
object,
* and a weight. Edges can be either directed or undirected.</p>
@@ -52,6 +54,8 @@
private int _type = 0;
private double _weight = 0;
private Object _userObj = null;
+ private List _cycle = null;
+ private boolean _removedFromGraph = false;
/**
* Constructor.
@@ -176,10 +180,39 @@
}
/**
+ * List of edges forming a cycle. Only set for TYPE_BACK and
TYPE_FORWARD edges.
+ */
+ public List getCycle() {
+ return _cycle;
+ }
+
+ /**
+ * List of edges forming a cycle. Only set for TYPE_BACK and
TYPE_FORWARD edges.
+ */
+ public void setCycle(List cycle) {
+ _cycle = cycle;
+ }
+
+ /**
+ * Returns if this edge is (still) part of the graph.
+ */
+ public boolean isRemovedFromGraph() {
+ return _removedFromGraph;
+ }
+
+ /**
+ * Mark this edge as removed from the graph.
+ */
+ public void setRemovedFromGraph() {
+ this._removedFromGraph = true;
+ }
+
+ /**
* Clear traversal info.
*/
public void clearTraversal() {
_type = 0;
+ _cycle = null;
}
public String toString() {
Added:
openjpa/trunk/openjpa-lib/src/main/resources/org/apache/openjpa/lib/graph/localizer.properties
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/resources/org/apache/openjpa/lib/graph/localizer.properties?view=auto&rev=557089
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/resources/org/apache/openjpa/lib/graph/localizer.properties
(added)
+++
openjpa/trunk/openjpa-lib/src/main/resources/org/apache/openjpa/lib/graph/localizer.properties
Tue Jul 17 16:56:45 2007
@@ -0,0 +1,22 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+cycle-null: The cycle must not be null for edge {0}!
+edge-no-loop: Edge {0} must be a single node loop, if the depth first
search \
+ path is null!
+node-not-on-path: Could not find node {1} in the depth first search path
\
+ leading to edge {0}!
Propchange:
openjpa/trunk/openjpa-lib/src/main/resources/org/apache/openjpa/lib/graph/localizer.properties
------------------------------------------------------------------------------
svn:eol-style = LF
Modified:
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
(original)
+++
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/graph/TestDepthFirstAnalysis.java
Tue Jul 17 16:56:45 2007
@@ -20,6 +20,7 @@
import java.util.Collection;
import java.util.Iterator;
+import java.util.List;
import org.apache.openjpa.lib.test.AbstractTestCase;
@@ -34,6 +35,10 @@
private DepthFirstAnalysis _dfa = null;
public void setUp() {
+ setUpGraph1();
+ }
+
+ public void setUpGraph1() {
Graph graph = new Graph();
Object node1 = new Object();
Object node2 = new Object();
@@ -51,15 +56,37 @@
_dfa = new DepthFirstAnalysis(graph);
}
+ public void setUpGraph2() {
+ Graph graph = new Graph();
+ Integer node1 = new Integer(5);
+ Integer node2 = new Integer(4);
+ Integer node3 = new Integer(3);
+ Integer node4 = new Integer(2);
+ Integer node5 = new Integer(1);
+ graph.addNode(node1);
+ graph.addNode(node2);
+ graph.addNode(node3);
+ graph.addNode(node4);
+ graph.addNode(node5);
+ graph.addEdge(new Edge(node1, node2, true));
+ graph.addEdge(new Edge(node2, node3, true));
+ graph.addEdge(new Edge(node3, node3, true));
+ graph.addEdge(new Edge(node3, node4, true));
+ graph.addEdge(new Edge(node4, node1, true));
+ graph.addEdge(new Edge(node4, node2, true));
+ graph.addEdge(new Edge(node5, node2, true));
+ _dfa = new DepthFirstAnalysis(graph);
+ }
+
public void testNodeSorting() {
Collection nodes = _dfa.getSortedNodes();
assertEquals(4, nodes.size());
- int time = Integer.MAX_VALUE;
+ int time = 0;
Object node;
for (Iterator itr = nodes.iterator(); itr.hasNext();) {
node = itr.next();
- assertTrue(time >= _dfa.getFinishedTime(node));
+ assertTrue(time <= _dfa.getFinishedTime(node));
time = _dfa.getFinishedTime(node);
}
}
@@ -74,6 +101,51 @@
|| edge1.getTo() == edge1.getFrom());
}
+ public void testBackEdges() {
+ setUpGraph2();
+ Collection edges = _dfa.getEdges(Edge.TYPE_BACK);
+ assertEquals(2, edges.size());
+ Iterator itr = edges.iterator();
+ Edge edge0 = (Edge) itr.next();
+ Edge edge1 = (Edge) itr.next();
+ if (edge0.getTo() == edge0.getFrom()) {
+ assertTrue(edge0.getCycle() != null && edge0.getCycle().size()
== 1);
+ List cycle = edge1.getCycle();
+ assertTrue(cycle != null && cycle.size() == 4);
+ assertTrue(((Edge)cycle.get(0)).getFrom() ==
((Edge)cycle.get(3)).getTo());
+ } else if (edge1.getTo() == edge1.getFrom()) {
+ assertTrue(edge1.getCycle() != null && edge1.getCycle().size()
== 1);
+ assertTrue(edge1 == edge1.getCycle());
+ List cycle = edge0.getCycle();
+ assertTrue(cycle != null && cycle.size() == 4);
+ assertTrue(((Edge)cycle.get(0)).getFrom() ==
((Edge)cycle.get(3)).getTo());
+ } else {
+ // should not happen
+ assertFalse(true);
+ }
+ }
+
+ public void testForwardEdges() {
+ setUpGraph2();
+ Collection edges = _dfa.getEdges(Edge.TYPE_FORWARD);
+ assertEquals(2, edges.size());
+ Iterator itr = edges.iterator();
+ Edge edge0 = (Edge) itr.next();
+ Edge edge1 = (Edge) itr.next();
+ if (edge0.getCycle() == null) {
+ List cycle = edge1.getCycle();
+ assertTrue(cycle != null && cycle.size() == 3);
+ assertTrue(((Edge)cycle.get(0)).getFrom() ==
((Edge)cycle.get(2)).getTo());
+ } else if (edge1.getCycle() == null) {
+ List cycle = edge0.getCycle();
+ assertTrue(cycle != null && cycle.size() == 3);
+ assertTrue(((Edge)cycle.get(0)).getFrom() ==
((Edge)cycle.get(2)).getTo());
+ } else {
+ // should not happen
+ assertFalse(true);
+ }
+ }
+
public static void main(String[] args) {
main(TestDepthFirstAnalysis.class);
}
Modified:
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityB.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityB.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityB.java
(original)
+++
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityB.java
Tue Jul 17 16:56:45 2007
@@ -40,7 +40,7 @@
private String name;
- @OneToOne(cascade = CascadeType.ALL)
+ @OneToOne(cascade = CascadeType.ALL, optional = false)
@JoinColumn(name = "entityc_id", referencedColumnName = "entityc_id",
nullable = false)
@ForeignKey
Modified:
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityC.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityC.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityC.java
(original)
+++
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityC.java
Tue Jul 17 16:56:45 2007
@@ -41,7 +41,7 @@
private String name;
- @OneToOne(cascade = CascadeType.ALL)
+ @OneToOne(cascade = CascadeType.ALL, optional = false)
@JoinColumn(name = "entityd_id", referencedColumnName = "entityd_id",
nullable = false)
@ForeignKey
Modified:
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityD.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityD.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityD.java
(original)
+++
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityD.java
Tue Jul 17 16:56:45 2007
@@ -18,12 +18,16 @@
*/
package org.apache.openjpa.jdbc.kernel;
+import org.apache.openjpa.persistence.jdbc.ForeignKey;
+
import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.GeneratedValue;
import javax.persistence.GenerationType;
import javax.persistence.Id;
import javax.persistence.Version;
+import javax.persistence.OneToOne;
+import javax.persistence.JoinColumn;
@Entity
public class EntityD {
@@ -35,6 +39,16 @@
private String name;
+ @OneToOne
+ @JoinColumn(name = "entitya_id", referencedColumnName = "entitya_id")
+ @ForeignKey
+ private EntityA entityA;
+
+ @OneToOne
+ @JoinColumn(name = "entityb_id", referencedColumnName = "entityb_id")
+ @ForeignKey
+ private EntityB entityB;
+
@Version
private Integer optLock;
@@ -49,6 +63,22 @@
return id;
}
+ public EntityA getEntityA() {
+ return this.entityA;
+ }
+
+ public void setEntityA(EntityA entityA) {
+ this.entityA = entityA;
+ }
+
+ public EntityB getEntityB() {
+ return entityB;
+ }
+
+ public void setEntityB(EntityB entityB) {
+ this.entityB = entityB;
+ }
+
public String getName() {
return this.name;
}
Added:
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityE.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityE.java?view=auto&rev=557089
==============================================================================
---
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityE.java
(added)
+++
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityE.java
Tue Jul 17 16:56:45 2007
@@ -0,0 +1,76 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.openjpa.jdbc.kernel;
+
+import javax.persistence.Column;
+import javax.persistence.Entity;
+import javax.persistence.GeneratedValue;
+import javax.persistence.GenerationType;
+import javax.persistence.Id;
+import javax.persistence.JoinColumn;
+import javax.persistence.OneToOne;
+import javax.persistence.Version;
+
+import org.apache.openjpa.persistence.jdbc.ForeignKey;
+
[EMAIL PROTECTED]
+public class EntityE {
+
+ @Id
+ @Column(name = "entitye_id", nullable = false)
+ @GeneratedValue(strategy = GenerationType.IDENTITY)
+ private Integer id;
+
+ private String name;
+
+ @OneToOne
+ @JoinColumn(name = "entityb_id", referencedColumnName = "entityb_id")
+ @ForeignKey
+ private EntityB entityB;
+
+ @Version
+ private Integer optLock;
+
+ public EntityE() {
+ }
+
+ public void setId(Integer id) {
+ this.id = id;
+ }
+
+ public Integer getId() {
+ return id;
+ }
+
+ public EntityB getEntityB() {
+ return this.entityB;
+ }
+
+ public void setEntityB(EntityB entityB) {
+ this.entityB = entityB;
+ }
+
+ public String getName() {
+ return this.name;
+ }
+
+ public void setName(String name) {
+ this.name = name;
+ }
+}
Propchange:
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/EntityE.java
------------------------------------------------------------------------------
svn:eol-style = LF
Modified:
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/TestNoForeignKeyViolation.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/TestNoForeignKeyViolation.java?view=diff&rev=557089&r1=557088&r2=557089
==============================================================================
---
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/TestNoForeignKeyViolation.java
(original)
+++
openjpa/trunk/openjpa-persistence-jdbc/src/test/java/org/apache/openjpa/jdbc/kernel/TestNoForeignKeyViolation.java
Tue Jul 17 16:56:45 2007
@@ -34,15 +34,20 @@
private EntityA entityA;
private EntityB entityB;
private EntityC entityC;
+ private EntityD entityD;
public void setUp() {
- setUp(EntityA.class, EntityB.class, EntityC.class, EntityD.class
);
+ setUp(EntityA.class, EntityB.class, EntityC.class, EntityD.class,
EntityE.class);
+ createTestData();
+ }
+
+ private void createTestData() {
entityA = new EntityA();
+ entityB = new EntityB();
entityC = new EntityC();
- EntityD entityD = new EntityD();
+ entityD = new EntityD();
entityA.setName("entityA");
- entityB = new EntityB();
entityB.setName("entityB");
entityC.setName("entityC");
entityD.setName("entityD");
@@ -52,7 +57,6 @@
}
public void testSqlOrder() {
-
EntityManager em = emf.createEntityManager();
try {
em.getTransaction().begin();
@@ -70,12 +74,78 @@
EntityC newEntityC = new EntityC();
newEntityC.setName("newEntityC");
newEntityD = new EntityD();
- newEntityD.setName("newEntityD");
+ newEntityD.setName("newNewEntityD");
newEntityC.setEntityD(newEntityD);
entityB.setEntityC(newEntityC);
em.getTransaction().begin();
em.merge(entityB);
+ em.getTransaction().commit();
+ }
+ finally {
+ if (em.getTransaction().isActive())
+ em.getTransaction().rollback();
+ em.close();
+ }
+ }
+
+ public void testSimpleCycle() {
+ EntityManager em = emf.createEntityManager();
+ try {
+ em.getTransaction().begin();
+ entityD.setEntityA(entityA);
+ em.persist(entityA);
+ em.getTransaction().commit();
+ }
+ finally {
+ if (em.getTransaction().isActive())
+ em.getTransaction().rollback();
+ em.close();
+ }
+ }
+
+ public void testComplexCycle() {
+ EntityManager em = emf.createEntityManager();
+ try {
+ EntityE entityE = new EntityE();
+ entityE.setName("entityE");
+ entityE.setEntityB(entityB);
+
+ em.getTransaction().begin();
+ em.persist(entityE);
+ entityD.setEntityA(entityA);
+ em.persist(entityA);
+ em.getTransaction().commit();
+
+ em.getTransaction().begin();
+ em.remove(entityE);
+ em.remove(entityA);
+ em.getTransaction().commit();
+ }
+ finally {
+ if (em.getTransaction().isActive())
+ em.getTransaction().rollback();
+ em.close();
+ }
+ }
+
+ public void testComplexTwoCycles() {
+ EntityManager em = emf.createEntityManager();
+ try {
+ EntityE entityE = new EntityE();
+ entityE.setName("entityE");
+ entityE.setEntityB(entityB);
+
+ em.getTransaction().begin();
+ em.persist(entityE);
+ entityD.setEntityA(entityA);
+ entityD.setEntityB(entityB);
+ em.persist(entityA);
+ em.getTransaction().commit();
+
+ em.getTransaction().begin();
+ em.remove(entityE);
+ em.remove(entityA);
em.getTransaction().commit();
}
finally {
