/*
* Copyright 2014 Basis Technology Corp.
*
* Licensed 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
*
* http://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 com.basistech.tclre;

import java.util.Arrays;
import java.util.EnumSet;
import java.util.List;

import com.google.common.collect.Lists;

/**
 * The internal implementation of matching.
 */
class Runtime {
    private static final int UNTRIED = 0;   /* not yet tried at all */
    private static final int TRYING = 1;    /* top matched, trying submatches */
    private static final int TRIED = 2;     /* top didn't match or submatches exhausted */

    Guts g;
    int eflags;
    List<RegMatch> match;
    CharSequence data;
    int dataLength; // cache this, it gets examined _a lot_.
    private HsrePattern re;
    private int[] mem; // backtracking.

    /**
     * exec - match regular expression
     */
    boolean exec(HsrePattern re, CharSequence data, EnumSet<ExecFlags> execFlags) throws RegexException {
    /* sanity checks */
    /* setup */


        if (0 != (re.guts.info & Flags.REG_UIMPOSSIBLE)) {
            throw new RegexException("Regex marked impossible");
        }

        eflags = 0;
        for (ExecFlags ef : execFlags) {
            switch (ef) {
            case NOTBOL:
                eflags |= Flags.REG_NOTBOL;
                break;
            case NOTEOL:
                eflags |= Flags.REG_NOTEOL;
                break;
            case LOOKING_AT:
                eflags |= Flags.REG_LOOKING_AT;
                break;
            default:
                throw new RuntimeException("impossible exec flag");
            }
        }

        this.re = re;
        this.g = re.guts;
        this.data = data;
        this.dataLength = this.data.length();
        if (this.match != null) {
            this.match.clear();
        } else {
            this.match = Lists.newArrayList();
        }
        match.add(null); // make room for 1.
        if (0 != (g.info & Flags.REG_UBACKREF)) {
            while (match.size() < g.nsub + 1) {
                match.add(null);
            }
        }
        if (mem != null && mem.length >= g.ntree) {
            Arrays.fill(mem, 0);
        } else {
            mem = new int[g.ntree];
        }
       
    /* do it */
        assert g.tree != null;

        if (0 != (g.info & Flags.REG_UBACKREF)) {
            return cfind(g.tree.machine);
        } else {
            return find(g.tree.machine);
        }
    }

