// Copyright 2015 The RE2 Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Original RE2 source here:
// https://github.com/google/re2/blob/master/re2/dfa.cc

package com.github.aaronshan.functions.regexp.re2j;

import com.github.aaronshan.functions.regexp.re2j.RE2.Anchor;
import com.github.aaronshan.functions.regexp.re2j.RE2.MatchKind;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

import static com.github.aaronshan.functions.regexp.re2j.DFA.NO_MATCH;
import static com.github.aaronshan.functions.regexp.re2j.RE2.Anchor.ANCHOR_START;
import static com.github.aaronshan.functions.regexp.re2j.RE2.MatchKind.FIRST_MATCH;
import static com.github.aaronshan.functions.regexp.re2j.RE2.MatchKind.LONGEST_MATCH;

/**
 * A {@link Machine} implementation using a DFA.
 */
class DFAMachine implements Machine {

    private static final int MAX_DFA_KEY = 4;

    @SuppressWarnings("unchecked")
    private final ConcurrentHashMap<DFAStateKey, DFAState>[] stateCache = new ConcurrentHashMap[MAX_DFA_KEY];
    private final AtomicInteger availableStates;
    @SuppressWarnings("unchecked")
    private final ThreadLocal<DFA>[] dfaCache = new ThreadLocal[MAX_DFA_KEY];
    private final RE2 re2;

    DFAMachine(RE2 re2, int maximumNumberOfDFAStates) {
        this.re2 = re2;
        this.availableStates = new AtomicInteger(maximumNumberOfDFAStates);

        for (int i = 0; i < MAX_DFA_KEY; ++i) {
            stateCache[i] = new ConcurrentHashMap<DFAStateKey, DFAState>();
        }

        setDfaThreadLocal(LONGEST_MATCH, true);
        setDfaThreadLocal(LONGEST_MATCH, false);
        setDfaThreadLocal(FIRST_MATCH, true);
        setDfaThreadLocal(FIRST_MATCH, false);
    }

    @Override
    public boolean match(MachineInput in, int pos, Anchor anchor, int[] submatches) {
        // Don't ask for the location if we won't use it. SearchDFA can do extra optimizations in that case.
        boolean wantMatchPosition = true;
        if (submatches.length == 0) {
            wantMatchPosition = false;
        }

        // Use DFA to find exact location of match, filter out non-matches.
        int matchStart;
        int matchEnd;
        switch (anchor) {
            case UNANCHORED:
                matchEnd = searchDFA(in, pos, in.endPos(), anchor, wantMatchPosition, re2.matchKind, false);
                if (matchEnd == NO_MATCH) {
                    return false;
                }

                // Matched. Don't care where
                if (!wantMatchPosition) {
                    return true;
                }

                // SearchDFA gives match end position but we don't know where the match started. Run the
                // regexp backwards from end position to find the longest possible match -- that's where it started.
                matchStart = searchDFA(in, pos, matchEnd, ANCHOR_START, true, LONGEST_MATCH, true);
                if (matchStart == NO_MATCH) {
                    throw new IllegalStateException("reverse DFA did not found a match");
                }

                break;
            case ANCHOR_BOTH:
            case ANCHOR_START:
                matchEnd = searchDFA(in, pos, in.endPos(), anchor, wantMatchPosition, re2.matchKind, false);
                if (matchEnd == NO_MATCH) {
                    return false;
                }
                matchStart = 0;
                break;
            default:
                throw new IllegalStateException("bad anchor");
        }

        if (submatches.length == 2) {
            submatches[0] = matchStart;
            submatches[1] = matchEnd;
        } else {
            if (!re2.nfaMachine.get().match(in, matchStart, anchor, submatches)) {
                throw new IllegalStateException("NFA inconsistency");
            }
        }

        return true;
    }

    private int searchDFA(MachineInput in, int startPos, int endPos, Anchor anchor, boolean wantMatchPosition, MatchKind matchKind, boolean reversed) {
        boolean hasCarat = reversed ? anchor.isAnchorEnd() : anchor.isAnchorStart();
        if (hasCarat && startPos != 0) {
            return NO_MATCH;
        }

        // Handle end match by running an anchored longest match and then checking if it covers all of text.
        boolean anchored = anchor.isAnchorStart();
        boolean endMatch = false;
        if (anchor.isAnchorEnd()) {
            endMatch = true;
            matchKind = LONGEST_MATCH;
        }

        // If the caller doesn't care where the match is (just whether one exists),
        // then we can stop at the very first match we find, the so-called
        // "earliest match".
        boolean wantEarliestMatch = false;
        if (!wantMatchPosition && !endMatch) {
            wantEarliestMatch = true;
            matchKind = LONGEST_MATCH;
        }

        DFA dfa = getDfa(matchKind, reversed);
        int match = dfa.search(in, startPos, endPos, anchored, wantEarliestMatch);

        if (match == NO_MATCH) {
            return NO_MATCH;
        }

        if (endMatch) {
            if ((reversed && match != startPos) || (!reversed && match != endPos)) {
                return NO_MATCH;
            }
        }

        return match;
    }

    private DFA getDfa(MatchKind matchKind, boolean reversed) {
        return dfaCache[dfaKey(matchKind, reversed)].get();
    }

    private int dfaKey(MatchKind matchKind, boolean reversed) {
        int longestInt = matchKind == LONGEST_MATCH ? 1 : 0;
        int reversedInt = reversed ? 1 : 0;
        return longestInt | (reversedInt << 1);
    }

    private void setDfaThreadLocal(final MatchKind matchKind, final boolean reversed) {
        final int dfaKey = dfaKey(matchKind, reversed);
        final Prog prog = reversed ? re2.reverseProg : re2.prog;
        dfaCache[dfaKey] = new ThreadLocal<DFA>() {
            @Override
            public DFA initialValue() {
                return new DFA(prog, matchKind, reversed, stateCache[dfaKey], availableStates);
            }
        };
    }
}
