/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.lang3.time;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.Serializable;
import java.text.DateFormatSymbols;
import java.text.ParseException;
import java.text.ParsePosition;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Comparator;
import java.util.Date;
import java.util.GregorianCalendar;
import java.util.HashMap;
import java.util.List;
import java.util.ListIterator;
import java.util.Locale;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.TimeZone;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Stream;

import org.apache.commons.lang3.CharUtils;
import org.apache.commons.lang3.LocaleUtils;
import org.apache.commons.lang3.SerializationUtils;
import org.apache.commons.lang3.StringUtils;

/**
 * FastDateParser is a fast and thread-safe version of {@link java.text.SimpleDateFormat}.
 *
 * <p>
 * To obtain a proxy to a FastDateParser, use {@link FastDateFormat#getInstance(String, TimeZone, Locale)} or another variation of the factory methods of
 * {@link FastDateFormat}.
 * </p>
 *
 * <p>
 * Since FastDateParser is thread safe, you can use a static member instance:
 * </p>
 * {@code
 *     private static final DateParser DATE_PARSER = FastDateFormat.getInstance("yyyy-MM-dd");
 * }
 *
 * <p>
 * This class can be used as a direct replacement for {@link SimpleDateFormat} in most parsing situations. This class is especially useful in multi-threaded
 * server environments. {@link SimpleDateFormat} is not thread-safe in any JDK version, nor will it be as Sun has closed the
 * <a href="https://bugs.openjdk.org/browse/JDK-4228335">bug</a>/RFE.
 * </p>
 *
 * <p>
 * Only parsing is supported by this class. Patterns are compatible with {@link SimpleDateFormat}, except for time zone extensions described below.
 * </p>
 *
 * <p>
 * The pattern {@code 'ZZ'} accepts {@code Z} for a zero offset or an ISO 8601 extended numeric offset such as {@code +08:00}. Three or more {@code 'Z'}
 * letters accept colon-separated numeric offsets in addition to the RFC822 offsets, GMT offsets, and localized time zone names accepted by a single
 * {@code 'Z'}. The patterns {@code 'z'} and a single {@code 'Z'} do not accept bare colon-separated numeric offsets.
 * </p>
 *
 * <p>
 * The class operates in lenient mode, so for example a time of 90 minutes is treated as 1 hour 30 minutes.
 * </p>
 *
 * <p>
 * Timing tests indicate this class is as about as fast as SimpleDateFormat in single thread applications and about 25% faster in multi-thread applications.
 * </p>
 *
 * @since 3.2
 * @see FastDatePrinter
 */
public class FastDateParser implements DateParser, Serializable {

    /**
     * A strategy that handles a text field in the parsing pattern
     */
    private static final class CaseInsensitiveTextStrategy extends PatternStrategy {

        private final int field;
        private final Locale locale;
        private final Map<String, Integer> lKeyValues;

        /**
         * Constructs a Strategy that parses a Text field
         *
         * @param field            The Calendar field
         * @param definingCalendar The Calendar to use
         * @param locale           The Locale to use
         */
        CaseInsensitiveTextStrategy(final int field, final Calendar definingCalendar, final Locale locale) {
            this.field = field;
            this.locale = LocaleUtils.toLocale(locale);
            final StringBuilder regex = new StringBuilder();
            regex.append("((?iu)");
            lKeyValues = appendDisplayNames(definingCalendar, locale, field, regex);
            regex.setLength(regex.length() - 1);
            regex.append(")");
            createPattern(regex);
        }

        /**
         * {@inheritDoc}
         */
        @Override
        void setCalendar(final FastDateParser parser, final Calendar calendar, final String value) {
            String lowerCase = value.toLowerCase(locale);
            Integer iVal = lKeyValues.get(lowerCase);
            if (iVal == null) {
                // match missing the optional trailing period
                iVal = lKeyValues.get(lowerCase + '.');
            }
            if (iVal == null) {
                // The regex matches case-insensitively via Unicode case folding ("(?iu)"), which is a
                // wider equivalence than the toLowerCase(locale) fold used to build the key map; retry
                // with the root-locale fold so that, for example, ASCII input under locales with
                // special casing rules still resolves to the same key.
                lowerCase = value.toLowerCase(Locale.ROOT);
                iVal = lKeyValues.get(lowerCase);
                if (iVal == null) {
                    iVal = lKeyValues.get(lowerCase + '.');
                }
            }
            if (iVal == null) {
                // Converted to a parse failure by PatternStrategy.parse instead of surfacing as an
                // undeclared NullPointerException.
                throw new IllegalArgumentException("Invalid display name for field " + field + ": '" + value + "'");
            }
            // LANG-1669: Mimic fix done in OpenJDK 17 to resolve issue with parsing newly supported day periods added in OpenJDK 16
            if (Calendar.AM_PM != this.field || iVal <= 1) {
                calendar.set(field, iVal.intValue());
            }
        }

        /**
         * Converts this instance to a handy debug string.
         *
         * @since 3.12.0
         */
        @Override
        public String toString() {
            return "CaseInsensitiveTextStrategy [field=" + field + ", locale=" + locale + ", lKeyValues=" + lKeyValues + ", pattern=" + pattern + "]";
        }
    }

    /**
     * A strategy that copies the static or quoted field in the parsing pattern
     */
    private static final class CopyQuotedStrategy extends Strategy {

        private final String formatField;

        /**
         * Constructs a Strategy that ensures the formatField has literal text
         *
         * @param formatField The literal text to match
         */
        CopyQuotedStrategy(final String formatField) {
            this.formatField = formatField;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        boolean isNumber() {
            return false;
        }

        @Override
        boolean parse(final FastDateParser parser, final Calendar calendar, final String source, final ParsePosition pos, final int maxWidth) {
            for (int idx = 0; idx < formatField.length(); ++idx) {
                final int sIdx = idx + pos.getIndex();
                if (sIdx == source.length() || formatField.charAt(idx) != source.charAt(sIdx)) {
                    pos.setErrorIndex(sIdx);
                    return false;
                }
            }
            pos.setIndex(formatField.length() + pos.getIndex());
            return true;
        }

        /**
         * Converts this instance to a handy debug string.
         *
         * @since 3.12.0
         */
        @Override
        public String toString() {
            return "CopyQuotedStrategy [formatField=" + formatField + "]";
        }
    }

