Bug 416713 - Optimize Storage.listEntryPaths for wildcards and recursion.

Use LinkedHashSet for optimized performance of contains() plus ordering guarantees.

Add new thread local class used to communicate to participating bundle files that recursion is desired on the first call to
getEntryPaths.

Have zip and directory bundle files participate in the recursion.

 - Update copyrights
 - Ensure ListEntryPathsThreadLocal is set to false in a finally block

5 files changed, 183 insertions, 55 deletions

diff --git a/bundles/org.eclipse.osgi/core/framework/org/eclipse/osgi/internal/loader/BundleLoader.java b/bundles/org.eclipse.osgi/core/framework/org/eclipse/osgi/internal/loader/BundleLoader.java
index 15359c76d..337235ea1 100644
--- a/bundles/org.eclipse.osgi/core/framework/org/eclipse/osgi/internal/loader/BundleLoader.java
+++ b/bundles/org.eclipse.osgi/core/framework/org/eclipse/osgi/internal/loader/BundleLoader.java
@@ -741,7 +741,9 @@ public class BundleLoader implements ClassLoaderDelegate {
 		}
 
 		boolean localSearch = (options & BundleWiring.LISTRESOURCES_LOCAL) != 0;
-		List<String> result = new ArrayList<String>();
+		// Use LinkedHashSet for optimized performance of contains() plus 
+		// ordering guarantees.
+		LinkedHashSet<String> result = new LinkedHashSet<String>();
 		Set<String> importedPackages = new HashSet<String>(0);
 		for (String name : packages) {
 			// look for import source
@@ -758,8 +760,8 @@ public class BundleLoader implements ClassLoaderDelegate {
 				String packagePath = name.replace('.', '/');
 				Collection<String> externalResources = externalSource.listResources(packagePath, filePattern);
 				for (String resource : externalResources) {
-					if (!result.contains(resource)) // prevent duplicates; could happen if the package is split or exporter has fragments/multiple jars
-						result.add(resource);
+					// Duplicates avoided by using a set.
+					result.add(resource);
 				}
 			}
 		}
