Appended is a patch which solved a problem I reported earlier at
http://castor.exolab.org/list-archive/msg10221.html
The patch performs a topological sorting on the classes of a mapping
to let the classes not dependent on and not extending other classes to
be processed first (processing classes means here: creating their
class descriptors).
Furthermore the patch gives more detailed error messages in the case
of dependency/extension cycles in the mapping.
The patch assumes that not only the dependency relation between classes
is not allowed to have cycles but even the combined dependency/extension
relation.
The patch is insofar a quick hack as general algorithms like topological
sorting should be organized in utility classes but not in the main code.
But for the time being it does what it shall do.
PLEASE CHECK THE PATCH AND ADD IT TO THE CVS VERSION.
If somebody wants to understand the topological sorting algorithm used,
I took it from Robert Sedgewick, "Algorithms". Unfortunately I have only
a German version of the book at hand, so I cannot give the page numbers.
--
Holger Krug
[EMAIL PROTECTED]
? schema
Index: main/org/exolab/castor/mapping/loader/MappingLoader.java
===================================================================
RCS file:
/cvs/castor/castor/src/main/org/exolab/castor/mapping/loader/MappingLoader.java,v
retrieving revision 1.72
diff -u -r1.72 MappingLoader.java
--- main/org/exolab/castor/mapping/loader/MappingLoader.java 21 Mar 2001 00:56:19
-0000 1.72
+++ main/org/exolab/castor/mapping/loader/MappingLoader.java 10 Sep 2001 21:18:09
+-0000
@@ -52,6 +52,7 @@
import java.lang.reflect.Modifier;
import java.io.PrintWriter;
import java.util.Hashtable;
+import java.util.Stack;
import java.util.Vector;
import java.util.Enumeration;
import java.util.NoSuchElementException;
@@ -184,6 +185,141 @@
return Types.typeFromName( _loader, typeName );
}
+ /**
+ * Sorts the class mappings to their dependency on each other.
+ * Checks the class structure for completeness and consistency.
+ * <p>
+ * A class mapping is said to depend on another one if the class
+ * mapped by it either extends or depends the class mapped by the
+ * other mapping.
+ *
+ * @param clsMaps the mapping information on classes
+ * @return a stack of all the <code>ClassMapping</code>'s, the topmost
+ * is the most independent one, i.e. can be processed first
+ * @throws MappingException The mapping file is invalid
+ */
+ private Stack sortClassMaps ( ClassMapping[] clsMaps )
+ throws MappingException {
+
+ int classCount = clsMaps.length;
+ Hashtable nameResolver = new Hashtable(classCount);
+ boolean[][] adjacencyMatrix = new boolean[classCount][classCount];
+
+ // fill the name resolver
+ for ( int i=0; i<classCount ; i++ ) {
+ String clsName = clsMaps[i].getName();
+ if ( nameResolver.get(clsName) != null ) {
+ throw new MappingException( "Two mappings for class " +
+ clsName + " defined");
+ }
+ nameResolver.put(clsName, new Integer(i));
+ }
+
+ // fill the adjacency matrix
+ for ( int i=0; i<classCount ; i++ ) {
+ // initialize
+ for ( int j=0; j<classCount ; j++ ) {
+ adjacencyMatrix[i][j] = false;
+ }
+ ClassMapping clsMap = clsMaps[i];
+ if ( clsMap.getExtends() != null ) {
+ String extendedClsName =
+ ( (ClassMapping) clsMap.getExtends() ).getName() ;
+ Integer extendedClsIdx =
+ (Integer) nameResolver.get(extendedClsName);
+ if ( extendedClsIdx == null ) {
+ throw new MappingException( "Class " +
+ clsMap.getName() +
+ " extends class " +
+ extendedClsName +
+ ", which is not mapped");
+ }
+ adjacencyMatrix[i][extendedClsIdx.intValue()] = true;
+ }
+ if ( clsMap.getDepends() != null ) {
+ String dependedClsName =
+ ( (ClassMapping) clsMap.getDepends() ).getName() ;
+ Integer dependedClsIdx =
+ (Integer) nameResolver.get(dependedClsName);
+ if ( dependedClsIdx == null ) {
+ throw new MappingException( "Class " +
+ clsMap.getName() +
+ " depends on class " +
+ dependedClsName +
+ ", which is not mapped");
+ }
+ adjacencyMatrix[i][dependedClsIdx.intValue()] = true;
+ }
+ }
+
+ // helpers arrays
+ boolean[] visited = new boolean[classCount];
+ boolean[] output = new boolean[classCount];
+ for ( int i=0; i<classCount ; i++ ) {
+ output[i] = false;
+ }
+
+ // topological sort
+ Stack resultStack = new Stack();
+
+ for ( int i=0; i<classCount ; i++ ) {
+ for ( int j=0; j<classCount ; j++ ) {
+ visited[j] = false;
+ }
+ topologicalSortVisit(i, adjacencyMatrix,
+ visited, output, resultStack,
+ clsMaps);
+ }
+
+ return resultStack;
+
+ }
+
+ /**
+ * Helper method to perform topological sorting of a direct acyclic
+ * graph.
+ * Should obviously be removed to some utility class or taken
+ * from an already existing library.
+ *
+ * @param toVisit The index of the node to visit next
+ * @param adjacencyMatrix The adjacency matrix defining the graph
+ * @param visited Marks all the graph nodes which are already visited
+ * @param output Marks all the graph nodes which were already output
+ * @param resultStack The result of topological sorting
+ * @param clsMaps Array containing the objects to be sorted
+ * @throws MappingException The mapping file is invalid
+ */
+ private void topologicalSortVisit( int toVisit,
+ boolean[][] adjacencyMatrix,
+ boolean[] visited,
+ boolean[] output,
+ Stack resultStack,
+ ClassMapping[] clsMaps
+ )
+ throws MappingException {
+ // proceed only if not already pushed on the stack
+ if ( output[toVisit] ) return;
+ if ( visited[toVisit]) {
+ // found a cycle, not allowed in a directed acyclic graph
+ throw new MappingException( "Class " +
+ clsMaps[toVisit].getName() +
+ " involved in a " +
+ "dependency/extension cycle"
+ );
+ }
+ // visit this node
+ visited[toVisit] = true;
+ // proceed to connected nodes
+ for ( int i=0; i<adjacencyMatrix.length ; i++ ) {
+ if ( adjacencyMatrix[i][toVisit] ) {
+ topologicalSortVisit(i, adjacencyMatrix, visited,
+ output, resultStack, clsMaps);
+ }
+ }
+ // push the node on the result stack
+ resultStack.push(clsMaps[toVisit]);
+ output[toVisit] = true;
+ }
/**
* Loads the mapping from the specified mapping object. Calls {@link
@@ -198,16 +334,18 @@
public void loadMapping( MappingRoot mapping, Object param )
throws MappingException
{
- Enumeration enum;
+ Stack clsMapStack;
+ // get the class mappings in order
+ clsMapStack = sortClassMaps(mapping.getClassMapping()) ;
+
// Load the mapping for all the classes. This is always returned
// in the same order as it appeared in the mapping file.
- enum = mapping.enumerateClassMapping();
- while ( enum.hasMoreElements() ) {
+ while ( ! clsMapStack.empty() ) {
ClassMapping clsMap;
ClassDescriptor clsDesc;
- clsMap = (ClassMapping) enum.nextElement();
+ clsMap = (ClassMapping) clsMapStack.pop();
clsDesc = createDescriptor( clsMap );
if ( clsDesc != NoDescriptor )
addDescriptor( clsDesc );
@@ -217,6 +355,8 @@
_logWriter.println( Messages.format( "mapping.ignoringMapping",
clsMap.getName() ) );
}
}
+
+ Enumeration enum;
enum = _clsDescs.elements();
while ( enum.hasMoreElements() ) {
