1 /*
2  * [The "BSD licence"]
3  * Copyright (c) 2010 Ben Gruver
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  * 3. The name of the author may not be used to endorse or promote products
15  *    derived from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 package org.jf.util;
30 
31 import com.google.common.collect.ArrayListMultimap;
32 import com.google.common.collect.Multimap;
33 
34 import javax.annotation.Nonnull;
35 import javax.annotation.Nullable;
36 import java.io.*;
37 import java.nio.ByteBuffer;
38 import java.nio.CharBuffer;
39 import java.nio.IntBuffer;
40 import java.util.Collection;
41 import java.util.regex.Pattern;
42 
43 /**
44  * This class handles the complexities of translating a class name into a file name. i.e. dealing with case insensitive
45  * file systems, windows reserved filenames, class names with extremely long package/class elements, etc.
46  *
47  * The types of transformations this class does include:
48  * - append a '#123' style numeric suffix if 2 physical representations collide
49  * - replace some number of characters in the middle with a '#' character name if an individual path element is too long
50  * - append a '#' if an individual path element would otherwise be considered a reserved filename
51  */
52 public class ClassFileNameHandler {
53     private static final int MAX_FILENAME_LENGTH = 255;
54     // How many characters to reserve in the physical filename for numeric suffixes
55     // Dex files can currently only have 64k classes, so 5 digits plus 1 for an '#' should
56     // be sufficient to handle the case when every class has a conflicting name
57     private static final int NUMERIC_SUFFIX_RESERVE = 6;
58 
59     private final int NO_VALUE = -1;
60     private final int CASE_INSENSITIVE = 0;
61     private final int CASE_SENSITIVE = 1;
62     private int forcedCaseSensitivity = NO_VALUE;
63 
64     private DirectoryEntry top;
65     private String fileExtension;
66     private boolean modifyWindowsReservedFilenames;
67 
ClassFileNameHandler(File path, String fileExtension)68     public ClassFileNameHandler(File path, String fileExtension) {
69         this.top = new DirectoryEntry(path);
70         this.fileExtension = fileExtension;
71         this.modifyWindowsReservedFilenames = isWindows();
72     }
73 
74     // for testing
ClassFileNameHandler(File path, String fileExtension, boolean caseSensitive, boolean modifyWindowsReservedFilenames)75     public ClassFileNameHandler(File path, String fileExtension, boolean caseSensitive,
76                                 boolean modifyWindowsReservedFilenames) {
77         this.top = new DirectoryEntry(path);
78         this.fileExtension = fileExtension;
79         this.forcedCaseSensitivity = caseSensitive?CASE_SENSITIVE:CASE_INSENSITIVE;
80         this.modifyWindowsReservedFilenames = modifyWindowsReservedFilenames;
81     }
82 
getMaxFilenameLength()83     private int getMaxFilenameLength() {
84         return MAX_FILENAME_LENGTH - NUMERIC_SUFFIX_RESERVE;
85     }
86 
getUniqueFilenameForClass(String className)87     public File getUniqueFilenameForClass(String className) {
88         //class names should be passed in the normal dalvik style, with a leading L, a trailing ;, and using
89         //'/' as a separator.
90         if (className.charAt(0) != 'L' || className.charAt(className.length()-1) != ';') {
91             throw new RuntimeException("Not a valid dalvik class name");
92         }
93 
94         int packageElementCount = 1;
95         for (int i=1; i<className.length()-1; i++) {
96             if (className.charAt(i) == '/') {
97                 packageElementCount++;
98             }
99         }
100 
101         String[] packageElements = new String[packageElementCount];
102         int elementIndex = 0;
103         int elementStart = 1;
104         for (int i=1; i<className.length()-1; i++) {
105             if (className.charAt(i) == '/') {
106                 //if the first char after the initial L is a '/', or if there are
107                 //two consecutive '/'
108                 if (i-elementStart==0) {
109                     throw new RuntimeException("Not a valid dalvik class name");
110                 }
111 
112                 packageElements[elementIndex++] = className.substring(elementStart, i);
113                 elementStart = ++i;
114             }
115         }
116 
117         //at this point, we have added all the package elements to packageElements, but still need to add
118         //the final class name. elementStart should point to the beginning of the class name
119 
120         //this will be true if the class ends in a '/', i.e. Lsome/package/className/;
121         if (elementStart >= className.length()-1) {
122             throw new RuntimeException("Not a valid dalvik class name");
123         }
124 
125         packageElements[elementIndex] = className.substring(elementStart, className.length()-1);
126 
127         return addUniqueChild(top, packageElements, 0);
128     }
129 
130     @Nonnull
addUniqueChild(@onnull DirectoryEntry parent, @Nonnull String[] packageElements, int packageElementIndex)131     private File addUniqueChild(@Nonnull DirectoryEntry parent, @Nonnull String[] packageElements,
132                                 int packageElementIndex) {
133         if (packageElementIndex == packageElements.length - 1) {
134             FileEntry fileEntry = new FileEntry(parent, packageElements[packageElementIndex] + fileExtension);
135             parent.addChild(fileEntry);
136 
137             String physicalName = fileEntry.getPhysicalName();
138 
139             // the physical name should be set when adding it as a child to the parent
140             assert  physicalName != null;
141 
142             return new File(parent.file, physicalName);
143         } else {
144             DirectoryEntry directoryEntry = new DirectoryEntry(parent, packageElements[packageElementIndex]);
145             directoryEntry = (DirectoryEntry)parent.addChild(directoryEntry);
146             return addUniqueChild(directoryEntry, packageElements, packageElementIndex+1);
147         }
148     }
149 
utf8Length(String str)150     private static int utf8Length(String str) {
151         int utf8Length = 0;
152         int i=0;
153         while (i<str.length()) {
154             int c = str.codePointAt(i);
155             utf8Length += utf8Length(c);
156             i += Character.charCount(c);
157         }
158         return utf8Length;
159     }
160 
utf8Length(int codePoint)161     private static int utf8Length(int codePoint) {
162         if (codePoint < 0x80) {
163             return 1;
164         } else if (codePoint < 0x800) {
165             return 2;
166         } else if (codePoint < 0x10000) {
167             return 3;
168         } else {
169             return 4;
170         }
171     }
172 
173     /**
174      * Shortens an individual file/directory name, removing the necessary number of code points
175      * from the middle of the string such that the utf-8 encoding of the string is at least
176      * bytesToRemove bytes shorter than the original.
177      *
178      * The removed codePoints in the middle of the string will be replaced with a # character.
179      */
180     @Nonnull
shortenPathComponent(@onnull String pathComponent, int bytesToRemove)181     static String shortenPathComponent(@Nonnull String pathComponent, int bytesToRemove) {
182         // We replace the removed part with a #, so we need to remove 1 extra char
183         bytesToRemove++;
184 
185         int[] codePoints;
186         try {
187             IntBuffer intBuffer = ByteBuffer.wrap(pathComponent.getBytes("UTF-32BE")).asIntBuffer();
188             codePoints = new int[intBuffer.limit()];
189             intBuffer.get(codePoints);
190         } catch (UnsupportedEncodingException ex) {
191             throw new RuntimeException(ex);
192         }
193 
194         int midPoint = codePoints.length/2;
195 
196         int firstEnd = midPoint; // exclusive
197         int secondStart = midPoint+1; // inclusive
198         int bytesRemoved = utf8Length(codePoints[midPoint]);
199 
200         // if we have an even number of codepoints, start by removing both middle characters,
201         // unless just removing the first already removes enough bytes
202         if (((codePoints.length % 2) == 0) && bytesRemoved < bytesToRemove) {
203             bytesRemoved += utf8Length(codePoints[secondStart]);
204             secondStart++;
205         }
206 
207         while ((bytesRemoved < bytesToRemove) &&
208                 (firstEnd > 0 || secondStart < codePoints.length)) {
209             if (firstEnd > 0) {
210                 firstEnd--;
211                 bytesRemoved += utf8Length(codePoints[firstEnd]);
212             }
213 
214             if (bytesRemoved < bytesToRemove && secondStart < codePoints.length) {
215                 bytesRemoved += utf8Length(codePoints[secondStart]);
216                 secondStart++;
217             }
218         }
219 
220         StringBuilder sb = new StringBuilder();
221         for (int i=0; i<firstEnd; i++) {
222             sb.appendCodePoint(codePoints[i]);
223         }
224         sb.append('#');
225         for (int i=secondStart; i<codePoints.length; i++) {
226             sb.appendCodePoint(codePoints[i]);
227         }
228 
229         return sb.toString();
230     }
231 
isWindows()232     private static boolean isWindows() {
233         return System.getProperty("os.name").startsWith("Windows");
234     }
235 
236     private static Pattern reservedFileNameRegex = Pattern.compile("^(CON|PRN|AUX|NUL|COM[1-9]|LPT[1-9])(\\..*)?$",
237             Pattern.CASE_INSENSITIVE);
isReservedFileName(String className)238     private static boolean isReservedFileName(String className) {
239         return reservedFileNameRegex.matcher(className).matches();
240     }
241 
242     private abstract class FileSystemEntry {
243         @Nullable public final DirectoryEntry parent;
244         @Nonnull public final String logicalName;
245         @Nullable protected String physicalName = null;
246 
FileSystemEntry(@ullable DirectoryEntry parent, @Nonnull String logicalName)247         private FileSystemEntry(@Nullable DirectoryEntry parent, @Nonnull String logicalName) {
248             this.parent = parent;
249             this.logicalName = logicalName;
250         }
251 
getNormalizedName(boolean preserveCase)252         @Nonnull public String getNormalizedName(boolean preserveCase) {
253             String elementName = logicalName;
254             if (!preserveCase && parent != null && !parent.isCaseSensitive()) {
255                 elementName = elementName.toLowerCase();
256             }
257 
258             if (modifyWindowsReservedFilenames && isReservedFileName(elementName)) {
259                 elementName = addSuffixBeforeExtension(elementName, "#");
260             }
261 
262             int utf8Length = utf8Length(elementName);
263             if (utf8Length > getMaxFilenameLength()) {
264                 elementName = shortenPathComponent(elementName, utf8Length - getMaxFilenameLength());
265             }
266             return elementName;
267         }
268 
269         @Nullable
getPhysicalName()270         public String getPhysicalName() {
271             return physicalName;
272         }
273 
setSuffix(int suffix)274         public void setSuffix(int suffix) {
275             if (suffix < 0 || suffix > 99999) {
276                 throw new IllegalArgumentException("suffix must be in [0, 100000)");
277             }
278 
279             if (this.physicalName != null) {
280                 throw new IllegalStateException("The suffix can only be set once");
281             }
282             this.physicalName = makePhysicalName(suffix);
283         }
284 
makePhysicalName(int suffix)285         protected abstract String makePhysicalName(int suffix);
286     }
287 
288     private class DirectoryEntry extends FileSystemEntry {
289         @Nullable private File file = null;
290         private int caseSensitivity = forcedCaseSensitivity;
291 
292         // maps a normalized (but not suffixed) entry name to 1 or more FileSystemEntries.
293         // Each FileSystemEntry asociated with a normalized entry name must have a distinct
294         // physical name
295         private final Multimap<String, FileSystemEntry> children = ArrayListMultimap.create();
296 
DirectoryEntry(@onnull File path)297         public DirectoryEntry(@Nonnull File path) {
298             super(null, path.getName());
299             file = path;
300             physicalName = file.getName();
301         }
302 
DirectoryEntry(@ullable DirectoryEntry parent, @Nonnull String logicalName)303         public DirectoryEntry(@Nullable DirectoryEntry parent, @Nonnull String logicalName) {
304             super(parent, logicalName);
305         }
306 
addChild(FileSystemEntry entry)307         public synchronized FileSystemEntry addChild(FileSystemEntry entry) {
308             String normalizedChildName = entry.getNormalizedName(false);
309             Collection<FileSystemEntry> entries = children.get(normalizedChildName);
310             if (entry instanceof DirectoryEntry) {
311                 for (FileSystemEntry childEntry: entries) {
312                     if (childEntry.logicalName.equals(entry.logicalName)) {
313                         return childEntry;
314                     }
315                 }
316             }
317             entry.setSuffix(entries.size());
318             entries.add(entry);
319             return entry;
320         }
321 
322         @Override
makePhysicalName(int suffix)323         protected String makePhysicalName(int suffix) {
324             if (suffix > 0) {
325                 return getNormalizedName(true) + "." + Integer.toString(suffix);
326             }
327             return getNormalizedName(true);
328         }
329 
330         @Override
setSuffix(int suffix)331         public void setSuffix(int suffix) {
332             super.setSuffix(suffix);
333             String physicalName = getPhysicalName();
334             if (parent != null && physicalName != null) {
335                 file = new File(parent.file, physicalName);
336             }
337         }
338 
isCaseSensitive()339         protected boolean isCaseSensitive() {
340             if (getPhysicalName() == null || file == null) {
341                 throw new IllegalStateException("Must call setSuffix() first");
342             }
343 
344             if (caseSensitivity != NO_VALUE) {
345                 return caseSensitivity == CASE_SENSITIVE;
346             }
347 
348             File path = file;
349             if (path.exists() && path.isFile()) {
350                 if (!path.delete()) {
351                     throw new ExceptionWithContext("Can't delete %s to make it into a directory",
352                             path.getAbsolutePath());
353                 }
354             }
355 
356             if (!path.exists() && !path.mkdirs()) {
357                 throw new ExceptionWithContext("Couldn't create directory %s", path.getAbsolutePath());
358             }
359 
360             try {
361                 boolean result = testCaseSensitivity(path);
362                 caseSensitivity = result?CASE_SENSITIVE:CASE_INSENSITIVE;
363                 return result;
364             } catch (IOException ex) {
365                 return false;
366             }
367         }
368 
testCaseSensitivity(File path)369         private boolean testCaseSensitivity(File path) throws IOException {
370             int num = 1;
371             File f, f2;
372             do {
373                 f = new File(path, "test." + num);
374                 f2 = new File(path, "TEST." + num++);
375             } while(f.exists() || f2.exists());
376 
377             try {
378                 try {
379                     FileWriter writer = new FileWriter(f);
380                     writer.write("test");
381                     writer.flush();
382                     writer.close();
383                 } catch (IOException ex) {
384                     try {f.delete();} catch (Exception ex2) {}
385                     throw ex;
386                 }
387 
388                 if (f2.exists()) {
389                     return false;
390                 }
391 
392                 if (f2.createNewFile()) {
393                     return true;
394                 }
395 
396                 //the above 2 tests should catch almost all cases. But maybe there was a failure while creating f2
397                 //that isn't related to case sensitivity. Let's see if we can open the file we just created using
398                 //f2
399                 try {
400                     CharBuffer buf = CharBuffer.allocate(32);
401                     FileReader reader = new FileReader(f2);
402 
403                     while (reader.read(buf) != -1 && buf.length() < 4);
404                     if (buf.length() == 4 && buf.toString().equals("test")) {
405                         return false;
406                     } else {
407                         //we probably shouldn't get here. If the filesystem was case-sensetive, creating a new
408                         //FileReader should have thrown a FileNotFoundException. Otherwise, we should have opened
409                         //the file and read in the string "test". It's remotely possible that someone else modified
410                         //the file after we created it. Let's be safe and return false here as well
411                         assert(false);
412                         return false;
413                     }
414                 } catch (FileNotFoundException ex) {
415                     return true;
416                 }
417             } finally {
418                 try { f.delete(); } catch (Exception ex) {}
419                 try { f2.delete(); } catch (Exception ex) {}
420             }
421         }
422     }
423 
424     private class FileEntry extends FileSystemEntry {
FileEntry(@ullable DirectoryEntry parent, @Nonnull String logicalName)425         private FileEntry(@Nullable DirectoryEntry parent, @Nonnull String logicalName) {
426             super(parent, logicalName);
427         }
428 
429         @Override
makePhysicalName(int suffix)430         protected String makePhysicalName(int suffix) {
431             if (suffix > 0) {
432                 return addSuffixBeforeExtension(getNormalizedName(true), '.' + Integer.toString(suffix));
433             }
434             return getNormalizedName(true);
435         }
436     }
437 
addSuffixBeforeExtension(String pathElement, String suffix)438     private static String addSuffixBeforeExtension(String pathElement, String suffix) {
439         int extensionStart = pathElement.lastIndexOf('.');
440 
441         StringBuilder newName = new StringBuilder(pathElement.length() + suffix.length() + 1);
442         if (extensionStart < 0) {
443             newName.append(pathElement);
444             newName.append(suffix);
445         } else {
446             newName.append(pathElement.subSequence(0, extensionStart));
447             newName.append(suffix);
448             newName.append(pathElement.subSequence(extensionStart, pathElement.length()));
449         }
450         return newName.toString();
451     }
452 }
453