    private static final class ISO8601TimeZoneStrategy extends PatternStrategy {
        // Z, +hh, -hh, +hhmm, -hhmm, +hh:mm or -hh:mm

        private static final Strategy ISO_8601_1_STRATEGY = new ISO8601TimeZoneStrategy("(Z|(?:[+-](?:2[0-3]|[01]\\d)))");

        private static final Strategy ISO_8601_2_STRATEGY = new ISO8601TimeZoneStrategy("(Z|(?:[+-](?:2[0-3]|[01]\\d)[0-5]\\d))");

        private static final Strategy ISO_8601_3_STRATEGY = new ISO8601TimeZoneStrategy("(Z|(?:[+-](?:2[0-3]|[01]\\d)(?::)[0-5]\\d))");

        /**
         * Gets the ISO 8601 time zone strategy.
         *
         * @param tokenLen A token indicating the length of the TimeZone String to be formatted.
         * @return A ISO8601TimeZoneStrategy that can format TimeZone String of length {@code tokenLen}. If no such strategy exists, an IllegalArgumentException
         *         will be thrown.
         */
        static Strategy getStrategy(final int tokenLen) {
            switch (tokenLen) {
            case 1:
                return ISO_8601_1_STRATEGY;
            case 2:
                return ISO_8601_2_STRATEGY;
            case 3:
                return ISO_8601_3_STRATEGY;
            default:
                throw new IllegalArgumentException("Invalid number of X");
            }
        }

        /**
         * Constructs a Strategy that parses a TimeZone
         *
         * @param pattern The Pattern
         */
        ISO8601TimeZoneStrategy(final String pattern) {
            createPattern(pattern);
        }

        /**
         * {@inheritDoc}
         */
        @Override
        void setCalendar(final FastDateParser parser, final Calendar calendar, final String value) {
            calendar.setTimeZone(FastTimeZone.getGmtTimeZone(value));
        }
    }

    /**
     * A strategy that handles a number field in the parsing pattern
     */
    private static class NumberStrategy extends Strategy {

        private final int field;

        /**
         * Constructs a Strategy that parses a Number field
         *
         * @param field The Calendar field
         */
        NumberStrategy(final int field) {
            this.field = field;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        boolean isNumber() {
            return true;
        }

        /**
         * Make any modifications to parsed integer
         *
         * @param parser The parser
         * @param iValue The parsed integer
         * @return The modified value
         */
        int modify(final FastDateParser parser, final int iValue) {
            return iValue;
        }

        @Override
        boolean parse(final FastDateParser parser, final Calendar calendar, final String source, final ParsePosition pos, final int maxWidth) {
            int idx = pos.getIndex();
            int last = source.length();
            if (maxWidth == 0) {
                // if no maxWidth, strip leading white space
                for (; idx < last; ++idx) {
                    final char c = source.charAt(idx);
                    if (!Character.isWhitespace(c)) {
                        break;
                    }
                }
                pos.setIndex(idx);
            } else {
                final int end = idx + maxWidth;
                if (last > end) {
                    last = end;
                }
            }
            for (; idx < last; ++idx) {
                final char c = source.charAt(idx);
                if (!Character.isDigit(c)) {
                    break;
                }
            }
            if (pos.getIndex() == idx) {
                pos.setErrorIndex(idx);
                return false;
            }
            final int value;
            try {
                value = Integer.parseInt(source.substring(pos.getIndex(), idx));
            } catch (final NumberFormatException nfe) {
                // A run of digits that overflows int cannot be represented by this field; signal a parse failure
                // rather than letting NumberFormatException escape the ParsePosition-based parse methods.
                pos.setErrorIndex(pos.getIndex());
                return false;
            }
            pos.setIndex(idx);
            calendar.set(field, modify(parser, value));
            return true;
        }

        /**
         * Converts this instance to a handy debug string.
         *
         * @since 3.12.0
         */
        @Override
        public String toString() {
            return getClass().getSimpleName() + " [field=" + field + "]";
        }
    }

    /**
     * A strategy to parse a single field from the parsing pattern
     */
    private abstract static class PatternStrategy extends Strategy {

        Pattern pattern;

        void createPattern(final String regex) {
            this.pattern = Pattern.compile(regex);
        }

        void createPattern(final StringBuilder regex) {
            createPattern(regex.toString());
        }

        /**
         * Tests whether this field is numeric. The default implementation returns false.
         *
         * @return true, if field is a number
         */
        @Override
        boolean isNumber() {
            return false;
        }

        @Override
        boolean parse(final FastDateParser parser, final Calendar calendar, final String source, final ParsePosition pos, final int maxWidth) {
            final Matcher matcher = pattern.matcher(source.substring(pos.getIndex()));
            if (!matcher.lookingAt()) {
                pos.setErrorIndex(pos.getIndex());
                return false;
            }
            try {
                setCalendar(parser, calendar, matcher.group(1));
            } catch (final IllegalArgumentException e) {
                // A matched field whose value cannot be interpreted (for example an out-of-range GMT
                // offset or a display name the key map cannot resolve) is a parse failure, reported
                // through the ParsePosition error index, not an undeclared runtime exception:
                // the public parse methods declare only ParseException.
                pos.setErrorIndex(pos.getIndex());
                return false;
            }
            pos.setIndex(pos.getIndex() + matcher.end(1));
            return true;
        }

        abstract void setCalendar(FastDateParser parser, Calendar calendar, String value);

