jf/util/ClassFileNameHandler.java

/*
 * [The "BSD licence"]
 * Copyright (c) 2010 Ben Gruver
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package org.jf.util;

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;

import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import java.io.*;
import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.IntBuffer;
import java.util.Collection;
import java.util.regex.Pattern;

/**
 * This class handles the complexities of translating a class name into a file name. i.e. dealing with case insensitive
 * file systems, windows reserved filenames, class names with extremely long package/class elements, etc.
 *
 * The types of transformations this class does include:
 * - append a '#123' style numeric suffix if 2 physical representations collide
 * - replace some number of characters in the middle with a '#' character name if an individual path element is too long
 * - append a '#' if an individual path element would otherwise be considered a reserved filename
 */
public class ClassFileNameHandler {
    private static final int MAX_FILENAME_LENGTH = 255;
    // How many characters to reserve in the physical filename for numeric suffixes
    // Dex files can currently only have 64k classes, so 5 digits plus 1 for an '#' should
    // be sufficient to handle the case when every class has a conflicting name
    private static final int NUMERIC_SUFFIX_RESERVE = 6;

    private final int NO_VALUE = -1;
    private final int CASE_INSENSITIVE = 0;
    private final int CASE_SENSITIVE = 1;
    private int forcedCaseSensitivity = NO_VALUE;

    private DirectoryEntry top;
    private String fileExtension;
    private boolean modifyWindowsReservedFilenames;

    public ClassFileNameHandler(File path, String fileExtension) {
        this.top = new DirectoryEntry(path);
        this.fileExtension = fileExtension;
        this.modifyWindowsReservedFilenames = isWindows();
    }

    // for testing
    public ClassFileNameHandler(File path, String fileExtension, boolean caseSensitive,
                                boolean modifyWindowsReservedFilenames) {
        this.top = new DirectoryEntry(path);
        this.fileExtension = fileExtension;
        this.forcedCaseSensitivity = caseSensitive?CASE_SENSITIVE:CASE_INSENSITIVE;
        this.modifyWindowsReservedFilenames = modifyWindowsReservedFilenames;
    }

    private int getMaxFilenameLength() {
        return MAX_FILENAME_LENGTH - NUMERIC_SUFFIX_RESERVE;
    }

    public File getUniqueFilenameForClass(String className) {
        //class names should be passed in the normal dalvik style, with a leading L, a trailing ;, and using
        //'/' as a separator.
        if (className.charAt(0) != 'L' || className.charAt(className.length()-1) != ';') {
            throw new RuntimeException("Not a valid dalvik class name");
        }

        int packageElementCount = 1;
        for (int i=1; i<className.length()-1; i++) {
            if (className.charAt(i) == '/') {
                packageElementCount++;
            }
        }

        String[] packageElements = new String[packageElementCount];
        int elementIndex = 0;
        int elementStart = 1;
        for (int i=1; i<className.length()-1; i++) {
            if (className.charAt(i) == '/') {
                //if the first char after the initial L is a '/', or if there are
                //two consecutive '/'
                if (i-elementStart==0) {
                    throw new RuntimeException("Not a valid dalvik class name");
                }

                packageElements[elementIndex++] = className.substring(elementStart, i);
                elementStart = ++i;
            }
        }

        //at this point, we have added all the package elements to packageElements, but still need to add
        //the final class name. elementStart should point to the beginning of the class name

        //this will be true if the class ends in a '/', i.e. Lsome/package/className/;
        if (elementStart >= className.length()-1) {
            throw new RuntimeException("Not a valid dalvik class name");
        }

        packageElements[elementIndex] = className.substring(elementStart, className.length()-1);

        return addUniqueChild(top, packageElements, 0);
    }

    @Nonnull
    private File addUniqueChild(@Nonnull DirectoryEntry parent, @Nonnull String[] packageElements,
                                int packageElementIndex) {
        if (packageElementIndex == packageElements.length - 1) {
            FileEntry fileEntry = new FileEntry(parent, packageElements[packageElementIndex] + fileExtension);
            parent.addChild(fileEntry);

            String physicalName = fileEntry.getPhysicalName();

            // the physical name should be set when adding it as a child to the parent
            assert  physicalName != null;

            return new File(parent.file, physicalName);
        } else {
            DirectoryEntry directoryEntry = new DirectoryEntry(parent, packageElements[packageElementIndex]);
            directoryEntry = (DirectoryEntry)parent.addChild(directoryEntry);
            return addUniqueChild(directoryEntry, packageElements, packageElementIndex+1);
        }
    }

    private static int utf8Length(String str) {
        int utf8Length = 0;
        int i=0;
        while (i<str.length()) {
            int c = str.codePointAt(i);
            utf8Length += utf8Length(c);
            i += Character.charCount(c);
        }
        return utf8Length;
    }