    /**
     * find - find a match for the main NFA (no-complications case)
     * <p>
     * First, it runs the 'search machine' in non-greedy mode (shortest). The 'search machine' is the NFA with
     * .* added to the front and the back, more or less. See 'makesearch'. In many cases, running the search machine
     * 'shortest' is considerably faster than running the actual regular expression in greedy (longest). So,
     * even though this may seem like it would take extra time doing an extra scan, the alternative is much slower.
     * The search machine tells you if the expression can be found anywhere, and, if so, where is the furthest possible
     * end.
     * </p>
     * <p>
     * If the search machine succeeds, the does an iteration to find the exact bounds;
     * the loop uses 'longest' or 'shortest' as appropriate to the flags. In C, there was an option to
     * _only_ run the search machine and return a simple boolean with no bounds.
     * We have no API for that via an ExecFlag.
     * </p>
     * <p>
     * If the top-level API call is 'lookingAt', we never want to scan down the data looking for matches. But 'shortest'
     * can still be much faster than 'longest'. So, the code runs the original machine first. If non-greedy expressions
     * were very common, I suppose that it would be faster to omit this step in that case. Thereafter, the loop has
     * a check to bail if these is no match at the beginning of the data, which is the constraint of lookingAt.
     * </p>
     *
     */
    boolean find(Cnfa cnfa) {
        int begin;
        int end = -1;
        int cold;
        int open;       /* open and close of range of possible starts */
        int close;
        boolean hitend;
        boolean shorter = 0 != (g.tree.flags & Subre.SHORTER);
        boolean lookingAt = 0 != (eflags & Flags.REG_LOOKING_AT);
        int[] coldp = new int[1];
        Dfa d = new Dfa(this, cnfa);

        if (lookingAt) {
            /*
             * shortest is faster than longest. So, we want to check with it.
             * However, since we aren't making a 'search re' with an extra .* on
             * the front, we don't add an extra requirement to make progress on the
             * very first arc. If the expression has something like a* at the front,
             * it can 'no-progress' consuming the a characters.
             * All of this casts doubts on the 'requireInitialProgress' feature -- at all.
             * These initial calls to shortest should be all the opportunity we need
             * to do 'lookingAt'.
             */
            close = d.shortest(0, 0, data.length(), coldp, null);
            cold = 0;
        } else {
            /* First, a shot with the search RE. */
            Dfa s = new Dfa(this, g.search);
            close = s.shortest(0, 0, data.length(), coldp, null);
            cold = coldp[0];
        }

        if (close == -1) {      /* not found */
            return false;
        }

    /* find starting point and match */
        open = cold;
        cold = -1;

        for (begin = open; begin <= close; begin++) {
            /*
             * if LOOKING_AT, we can't validly have a 'begin' after 'open'.
             * I'm not sure this test can even ever go off, since the 'shortest' test
             * up above should accomplish the same thing.
             */
            if (begin > 0 && lookingAt) {
                return false;
            }

            boolean[] hitendp = new boolean[1];
            if (shorter) {
                end = d.shortest(begin, begin, data.length(), null, hitendp);
            } else {
                end = d.longest(begin, data.length(), hitendp);
            }
            hitend = hitendp[0];

            if (hitend && cold == -1) {
                cold = begin;
            }
            if (end != -1) { /* success */
                break;      /* NOTE BREAK OUT */
            }
        }

        if (end == -1) {
            return false;
        }

        /* and pin down details */
        match.set(0, new RegMatch(begin, end));

        // no need to do the work.
        return re.nsub <= 0 || dissect(g.tree, begin, end);
    }


    /**
     * cfind - find a match for the main NFA (with complications)
     */
    private boolean cfind(Cnfa cnfa) {
        int[] cold = new int[1];

        Dfa s = new Dfa(this, g.search);
        Dfa d = new Dfa(this, cnfa);

        return cfindloop(d, s, cold);
    }

    /**
     * cfindloop - the heart of cfind
     */
    private boolean cfindloop(Dfa d, Dfa s, int[] coldp) {
        int begin;
        int end;
        int cold;
        int open;       /* open and close of range of possible starts */
        int close;
        int estart;
        int estop;
        boolean shorter = 0 != (g.tree.flags & Subre.SHORTER);
        boolean hitend[] = new boolean[1];
        boolean lookingAt = 0 != (eflags & Flags.REG_LOOKING_AT);

        assert d != null && s != null;
        close = 0;
        do {
            int[] cold0 = new int[1];
            /*
             * Call search NFA to see if this is possible at all.
             */
            if (lookingAt) {
                // in the looking at case, we use the un-search-ified RE.
                close = d.shortest(close, close, data.length(), cold0, null);
                cold = 0;

            } else {
                close = s.shortest(close, close, data.length(), cold0, null);
                cold = cold0[0];
            }

            if (close == -1) {
                break;              /* NOTE BREAK */
            }
            assert cold != -1;
            open = cold;
            cold = -1;

            for (begin = open; begin <= close; begin++) {

                if (begin > 0 && lookingAt) {
                    // Is this possible given the looking-at constraint in the call to shortest above?
                    return false;
                }
                estart = begin;
                estop = data.length();
                for (;;) {
                    if (shorter) {
                        end = d.shortest(begin, estart, estop, null, hitend);
                    } else {
                        end = d.longest(begin, estop, hitend);
                    }
                    if (hitend[0] && cold == -1) {
                        cold = begin;
                    }
                    if (end == -1) {
                        break;      /* NOTE BREAK OUT */
                    }

                    for (int x = 0; x < match.size(); x++) {
                        match.set(x, null);
                    }

                    int maxsubno = getMaxSubno(g.tree, 0);
                    mem = new int[maxsubno + 1];
                    boolean matched = cdissect(g.tree, begin, end);
                    if (matched) {
                        // indicate the full match bounds.
                        match.set(0, new RegMatch(begin, end));
                        coldp[0] = cold;
                        return true;
                    }
                    if (shorter ? end == estop : end == begin) {
                        /* no point in trying again */
                        coldp[0] = cold;
                        return false;
                    }
                    /* go around and try again */
                    if (shorter) {
                        estart = end + 1;
                    } else {
                        estop = end - 1;
                    }
                }
            }
        } while (close < data.length());

        coldp[0] = cold;
        return false;
    }

