java.lang.StackOverflowError Recursive Directory

Question

In my Android application I'm populating all of the paths of the external storage into an array.

A small number of devices are reporting a StackOverflowError.

I've read many linked posts regarding the cause of this issue, but I don't know how to handle it or prevent it from happening within the code I'm using. Neither do I understand the 'recursive limit' that Android can handle.

The code below is adapted from this source.

private final Locale loc = SupportedLanguages.isSupported();
private final String CACHE = "cache";
private final String TEMP = "temp";

@Override
protected Boolean doInBackground(Void... params) {

        final File fileList = Environment.getExternalStorageDirectory();

        final String absolutePath = Environment.getExternalStorageDirectory().getAbsolutePath();

        final File[] dirList = fileList.listFiles();

        final List<File> listDirs = Arrays.asList(dirList);

        if (Environment.getExternalStorageState().equals(Environment.MEDIA_MOUNTED)) {

            final ArrayList<String> dirPath = new ArrayList<String>();
            final ArrayList<String> dirName = new ArrayList<String>();
            String fileName = "";

            for (final File startingDirectory : listDirs) {
                if (!startingDirectory.isFile() && startingDirectory.canRead() && !startingDirectory.isHidden()) {

                    final List<File> files = getFileListing(startingDirectory);

                    if (files != null) {

                        for (final File file : files) {

                            fileName = file.getPath().replaceAll(absolutePath, "").toLowerCase(loc).replaceAll("\\/", " ")
                                    .trim();
                            fileName = fileName.replaceAll(" +", " ");

                            dirName.add(fileName);
                            dirPath.add(file.toString());
                        }
                    }
                }
            }

        } 


    return true;
}

private List<File> getFileListing(File aStartingDir) {
    List<File> result = getFileListingNoSort(aStartingDir);

    if (result != null && !result.isEmpty()) {
        Collections.sort(result);
    }
    return result;
}

private List<File> getFileListingNoSort(File aStartingDir) {
    List<File> resultArray = new ArrayList<File>();
    File[] filesAndDirs = aStartingDir.listFiles();

    if (filesAndDirs != null && filesAndDirs.length > 0) {

        List<File> filesDirs = Arrays.asList(filesAndDirs);

        for (File file : filesDirs) {
            if (!file.isFile() && file.canRead() && !file.isHidden() && !file.getName().toLowerCase(loc).startsWith(CACHE)
                    && !file.getName().toLowerCase(loc).startsWith(TEMP)) {

                resultArray.add(file);
                List<File> deeperList = getFileListingNoSort(file);
                resultArray.addAll(deeperList);
            }
        }
    }

    return resultArray;
}

The crash log:

> Caused by: java.lang.StackOverflowError at
> java.lang.AbstractStringBuilder.append0(AbstractStringBuilder.java:145)
> at java.lang.StringBuilder.append(StringBuilder.java:216) at
> java.io.File.join(File.java:215) at java.io.File.<init>(File.java:157)
> at java.io.File.<init>(File.java:124) at
> java.io.File.filenamesToFiles(File.java:852) at
> java.io.File.listFiles(File.java:791) at
> com.mypackage.name.ll.a(Unknown Source) at
> com.mypackage.name.ll.a(Unknown Source) at
> com.mypackage.name.ll.a(Unknown Source) at
> com.mypackage.name.ll.a(Unknown Source) at
> com.mypackage.name.ll.a(Unknown Source) at
> com.mypackage.name.ll.a(Unknown Source) at
> com.mypackage.name.ll.a(Unknown Source) at
> com.mypackage.name.ll.a(Unknown Source) at
> com.mypackage.name.ll.a(Unknown Source)

And so on......

The proguard mapping:

com.mypackage.name.GenerateSubDirectoryList -> com.mypackage.name.ll:
java.util.List getFileListingNoSort(java.io.File) -> a

Somewhere I'll need to count the recursions and apply a limit. But I don't know where or the limit that applies to Android or perhaps individual device hardware?

Thanks in advance for your help.

score 1 · Answer 1 · answered May 16 '13 at 13:07

Counting recursions is easy: just add an int parameter to the getFileListingNoSort method and increment the value on each call:

private List<File> getFileListingNoSort(File aStartingDir, int level) {
    List<File> resultArray = new ArrayList<File>();
    File[] filesAndDirs = aStartingDir.listFiles();

    if (level < MAX_LEVEL && filesAndDirs != null && filesAndDirs.length > 0) {

        List<File> filesDirs = Arrays.asList(filesAndDirs);

        for (File file : filesDirs) {
            if (!file.isFile() && file.canRead() && !file.isHidden() && !file.getName().toLowerCase(loc).startsWith(CACHE)
                    && !file.getName().toLowerCase(loc).startsWith(TEMP)) {

                resultArray.add(file);
                List<File> deeperList = getFileListingNoSort(file, ++level);
                resultArray.addAll(deeperList);
            }
        }
    }

    return resultArray;
}

But the question is still: what would be the best value for MAX_LEVEL and why does it loop indinitely. The file systems in question may have symbolic links that create cycles.

Thanks Andreas. Yes, the question remains what this limit should be set to? Also, I've seen posts where the 'maximum integer level' is exceeded and a long should be used instead. Without knowing the limit, I don't know if this also needs to be considered though? Unlikely perhaps due to the count being storage paths. Thanks for pointing out the symbolic links - I hand't considered that. I'll investigate. — brandall, May 16 '13 at 13:15

Ben Brammer · Answer 2 · 2013-05-16T14:09:59.703

Android runs on a lot of hardware, much of which may not have much stack at all; instead of recursing through the subdirectories, do a breadth-first search, thus:

private List<File> getFileListingNoSort(File aStartingDir) 
{
    // assuming aStartingDir is a valid input
    List<File> dirsToSearch = new ArrayList<File>();
    dirsToSearch.add(aStartingDir);
    List<File> resultArray = new ArrayList<File>();
    do{
        File thisDir = dirsToSearch.remove(0);      
        List<File> filesDirs = Arrays.asList(thisDir.listFiles());

        for (File file : filesDirs) 
        {
            if (file.isDirectory())
            {
                dirsToSearch.add(file);
            }
             else if( file.canRead() && 
                      !file.isHidden() &&     
                      !file.getName().toLowerCase(loc).startsWith(CACHE) &&
                      !file.getName().toLowerCase(loc).startsWith(TEMP))
            {
                resultArray.add(file);              
            }
        }
    } while(false == dirsToSearch.isEmpty());
    return resultArray;
}

caveat emptor: I didn't run or even see if this code compiles.

But the idea is, maintain a list of directories, starting with the directory you are care about, remove the first directory from that list, add the files from that directory to the results (modify the code to add the directories to the resultArray if you want directories too), add the directories to the list of directories to search, and continue until the list of directories is empty.

Recursion is bad if you can't know in advance how far you have to recurse, or how far you are able. I don't believe that file-system iteration is an appropriate place for recursion, but that's my own opinion.

Thanks Ben, but I'm a little confused - 'maintain a list of directories' <- How can I do that in the first place without recursively creating one!? — brandall, May 16 '13 at 13:56
when, during the course of iterating through filesDirs, you come across a directory, you add it to dirsToSearch; otherwise, you check to see if it meets your conditions, and if it does, add it to the resultsArray. The do...while loop will continue as long as there are directories that you have added but not listed, and the first step of listing a directory is to remove it from the dirsToSearch. — Ben Brammer, May 16 '13 at 14:12
I will need a little time to digest your suggested implementation. Thanks for returning to clarify. — brandall, May 16 '13 at 14:37

java.lang.StackOverflowError Recursive Directory

2 Answers2