        /**
         * Converts this instance to a handy debug string.
         *
         * @since 3.12.0
         */
        @Override
        public String toString() {
            return getClass().getSimpleName() + " [pattern=" + pattern + "]";
        }

    }

    /**
     * A strategy to parse a single field from the parsing pattern
     */
    private abstract static class Strategy {

        /**
         * Tests whether this field is numeric. The default implementation returns false.
         *
         * @return true, if field is a number
         */
        boolean isNumber() {
            return false;
        }

        abstract boolean parse(FastDateParser parser, Calendar calendar, String source, ParsePosition pos, int maxWidth);
    }

    /**
     * Holds strategy and field width
     */
    private static final class StrategyAndWidth {

        final Strategy strategy;
        final int width;

        StrategyAndWidth(final Strategy strategy, final int width) {
            this.strategy = Objects.requireNonNull(strategy, "strategy");
            this.width = width;
        }

        int getMaxWidth(final ListIterator<StrategyAndWidth> lt) {
            if (!strategy.isNumber() || !lt.hasNext()) {
                return 0;
            }
            final Strategy nextStrategy = lt.next().strategy;
            lt.previous();
            return nextStrategy.isNumber() ? width : 0;
        }

        @Override
        public String toString() {
            return "StrategyAndWidth [strategy=" + strategy + ", width=" + width + "]";
        }
    }

    /**
     * Parses the format into strategies.
     *
     * <p>
     * Instances are confined to a single {@link #init(Calendar)} invocation and never escape that invocation.
     * </p>
     */
    private final class StrategyParser {
        private final Calendar definingCalendar;
        private int currentIdx;

        StrategyParser(final Calendar definingCalendar) {
            this.definingCalendar = Objects.requireNonNull(definingCalendar, "definingCalendar");
        }

        StrategyAndWidth getNextStrategy() {
            if (currentIdx >= pattern.length()) {
                return null;
            }
            final char c = pattern.charAt(currentIdx);
            if (CharUtils.isAsciiAlpha(c)) {
                return letterPattern(c);
            }
            return literal();
        }

        private StrategyAndWidth letterPattern(final char c) {
            final int begin = currentIdx;
            while (++currentIdx < pattern.length()) {
                if (pattern.charAt(currentIdx) != c) {
                    break;
                }
            }
            final int width = currentIdx - begin;
            return new StrategyAndWidth(getStrategy(c, width, definingCalendar), width);
        }

        private StrategyAndWidth literal() {
            boolean activeQuote = false;
            final StringBuilder sb = new StringBuilder();
            while (currentIdx < pattern.length()) {
                final char c = pattern.charAt(currentIdx);
                if (!activeQuote && CharUtils.isAsciiAlpha(c)) {
                    break;
                }
                if (c == '\'' && (++currentIdx == pattern.length() || pattern.charAt(currentIdx) != '\'')) {
                    activeQuote = !activeQuote;
                    continue;
                }
                ++currentIdx;
                sb.append(c);
            }
            if (activeQuote) {
                throw new IllegalArgumentException("Unterminated quote");
            }
            final String formatField = sb.toString();
            return new StrategyAndWidth(new CopyQuotedStrategy(formatField), formatField.length());
        }
    }

    /**
     * A strategy that handles a time zone field in the parsing pattern
     */
    static class TimeZoneStrategy extends PatternStrategy {

        private static final class TzInfo {
            final TimeZone zone;
            final int dstOffset;

            TzInfo(final TimeZone tz, final boolean useDst) {
                zone = tz;
                dstOffset = useDst ? tz.getDSTSavings() : 0;
            }

            @Override
            public String toString() {
                return "TzInfo [zone=" + zone + ", dstOffset=" + dstOffset + "]";
            }
        }

        // The RFC 822 numeric offset form "+hhmm"; SimpleDateFormat rejects "+hh:mm" here, and so must 'z'.
        private static final String RFC_822_TIME_ZONE = "[+-](?:2[0-3]|[01]\\d)[0-5]\\d";

        /**
         * Same as {@link #RFC_822_TIME_ZONE} but also accepts the ISO 8601 extended form {@code "+hh:mm"}.
         */
        private static final String ISO_8601_EXTENDED_TIME_ZONE = "[+-](?:2[0-3]|[01]\\d):?[0-5]\\d";

        /**
         * Cache of {@link TimeZoneStrategy} instances that accept the ISO 8601 extended form, keyed by locale. Kept separate from the field caches because 'z'
         * (and 'Z' with a single letter) must keep exact SimpleDateFormat parity and reject the extended form.
         */
        private static final ConcurrentMap<Locale, Strategy> ISO_EXTENDED_ZONE_CACHE = new ConcurrentHashMap<>(3);

        private static final String GMT_OPTION = TimeZones.GMT_ID + "[+-]\\d{1,2}:\\d{2}";

        /**
         * Index of zone id from {@link DateFormatSymbols#getZoneStrings()}.
         */
        private static final int ID = 0;

        static void clearIsoExtendedCache() {
            ISO_EXTENDED_ZONE_CACHE.clear();
        }

        /**
         * Gets a {@link TimeZoneStrategy} that also parses the ISO 8601 extended offset form {@code "+hh:mm"}.
         *
         * @param locale The Locale.
         * @return A shared strategy instance for the given Locale.
         */
        static Strategy getIsoExtendedStrategy(final Locale locale) {
            return ISO_EXTENDED_ZONE_CACHE.computeIfAbsent(LocaleUtils.toLocale(locale), k -> new TimeZoneStrategy(k, true));
        }

        /**
         * Tests whether to skip the given time zone, true if TimeZone.getTimeZone().
         * <p>
         * On Java 25 and up, skips short IDs if {@code ignoreTimeZoneShortIDs} is true.
         * </p>
         * <p>
         * This method is package private only for testing.
         * </p>
         *
         * @param tzId The ID to test.
         * @return Whether to skip the given time zone ID.
         */
        static boolean skipTimeZone(final String tzId) {
            return tzId.equalsIgnoreCase(TimeZones.GMT_ID);
        }

