DO NOT MERGE. Use resolved path for both checking and opening. am: 8a2e551874
[android/platform/packages/providers/DownloadProvider.git] / src / com / android / providers / downloads / Helpers.java
1 /*
2  * Copyright (C) 2008 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package com.android.providers.downloads;
18
19 import static com.android.providers.downloads.Constants.TAG;
20
21 import android.content.Context;
22 import android.net.Uri;
23 import android.os.Environment;
24 import android.os.SystemClock;
25 import android.provider.Downloads;
26 import android.util.Log;
27 import android.webkit.MimeTypeMap;
28
29 import java.io.File;
30 import java.io.IOException;
31 import java.util.Random;
32 import java.util.Set;
33 import java.util.regex.Matcher;
34 import java.util.regex.Pattern;
35
36 /**
37  * Some helper functions for the download manager
38  */
39 public class Helpers {
40     public static Random sRandom = new Random(SystemClock.uptimeMillis());
41
42     /** Regex used to parse content-disposition headers */
43     private static final Pattern CONTENT_DISPOSITION_PATTERN =
44             Pattern.compile("attachment;\\s*filename\\s*=\\s*\"([^\"]*)\"");
45
46     private static final Object sUniqueLock = new Object();
47
48     private Helpers() {
49     }
50
51     /*
52      * Parse the Content-Disposition HTTP Header. The format of the header
53      * is defined here: http://www.w3.org/Protocols/rfc2616/rfc2616-sec19.html
54      * This header provides a filename for content that is going to be
55      * downloaded to the file system. We only support the attachment type.
56      */
57     private static String parseContentDisposition(String contentDisposition) {
58         try {
59             Matcher m = CONTENT_DISPOSITION_PATTERN.matcher(contentDisposition);
60             if (m.find()) {
61                 return m.group(1);
62             }
63         } catch (IllegalStateException ex) {
64              // This function is defined as returning null when it can't parse the header
65         }
66         return null;
67     }
68
69     /**
70      * Creates a filename (where the file should be saved) from info about a download.
71      */
72     static String generateSaveFile(
73             Context context,
74             String url,
75             String hint,
76             String contentDisposition,
77             String contentLocation,
78             String mimeType,
79             int destination,
80             long contentLength,
81             StorageManager storageManager) throws StopRequestException {
82         if (contentLength < 0) {
83             contentLength = 0;
84         }
85         String path;
86         File base = null;
87         if (destination == Downloads.Impl.DESTINATION_FILE_URI) {
88             path = Uri.parse(hint).getPath();
89         } else {
90             base = storageManager.locateDestinationDirectory(mimeType, destination,
91                     contentLength);
92             path = chooseFilename(url, hint, contentDisposition, contentLocation,
93                                              destination);
94         }
95         storageManager.verifySpace(destination, path, contentLength);
96         if (DownloadDrmHelper.isDrmConvertNeeded(mimeType)) {
97             path = DownloadDrmHelper.modifyDrmFwLockFileExtension(path);
98         }
99         path = getFullPath(path, mimeType, destination, base);
100         return path;
101     }
102
103     static String getFullPath(String filename, String mimeType, int destination, File base)
104             throws StopRequestException {
105         String extension = null;
106         int dotIndex = filename.lastIndexOf('.');
107         boolean missingExtension = dotIndex < 0 || dotIndex < filename.lastIndexOf('/');
108         if (destination == Downloads.Impl.DESTINATION_FILE_URI) {
109             // Destination is explicitly set - do not change the extension
110             if (missingExtension) {
111                 extension = "";
112             } else {
113                 extension = filename.substring(dotIndex);
114                 filename = filename.substring(0, dotIndex);
115             }
116         } else {
117             // Split filename between base and extension
118             // Add an extension if filename does not have one
119             if (missingExtension) {
120                 extension = chooseExtensionFromMimeType(mimeType, true);
121             } else {
122                 extension = chooseExtensionFromFilename(mimeType, destination, filename, dotIndex);
123                 filename = filename.substring(0, dotIndex);
124             }
125         }
126
127         boolean recoveryDir = Constants.RECOVERY_DIRECTORY.equalsIgnoreCase(filename + extension);
128
129         if (base != null) {
130             filename = base.getPath() + File.separator + filename;
131         }
132
133         if (Constants.LOGVV) {
134             Log.v(Constants.TAG, "target file: " + filename + extension);
135         }
136
137         synchronized (sUniqueLock) {
138             final String path = chooseUniqueFilenameLocked(
139                     destination, filename, extension, recoveryDir);
140
141             // Claim this filename inside lock to prevent other threads from
142             // clobbering us. We're not paranoid enough to use O_EXCL.
143             try {
144                 File file = new File(path);
145                 File parent = file.getParentFile();
146
147                 // Make sure the parent directories exists before generates new file
148                 if (parent != null && !parent.exists()) {
149                     parent.mkdirs();
150                 }
151
152                 file.createNewFile();
153             } catch (IOException e) {
154                 throw new StopRequestException(Downloads.Impl.STATUS_FILE_ERROR,
155                         "Failed to create target file " + path, e);
156             }
157             return path;
158         }
159     }
160
161     private static String chooseFilename(String url, String hint, String contentDisposition,
162             String contentLocation, int destination) {
163         String filename = null;
164
165         // First, try to use the hint from the application, if there's one
166         if (filename == null && hint != null && !hint.endsWith("/")) {
167             if (Constants.LOGVV) {
168                 Log.v(Constants.TAG, "getting filename from hint");
169             }
170             int index = hint.lastIndexOf('/') + 1;
171             if (index > 0) {
172                 filename = hint.substring(index);
173             } else {
174                 filename = hint;
175             }
176         }
177
178         // If we couldn't do anything with the hint, move toward the content disposition
179         if (filename == null && contentDisposition != null) {
180             filename = parseContentDisposition(contentDisposition);
181             if (filename != null) {
182                 if (Constants.LOGVV) {
183                     Log.v(Constants.TAG, "getting filename from content-disposition");
184                 }
185                 int index = filename.lastIndexOf('/') + 1;
186                 if (index > 0) {
187                     filename = filename.substring(index);
188                 }
189             }
190         }
191
192         // If we still have nothing at this point, try the content location
193         if (filename == null && contentLocation != null) {
194             String decodedContentLocation = Uri.decode(contentLocation);
195             if (decodedContentLocation != null
196                     && !decodedContentLocation.endsWith("/")
197                     && decodedContentLocation.indexOf('?') < 0) {
198                 if (Constants.LOGVV) {
199                     Log.v(Constants.TAG, "getting filename from content-location");
200                 }
201                 int index = decodedContentLocation.lastIndexOf('/') + 1;
202                 if (index > 0) {
203                     filename = decodedContentLocation.substring(index);
204                 } else {
205                     filename = decodedContentLocation;
206                 }
207             }
208         }
209
210         // If all the other http-related approaches failed, use the plain uri
211         if (filename == null) {
212             String decodedUrl = Uri.decode(url);
213             if (decodedUrl != null
214                     && !decodedUrl.endsWith("/") && decodedUrl.indexOf('?') < 0) {
215                 int index = decodedUrl.lastIndexOf('/') + 1;
216                 if (index > 0) {
217                     if (Constants.LOGVV) {
218                         Log.v(Constants.TAG, "getting filename from uri");
219                     }
220                     filename = decodedUrl.substring(index);
221                 }
222             }
223         }
224
225         // Finally, if couldn't get filename from URI, get a generic filename
226         if (filename == null) {
227             if (Constants.LOGVV) {
228                 Log.v(Constants.TAG, "using default filename");
229             }
230             filename = Constants.DEFAULT_DL_FILENAME;
231         }
232
233         // The VFAT file system is assumed as target for downloads.
234         // Replace invalid characters according to the specifications of VFAT.
235         filename = replaceInvalidVfatCharacters(filename);
236
237         return filename;
238     }
239
240     private static String chooseExtensionFromMimeType(String mimeType, boolean useDefaults) {
241         String extension = null;
242         if (mimeType != null) {
243             extension = MimeTypeMap.getSingleton().getExtensionFromMimeType(mimeType);
244             if (extension != null) {
245                 if (Constants.LOGVV) {
246                     Log.v(Constants.TAG, "adding extension from type");
247                 }
248                 extension = "." + extension;
249             } else {
250                 if (Constants.LOGVV) {
251                     Log.v(Constants.TAG, "couldn't find extension for " + mimeType);
252                 }
253             }
254         }
255         if (extension == null) {
256             if (mimeType != null && mimeType.toLowerCase().startsWith("text/")) {
257                 if (mimeType.equalsIgnoreCase("text/html")) {
258                     if (Constants.LOGVV) {
259                         Log.v(Constants.TAG, "adding default html extension");
260                     }
261                     extension = Constants.DEFAULT_DL_HTML_EXTENSION;
262                 } else if (useDefaults) {
263                     if (Constants.LOGVV) {
264                         Log.v(Constants.TAG, "adding default text extension");
265                     }
266                     extension = Constants.DEFAULT_DL_TEXT_EXTENSION;
267                 }
268             } else if (useDefaults) {
269                 if (Constants.LOGVV) {
270                     Log.v(Constants.TAG, "adding default binary extension");
271                 }
272                 extension = Constants.DEFAULT_DL_BINARY_EXTENSION;
273             }
274         }
275         return extension;
276     }
277
278     private static String chooseExtensionFromFilename(String mimeType, int destination,
279             String filename, int lastDotIndex) {
280         String extension = null;
281         if (mimeType != null) {
282             // Compare the last segment of the extension against the mime type.
283             // If there's a mismatch, discard the entire extension.
284             String typeFromExt = MimeTypeMap.getSingleton().getMimeTypeFromExtension(
285                     filename.substring(lastDotIndex + 1));
286             if (typeFromExt == null || !typeFromExt.equalsIgnoreCase(mimeType)) {
287                 extension = chooseExtensionFromMimeType(mimeType, false);
288                 if (extension != null) {
289                     if (Constants.LOGVV) {
290                         Log.v(Constants.TAG, "substituting extension from type");
291                     }
292                 } else {
293                     if (Constants.LOGVV) {
294                         Log.v(Constants.TAG, "couldn't find extension for " + mimeType);
295                     }
296                 }
297             }
298         }
299         if (extension == null) {
300             if (Constants.LOGVV) {
301                 Log.v(Constants.TAG, "keeping extension");
302             }
303             extension = filename.substring(lastDotIndex);
304         }
305         return extension;
306     }
307
308     private static String chooseUniqueFilenameLocked(int destination, String filename,
309             String extension, boolean recoveryDir) throws StopRequestException {
310         String fullFilename = filename + extension;
311         if (!new File(fullFilename).exists()
312                 && (!recoveryDir ||
313                 (destination != Downloads.Impl.DESTINATION_CACHE_PARTITION &&
314                         destination != Downloads.Impl.DESTINATION_SYSTEMCACHE_PARTITION &&
315                         destination != Downloads.Impl.DESTINATION_CACHE_PARTITION_PURGEABLE &&
316                         destination != Downloads.Impl.DESTINATION_CACHE_PARTITION_NOROAMING))) {
317             return fullFilename;
318         }
319         filename = filename + Constants.FILENAME_SEQUENCE_SEPARATOR;
320         /*
321         * This number is used to generate partially randomized filenames to avoid
322         * collisions.
323         * It starts at 1.
324         * The next 9 iterations increment it by 1 at a time (up to 10).
325         * The next 9 iterations increment it by 1 to 10 (random) at a time.
326         * The next 9 iterations increment it by 1 to 100 (random) at a time.
327         * ... Up to the point where it increases by 100000000 at a time.
328         * (the maximum value that can be reached is 1000000000)
329         * As soon as a number is reached that generates a filename that doesn't exist,
330         *     that filename is used.
331         * If the filename coming in is [base].[ext], the generated filenames are
332         *     [base]-[sequence].[ext].
333         */
334         int sequence = 1;
335         for (int magnitude = 1; magnitude < 1000000000; magnitude *= 10) {
336             for (int iteration = 0; iteration < 9; ++iteration) {
337                 fullFilename = filename + sequence + extension;
338                 if (!new File(fullFilename).exists()) {
339                     return fullFilename;
340                 }
341                 if (Constants.LOGVV) {
342                     Log.v(Constants.TAG, "file with sequence number " + sequence + " exists");
343                 }
344                 sequence += sRandom.nextInt(magnitude) + 1;
345             }
346         }
347         throw new StopRequestException(Downloads.Impl.STATUS_FILE_ERROR,
348                 "failed to generate an unused filename on internal download storage");
349     }
350
351     /**
352      * Checks whether the filename looks legitimate for security purposes. This
353      * prevents us from opening files that aren't actually downloads.
354      */
355     static boolean isFilenameValid(Context context, File file) {
356         final File[] whitelist;
357         try {
358             whitelist = new File[] {
359                     context.getFilesDir().getCanonicalFile(),
360                     context.getCacheDir().getCanonicalFile(),
361                     Environment.getDownloadCacheDirectory().getCanonicalFile(),
362                     Environment.getExternalStorageDirectory().getCanonicalFile(),
363             };
364         } catch (IOException e) {
365             Log.w(TAG, "Failed to resolve canonical path: " + e);
366             return false;
367         }
368
369         for (File testDir : whitelist) {
370             if (contains(testDir, file)) {
371                 return true;
372             }
373         }
374
375         return false;
376     }
377
378     /**
379      * Test if a file lives under the given directory, either as a direct child
380      * or a distant grandchild.
381      * <p>
382      * Both files <em>must</em> have been resolved using
383      * {@link File#getCanonicalFile()} to avoid symlink or path traversal
384      * attacks.
385      */
386     public static boolean contains(File[] dirs, File file) {
387         for (File dir : dirs) {
388             if (contains(dir, file)) {
389                 return true;
390             }
391         }
392         return false;
393     }
394
395     /**
396      * Test if a file lives under the given directory, either as a direct child
397      * or a distant grandchild.
398      * <p>
399      * Both files <em>must</em> have been resolved using
400      * {@link File#getCanonicalFile()} to avoid symlink or path traversal
401      * attacks.
402      */
403     public static boolean contains(File dir, File file) {
404         if (dir == null || file == null) return false;
405
406         String dirPath = dir.getAbsolutePath();
407         String filePath = file.getAbsolutePath();
408
409         if (dirPath.equals(filePath)) {
410             return true;
411         }
412
413         if (!dirPath.endsWith("/")) {
414             dirPath += "/";
415         }
416         return filePath.startsWith(dirPath);
417     }
418
419     /**
420      * Checks whether this looks like a legitimate selection parameter
421      */
422     public static void validateSelection(String selection, Set<String> allowedColumns) {
423         try {
424             if (selection == null || selection.isEmpty()) {
425                 return;
426             }
427             Lexer lexer = new Lexer(selection, allowedColumns);
428             parseExpression(lexer);
429             if (lexer.currentToken() != Lexer.TOKEN_END) {
430                 throw new IllegalArgumentException("syntax error");
431             }
432         } catch (RuntimeException ex) {
433             if (Constants.LOGV) {
434                 Log.d(Constants.TAG, "invalid selection [" + selection + "] triggered " + ex);
435             } else if (false) {
436                 Log.d(Constants.TAG, "invalid selection triggered " + ex);
437             }
438             throw ex;
439         }
440
441     }
442
443     // expression <- ( expression ) | statement [AND_OR ( expression ) | statement] *
444     //             | statement [AND_OR expression]*
445     private static void parseExpression(Lexer lexer) {
446         for (;;) {
447             // ( expression )
448             if (lexer.currentToken() == Lexer.TOKEN_OPEN_PAREN) {
449                 lexer.advance();
450                 parseExpression(lexer);
451                 if (lexer.currentToken() != Lexer.TOKEN_CLOSE_PAREN) {
452                     throw new IllegalArgumentException("syntax error, unmatched parenthese");
453                 }
454                 lexer.advance();
455             } else {
456                 // statement
457                 parseStatement(lexer);
458             }
459             if (lexer.currentToken() != Lexer.TOKEN_AND_OR) {
460                 break;
461             }
462             lexer.advance();
463         }
464     }
465
466     // statement <- COLUMN COMPARE VALUE
467     //            | COLUMN IS NULL
468     private static void parseStatement(Lexer lexer) {
469         // both possibilities start with COLUMN
470         if (lexer.currentToken() != Lexer.TOKEN_COLUMN) {
471             throw new IllegalArgumentException("syntax error, expected column name");
472         }
473         lexer.advance();
474
475         // statement <- COLUMN COMPARE VALUE
476         if (lexer.currentToken() == Lexer.TOKEN_COMPARE) {
477             lexer.advance();
478             if (lexer.currentToken() != Lexer.TOKEN_VALUE) {
479                 throw new IllegalArgumentException("syntax error, expected quoted string");
480             }
481             lexer.advance();
482             return;
483         }
484
485         // statement <- COLUMN IS NULL
486         if (lexer.currentToken() == Lexer.TOKEN_IS) {
487             lexer.advance();
488             if (lexer.currentToken() != Lexer.TOKEN_NULL) {
489                 throw new IllegalArgumentException("syntax error, expected NULL");
490             }
491             lexer.advance();
492             return;
493         }
494
495         // didn't get anything good after COLUMN
496         throw new IllegalArgumentException("syntax error after column name");
497     }
498
499     /**
500      * A simple lexer that recognizes the words of our restricted subset of SQL where clauses
501      */
502     private static class Lexer {
503         public static final int TOKEN_START = 0;
504         public static final int TOKEN_OPEN_PAREN = 1;
505         public static final int TOKEN_CLOSE_PAREN = 2;
506         public static final int TOKEN_AND_OR = 3;
507         public static final int TOKEN_COLUMN = 4;
508         public static final int TOKEN_COMPARE = 5;
509         public static final int TOKEN_VALUE = 6;
510         public static final int TOKEN_IS = 7;
511         public static final int TOKEN_NULL = 8;
512         public static final int TOKEN_END = 9;
513
514         private final String mSelection;
515         private final Set<String> mAllowedColumns;
516         private int mOffset = 0;
517         private int mCurrentToken = TOKEN_START;
518         private final char[] mChars;
519
520         public Lexer(String selection, Set<String> allowedColumns) {
521             mSelection = selection;
522             mAllowedColumns = allowedColumns;
523             mChars = new char[mSelection.length()];
524             mSelection.getChars(0, mChars.length, mChars, 0);
525             advance();
526         }
527
528         public int currentToken() {
529             return mCurrentToken;
530         }
531
532         public void advance() {
533             char[] chars = mChars;
534
535             // consume whitespace
536             while (mOffset < chars.length && chars[mOffset] == ' ') {
537                 ++mOffset;
538             }
539
540             // end of input
541             if (mOffset == chars.length) {
542                 mCurrentToken = TOKEN_END;
543                 return;
544             }
545
546             // "("
547             if (chars[mOffset] == '(') {
548                 ++mOffset;
549                 mCurrentToken = TOKEN_OPEN_PAREN;
550                 return;
551             }
552
553             // ")"
554             if (chars[mOffset] == ')') {
555                 ++mOffset;
556                 mCurrentToken = TOKEN_CLOSE_PAREN;
557                 return;
558             }
559
560             // "?"
561             if (chars[mOffset] == '?') {
562                 ++mOffset;
563                 mCurrentToken = TOKEN_VALUE;
564                 return;
565             }
566
567             // "=" and "=="
568             if (chars[mOffset] == '=') {
569                 ++mOffset;
570                 mCurrentToken = TOKEN_COMPARE;
571                 if (mOffset < chars.length && chars[mOffset] == '=') {
572                     ++mOffset;
573                 }
574                 return;
575             }
576
577             // ">" and ">="
578             if (chars[mOffset] == '>') {
579                 ++mOffset;
580                 mCurrentToken = TOKEN_COMPARE;
581                 if (mOffset < chars.length && chars[mOffset] == '=') {
582                     ++mOffset;
583                 }
584                 return;
585             }
586
587             // "<", "<=" and "<>"
588             if (chars[mOffset] == '<') {
589                 ++mOffset;
590                 mCurrentToken = TOKEN_COMPARE;
591                 if (mOffset < chars.length && (chars[mOffset] == '=' || chars[mOffset] == '>')) {
592                     ++mOffset;
593                 }
594                 return;
595             }
596
597             // "!="
598             if (chars[mOffset] == '!') {
599                 ++mOffset;
600                 mCurrentToken = TOKEN_COMPARE;
601                 if (mOffset < chars.length && chars[mOffset] == '=') {
602                     ++mOffset;
603                     return;
604                 }
605                 throw new IllegalArgumentException("Unexpected character after !");
606             }
607
608             // columns and keywords
609             // first look for anything that looks like an identifier or a keyword
610             //     and then recognize the individual words.
611             // no attempt is made at discarding sequences of underscores with no alphanumeric
612             //     characters, even though it's not clear that they'd be legal column names.
613             if (isIdentifierStart(chars[mOffset])) {
614                 int startOffset = mOffset;
615                 ++mOffset;
616                 while (mOffset < chars.length && isIdentifierChar(chars[mOffset])) {
617                     ++mOffset;
618                 }
619                 String word = mSelection.substring(startOffset, mOffset);
620                 if (mOffset - startOffset <= 4) {
621                     if (word.equals("IS")) {
622                         mCurrentToken = TOKEN_IS;
623                         return;
624                     }
625                     if (word.equals("OR") || word.equals("AND")) {
626                         mCurrentToken = TOKEN_AND_OR;
627                         return;
628                     }
629                     if (word.equals("NULL")) {
630                         mCurrentToken = TOKEN_NULL;
631                         return;
632                     }
633                 }
634                 if (mAllowedColumns.contains(word)) {
635                     mCurrentToken = TOKEN_COLUMN;
636                     return;
637                 }
638                 throw new IllegalArgumentException("unrecognized column or keyword");
639             }
640
641             // quoted strings
642             if (chars[mOffset] == '\'') {
643                 ++mOffset;
644                 while (mOffset < chars.length) {
645                     if (chars[mOffset] == '\'') {
646                         if (mOffset + 1 < chars.length && chars[mOffset + 1] == '\'') {
647                             ++mOffset;
648                         } else {
649                             break;
650                         }
651                     }
652                     ++mOffset;
653                 }
654                 if (mOffset == chars.length) {
655                     throw new IllegalArgumentException("unterminated string");
656                 }
657                 ++mOffset;
658                 mCurrentToken = TOKEN_VALUE;
659                 return;
660             }
661
662             // anything we don't recognize
663             throw new IllegalArgumentException("illegal character: " + chars[mOffset]);
664         }
665
666         private static final boolean isIdentifierStart(char c) {
667             return c == '_' ||
668                     (c >= 'A' && c <= 'Z') ||
669                     (c >= 'a' && c <= 'z');
670         }
671
672         private static final boolean isIdentifierChar(char c) {
673             return c == '_' ||
674                     (c >= 'A' && c <= 'Z') ||
675                     (c >= 'a' && c <= 'z') ||
676                     (c >= '0' && c <= '9');
677         }
678     }
679
680     /**
681      * Replace invalid filename characters according to
682      * specifications of the VFAT.
683      * @note Package-private due to testing.
684      */
685     private static String replaceInvalidVfatCharacters(String filename) {
686         final char START_CTRLCODE = 0x00;
687         final char END_CTRLCODE = 0x1f;
688         final char QUOTEDBL = 0x22;
689         final char ASTERISK = 0x2A;
690         final char SLASH = 0x2F;
691         final char COLON = 0x3A;
692         final char LESS = 0x3C;
693         final char GREATER = 0x3E;
694         final char QUESTION = 0x3F;
695         final char BACKSLASH = 0x5C;
696         final char BAR = 0x7C;
697         final char DEL = 0x7F;
698         final char UNDERSCORE = 0x5F;
699
700         StringBuffer sb = new StringBuffer();
701         char ch;
702         boolean isRepetition = false;
703         for (int i = 0; i < filename.length(); i++) {
704             ch = filename.charAt(i);
705             if ((START_CTRLCODE <= ch &&
706                 ch <= END_CTRLCODE) ||
707                 ch == QUOTEDBL ||
708                 ch == ASTERISK ||
709                 ch == SLASH ||
710                 ch == COLON ||
711                 ch == LESS ||
712                 ch == GREATER ||
713                 ch == QUESTION ||
714                 ch == BACKSLASH ||
715                 ch == BAR ||
716                 ch == DEL){
717                 if (!isRepetition) {
718                     sb.append(UNDERSCORE);
719                     isRepetition = true;
720                 }
721             } else {
722                 sb.append(ch);
723                 isRepetition = false;
724             }
725         }
726         return sb.toString();
727     }
728 }