    /**
     * subset - set any subexpression relevant to a successful subre
     */
    private void subset(RuntimeSubexpression sub, int begin, int end) {
        int n = sub.number;

        assert n > 0;

        while (match.size() < (n + 1)) {
            match.add(null);
        }

        match.set(n, new RegMatch(begin, end));
    }

    /**
     * dissect - determine subexpression matches (uncomplicated case)
     */
    private boolean dissect(RuntimeSubexpression t, int begin, int end) {
        switch (t.op) {
        case '=':       /* terminal node */
            assert t.left == null && t.right == null;
            return true;    /* no action, parent did the work */

        case '|':       /* alternation */
            assert t.left != null;
            return altdissect(t, begin, end);

        case 'b':       /* back ref -- shouldn't be calling us! */
            throw new RuntimeException("impossible backref");

        case '.':       /* concatenation */
            assert t.left != null && t.right != null;
            return condissect(t, begin, end);

        case '(':       /* capturing */
            assert t.left != null && t.right == null;
            assert t.number > 0;
            subset(t, begin, end);
            return dissect(t.left, begin, end);

        default:
            throw new RuntimeException("Impossible op");
        }
    }


    /**
     * condissect - determine concatenation subexpression matches (uncomplicated)
     */
    private boolean condissect(RuntimeSubexpression t, int begin, int end) {
        Dfa d;
        Dfa d2;
        int mid;
        assert t.op == '.';
        assert t.left != null && t.left.machine.states.length > 0;
        assert t.right != null && t.right.machine.states.length > 0;

        boolean shorter = (t.left.flags & Subre.SHORTER) != 0;
        int stop = shorter ? end : begin;


        d = new Dfa(this, t.left.machine);
        d2 = new Dfa(this, t.right.machine);

    /* pick a tentative midpoint */
        if (shorter) {
            mid = d.shortest(begin, begin, end, null, null);
        } else {
            mid = d.longest(begin, end, null);
        }
        if (mid == -1) {
            throw new RuntimeException("Impossible mid.");
        }

    /* iterate until satisfaction or failure */
        while (d2.longest(mid, end, null) != end) {
        /* that midpoint didn't work, find a new one */
            if (mid == stop) {
            /* all possibilities exhausted! */
                throw new RuntimeException("no midpoint");
            }
            if (shorter) {
                mid = d.shortest(begin, mid + 1, end, null, null);
            } else {
                mid = d.longest(begin, mid - 1, null);
            }
            if (mid == -1) {
                throw new RuntimeException("Failed midpoint");
            }
        }

    /* satisfaction */
        boolean dissectMatch = dissect(t.left, begin, mid);
        if (!dissectMatch) {
            return false;
        }
        return dissect(t.right, mid, end);
    }

    /**
     * altdissect - determine alternative subexpression matches (uncomplicated)
     */
    private boolean altdissect(RuntimeSubexpression t, int begin, int end) {
        Dfa d;

        assert t != null;
        assert t.op == '|';

        for (; t != null; t = t.right) {
            assert t.left != null && t.left.machine.states.length > 0;
            d = new Dfa(this, t.left.machine);
            if (d.longest(begin, end, null) == end) {
                return dissect(t.left, begin, end);
            }
        }
        throw new RuntimeException("none matched");
    }