        private final Locale locale;

        /**
         * Using lower case only or upper case only will cause problems with some Locales like Turkey, Armenia, Colognian and also depending on the Java
         * version. For details, see https://garygregory.wordpress.com/2015/11/03/java-lowercase-conversion-turkey/
         */
        private final Map<String, TzInfo> tzNames = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

        /**
         * Constructs a Strategy that parses a TimeZone.
         *
         * @param locale           The Locale.
         * @param iso8601Extended Whether to also accept the ISO 8601 extended offset form {@code "+hh:mm"} that FastDatePrinter emits for three or more 'Z'
         *                        pattern letters.
         */
        TimeZoneStrategy(final Locale locale, final boolean iso8601Extended) {
            this.locale = LocaleUtils.toLocale(locale);
            final StringBuilder sb = new StringBuilder();
            sb.append("((?iu)" + (iso8601Extended ? ISO_8601_EXTENDED_TIME_ZONE : RFC_822_TIME_ZONE) + "|" + GMT_OPTION);
            final Set<String> sorted = new TreeSet<>(LONGER_FIRST_LOWERCASE);
            // Order is undefined.
            // TODO Use of getZoneStrings() is discouraged per its Javadoc.
            final String[][] zones = DateFormatSymbols.getInstance(locale).getZoneStrings();
            for (final String[] zoneNames : zones) {
                // offset 0 is the time zone ID and is not localized
                final String tzId = zoneNames[ID];
                if (skipTimeZone(tzId)) {
                    continue;
                }
                final TimeZone tz = TimeZones.getTimeZone(tzId);
                // offset 1 is long standard name
                // offset 2 is short standard name
                final TzInfo standard = new TzInfo(tz, false);
                TzInfo tzInfo = standard;
                for (int i = 1; i < zoneNames.length; ++i) {
                    switch (i) {
                    case 3: // offset 3 is long daylight savings (or summertime) name
                            // offset 4 is the short summertime name
                        tzInfo = new TzInfo(tz, true);
                        break;
                    case 5: // offset 5 starts additional names, probably standard time
                        tzInfo = standard;
                        break;
                    default:
                        break;
                    }
                    final String zoneName = zoneNames[i];
                    // ignore the data associated with duplicates supplied in the additional names
                    if (zoneName != null && sorted.add(zoneName)) {
                        tzNames.put(zoneName, tzInfo);
                    }
                }
            }
            // Order is undefined.
            for (final String tzId : TimeZones.SORTED_AVAILABLE_IDS) {
                if (skipTimeZone(tzId)) {
                    continue;
                }
                final TimeZone tz = TimeZones.getTimeZone(tzId);
                final String zoneName = tz.getDisplayName(locale);
                if (sorted.add(zoneName)) {
                    tzNames.put(zoneName, new TzInfo(tz, tz.observesDaylightTime()));
                }
            }
            // order the regex alternatives with longer strings first, greedy
            // match will ensure the longest string will be consumed
            sorted.forEach(zoneName -> simpleQuote(sb.append('|'), zoneName));
            sb.append(")");
            createPattern(sb);
        }

        /**
         * {@inheritDoc}
         */
        @Override
        void setCalendar(final FastDateParser parser, final Calendar calendar, final String timeZone) {
            final TimeZone tz = FastTimeZone.getGmtTimeZone(timeZone);
            if (tz != null) {
                calendar.setTimeZone(tz);
            } else {
                TzInfo tzInfo = tzNames.get(timeZone);
                if (tzInfo == null) {
                    // match missing the optional trailing period
                    tzInfo = tzNames.get(timeZone + '.');
                    if (tzInfo == null) {
                        // Converted to a parse failure by PatternStrategy.parse instead of surfacing as an
                        // undeclared IllegalStateException; the message is bounded by the matched input
                        // (no dump of the entire time zone name table).
                        throw new IllegalArgumentException(
                                String.format("Can't find time zone '%s' (%d chars)", timeZone, timeZone.length()));
                    }
                }
                calendar.set(Calendar.DST_OFFSET, tzInfo.dstOffset);
                calendar.set(Calendar.ZONE_OFFSET, tzInfo.zone.getRawOffset());
            }
        }

        /**
         * Converts this instance to a handy debug string.
         *
         * @since 3.12.0
         */
        @Override
        public String toString() {
            return "TimeZoneStrategy [locale=" + locale + ", tzNames=" + tzNames + ", pattern=" + pattern + "]";
        }

    }

    /**
     * A write-through recorder used while parsing a pattern that contains a week year ('Y'). Every mutation is delegated to the real target calendar
     * unchanged, and the raw values assigned to the three week-date fields are additionally captured, so that after all fields are parsed the week date can
     * be resolved from exactly what was parsed - mirroring {@code java.text.CalendarBuilder}, which {@link java.text.SimpleDateFormat} uses for the same
     * purpose. (Reading the values back from the calendar instead would normalize them: {@link Calendar#get(int)} resolves the complete date, so a parsed
     * week 53 read back through a calendar-year interpretation can roll the year and land a full year away.)
     */
    private static final class WeekDateRecorder extends GregorianCalendar {

        private static final long serialVersionUID = 1L;

        /** The calendar every mutation is delegated to. */
        private final Calendar target;

        private transient int weekYearValue;
        private transient boolean weekYearSet;
        private transient int weekOfYearValue;
        private transient boolean weekOfYearSet;
        private transient int dayOfWeekValue;
        private transient boolean dayOfWeekSet;

        WeekDateRecorder(final Calendar target) {
            this.target = target;
        }

