Strange StackOverflowError

[Michael Herrmann]

Hi,
I'm currently writing a class called FileIterator that implements the Iterator interface and enables to iterate over all files, dirs, files in those dirs etc. in a specific directory. As you can see, you can provide a FileFilter or a FilenameFilter to filter files you don't want to be returned. The strange thing is: if I specify a filter that somehow invokes a method on one of FileFilter or FilenameFilter's accept() args, a StackOverflowError is thrown(see WorkingFileiteratorTest and NotWorkingFileIteratorTest below). What's even more strange is is the fact, that the StackOverflowError is not thrown immediately and, if the number of files in the specified directory is small enough, everything works just fine. Sorry for the long listing, you don't have to read the whole code, the interesting parts lie in WorkingFileiteratorTest and NotWorkingFileIteratorTest.

FileIterator.java:

/*
 * Created on 11.09.2004
 */
package at.mherrmann.io;
 
import java.io.File;
import java.io.FileFilter;
import java.io.FileNotFoundException;
import java.io.FilenameFilter;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Vector;
 
public class FileIterator implements Iterator {
    
    private File lastFile;
    private File targetDir;
    private Vector files;
    private FileFilter filter;
    
    public FileIterator(String dir) throws FileNotFoundException {
        this(dir, (FileFilter)null);
    }
    
    public FileIterator(File dir) throws FileNotFoundException {
        this(dir, (FileFilter)null);
    }
    
    public FileIterator(String dir, FilenameFilter filter) throws FileNotFoundException {
        this(new File(dir), filter);
    }
      
    public FileIterator(File dir, FilenameFilter filter) throws FileNotFoundException {
        this(dir, new FilenameFilterWrapper(filter));
    }
    
    public FileIterator(String dir, FileFilter filter) throws FileNotFoundException {
        this(new File(dir), filter);
    }
    
    public FileIterator(File dir, FileFilter filter) throws FileNotFoundException {
        if(!dir.isDirectory())
            throw new IllegalArgumentException("The specified file is not a directory.");
        if(!dir.exists())
            throw new FileNotFoundException();
        targetDir = dir;
        this.filter = filter;
        files = new Vector();
        addSubFiles(dir);
    }
    
    public void remove() {
        if(lastFile==null)
            throw new IllegalStateException();
        if(lastFile.isDirectory() && lastFile.listFiles().length>0) {
            // We can't delete nonempty dirs so we have to empty the dir ourselves.
            FileIterator iter = null;
            try {
                iter = new FileIterator(lastFile);
            } catch(FileNotFoundException e) {
                //Should not happen. 
            }
            while(iter.hasNext()) {
                iter.next();
                iter.remove();
            }
            // Now that the dir is empty, let the else block beneath finish our work. 
            remove();
        } else {
            if(!lastFile.delete())
                throw new RuntimeException("Couldn't delete the file "+lastFile.toString());
            lastFile = null;
        }
    }
 
    public boolean hasNext() {
        return files.size()>0;
    }
 
    public Object next() {
        if(!hasNext())
            throw new NoSuchElementException();
        lastFile = (File)files.remove(0);
if(lastFile.isDirectory())
addSubFiles(lastFile);
if(filter==null || filter.accept(lastFile))
    return lastFile;
else
    return next();
    }
 
    private void addSubFiles(File dir) {
        if(!dir.isDirectory())
            throw new IllegalArgumentException("The specified file "+dir.toString()+" is not a directory!.");
        File[] subFiles = dir.listFiles();
        if(subFiles==null)
            return;
for(int i=0;i<subFiles.length;i++) {
files.add(subFiles[i]);
}
    }
}

FilenameFilter.java:

/*
 * Created on 23.09.2004
 *
 * Wraps a FileFilter around a FilenameFilter. 
 */
package at.mherrmann.io;
 
import java.io.File;
import java.io.FileFilter;
import java.io.FilenameFilter;
 
public class FilenameFilterWrapper implements FileFilter {
 
    private FilenameFilter filter;
    
    public FilenameFilterWrapper(FilenameFilter filter) {
        this.filter = filter;
    }
 
    public boolean accept(File dir) {
        return filter.accept(dir.getParentFile(), dir.getName());
    }
 
}

NotWorkingFileiteratorTest.java(Throws a StackOverflowError after having found some files):

import java.io.File;
import java.io.FileFilter;
import java.util.Iterator;
 
import at.mherrmann.io.FileIterator;
 
public class NotWorkingFileiteratorTest {
 
    public static void main(String[] args) throws Exception {
        Iterator iter = new FileIterator("C:/", new FileFilter() {
            public boolean accept(File file) {
// This is the tricky part
                return file.getName().indexOf(".java")!=-1;
            }
        });
        long time = System.currentTimeMillis();
        int filesFound = 0;
        int dirsFound = 0;
        File next;
        while(iter.hasNext()) {
            next =(File)iter.next(); 
            if(next.isDirectory()) {
                dirsFound++;
            } else {
                filesFound++;
            }
            System.out.println(next);
        }
        long timeNeeded = System.currentTimeMillis()-time;
        System.out.println("\nSearched "+timeNeeded/1000+" secs. Found "+filesFound+" files in "+dirsFound+" directories");
    }
}

WorkingFileiteratorTest.java:

/*
 * Created on 25.09.2004
 */
package at.mherrmann.lab;
 
import java.io.File;
import java.io.FileFilter;
import java.util.Iterator;
 
import at.mherrmann.io.FileIterator;
 
public class WorkingFileiteratorTest {
 
