Introduction of a tool to find main dex classes.

This is for legacy application wanting to allow --multi-dex on dx
and load the multiple files using the com.android.multidex.installer
library. The mainDexClasses script will provide the content of the
file to give to dx in --main-dex-list.

Change-Id: Id14bc785c6a888f6af49c018b2c29b89284ae40e
diff --git a/dx/Android.mk b/dx/Android.mk
index edf8ca3..a69c785 100644
--- a/dx/Android.mk
+++ b/dx/Android.mk
@@ -29,6 +29,65 @@
 
 endif # TARGET_BUILD_APPS
 
+# the mainDexClasses rules
+# ============================================================
+include $(CLEAR_VARS)
+LOCAL_IS_HOST_MODULE := true
+LOCAL_MODULE_CLASS := EXECUTABLES
+LOCAL_MODULE_TAGS := optional
+LOCAL_MODULE := mainDexClasses.rules
+
+include $(BUILD_SYSTEM)/base_rules.mk
+
+$(LOCAL_BUILT_MODULE): $(HOST_OUT_JAVA_LIBRARIES)/dx$(COMMON_JAVA_PACKAGE_SUFFIX)
+$(LOCAL_BUILT_MODULE): $(LOCAL_PATH)/etc/mainDexClasses.rules | $(ACP)
+	@echo "Copy: $(PRIVATE_MODULE) ($@)"
+	$(copy-file-to-new-target)
+
+INTERNAL_DALVIK_MODULES += $(LOCAL_INSTALLED_MODULE)
+
+installed_mainDexClasses.rules := $(LOCAL_INSTALLED_MODULE)
+
+# the shrinkedAndroid jar is a library used by the mainDexClasses script
+# ============================================================
+include $(CLEAR_VARS)
+LOCAL_IS_HOST_MODULE := true
+LOCAL_MODULE_CLASS := JAVA_LIBRARIES
+LOCAL_MODULE_TAGS := optional
+LOCAL_MODULE := shrinkedAndroid
+LOCAL_BUILT_MODULE_STEM := shrinkedAndroid.jar
+LOCAL_MODULE_SUFFIX := $(COMMON_JAVA_PACKAGE_SUFFIX)
+
+include $(BUILD_SYSTEM)/base_rules.mk
+
+$(LOCAL_BUILT_MODULE): PRIVATE_PROGUARD_FLAGS:= \
+  -include $(addprefix $(LOCAL_PATH)/, shrinkedAndroid.proguard.flags)
+$(LOCAL_BUILT_MODULE): $(call java-lib-files,android_stubs_current)| $(PROGUARD)
+	$(call proguard-enabled-commands,)
+
+INTERNAL_DALVIK_MODULES += $(LOCAL_INSTALLED_MODULE)
+
+installed_shrinkedAndroid := $(LOCAL_INSTALLED_MODULE)
+
+# the mainDexClasses script
+# ============================================================
+include $(CLEAR_VARS)
+LOCAL_IS_HOST_MODULE := true
+LOCAL_MODULE_CLASS := EXECUTABLES
+LOCAL_MODULE_TAGS := optional
+LOCAL_MODULE := mainDexClasses
+
+include $(BUILD_SYSTEM)/base_rules.mk
+
+$(LOCAL_BUILT_MODULE): $(HOST_OUT_JAVA_LIBRARIES)/dx$(COMMON_JAVA_PACKAGE_SUFFIX)
+$(LOCAL_BUILT_MODULE): $(LOCAL_PATH)/etc/mainDexClasses | $(ACP)
+	@echo "Copy: $(PRIVATE_MODULE) ($@)"
+	$(copy-file-to-new-target)
+	$(hide) chmod 755 $@
+
+$(LOCAL_INSTALLED_MODULE): | $(installed_shrinkedAndroid) $(installed_mainDexClasses.rules)
+INTERNAL_DALVIK_MODULES += $(LOCAL_INSTALLED_MODULE)
+
 # the dexmerger script
 # ============================================================
 include $(CLEAR_VARS)
