View Javadoc
1   /*
2    *
3    * The DbUnit Database Testing Framework
4    * Copyright (C)2002-2004, DbUnit.org
5    *
6    * This library is free software; you can redistribute it and/or
7    * modify it under the terms of the GNU Lesser General Public
8    * License as published by the Free Software Foundation; either
9    * version 2.1 of the License, or (at your option) any later version.
10   *
11   * This library is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14   * Lesser General Public License for more details.
15   *
16   * You should have received a copy of the GNU Lesser General Public
17   * License along with this library; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19   *
20   */
21  package org.dbunit.database;
22  
23  import java.sql.SQLException;
24  import java.util.Arrays;
25  import java.util.HashMap;
26  import java.util.HashSet;
27  import java.util.Iterator;
28  import java.util.LinkedList;
29  import java.util.List;
30  import java.util.Map;
31  import java.util.Set;
32  
33  import org.dbunit.database.search.TablesDependencyHelper;
34  import org.dbunit.dataset.DataSetException;
35  import org.dbunit.dataset.filter.SequenceTableFilter;
36  import org.dbunit.util.search.SearchException;
37  import org.slf4j.Logger;
38  import org.slf4j.LoggerFactory;
39  
40  /**
41   * This filter orders tables using dependency information provided by
42   * {@link java.sql.DatabaseMetaData#getExportedKeys}. Note that this class
43   * name is a bit misleading since it is not at all related to database
44   * sequences. It just brings database tables in a specific order.
45   *
46   * @author Manuel Laflamme
47   * @author Erik Price
48   * @author Last changed by: $Author$
49   * @version $Revision$ $Date$
50   * @since 1.5.1 (Mar 23, 2003)
51   */
52  public class DatabaseSequenceFilter extends SequenceTableFilter
53  {
54  
55      /**
56       * Logger for this class
57       */
58      private static final Logger logger = LoggerFactory.getLogger(DatabaseSequenceFilter.class);
59    
60  
61      /**
62       * Create a DatabaseSequenceFilter that only exposes specified table names.
63       */
64      public DatabaseSequenceFilter(IDatabaseConnection connection,
65              String[] tableNames) throws DataSetException, SQLException
66      {
67          super(sortTableNames(connection, tableNames));
68      }
69  
70      /**
71       * Create a DatabaseSequenceFilter that exposes all the database tables.
72       */
73      public DatabaseSequenceFilter(IDatabaseConnection connection)
74              throws DataSetException, SQLException
75      {
76          this(connection, connection.createDataSet().getTableNames());
77      }
78  
79      /**
80       * Re-orders a string array of table names, placing dependent ("parent")
81       * tables after their dependencies ("children").
82       *
83       * @param tableNames A string array of table names to be ordered.
84       * @return The re-ordered array of table names.
85       * @throws DataSetException
86       * @throws SQLException If an exception is encountered in accessing the database.
87       */
88      static String[] sortTableNames(
89          IDatabaseConnection connection,
90          String[] tableNames)
91          throws DataSetException, SQLException
92              // not sure why this throws DataSetException ? - ENP
93      {
94          logger.debug("sortTableNames(connection={}, tableNames={}) - start", connection, tableNames);
95  
96          // Get dependencies for each table
97          Map dependencies = new HashMap();
98          try {
99              for (int i = 0; i < tableNames.length; i++) {
100                 String tableName = tableNames[i];
101                 DependencyInfo info = getDependencyInfo(connection, tableName);
102                 dependencies.put(tableName, info);
103             }
104         } catch (SearchException e) {
105             throw new DataSetException("Exception while searching the dependent tables.", e);
106         }
107 
108         
109         // Check whether the table dependency info contains cycles
110         for (Iterator iterator = dependencies.values().iterator(); iterator.hasNext();) {
111             DependencyInfo info = (DependencyInfo) iterator.next();
112             info.checkCycles();
113         }
114         
115         return sort(tableNames, dependencies);
116     }
117     
118 
119     private static String[] sort(String[] tableNames, Map dependencies) 
120     {
121         logger.debug("sort(tableNames={}, dependencies={}) - start", tableNames, dependencies);
122         
123         boolean reprocess = true;
124         List tmpTableNames = Arrays.asList(tableNames);
125         List sortedTableNames = null;
126         
127         while (reprocess) {
128             sortedTableNames = new LinkedList();
129             
130             // re-order 'tmpTableNames' into 'sortedTableNames'
131             for (Iterator i = tmpTableNames.iterator(); i.hasNext();)
132             {
133                 boolean foundDependentInSortedTableNames = false;
134                 String tmpTable = (String)i.next();
135                 DependencyInfo tmpTableDependents = (DependencyInfo) dependencies.get(tmpTable);
136                 
137 
138                 int sortedTableIndex = -1;
139                 for (Iterator k = sortedTableNames.iterator(); k.hasNext();)
140                 {
141                     String sortedTable = (String)k.next();
142                     if (tmpTableDependents.containsDirectDependsOn(sortedTable))
143                     {
144                         sortedTableIndex = sortedTableNames.indexOf(sortedTable);
145                         foundDependentInSortedTableNames = true;
146                         break; // end for loop; we know the index
147                     }
148                 }
149 
150                 
151                 // add 'tmpTable' to 'sortedTableNames'.
152                 // Insert it before its first dependent if there are any,
153                 // otherwise append it to the end of 'sortedTableNames'
154                 if (foundDependentInSortedTableNames) {
155                     if (sortedTableIndex < 0) {
156                         throw new IllegalStateException(
157                             "sortedTableIndex should be 0 or greater, but is "
158                                 + sortedTableIndex);
159                     }
160                     sortedTableNames.add(sortedTableIndex, tmpTable);
161                 }
162                 else
163                 {
164                     sortedTableNames.add(tmpTable);
165                 }
166             }
167             
168             
169             
170             // don't stop processing until we have a perfect run (no re-ordering)
171             if (tmpTableNames.equals(sortedTableNames))
172             {
173                 reprocess = false;
174             }
175             else
176             {
177 
178                 tmpTableNames = null;
179                 tmpTableNames = (List)((LinkedList)sortedTableNames).clone();
180             }
181         }// end 'while (reprocess)'
182         
183         return (String[])sortedTableNames.toArray(new String[0]);
184     }
185 
186     /**
187      * Creates the dependency information for the given table
188      * @param connection
189      * @param tableName
190      * @return The dependency information for the given table
191      * @throws SearchException
192      */
193     private static DependencyInfo getDependencyInfo(
194             IDatabaseConnection connection, String tableName) 
195     throws SearchException 
196     {
197         logger.debug("getDependencyInfo(connection={}, tableName={}) - start", connection, tableName);
198         
199         // The tables dependency helpers makes a depth search for dependencies and returns the whole
200         // tree of dependent objects, not only the direct FK-PK related tables.
201         String[] allDependentTables = TablesDependencyHelper.getDependentTables(connection, tableName);
202         String[] allDependsOnTables = TablesDependencyHelper.getDependsOnTables(connection, tableName);
203         Set allDependentTablesSet = new HashSet(Arrays.asList(allDependentTables));
204         Set allDependsOnTablesSet = new HashSet(Arrays.asList(allDependsOnTables));
205         // Remove the table itself which is automatically included by the TablesDependencyHelper
206         allDependentTablesSet.remove(tableName);
207         allDependsOnTablesSet.remove(tableName);
208         
209         Set directDependsOnTablesSet = TablesDependencyHelper.getDirectDependsOnTables(connection, tableName);
210         Set directDependentTablesSet = TablesDependencyHelper.getDirectDependentTables(connection, tableName);
211         directDependsOnTablesSet.remove(tableName);
212         directDependentTablesSet.remove(tableName);
213         
214         DependencyInfo info = new DependencyInfo(tableName, 
215                 directDependsOnTablesSet, directDependentTablesSet, 
216                 allDependsOnTablesSet, allDependentTablesSet);
217         return info;
218     }
219 
220 
221     
222     /**
223      * Container of dependency information for one single table.
224      * 
225      * @author gommma (gommma AT users.sourceforge.net)
226      * @author Last changed by: $Author$
227      * @version $Revision$ $Date$
228      * @since 2.4.0
229      */
230     static class DependencyInfo
231     {
232         /**
233          * Logger for this class
234          */
235         private static final Logger logger = LoggerFactory.getLogger(DatabaseSequenceFilter.class);
236 
237         private String tableName;
238         
239         private Set allTableDependsOn;
240         private Set allTableDependent;
241         
242         private Set directDependsOnTablesSet;
243         private Set directDependentTablesSet;
244         
245         /**
246          * @param tableName
247          * @param allTableDependsOn Tables that are required as prerequisite so that this one can exist
248          * @param allTableDependent Tables that need this one in order to be able to exist
249          */
250         public DependencyInfo(String tableName, 
251                 Set directDependsOnTablesSet, Set directDependentTablesSet,
252                 Set allTableDependsOn, Set allTableDependent) 
253         {
254             super();
255             this.directDependsOnTablesSet = directDependsOnTablesSet;
256             this.directDependentTablesSet = directDependentTablesSet;
257             this.allTableDependsOn = allTableDependsOn;
258             this.allTableDependent = allTableDependent;
259             this.tableName = tableName;
260         }
261 
262         public boolean containsDirectDependent(String tableName) {
263             return this.directDependentTablesSet.contains(tableName);
264         }
265         public boolean containsDirectDependsOn(String tableName) {
266             return this.directDependsOnTablesSet.contains(tableName);
267         }
268 
269         public String getTableName() {
270             return tableName;
271         }
272 
273         public Set getAllTableDependsOn() {
274             return allTableDependsOn;
275         }
276 
277         public Set getAllTableDependent() {
278             return allTableDependent;
279         }
280         
281         public Set getDirectDependsOnTablesSet() {
282             return directDependsOnTablesSet;
283         }
284 
285         public Set getDirectDependentTablesSet() {
286             return directDependentTablesSet;
287         }
288 
289         /**
290          * Checks this table's information for cycles by intersecting the two sets.
291          * When the result set has at least one element we do have cycles.
292          * @throws CyclicTablesDependencyException
293          */
294         public void checkCycles() throws CyclicTablesDependencyException 
295         {
296             logger.debug("checkCycles() - start");
297 
298             // Intersect the "tableDependsOn" and "otherTablesDependOn" to check for cycles
299             Set intersect = new HashSet(this.allTableDependsOn);
300             intersect.retainAll(this.allTableDependent);
301             if(!intersect.isEmpty()){
302                 throw new CyclicTablesDependencyException(tableName, intersect);
303             }
304         }
305 
306         public String toString()
307         {
308             StringBuffer sb = new StringBuffer();
309             sb.append("DependencyInfo[");
310             sb.append("table=").append(tableName);
311             sb.append(", directDependsOn=").append(directDependsOnTablesSet);
312             sb.append(", directDependent=").append(directDependentTablesSet);
313             sb.append(", allDependsOn=").append(allTableDependsOn);
314             sb.append(", allDependent=").append(allTableDependent);
315             sb.append("]");
316             return sb.toString();
317         }
318         
319     }
320 }