    public static void main(String[] args) throws Exception {
        Iterator iter = new FileIterator("C:/", new FileFilter() {
            public boolean accept(File file) {
                // This is the tricky part
                return true;
            }
        });
        long time = System.currentTimeMillis();
        int filesFound = 0;
        int dirsFound = 0;
        File next;
        while(iter.hasNext()) {
            next =(File)iter.next(); 
            if(next.isDirectory()) {
                dirsFound++;
            } else {
                filesFound++;
            }
            System.out.println(next);
        }
        long timeNeeded = System.currentTimeMillis()-time;
        System.out.println("\nSearched "+timeNeeded/1000+" secs. Found "+filesFound+" files in "+dirsFound+" directories");
    }
}

Sorry for this long post and thanks if vou'ye managed to get this far

[Ernest Friedman-Hill]

The problem is in this method:

public Object next() {
        if(!hasNext())
            throw new NoSuchElementException();
                lastFile = (File)files.remove(0);
        if(lastFile.isDirectory())
    addSubFiles(lastFile);
if(filter==null || filter.accept(lastFile))
    return lastFile;
else
    return next();
    }

If the filter returns true, then we return "lastFile", and everything's OK. But if the filter returns "false", then this method calls itself recursively. If there are many non-matching files, then you'll get many recursive calls, and eventually you'll run out of stack space and get the exception.

You could rewrite it non-recursively something like this:

public Object next() {
        while (hasNext()) {
                lastFile = (File)files.remove(0);
if(lastFile.isDirectory())
    addSubFiles(lastFile);
if(filter==null || filter.accept(lastFile))
    return lastFile;
        }
        throw new NoSuchElementException();
    }

[Michael Herrmann]

You are my hero
I suspected the problem to be somewhere completely else.
I have to rewrite it nevertheless, because hasNext doesn't work properly. This class was a work in progress and the ability to add Filters was not included in the first running version, so it isn't suited for being able to filter files(I noticed that while searching for the error's cause after having opened this thread). I'll rewrite it and post it in here, maybe someone finds it useful(I definitely think it is).

Thank you very much,
Michael Herrmann
[ September 26, 2004: Message edited by: Michael Herrmann ]

[Michael Herrmann]

Here is the rewritten version that doesn't produce the StackOverflowError mentioned above when traversing my whole HDD(122.000 files, 12.000 directories) or when FileIterator.remove()-ing a directory that contains 23.000 files in 1.600 directories:

/*
 * Created on 11.09.2004
 */
package at.mherrmann.io;
 
import java.io.File;
import java.io.FileFilter;
import java.io.FilenameFilter;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Vector;
 
public class FileIterator implements Iterator {
    
    // The last file returned by next() is stored in here to support remove().
    private File lastFile;
    // The files that passed the filter are stored in this Vector. 
    private Vector files;
    /* The directories found when traversing the dir hierarchy are stored in here. 
     * This prevents files from not being found because the dir they are located in 
     * didn't pass the filter. */
    private Vector dirs;
    private FileFilter filter;
    
    public FileIterator(String dir) {
        this(dir, (FileFilter)null);
    }
    
    public FileIterator(File dir) {
        this(dir, (FileFilter)null);
    }
    
    public FileIterator(String dir, FilenameFilter filter) {
        this(new File(dir), filter);
    }
      
    public FileIterator(File dir, FilenameFilter filter) {
        this(dir, new FilenameFilterWrapper(filter));
    }
    
    public FileIterator(String dir, FileFilter filter) {
        this(new File(dir), filter);
    }
    
    public FileIterator(File dir, FileFilter filter) {
        if(!dir.isDirectory())
            throw new IllegalArgumentException("The specified file "+dir.toString()+" is not a directory or does not exist.");
        this.filter = filter;
        files = new Vector();
        dirs = new Vector();
        dirs.add(dir);
    }
    
    public void remove() {
        if(lastFile==null)
            throw new IllegalStateException();
        if(lastFile.isDirectory() && lastFile.listFiles().length>0) {
            // We can't delete nonempty dirs so we have to empty the dir ourselves.
            emptyDirectory(lastFile);
            // Now that the dir is empty, let the else block beneath finish our work. 
            remove();
        } else {
            if(!lastFile.delete())
                throw new RuntimeException("Couldn't delete the file "+lastFile.toString());
            lastFile = null;
        }
    }
 
    public boolean hasNext() {
        return files.size()>0 || findFiles();
    }
 
    public Object next() {
        if(!hasNext())
            throw new NoSuchElementException();
        lastFile = (File)files.remove(files.size()-1);
return lastFile;
    }
 
    private void emptyDirectory(File dir) {
        FileIterator iter = new FileIterator(dir);
        while(iter.hasNext()) {
            iter.next();
            iter.remove();
        }
    }
 
    private void scanDir(File dir) {
        File[] subFiles = dir.listFiles();
        if(subFiles==null)
            return;
        for(int i=0;i<subFiles.length;i++) {
            if(filter==null || filter.accept(subFiles[i]))
                files.add(subFiles[i]);
            if(subFiles[i].isDirectory())
                dirs.add(subFiles[i]);
}
    }
    
    /**
     * Traverses directories until
     * 1) One or more files that pass the filter are found(->returns true)
     * or
     * 2) There are no more directories to traverse(->returns false). 
     * @return true if new files that pass the filter were found, false otherwise. 
     */
    private boolean findFiles() {
        while(dirs.size()>0) {
            scanDir((File)dirs.remove(0));
            if(files.size()>0)
                return true;
        }
        return false;
    }
}