diff --git a/dx/etc/mainDexClasses b/dx/etc/mainDexClasses
new file mode 100644
index 0000000..39760ec
--- /dev/null
+++ b/dx/etc/mainDexClasses
@@ -0,0 +1,150 @@
+#!/bin/bash
+#
+# Copyright (C) 2013 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+function makeTempJar ()
+{
+  local tempDir=/tmp
+  if [ ! -e ${tempDir} ]; then
+    tempDir=.
+  fi
+  local tempfile="${tempDir}/mainDexClasses-$$.tmp.jar"
+  if [ -e ${tempfile} ]; then
+    echo "Failed to create temporary file" >2
+    exit 6
+  fi
+  echo ${tempfile}
+}
+
+function cleanTmp ()
+{
+  if [ -e ${tmpOut} ] ; then
+    rm ${tmpOut}
+  fi
+}
+
+
+# Set up prog to be the path of this script, including following symlinks,
+# and set up progdir to be the fully-qualified pathname of its directory.
+prog="$0"
+
+while [ -h "${prog}" ]; do
+    newProg=`/bin/ls -ld "${prog}"`
+    newProg=`expr "${newProg}" : ".* -> \(.*\)$"`
+    if expr "x${newProg}" : 'x/' >/dev/null; then
+        prog="${newProg}"
+    else
+        progdir=`dirname "${prog}"`
+        prog="${progdir}/${newProg}"
+    fi
+done
+oldwd=`pwd`
+progdir=`dirname "${prog}"`
+cd "${progdir}"
+progdir=`pwd`
+prog="${progdir}"/`basename "${prog}"`
+cd "${oldwd}"
+
+baserules="${progdir}"/mainDexClasses.rules
+if [ ! -r ${baserules} ]; then
+    echo `basename "$prog"`": can't find mainDexClasses.rules" 1>&2
+    exit 1
+fi
+
+jarfile=dx.jar
+libdir="$progdir"
+
+if [ ! -r "$libdir/$jarfile" ]; then
+    # set dx.jar location for the SDK case
+    libdir=`dirname "$progdir"`/platform-tools/lib
+fi
+
+
+if [ ! -r "$libdir/$jarfile" ]; then
+    # set dx.jar location for the Android tree case
+    libdir=`dirname "$progdir"`/framework
+fi
+
+if [ ! -r "$libdir/$jarfile" ]; then
+    echo `basename "$prog"`": can't find $jarfile" 1>&2
+    exit 1
+fi
+
+proguardExec="proguard.sh"
+proguard=${PROGUARD_HOME}/${proguardExec}
+
+if [ ! -r ${proguard} ]; then
+  # set proguard location for the SDK case
+  proguardBaseDir=`dirname "$progdir"`
+  #"${progdir}"/../..
+  proguardBaseDir=`dirname "$proguardBaseDir"`
+  proguard="${proguardBaseDir}"/tools/proguard/bin/${proguardExec}
+fi
+
+if [ ! -r ${proguard} ]; then
+  # set proguard location for the Android tree case
+  proguardBaseDir=`dirname "$proguardBaseDir"`
+  # ${progdir}"/../../../..
+  proguardBaseDir=`dirname "$proguardBaseDir"`
+  proguard="${proguardBaseDir}"/external/proguard/bin/${proguardExec}
+fi
+
+if [ ! -r ${proguard} ]; then
+    echo `basename "$prog"`": can't find ${proguardExec}" 1>&2
+    exit 1
+fi
+
+shrinkedAndroidJar=${SHRINKED_ANDROID_JAR}
+if [ -z ${shrinkedAndroidJar} ]; then
+  shrinkedAndroidJar=shrinkedAndroid.jar
+fi
+
+if [ ! -r ${shrinkedAndroidJar} ]; then
+  shrinkedAndroidJar=${libdir}/${shrinkedAndroidJar}
+fi
+
+if [ ! -r ${shrinkedAndroidJar} ]; then
+    echo `basename "$prog"`": can't find shrinkedAndroid.jar" 1>&2
+    exit 1
+fi
+
+if [ "$OSTYPE" = "cygwin" ]; then
+    # For Cygwin, convert the jarfile path into native Windows style.
+    jarpath=`cygpath -w "$libdir/$jarfile"`
+  proguard=`cygpath -w "${proguard}"`
+  shrinkedAndroidJar=`cygpath -w "${shrinkedAndroidJar}"`
+else
+    jarpath="$libdir/$jarfile"
+fi
+
+if expr "x$1" : 'x--output' >/dev/null; then
+    exec 1>$2
+    shift 2
+fi
+
+if [ $# -ne 1 ]; then
+  echo "Usage : $0 [--output <output file>] <application path>" 1>&2
+  exit 2
+fi
+
+tmpOut=`makeTempJar`
+
+trap cleanTmp 0
+
+${proguard} -injars ${@} -dontwarn -forceprocessing  -outjars ${tmpOut} \
+  -libraryjars "${shrinkedAndroidJar}" -dontoptimize -dontobfuscate -dontpreverify \
+  -include "${baserules}" 1>/dev/null || exit 10
+
+exec java -cp "$jarpath" com.android.multidex.ClassReferenceListBuilder ${tmpOut} ${@} ||  exit 11
diff --git a/dx/etc/mainDexClasses.bat b/dx/etc/mainDexClasses.bat
new file mode 100755
index 0000000..00b60e8
--- /dev/null
+++ b/dx/etc/mainDexClasses.bat
@@ -0,0 +1,110 @@
+@echo off

+REM Copyright (C) 2013 The Android Open Source Project

+REM

+REM Licensed under the Apache License, Version 2.0 (the "License");

+REM you may not use this file except in compliance with the License.

+REM You may obtain a copy of the License at

+REM

+REM     http://www.apache.org/licenses/LICENSE-2.0

+REM

+REM Unless required by applicable law or agreed to in writing, software

+REM distributed under the License is distributed on an "AS IS" BASIS,

+REM WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

+REM See the License for the specific language governing permissions and

+REM limitations under the License.

+

+REM don't modify the caller's environment

+setlocal

+

+rem Check we have a valid Java.exe in the path.

+set java_exe=

+if exist    "%~dp0..\tools\lib\find_java.bat"    call    "%~dp0..\tools\lib\find_java.bat"

+if exist    "%~dp0..\..\tools\lib\find_java.bat" call    "%~dp0..\..\tools\lib\find_java.bat"

+if not defined java_exe goto :EOF

+

+set baserules="%~dp0\mainDexClasses.rules"

+

+REM Locate dx.jar in the directory where dx.bat was found.

+set jarfile=dx.jar

+set "frameworkdir=%~dp0"

+rem frameworkdir must not end with a dir sep.

+set "frameworkdir=%frameworkdir:~0,-1%"

+if exist "%frameworkdir%\%jarfile%" goto JarFileOk

+    set "frameworkdir=%~dp0lib"

+

+if exist "%frameworkdir%\%jarfile%" goto JarFileOk

+    set "frameworkdir=%~dp0..\framework"

+:JarFileOk

+

+set "jarpath=%frameworkdir%\%jarfile%"

+

+set "shrinkedAndroidJar=%SHRINKED_ANDROID_JAR%

+if exist "%shrinkedAndroidJar%" goto shrinkedAndroidOk

+    set "shrinkedAndroidJar=shrinkedAndroid.jar"

+

+if exist "%shrinkedAndroidJar%" goto shrinkedAndroidOk

+    set "shrinkedAndroidJar=%frameworkdir%\%shrinkedAndroidJar%"

+

+:shrinkedAndroidOk

+set "proguardExec=proguard.bat"

+set "proguard=%PROGUARD_HOME%\bin\%proguardExec%"

+

+if exist "%proguard%" goto proguardOk

+REM set proguard location for the SDK case

+    set "PROGUARD_HOME=%~dp0\..\..\tools\proguard"

+    set "proguard=%PROGUARD_HOME%\bin\%proguardExec%"

+

+if exist "%proguard%" goto proguardOk

+REM set proguard location for the Android tree case

+    set "PROGUARD_HOME=%~dp0\..\..\..\..\external\proguard"

+    set "proguard=%PROGUARD_HOME%\bin\%proguardExec%"

+

+:proguardOk

+REM Capture all arguments.

+REM Note that when reading the input arguments with %1, the cmd.exe

+REM automagically converts --name=value arguments into 2 arguments "--name"

+REM followed by "value". Dx has been changed to know how to deal with that.

+set params=

+

+set output=

+

+:firstArg

+if [%1]==[] goto endArgs

+

+    if %1 NEQ --output goto notOut

+        set "output=%2"

+        shift

+        shift

+        goto firstArg

+

+:notOut

+    if defined params goto usage

+    set params=%1

+    shift

+    goto firstArg

+

+:endArgs

+if defined params ( goto makeTmpJar ) else ( goto usage )

+

+:makeTmpJar

+set "tmpJar=%TMP%\mainDexClasses-%RANDOM%.tmp.jar"

+if exist "%tmpJar%" goto makeTmpJar

+echo "" > "%tmpJar%"

+set "exitStatus=0"

+

+

+call "%proguard%" -injars %params% -dontwarn -forceprocessing  -outjars "%tmpJar%" -libraryjars "%shrinkedAndroidJar%" -dontoptimize -dontobfuscate -dontpreverify -include "%baserules%" 1>nul

+

+if DEFINED output goto redirect

+call "%java_exe%" -Djava.ext.dirs="%frameworkdir%" com.android.multidex.ClassReferenceListBuilder "%tmpJar%" "%params%"

+goto afterClassReferenceListBuilder

+:redirect

+call "%java_exe%" -Djava.ext.dirs="%frameworkdir%" com.android.multidex.ClassReferenceListBuilder "%tmpJar%" "%params%" 1>"%output%"

+:afterClassReferenceListBuilder

+

+del %tmpJar%

+exit /b

+

+:usage

+echo "Usage : %0 [--output <output file>] <application path>"

+exit /b 1

diff --git a/dx/etc/mainDexClasses.rules b/dx/etc/mainDexClasses.rules
new file mode 100644
index 0000000..4a3bb50
--- /dev/null
+++ b/dx/etc/mainDexClasses.rules
@@ -0,0 +1,17 @@
+  -keep public class * extends android.app.Instrumentation {

+  }

+  -keep public class * extends android.app.Application {

+  }

+  -keep public class * extends android.app.Activity {

+  }

+  -keep public class * extends android.app.Service {

+  }

+  -keep public class * extends android.content.ContentProvider {

+  }

+  -keep public class * extends android.content.BroadcastReceiver {

+  }

+  -keep public class * extends android.app.backup.BackupAgent {

+  }

+  -keep class android.support.multidex.** {

+    *;

+  }
\ No newline at end of file
diff --git a/dx/shrinkedAndroid.proguard.flags b/dx/shrinkedAndroid.proguard.flags
new file mode 100644
index 0000000..65c8689
--- /dev/null
+++ b/dx/shrinkedAndroid.proguard.flags
@@ -0,0 +1,21 @@
+-dontwarn
+-forceprocessing
+-dontoptimize
+-dontobfuscate
+-dontpreverify
+-keep public class * extends android.app.Instrumentation {
+}
+-keep public class * extends android.app.Application {
+}
+-keep public class * extends android.app.Activity {
+}
+-keep public class * extends android.app.Service {
+}
+-keep public class * extends android.content.ContentProvider {
+}
+-keep public class * extends android.content.BroadcastReceiver {
+}
+-keep public class * extends android.app.backup.BackupAgent {
+}
+-keep class android.support.multidex.installer.** {
+}
diff --git a/dx/src/com/android/dx/rop/cst/ConstantPool.java b/dx/src/com/android/dx/rop/cst/ConstantPool.java
index efc394d..f4b8086 100644
--- a/dx/src/com/android/dx/rop/cst/ConstantPool.java
+++ b/dx/src/com/android/dx/rop/cst/ConstantPool.java
@@ -67,4 +67,11 @@
      * the index is in-range but invalid
      */
     public Constant getOrNull(int n);
+
+    /**
+     * Get all entries in this constant pool.
+     *
+     * @return the returned array may contain null entries.
+     */
+    public Constant[] getEntries();
 }