@@ -768,7 +770,7 @@ public class BundleLoader implements ClassLoaderDelegate {
 		Collection<String> localResources = createClassLoader().listLocalResources(path, filePattern, options);
 		for (String resource : localResources) {
 			String resourcePkg = getResourcePackageName(resource);
-			if (!importedPackages.contains(resourcePkg) && !result.contains(resource))
+			if (!importedPackages.contains(resourcePkg)) // Duplicates avoided by using a set.
 				result.add(resource);
 		}
 		return result;
diff --git a/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/BaseAdaptor.java b/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/BaseAdaptor.java
index 0c2aebb92..98c20127d 100644
--- a/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/BaseAdaptor.java
+++ b/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/BaseAdaptor.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2005, 2011 IBM Corporation and others.
+ * Copyright (c) 2005, 2013 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
@@ -580,8 +580,9 @@ public class BaseAdaptor implements FrameworkAdaptor {
 	 * @see BundleWiring#listResources(String, String, int)
 	 */
 	public List<String> listEntryPaths(List<BundleFile> bundleFiles, String path, String filePattern, int options) {
-		// a list used to store the results of the search
-		List<String> pathList = new ArrayList<String>();
+		// Store the results of the search. Use LinkedHashSet for optimized 
+		// performance of contains() plus ordering guarantees.
+		LinkedHashSet<String> pathList = new LinkedHashSet<String>();
 		Filter patternFilter = null;
 		Hashtable<String, String> patternProps = null;
 		if (filePattern != null) {
@@ -596,7 +597,7 @@ public class BaseAdaptor implements FrameworkAdaptor {
 					if (bundleFile.getEntry(path) != null && !pathList.contains(path))
 						pathList.add(path);
 				}
-				return pathList;
+				return new ArrayList<String>(pathList);
 			}
 			// For when the file pattern includes a wildcard.
 			try {
@@ -608,14 +609,14 @@ public class BaseAdaptor implements FrameworkAdaptor {
 				// something unexpected happened; log error and return nothing
 				Bundle b = context == null ? null : context.getBundle();
 				eventPublisher.publishFrameworkEvent(FrameworkEvent.ERROR, b, e);
-				return pathList;
+				return new ArrayList<String>(pathList);
 			}
 		}
 		// find the entry paths for the datas
 		for (BundleFile bundleFile : bundleFiles) {
 			listEntryPaths(bundleFile, path, patternFilter, patternProps, options, pathList);
 		}
-		return pathList;
+		return new ArrayList<String>(pathList);
 	}
 
 	private String sanitizeFilterInput(String filePattern) throws InvalidSyntaxException {
@@ -658,10 +659,35 @@ public class BaseAdaptor implements FrameworkAdaptor {
 		return buffer == null ? filePattern : buffer.toString();
 	}
 
-	private List<String> listEntryPaths(BundleFile bundleFile, String path, Filter patternFilter, Hashtable<String, String> patternProps, int options, List<String> pathList) {
+	// Use LinkedHashSet for optimized performance of contains() plus ordering 
+	// guarantees.
+	private LinkedHashSet<String> listEntryPaths(BundleFile bundleFile, String path, Filter patternFilter, Hashtable<String, String> patternProps, int options, LinkedHashSet<String> pathList) {
 		if (pathList == null)
-			pathList = new ArrayList<String>();
-		Enumeration<String> entryPaths = bundleFile.getEntryPaths(path);
+			pathList = new LinkedHashSet<String>();
+		// Set a local flag indicating whether or not this method should use the
+		// original, unoptimized recursion at the end.
+		boolean isRecursive = false;
+		if ((options & BundleWiring.FINDENTRIES_RECURSE) != 0) {
+			// Recursion was requested. Set the thread local to indicate that
+			// participating bundle files should return entry paths
+			// recursively on the first call.
+			ListEntryPathsThreadLocal.setRecursive(true);
+		}
+		Enumeration<String> entryPaths;
+		// Let the bundle file do its work.
+		try {
+			entryPaths = bundleFile.getEntryPaths(path);
+			if ((options & BundleWiring.FINDENTRIES_RECURSE) != 0) {
+				// Since recursion was requested, set the value of the local
+				// recursion flag to the value of the thread local. If the bundle
+				// file used recursion, it will set the thread local back to false;
+				// otherwise, it will still be true.
+				isRecursive = ListEntryPathsThreadLocal.isRecursive();
+			}
+		} finally {
+			// Reset the thread local value to its default.
+			ListEntryPathsThreadLocal.setRecursive(false);
+		}
 		if (entryPaths == null)
 			return pathList;
 		while (entryPaths.hasMoreElements()) {
@@ -689,8 +715,9 @@ public class BaseAdaptor implements FrameworkAdaptor {
 			// prevent duplicates and match on the patternFilter
 			if (!pathList.contains(entry) && (patternFilter == null || patternFilter.matchCase(patternProps)))
 				pathList.add(entry);
-			// recurse only into entries that are directories
-			if (((options & BundleWiring.FINDENTRIES_RECURSE) != 0) && !entry.equals(path) && entry.length() > 0 && lastSlash == (entry.length() - 1))
+			// recurse only into entries that are directories and only if the
+			// bundle file did not do the recursion itself
+			if (isRecursive && !entry.equals(path) && entry.length() > 0 && lastSlash == (entry.length() - 1))
 				listEntryPaths(bundleFile, entry, patternFilter, patternProps, options, pathList);
 		}
 		return pathList;
diff --git a/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/bundlefile/DirBundleFile.java b/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/bundlefile/DirBundleFile.java
index e94db2ca7..fa1c33899 100644
--- a/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/bundlefile/DirBundleFile.java
+++ b/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/bundlefile/DirBundleFile.java
@@ -13,9 +13,9 @@ package org.eclipse.osgi.baseadaptor.bundlefile;
 
 import java.io.File;
 import java.io.IOException;
-import java.util.Enumeration;
-import java.util.NoSuchElementException;
+import java.util.*;
 import org.eclipse.osgi.internal.baseadaptor.AdaptorMsg;
+import org.eclipse.osgi.internal.baseadaptor.ListEntryPathsThreadLocal;
 import org.eclipse.osgi.util.NLS;
 
 /**
@@ -117,34 +117,41 @@ public class DirBundleFile extends BundleFile {
 	}
 
 	public Enumeration<String> getEntryPaths(String path) {
+		// Get entry paths. Recurse or not based on caller's thread local
+		// request.
+		Enumeration<String> result = getEntryPaths(path, ListEntryPathsThreadLocal.isRecursive());
+		// Always set the thread local back to its default value. If the caller
+		// requested recursion, this will indicate that recursion was done.
+		// Otherwise, no harm is done.
+		ListEntryPathsThreadLocal.setRecursive(false);
+		return result;
+	}
+
+	// Optimized method allowing this directory bundle file to recursively 
+	// return entry paths when requested.
+	public Enumeration<String> getEntryPaths(String path, boolean recurse) {
 		if (path.length() > 0 && path.charAt(0) == '/')
 			path = path.substring(1);
-		final File pathFile = getFile(path, false);
+		File pathFile = getFile(path, false);
 		if (pathFile == null || !BundleFile.secureAction.isDirectory(pathFile))
 			return null;
-		final String[] fileList = BundleFile.secureAction.list(pathFile);
+		String[] fileList = BundleFile.secureAction.list(pathFile);
 		if (fileList == null || fileList.length == 0)
 			return null;
-		final String dirPath = path.length() == 0 || path.charAt(path.length() - 1) == '/' ? path : path + '/';
-		return new Enumeration<String>() {
-			int cur = 0;
-
-			public boolean hasMoreElements() {
-				return fileList != null && cur < fileList.length;
-			}
-
-			public String nextElement() {
-				if (!hasMoreElements()) {
-					throw new NoSuchElementException();
-				}
-				java.io.File childFile = new java.io.File(pathFile, fileList[cur]);
-				StringBuffer sb = new StringBuffer(dirPath).append(fileList[cur++]);
-				if (BundleFile.secureAction.isDirectory(childFile)) {
-					sb.append("/"); //$NON-NLS-1$
-				}
-				return sb.toString();
+		String dirPath = path.length() == 0 || path.charAt(path.length() - 1) == '/' ? path : path + '/';
+
+		LinkedHashSet<String> entries = new LinkedHashSet<String>();
+		for (String s : fileList) {
+			java.io.File childFile = new java.io.File(pathFile, s);
+			StringBuilder sb = new StringBuilder(dirPath).append(s);
+			if (BundleFile.secureAction.isDirectory(childFile)) {
+				sb.append("/"); //$NON-NLS-1$
+				if (recurse)
+					entries.addAll(Collections.list(getEntryPaths(sb.toString(), true)));
 			}
-		};
+			entries.add(sb.toString());
+		}
+		return Collections.enumeration(entries);
 	}
 
 	public void close() {
diff --git a/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/bundlefile/ZipBundleFile.java b/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/bundlefile/ZipBundleFile.java
index 9ce5c789d..a4bf05dbf 100644
--- a/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/bundlefile/ZipBundleFile.java
+++ b/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/baseadaptor/bundlefile/ZipBundleFile.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2005, 2010 IBM Corporation and others.
+ * Copyright (c) 2005, 2013 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
@@ -18,8 +18,7 @@ import java.util.zip.ZipEntry;
 import java.util.zip.ZipFile;
 import org.eclipse.osgi.baseadaptor.BaseData;
 import org.eclipse.osgi.framework.debug.Debug;
-import org.eclipse.osgi.internal.baseadaptor.AdaptorMsg;
-import org.eclipse.osgi.internal.baseadaptor.AdaptorUtil;
+import org.eclipse.osgi.internal.baseadaptor.*;
 import org.eclipse.osgi.util.NLS;
 import org.osgi.framework.FrameworkEvent;
 
@@ -259,36 +258,101 @@ public class ZipBundleFile extends BundleFile {
 	}
 
 	public synchronized Enumeration<String> getEntryPaths(String path) {
-		if (!checkedOpen())
-			return null;
+		// Get entry paths. Recurse or not based on caller's thread local
+		// request.
+		Enumeration<String> result = getEntryPaths(path, ListEntryPathsThreadLocal.isRecursive());
+		// Always set the thread local back to its default value. If the caller
+		// requested recursion, this will indicate that recursion was done.
+		// Otherwise, no harm is done.
+		ListEntryPathsThreadLocal.setRecursive(false);
+		return result;
+	}
+
+	// Optimized method allowing this zip bundle file to recursively return 
+	// entry paths when requested.
+	public synchronized Enumeration<String> getEntryPaths(String path, boolean doRecurse) {
 		if (path == null)
 			throw new NullPointerException();
+		// Is the zip file already open or, if not, can it be opened?
+		if (!checkedOpen())
+			return null;
 
+		// Strip any leading '/' off of path.
 		if (path.length() > 0 && path.charAt(0) == '/')
 			path = path.substring(1);
+		// Append a '/', if not already there, to path if not an empty string.
 		if (path.length() > 0 && path.charAt(path.length() - 1) != '/')
-			path = new StringBuffer(path).append("/").toString(); //$NON-NLS-1$
+			path = new StringBuilder(path).append("/").toString(); //$NON-NLS-1$
 
-		List<String> vEntries = new ArrayList<String>();
+		LinkedHashSet<String> result = new LinkedHashSet<String>();
+		// Get all zip file entries and add the ones of interest.
 		Enumeration<? extends ZipEntry> entries = zipFile.entries();
 		while (entries.hasMoreElements()) {
 			ZipEntry zipEntry = entries.nextElement();
 			String entryPath = zipEntry.getName();
+			// Is the entry of possible interest? Note that 
+			// string.startsWith("") == true.
 			if (entryPath.startsWith(path)) {
+				// If we get here, we know that the entry is either (1) equal to
+				// path, (2) a file under path, or (3) a subdirectory of path.
 				if (path.length() < entryPath.length()) {
-					if (entryPath.lastIndexOf('/') < path.length()) {
-						vEntries.add(entryPath);
-					} else {
-						entryPath = entryPath.substring(path.length());
-						int slash = entryPath.indexOf('/');
-						entryPath = path + entryPath.substring(0, slash + 1);
-						if (!vEntries.contains(entryPath))
-							vEntries.add(entryPath);
-					}
+					// If we get here, we know that entry is not equal to path.
+					getEntryPaths(path, entryPath.substring(path.length()), doRecurse, result);
 				}
 			}
 		}
-		return vEntries.size() == 0 ? null : Collections.enumeration(vEntries);
+		return result.size() == 0 ? null : Collections.enumeration(result);
+	}
+
+	/**
+	 * Process the given entry by appending it to path and adding the full path
+	 * to entries. If recursive, sub-paths of entry will also be processed.
+	 * 
+	 * For example, given the following parameters:
+	 * 
+	 * path = com/
+	 * entry = foo/bar/X.class
+	 * doRecurse = false
+	 * 
+	 * com/foo/ will be added to entries and the method will return.
+	 * 
+	 * If, instead, doRecurse equals true, the following will be added to
+	 * entries before returning:
+	 * 
+	 * com/foo/
+	 * com/foo/bar/
+	 * com/foo/bar/X.class
+	 * 
+	 * @param path - The requested or already processed path. On the first call
+	 *               to this method, this will be the path requested by the
+	 *               caller of {@link #getEntryPaths(String, boolean)}. On
+	 *               subsequent, recursive calls, this will be the portion of
+	 *               the path already processed.
+	 * @param entry - The entry underneath path to process.
+	 * @param doRecurse - If true, process all path segments under entry
+	 *                    recursively. If false, process only the first path 
+	 *                    segment in entry.
+	 * @param entries - The set of processed entries.
+	 */
+	private void getEntryPaths(String path, String entry, boolean doRecurse, LinkedHashSet<String> entries) {
+		if (entry.length() == 0) // Terminating condition.
+			// The previous entry was a directory with no files.
+			return;
+		int slash = entry.indexOf('/');
+		if (slash == -1) // Terminating condition.
+			// The entry is a file so nothing follows. Add its full path and
+			// return.
+			entries.add(path + entry);
+		else {
+			// Append the entry to the path to track the full path for recursion.
+			path = path + entry.substring(0, slash + 1);
+			// Add the full entry path.
+			entries.add(path);
+			if (doRecurse)
+				// Recurse with the updated path plus the next path segment of
+				// entry.
+				getEntryPaths(path, entry.substring(slash + 1), true, entries);
+		}
 	}
 
 	public synchronized void close() throws IOException {
diff --git a/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/internal/baseadaptor/ListEntryPathsThreadLocal.java b/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/internal/baseadaptor/ListEntryPathsThreadLocal.java
new file mode 100755
index 000000000..dbe9fc4b4
--- /dev/null
+++ b/bundles/org.eclipse.osgi/defaultAdaptor/src/org/eclipse/osgi/internal/baseadaptor/ListEntryPathsThreadLocal.java
@@ -0,0 +1,28 @@
+/*******************************************************************************
+ * Copyright (c) 2005, 2013 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.osgi.internal.baseadaptor;
+
+public class ListEntryPathsThreadLocal {
+	private static final ThreadLocal<Boolean> recurse = new ThreadLocal<Boolean>() {
+		@Override
+		protected Boolean initialValue() {
+			return Boolean.FALSE;
+		}
+	};
+
+	public static boolean isRecursive() {
+		return recurse.get();
+	}
+
+	public static void setRecursive(boolean value) {
+		recurse.set(value);
+	}
+}