js repl: in/out markers done
[idea/community.git] / platform / util / src / com / intellij / openapi / util / text / StringUtil.java
1 /*
2  * Copyright 2000-2013 JetBrains s.r.o.
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 package com.intellij.openapi.util.text;
17
18 import com.intellij.CommonBundle;
19 import com.intellij.openapi.diagnostic.Logger;
20 import com.intellij.openapi.progress.ProcessCanceledException;
21 import com.intellij.openapi.util.Pair;
22 import com.intellij.openapi.util.TextRange;
23 import com.intellij.util.*;
24 import com.intellij.util.containers.ContainerUtil;
25 import com.intellij.util.text.CharArrayCharSequence;
26 import com.intellij.util.text.CharArrayUtil;
27 import com.intellij.util.text.StringFactory;
28 import org.jetbrains.annotations.Contract;
29 import org.jetbrains.annotations.NonNls;
30 import org.jetbrains.annotations.NotNull;
31 import org.jetbrains.annotations.Nullable;
32
33 import java.beans.Introspector;
34 import java.io.IOException;
35 import java.util.*;
36 import java.util.regex.Matcher;
37 import java.util.regex.Pattern;
38
39 //TeamCity inherits StringUtil: do not add private constructors!!!
40 @SuppressWarnings({"UtilityClassWithoutPrivateConstructor", "MethodOverridesStaticMethodOfSuperclass"})
41 public class StringUtil extends StringUtilRt {
42   private static final Logger LOG = Logger.getInstance("#com.intellij.openapi.util.text.StringUtil");
43
44   @NonNls private static final String VOWELS = "aeiouy";
45   @NonNls private static final Pattern EOL_SPLIT_KEEP_SEPARATORS = Pattern.compile("(?<=(\r\n|\n))|(?<=\r)(?=[^\n])");
46   @NonNls private static final Pattern EOL_SPLIT_PATTERN = Pattern.compile(" *(\r|\n|\r\n)+ *");
47   @NonNls private static final Pattern EOL_SPLIT_PATTERN_WITH_EMPTY = Pattern.compile(" *(\r|\n|\r\n) *");
48   @NonNls private static final Pattern EOL_SPLIT_DONT_TRIM_PATTERN = Pattern.compile("(\r|\n|\r\n)+");
49
50   public static final NotNullFunction<String, String> QUOTER = new NotNullFunction<String, String>() {
51     @Override
52     @NotNull
53     public String fun(String s) {
54       return "\"" + s + "\"";
55     }
56   };
57
58   public static final NotNullFunction<String, String> SINGLE_QUOTER = new NotNullFunction<String, String>() {
59     @Override
60     @NotNull
61     public String fun(String s) {
62       return "'" + s + "'";
63     }
64   };
65
66   @NotNull
67   public static List<String> getWordsInStringLongestFirst(@NotNull String find) {
68     List<String> words = getWordsIn(find);
69     // hope long words are rare
70     Collections.sort(words, new Comparator<String>() {
71       @Override
72       public int compare(@NotNull final String o1, @NotNull final String o2) {
73         return o2.length() - o1.length();
74       }
75     });
76     return words;
77   }
78
79   @NotNull
80   public static String escapePattern(@NotNull final String text) {
81     return replace(replace(text, "'", "''"), "{", "'{'");
82   }
83
84   @NotNull
85   public static <T> Function<T, String> createToStringFunction(@NotNull Class<T> cls) {
86     return new Function<T, String>() {
87       @Override
88       public String fun(@NotNull T o) {
89         return o.toString();
90       }
91     };
92   }
93
94   @NotNull
95   public static Function<String, String> TRIMMER = new Function<String, String>() {
96     @Nullable
97     @Override
98     public String fun(@Nullable String s) {
99       return s == null ? null : s.trim();
100     }
101   };
102
103   @NotNull
104   public static String replace(@NonNls @NotNull String text, @NonNls @NotNull String oldS, @NonNls @Nullable String newS) {
105     return replace(text, oldS, newS, false);
106   }
107
108   @NotNull
109   public static String replaceIgnoreCase(@NotNull String text, @NotNull String oldS, @Nullable String newS) {
110     return replace(text, oldS, newS, true);
111   }
112
113   public static void replaceChar(@NotNull char[] buffer, char oldChar, char newChar, int start, int end) {
114     for (int i = start; i < end; i++) {
115       char c = buffer[i];
116       if (c == oldChar) {
117         buffer[i] = newChar;
118       }
119     }
120   }
121
122   @NotNull
123   public static String replaceChar(@NotNull String buffer, char oldChar, char newChar) {
124     StringBuilder newBuffer = null;
125     for (int i = 0; i < buffer.length(); i++) {
126       char c = buffer.charAt(i);
127       if (c == oldChar) {
128         if (newBuffer == null) {
129           newBuffer = new StringBuilder(buffer.length());
130           newBuffer.append(buffer, 0, i);
131         }
132
133         newBuffer.append(newChar);
134       }
135       else if (newBuffer != null) {
136         newBuffer.append(c);
137       }
138     }
139     return newBuffer == null ? buffer : newBuffer.toString();
140   }
141
142   public static String replace(@NotNull final String text, @NotNull final String oldS, @Nullable final String newS, boolean ignoreCase) {
143     if (text.length() < oldS.length()) return text;
144
145     final String text1 = ignoreCase ? text.toLowerCase() : text;
146     final String oldS1 = ignoreCase ? oldS.toLowerCase() : oldS;
147     StringBuilder newText = null;
148     int i = 0;
149
150     while (i < text1.length()) {
151       int i1 = text1.indexOf(oldS1, i);
152       if (i1 < 0) {
153         if (i == 0) return text;
154         newText.append(text, i, text.length());
155         break;
156       }
157       else {
158         if (newS == null) return null;
159         if (newText == null) newText = new StringBuilder(text.length() - i);
160         newText.append(text, i, i1);
161         newText.append(newS);
162         i = i1 + oldS.length();
163       }
164     }
165     return newText != null ? newText.toString() : "";
166   }
167
168   /**
169    * Implementation copied from {@link String#indexOf(String, int)} except character comparisons made case insensitive
170    */
171   public static int indexOfIgnoreCase(@NotNull String where, @NotNull String what, int fromIndex) {
172     int targetCount = what.length();
173     int sourceCount = where.length();
174
175     if (fromIndex >= sourceCount) {
176       return targetCount == 0 ? sourceCount : -1;
177     }
178
179     if (fromIndex < 0) {
180       fromIndex = 0;
181     }
182
183     if (targetCount == 0) {
184       return fromIndex;
185     }
186
187     char first = what.charAt(0);
188     int max = sourceCount - targetCount;
189
190     for (int i = fromIndex; i <= max; i++) {
191       /* Look for first character. */
192       if (!charsEqualIgnoreCase(where.charAt(i), first)) {
193         while (++i <= max && !charsEqualIgnoreCase(where.charAt(i), first)) ;
194       }
195
196       /* Found first character, now look at the rest of v2 */
197       if (i <= max) {
198         int j = i + 1;
199         int end = j + targetCount - 1;
200         for (int k = 1; j < end && charsEqualIgnoreCase(where.charAt(j), what.charAt(k)); j++, k++) ;
201
202         if (j == end) {
203           /* Found whole string. */
204           return i;
205         }
206       }
207     }
208
209     return -1;
210   }
211
212   public static int indexOfIgnoreCase(@NotNull String where, char what, int fromIndex) {
213     int sourceCount = where.length();
214
215     if (fromIndex >= sourceCount) {
216       return -1;
217     }
218
219     if (fromIndex < 0) {
220       fromIndex = 0;
221     }
222
223     for (int i = fromIndex; i < sourceCount; i++) {
224       if (charsEqualIgnoreCase(where.charAt(i), what)) {
225         return i;
226       }
227     }
228
229     return -1;
230   }
231
232   public static boolean containsIgnoreCase(@NotNull String where, @NotNull String what) {
233     return indexOfIgnoreCase(where, what, 0) >= 0;
234   }
235
236   public static boolean endsWithIgnoreCase(@NonNls @NotNull String str, @NonNls @NotNull String suffix) {
237     final int stringLength = str.length();
238     final int suffixLength = suffix.length();
239     return stringLength >= suffixLength && str.regionMatches(true, stringLength - suffixLength, suffix, 0, suffixLength);
240   }
241
242   public static boolean startsWithIgnoreCase(@NonNls @NotNull String str, @NonNls @NotNull String prefix) {
243     return StringUtilRt.startsWithIgnoreCase(str, prefix);
244   }
245
246   public static String stripHtml(@NotNull String html, boolean convertBreaks) {
247     if (convertBreaks) {
248       html = html.replaceAll("<br/?>", "\n\n");
249     }
250
251     return html.replaceAll("<(.|\n)*?>", "");
252   }
253
254   public static String toLowerCase(@Nullable final String str) {
255     //noinspection ConstantConditions
256     return str == null ? null : str.toLowerCase();
257   }
258
259   @NotNull
260   public static String getPackageName(@NotNull String fqName) {
261     return getPackageName(fqName, '.');
262   }
263
264   @NotNull
265   public static String getPackageName(@NotNull String fqName, char separator) {
266     int lastPointIdx = fqName.lastIndexOf(separator);
267     if (lastPointIdx >= 0) {
268       return fqName.substring(0, lastPointIdx);
269     }
270     return "";
271   }
272
273   public static int getLineBreakCount(@NotNull CharSequence text) {
274     int count = 0;
275     for (int i = 0; i < text.length(); i++) {
276       char c = text.charAt(i);
277       if (c == '\n') {
278         count++;
279       }
280       else if (c == '\r') {
281         if (i + 1 < text.length() && text.charAt(i + 1) == '\n') {
282           //noinspection AssignmentToForLoopParameter
283           i++;
284           count++;
285         }
286         else {
287           count++;
288         }
289       }
290     }
291     return count;
292   }
293
294   public static boolean containsLineBreak(@NotNull CharSequence text) {
295     for (int i = 0; i < text.length(); i++) {
296       char c = text.charAt(i);
297       if (isLineBreak(c)) return true;
298     }
299     return false;
300   }
301
302   public static boolean isLineBreak(char c) {
303     return c == '\n' || c == '\r';
304   }
305
306   @NotNull
307   public static String escapeLineBreak(@NotNull String text) {
308     StringBuilder buffer = new StringBuilder(text.length());
309     for (int i = 0; i < text.length(); i++) {
310       char c = text.charAt(i);
311       switch (c) {
312         case '\n':
313           buffer.append("\\n");
314           break;
315         case '\r':
316           buffer.append("\\r");
317           break;
318         default:
319           buffer.append(c);
320       }
321     }
322     return buffer.toString();
323   }
324
325   public static boolean endsWithLineBreak(@NotNull CharSequence text) {
326     int len = text.length();
327     return len > 0 && isLineBreak(text.charAt(len - 1));
328   }
329
330   public static int lineColToOffset(@NotNull CharSequence text, int line, int col) {
331     int curLine = 0;
332     int offset = 0;
333     while (line != curLine) {
334       if (offset == text.length()) return -1;
335       char c = text.charAt(offset);
336       if (c == '\n') {
337         curLine++;
338       }
339       else if (c == '\r') {
340         curLine++;
341         if (offset < text.length() - 1 && text.charAt(offset + 1) == '\n') {
342           offset++;
343         }
344       }
345       offset++;
346     }
347     return offset + col;
348   }
349
350   public static int offsetToLineNumber(@NotNull CharSequence text, int offset) {
351     int curLine = 0;
352     int curOffset = 0;
353     while (curOffset < offset) {
354       if (curOffset == text.length()) return -1;
355       char c = text.charAt(curOffset);
356       if (c == '\n') {
357         curLine++;
358       }
359       else if (c == '\r') {
360         curLine++;
361         if (curOffset < text.length() - 1 && text.charAt(curOffset + 1) == '\n') {
362           curOffset++;
363         }
364       }
365       curOffset++;
366     }
367     return curLine;
368   }
369
370   /**
371    * Classic dynamic programming algorithm for string differences.
372    */
373   public static int difference(@NotNull String s1, @NotNull String s2) {
374     int[][] a = new int[s1.length()][s2.length()];
375
376     for (int i = 0; i < s1.length(); i++) {
377       a[i][0] = i;
378     }
379
380     for (int j = 0; j < s2.length(); j++) {
381       a[0][j] = j;
382     }
383
384     for (int i = 1; i < s1.length(); i++) {
385       for (int j = 1; j < s2.length(); j++) {
386
387         a[i][j] = Math.min(Math.min(a[i - 1][j - 1] + (s1.charAt(i) == s2.charAt(j) ? 0 : 1), a[i - 1][j] + 1), a[i][j - 1] + 1);
388       }
389     }
390
391     return a[s1.length() - 1][s2.length() - 1];
392   }
393
394   @NotNull
395   public static String wordsToBeginFromUpperCase(@NotNull String s) {
396     return toTitleCase(s, ourPrepositions);
397   }
398
399   @NotNull
400   public static String toTitleCase(@NotNull String s) {
401     return toTitleCase(s, ArrayUtil.EMPTY_STRING_ARRAY);
402   }
403
404   @NotNull
405   private static String toTitleCase(@NotNull String s, @NotNull String[] prepositions) {
406     StringBuilder buffer = null;
407     for (int i = 0; i < s.length(); i++) {
408       char prevChar = i == 0 ? ' ' : s.charAt(i - 1);
409       char currChar = s.charAt(i);
410       if (!Character.isLetterOrDigit(prevChar) && prevChar != '\'') {
411         if (Character.isLetterOrDigit(currChar)) {
412           if (!Character.isUpperCase(currChar)) {
413             int j = i;
414             for (; j < s.length(); j++) {
415               if (!Character.isLetterOrDigit(s.charAt(j))) {
416                 break;
417               }
418             }
419             if (!isPreposition(s, i, j - 1, prepositions)) {
420               if (buffer == null) {
421                 buffer = new StringBuilder(s);
422               }
423               buffer.setCharAt(i, toUpperCase(currChar));
424             }
425           }
426         }
427       }
428     }
429     if (buffer == null) {
430       return s;
431     }
432     else {
433       return buffer.toString();
434     }
435   }
436
437   @NonNls private static final String[] ourPrepositions = {
438     "a", "an", "and", "as", "at", "but", "by", "down", "for", "from", "if", "in", "into", "not", "of", "on", "onto", "or", "out", "over",
439     "per", "nor", "the", "to", "up", "upon", "via", "with"
440   };
441
442   public static boolean isPreposition(@NotNull String s, int firstChar, int lastChar) {
443     return isPreposition(s, firstChar, lastChar, ourPrepositions);
444   }
445
446   public static boolean isPreposition(@NotNull String s, int firstChar, int lastChar, @NotNull String[] prepositions) {
447     for (String preposition : prepositions) {
448       boolean found = false;
449       if (lastChar - firstChar + 1 == preposition.length()) {
450         found = true;
451         for (int j = 0; j < preposition.length(); j++) {
452           if (!(toLowerCase(s.charAt(firstChar + j)) == preposition.charAt(j))) {
453             found = false;
454           }
455         }
456       }
457       if (found) {
458         return true;
459       }
460     }
461     return false;
462   }
463
464   @NotNull
465   public static NotNullFunction<String, String> escaper(final boolean escapeSlash, @Nullable final String additionalChars) {
466     return new NotNullFunction<String, String>() {
467       @NotNull
468       @Override
469       public String fun(@NotNull String dom) {
470         final StringBuilder builder = new StringBuilder(dom.length());
471         escapeStringCharacters(dom.length(), dom, additionalChars, escapeSlash, builder);
472         return builder.toString();
473       }
474     };
475   }
476
477
478   public static void escapeStringCharacters(int length, @NotNull String str, @NotNull @NonNls StringBuilder buffer) {
479     escapeStringCharacters(length, str, "\"", buffer);
480   }
481
482   @NotNull
483   public static StringBuilder escapeStringCharacters(int length,
484                                                      @NotNull String str,
485                                                      @Nullable String additionalChars,
486                                                      @NotNull @NonNls StringBuilder buffer) {
487     return escapeStringCharacters(length, str, additionalChars, true, buffer);
488   }
489
490   @NotNull
491   public static StringBuilder escapeStringCharacters(int length,
492                                                      @NotNull String str,
493                                                      @Nullable String additionalChars,
494                                                      boolean escapeSlash,
495                                                      @NotNull @NonNls StringBuilder buffer) {
496     char prev = 0;
497     for (int idx = 0; idx < length; idx++) {
498       char ch = str.charAt(idx);
499       switch (ch) {
500         case '\b':
501           buffer.append("\\b");
502           break;
503
504         case '\t':
505           buffer.append("\\t");
506           break;
507
508         case '\n':
509           buffer.append("\\n");
510           break;
511
512         case '\f':
513           buffer.append("\\f");
514           break;
515
516         case '\r':
517           buffer.append("\\r");
518           break;
519
520         default:
521           if (escapeSlash && ch == '\\') {
522             buffer.append("\\\\");
523           }
524           else if (additionalChars != null && additionalChars.indexOf(ch) > -1 && (escapeSlash || prev != '\\')) {
525             buffer.append("\\").append(ch);
526           }
527           else if (Character.isISOControl(ch)) {
528             String hexCode = StringUtilRt.toUpperCase(Integer.toHexString(ch));
529             buffer.append("\\u");
530             int paddingCount = 4 - hexCode.length();
531             while (paddingCount-- > 0) {
532               buffer.append(0);
533             }
534             buffer.append(hexCode);
535           }
536           else {
537             buffer.append(ch);
538           }
539       }
540       prev = ch;
541     }
542     return buffer;
543   }
544
545   @NotNull
546   public static String escapeStringCharacters(@NotNull String s) {
547     StringBuilder buffer = new StringBuilder(s.length());
548     escapeStringCharacters(s.length(), s, "\"", buffer);
549     return buffer.toString();
550   }
551
552   @NotNull
553   public static String escapeCharCharacters(@NotNull String s) {
554     StringBuilder buffer = new StringBuilder(s.length());
555     escapeStringCharacters(s.length(), s, "\'", buffer);
556     return buffer.toString();
557   }
558
559   @NotNull
560   public static String unescapeStringCharacters(@NotNull String s) {
561     StringBuilder buffer = new StringBuilder(s.length());
562     unescapeStringCharacters(s.length(), s, buffer);
563     return buffer.toString();
564   }
565
566   @NotNull
567   public static String unquoteString(@NotNull String s) {
568     char c;
569     if (s.length() <= 1 || (c = s.charAt(0)) != '"' && c != '\'' || s.charAt(s.length() - 1) != c) {
570       return s;
571     }
572     return s.substring(1, s.length() - 1);
573   }
574
575   @NotNull
576   public static String unquoteString(@NotNull String s, char quotationChar) {
577     char c;
578     if (s.length() <= 1 || (c = s.charAt(0)) != quotationChar || s.charAt(s.length() - 1) != c) {
579       return s;
580     }
581     return s.substring(1, s.length() - 1);
582   }
583
584   /**
585    * This is just an optimized version of Matcher.quoteReplacement
586    */
587   @NotNull
588   public static String quoteReplacement(@NotNull String s) {
589     boolean needReplacements = false;
590
591     for (int i = 0; i < s.length(); i++) {
592       char c = s.charAt(i);
593       if (c == '\\' || c == '$') {
594         needReplacements = true;
595         break;
596       }
597     }
598
599     if (!needReplacements) return s;
600
601     StringBuilder sb = new StringBuilder(s.length() * 6 / 5);
602     for (int i = 0; i < s.length(); i++) {
603       char c = s.charAt(i);
604       if (c == '\\') {
605         sb.append('\\');
606         sb.append('\\');
607       }
608       else if (c == '$') {
609         sb.append('\\');
610         sb.append('$');
611       }
612       else {
613         sb.append(c);
614       }
615     }
616     return sb.toString();
617   }
618
619   private static void unescapeStringCharacters(int length, @NotNull String s, @NotNull StringBuilder buffer) {
620     boolean escaped = false;
621     for (int idx = 0; idx < length; idx++) {
622       char ch = s.charAt(idx);
623       if (!escaped) {
624         if (ch == '\\') {
625           escaped = true;
626         }
627         else {
628           buffer.append(ch);
629         }
630       }
631       else {
632         switch (ch) {
633           case 'n':
634             buffer.append('\n');
635             break;
636
637           case 'r':
638             buffer.append('\r');
639             break;
640
641           case 'b':
642             buffer.append('\b');
643             break;
644
645           case 't':
646             buffer.append('\t');
647             break;
648
649           case 'f':
650             buffer.append('\f');
651             break;
652
653           case '\'':
654             buffer.append('\'');
655             break;
656
657           case '\"':
658             buffer.append('\"');
659             break;
660
661           case '\\':
662             buffer.append('\\');
663             break;
664
665           case 'u':
666             if (idx + 4 < length) {
667               try {
668                 int code = Integer.parseInt(s.substring(idx + 1, idx + 5), 16);
669                 idx += 4;
670                 buffer.append((char)code);
671               }
672               catch (NumberFormatException e) {
673                 buffer.append("\\u");
674               }
675             }
676             else {
677               buffer.append("\\u");
678             }
679             break;
680
681           default:
682             buffer.append(ch);
683             break;
684         }
685         escaped = false;
686       }
687     }
688
689     if (escaped) buffer.append('\\');
690   }
691
692   @SuppressWarnings({"HardCodedStringLiteral"})
693   @NotNull
694   public static String pluralize(@NotNull String suggestion) {
695     if (suggestion.endsWith("Child") || suggestion.endsWith("child")) {
696       return suggestion + "ren";
697     }
698
699     if (suggestion.equals("this")) {
700       return "these";
701     }
702     if (suggestion.equals("This")) {
703       return "These";
704     }
705
706     if (endsWithIgnoreCase(suggestion, "s") || endsWithIgnoreCase(suggestion, "x") || endsWithIgnoreCase(suggestion, "ch")) {
707       return suggestion + "es";
708     }
709
710     int len = suggestion.length();
711     if (endsWithIgnoreCase(suggestion, "y") && len > 1 && !isVowel(toLowerCase(suggestion.charAt(len - 2)))) {
712       return suggestion.substring(0, len - 1) + "ies";
713     }
714
715     return suggestion + "s";
716   }
717
718   @NotNull
719   public static String capitalizeWords(@NotNull String text,
720                                        boolean allWords) {
721     return capitalizeWords(text, " \t\n\r\f", allWords, false);
722   }
723
724   @NotNull
725   public static String capitalizeWords(@NotNull String text,
726                                        @NotNull String tokenizerDelim,
727                                        boolean allWords,
728                                        boolean leaveOriginalDelims) {
729     final StringTokenizer tokenizer = new StringTokenizer(text, tokenizerDelim, leaveOriginalDelims);
730     final StringBuilder out = new StringBuilder(text.length());
731     boolean toCapitalize = true;
732     while (tokenizer.hasMoreTokens()) {
733       final String word = tokenizer.nextToken();
734       if (!leaveOriginalDelims && out.length() > 0) {
735         out.append(' ');
736       }
737       out.append(toCapitalize ? capitalize(word) : word);
738       if (!allWords) {
739         toCapitalize = false;
740       }
741     }
742     return out.toString();
743   }
744
745   public static String decapitalize(String s) {
746     return Introspector.decapitalize(s);
747   }
748
749   public static boolean isVowel(char c) {
750     return VOWELS.indexOf(c) >= 0;
751   }
752
753   @NotNull
754   public static String capitalize(@NotNull String s) {
755     if (s.isEmpty()) return s;
756     if (s.length() == 1) return StringUtilRt.toUpperCase(s);
757
758     // Optimization
759     if (Character.isUpperCase(s.charAt(0))) return s;
760     return toUpperCase(s.charAt(0)) + s.substring(1);
761   }
762
763   @Contract("null -> false")
764   public static boolean isCapitalized(@Nullable String s) {
765     return s != null && !s.isEmpty() && Character.isUpperCase(s.charAt(0));
766   }
767
768   @NotNull
769   public static String capitalizeWithJavaBeanConvention(@NotNull String s) {
770     if (s.length() > 1 && Character.isUpperCase(s.charAt(1))) {
771       return s;
772     }
773     return capitalize(s);
774   }
775
776   public static int stringHashCode(@NotNull CharSequence chars) {
777     if (chars instanceof String) return chars.hashCode();
778     if (chars instanceof CharSequenceWithStringHash) return chars.hashCode();
779     if (chars instanceof CharArrayCharSequence) return chars.hashCode();
780
781     return stringHashCode(chars, 0, chars.length());
782   }
783
784   public static int stringHashCode(@NotNull CharSequence chars, int from, int to) {
785     int h = 0;
786     for (int off = from; off < to; off++) {
787       h = 31 * h + chars.charAt(off);
788     }
789     return h;
790   }
791
792   public static int stringHashCode(char[] chars, int from, int to) {
793     int h = 0;
794     for (int off = from; off < to; off++) {
795       h = 31 * h + chars[off];
796     }
797     return h;
798   }
799
800   public static int stringHashCodeInsensitive(@NotNull char[] chars, int from, int to) {
801     int h = 0;
802     for (int off = from; off < to; off++) {
803       h = 31 * h + toLowerCase(chars[off]);
804     }
805     return h;
806   }
807
808   public static int stringHashCodeInsensitive(@NotNull CharSequence chars, int from, int to) {
809     int h = 0;
810     for (int off = from; off < to; off++) {
811       h = 31 * h + toLowerCase(chars.charAt(off));
812     }
813     return h;
814   }
815
816   public static int stringHashCodeInsensitive(@NotNull CharSequence chars) {
817     return stringHashCodeInsensitive(chars, 0, chars.length());
818   }
819
820   /**
821    * Equivalent to string.startsWith(prefixes[0] + prefixes[1] + ...) but avoids creating an object for concatenation.
822    */
823   public static boolean startsWithConcatenation(@NotNull String string, @NotNull String... prefixes) {
824     int offset = 0;
825     for (String prefix : prefixes) {
826       int prefixLen = prefix.length();
827       if (!string.regionMatches(offset, prefix, 0, prefixLen)) {
828         return false;
829       }
830       offset += prefixLen;
831     }
832     return true;
833   }
834
835   /**
836    * @deprecated use {@link #startsWithConcatenation(String, String...)} (to remove in IDEA 14).
837    */
838   @SuppressWarnings("UnusedDeclaration")
839   public static boolean startsWithConcatenationOf(@NotNull String string, @NotNull String firstPrefix, @NotNull String secondPrefix) {
840     return startsWithConcatenation(string, firstPrefix, secondPrefix);
841   }
842
843   /**
844    * @deprecated use {@link #startsWithConcatenation(String, String...)} (to remove in IDEA 14).
845    */
846   @SuppressWarnings("UnusedDeclaration")
847   public static boolean startsWithConcatenationOf(@NotNull String string,
848                                                   @NotNull String firstPrefix,
849                                                   @NotNull String secondPrefix,
850                                                   @NotNull String thirdPrefix) {
851     return startsWithConcatenation(string, firstPrefix, secondPrefix, thirdPrefix);
852   }
853
854   @NotNull
855   public static String trimEnd(@NotNull String s, @NonNls @NotNull String suffix) {
856     if (s.endsWith(suffix)) {
857       return s.substring(0, s.length() - suffix.length());
858     }
859     return s;
860   }
861
862   @NotNull
863   public static String trimLog(@NotNull final String text, final int limit) {
864     if (limit > 5 && text.length() > limit) {
865       return text.substring(0, limit - 5) + " ...\n";
866     }
867     return text;
868   }
869
870   @NotNull
871   public static String trimLeading(@NotNull String string) {
872     int index = 0;
873     while (index < string.length() && Character.isWhitespace(string.charAt(index))) index++;
874     return string.substring(index);
875   }
876
877   @NotNull
878   public static String trimLeading(@NotNull String string, char symbol) {
879     int index = 0;
880     while (index < string.length() && string.charAt(index) == symbol) index++;
881     return string.substring(index);
882   }
883
884   @NotNull
885   public static String trimTrailing(@NotNull String string) {
886     int index = string.length() - 1;
887     while (index >= 0 && Character.isWhitespace(string.charAt(index))) index--;
888     return string.substring(0, index + 1);
889   }
890
891   public static boolean startsWithChar(@Nullable CharSequence s, char prefix) {
892     return s != null && s.length() != 0 && s.charAt(0) == prefix;
893   }
894
895   public static boolean endsWithChar(@Nullable CharSequence s, char suffix) {
896     return StringUtilRt.endsWithChar(s, suffix);
897   }
898
899   @NotNull
900   public static String trimStart(@NotNull String s, @NonNls @NotNull String prefix) {
901     if (s.startsWith(prefix)) {
902       return s.substring(prefix.length());
903     }
904     return s;
905   }
906
907   @NotNull
908   public static String pluralize(@NotNull String base, int n) {
909     if (n == 1) return base;
910     return pluralize(base);
911   }
912
913   public static void repeatSymbol(@NotNull Appendable buffer, char symbol, int times) {
914     assert times >= 0 : times;
915     try {
916       for (int i = 0; i < times; i++) {
917         buffer.append(symbol);
918       }
919     }
920     catch (IOException e) {
921       LOG.error(e);
922     }
923   }
924
925   @Contract("null -> false")
926   public static boolean isNotEmpty(@Nullable String s) {
927     return s != null && !s.isEmpty();
928   }
929
930   @Contract("null -> true")
931   public static boolean isEmpty(@Nullable String s) {
932     return s == null || s.isEmpty();
933   }
934
935   @Contract("null -> true")
936   public static boolean isEmpty(@Nullable CharSequence cs) {
937     return cs == null || cs.length() == 0;
938   }
939
940   public static int length(@Nullable CharSequence cs) {
941     return cs == null ? 0 : cs.length();
942   }
943
944   @NotNull
945   public static String notNullize(@Nullable final String s) {
946     return notNullize(s, "");
947   }
948
949   @NotNull
950   public static String notNullize(@Nullable final String s, @NotNull String defaultValue) {
951     return s == null ? defaultValue : s;
952   }
953
954   @Nullable
955   public static String nullize(@Nullable final String s) {
956     return nullize(s, false);
957   }
958
959   @Nullable
960   public static String nullize(@Nullable final String s, boolean nullizeSpaces) {
961     if (nullizeSpaces) {
962       if (isEmptyOrSpaces(s)) return null;
963     }
964     else {
965       if (isEmpty(s)) return null;
966     }
967     return s;
968   }
969
970   @Contract("null -> true")
971   public static boolean isEmptyOrSpaces(@Nullable final String s) {
972     if (s == null || s.isEmpty()) {
973       return true;
974     }
975     for (int i = 0; i < s.length(); i++) {
976       if (s.charAt(i) > ' ') {
977         return false;
978       }
979     }
980     return true;
981   }
982
983   /**
984    * Allows to answer if given symbol is white space, tabulation or line feed.
985    *
986    * @param c symbol to check
987    * @return <code>true</code> if given symbol is white space, tabulation or line feed; <code>false</code> otherwise
988    */
989   public static boolean isWhiteSpace(char c) {
990     return c == '\n' || c == '\t' || c == ' ';
991   }
992
993   @NotNull
994   public static String getThrowableText(@NotNull Throwable aThrowable) {
995     return ExceptionUtil.getThrowableText(aThrowable);
996   }
997
998   @NotNull
999   public static String getThrowableText(@NotNull Throwable aThrowable, @NonNls @NotNull final String stackFrameSkipPattern) {
1000     return ExceptionUtil.getThrowableText(aThrowable, stackFrameSkipPattern);
1001   }
1002
1003   @Nullable
1004   public static String getMessage(@NotNull Throwable e) {
1005     return ExceptionUtil.getMessage(e);
1006   }
1007
1008   @NotNull
1009   public static String repeatSymbol(final char aChar, final int count) {
1010     char[] buffer = new char[count];
1011     Arrays.fill(buffer, aChar);
1012     return StringFactory.createShared(buffer);
1013   }
1014
1015   @NotNull
1016   public static String repeat(@NotNull String s, int count) {
1017     assert count >= 0 : count;
1018     StringBuilder sb = new StringBuilder(s.length() * count);
1019     for (int i = 0; i < count; i++) {
1020       sb.append(s);
1021     }
1022     return sb.toString();
1023   }
1024
1025   @NotNull
1026   public static List<String> splitHonorQuotes(@NotNull String s, char separator) {
1027     final List<String> result = new ArrayList<String>();
1028     final StringBuilder builder = new StringBuilder(s.length());
1029     boolean inQuotes = false;
1030     for (int i = 0; i < s.length(); i++) {
1031       final char c = s.charAt(i);
1032       if (c == separator && !inQuotes) {
1033         if (builder.length() > 0) {
1034           result.add(builder.toString());
1035           builder.setLength(0);
1036         }
1037         continue;
1038       }
1039
1040       if ((c == '"' || c == '\'') && !(i > 0 && s.charAt(i - 1) == '\\')) {
1041         inQuotes = !inQuotes;
1042       }
1043       builder.append(c);
1044     }
1045
1046     if (builder.length() > 0) {
1047       result.add(builder.toString());
1048     }
1049     return result;
1050   }
1051
1052
1053   @NotNull
1054   public static List<String> split(@NotNull String s, @NotNull String separator) {
1055     return split(s, separator, true);
1056   }
1057
1058   @NotNull
1059   public static List<String> split(@NotNull String s, @NotNull String separator,
1060                                    boolean excludeSeparator) {
1061     return split(s, separator, excludeSeparator, true);
1062   }
1063
1064   @NotNull
1065   public static List<String> split(@NotNull String s, @NotNull String separator,
1066                                    boolean excludeSeparator, boolean excludeEmptyStrings) {
1067     if (separator.isEmpty()) {
1068       return Collections.singletonList(s);
1069     }
1070     List<String> result = new ArrayList<String>();
1071     int pos = 0;
1072     while (true) {
1073       int index = s.indexOf(separator, pos);
1074       if (index == -1) break;
1075       final int nextPos = index + separator.length();
1076       String token = s.substring(pos, excludeSeparator ? index : nextPos);
1077       if (!token.isEmpty() || !excludeEmptyStrings) {
1078         result.add(token);
1079       }
1080       pos = nextPos;
1081     }
1082     if (pos < s.length() || !excludeEmptyStrings && pos == s.length()) {
1083       result.add(s.substring(pos, s.length()));
1084     }
1085     return result;
1086   }
1087
1088   @NotNull
1089   public static Iterable<String> tokenize(@NotNull String s, @NotNull String separators) {
1090     final com.intellij.util.text.StringTokenizer tokenizer = new com.intellij.util.text.StringTokenizer(s, separators);
1091     return new Iterable<String>() {
1092       @NotNull
1093       @Override
1094       public Iterator<String> iterator() {
1095         return new Iterator<String>() {
1096           @Override
1097           public boolean hasNext() {
1098             return tokenizer.hasMoreTokens();
1099           }
1100
1101           @Override
1102           public String next() {
1103             return tokenizer.nextToken();
1104           }
1105
1106           @Override
1107           public void remove() {
1108             throw new UnsupportedOperationException();
1109           }
1110         };
1111       }
1112     };
1113   }
1114
1115   @NotNull
1116   public static Iterable<String> tokenize(@NotNull final StringTokenizer tokenizer) {
1117     return new Iterable<String>() {
1118       @NotNull
1119       @Override
1120       public Iterator<String> iterator() {
1121         return new Iterator<String>() {
1122           @Override
1123           public boolean hasNext() {
1124             return tokenizer.hasMoreTokens();
1125           }
1126
1127           @Override
1128           public String next() {
1129             return tokenizer.nextToken();
1130           }
1131
1132           @Override
1133           public void remove() {
1134             throw new UnsupportedOperationException();
1135           }
1136         };
1137       }
1138     };
1139   }
1140
1141   /**
1142    * @return list containing all words in {@code text}, or {@link ContainerUtil#emptyList()} if there are none.
1143    * The <b>word</b> here means the maximum sub-string consisting entirely of characters which are <code>Character.isJavaIdentifierPart(c)</code>.
1144    */
1145   @NotNull
1146   public static List<String> getWordsIn(@NotNull String text) {
1147     List<String> result = null;
1148     int start = -1;
1149     for (int i = 0; i < text.length(); i++) {
1150       char c = text.charAt(i);
1151       boolean isIdentifierPart = Character.isJavaIdentifierPart(c);
1152       if (isIdentifierPart && start == -1) {
1153         start = i;
1154       }
1155       if (isIdentifierPart && i == text.length() - 1 && start != -1) {
1156         if (result == null) {
1157           result = new SmartList<String>();
1158         }
1159         result.add(text.substring(start, i + 1));
1160       }
1161       else if (!isIdentifierPart && start != -1) {
1162         if (result == null) {
1163           result = new SmartList<String>();
1164         }
1165         result.add(text.substring(start, i));
1166         start = -1;
1167       }
1168     }
1169     if (result == null) {
1170       return ContainerUtil.emptyList();
1171     }
1172     return result;
1173   }
1174
1175   @NotNull
1176   public static List<TextRange> getWordIndicesIn(@NotNull String text) {
1177     List<TextRange> result = new SmartList<TextRange>();
1178     int start = -1;
1179     for (int i = 0; i < text.length(); i++) {
1180       char c = text.charAt(i);
1181       boolean isIdentifierPart = Character.isJavaIdentifierPart(c);
1182       if (isIdentifierPart && start == -1) {
1183         start = i;
1184       }
1185       if (isIdentifierPart && i == text.length() - 1 && start != -1) {
1186         result.add(new TextRange(start, i + 1));
1187       }
1188       else if (!isIdentifierPart && start != -1) {
1189         result.add(new TextRange(start, i));
1190         start = -1;
1191       }
1192     }
1193     return result;
1194   }
1195
1196   @NotNull
1197   public static String join(@NotNull final String[] strings, @NotNull final String separator) {
1198     return join(strings, 0, strings.length, separator);
1199   }
1200
1201   @NotNull
1202   public static String join(@NotNull final String[] strings, int startIndex, int endIndex, @NotNull final String separator) {
1203     final StringBuilder result = new StringBuilder();
1204     for (int i = startIndex; i < endIndex; i++) {
1205       if (i > startIndex) result.append(separator);
1206       result.append(strings[i]);
1207     }
1208     return result.toString();
1209   }
1210
1211   @NotNull
1212   public static String[] zip(@NotNull String[] strings1, @NotNull String[] strings2, String separator) {
1213     if (strings1.length != strings2.length) throw new IllegalArgumentException();
1214
1215     String[] result = ArrayUtil.newStringArray(strings1.length);
1216     for (int i = 0; i < result.length; i++) {
1217       result[i] = strings1[i] + separator + strings2[i];
1218     }
1219
1220     return result;
1221   }
1222
1223   @NotNull
1224   public static String[] surround(@NotNull String[] strings1, String prefix, String suffix) {
1225     String[] result = ArrayUtil.newStringArray(strings1.length);
1226     for (int i = 0; i < result.length; i++) {
1227       result[i] = prefix + strings1[i] + suffix;
1228     }
1229
1230     return result;
1231   }
1232
1233   @NotNull
1234   public static <T> String join(@NotNull T[] items, @NotNull Function<T, String> f, @NotNull @NonNls String separator) {
1235     return join(Arrays.asList(items), f, separator);
1236   }
1237
1238   @NotNull
1239   public static <T> String join(@NotNull Collection<? extends T> items,
1240                                 @NotNull Function<? super T, String> f,
1241                                 @NotNull @NonNls String separator) {
1242     if (items.isEmpty()) return "";
1243     return join((Iterable<? extends T>)items, f, separator);
1244   }
1245
1246   public static String join(@NotNull Iterable<?> items, @NotNull @NonNls String separator) {
1247     StringBuilder result = new StringBuilder();
1248     for (Object item : items) {
1249       result.append(item).append(separator);
1250     }
1251     if (result.length() > 0) {
1252       result.setLength(result.length() - separator.length());
1253     }
1254     return result.toString();
1255   }
1256
1257   @NotNull
1258   public static <T> String join(@NotNull Iterable<? extends T> items,
1259                                 @NotNull Function<? super T, String> f,
1260                                 @NotNull @NonNls String separator) {
1261     final StringBuilder result = new StringBuilder();
1262     for (T item : items) {
1263       String string = f.fun(item);
1264       if (string != null && !string.isEmpty()) {
1265         if (result.length() != 0) result.append(separator);
1266         result.append(string);
1267       }
1268     }
1269     return result.toString();
1270   }
1271
1272   @NotNull
1273   public static String join(@NotNull Collection<? extends String> strings, @NotNull String separator) {
1274     StringBuilder result = new StringBuilder();
1275     join(strings, separator, result);
1276     return result.toString();
1277   }
1278
1279   public static void join(@NotNull Collection<? extends String> strings, @NotNull String separator, @NotNull StringBuilder result) {
1280     boolean isFirst = true;
1281     for (String string : strings) {
1282       if (string != null) {
1283         if (isFirst) {
1284           isFirst = false;
1285         }
1286         else {
1287           result.append(separator);
1288         }
1289         result.append(string);
1290       }
1291     }
1292   }
1293
1294   @NotNull
1295   public static String join(@NotNull final int[] strings, @NotNull final String separator) {
1296     final StringBuilder result = new StringBuilder();
1297     for (int i = 0; i < strings.length; i++) {
1298       if (i > 0) result.append(separator);
1299       result.append(strings[i]);
1300     }
1301     return result.toString();
1302   }
1303
1304   @NotNull
1305   public static String join(@Nullable final String... strings) {
1306     if (strings == null || strings.length == 0) return "";
1307
1308     final StringBuilder builder = new StringBuilder();
1309     for (final String string : strings) {
1310       builder.append(string);
1311     }
1312     return builder.toString();
1313   }
1314
1315   @NotNull
1316   public static String stripQuotesAroundValue(@NotNull String text) {
1317     if (startsWithChar(text, '\"') || startsWithChar(text, '\'')) text = text.substring(1);
1318     if (endsWithChar(text, '\"') || endsWithChar(text, '\'')) text = text.substring(0, text.length() - 1);
1319     return text;
1320   }
1321
1322   public static boolean isQuotedString(@NotNull String text) {
1323     return startsWithChar(text, '\"') && endsWithChar(text, '\"')
1324            || startsWithChar(text, '\'') && endsWithChar(text, '\'');
1325   }
1326
1327   /**
1328    * Formats the specified file size as a string.
1329    *
1330    * @param fileSize the size to format.
1331    * @return the size formatted as a string.
1332    * @since 5.0.1
1333    */
1334   @NotNull
1335   public static String formatFileSize(final long fileSize) {
1336     if (fileSize < 0x400) {
1337       return CommonBundle.message("format.file.size.bytes", fileSize);
1338     }
1339     if (fileSize < 0x100000) {
1340       long kbytes = fileSize * 100 / 1024;
1341       final String kbs = kbytes / 100 + "." + formatMinor(kbytes % 100);
1342       return CommonBundle.message("format.file.size.kbytes", kbs);
1343     }
1344     long mbytes = fileSize * 100 / 1024 / 1024;
1345     final String size = mbytes / 100 + "." + formatMinor(mbytes % 100);
1346     return CommonBundle.message("format.file.size.mbytes", size);
1347   }
1348
1349   @NotNull
1350   public static String formatDuration(long duration) {
1351     final long minutes = duration / 60000;
1352     final long seconds = ((duration + 500L) % 60000) / 1000;
1353     if (minutes > 0L) {
1354       return minutes + " min " + seconds + " sec";
1355     }
1356     return seconds + " sec";
1357   }
1358
1359   @NotNull
1360   private static String formatMinor(long number) {
1361     if (number > 0L && number <= 9L) {
1362       return "0" + number;
1363     }
1364     return String.valueOf(number);
1365   }
1366
1367   /**
1368    * Returns unpluralized variant using English based heuristics like properties -> property, names -> name, children -> child.
1369    * Returns <code>null</code> if failed to match appropriate heuristic.
1370    *
1371    * @param name english word in plural form
1372    * @return name in singular form or <code>null</code> if failed to find one.
1373    */
1374   @SuppressWarnings({"HardCodedStringLiteral"})
1375   @Nullable
1376   public static String unpluralize(@NotNull final String name) {
1377     if (name.endsWith("sses") || name.endsWith("shes") || name.endsWith("ches") || name.endsWith("xes")) { //?
1378       return name.substring(0, name.length() - 2);
1379     }
1380
1381     if (name.endsWith("ses")) {
1382       return name.substring(0, name.length() - 1);
1383     }
1384
1385     if (name.endsWith("ies")) {
1386       if (name.endsWith("cookies") || name.endsWith("Cookies")) {
1387         return name.substring(0, name.length() - "ookies".length()) + "ookie";
1388       }
1389
1390       return name.substring(0, name.length() - 3) + "y";
1391     }
1392
1393     if (name.endsWith("leaves") || name.endsWith("Leaves")) {
1394       return name.substring(0, name.length() - "eaves".length()) + "eaf";
1395     }
1396
1397     String result = stripEnding(name, "s");
1398     if (result != null) {
1399       return result;
1400     }
1401
1402     if (name.endsWith("children")) {
1403       return name.substring(0, name.length() - "children".length()) + "child";
1404     }
1405
1406     if (name.endsWith("Children") && name.length() > "Children".length()) {
1407       return name.substring(0, name.length() - "Children".length()) + "Child";
1408     }
1409
1410
1411     return null;
1412   }
1413
1414   @Nullable
1415   private static String stripEnding(@NotNull String name, @NotNull String ending) {
1416     if (name.endsWith(ending)) {
1417       if (name.equals(ending)) return name; // do not return empty string
1418       return name.substring(0, name.length() - 1);
1419     }
1420     return null;
1421   }
1422
1423   public static boolean containsAlphaCharacters(@NotNull String value) {
1424     for (int i = 0; i < value.length(); i++) {
1425       if (Character.isLetter(value.charAt(i))) return true;
1426     }
1427     return false;
1428   }
1429
1430   public static boolean containsAnyChar(@NotNull final String value, @NotNull final String chars) {
1431     if (chars.length() > value.length()) {
1432       return containsAnyChar(value, chars, 0, value.length());
1433     }
1434     else {
1435       return containsAnyChar(chars, value, 0, chars.length());
1436     }
1437   }
1438
1439   public static boolean containsAnyChar(@NotNull final String value,
1440                                         @NotNull final String chars,
1441                                         final int start, final int end) {
1442     for (int i = start; i < end; i++) {
1443       if (chars.indexOf(value.charAt(i)) >= 0) {
1444         return true;
1445       }
1446     }
1447
1448     return false;
1449   }
1450
1451   public static boolean containsChar(@NotNull final String value, final char ch) {
1452     return value.indexOf(ch) >= 0;
1453   }
1454
1455   /**
1456    * @deprecated use #capitalize(String)
1457    */
1458   @Nullable
1459   public static String firstLetterToUpperCase(@Nullable final String displayString) {
1460     if (displayString == null || displayString.isEmpty()) return displayString;
1461     char firstChar = displayString.charAt(0);
1462     char uppedFirstChar = toUpperCase(firstChar);
1463
1464     if (uppedFirstChar == firstChar) return displayString;
1465
1466     char[] buffer = displayString.toCharArray();
1467     buffer[0] = uppedFirstChar;
1468     return StringFactory.createShared(buffer);
1469   }
1470
1471   /**
1472    * Strip out all characters not accepted by given filter
1473    *
1474    * @param s      e.g. "/n    my string "
1475    * @param filter e.g. {@link CharFilter#NOT_WHITESPACE_FILTER}
1476    * @return stripped string e.g. "mystring"
1477    */
1478   @NotNull
1479   public static String strip(@NotNull final String s, @NotNull final CharFilter filter) {
1480     final StringBuilder result = new StringBuilder(s.length());
1481     for (int i = 0; i < s.length(); i++) {
1482       char ch = s.charAt(i);
1483       if (filter.accept(ch)) {
1484         result.append(ch);
1485       }
1486     }
1487     return result.toString();
1488   }
1489
1490   @NotNull
1491   public static List<String> findMatches(@NotNull String s, @NotNull Pattern pattern) {
1492     return findMatches(s, pattern, 1);
1493   }
1494
1495   @NotNull
1496   public static List<String> findMatches(@NotNull String s, @NotNull Pattern pattern, int groupIndex) {
1497     List<String> result = new SmartList<String>();
1498     Matcher m = pattern.matcher(s);
1499     while (m.find()) {
1500       String group = m.group(groupIndex);
1501       if (group != null) {
1502         result.add(group);
1503       }
1504     }
1505     return result;
1506   }
1507
1508   /**
1509    * Find position of the first character accepted by given filter.
1510    *
1511    * @param s      the string to search
1512    * @param filter search filter
1513    * @return position of the first character accepted or -1 if not found
1514    */
1515   public static int findFirst(@NotNull final CharSequence s, @NotNull CharFilter filter) {
1516     for (int i = 0; i < s.length(); i++) {
1517       char ch = s.charAt(i);
1518       if (filter.accept(ch)) {
1519         return i;
1520       }
1521     }
1522     return -1;
1523   }
1524
1525   @NotNull
1526   public static String replaceSubstring(@NotNull String string, @NotNull TextRange range, @NotNull String replacement) {
1527     return range.replace(string, replacement);
1528   }
1529
1530   public static boolean startsWithWhitespace(@NotNull String text) {
1531     return !text.isEmpty() && Character.isWhitespace(text.charAt(0));
1532   }
1533
1534   public static boolean isChar(CharSequence seq, int index, char c) {
1535     return index >= 0 && index < seq.length() && seq.charAt(index) == c;
1536   }
1537
1538   public static boolean startsWith(@NotNull CharSequence text, @NotNull CharSequence prefix) {
1539     int l1 = text.length();
1540     int l2 = prefix.length();
1541     if (l1 < l2) return false;
1542
1543     for (int i = 0; i < l2; i++) {
1544       if (text.charAt(i) != prefix.charAt(i)) return false;
1545     }
1546
1547     return true;
1548   }
1549
1550   public static boolean startsWith(@NotNull CharSequence text, int startIndex, @NotNull CharSequence prefix) {
1551     int l1 = text.length() - startIndex;
1552     int l2 = prefix.length();
1553     if (l1 < l2) return false;
1554
1555     for (int i = 0; i < l2; i++) {
1556       if (text.charAt(i + startIndex) != prefix.charAt(i)) return false;
1557     }
1558
1559     return true;
1560   }
1561
1562   public static boolean endsWith(@NotNull CharSequence text, @NotNull CharSequence suffix) {
1563     int l1 = text.length();
1564     int l2 = suffix.length();
1565     if (l1 < l2) return false;
1566
1567     for (int i = l1 - 1; i >= l1 - l2; i--) {
1568       if (text.charAt(i) != suffix.charAt(i + l2 - l1)) return false;
1569     }
1570
1571     return true;
1572   }
1573
1574   @NotNull
1575   public static String commonPrefix(@NotNull String s1, @NotNull String s2) {
1576     return s1.substring(0, commonPrefixLength(s1, s2));
1577   }
1578
1579   public static int commonPrefixLength(@NotNull CharSequence s1, @NotNull CharSequence s2) {
1580     int i;
1581     int minLength = Math.min(s1.length(), s2.length());
1582     for (i = 0; i < minLength; i++) {
1583       if (s1.charAt(i) != s2.charAt(i)) {
1584         break;
1585       }
1586     }
1587     return i;
1588   }
1589
1590   @NotNull
1591   public static String commonSuffix(@NotNull String s1, @NotNull String s2) {
1592     return s1.substring(s1.length() - commonSuffixLength(s1, s2));
1593   }
1594
1595   public static int commonSuffixLength(@NotNull CharSequence s1, @NotNull CharSequence s2) {
1596     int s1Length = s1.length();
1597     int s2Length = s2.length();
1598     if (s1Length == 0 || s2Length == 0) return 0;
1599     int i;
1600     for (i = 0; i < s1Length && i < s2Length; i++) {
1601       if (s1.charAt(s1Length - i - 1) != s2.charAt(s2Length - i - 1)) {
1602         break;
1603       }
1604     }
1605     return i;
1606   }
1607
1608   /**
1609    * Allows to answer if target symbol is contained at given char sequence at <code>[start; end)</code> interval.
1610    *
1611    * @param s     target char sequence to check
1612    * @param start start offset to use within the given char sequence (inclusive)
1613    * @param end   end offset to use within the given char sequence (exclusive)
1614    * @param c     target symbol to check
1615    * @return <code>true</code> if given symbol is contained at the target range of the given char sequence;
1616    * <code>false</code> otherwise
1617    */
1618   public static boolean contains(@NotNull CharSequence s, int start, int end, char c) {
1619     return indexOf(s, c, start, end) >= 0;
1620   }
1621
1622   public static boolean containsWhitespaces(@Nullable CharSequence s) {
1623     if (s == null) return false;
1624
1625     for (int i = 0; i < s.length(); i++) {
1626       if (Character.isWhitespace(s.charAt(i))) return true;
1627     }
1628     return false;
1629   }
1630
1631   public static int indexOf(@NotNull CharSequence s, char c) {
1632     return indexOf(s, c, 0, s.length());
1633   }
1634
1635   public static int indexOf(@NotNull CharSequence s, char c, int start) {
1636     return indexOf(s, c, start, s.length());
1637   }
1638
1639   public static int indexOf(@NotNull CharSequence s, char c, int start, int end) {
1640     for (int i = start; i < end; i++) {
1641       if (s.charAt(i) == c) return i;
1642     }
1643     return -1;
1644   }
1645
1646   public static int indexOf(@NotNull CharSequence s, char c, int start, int end, boolean caseSensitive) {
1647     for (int i = start; i < end; i++) {
1648       if (charsMatch(s.charAt(i), c, !caseSensitive)) return i;
1649     }
1650     return -1;
1651   }
1652
1653   public static int indexOf(@NotNull char[] s, char c, int start, int end, boolean caseSensitive) {
1654     for (int i = start; i < end; i++) {
1655       if (charsMatch(s[i], c, !caseSensitive)) return i;
1656     }
1657     return -1;
1658   }
1659
1660   public static int indexOfSubstringEnd(@NotNull String text, @NotNull String subString) {
1661     int i = text.indexOf(subString);
1662     if (i == -1) return -1;
1663     return i + subString.length();
1664   }
1665
1666   public static int indexOfAny(@NotNull final String s, @NotNull final String chars) {
1667     return indexOfAny(s, chars, 0, s.length());
1668   }
1669
1670   public static int indexOfAny(@NotNull final CharSequence s, @NotNull final String chars) {
1671     return indexOfAny(s, chars, 0, s.length());
1672   }
1673
1674   public static int indexOfAny(@NotNull final String s, @NotNull final String chars, final int start, final int end) {
1675     return indexOfAny((CharSequence)s, chars, start, end);
1676   }
1677
1678   public static int indexOfAny(@NotNull final CharSequence s, @NotNull final String chars, final int start, final int end) {
1679     for (int i = start; i < end; i++) {
1680       if (containsChar(chars, s.charAt(i))) return i;
1681     }
1682     return -1;
1683   }
1684
1685   @Nullable
1686   public static String substringAfter(@NotNull String text, @NotNull String subString) {
1687     int i = text.indexOf(subString);
1688     if (i == -1) return null;
1689     return text.substring(i + subString.length());
1690   }
1691
1692   /**
1693    * Allows to retrieve index of last occurrence of the given symbols at <code>[start; end)</code> sub-sequence of the given text.
1694    *
1695    * @param s     target text
1696    * @param c     target symbol which last occurrence we want to check
1697    * @param start start offset of the target text (inclusive)
1698    * @param end   end offset of the target text (exclusive)
1699    * @return index of the last occurrence of the given symbol at the target sub-sequence of the given text if any;
1700    * <code>-1</code> otherwise
1701    */
1702   public static int lastIndexOf(@NotNull CharSequence s, char c, int start, int end) {
1703     for (int i = end - 1; i >= start; i--) {
1704       if (s.charAt(i) == c) return i;
1705     }
1706     return -1;
1707   }
1708
1709   @NotNull
1710   public static String first(@NotNull String text, final int maxLength, final boolean appendEllipsis) {
1711     return text.length() > maxLength ? text.substring(0, maxLength) + (appendEllipsis ? "..." : "") : text;
1712   }
1713
1714   @NotNull
1715   public static CharSequence first(@NotNull CharSequence text, final int length, final boolean appendEllipsis) {
1716     return text.length() > length ? text.subSequence(0, length) + (appendEllipsis ? "..." : "") : text;
1717   }
1718
1719   @NotNull
1720   public static CharSequence last(@NotNull CharSequence text, final int length, boolean prependEllipsis) {
1721     return text.length() > length ? (prependEllipsis ? "..." : "") + text.subSequence(text.length() - length, text.length()) : text;
1722   }
1723
1724   @NotNull
1725   public static String escapeChar(@NotNull final String str, final char character) {
1726     final StringBuilder buf = new StringBuilder(str);
1727     escapeChar(buf, character);
1728     return buf.toString();
1729   }
1730
1731   private static void escapeChar(@NotNull final StringBuilder buf, final char character) {
1732     int idx = 0;
1733     while ((idx = indexOf(buf, character, idx)) >= 0) {
1734       buf.insert(idx, "\\");
1735       idx += 2;
1736     }
1737   }
1738
1739   @NotNull
1740   public static String escapeQuotes(@NotNull final String str) {
1741     return escapeChar(str, '"');
1742   }
1743
1744   public static void escapeQuotes(@NotNull final StringBuilder buf) {
1745     escapeChar(buf, '"');
1746   }
1747
1748   @NotNull
1749   public static String escapeSlashes(@NotNull final String str) {
1750     return escapeChar(str, '/');
1751   }
1752
1753   @NotNull
1754   public static String escapeBackSlashes(@NotNull final String str) {
1755     return escapeChar(str, '\\');
1756   }
1757
1758   public static void escapeSlashes(@NotNull final StringBuilder buf) {
1759     escapeChar(buf, '/');
1760   }
1761
1762   @NotNull
1763   public static String unescapeSlashes(@NotNull final String str) {
1764     final StringBuilder buf = new StringBuilder(str.length());
1765     unescapeSlashes(buf, str);
1766     return buf.toString();
1767   }
1768
1769   private static void unescapeSlashes(@NotNull StringBuilder buf, @NotNull String str) {
1770     final int length = str.length();
1771     final int last = length - 1;
1772     for (int i = 0; i < length; i++) {
1773       char ch = str.charAt(i);
1774       if (ch == '\\' && i != last) {
1775         i++;
1776         ch = str.charAt(i);
1777         if (ch != '/') buf.append('\\');
1778       }
1779
1780       buf.append(ch);
1781     }
1782   }
1783
1784   public static void quote(@NotNull final StringBuilder builder) {
1785     quote(builder, '\"');
1786   }
1787
1788   public static void quote(@NotNull final StringBuilder builder, final char quotingChar) {
1789     builder.insert(0, quotingChar);
1790     builder.append(quotingChar);
1791   }
1792
1793   @NotNull
1794   public static String wrapWithDoubleQuote(@NotNull String str) {
1795     return '\"' + str + "\"";
1796   }
1797
1798   @NonNls private static final String[] REPLACES_REFS = {"&lt;", "&gt;", "&amp;", "&#39;", "&quot;"};
1799   @NonNls private static final String[] REPLACES_DISP = {"<", ">", "&", "'", "\""};
1800
1801   public static String unescapeXml(@Nullable final String text) {
1802     if (text == null) return null;
1803     return replace(text, REPLACES_REFS, REPLACES_DISP);
1804   }
1805
1806   public static String escapeXml(@Nullable final String text) {
1807     if (text == null) return null;
1808     return replace(text, REPLACES_DISP, REPLACES_REFS);
1809   }
1810
1811   @NotNull
1812   public static String htmlEmphasize(String text) {
1813     return "<b><code>" + escapeXml(text) + "</code></b>";
1814   }
1815
1816
1817   @NotNull
1818   public static String escapeToRegexp(@NotNull String text) {
1819     final StringBuilder result = new StringBuilder(text.length());
1820     return escapeToRegexp(text, result).toString();
1821   }
1822
1823   @NotNull
1824   public static StringBuilder escapeToRegexp(@NotNull CharSequence text, @NotNull StringBuilder builder) {
1825     for (int i = 0; i < text.length(); i++) {
1826       final char c = text.charAt(i);
1827       if (c == ' ' || Character.isLetter(c) || Character.isDigit(c) || c == '_') {
1828         builder.append(c);
1829       }
1830       else if (c == '\n') {
1831         builder.append("\\n");
1832       }
1833       else {
1834         builder.append('\\').append(c);
1835       }
1836     }
1837
1838     return builder;
1839   }
1840
1841   public static boolean isNotEscapedBackslash(@NotNull char[] chars, int startOffset, int backslashOffset) {
1842     if (chars[backslashOffset] != '\\') {
1843       return false;
1844     }
1845     boolean escaped = false;
1846     for (int i = startOffset; i < backslashOffset; i++) {
1847       if (chars[i] == '\\') {
1848         escaped = !escaped;
1849       }
1850       else {
1851         escaped = false;
1852       }
1853     }
1854     return !escaped;
1855   }
1856
1857   public static boolean isNotEscapedBackslash(@NotNull CharSequence text, int startOffset, int backslashOffset) {
1858     if (text.charAt(backslashOffset) != '\\') {
1859       return false;
1860     }
1861     boolean escaped = false;
1862     for (int i = startOffset; i < backslashOffset; i++) {
1863       if (text.charAt(i) == '\\') {
1864         escaped = !escaped;
1865       }
1866       else {
1867         escaped = false;
1868       }
1869     }
1870     return !escaped;
1871   }
1872
1873   @NotNull
1874   public static String replace(@NotNull String text, @NotNull String[] from, @NotNull String[] to) {
1875     final StringBuilder result = new StringBuilder(text.length());
1876     replace:
1877     for (int i = 0; i < text.length(); i++) {
1878       for (int j = 0; j < from.length; j += 1) {
1879         String toReplace = from[j];
1880         String replaceWith = to[j];
1881
1882         final int len = toReplace.length();
1883         if (text.regionMatches(i, toReplace, 0, len)) {
1884           result.append(replaceWith);
1885           i += len - 1;
1886           continue replace;
1887         }
1888       }
1889       result.append(text.charAt(i));
1890     }
1891     return result.toString();
1892   }
1893
1894   @NotNull
1895   public static String[] filterEmptyStrings(@NotNull String[] strings) {
1896     int emptyCount = 0;
1897     for (String string : strings) {
1898       if (string == null || string.isEmpty()) emptyCount++;
1899     }
1900     if (emptyCount == 0) return strings;
1901
1902     String[] result = ArrayUtil.newStringArray(strings.length - emptyCount);
1903     int count = 0;
1904     for (String string : strings) {
1905       if (string == null || string.isEmpty()) continue;
1906       result[count++] = string;
1907     }
1908
1909     return result;
1910   }
1911
1912   public static int countNewLines(@NotNull CharSequence text) {
1913     return countChars(text, '\n');
1914   }
1915
1916   public static int countChars(@NotNull CharSequence text, char c) {
1917     return countChars(text, c, 0, false);
1918   }
1919
1920   public static int countChars(@NotNull CharSequence text, char c, int offset, boolean continuous) {
1921     int count = 0;
1922     for (int i = offset; i < text.length(); ++i) {
1923       if (text.charAt(i) == c) {
1924         count++;
1925       }
1926       else if (continuous) {
1927         break;
1928       }
1929     }
1930     return count;
1931   }
1932
1933   @NotNull
1934   public static String capitalsOnly(@NotNull String s) {
1935     StringBuilder b = new StringBuilder();
1936     for (int i = 0; i < s.length(); i++) {
1937       if (Character.isUpperCase(s.charAt(i))) {
1938         b.append(s.charAt(i));
1939       }
1940     }
1941
1942     return b.toString();
1943   }
1944
1945   /**
1946    * @param args Strings to join.
1947    * @return {@code null} if any of given Strings is {@code null}.
1948    */
1949   @Nullable
1950   public static String joinOrNull(@NotNull String... args) {
1951     StringBuilder r = new StringBuilder();
1952     for (String arg : args) {
1953       if (arg == null) return null;
1954       r.append(arg);
1955     }
1956     return r.toString();
1957   }
1958
1959   @Nullable
1960   public static String getPropertyName(@NonNls @NotNull String methodName) {
1961     if (methodName.startsWith("get")) {
1962       return Introspector.decapitalize(methodName.substring(3));
1963     }
1964     else if (methodName.startsWith("is")) {
1965       return Introspector.decapitalize(methodName.substring(2));
1966     }
1967     else if (methodName.startsWith("set")) {
1968       return Introspector.decapitalize(methodName.substring(3));
1969     }
1970     else {
1971       return null;
1972     }
1973   }
1974
1975   public static boolean isJavaIdentifierStart(char c) {
1976     return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || Character.isJavaIdentifierStart(c);
1977   }
1978
1979   public static boolean isJavaIdentifierPart(char c) {
1980     return c >= '0' && c <= '9' || isJavaIdentifierStart(c);
1981   }
1982
1983   public static boolean isJavaIdentifier(@NotNull String text) {
1984     int len = text.length();
1985     if (len == 0) return false;
1986
1987     if (!isJavaIdentifierStart(text.charAt(0))) return false;
1988
1989     for (int i = 1; i < len; i++) {
1990       if (!isJavaIdentifierPart(text.charAt(i))) return false;
1991     }
1992
1993     return true;
1994   }
1995
1996   /**
1997    * Escape property name or key in property file. Unicode characters are escaped as well.
1998    *
1999    * @param input an input to escape
2000    * @param isKey if true, the rules for key escaping are applied. The leading space is escaped in that case.
2001    * @return an escaped string
2002    */
2003   @NotNull
2004   public static String escapeProperty(@NotNull String input, final boolean isKey) {
2005     final StringBuilder escaped = new StringBuilder(input.length());
2006     for (int i = 0; i < input.length(); i++) {
2007       final char ch = input.charAt(i);
2008       switch (ch) {
2009         case ' ':
2010           if (isKey && i == 0) {
2011             // only the leading space has to be escaped
2012             escaped.append('\\');
2013           }
2014           escaped.append(' ');
2015           break;
2016         case '\t':
2017           escaped.append("\\t");
2018           break;
2019         case '\r':
2020           escaped.append("\\r");
2021           break;
2022         case '\n':
2023           escaped.append("\\n");
2024           break;
2025         case '\f':
2026           escaped.append("\\f");
2027           break;
2028         case '\\':
2029         case '#':
2030         case '!':
2031         case ':':
2032         case '=':
2033           escaped.append('\\');
2034           escaped.append(ch);
2035           break;
2036         default:
2037           if (20 < ch && ch < 0x7F) {
2038             escaped.append(ch);
2039           }
2040           else {
2041             escaped.append("\\u");
2042             escaped.append(Character.forDigit((ch >> 12) & 0xF, 16));
2043             escaped.append(Character.forDigit((ch >> 8) & 0xF, 16));
2044             escaped.append(Character.forDigit((ch >> 4) & 0xF, 16));
2045             escaped.append(Character.forDigit((ch) & 0xF, 16));
2046           }
2047           break;
2048       }
2049     }
2050     return escaped.toString();
2051   }
2052
2053   public static String getQualifiedName(@Nullable String packageName, String className) {
2054     if (packageName == null || packageName.isEmpty()) {
2055       return className;
2056     }
2057     return packageName + '.' + className;
2058   }
2059
2060   public static int compareVersionNumbers(@Nullable String v1, @Nullable String v2) {
2061     if (v1 == null && v2 == null) {
2062       return 0;
2063     }
2064     if (v1 == null) {
2065       return -1;
2066     }
2067     if (v2 == null) {
2068       return 1;
2069     }
2070
2071     String[] part1 = v1.split("[\\.\\_\\-]");
2072     String[] part2 = v2.split("[\\.\\_\\-]");
2073
2074     int idx = 0;
2075     for (; idx < part1.length && idx < part2.length; idx++) {
2076       String p1 = part1[idx];
2077       String p2 = part2[idx];
2078
2079       int cmp;
2080       if (p1.matches("\\d+") && p2.matches("\\d+")) {
2081         cmp = new Integer(p1).compareTo(new Integer(p2));
2082       }
2083       else {
2084         cmp = part1[idx].compareTo(part2[idx]);
2085       }
2086       if (cmp != 0) return cmp;
2087     }
2088
2089     if (part1.length == part2.length) {
2090       return 0;
2091     }
2092     else {
2093       boolean left = part1.length > idx;
2094       String[] parts = left ? part1 : part2;
2095
2096       for (; idx < parts.length; idx++) {
2097         String p = parts[idx];
2098         int cmp;
2099         if (p.matches("\\d+")) {
2100           cmp = new Integer(p).compareTo(0);
2101         }
2102         else {
2103           cmp = 1;
2104         }
2105         if (cmp != 0) return left ? cmp : -cmp;
2106       }
2107       return 0;
2108     }
2109   }
2110
2111   public static int getOccurrenceCount(@NotNull String text, final char c) {
2112     int res = 0;
2113     int i = 0;
2114     while (i < text.length()) {
2115       i = text.indexOf(c, i);
2116       if (i >= 0) {
2117         res++;
2118         i++;
2119       }
2120       else {
2121         break;
2122       }
2123     }
2124     return res;
2125   }
2126
2127   public static int getOccurrenceCount(@NotNull String text, @NotNull String s) {
2128     int res = 0;
2129     int i = 0;
2130     while (i < text.length()) {
2131       i = text.indexOf(s, i);
2132       if (i >= 0) {
2133         res++;
2134         i++;
2135       }
2136       else {
2137         break;
2138       }
2139     }
2140     return res;
2141   }
2142
2143   @NotNull
2144   public static String fixVariableNameDerivedFromPropertyName(@NotNull String name) {
2145     if (isEmptyOrSpaces(name)) return name;
2146     char c = name.charAt(0);
2147     if (isVowel(c)) {
2148       return "an" + Character.toUpperCase(c) + name.substring(1);
2149     }
2150     return "a" + Character.toUpperCase(c) + name.substring(1);
2151   }
2152
2153   @NotNull
2154   public static String sanitizeJavaIdentifier(@NotNull String name) {
2155     final StringBuilder result = new StringBuilder(name.length());
2156
2157     for (int i = 0; i < name.length(); i++) {
2158       final char ch = name.charAt(i);
2159       if (Character.isJavaIdentifierPart(ch)) {
2160         if (result.length() == 0 && !Character.isJavaIdentifierStart(ch)) {
2161           result.append("_");
2162         }
2163         result.append(ch);
2164       }
2165     }
2166
2167     return result.toString();
2168   }
2169
2170   public static void assertValidSeparators(@NotNull CharSequence s) {
2171     char[] chars = CharArrayUtil.fromSequenceWithoutCopying(s);
2172     int slashRIndex = -1;
2173
2174     if (chars != null) {
2175       for (int i = 0, len = s.length(); i < len; ++i) {
2176         if (chars[i] == '\r') {
2177           slashRIndex = i;
2178           break;
2179         }
2180       }
2181     }
2182     else {
2183       for (int i = 0, len = s.length(); i < len; i++) {
2184         if (s.charAt(i) == '\r') {
2185           slashRIndex = i;
2186           break;
2187         }
2188       }
2189     }
2190
2191     if (slashRIndex != -1) {
2192       String context =
2193         String.valueOf(last(s.subSequence(0, slashRIndex), 10, true)) + first(s.subSequence(slashRIndex, s.length()), 10, true);
2194       context = escapeStringCharacters(context);
2195       LOG.error("Wrong line separators: '" + context + "' at offset " + slashRIndex);
2196     }
2197   }
2198
2199   @NotNull
2200   public static String tail(@NotNull String s, final int idx) {
2201     return idx >= s.length() ? "" : s.substring(idx, s.length());
2202   }
2203
2204   /**
2205    * Splits string by lines.
2206    *
2207    * @param string String to split
2208    * @return array of strings
2209    */
2210   @NotNull
2211   public static String[] splitByLines(@NotNull String string) {
2212     return splitByLines(string, true);
2213   }
2214
2215   /**
2216    * Splits string by lines. If several line separators are in a row corresponding empty lines
2217    * are also added to result if {@code excludeEmptyStrings} is {@code false}.
2218    *
2219    * @param string String to split
2220    * @return array of strings
2221    */
2222   @NotNull
2223   public static String[] splitByLines(@NotNull String string, boolean excludeEmptyStrings) {
2224     return (excludeEmptyStrings ? EOL_SPLIT_PATTERN : EOL_SPLIT_PATTERN_WITH_EMPTY).split(string);
2225   }
2226
2227   @NotNull
2228   public static String[] splitByLinesDontTrim(@NotNull String string) {
2229     return EOL_SPLIT_DONT_TRIM_PATTERN.split(string);
2230   }
2231
2232   /**
2233    * Splits string by lines, keeping all line separators at the line ends and in the empty lines.
2234    * <br> E.g. splitting text
2235    * <blockquote>
2236    *   foo\r\n<br>
2237    *   \n<br>
2238    *   bar\n<br>
2239    *   \r\n<br>
2240    *   baz\r<br>
2241    *   \r<br>
2242    * </blockquote>
2243    * will return the following array: foo\r\n, \n, bar\n, \r\n, baz\r, \r
2244    *   
2245    */
2246   @NotNull
2247   public static String[] splitByLinesKeepSeparators(@NotNull String string) {
2248     return EOL_SPLIT_KEEP_SEPARATORS.split(string);
2249   }
2250
2251   @NotNull
2252   public static List<Pair<String, Integer>> getWordsWithOffset(@NotNull String s) {
2253     List<Pair<String, Integer>> res = ContainerUtil.newArrayList();
2254     s += " ";
2255     StringBuilder name = new StringBuilder();
2256     int startInd = -1;
2257     for (int i = 0; i < s.length(); i++) {
2258       if (Character.isWhitespace(s.charAt(i))) {
2259         if (name.length() > 0) {
2260           res.add(Pair.create(name.toString(), startInd));
2261           name.setLength(0);
2262           startInd = -1;
2263         }
2264       }
2265       else {
2266         if (startInd == -1) {
2267           startInd = i;
2268         }
2269         name.append(s.charAt(i));
2270       }
2271     }
2272     return res;
2273   }
2274
2275   /**
2276    * Implementation of "Sorting for Humans: Natural Sort Order":
2277    * http://www.codinghorror.com/blog/2007/12/sorting-for-humans-natural-sort-order.html
2278    */
2279   public static int naturalCompare(@Nullable String string1, @Nullable String string2) {
2280     return naturalCompare(string1, string2, false);
2281   }
2282
2283   private static int naturalCompare(@Nullable String string1, @Nullable String string2, boolean caseSensitive) {
2284     //noinspection StringEquality
2285     if (string1 == string2) {
2286       return 0;
2287     }
2288     if (string1 == null) {
2289       return -1;
2290     }
2291     if (string2 == null) {
2292       return 1;
2293     }
2294
2295     final int string1Length = string1.length();
2296     final int string2Length = string2.length();
2297     int i = 0, j = 0;
2298     for (; i < string1Length && j < string2Length; i++, j++) {
2299       char ch1 = string1.charAt(i);
2300       char ch2 = string2.charAt(j);
2301       if ((isDecimalDigit(ch1) || ch1 == ' ') && (isDecimalDigit(ch2) || ch2 == ' ')) {
2302         int startNum1 = i;
2303         while (ch1 == ' ' || ch1 == '0') { // skip leading spaces and zeros
2304           startNum1++;
2305           if (startNum1 >= string1Length) break;
2306           ch1 = string1.charAt(startNum1);
2307         }
2308         int startNum2 = j;
2309         while (ch2 == ' ' || ch2 == '0') { // skip leading spaces and zeros
2310           startNum2++;
2311           if (startNum2 >= string2Length) break;
2312           ch2 = string2.charAt(startNum2);
2313         }
2314         i = startNum1;
2315         j = startNum2;
2316         // find end index of number
2317         while (i < string1Length && isDecimalDigit(string1.charAt(i))) i++;
2318         while (j < string2Length && isDecimalDigit(string2.charAt(j))) j++;
2319         final int lengthDiff = (i - startNum1) - (j - startNum2);
2320         if (lengthDiff != 0) {
2321           // numbers with more digits are always greater than shorter numbers
2322           return lengthDiff;
2323         }
2324         for (; startNum1 < i; startNum1++, startNum2++) {
2325           // compare numbers with equal digit count
2326           final int diff = string1.charAt(startNum1) - string2.charAt(startNum2);
2327           if (diff != 0) {
2328             return diff;
2329           }
2330         }
2331         i--;
2332         j--;
2333       }
2334       else {
2335         if (caseSensitive) {
2336           return ch1 - ch2;
2337         }
2338         else {
2339           // similar logic to charsMatch() below
2340           if (ch1 != ch2) {
2341             final int diff1 = StringUtilRt.toUpperCase(ch1) - StringUtilRt.toUpperCase(ch2);
2342             if (diff1 != 0) {
2343               final int diff2 = StringUtilRt.toLowerCase(ch1) - StringUtilRt.toLowerCase(ch2);
2344               if (diff2 != 0) {
2345                 return diff2;
2346               }
2347             }
2348           }
2349         }
2350       }
2351     }
2352     // After the loop the end of one of the strings might not have been reached, if the other
2353     // string ends with a number and the strings are equal until the end of that number. When
2354     // there are more characters in the string, then it is greater.
2355     if (i < string1Length) {
2356       return 1;
2357     }
2358     else if (j < string2Length) {
2359       return -1;
2360     }
2361     if (!caseSensitive && string1Length == string2Length) {
2362       // do case sensitive compare if case insensitive strings are equal
2363       return naturalCompare(string1, string2, true);
2364     }
2365     return string1Length - string2Length;
2366   }
2367
2368   public static boolean isDecimalDigit(char c) {
2369     return c >= '0' && c <= '9';
2370   }
2371
2372   public static int compare(@Nullable String s1, @Nullable String s2, boolean ignoreCase) {
2373     //noinspection StringEquality
2374     if (s1 == s2) return 0;
2375     if (s1 == null) return -1;
2376     if (s2 == null) return 1;
2377     return ignoreCase ? s1.compareToIgnoreCase(s2) : s1.compareTo(s2);
2378   }
2379
2380   public static int comparePairs(@Nullable String s1, @Nullable String t1, @Nullable String s2, @Nullable String t2, boolean ignoreCase) {
2381     final int compare = compare(s1, s2, ignoreCase);
2382     return compare != 0 ? compare : compare(t1, t2, ignoreCase);
2383   }
2384
2385   public static int hashCode(@NotNull CharSequence s) {
2386     return stringHashCode(s);
2387   }
2388
2389   public static boolean equals(@Nullable CharSequence s1, @Nullable CharSequence s2) {
2390     if (s1 == null ^ s2 == null) {
2391       return false;
2392     }
2393
2394     if (s1 == null) {
2395       return true;
2396     }
2397
2398     if (s1.length() != s2.length()) {
2399       return false;
2400     }
2401     for (int i = 0; i < s1.length(); i++) {
2402       if (s1.charAt(i) != s2.charAt(i)) {
2403         return false;
2404       }
2405     }
2406     return true;
2407   }
2408
2409   public static boolean equalsIgnoreCase(@Nullable CharSequence s1, @Nullable CharSequence s2) {
2410     if (s1 == null ^ s2 == null) {
2411       return false;
2412     }
2413
2414     if (s1 == null) {
2415       return true;
2416     }
2417
2418     if (s1.length() != s2.length()) {
2419       return false;
2420     }
2421     for (int i = 0; i < s1.length(); i++) {
2422       if (!charsMatch(s1.charAt(i), s2.charAt(i), true)) {
2423         return false;
2424       }
2425     }
2426     return true;
2427   }
2428
2429   public static int compare(char c1, char c2, boolean ignoreCase) {
2430     // duplicating String.equalsIgnoreCase logic
2431     int d = c1 - c2;
2432     if (d == 0 || !ignoreCase) {
2433       return d;
2434     }
2435     // If characters don't match but case may be ignored,
2436     // try converting both characters to uppercase.
2437     // If the results match, then the comparison scan should
2438     // continue.
2439     char u1 = StringUtilRt.toUpperCase(c1);
2440     char u2 = StringUtilRt.toUpperCase(c2);
2441     d = u1 - u2;
2442     if (d != 0) {
2443       // Unfortunately, conversion to uppercase does not work properly
2444       // for the Georgian alphabet, which has strange rules about case
2445       // conversion.  So we need to make one last check before
2446       // exiting.
2447       d = StringUtilRt.toLowerCase(u1) - StringUtilRt.toLowerCase(u2);
2448     }
2449     return d;
2450   }
2451
2452   public static boolean charsMatch(char c1, char c2, boolean ignoreCase) {
2453     return compare(c1, c2, ignoreCase) == 0;
2454   }
2455
2456   @NotNull
2457   public static String formatLinks(@NotNull String message) {
2458     Pattern linkPattern = Pattern.compile("http://[a-zA-Z0-9\\./\\-\\+]+");
2459     StringBuffer result = new StringBuffer();
2460     Matcher m = linkPattern.matcher(message);
2461     while (m.find()) {
2462       m.appendReplacement(result, "<a href=\"" + m.group() + "\">" + m.group() + "</a>");
2463     }
2464     m.appendTail(result);
2465     return result.toString();
2466   }
2467
2468   public static boolean isHexDigit(char c) {
2469     return '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F';
2470   }
2471
2472   public static boolean isOctalDigit(char c) {
2473     return '0' <= c && c <= '7';
2474   }
2475
2476   @NotNull
2477   public static String shortenTextWithEllipsis(@NotNull final String text, final int maxLength, final int suffixLength) {
2478     return shortenTextWithEllipsis(text, maxLength, suffixLength, false);
2479   }
2480
2481   @NotNull
2482   public static String trimMiddle(@NotNull String text, int maxLength) {
2483     return shortenTextWithEllipsis(text, maxLength, maxLength >> 1, true);
2484   }
2485
2486   @NotNull
2487   public static String shortenTextWithEllipsis(@NotNull final String text,
2488                                                final int maxLength,
2489                                                final int suffixLength,
2490                                                boolean useEllipsisSymbol) {
2491     final int textLength = text.length();
2492     if (textLength > maxLength) {
2493       String symbol = useEllipsisSymbol ? "\u2026" : "...";
2494       final int prefixLength = maxLength - suffixLength - symbol.length();
2495       assert prefixLength > 0;
2496       return text.substring(0, prefixLength) + symbol + text.substring(textLength - suffixLength);
2497     }
2498     else {
2499       return text;
2500     }
2501   }
2502
2503   @NotNull
2504   public static String shortenPathWithEllipsis(@NotNull final String path, final int maxLength, boolean useEllipsisSymbol) {
2505     return shortenTextWithEllipsis(path, maxLength, (int)(maxLength * 0.7), useEllipsisSymbol);
2506   }
2507
2508   @NotNull
2509   public static String shortenPathWithEllipsis(@NotNull final String path, final int maxLength) {
2510     return shortenPathWithEllipsis(path, maxLength, false);
2511   }
2512
2513   public static boolean charsEqual(char a, char b, boolean ignoreCase) {
2514     return ignoreCase ? charsEqualIgnoreCase(a, b) : a == b;
2515   }
2516
2517   public static boolean charsEqualIgnoreCase(char a, char b) {
2518     return StringUtilRt.charsEqualIgnoreCase(a, b);
2519   }
2520
2521   public static char toUpperCase(char a) {
2522     return StringUtilRt.toUpperCase(a);
2523   }
2524
2525   @NotNull
2526   public static String toUpperCase(@NotNull String a) {
2527     return StringUtilRt.toUpperCase(a);
2528   }
2529
2530   public static char toLowerCase(final char a) {
2531     return StringUtilRt.toLowerCase(a);
2532   }
2533
2534   @NotNull
2535   public static String convertLineSeparators(@NotNull String text) {
2536     return StringUtilRt.convertLineSeparators(text);
2537   }
2538
2539   @NotNull
2540   public static String convertLineSeparators(@NotNull String text, boolean keepCarriageReturn) {
2541     return StringUtilRt.convertLineSeparators(text, keepCarriageReturn);
2542   }
2543
2544   @NotNull
2545   public static String convertLineSeparators(@NotNull String text, @NotNull String newSeparator) {
2546     return StringUtilRt.convertLineSeparators(text, newSeparator);
2547   }
2548
2549   @NotNull
2550   public static String convertLineSeparators(@NotNull String text, @NotNull String newSeparator, @Nullable int[] offsetsToKeep) {
2551     return StringUtilRt.convertLineSeparators(text, newSeparator, offsetsToKeep);
2552   }
2553
2554   @NotNull
2555   public static String convertLineSeparators(@NotNull String text,
2556                                              @NotNull String newSeparator,
2557                                              @Nullable int[] offsetsToKeep,
2558                                              boolean keepCarriageReturn) {
2559     return StringUtilRt.convertLineSeparators(text, newSeparator, offsetsToKeep, keepCarriageReturn);
2560   }
2561
2562   public static int parseInt(final String string, final int defaultValue) {
2563     return StringUtilRt.parseInt(string, defaultValue);
2564   }
2565
2566   public static double parseDouble(final String string, final double defaultValue) {
2567     return StringUtilRt.parseDouble(string, defaultValue);
2568   }
2569
2570   public static boolean parseBoolean(String string, final boolean defaultValue) {
2571     return StringUtilRt.parseBoolean(string, defaultValue);
2572   }
2573
2574   @NotNull
2575   public static String getShortName(@NotNull Class aClass) {
2576     return StringUtilRt.getShortName(aClass);
2577   }
2578
2579   @NotNull
2580   public static String getShortName(@NotNull String fqName) {
2581     return StringUtilRt.getShortName(fqName);
2582   }
2583
2584   @NotNull
2585   public static String getShortName(@NotNull String fqName, char separator) {
2586     return StringUtilRt.getShortName(fqName, separator);
2587   }
2588
2589   @NotNull
2590   public static CharSequence newBombedCharSequence(@NotNull CharSequence sequence, long delay) {
2591     final long myTime = System.currentTimeMillis() + delay;
2592     return new BombedCharSequence(sequence) {
2593       @Override
2594       protected void checkCanceled() {
2595         long l = System.currentTimeMillis();
2596         if (l >= myTime) {
2597           throw new ProcessCanceledException();
2598         }
2599       }
2600     };
2601   }
2602
2603   public static boolean trimEnd(@NotNull StringBuilder buffer, @NotNull CharSequence end) {
2604     if (endsWith(buffer, end)) {
2605       buffer.delete(buffer.length() - end.length(), buffer.length());
2606       return true;
2607     }
2608     return false;
2609   }
2610
2611   private static boolean trimStart(@NotNull StringBuilder buffer, @NotNull CharSequence start) {
2612     if (startsWith(buffer, start)) {
2613       buffer.delete(0, start.length());
2614       return true;
2615     }
2616     return false;
2617   }
2618
2619   /**
2620    * Say smallPart = "op" and bigPart="open". Method returns true for "Ope" and false for "ops"
2621    */
2622   public static boolean isBetween(@NotNull String string, @NotNull String smallPart, @NotNull String bigPart) {
2623     final String s = string.toLowerCase();
2624     return s.startsWith(smallPart.toLowerCase()) && bigPart.toLowerCase().startsWith(s);
2625   }
2626
2627   /**
2628    * Expirable CharSequence. Very useful to control external library execution time,
2629    * i.e. when java.util.regex.Pattern match goes out of control.
2630    */
2631   public abstract static class BombedCharSequence implements CharSequence {
2632     private CharSequence delegate;
2633     private int i = 0;
2634
2635     public BombedCharSequence(@NotNull CharSequence sequence) {
2636       delegate = sequence;
2637     }
2638
2639     @Override
2640     public int length() {
2641       check();
2642       return delegate.length();
2643     }
2644
2645     @Override
2646     public char charAt(int i) {
2647       check();
2648       return delegate.charAt(i);
2649     }
2650
2651     protected void check() {
2652       if ((++i & 1023) == 0) {
2653         checkCanceled();
2654       }
2655     }
2656
2657     @NotNull
2658     @Override
2659     public String toString() {
2660       check();
2661       return delegate.toString();
2662     }
2663
2664     protected abstract void checkCanceled();
2665
2666     @Override
2667     public CharSequence subSequence(int i, int i1) {
2668       check();
2669       return delegate.subSequence(i, i1);
2670     }
2671   }
2672 }