    private static int utf8Length(int codePoint) {
        if (codePoint < 0x80) {
            return 1;
        } else if (codePoint < 0x800) {
            return 2;
        } else if (codePoint < 0x10000) {
            return 3;
        } else {
            return 4;
        }
    }

    /**
     * Shortens an individual file/directory name, removing the necessary number of code points
     * from the middle of the string such that the utf-8 encoding of the string is at least
     * bytesToRemove bytes shorter than the original.
     *
     * The removed codePoints in the middle of the string will be replaced with a # character.
     */
    @Nonnull
    static String shortenPathComponent(@Nonnull String pathComponent, int bytesToRemove) {
        // We replace the removed part with a #, so we need to remove 1 extra char
        bytesToRemove++;

        int[] codePoints;
        try {
            IntBuffer intBuffer = ByteBuffer.wrap(pathComponent.getBytes("UTF-32BE")).asIntBuffer();
            codePoints = new int[intBuffer.limit()];
            intBuffer.get(codePoints);
        } catch (UnsupportedEncodingException ex) {
            throw new RuntimeException(ex);
        }

        int midPoint = codePoints.length/2;

        int firstEnd = midPoint; // exclusive
        int secondStart = midPoint+1; // inclusive
        int bytesRemoved = utf8Length(codePoints[midPoint]);

        // if we have an even number of codepoints, start by removing both middle characters,
        // unless just removing the first already removes enough bytes
        if (((codePoints.length % 2) == 0) && bytesRemoved < bytesToRemove) {
            bytesRemoved += utf8Length(codePoints[secondStart]);
            secondStart++;
        }

        while ((bytesRemoved < bytesToRemove) &&
                (firstEnd > 0 || secondStart < codePoints.length)) {
            if (firstEnd > 0) {
                firstEnd--;
                bytesRemoved += utf8Length(codePoints[firstEnd]);
            }

            if (bytesRemoved < bytesToRemove && secondStart < codePoints.length) {
                bytesRemoved += utf8Length(codePoints[secondStart]);
                secondStart++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i=0; i<firstEnd; i++) {
            sb.appendCodePoint(codePoints[i]);
        }
        sb.append('#');
        for (int i=secondStart; i<codePoints.length; i++) {
            sb.appendCodePoint(codePoints[i]);
        }

        return sb.toString();
    }

    private static boolean isWindows() {
        return System.getProperty("os.name").startsWith("Windows");
    }

    private static Pattern reservedFileNameRegex = Pattern.compile("^(CON|PRN|AUX|NUL|COM[1-9]|LPT[1-9])(\\..*)?$",
            Pattern.CASE_INSENSITIVE);
    private static boolean isReservedFileName(String className) {
        return reservedFileNameRegex.matcher(className).matches();
    }

    private abstract class FileSystemEntry {
        @Nullable public final DirectoryEntry parent;
        @Nonnull public final String logicalName;
        @Nullable protected String physicalName = null;

        private FileSystemEntry(@Nullable DirectoryEntry parent, @Nonnull String logicalName) {
            this.parent = parent;
            this.logicalName = logicalName;
        }

        @Nonnull public String getNormalizedName(boolean preserveCase) {
            String elementName = logicalName;
            if (!preserveCase && parent != null && !parent.isCaseSensitive()) {
                elementName = elementName.toLowerCase();
            }

            if (modifyWindowsReservedFilenames && isReservedFileName(elementName)) {
                elementName = addSuffixBeforeExtension(elementName, "#");
            }

            int utf8Length = utf8Length(elementName);
            if (utf8Length > getMaxFilenameLength()) {
                elementName = shortenPathComponent(elementName, utf8Length - getMaxFilenameLength());
            }
            return elementName;
        }

        @Nullable
        public String getPhysicalName() {
            return physicalName;
        }

        public void setSuffix(int suffix) {
            if (suffix < 0 || suffix > 99999) {
                throw new IllegalArgumentException("suffix must be in [0, 100000)");
            }

            if (this.physicalName != null) {
                throw new IllegalStateException("The suffix can only be set once");
            }
            this.physicalName = makePhysicalName(suffix);
        }

        protected abstract String makePhysicalName(int suffix);
    }

    private class DirectoryEntry extends FileSystemEntry {
        @Nullable private File file = null;
        private int caseSensitivity = forcedCaseSensitivity;

        // maps a normalized (but not suffixed) entry name to 1 or more FileSystemEntries.
        // Each FileSystemEntry asociated with a normalized entry name must have a distinct
        // physical name
        private final Multimap<String, FileSystemEntry> children = ArrayListMultimap.create();

        public DirectoryEntry(@Nonnull File path) {
            super(null, path.getName());
            file = path;
            physicalName = file.getName();
        }

        public DirectoryEntry(@Nullable DirectoryEntry parent, @Nonnull String logicalName) {
            super(parent, logicalName);
        }

        public synchronized FileSystemEntry addChild(FileSystemEntry entry) {
            String normalizedChildName = entry.getNormalizedName(false);
            Collection<FileSystemEntry> entries = children.get(normalizedChildName);
            if (entry instanceof DirectoryEntry) {
                for (FileSystemEntry childEntry: entries) {
                    if (childEntry.logicalName.equals(entry.logicalName)) {
                        return childEntry;
                    }
                }
            }
            entry.setSuffix(entries.size());
            entries.add(entry);
            return entry;
        }

        @Override
        protected String makePhysicalName(int suffix) {
            if (suffix > 0) {
                return getNormalizedName(true) + "." + Integer.toString(suffix);
            }
            return getNormalizedName(true);
        }

        @Override
        public void setSuffix(int suffix) {
            super.setSuffix(suffix);
            String physicalName = getPhysicalName();
            if (parent != null && physicalName != null) {
                file = new File(parent.file, physicalName);
            }
        }

        protected boolean isCaseSensitive() {
            if (getPhysicalName() == null || file == null) {
                throw new IllegalStateException("Must call setSuffix() first");
            }

            if (caseSensitivity != NO_VALUE) {
                return caseSensitivity == CASE_SENSITIVE;
            }

            File path = file;
            if (path.exists() && path.isFile()) {
                if (!path.delete()) {
                    throw new ExceptionWithContext("Can't delete %s to make it into a directory",
                            path.getAbsolutePath());
                }
            }

            if (!path.exists() && !path.mkdirs()) {
                throw new ExceptionWithContext("Couldn't create directory %s", path.getAbsolutePath());
            }

            try {
                boolean result = testCaseSensitivity(path);
                caseSensitivity = result?CASE_SENSITIVE:CASE_INSENSITIVE;
                return result;
            } catch (IOException ex) {
                return false;
            }
        }

        private boolean testCaseSensitivity(File path) throws IOException {
            int num = 1;
            File f, f2;
            do {
                f = new File(path, "test." + num);
                f2 = new File(path, "TEST." + num++);
            } while(f.exists() || f2.exists());

            try {
                try {
                    FileWriter writer = new FileWriter(f);
                    writer.write("test");
                    writer.flush();
                    writer.close();
                } catch (IOException ex) {
                    try {f.delete();} catch (Exception ex2) {}
                    throw ex;
                }

                if (f2.exists()) {
                    return false;
                }

                if (f2.createNewFile()) {
                    return true;
                }

                //the above 2 tests should catch almost all cases. But maybe there was a failure while creating f2
                //that isn't related to case sensitivity. Let's see if we can open the file we just created using
                //f2
                try {
                    CharBuffer buf = CharBuffer.allocate(32);
                    FileReader reader = new FileReader(f2);

                    while (reader.read(buf) != -1 && buf.length() < 4);
                    if (buf.length() == 4 && buf.toString().equals("test")) {
                        return false;
                    } else {
                        //we probably shouldn't get here. If the filesystem was case-sensetive, creating a new
                        //FileReader should have thrown a FileNotFoundException. Otherwise, we should have opened
                        //the file and read in the string "test". It's remotely possible that someone else modified
                        //the file after we created it. Let's be safe and return false here as well
                        assert(false);
                        return false;
                    }
                } catch (FileNotFoundException ex) {
                    return true;
                }
            } finally {
                try { f.delete(); } catch (Exception ex) {}
                try { f2.delete(); } catch (Exception ex) {}
            }
        }
    }

    private class FileEntry extends FileSystemEntry {
        private FileEntry(@Nullable DirectoryEntry parent, @Nonnull String logicalName) {
            super(parent, logicalName);
        }

        @Override
        protected String makePhysicalName(int suffix) {
            if (suffix > 0) {
                return addSuffixBeforeExtension(getNormalizedName(true), '.' + Integer.toString(suffix));
            }
            return getNormalizedName(true);
        }
    }

    private static String addSuffixBeforeExtension(String pathElement, String suffix) {
        int extensionStart = pathElement.lastIndexOf('.');

        StringBuilder newName = new StringBuilder(pathElement.length() + suffix.length() + 1);
        if (extensionStart < 0) {
            newName.append(pathElement);
            newName.append(suffix);
        } else {
            newName.append(pathElement.subSequence(0, extensionStart));
            newName.append(suffix);
            newName.append(pathElement.subSequence(extensionStart, pathElement.length()));
        }
        return newName.toString();
    }
}