diff --git a/dx/src/com/android/dx/rop/cst/StdConstantPool.java b/dx/src/com/android/dx/rop/cst/StdConstantPool.java
index bb975e4..f941f7d 100644
--- a/dx/src/com/android/dx/rop/cst/StdConstantPool.java
+++ b/dx/src/com/android/dx/rop/cst/StdConstantPool.java
@@ -88,6 +88,15 @@
     }
 
     /**
+     * Get all entries in this constant pool.
+     *
+     * @return the returned array may contain null entries.
+     */
+    public Constant[] getEntries() {
+        return entries;
+    }
+
+    /**
      * Sets the entry at the given index.
      *
      * @param n {@code >= 1, < size();} which entry
diff --git a/dx/src/com/android/multidex/ArchivePathElement.java b/dx/src/com/android/multidex/ArchivePathElement.java
new file mode 100644
index 0000000..e76993b
--- /dev/null
+++ b/dx/src/com/android/multidex/ArchivePathElement.java
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.multidex;
+
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.zip.ZipEntry;
+import java.util.zip.ZipFile;
+
+/**
+ * A zip element.
+ */
+class ArchivePathElement implements ClassPathElement {
+
+    private ZipFile archive;
+
+    public ArchivePathElement(ZipFile archive) {
+        this.archive = archive;
+    }
+
+    @Override
+    public InputStream open(String path) throws IOException {
+        ZipEntry entry = archive.getEntry(path);
+        if (entry == null) {
+            throw new FileNotFoundException(path);
+        } else {
+            return archive.getInputStream(entry);
+        }
+    }
+
+    @Override
+    public void close() throws IOException {
+        archive.close();
+    }
+
+}
diff --git a/dx/src/com/android/multidex/ClassPathElement.java b/dx/src/com/android/multidex/ClassPathElement.java
new file mode 100644
index 0000000..6c60721
--- /dev/null
+++ b/dx/src/com/android/multidex/ClassPathElement.java
@@ -0,0 +1,39 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.multidex;
+
+import java.io.IOException;
+import java.io.InputStream;
+
+/**
+ * An element of the class path in which class files can be found.
+ */
+interface ClassPathElement {
+
+    char SEPARATOR_CHAR = '/';
+
+    /**
+     * Open a "file" from this {@code ClassPathElement}.
+     * @param path a '/' separated relative path to the wanted file.
+     * @return an {@code InputStream} ready to read the requested file.
+     * @throws IOException if the path can not be found or if an error occurred while opening it.
+     */
+    InputStream open(String path) throws IOException;
+
+    void close() throws IOException;
+
+}
diff --git a/dx/src/com/android/multidex/ClassReferenceListBuilder.java b/dx/src/com/android/multidex/ClassReferenceListBuilder.java
new file mode 100644
index 0000000..080efaa
--- /dev/null
+++ b/dx/src/com/android/multidex/ClassReferenceListBuilder.java
@@ -0,0 +1,294 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.multidex;
+
+import com.android.dx.cf.direct.DirectClassFile;
+import com.android.dx.cf.direct.StdAttributeFactory;
+import com.android.dx.rop.cst.Constant;
+import com.android.dx.rop.cst.ConstantPool;
+import com.android.dx.rop.cst.CstType;
+import com.android.dx.rop.type.Type;
+import com.android.dx.rop.type.TypeList;
+
+import java.io.ByteArrayOutputStream;
+import java.io.File;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.ArrayList;
+import java.util.Enumeration;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.regex.Pattern;
+import java.util.zip.ZipEntry;
+import java.util.zip.ZipException;
+import java.util.zip.ZipFile;
+
+/**
+ * This is a command line tool used by mainDexClasses script to find direct class references to
+ * other classes. First argument of the command line is an archive, each class file contained in
+ * this archive is used to identify a class whose references are to be searched, those class files
+ * are not opened by this tool only their names matter. Other arguments must be zip files or
+ * directories, they constitute in a classpath in with the classes named by the first argument
+ * will be searched. Each searched class must be found. On each of this classes are searched for
+ * their dependencies to other classes. Finally the tools prints on standard output a list of class
+ * files names suitable as content of the file argument --main-dex-list of dx.
+ */
+public class ClassReferenceListBuilder {
+
+    private static final String CLASS_EXTENSION = ".class";
+
+    private static final int STATUS_ERROR = 1;
+
+    private static final String EOL = System.getProperty("line.separator");
+
+    private static String USAGE_MESSAGE =
+            "Usage:" + EOL + EOL +
+            "Short version: Don't use this." + EOL + EOL +
+            "Slightly longer version: This tool is used by mainDexClasses script to find direct"
+            + EOL +
+            "references of some classes." + EOL;
+
+    private Path path;
+    private Set<String> toKeep = new HashSet<String>();
+
+    private ClassReferenceListBuilder(Path path) {
+        this.path = path;
+    }
+
+    public static void main(String[] args) {
+
+        if (args.length != 2) {
+            printUsage();
+            System.exit(STATUS_ERROR);
+        }
+
+        ZipFile jarOfRoots;
+        try {
+            jarOfRoots = new ZipFile(args[0]);
+        } catch (IOException e) {
+            System.err.println("\"" + args[0] + "\" can not be read as a zip archive. ("
+                    + e.getMessage() + ")");
+            System.exit(STATUS_ERROR);
+            return;
+        }
+
+        Path path = null;
+        try {
+            path = new Path(args[1]);
+
+            ClassReferenceListBuilder builder = new ClassReferenceListBuilder(path);
+            builder.addRoots(jarOfRoots);
+
+            printList(builder.toKeep);
+        } catch (IOException e) {
+            System.err.println("A fatal error occured: " + e.getMessage());
+            System.exit(STATUS_ERROR);
+            return;
+        } finally {
+            try {
+                jarOfRoots.close();
+            } catch (IOException e) {
+                // ignore
+            }
+            if (path != null) {
+                for (ClassPathElement element : path.elements) {
+                    try {
+                        element.close();
+                    } catch (IOException e) {
+                        // keep going, lets do our best.
+                    }
+                }
+            }
+        }
+    }
+
+    private static void printUsage() {
+        System.err.print(USAGE_MESSAGE);
+    }
+
+    private static ClassPathElement getClassPathElement(File file)
+            throws ZipException, IOException {
+        if (file.isDirectory()) {
+            return new FolderPathElement(file);
+        } else if (file.isFile()) {
+            return new ArchivePathElement(new ZipFile(file));
+        } else if (file.exists()) {
+            throw new IOException(file.getAbsolutePath() +
+                    " is not a directory neither a zip file");
+        } else {
+            throw new FileNotFoundException(file.getAbsolutePath());
+        }
+    }
+
+    private static void printList(Set<String> toKeep) {
+        for (String classDescriptor : toKeep) {
+            System.out.print(classDescriptor);
+            System.out.println(CLASS_EXTENSION);
+        }
+    }
+
+    private void addRoots(ZipFile jarOfRoots) throws IOException {
+
+        // keep roots
+        for (Enumeration<? extends ZipEntry> entries = jarOfRoots.entries();
+                entries.hasMoreElements();) {
+            ZipEntry entry = entries.nextElement();
+            String name = entry.getName();
+            if (name.endsWith(CLASS_EXTENSION)) {
+                toKeep.add(name.substring(0, name.length() - CLASS_EXTENSION.length()));
+            }
+        }
+
+        // keep direct references of roots (+ direct references hierarchy)
+        for (Enumeration<? extends ZipEntry> entries = jarOfRoots.entries();
+                entries.hasMoreElements();) {
+            ZipEntry entry = entries.nextElement();
+            String name = entry.getName();
+            if (name.endsWith(CLASS_EXTENSION)) {
+                DirectClassFile classFile;
+                try {
+                    classFile = path.getClass(name);
+                } catch (FileNotFoundException e) {
+                    throw new IOException("Class " + name +
+                            " is missing form original class path " + path, e);
+                }
+
+                addDependencies(classFile.getConstantPool());
+            }
+        }
+    }
+
+    private void addDependencies(ConstantPool pool) {
+        int entryCount = pool.size();
+        for (Constant constant : pool.getEntries()) {
+            if (constant instanceof CstType) {
+                Type type = ((CstType) constant).getClassType();
+                String descriptor = type.getDescriptor();
+                if (descriptor.endsWith(";")) {
+                    int lastBrace = descriptor.lastIndexOf('[');
+                    if (lastBrace < 0) {
+                        addClassWithHierachy(descriptor.substring(1, descriptor.length()-1));
+                    } else {
+                        assert descriptor.length() > lastBrace + 3
+                        && descriptor.charAt(lastBrace + 1) == 'L';
+                        addClassWithHierachy(descriptor.substring(lastBrace + 2,
+                                descriptor.length() - 1));
+                    }
+                }
+            }
+        }
+    }
+
+    private void addClassWithHierachy(String classBinaryName) {
+        if (toKeep.contains(classBinaryName)) {
+            return;
+        }
+
+        String fileName = classBinaryName + CLASS_EXTENSION;
+        try {
+            DirectClassFile classFile = path.getClass(fileName);
+            toKeep.add(classBinaryName);
+            CstType superClass = classFile.getSuperclass();
+            if (superClass != null) {
+                addClassWithHierachy(superClass.getClassType().getDescriptor());
+            }
+
+            TypeList interfaceList = classFile.getInterfaces();
+            int interfaceNumber = interfaceList.size();
+            for (int i = 0; i < interfaceNumber; i++) {
+                addClassWithHierachy(interfaceList.getType(i).getDescriptor());
+            }
+        } catch (FileNotFoundException e) {
+            // Ignore: The referenced type is not in the path it must be part of the libraries.
+        }
+    }
+
+    private static class Path {
+        private List<ClassPathElement> elements = new ArrayList<ClassPathElement>();
+        private String definition;
+        private ByteArrayOutputStream baos = new ByteArrayOutputStream(40 * 1024);
+        private byte[] readBuffer = new byte[20 * 1024];
+
+        public Path(String definition) throws IOException {
+            this.definition = definition;
+            for (String filePath : definition.split(Pattern.quote(File.pathSeparator))) {
+                try {
+                    addElement(getClassPathElement(new File(filePath)));
+                } catch (IOException e) {
+                    throw new IOException("\"" + filePath + "\" can not be used as a classpath"
+                            + " element. ("
+                            + e.getMessage() + ")", e);
+                }
+            }
+        }
+
+        private static byte[] readStream(InputStream in, ByteArrayOutputStream baos, byte[] readBuffer)
+                throws IOException {
+            try {
+                for (;;) {
+                    int amt = in.read(readBuffer);
+                    if (amt < 0) {
+                        break;
+                    }
+
+                    baos.write(readBuffer, 0, amt);
+                }
+            } finally {
+                in.close();
+            }
+            return baos.toByteArray();
+        }
+
+        @Override
+        public String toString() {
+            return definition;
+        }
+
+        private void addElement(ClassPathElement element) {
+            assert element != null;
+            elements.add(element);
+        }
+
+        private DirectClassFile getClass(String path) throws FileNotFoundException {
+            DirectClassFile classFile = null;
+            for (ClassPathElement element : elements) {
+                try {
+                    InputStream in = element.open(path);
+                    try {
+                        byte[] bytes = readStream(in, baos, readBuffer);
+                        baos.reset();
+                        classFile = new DirectClassFile(bytes, path, false);
+                        classFile.setAttributeFactory(StdAttributeFactory.THE_ONE);
+                        break;
+                    } finally {
+                        in.close();
+                    }
+                } catch (IOException e) {
+                    // search next element
+                }
+            }
+            if (classFile == null) {
+                throw new FileNotFoundException(path);
+            }
+            return classFile;
+        }
+    }
+
+
+}
diff --git a/dx/src/com/android/multidex/FolderPathElement.java b/dx/src/com/android/multidex/FolderPathElement.java
new file mode 100644
index 0000000..2242547
--- /dev/null
+++ b/dx/src/com/android/multidex/FolderPathElement.java
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.multidex;
+
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileNotFoundException;
+import java.io.InputStream;
+
+/**
+ * A folder element.
+ */
+class FolderPathElement implements ClassPathElement {
+
+    private File baseFolder;
+
+    public FolderPathElement(File baseFolder) {
+        this.baseFolder = baseFolder;
+    }
+
+    @Override
+    public InputStream open(String path) throws FileNotFoundException {
+        return new FileInputStream(new File(baseFolder,
+                path.replace(SEPARATOR_CHAR, File.separatorChar)));
+    }
+
+    @Override
+    public void close() {
+    }
+
+}