001package gudusoft.gsqlparser.util;
002
003/**
004 * String operations that give exactly the result of a {@code java.util.regex} {@code replaceAll}, in one linear pass.
005 * The regexes they replace backtrack over a long run that does not end where the pattern needs it to, which made them
006 * quadratic on long input.
007 *
008 * <p>Whitespace here is the regex {@code \s} of Java 8 without {@code UNICODE_CHARACTER_CLASS}: space, tab, line
009 * feed, vertical tab, form feed and carriage return. A pattern ending in {@code $} (without {@code MULTILINE}) also
010 * matches before a line terminator that ends the input: {@code \n}, {@code \r\n}, {@code \r}, {@code \u0085},
011 * {@code 
} or {@code 
}.
012 */
013public final class RegexEquivalents {
014
015        private RegexEquivalents() {
016        }
017
018        /** A character of the regex {@code \s}. */
019        public static boolean isRegexWhitespace(char c) {
020                return c == ' ' || c == '\t' || c == '\n' || c == 0x0B || c == '\f' || c == '\r';
021        }
022
023        /** {@code s.replaceAll("\\s+", "")}. */
024        public static String removeWhitespace(String s) {
025                StringBuilder out = null;
026                for (int i = 0; i < s.length(); i++) {
027                        char c = s.charAt(i);
028                        if (isRegexWhitespace(c)) {
029                                if (out == null) {
030                                        out = new StringBuilder(s.length()).append(s, 0, i);
031                                }
032                        } else if (out != null) {
033                                out.append(c);
034                        }
035                }
036                return out == null ? s : out.toString();
037        }
038
039        /** {@code s.replaceAll("^\\s+", "")}. */
040        public static String stripLeadingWhitespace(String s) {
041                int i = 0;
042                while (i < s.length() && isRegexWhitespace(s.charAt(i))) {
043                        i++;
044                }
045                return i == 0 ? s : s.substring(i);
046        }
047
048        /** {@code s.replaceAll("\\s+$", "")}. */
049        public static String stripTrailingWhitespace(String s) {
050                return stripRunBeforeEnd(s, WHITESPACE);
051        }
052
053        /** {@code s.replaceAll(";+$", "")}. */
054        public static String stripTrailingSemicolons(String s) {
055                return stripRunBeforeEnd(s, SEMICOLON);
056        }
057
058        private interface CharClass {
059                boolean contains(char c);
060        }
061
062        private static final CharClass WHITESPACE = new CharClass() {
063                public boolean contains(char c) {
064                        return isRegexWhitespace(c);
065                }
066        };
067
068        private static final CharClass SEMICOLON = new CharClass() {
069                public boolean contains(char c) {
070                        return c == ';';
071                }
072        };
073
074        /**
075         * {@code s.replaceAll("X+$", "")} for the class X: each maximal run of X is matched from its start, greedily, up
076         * to the last position inside it where {@code $} holds, as the regex matches it.
077         */
078        private static String stripRunBeforeEnd(String s, CharClass x) {
079                int length = s.length();
080                StringBuilder out = null;
081                int copied = 0;
082                int i = 0;
083                while (i < length) {
084                        if (!x.contains(s.charAt(i))) {
085                                i++;
086                                continue;
087                        }
088                        int end = i;
089                        while (end < length && x.contains(s.charAt(end))) {
090                                end++;
091                        }
092                        int matchEnd = -1;
093                        // $ holds only in the last two positions and at the end, so only those can end a match
094                        for (int p = Math.min(end, length); p > i && p >= length - 2; p--) {
095                                if (dollarHolds(s, p)) {
096                                        matchEnd = p;
097                                        break;
098                                }
099                        }
100                        if (matchEnd < 0) {
101                                i = end;
102                                continue;
103                        }
104                        if (out == null) {
105                                out = new StringBuilder(length);
106                        }
107                        out.append(s, copied, i);
108                        copied = matchEnd;
109                        i = matchEnd;
110                }
111                if (out == null) {
112                        return s;
113                }
114                return out.append(s, copied, length).toString();
115        }
116
117        /** The regex {@code $} without {@code MULTILINE} at position {@code i}. */
118        private static boolean dollarHolds(String s, int i) {
119                int length = s.length();
120                if (i == length) {
121                        return true;
122                }
123                if (i == length - 2) {
124                        return s.charAt(i) == '\r' && s.charAt(i + 1) == '\n';
125                }
126                if (i == length - 1) {
127                        char c = s.charAt(i);
128                        if (c == '\n') {
129                                return i == 0 || s.charAt(i - 1) != '\r';
130                        }
131                        return c == '\r' || c == '\u0085' || c == '
' || c == '
';
132                }
133                return false;
134        }
135}