001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      https://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.lang3.time;
018
019import java.io.IOException;
020import java.io.ObjectInputStream;
021import java.io.Serializable;
022import java.text.DateFormatSymbols;
023import java.text.ParseException;
024import java.text.ParsePosition;
025import java.text.SimpleDateFormat;
026import java.util.ArrayList;
027import java.util.Arrays;
028import java.util.Calendar;
029import java.util.Comparator;
030import java.util.Date;
031import java.util.HashMap;
032import java.util.List;
033import java.util.ListIterator;
034import java.util.Locale;
035import java.util.Map;
036import java.util.Objects;
037import java.util.Set;
038import java.util.TimeZone;
039import java.util.TreeMap;
040import java.util.TreeSet;
041import java.util.concurrent.ConcurrentHashMap;
042import java.util.concurrent.ConcurrentMap;
043import java.util.regex.Matcher;
044import java.util.regex.Pattern;
045import java.util.stream.Stream;
046
047import org.apache.commons.lang3.ArraySorter;
048import org.apache.commons.lang3.CharUtils;
049import org.apache.commons.lang3.LocaleUtils;
050
051/**
052 * FastDateParser is a fast and thread-safe version of {@link java.text.SimpleDateFormat}.
053 *
054 * <p>
055 * To obtain a proxy to a FastDateParser, use {@link FastDateFormat#getInstance(String, TimeZone, Locale)} or another variation of the factory methods of
056 * {@link FastDateFormat}.
057 * </p>
058 *
059 * <p>
060 * Since FastDateParser is thread safe, you can use a static member instance:
061 * </p>
062 * {@code
063 *     private static final DateParser DATE_PARSER = FastDateFormat.getInstance("yyyy-MM-dd");
064 * }
065 *
066 * <p>
067 * This class can be used as a direct replacement for {@link SimpleDateFormat} in most parsing situations. This class is especially useful in multi-threaded
068 * server environments. {@link SimpleDateFormat} is not thread-safe in any JDK version, nor will it be as Sun has closed the
069 * <a href="https://bugs.openjdk.org/browse/JDK-4228335">bug</a>/RFE.
070 * </p>
071 *
072 * <p>
073 * Only parsing is supported by this class, but all patterns are compatible with SimpleDateFormat.
074 * </p>
075 *
076 * <p>
077 * The class operates in lenient mode, so for example a time of 90 minutes is treated as 1 hour 30 minutes.
078 * </p>
079 *
080 * <p>
081 * Timing tests indicate this class is as about as fast as SimpleDateFormat in single thread applications and about 25% faster in multi-thread applications.
082 * </p>
083 *
084 * @since 3.2
085 * @see FastDatePrinter
086 */
087public class FastDateParser implements DateParser, Serializable {
088
089    /**
090     * A strategy that handles a text field in the parsing pattern
091     */
092    private static final class CaseInsensitiveTextStrategy extends PatternStrategy {
093
094        private final int field;
095        private final Locale locale;
096        private final Map<String, Integer> lKeyValues;
097
098        /**
099         * Constructs a Strategy that parses a Text field
100         *
101         * @param field            The Calendar field
102         * @param definingCalendar The Calendar to use
103         * @param locale           The Locale to use
104         */
105        CaseInsensitiveTextStrategy(final int field, final Calendar definingCalendar, final Locale locale) {
106            this.field = field;
107            this.locale = LocaleUtils.toLocale(locale);
108
109            final StringBuilder regex = new StringBuilder();
110            regex.append("((?iu)");
111            lKeyValues = appendDisplayNames(definingCalendar, locale, field, regex);
112            regex.setLength(regex.length() - 1);
113            regex.append(")");
114            createPattern(regex);
115        }
116
117        /**
118         * {@inheritDoc}
119         */
120        @Override
121        void setCalendar(final FastDateParser parser, final Calendar calendar, final String value) {
122            final String lowerCase = value.toLowerCase(locale);
123            Integer iVal = lKeyValues.get(lowerCase);
124            if (iVal == null) {
125                // match missing the optional trailing period
126                iVal = lKeyValues.get(lowerCase + '.');
127            }
128            // LANG-1669: Mimic fix done in OpenJDK 17 to resolve issue with parsing newly supported day periods added in OpenJDK 16
129            if (Calendar.AM_PM != this.field || iVal <= 1) {
130                calendar.set(field, iVal.intValue());
131            }
132        }
133
134        /**
135         * Converts this instance to a handy debug string.
136         *
137         * @since 3.12.0
138         */
139        @Override
140        public String toString() {
141            return "CaseInsensitiveTextStrategy [field=" + field + ", locale=" + locale + ", lKeyValues=" + lKeyValues + ", pattern=" + pattern + "]";
142        }
143    }
144
145    /**
146     * A strategy that copies the static or quoted field in the parsing pattern
147     */
148    private static final class CopyQuotedStrategy extends Strategy {
149
150        private final String formatField;
151
152        /**
153         * Constructs a Strategy that ensures the formatField has literal text
154         *
155         * @param formatField The literal text to match
156         */
157        CopyQuotedStrategy(final String formatField) {
158            this.formatField = formatField;
159        }
160
161        /**
162         * {@inheritDoc}
163         */
164        @Override
165        boolean isNumber() {
166            return false;
167        }
168
169        @Override
170        boolean parse(final FastDateParser parser, final Calendar calendar, final String source, final ParsePosition pos, final int maxWidth) {
171            for (int idx = 0; idx < formatField.length(); ++idx) {
172                final int sIdx = idx + pos.getIndex();
173                if (sIdx == source.length()) {
174                    pos.setErrorIndex(sIdx);
175                    return false;
176                }
177                if (formatField.charAt(idx) != source.charAt(sIdx)) {
178                    pos.setErrorIndex(sIdx);
179                    return false;
180                }
181            }
182            pos.setIndex(formatField.length() + pos.getIndex());
183            return true;
184        }
185
186        /**
187         * Converts this instance to a handy debug string.
188         *
189         * @since 3.12.0
190         */
191        @Override
192        public String toString() {
193            return "CopyQuotedStrategy [formatField=" + formatField + "]";
194        }
195    }
196
197    private static final class ISO8601TimeZoneStrategy extends PatternStrategy {
198        // Z, +hh, -hh, +hhmm, -hhmm, +hh:mm or -hh:mm
199
200        private static final Strategy ISO_8601_1_STRATEGY = new ISO8601TimeZoneStrategy("(Z|(?:[+-]\\d{2}))");
201
202        private static final Strategy ISO_8601_2_STRATEGY = new ISO8601TimeZoneStrategy("(Z|(?:[+-]\\d{2}\\d{2}))");
203
204        private static final Strategy ISO_8601_3_STRATEGY = new ISO8601TimeZoneStrategy("(Z|(?:[+-]\\d{2}(?::)\\d{2}))");
205        /**
206         * Factory method for ISO8601TimeZoneStrategies.
207         *
208         * @param tokenLen a token indicating the length of the TimeZone String to be formatted.
209         * @return a ISO8601TimeZoneStrategy that can format TimeZone String of length {@code tokenLen}. If no such strategy exists, an IllegalArgumentException
210         *         will be thrown.
211         */
212        static Strategy getStrategy(final int tokenLen) {
213            switch (tokenLen) {
214            case 1:
215                return ISO_8601_1_STRATEGY;
216            case 2:
217                return ISO_8601_2_STRATEGY;
218            case 3:
219                return ISO_8601_3_STRATEGY;
220            default:
221                throw new IllegalArgumentException("invalid number of X");
222            }
223        }
224        /**
225         * Constructs a Strategy that parses a TimeZone
226         *
227         * @param pattern The Pattern
228         */
229        ISO8601TimeZoneStrategy(final String pattern) {
230            createPattern(pattern);
231        }
232
233        /**
234         * {@inheritDoc}
235         */
236        @Override
237        void setCalendar(final FastDateParser parser, final Calendar calendar, final String value) {
238            calendar.setTimeZone(FastTimeZone.getGmtTimeZone(value));
239        }
240    }
241
242    /**
243     * A strategy that handles a number field in the parsing pattern
244     */
245    private static class NumberStrategy extends Strategy {
246
247        private final int field;
248
249        /**
250         * Constructs a Strategy that parses a Number field
251         *
252         * @param field The Calendar field
253         */
254        NumberStrategy(final int field) {
255            this.field = field;
256        }
257
258        /**
259         * {@inheritDoc}
260         */
261        @Override
262        boolean isNumber() {
263            return true;
264        }
265
266        /**
267         * Make any modifications to parsed integer
268         *
269         * @param parser The parser
270         * @param iValue The parsed integer
271         * @return The modified value
272         */
273        int modify(final FastDateParser parser, final int iValue) {
274            return iValue;
275        }
276
277        @Override
278        boolean parse(final FastDateParser parser, final Calendar calendar, final String source, final ParsePosition pos, final int maxWidth) {
279            int idx = pos.getIndex();
280            int last = source.length();
281
282            if (maxWidth == 0) {
283                // if no maxWidth, strip leading white space
284                for (; idx < last; ++idx) {
285                    final char c = source.charAt(idx);
286                    if (!Character.isWhitespace(c)) {
287                        break;
288                    }
289                }
290                pos.setIndex(idx);
291            } else {
292                final int end = idx + maxWidth;
293                if (last > end) {
294                    last = end;
295                }
296            }
297
298            for (; idx < last; ++idx) {
299                final char c = source.charAt(idx);
300                if (!Character.isDigit(c)) {
301                    break;
302                }
303            }
304
305            if (pos.getIndex() == idx) {
306                pos.setErrorIndex(idx);
307                return false;
308            }
309
310            final int value = Integer.parseInt(source.substring(pos.getIndex(), idx));
311            pos.setIndex(idx);
312
313            calendar.set(field, modify(parser, value));
314            return true;
315        }
316
317        /**
318         * Converts this instance to a handy debug string.
319         *
320         * @since 3.12.0
321         */
322        @Override
323        public String toString() {
324            return "NumberStrategy [field=" + field + "]";
325        }
326    }
327
328    /**
329     * A strategy to parse a single field from the parsing pattern
330     */
331    private abstract static class PatternStrategy extends Strategy {
332
333        Pattern pattern;
334
335        void createPattern(final String regex) {
336            this.pattern = Pattern.compile(regex);
337        }
338
339        void createPattern(final StringBuilder regex) {
340            createPattern(regex.toString());
341        }
342
343        /**
344         * Is this field a number? The default implementation returns false.
345         *
346         * @return true, if field is a number
347         */
348        @Override
349        boolean isNumber() {
350            return false;
351        }
352
353        @Override
354        boolean parse(final FastDateParser parser, final Calendar calendar, final String source, final ParsePosition pos, final int maxWidth) {
355            final Matcher matcher = pattern.matcher(source.substring(pos.getIndex()));
356            if (!matcher.lookingAt()) {
357                pos.setErrorIndex(pos.getIndex());
358                return false;
359            }
360            pos.setIndex(pos.getIndex() + matcher.end(1));
361            setCalendar(parser, calendar, matcher.group(1));
362            return true;
363        }
364
365        abstract void setCalendar(FastDateParser parser, Calendar calendar, String value);
366
367        /**
368         * Converts this instance to a handy debug string.
369         *
370         * @since 3.12.0
371         */
372        @Override
373        public String toString() {
374            return getClass().getSimpleName() + " [pattern=" + pattern + "]";
375        }
376
377    }
378
379    /**
380     * A strategy to parse a single field from the parsing pattern
381     */
382    private abstract static class Strategy {
383
384        /**
385         * Is this field a number? The default implementation returns false.
386         *
387         * @return true, if field is a number
388         */
389        boolean isNumber() {
390            return false;
391        }
392
393        abstract boolean parse(FastDateParser parser, Calendar calendar, String source, ParsePosition pos, int maxWidth);
394    }
395
396    /**
397     * Holds strategy and field width
398     */
399    private static final class StrategyAndWidth {
400
401        final Strategy strategy;
402        final int width;
403
404        StrategyAndWidth(final Strategy strategy, final int width) {
405            this.strategy = Objects.requireNonNull(strategy, "strategy");
406            this.width = width;
407        }
408
409        int getMaxWidth(final ListIterator<StrategyAndWidth> lt) {
410            if (!strategy.isNumber() || !lt.hasNext()) {
411                return 0;
412            }
413            final Strategy nextStrategy = lt.next().strategy;
414            lt.previous();
415            return nextStrategy.isNumber() ? width : 0;
416        }
417
418        @Override
419        public String toString() {
420            return "StrategyAndWidth [strategy=" + strategy + ", width=" + width + "]";
421        }
422    }
423
424    /**
425     * Parse format into Strategies
426     */
427    private final class StrategyParser {
428        private final Calendar definingCalendar;
429        private int currentIdx;
430
431        StrategyParser(final Calendar definingCalendar) {
432            this.definingCalendar = Objects.requireNonNull(definingCalendar, "definingCalendar");
433        }
434
435        StrategyAndWidth getNextStrategy() {
436            if (currentIdx >= pattern.length()) {
437                return null;
438            }
439            final char c = pattern.charAt(currentIdx);
440            if (CharUtils.isAsciiAlpha(c)) {
441                return letterPattern(c);
442            }
443            return literal();
444        }
445
446        private StrategyAndWidth letterPattern(final char c) {
447            final int begin = currentIdx;
448            while (++currentIdx < pattern.length()) {
449                if (pattern.charAt(currentIdx) != c) {
450                    break;
451                }
452            }
453            final int width = currentIdx - begin;
454            return new StrategyAndWidth(getStrategy(c, width, definingCalendar), width);
455        }
456
457        private StrategyAndWidth literal() {
458            boolean activeQuote = false;
459
460            final StringBuilder sb = new StringBuilder();
461            while (currentIdx < pattern.length()) {
462                final char c = pattern.charAt(currentIdx);
463                if (!activeQuote && CharUtils.isAsciiAlpha(c)) {
464                    break;
465                }
466                if (c == '\'' && (++currentIdx == pattern.length() || pattern.charAt(currentIdx) != '\'')) {
467                    activeQuote = !activeQuote;
468                    continue;
469                }
470                ++currentIdx;
471                sb.append(c);
472            }
473            if (activeQuote) {
474                throw new IllegalArgumentException("Unterminated quote");
475            }
476            final String formatField = sb.toString();
477            return new StrategyAndWidth(new CopyQuotedStrategy(formatField), formatField.length());
478        }
479    }
480
481    /**
482     * A strategy that handles a time zone field in the parsing pattern
483     */
484    static class TimeZoneStrategy extends PatternStrategy {
485        private static final class TzInfo {
486            final TimeZone zone;
487            final int dstOffset;
488
489            TzInfo(final TimeZone tz, final boolean useDst) {
490                zone = tz;
491                dstOffset = useDst ? tz.getDSTSavings() : 0;
492            }
493
494            @Override
495            public String toString() {
496                return "TzInfo [zone=" + zone + ", dstOffset=" + dstOffset + "]";
497            }
498        }
499        private static final String RFC_822_TIME_ZONE = "[+-]\\d{4}";
500
501        private static final String GMT_OPTION = TimeZones.GMT_ID + "[+-]\\d{1,2}:\\d{2}";
502
503        /**
504         * Index of zone id from {@link DateFormatSymbols#getZoneStrings()}.
505         */
506        private static final int ID = 0;
507
508        private final Locale locale;
509
510        /**
511         * Using lower case only or upper case only will cause problems with some Locales like Turkey, Armenia, Colognian and also depending on the Java
512         * version. For details, see https://garygregory.wordpress.com/2015/11/03/java-lowercase-conversion-turkey/
513         */
514        private final Map<String, TzInfo> tzNames = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
515
516        /**
517         * Constructs a Strategy that parses a TimeZone
518         *
519         * @param locale The Locale
520         */
521        TimeZoneStrategy(final Locale locale) {
522            this.locale = LocaleUtils.toLocale(locale);
523
524            final StringBuilder sb = new StringBuilder();
525            sb.append("((?iu)" + RFC_822_TIME_ZONE + "|" + GMT_OPTION);
526
527            final Set<String> sorted = new TreeSet<>(LONGER_FIRST_LOWERCASE);
528
529            // Order is undefined.
530            // TODO Use of getZoneStrings() is discouraged per its Javadoc.
531            final String[][] zones = DateFormatSymbols.getInstance(locale).getZoneStrings();
532            for (final String[] zoneNames : zones) {
533                // offset 0 is the time zone ID and is not localized
534                final String tzId = zoneNames[ID];
535                if (tzId.equalsIgnoreCase(TimeZones.GMT_ID)) {
536                    continue;
537                }
538                final TimeZone tz = TimeZone.getTimeZone(tzId);
539                // offset 1 is long standard name
540                // offset 2 is short standard name
541                final TzInfo standard = new TzInfo(tz, false);
542                TzInfo tzInfo = standard;
543                for (int i = 1; i < zoneNames.length; ++i) {
544                    switch (i) {
545                    case 3: // offset 3 is long daylight savings (or summertime) name
546                            // offset 4 is the short summertime name
547                        tzInfo = new TzInfo(tz, true);
548                        break;
549                    case 5: // offset 5 starts additional names, probably standard time
550                        tzInfo = standard;
551                        break;
552                    default:
553                        break;
554                    }
555                    final String zoneName = zoneNames[i];
556                    // ignore the data associated with duplicates supplied in the additional names
557                    if (zoneName != null && sorted.add(zoneName)) {
558                        tzNames.put(zoneName, tzInfo);
559                    }
560                }
561            }
562            // Order is undefined.
563            for (final String tzId : ArraySorter.sort(TimeZone.getAvailableIDs())) {
564                if (tzId.equalsIgnoreCase(TimeZones.GMT_ID)) {
565                    continue;
566                }
567                final TimeZone tz = TimeZone.getTimeZone(tzId);
568                final String zoneName = tz.getDisplayName(locale);
569                if (sorted.add(zoneName)) {
570                    tzNames.put(zoneName, new TzInfo(tz, tz.observesDaylightTime()));
571                }
572            }
573            // order the regex alternatives with longer strings first, greedy
574            // match will ensure the longest string will be consumed
575            sorted.forEach(zoneName -> simpleQuote(sb.append('|'), zoneName));
576            sb.append(")");
577            createPattern(sb);
578        }
579
580        /**
581         * {@inheritDoc}
582         */
583        @Override
584        void setCalendar(final FastDateParser parser, final Calendar calendar, final String timeZone) {
585            final TimeZone tz = FastTimeZone.getGmtTimeZone(timeZone);
586            if (tz != null) {
587                calendar.setTimeZone(tz);
588            } else {
589                TzInfo tzInfo = tzNames.get(timeZone);
590                if (tzInfo == null) {
591                    // match missing the optional trailing period
592                    tzInfo = tzNames.get(timeZone + '.');
593                    if (tzInfo == null) {
594                        // show chars in case this is multiple byte character issue
595                        final char[] charArray = timeZone.toCharArray();
596                        throw new IllegalStateException(String.format("Can't find time zone '%s' (%d %s) in %s", timeZone, charArray.length,
597                                Arrays.toString(charArray), new TreeSet<>(tzNames.keySet())));
598                    }
599                }
600                calendar.set(Calendar.DST_OFFSET, tzInfo.dstOffset);
601                calendar.set(Calendar.ZONE_OFFSET, tzInfo.zone.getRawOffset());
602            }
603        }
604
605        /**
606         * Converts this instance to a handy debug string.
607         *
608         * @since 3.12.0
609         */
610        @Override
611        public String toString() {
612            return "TimeZoneStrategy [locale=" + locale + ", tzNames=" + tzNames + ", pattern=" + pattern + "]";
613        }
614
615    }
616
617    /**
618     * Required for serialization support.
619     *
620     * @see java.io.Serializable
621     */
622    private static final long serialVersionUID = 3L;
623
624    static final Locale JAPANESE_IMPERIAL = new Locale("ja", "JP", "JP");
625
626    /**
627     * comparator used to sort regex alternatives. Alternatives should be ordered longer first, and shorter last. ('february' before 'feb'). All entries must be
628     * lower-case by locale.
629     */
630    private static final Comparator<String> LONGER_FIRST_LOWERCASE = Comparator.reverseOrder();
631
632    // helper classes to parse the format string
633
634    @SuppressWarnings("unchecked") // OK because we are creating an array with no entries
635    private static final ConcurrentMap<Locale, Strategy>[] CACHES = new ConcurrentMap[Calendar.FIELD_COUNT];
636
637    private static final Strategy ABBREVIATED_YEAR_STRATEGY = new NumberStrategy(Calendar.YEAR) {
638        /**
639         * {@inheritDoc}
640         */
641        @Override
642        int modify(final FastDateParser parser, final int iValue) {
643            return iValue < 100 ? parser.adjustYear(iValue) : iValue;
644        }
645    };
646
647    private static final Strategy NUMBER_MONTH_STRATEGY = new NumberStrategy(Calendar.MONTH) {
648        @Override
649        int modify(final FastDateParser parser, final int iValue) {
650            return iValue - 1;
651        }
652    };
653
654    private static final Strategy LITERAL_YEAR_STRATEGY = new NumberStrategy(Calendar.YEAR);
655
656    private static final Strategy WEEK_OF_YEAR_STRATEGY = new NumberStrategy(Calendar.WEEK_OF_YEAR);
657
658    private static final Strategy WEEK_OF_MONTH_STRATEGY = new NumberStrategy(Calendar.WEEK_OF_MONTH);
659
660    private static final Strategy DAY_OF_YEAR_STRATEGY = new NumberStrategy(Calendar.DAY_OF_YEAR);
661
662    private static final Strategy DAY_OF_MONTH_STRATEGY = new NumberStrategy(Calendar.DAY_OF_MONTH);
663
664    private static final Strategy DAY_OF_WEEK_STRATEGY = new NumberStrategy(Calendar.DAY_OF_WEEK) {
665        @Override
666        int modify(final FastDateParser parser, final int iValue) {
667            return iValue == 7 ? Calendar.SUNDAY : iValue + 1;
668        }
669    };
670
671    private static final Strategy DAY_OF_WEEK_IN_MONTH_STRATEGY = new NumberStrategy(Calendar.DAY_OF_WEEK_IN_MONTH);
672
673    private static final Strategy HOUR_OF_DAY_STRATEGY = new NumberStrategy(Calendar.HOUR_OF_DAY);
674
675    private static final Strategy HOUR24_OF_DAY_STRATEGY = new NumberStrategy(Calendar.HOUR_OF_DAY) {
676        @Override
677        int modify(final FastDateParser parser, final int iValue) {
678            return iValue == 24 ? 0 : iValue;
679        }
680    };
681
682    private static final Strategy HOUR12_STRATEGY = new NumberStrategy(Calendar.HOUR) {
683        @Override
684        int modify(final FastDateParser parser, final int iValue) {
685            return iValue == 12 ? 0 : iValue;
686        }
687    };
688
689    private static final Strategy HOUR_STRATEGY = new NumberStrategy(Calendar.HOUR);
690
691    private static final Strategy MINUTE_STRATEGY = new NumberStrategy(Calendar.MINUTE);
692
693    private static final Strategy SECOND_STRATEGY = new NumberStrategy(Calendar.SECOND);
694
695    private static final Strategy MILLISECOND_STRATEGY = new NumberStrategy(Calendar.MILLISECOND);
696
697    /**
698     * Gets the short and long values displayed for a field
699     *
700     * @param calendar The calendar to obtain the short and long values
701     * @param locale   The locale of display names
702     * @param field    The field of interest
703     * @param regex    The regular expression to build
704     * @return The map of string display names to field values
705     */
706    private static Map<String, Integer> appendDisplayNames(final Calendar calendar, final Locale locale, final int field, final StringBuilder regex) {
707        Objects.requireNonNull(calendar, "calendar");
708        final Map<String, Integer> values = new HashMap<>();
709        final Locale actualLocale = LocaleUtils.toLocale(locale);
710        final Map<String, Integer> displayNames = calendar.getDisplayNames(field, Calendar.ALL_STYLES, actualLocale);
711        final TreeSet<String> sorted = new TreeSet<>(LONGER_FIRST_LOWERCASE);
712        displayNames.forEach((k, v) -> {
713            final String keyLc = k.toLowerCase(actualLocale);
714            if (sorted.add(keyLc)) {
715                values.put(keyLc, v);
716            }
717        });
718        sorted.forEach(symbol -> simpleQuote(regex, symbol).append('|'));
719        return values;
720    }
721
722    /**
723     * Clears the cache.
724     */
725    static void clear() {
726        Stream.of(CACHES).filter(Objects::nonNull).forEach(ConcurrentMap::clear);
727    }
728
729    /**
730     * Gets a cache of Strategies for a particular field
731     *
732     * @param field The Calendar field
733     * @return a cache of Locale to Strategy
734     */
735    private static ConcurrentMap<Locale, Strategy> getCache(final int field) {
736        synchronized (CACHES) {
737            if (CACHES[field] == null) {
738                CACHES[field] = new ConcurrentHashMap<>(3);
739            }
740            return CACHES[field];
741        }
742    }
743
744    private static StringBuilder simpleQuote(final StringBuilder sb, final String value) {
745        for (int i = 0; i < value.length(); ++i) {
746            final char c = value.charAt(i);
747            switch (c) {
748            case '\\':
749            case '^':
750            case '$':
751            case '.':
752            case '|':
753            case '?':
754            case '*':
755            case '+':
756            case '(':
757            case ')':
758            case '[':
759            case '{':
760                sb.append('\\');
761                // falls-through
762            default:
763                sb.append(c);
764            }
765        }
766        if (sb.charAt(sb.length() - 1) == '.') {
767            // trailing '.' is optional
768            sb.append('?');
769        }
770        return sb;
771    }
772
773    /** Input pattern. */
774    private final String pattern;
775
776    /** Input TimeZone. */
777    private final TimeZone timeZone;
778
779    /** Input Locale. */
780    private final Locale locale;
781
782    /**
783     * Century from Date.
784     */
785    private final int century;
786
787    /**
788     * Start year from Date.
789     */
790    private final int startYear;
791
792    /** Initialized from Calendar. */
793    private transient List<StrategyAndWidth> patterns;
794
795    /**
796     * Constructs a new FastDateParser.
797     *
798     * Use {@link FastDateFormat#getInstance(String, TimeZone, Locale)} or another variation of the factory methods of {@link FastDateFormat} to get a cached
799     * FastDateParser instance.
800     *
801     * @param pattern  non-null {@link java.text.SimpleDateFormat} compatible pattern
802     * @param timeZone non-null time zone to use
803     * @param locale   non-null locale
804     */
805    protected FastDateParser(final String pattern, final TimeZone timeZone, final Locale locale) {
806        this(pattern, timeZone, locale, null);
807    }
808
809    /**
810     * Constructs a new FastDateParser.
811     *
812     * @param pattern      non-null {@link java.text.SimpleDateFormat} compatible pattern
813     * @param timeZone     non-null time zone to use
814     * @param locale       locale, null maps to the default Locale.
815     * @param centuryStart The start of the century for 2 digit year parsing
816     * @since 3.5
817     */
818    protected FastDateParser(final String pattern, final TimeZone timeZone, final Locale locale, final Date centuryStart) {
819        this.pattern = Objects.requireNonNull(pattern, "pattern");
820        this.timeZone = Objects.requireNonNull(timeZone, "timeZone");
821        this.locale = LocaleUtils.toLocale(locale);
822        final Calendar definingCalendar = Calendar.getInstance(timeZone, this.locale);
823        final int centuryStartYear;
824        if (centuryStart != null) {
825            definingCalendar.setTime(centuryStart);
826            centuryStartYear = definingCalendar.get(Calendar.YEAR);
827        } else if (this.locale.equals(JAPANESE_IMPERIAL)) {
828            centuryStartYear = 0;
829        } else {
830            // from 80 years ago to 20 years from now
831            definingCalendar.setTime(new Date());
832            centuryStartYear = definingCalendar.get(Calendar.YEAR) - 80;
833        }
834        century = centuryStartYear / 100 * 100;
835        startYear = centuryStartYear - century;
836        init(definingCalendar);
837    }
838
839    /**
840     * Adjusts dates to be within appropriate century
841     *
842     * @param twoDigitYear The year to adjust
843     * @return A value between centuryStart(inclusive) to centuryStart+100(exclusive)
844     */
845    private int adjustYear(final int twoDigitYear) {
846        final int trial = century + twoDigitYear;
847        return twoDigitYear >= startYear ? trial : trial + 100;
848    }
849
850    /**
851     * Compares another object for equality with this object.
852     *
853     * @param obj the object to compare to
854     * @return {@code true}if equal to this instance
855     */
856    @Override
857    public boolean equals(final Object obj) {
858        if (!(obj instanceof FastDateParser)) {
859            return false;
860        }
861        final FastDateParser other = (FastDateParser) obj;
862        return pattern.equals(other.pattern) && timeZone.equals(other.timeZone) && locale.equals(other.locale);
863    }
864
865    /*
866     * (non-Javadoc)
867     *
868     * @see org.apache.commons.lang3.time.DateParser#getLocale()
869     */
870    @Override
871    public Locale getLocale() {
872        return locale;
873    }
874
875    /**
876     * Constructs a Strategy that parses a Text field
877     *
878     * @param field            The Calendar field
879     * @param definingCalendar The calendar to obtain the short and long values
880     * @return a TextStrategy for the field and Locale
881     */
882    private Strategy getLocaleSpecificStrategy(final int field, final Calendar definingCalendar) {
883        final ConcurrentMap<Locale, Strategy> cache = getCache(field);
884        return cache.computeIfAbsent(locale,
885                k -> field == Calendar.ZONE_OFFSET ? new TimeZoneStrategy(locale) : new CaseInsensitiveTextStrategy(field, definingCalendar, locale));
886    }
887
888    /*
889     * (non-Javadoc)
890     *
891     * @see org.apache.commons.lang3.time.DateParser#getPattern()
892     */
893    @Override
894    public String getPattern() {
895        return pattern;
896    }
897    /**
898     * Gets a Strategy given a field from a SimpleDateFormat pattern
899     *
900     * @param f                A sub-sequence of the SimpleDateFormat pattern
901     * @param width            formatting width
902     * @param definingCalendar The calendar to obtain the short and long values
903     * @return The Strategy that will handle parsing for the field
904     */
905    private Strategy getStrategy(final char f, final int width, final Calendar definingCalendar) {
906        switch (f) {
907        case 'D':
908            return DAY_OF_YEAR_STRATEGY;
909        case 'E':
910            return getLocaleSpecificStrategy(Calendar.DAY_OF_WEEK, definingCalendar);
911        case 'F':
912            return DAY_OF_WEEK_IN_MONTH_STRATEGY;
913        case 'G':
914            return getLocaleSpecificStrategy(Calendar.ERA, definingCalendar);
915        case 'H': // Hour in day (0-23)
916            return HOUR_OF_DAY_STRATEGY;
917        case 'K': // Hour in am/pm (0-11)
918            return HOUR_STRATEGY;
919        case 'M':
920        case 'L':
921            return width >= 3 ? getLocaleSpecificStrategy(Calendar.MONTH, definingCalendar) : NUMBER_MONTH_STRATEGY;
922        case 'S':
923            return MILLISECOND_STRATEGY;
924        case 'W':
925            return WEEK_OF_MONTH_STRATEGY;
926        case 'a':
927            return getLocaleSpecificStrategy(Calendar.AM_PM, definingCalendar);
928        case 'd':
929            return DAY_OF_MONTH_STRATEGY;
930        case 'h': // Hour in am/pm (1-12), i.e. midday/midnight is 12, not 0
931            return HOUR12_STRATEGY;
932        case 'k': // Hour in day (1-24), i.e. midnight is 24, not 0
933            return HOUR24_OF_DAY_STRATEGY;
934        case 'm':
935            return MINUTE_STRATEGY;
936        case 's':
937            return SECOND_STRATEGY;
938        case 'u':
939            return DAY_OF_WEEK_STRATEGY;
940        case 'w':
941            return WEEK_OF_YEAR_STRATEGY;
942        case 'y':
943        case 'Y':
944            return width > 2 ? LITERAL_YEAR_STRATEGY : ABBREVIATED_YEAR_STRATEGY;
945        case 'X':
946            return ISO8601TimeZoneStrategy.getStrategy(width);
947        case 'Z':
948            if (width == 2) {
949                return ISO8601TimeZoneStrategy.ISO_8601_3_STRATEGY;
950            }
951            // falls-through
952        case 'z':
953            return getLocaleSpecificStrategy(Calendar.ZONE_OFFSET, definingCalendar);
954        default:
955            throw new IllegalArgumentException("Format '" + f + "' not supported");
956        }
957    }
958
959    /*
960     * (non-Javadoc)
961     *
962     * @see org.apache.commons.lang3.time.DateParser#getTimeZone()
963     */
964    @Override
965    public TimeZone getTimeZone() {
966        return timeZone;
967    }
968
969    /**
970     * Returns a hash code compatible with equals.
971     *
972     * @return a hash code compatible with equals
973     */
974    @Override
975    public int hashCode() {
976        return pattern.hashCode() + 13 * (timeZone.hashCode() + 13 * locale.hashCode());
977    }
978
979    /**
980     * Initializes derived fields from defining fields. This is called from constructor and from readObject (de-serialization)
981     *
982     * @param definingCalendar the {@link java.util.Calendar} instance used to initialize this FastDateParser
983     */
984    private void init(final Calendar definingCalendar) {
985        patterns = new ArrayList<>();
986
987        final StrategyParser strategyParser = new StrategyParser(definingCalendar);
988        for (;;) {
989            final StrategyAndWidth field = strategyParser.getNextStrategy();
990            if (field == null) {
991                break;
992            }
993            patterns.add(field);
994        }
995    }
996
997    /*
998     * (non-Javadoc)
999     *
1000     * @see org.apache.commons.lang3.time.DateParser#parse(String)
1001     */
1002    @Override
1003    public Date parse(final String source) throws ParseException {
1004        final ParsePosition pp = new ParsePosition(0);
1005        final Date date = parse(source, pp);
1006        if (date == null) {
1007            // Add a note regarding supported date range
1008            if (locale.equals(JAPANESE_IMPERIAL)) {
1009                throw new ParseException("(The " + locale + " locale does not support dates before 1868 AD)\nUnparseable date: \"" + source,
1010                        pp.getErrorIndex());
1011            }
1012            throw new ParseException("Unparseable date: " + source, pp.getErrorIndex());
1013        }
1014        return date;
1015    }
1016    /**
1017     * This implementation updates the ParsePosition if the parse succeeds. However, it sets the error index to the position before the failed field unlike the
1018     * method {@link java.text.SimpleDateFormat#parse(String, ParsePosition)} which sets the error index to after the failed field.
1019     * <p>
1020     * To determine if the parse has succeeded, the caller must check if the current parse position given by {@link ParsePosition#getIndex()} has been updated.
1021     * If the input buffer has been fully parsed, then the index will point to just after the end of the input buffer.
1022     * </p>
1023     *
1024     * @see org.apache.commons.lang3.time.DateParser#parse(String, java.text.ParsePosition)
1025     */
1026    @Override
1027    public Date parse(final String source, final ParsePosition pos) {
1028        // timing tests indicate getting new instance is 19% faster than cloning
1029        final Calendar cal = Calendar.getInstance(timeZone, locale);
1030        cal.clear();
1031        return parse(source, pos, cal) ? cal.getTime() : null;
1032    }
1033    /**
1034     * Parses a formatted date string according to the format. Updates the Calendar with parsed fields. Upon success, the ParsePosition index is updated to
1035     * indicate how much of the source text was consumed. Not all source text needs to be consumed. Upon parse failure, ParsePosition error index is updated to
1036     * the offset of the source text which does not match the supplied format.
1037     *
1038     * @param source   The text to parse.
1039     * @param pos      On input, the position in the source to start parsing, on output, updated position.
1040     * @param calendar The calendar into which to set parsed fields.
1041     * @return true, if source has been parsed (pos parsePosition is updated); otherwise false (and pos errorIndex is updated)
1042     * @throws IllegalArgumentException when Calendar has been set to be not lenient, and a parsed field is out of range.
1043     */
1044    @Override
1045    public boolean parse(final String source, final ParsePosition pos, final Calendar calendar) {
1046        final ListIterator<StrategyAndWidth> lt = patterns.listIterator();
1047        while (lt.hasNext()) {
1048            final StrategyAndWidth strategyAndWidth = lt.next();
1049            final int maxWidth = strategyAndWidth.getMaxWidth(lt);
1050            if (!strategyAndWidth.strategy.parse(this, calendar, source, pos, maxWidth)) {
1051                return false;
1052            }
1053        }
1054        return true;
1055    }
1056
1057    /*
1058     * (non-Javadoc)
1059     *
1060     * @see org.apache.commons.lang3.time.DateParser#parseObject(String)
1061     */
1062    @Override
1063    public Object parseObject(final String source) throws ParseException {
1064        return parse(source);
1065    }
1066
1067    /*
1068     * (non-Javadoc)
1069     *
1070     * @see org.apache.commons.lang3.time.DateParser#parseObject(String, java.text.ParsePosition)
1071     */
1072    @Override
1073    public Object parseObject(final String source, final ParsePosition pos) {
1074        return parse(source, pos);
1075    }
1076
1077    // Serializing
1078    /**
1079     * Creates the object after serialization. This implementation reinitializes the transient properties.
1080     *
1081     * @param in ObjectInputStream from which the object is being deserialized.
1082     * @throws IOException            if there is an IO issue.
1083     * @throws ClassNotFoundException if a class cannot be found.
1084     */
1085    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
1086        in.defaultReadObject();
1087        final Calendar definingCalendar = Calendar.getInstance(timeZone, locale);
1088        init(definingCalendar);
1089    }
1090
1091    /**
1092     * Gets a string version of this formatter.
1093     *
1094     * @return a debugging string
1095     */
1096    @Override
1097    public String toString() {
1098        return "FastDateParser[" + pattern + ", " + locale + ", " + timeZone.getID() + "]";
1099    }
1100
1101    /**
1102     * Converts all state of this instance to a String handy for debugging.
1103     *
1104     * @return a string.
1105     * @since 3.12.0
1106     */
1107    public String toStringAll() {
1108        return "FastDateParser [pattern=" + pattern + ", timeZone=" + timeZone + ", locale=" + locale + ", century=" + century + ", startYear=" + startYear
1109                + ", patterns=" + patterns + "]";
1110    }
1111}