        /**
         * Resolves the recorded week year through the target calendar's week-date machinery. The parsed 'Y' value was delegated into {@link Calendar#YEAR}
         * by the number strategy; {@link Calendar#setWeekDate(int, int, int)} reinterprets it as a week year together with the parsed week of year and day
         * of week, defaulting to week 1 and the calendar's first day-of-week when the pattern did not contain them (the same defaults as
         * {@code java.text.CalendarBuilder}). The fields set by {@code setWeekDate} take precedence over any month/day fields parsed earlier, which matches
         * {@link java.text.SimpleDateFormat}.
         */
        void applyWeekDate() {
            if (!weekYearSet) {
                return;
            }
            int weekOfYear = weekOfYearSet ? weekOfYearValue : 1;
            int dayOfWeek = dayOfWeekSet ? dayOfWeekValue : target.getFirstDayOfWeek();
            if (!isValidDayOfWeek(dayOfWeek) && target.isLenient()) {
                // Calendar.setWeekDate rejects a day of week outside SUNDAY..SATURDAY even on a lenient calendar, so fold the overflow of an
                // out-of-range 'u' value into the week number first, exactly as java.text.CalendarBuilder does for SimpleDateFormat.
                if (dayOfWeek >= 8) {
                    dayOfWeek--;
                    weekOfYear += dayOfWeek / 7;
                    dayOfWeek = dayOfWeek % 7 + 1;
                } else {
                    while (dayOfWeek <= 0) {
                        dayOfWeek += 7;
                        weekOfYear--;
                    }
                }
                dayOfWeek = toCalendarDayOfWeek(dayOfWeek);
            }
            target.setWeekDate(weekYearValue, weekOfYear, dayOfWeek);
        }

        @Override
        public void set(final int field, final int value) {
            if (target == null) {
                // Callers from the superclass constructors, before this recorder is fully constructed.
                super.set(field, value);
                return;
            }
            switch (field) {
            case Calendar.YEAR:
                weekYearValue = value;
                weekYearSet = true;
                break;
            case Calendar.WEEK_OF_YEAR:
                weekOfYearValue = value;
                weekOfYearSet = true;
                break;
            case Calendar.DAY_OF_WEEK:
                dayOfWeekValue = value;
                dayOfWeekSet = true;
                break;
            default:
                break;
            }
            target.set(field, value);
        }

        @Override
        public void setTimeZone(final TimeZone zone) {
            if (target == null) {
                // Callers from the superclass constructors, before this recorder is fully constructed.
                super.setTimeZone(zone);
                return;
            }
            target.setTimeZone(zone);
        }
    }

    /**
     * Required for serialization support.
     *
     * @see java.io.Serializable
     */
    private static final long serialVersionUID = 3L;

    static final Locale JAPANESE_IMPERIAL = new Locale("ja", "JP", "JP");

    // helper classes to parse the format string

    /**
     * comparator used to sort regex alternatives. Alternatives should be ordered longer first, and shorter last. ('february' before 'feb'). All entries must be
     * lower-case by locale.
     */
    private static final Comparator<String> LONGER_FIRST_LOWERCASE = Comparator.reverseOrder();

    @SuppressWarnings("unchecked") // OK because we are creating an array with no entries
    private static final ConcurrentMap<Locale, Strategy>[] CACHES = new ConcurrentMap[Calendar.FIELD_COUNT];

    private static final Strategy ABBREVIATED_YEAR_STRATEGY = new NumberStrategy(Calendar.YEAR) {

        /**
         * {@inheritDoc}
         */
        @Override
        int modify(final FastDateParser parser, final int iValue) {
            return iValue < 100 ? parser.adjustYear(iValue) : iValue;
        }
    };

    private static final Strategy NUMBER_MONTH_STRATEGY = new NumberStrategy(Calendar.MONTH) {
        @Override
        int modify(final FastDateParser parser, final int iValue) {
            return iValue - 1;
        }
    };

    private static final Strategy LITERAL_YEAR_STRATEGY = new NumberStrategy(Calendar.YEAR);

    private static final Strategy WEEK_OF_YEAR_STRATEGY = new NumberStrategy(Calendar.WEEK_OF_YEAR);

    private static final Strategy WEEK_OF_MONTH_STRATEGY = new NumberStrategy(Calendar.WEEK_OF_MONTH);

    private static final Strategy DAY_OF_YEAR_STRATEGY = new NumberStrategy(Calendar.DAY_OF_YEAR);

    private static final Strategy DAY_OF_MONTH_STRATEGY = new NumberStrategy(Calendar.DAY_OF_MONTH);

    private static final Strategy DAY_OF_WEEK_STRATEGY = new NumberStrategy(Calendar.DAY_OF_WEEK) {
        @Override
        int modify(final FastDateParser parser, final int iValue) {
            return toCalendarDayOfWeek(iValue);
        }
    };

    private static final Strategy DAY_OF_WEEK_IN_MONTH_STRATEGY = new NumberStrategy(Calendar.DAY_OF_WEEK_IN_MONTH);

    private static final Strategy HOUR_OF_DAY_STRATEGY = new NumberStrategy(Calendar.HOUR_OF_DAY);

    private static final Strategy HOUR24_OF_DAY_STRATEGY = new NumberStrategy(Calendar.HOUR_OF_DAY) {
        @Override
        int modify(final FastDateParser parser, final int iValue) {
            return iValue == 24 ? 0 : iValue;
        }
    };

    private static final Strategy HOUR12_STRATEGY = new NumberStrategy(Calendar.HOUR) {
        @Override
        int modify(final FastDateParser parser, final int iValue) {
            return iValue == 12 ? 0 : iValue;
        }
    };

    private static final Strategy HOUR_STRATEGY = new NumberStrategy(Calendar.HOUR);

    private static final Strategy MINUTE_STRATEGY = new NumberStrategy(Calendar.MINUTE);

    private static final Strategy SECOND_STRATEGY = new NumberStrategy(Calendar.SECOND);

    private static final Strategy MILLISECOND_STRATEGY = new NumberStrategy(Calendar.MILLISECOND);

