DatabaseSequenceFilter.java

/*
 *
 * The DbUnit Database Testing Framework
 * Copyright (C)2002-2004, DbUnit.org
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */
package org.dbunit.database;

import java.sql.SQLException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.dbunit.database.search.TablesDependencyHelper;
import org.dbunit.dataset.DataSetException;
import org.dbunit.dataset.filter.SequenceTableFilter;
import org.dbunit.util.search.SearchException;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * This filter orders tables using dependency information provided by
 * {@link java.sql.DatabaseMetaData#getExportedKeys}. Note that this class
 * name is a bit misleading since it is not at all related to database
 * sequences. It just brings database tables in a specific order.
 *
 * @author Manuel Laflamme
 * @author Erik Price
 * @author Last changed by: $Author$
 * @version $Revision$ $Date$
 * @since 1.5.1 (Mar 23, 2003)
 */
public class DatabaseSequenceFilter extends SequenceTableFilter
{

    /**
     * Logger for this class
     */
    private static final Logger logger = LoggerFactory.getLogger(DatabaseSequenceFilter.class);
  

    /**
     * Create a DatabaseSequenceFilter that only exposes specified table names.
     */
    public DatabaseSequenceFilter(IDatabaseConnection connection,
            String[] tableNames) throws DataSetException, SQLException
    {
        super(sortTableNames(connection, tableNames));
    }

    /**
     * Create a DatabaseSequenceFilter that exposes all the database tables.
     */
    public DatabaseSequenceFilter(IDatabaseConnection connection)
            throws DataSetException, SQLException
    {
        this(connection, connection.createDataSet().getTableNames());
    }

    /**
     * Re-orders a string array of table names, placing dependent ("parent")
     * tables after their dependencies ("children").
     *
     * @param tableNames A string array of table names to be ordered.
     * @return The re-ordered array of table names.
     * @throws DataSetException
     * @throws SQLException If an exception is encountered in accessing the database.
     */
    static String[] sortTableNames(
        IDatabaseConnection connection,
        String[] tableNames)
        throws DataSetException, SQLException
            // not sure why this throws DataSetException ? - ENP
    {
        logger.debug("sortTableNames(connection={}, tableNames={}) - start", connection, tableNames);

        // Get dependencies for each table
        Map dependencies = new HashMap();
        try {
            for (int i = 0; i < tableNames.length; i++) {
                String tableName = tableNames[i];
                DependencyInfo info = getDependencyInfo(connection, tableName);
                dependencies.put(tableName, info);
            }
        } catch (SearchException e) {
            throw new DataSetException("Exception while searching the dependent tables.", e);
        }

        
        // Check whether the table dependency info contains cycles
        for (Iterator iterator = dependencies.values().iterator(); iterator.hasNext();) {
            DependencyInfo info = (DependencyInfo) iterator.next();
            info.checkCycles();
        }
        
        return sort(tableNames, dependencies);
    }
    

    private static String[] sort(String[] tableNames, Map dependencies) 
    {
        logger.debug("sort(tableNames={}, dependencies={}) - start", tableNames, dependencies);
        
        boolean reprocess = true;
        List tmpTableNames = Arrays.asList(tableNames);
        List sortedTableNames = null;
        
        while (reprocess) {
            sortedTableNames = new LinkedList();
            
            // re-order 'tmpTableNames' into 'sortedTableNames'
            for (Iterator i = tmpTableNames.iterator(); i.hasNext();)
            {
                boolean foundDependentInSortedTableNames = false;
                String tmpTable = (String)i.next();
                DependencyInfo tmpTableDependents = (DependencyInfo) dependencies.get(tmpTable);
                

                int sortedTableIndex = -1;
                for (Iterator k = sortedTableNames.iterator(); k.hasNext();)
                {
                    String sortedTable = (String)k.next();
                    if (tmpTableDependents.containsDirectDependsOn(sortedTable))
                    {
                        sortedTableIndex = sortedTableNames.indexOf(sortedTable);
                        foundDependentInSortedTableNames = true;
                        break; // end for loop; we know the index
                    }
                }

                
                // add 'tmpTable' to 'sortedTableNames'.
                // Insert it before its first dependent if there are any,
                // otherwise append it to the end of 'sortedTableNames'
                if (foundDependentInSortedTableNames) {
                    if (sortedTableIndex < 0) {
                        throw new IllegalStateException(
                            "sortedTableIndex should be 0 or greater, but is "
                                + sortedTableIndex);
                    }
                    sortedTableNames.add(sortedTableIndex, tmpTable);
                }
                else
                {
                    sortedTableNames.add(tmpTable);
                }
            }
            
            
            
            // don't stop processing until we have a perfect run (no re-ordering)
            if (tmpTableNames.equals(sortedTableNames))
            {
                reprocess = false;
            }
            else
            {

                tmpTableNames = null;
                tmpTableNames = (List)((LinkedList)sortedTableNames).clone();
            }
        }// end 'while (reprocess)'
        
        return (String[])sortedTableNames.toArray(new String[0]);
    }

    /**
     * Creates the dependency information for the given table
     * @param connection
     * @param tableName
     * @return The dependency information for the given table
     * @throws SearchException
     */
    private static DependencyInfo getDependencyInfo(
            IDatabaseConnection connection, String tableName) 
    throws SearchException 
    {
        logger.debug("getDependencyInfo(connection={}, tableName={}) - start", connection, tableName);
        
        // The tables dependency helpers makes a depth search for dependencies and returns the whole
        // tree of dependent objects, not only the direct FK-PK related tables.
        String[] allDependentTables = TablesDependencyHelper.getDependentTables(connection, tableName);
        String[] allDependsOnTables = TablesDependencyHelper.getDependsOnTables(connection, tableName);
        Set allDependentTablesSet = new HashSet(Arrays.asList(allDependentTables));
        Set allDependsOnTablesSet = new HashSet(Arrays.asList(allDependsOnTables));
        // Remove the table itself which is automatically included by the TablesDependencyHelper
        allDependentTablesSet.remove(tableName);
        allDependsOnTablesSet.remove(tableName);
        
        Set directDependsOnTablesSet = TablesDependencyHelper.getDirectDependsOnTables(connection, tableName);
        Set directDependentTablesSet = TablesDependencyHelper.getDirectDependentTables(connection, tableName);
        directDependsOnTablesSet.remove(tableName);
        directDependentTablesSet.remove(tableName);
        
        DependencyInfo info = new DependencyInfo(tableName, 
                directDependsOnTablesSet, directDependentTablesSet, 
                allDependsOnTablesSet, allDependentTablesSet);
        return info;
    }


    
    /**
     * Container of dependency information for one single table.
     * 
     * @author gommma (gommma AT users.sourceforge.net)
     * @author Last changed by: $Author$
     * @version $Revision$ $Date$
     * @since 2.4.0
     */
    static class DependencyInfo
    {
        /**
         * Logger for this class
         */
        private static final Logger logger = LoggerFactory.getLogger(DatabaseSequenceFilter.class);

        private String tableName;
        
        private Set allTableDependsOn;
        private Set allTableDependent;
        
        private Set directDependsOnTablesSet;
        private Set directDependentTablesSet;
        
        /**
         * @param tableName
         * @param allTableDependsOn Tables that are required as prerequisite so that this one can exist
         * @param allTableDependent Tables that need this one in order to be able to exist
         */
        public DependencyInfo(String tableName, 
                Set directDependsOnTablesSet, Set directDependentTablesSet,
                Set allTableDependsOn, Set allTableDependent) 
        {
            super();
            this.directDependsOnTablesSet = directDependsOnTablesSet;
            this.directDependentTablesSet = directDependentTablesSet;
            this.allTableDependsOn = allTableDependsOn;
            this.allTableDependent = allTableDependent;
            this.tableName = tableName;
        }

        public boolean containsDirectDependent(String tableName) {
            return this.directDependentTablesSet.contains(tableName);
        }
        public boolean containsDirectDependsOn(String tableName) {
            return this.directDependsOnTablesSet.contains(tableName);
        }

        public String getTableName() {
            return tableName;
        }

        public Set getAllTableDependsOn() {
            return allTableDependsOn;
        }

        public Set getAllTableDependent() {
            return allTableDependent;
        }
        
        public Set getDirectDependsOnTablesSet() {
            return directDependsOnTablesSet;
        }

        public Set getDirectDependentTablesSet() {
            return directDependentTablesSet;
        }

        /**
         * Checks this table's information for cycles by intersecting the two sets.
         * When the result set has at least one element we do have cycles.
         * @throws CyclicTablesDependencyException
         */
        public void checkCycles() throws CyclicTablesDependencyException 
        {
            logger.debug("checkCycles() - start");

            // Intersect the "tableDependsOn" and "otherTablesDependOn" to check for cycles
            Set intersect = new HashSet(this.allTableDependsOn);
            intersect.retainAll(this.allTableDependent);
            if(!intersect.isEmpty()){
                throw new CyclicTablesDependencyException(tableName, intersect);
            }
        }

        public String toString()
        {
            final StringBuilder sb = new StringBuilder();
            sb.append("DependencyInfo[");
            sb.append("table=").append(tableName);
            sb.append(", directDependsOn=").append(directDependsOnTablesSet);
            sb.append(", directDependent=").append(directDependentTablesSet);
            sb.append(", allDependsOn=").append(allTableDependsOn);
            sb.append(", allDependent=").append(allTableDependent);
            sb.append("]");
            return sb.toString();
        }
        
    }
}