    /**
     * cdissect - determine subexpression matches (with complications)
     * The retry memory stores the offset of the trial midpoint from begin,
     * plus 1 so that 0 uniquely means "clean slate".
     */
    private boolean cdissect(RuntimeSubexpression t, int begin, int end) {

        assert t != null;

        switch (t.op) {
        case '=':       /* terminal node */
            assert t.left == null && t.right == null;
            return true;    /* no action, parent did the work */

        case '|':       /* alternation */
            assert t.left != null;
            return caltdissect(t, begin, end);

        case 'b':       /* back ref -- shouldn't be calling us! */
            assert t.left == null && t.right == null;
            return cbrdissect(t, begin, end);

        case '.':       /* concatenation */
            assert t.left != null && t.right != null;
            return ccondissect(t, begin, end);

        case '(':       /* capturing */
            assert t.left != null && t.right == null;
            assert t.number > 0;
            boolean cdmatch = cdissect(t.left, begin, end);
            if (cdmatch) {
                subset(t, begin, end);
            }
            return cdmatch;

        default:
            throw new RuntimeException("Impossible op");
        }
    }

    /**
     * - ccondissect - concatenation subexpression matches (with complications)
     * The retry memory stores the offset of the trial midpoint from begin,
     * plus 1 so that 0 uniquely means "clean slate".
     */
    private boolean ccondissect(RuntimeSubexpression t, int begin, int end) {
        Dfa d;
        Dfa d2;
        int mid;

        assert t.op == '.';
        assert t.left != null && t.left.machine.states.length > 0;
        assert t.right != null && t.right.machine.states.length > 0;

        if (0 != (t.left.flags & Subre.SHORTER)) {      /* reverse scan */
            return crevdissect(t, begin, end);
        }

        d = new Dfa(this, t.left.machine);
        d2 = new Dfa(this, t.right.machine);

    /* pick a tentative midpoint */
        if (mem[t.retry] == 0) {
            mid = d.longest(begin, end, null);
            if (mid == -1) {
                return false;
            }
            mem[t.retry] = (mid - begin) + 1;
        } else {
            mid = begin + (mem[t.retry] - 1);
        }

    /* iterate until satisfaction or failure */
        for (;;) {
        /* try this midpoint on for size */
            boolean cdmatch = cdissect(t.left, begin, mid);
            if (cdmatch && d2.longest(mid, end, null) == end
                    && (cdissect(t.right, mid, end))) {
                break;          /* NOTE BREAK OUT */

            }

        /* that midpoint didn't work, find a new one */
            if (mid == begin) {
            /* all possibilities exhausted */
                return false;
            }
            mid = d.longest(begin, mid - 1, null);
            if (mid == -1) {
            /* failed to find a new one */
                return false;
            }
            mem[t.retry] = (mid - begin) + 1;
            zapmem(t.left);
            zapmem(t.right);
        }

    /* satisfaction */
        return true;
    }

    private void zapmem(RuntimeSubexpression t) {
        mem[t.retry] = 0;
        while (match.size() < t.number + 1) {
            match.add(null);
        }
        if (t.left != null) {
            zapmem(t.left);
        }
        if (t.right != null) {
            zapmem(t.right);
        }
    }