    /**
     * Gets the short and long values displayed for a field
     *
     * @param calendar The calendar to obtain the short and long values
     * @param locale   The locale of display names
     * @param field    The field of interest
     * @param regex    The regular expression to build
     * @return The map of string display names to field values
     */
    private static Map<String, Integer> appendDisplayNames(final Calendar calendar, final Locale locale, final int field, final StringBuilder regex) {
        Objects.requireNonNull(calendar, "calendar");
        final Map<String, Integer> values = new HashMap<>();
        final Locale actualLocale = LocaleUtils.toLocale(locale);
        final Map<String, Integer> displayNames = calendar.getDisplayNames(field, Calendar.ALL_STYLES, actualLocale);
        final TreeSet<String> sorted = new TreeSet<>(LONGER_FIRST_LOWERCASE);
        displayNames.forEach((k, v) -> {
            final String keyLc = k.toLowerCase(actualLocale);
            if (sorted.add(keyLc)) {
                values.put(keyLc, v);
            }
        });
        sorted.forEach(symbol -> simpleQuote(regex, symbol).append('|'));
        return values;
    }

    /**
     * Clears the cache.
     */
    static void clear() {
        Stream.of(CACHES).filter(Objects::nonNull).forEach(ConcurrentMap::clear);
        TimeZoneStrategy.clearIsoExtendedCache();
    }

    /**
     * Gets a cache of Strategies for a particular field
     *
     * @param field The Calendar field
     * @return A cache of Locale to Strategy
     */
    private static ConcurrentMap<Locale, Strategy> getCache(final int field) {
        synchronized (CACHES) {
            if (CACHES[field] == null) {
                CACHES[field] = new ConcurrentHashMap<>(3);
            }
            return CACHES[field];
        }
    }

    /**
     * Tests whether a value is a valid {@link Calendar#DAY_OF_WEEK} value, in the range {@link Calendar#SUNDAY} to {@link Calendar#SATURDAY}.
     *
     * @param dayOfWeek the value to test.
     * @return true if the value is in range.
     */
    private static boolean isValidDayOfWeek(final int dayOfWeek) {
        return dayOfWeek >= Calendar.SUNDAY && dayOfWeek <= Calendar.SATURDAY;
    }

    private static StringBuilder simpleQuote(final StringBuilder sb, final String value) {
        for (int i = 0; i < value.length(); ++i) {
            final char c = value.charAt(i);
            switch (c) {
            case '\\':
            case '^':
            case '$':
            case '.':
            case '|':
            case '?':
            case '*':
            case '+':
            case '(':
            case ')':
            case '[':
            case '{':
                sb.append('\\');
                // falls-through
            default:
                sb.append(c);
            }
        }
        if (sb.charAt(sb.length() - 1) == '.') {
            // trailing '.' is optional
            sb.append('?');
        }
        return sb;
    }

    /**
     * Converts an ISO 8601 day number of week ('u', Monday = 1 to Sunday = 7) to a {@link Calendar#DAY_OF_WEEK} value.
     *
     * <p>
     * An out-of-range value is returned unchanged so a lenient calendar can adjust it, as {@code java.text.CalendarBuilder} does for
     * {@link java.text.SimpleDateFormat}.
     * </p>
     *
     * @param isoDayOfWeek the parsed ISO day number of week.
     * @return the {@link Calendar#DAY_OF_WEEK} value, or the input when it is out of range.
     */
    private static int toCalendarDayOfWeek(final int isoDayOfWeek) {
        if (!isValidDayOfWeek(isoDayOfWeek)) {
            return isoDayOfWeek;
        }
        return isoDayOfWeek == 7 ? Calendar.SUNDAY : isoDayOfWeek + 1;
    }

    /** Input pattern. */
    private final String pattern;

    /** Input TimeZone. */
    private final TimeZone timeZone;

    /** Input Locale. */
    private final Locale locale;

    /**
     * Century from Date.
     */
    private final int century;

    /**
     * Start year from Date.
     */
    private final int startYear;

    /** Initialized from Calendar. */
    private transient List<StrategyAndWidth> patterns;

    /**
     * Whether the pattern contains a week-year field ('Y'). Derived from the pattern in {@link #init(Calendar)} (called from the constructor and from
     * readObject), so it does not need to be serialized.
     */
    private transient volatile boolean weekYear;

    /**
     * Constructs a new FastDateParser.
     *
     * Use {@link FastDateFormat#getInstance(String, TimeZone, Locale)} or another variation of the factory methods of {@link FastDateFormat} to get a cached
     * FastDateParser instance.
     *
     * @param pattern  non-null {@link java.text.SimpleDateFormat} compatible pattern
     * @param timeZone non-null time zone to use
     * @param locale   non-null locale
     */
    protected FastDateParser(final String pattern, final TimeZone timeZone, final Locale locale) {
        this(pattern, timeZone, locale, null);
    }

    /**
     * Constructs a new FastDateParser.
     *
     * @param pattern      non-null {@link java.text.SimpleDateFormat} compatible pattern
     * @param timeZone     non-null time zone to use
     * @param locale       locale, null maps to the default Locale.
     * @param centuryStart The start of the century for 2 digit year parsing
     * @since 3.5
     */
    protected FastDateParser(final String pattern, final TimeZone timeZone, final Locale locale, final Date centuryStart) {
        this.pattern = Objects.requireNonNull(pattern, "pattern");
        // TimeZone is mutable and instances are shared through the FastDateFormat cache.
        this.timeZone = (TimeZone) Objects.requireNonNull(timeZone, "timeZone").clone();
        this.locale = LocaleUtils.toLocale(locale);
        final Calendar definingCalendar = Calendar.getInstance(timeZone, this.locale);
        final int centuryStartYear;
        if (centuryStart != null) {
            definingCalendar.setTime(centuryStart);
            centuryStartYear = definingCalendar.get(Calendar.YEAR);
        } else if (this.locale.equals(JAPANESE_IMPERIAL)) {
            centuryStartYear = 0;
        } else {
            // from 80 years ago to 20 years from now
            definingCalendar.setTime(new Date());
            centuryStartYear = definingCalendar.get(Calendar.YEAR) - 80;
        }
        century = centuryStartYear / 100 * 100;
        startYear = centuryStartYear - century;
        init(definingCalendar);
    }

    /**
     * Adjusts dates to be within appropriate century
     *
     * @param twoDigitYear The year to adjust
     * @return A value between centuryStart(inclusive) to centuryStart+100(exclusive)
     */
    private int adjustYear(final int twoDigitYear) {
        final int trial = century + twoDigitYear;
        return twoDigitYear >= startYear ? trial : trial + 100;
    }

    private boolean checkLength(final String source, final ParsePosition pos) {
        final int startIndex = pos.getIndex();
        if (startIndex > source.length()) {
            pos.setErrorIndex(startIndex);
            return false;
        }
        return true;
    }

    /**
     * Compares another object for equality with this object.
     *
     * @param obj The object to compare to
     * @return {@code true}if equal to this instance
     */
    @Override
    public boolean equals(final Object obj) {
        if (!(obj instanceof FastDateParser)) {
            return false;
        }
        final FastDateParser other = (FastDateParser) obj;
        return pattern.equals(other.pattern) && timeZone.equals(other.timeZone) && locale.equals(other.locale);
    }

    /*
     * (non-Javadoc)
     *
     * @see org.apache.commons.lang3.time.DateParser#getLocale()
     */
    @Override
    public Locale getLocale() {
        return locale;
    }

    /**
     * Gets a strategy that parses a text field.
     *
     * @param field            The Calendar field
     * @param definingCalendar The calendar to obtain the short and long values
     * @return A TextStrategy for the field and Locale
     */
    private Strategy getLocaleSpecificStrategy(final int field, final Calendar definingCalendar) {
        return getCache(field).computeIfAbsent(locale,
                k -> field == Calendar.ZONE_OFFSET ? new TimeZoneStrategy(locale, false)
                        : new CaseInsensitiveTextStrategy(field, definingCalendar, locale));
    }

    /*
     * (non-Javadoc)
     *
     * @see org.apache.commons.lang3.time.DateParser#getPattern()
     */
    @Override
    public String getPattern() {
        return pattern;
    }

    List<StrategyAndWidth> getPatterns() {
        return patterns;
    }

    /**
     * Gets a Strategy given a field from a SimpleDateFormat pattern
     *
     * @param f                A sub-sequence of the SimpleDateFormat pattern
     * @param width            formatting width
     * @param definingCalendar The calendar to obtain the short and long values
     * @return The Strategy that will handle parsing for the field
     */
    private Strategy getStrategy(final char f, final int width, final Calendar definingCalendar) {
        switch (f) {
        case 'D':
            return DAY_OF_YEAR_STRATEGY;
        case 'E':
            return getLocaleSpecificStrategy(Calendar.DAY_OF_WEEK, definingCalendar);
        case 'F':
            return DAY_OF_WEEK_IN_MONTH_STRATEGY;
        case 'G':
            return getLocaleSpecificStrategy(Calendar.ERA, definingCalendar);
        case 'H': // Hour in day (0-23)
            return HOUR_OF_DAY_STRATEGY;
        case 'K': // Hour in am/pm (0-11)
            return HOUR_STRATEGY;
        case 'M':
        case 'L':
            return width >= 3 ? getLocaleSpecificStrategy(Calendar.MONTH, definingCalendar) : NUMBER_MONTH_STRATEGY;
        case 'S':
            return MILLISECOND_STRATEGY;
        case 'W':
            return WEEK_OF_MONTH_STRATEGY;
        case 'a':
            return getLocaleSpecificStrategy(Calendar.AM_PM, definingCalendar);
        case 'd':
            return DAY_OF_MONTH_STRATEGY;
        case 'h': // Hour in am/pm (1-12), i.e. midday/midnight is 12, not 0
            return HOUR12_STRATEGY;
        case 'k': // Hour in day (1-24), i.e. midnight is 24, not 0
            return HOUR24_OF_DAY_STRATEGY;
        case 'm':
            return MINUTE_STRATEGY;
        case 's':
            return SECOND_STRATEGY;
        case 'u':
            return DAY_OF_WEEK_STRATEGY;
        case 'w':
            return WEEK_OF_YEAR_STRATEGY;
        case 'y':
            return width > 2 ? LITERAL_YEAR_STRATEGY : ABBREVIATED_YEAR_STRATEGY;
        case 'Y':
            // Week year: the number is parsed like a year (including the two-digit-century adjustment,
            // as SimpleDateFormat does for 'YY'), but it must be resolved through the calendar's
            // week-date machinery rather than Calendar.YEAR. Record that this pattern contains a week
            // year; parse(String, ParsePosition, Calendar) re-resolves the date via setWeekDate,
            // mirroring FastDatePrinter's WeekYear rule and java.text.CalendarBuilder. When the
            // calendar does not support week dates, the value falls back to Calendar.YEAR, exactly
            // like FastDatePrinter's fallback.
            weekYear = true;
            return width > 2 ? LITERAL_YEAR_STRATEGY : ABBREVIATED_YEAR_STRATEGY;
        case 'X':
            return ISO8601TimeZoneStrategy.getStrategy(width);
        case 'Z':
            if (width == 2) {
                return ISO8601TimeZoneStrategy.ISO_8601_3_STRATEGY;
            }
            if (width >= 3) {
                // FastDatePrinter formats three or more 'Z' as the ISO 8601 extended offset "+hh:mm", so parsing
                // 'Z' must accept that form as well. 'z' keeps exact SimpleDateFormat parity and rejects it.
                return TimeZoneStrategy.getIsoExtendedStrategy(locale);
            }
            // falls-through
        case 'z':
            return getLocaleSpecificStrategy(Calendar.ZONE_OFFSET, definingCalendar);
        default:
            throw new IllegalArgumentException("Format '" + f + "' not supported");
        }
    }