    /**
     * crevdissect - determine backref shortest-first subexpression matches
     * The retry memory stores the offset of the trial midpoint from begin,
     * plus 1 so that 0 uniquely means "clean slate".
     */
    private boolean crevdissect(RuntimeSubexpression t, int begin, int end) {
        Dfa d;
        Dfa d2;
        int mid;

        assert t.op == '.';
        assert t.left != null && t.left.machine.states.length > 0;
        assert t.right != null && t.right.machine.states.length > 0;
        assert 0 != (t.left.flags & Subre.SHORTER);

    /* concatenation -- need to split the substring between parts */
        d = new Dfa(this, t.left.machine);
        d2 = new Dfa(this, t.right.machine);

    /* pick a tentative midpoint */
        if (mem[t.retry] == 0) {
            mid = d.shortest(begin, begin, end, null, null);
            if (mid == -1) {
                return false;
            }
            mem[t.retry] = (mid - begin) + 1;
        } else {
            mid = begin + (mem[t.retry] - 1);
        }

    /* iterate until satisfaction or failure */
        for (;;) {
        /* try this midpoint on for size */
            boolean cdmatch = cdissect(t.left, begin, mid);
            if (cdmatch
                    && d2.longest(mid, end, null) == end
                    && (cdissect(t.right, mid, end))) {
                break;          /* NOTE BREAK OUT */
            }

        /* that midpoint didn't work, find a new one */
            if (mid == end) {
            /* all possibilities exhausted */
                return false;
            }
            mid = d.shortest(begin, mid + 1, end, null, null);
            if (mid == -1) {
            /* failed to find a new one */
                return false;
            }
            mem[t.retry] = (mid - begin) + 1;
            zapmem(t.left);
            zapmem(t.right);
        }

    /* satisfaction */
        return true;
    }


    /**
     * cbrdissect - determine backref subexpression matches
     */
    private boolean cbrdissect(RuntimeSubexpression t, int begin, int end) {
        int i;
        int n = t.number;
        int len;
        int paren;
        int p;
        int stop;
        int min = t.min;
        int max = t.max;

        assert t.op == 'b';
        assert n >= 0;

        //TODO: could this get be out of range?
        if (match.get(n) == null) {
            return false;
        }
        paren = match.get(n).start;
        len = match.get(n).end - match.get(n).start;

    /* no room to maneuver -- retries are pointless */
        if (0 != mem[t.retry]) {
            return false;
        }
        mem[t.retry] = 1;

    /* special-case zero-length string */
        if (len == 0) {
            return begin == end;
        }

        /* and too-short string */
        assert end >= begin;
        if ((end - begin) < len) {
            return false;
        }
        stop = end - len;

    /* count occurrences */
        i = 0;
        for (p = begin; p <= stop && (i < max || max == Compiler.INFINITY); p += len) {
            // paren is index of

            if (g.compare.compare(data, paren, p, len) != 0) {
                break;
            }
            i++;
        }

    /* and sort it out */
        if (p != end) {         /* didn't consume all of it */
            return false;
        }
        return min <= i && (i <= max || max == Compiler.INFINITY);
    }

    /*
     - caltdissect - determine alternative subexpression matches (w. complications)
     ^ static int caltdissect(struct vars *, struct Subre , int , int );
     */
    private boolean caltdissect(RuntimeSubexpression t, int begin, int end) {
        Dfa d;
        if (t == null) {
            return false;
        }
        assert t.op == '|';
        if (mem[t.retry] == TRIED) {
            return caltdissect(t.right, begin, end);
        }

        if (mem[t.retry] == UNTRIED) {
            d = new Dfa(this, t.left.machine);
            if (d.longest(begin, end, null) != end) {
                mem[t.retry] = TRIED;
                return caltdissect(t.right, begin, end);
            }
            mem[t.retry] = TRYING;
        }

        boolean cdmatch = cdissect(t.left, begin, end);
        if (cdmatch) {
            return true;
        }

        mem[t.retry] = TRIED;
        return caltdissect(t.right, begin, end);
    }

    private int getMaxSubno(RuntimeSubexpression tree, int i) {
        i = Math.max(i, tree.retry);
        if (tree.left != null) {
            i = Math.max(i, getMaxSubno(tree.left, i));
        }
        if (tree.right != null) {
            i = Math.max(i, getMaxSubno(tree.right, i));
        }
        return i;
    }
}