    /*
     * (non-Javadoc)
     *
     * @see org.apache.commons.lang3.time.DateParser#getTimeZone()
     */
    @Override
    public TimeZone getTimeZone() {
        return (TimeZone) timeZone.clone();
    }

    /**
     * Returns a hash code compatible with equals.
     *
     * @return A hash code compatible with equals
     */
    @Override
    public int hashCode() {
        return pattern.hashCode() + 13 * (timeZone.hashCode() + 13 * locale.hashCode());
    }

    /**
     * Initializes derived fields from defining fields. This is called from constructor and from readObject (de-serialization)
     *
     * @param definingCalendar The {@link java.util.Calendar} instance used to initialize this FastDateParser
     */
    private void init(final Calendar definingCalendar) {
        patterns = new ArrayList<>();

        final StrategyParser strategyParser = new StrategyParser(definingCalendar);
        for (;;) {
            final StrategyAndWidth field = strategyParser.getNextStrategy();
            if (field == null) {
                break;
            }
            patterns.add(field);
        }
    }

    /*
     * (non-Javadoc)
     *
     * @see org.apache.commons.lang3.time.DateParser#parse(String)
     */
    @Override
    public Date parse(final String source) throws ParseException {
        final ParsePosition pp = new ParsePosition(0);
        final Date date = parse(source, pp);
        if (date == null) {
            // Add a note regarding supported date range
            final int errorIndex = pp.getErrorIndex();
            final String msg = String.format("Unparseable date: '%s', parse position = %s", source, pp);
            if (locale.equals(JAPANESE_IMPERIAL)) {
                throw new ParseException(String.format("%s; the %s locale does not support dates before 1868-01-01.", msg, locale), errorIndex);
            }
            throw new ParseException(msg, errorIndex);
        }
        return date;
    }

    /**
     * This implementation updates the ParsePosition if the parse succeeds. However, it sets the error index to the position before the failed field unlike the
     * method {@link java.text.SimpleDateFormat#parse(String, ParsePosition)} which sets the error index to after the failed field.
     * <p>
     * To determine if the parse has succeeded, the caller must check if the current parse position given by {@link ParsePosition#getIndex()} has been updated.
     * If the input buffer has been fully parsed, then the index will point to just after the end of the input buffer.
     * </p>
     *
     * @see org.apache.commons.lang3.time.DateParser#parse(String, java.text.ParsePosition)
     */
    @Override
    public Date parse(final String source, final ParsePosition pos) {
        if (!checkLength(source, pos)) {
            return null;
        }
        // timing tests indicate getting new instance is 19% faster than cloning
        final Calendar cal = Calendar.getInstance(timeZone, locale);
        cal.clear();
        return parse(source, pos, cal) ? cal.getTime() : null;
    }

    /**
     * Parses a formatted date string according to the format. Updates the Calendar with parsed fields. Upon success, the ParsePosition index is updated to
     * 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
     * the offset of the source text which does not match the supplied format.
     *
     * @param source   The text to parse.
     * @param pos      On input, the position in the source to start parsing, on output, updated position.
     * @param calendar The calendar into which to set parsed fields.
     * @return true, if source has been parsed (pos parsePosition is updated); otherwise false (and pos errorIndex is updated)
     * @throws IllegalArgumentException Thrown when Calendar has been set to be not lenient, and a parsed field is out of range.
     */
    @Override
    public boolean parse(final String source, final ParsePosition pos, final Calendar calendar) {
        if (!checkLength(source, pos)) {
            return false;
        }
        final WeekDateRecorder recorder = weekYear && calendar.isWeekDateSupported() ? new WeekDateRecorder(calendar) : null;
        final Calendar sink = recorder != null ? recorder : calendar;
        final ListIterator<StrategyAndWidth> lt = patterns.listIterator();
        while (lt.hasNext()) {
            final StrategyAndWidth strategyAndWidth = lt.next();
            final int maxWidth = strategyAndWidth.getMaxWidth(lt);
            if (!strategyAndWidth.strategy.parse(this, sink, source, pos, maxWidth)) {
                return false;
            }
        }
        if (recorder != null) {
            recorder.applyWeekDate();
        }
        return true;
    }

    /*
     * (non-Javadoc)
     *
     * @see org.apache.commons.lang3.time.DateParser#parseObject(String)
     */
    @Override
    public Object parseObject(final String source) throws ParseException {
        return parse(source);
    }

    /*
     * (non-Javadoc)
     *
     * @see org.apache.commons.lang3.time.DateParser#parseObject(String, java.text.ParsePosition)
     */
    @Override
    public Object parseObject(final String source, final ParsePosition pos) {
        return parse(source, pos);
    }

    /**
     * Creates the object after serialization. This implementation reinitializes the transient properties.
     *
     * @param in ObjectInputStream from which the object is being deserialized.
     * @throws IOException            Thrown if there is an IO issue.
     * @throws ClassNotFoundException Thrown if a class cannot be found.
     */
    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        SerializationUtils.requireNonNull(pattern, "pattern null");
        SerializationUtils.requireNonNull(timeZone, "timeZone null");
        init(Calendar.getInstance(timeZone, locale));
    }

    /**
     * Gets a string version of this formatter.
     *
     * @return A debugging string
     */
    @Override
    public String toString() {
        return "FastDateParser[" + pattern + ", " + locale + ", " + timeZone.getID() + "]";
    }


    /**
     * Converts all state of this instance to a String handy for debugging.
     *
     * @return A string.
     * @since 3.12.0
     */
    public String toStringAll() {
        return "FastDateParser [pattern=" + pattern + ", timeZone=" + timeZone + ", locale=" + locale + ", century=" + century + ", startYear=" + startYear
                + ", patterns=" + StringUtils.join(patterns, ", " + System.lineSeparator() + "\t") + "]";
    }
}