<commit_before>package parser;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

import java_cup.Main;
import java_cup.lalr_item;
import java_cup.lalr_state;
import java_cup.non_terminal;
import java_cup.production;
import java_cup.symbol;
import java_cup.symbol_part;
import java_cup.terminal;

public class UnifiedExample {

    public static final boolean extendedSearch = false;

    protected static final int PRODUCTION_COST = 50;
    protected static final int REDUCE_COST = 1;
    protected static final int SHIFT_COST = 1;
    protected static final int UNSHIFT_COST = 1;
    protected static final int DUPLICATE_PRODUCTION_COST = 0;
    protected static final int EXTENDED_COST = 10000;

    protected static final long ASSURANCE_LIMIT = 2 * 1000000000L;
    protected static final long TIME_LIMIT = 5 * 1000000000L;

    protected lalr_state conflict;
    protected lalr_item itm1;
    protected lalr_item itm2;
    protected terminal nextSym;
    protected boolean isShiftReduce;
    protected List<StateItem> shortestConflictPath;
    protected Set<lalr_state> scpSet;
    protected Set<lalr_state> rppSet;

    public UnifiedExample(lalr_state conflict, lalr_item itm1, lalr_item itm2,
            terminal nextSym) {
        this.conflict = conflict;
        this.nextSym = nextSym;
        if (itm1.dot_at_end()) {
            if (itm2.dot_at_end()) {
                // reduce/reduce conflict
                this.itm1 = itm1;
                this.itm2 = itm2;
                isShiftReduce = false;
            }
            else {
                // shift/reduce conflict
                this.itm1 = itm1;
                this.itm2 = itm2;
                isShiftReduce = true;
            }
        }
        else if (itm2.dot_at_end()) {
            // shift/reduce conflict
            this.itm1 = itm2;
            this.itm2 = itm1;
            isShiftReduce = true;
        }
        else throw new Error("Expected at least one reduce item.");
        shortestConflictPath = findShortestPathFromStart();
        scpSet = new HashSet<>(shortestConflictPath.size());
        production reduceProd = this.itm1.the_production();
        rppSet = new HashSet<>(reduceProd.rhs_length());
        boolean reduceProdReached = false;
        for (StateItem si : shortestConflictPath) {
            scpSet.add(si.state);
            reduceProdReached =
                    reduceProdReached || si.item.the_production() == reduceProd;
            if (reduceProdReached) rppSet.add(si.state);
        }
    }

    protected List<StateItem> findShortestPathFromStart() {
        StateItem.init();
        long start = System.nanoTime();
        lalr_state startState = lalr_state.startState();
        lalr_item startItem = lalr_state.startItem();
        StateItem source = StateItem.lookup(startState, startItem);
        StateItem target = StateItem.lookup(conflict, itm1);
        Queue<List<StateItemWithLookahead>> queue = new LinkedList<>();
        Set<StateItemWithLookahead> visited = new HashSet<>();
        {
            List<StateItemWithLookahead> init = new LinkedList<>();
            init.add(new StateItemWithLookahead(source,
                                                StateItem.symbolSet(source.item.lookahead())));
            queue.add(init);
        }
        while (!queue.isEmpty()) {
            List<StateItemWithLookahead> path = queue.remove();
            StateItemWithLookahead last = path.get(path.size() - 1);
            if (visited.contains(last)) continue;
            visited.add(last);
            if (target.equals(last.si) && last.lookahead.contains(nextSym)) {
                // Done
//                System.err.println(path);
                if (Main.report_cex_stats)
                    System.out.println("reachable:\n"
                            + (System.nanoTime() - start));
                System.err.println("reachable: " + (System.nanoTime() - start));
                List<StateItem> shortestConflictPath =
                        new ArrayList<>(path.size());
                for (StateItemWithLookahead sil : path)
                    shortestConflictPath.add(sil.si);
                return shortestConflictPath;
            }
            if (StateItem.trans.containsKey(last.si)) {
                for (Map.Entry<symbol, StateItem> trans : StateItem.trans.get(last.si)
                        .entrySet()) {
                    StateItem nextSI = trans.getValue();
                    StateItemWithLookahead next =
                            new StateItemWithLookahead(nextSI, last.lookahead);
                    List<StateItemWithLookahead> nextPath =
                            new LinkedList<>(path);
                    nextPath.add(next);
                    queue.add(nextPath);
                }
            }
            if (StateItem.prods.containsKey(last.si)) {
                production prod = last.si.item.the_production();
                int len = prod.rhs_length();
                int pos = last.si.item.dot_pos() + 1;
                Set<symbol> lookahead = new HashSet<>();
                do {
                    if (pos == len) {
                        lookahead.addAll(last.lookahead);
                        break;
                    }
                    else {
                        symbol sym = rhs(prod, pos);
                        if (sym instanceof terminal) {
                            lookahead.add(sym);
                            break;
                        }
                        else {
                            non_terminal nt = (non_terminal) sym;
                            lookahead.addAll(StateItem.symbolSet(nt.first_set()));
                            if (!nt.nullable()) break;
                        }
                    }
                    pos++;
                } while (pos <= len);
                for (lalr_item itm : StateItem.prods.get(last.si)) {
                    StateItem nextSI = StateItem.lookup(last.si.state, itm);
                    StateItemWithLookahead next =
                            new StateItemWithLookahead(nextSI, lookahead);
                    List<StateItemWithLookahead> nextPath =
                            new LinkedList<>(path);
                    nextPath.add(next);
                    queue.add(nextPath);
                }
            }
        }
        throw new Error("Cannot find shortest path to conflict state.");
    }

    protected class StateItemWithLookahead {
        protected StateItem si;
        protected Set<symbol> lookahead;

        protected StateItemWithLookahead(StateItem si, Set<symbol> lookahead) {
            this.si = si;
            this.lookahead = lookahead;
        }

        @Override
        public String toString() {
            return si.toString() + lookahead.toString();
        }

        @Override
        public int hashCode() {
            return si.hashCode() * 31 + lookahead.hashCode();
        }
<commit_msg>Optimized search for shortest lookahead-sensitive path.<commit_after>package parser;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

import java_cup.Main;
import java_cup.lalr_item;
import java_cup.lalr_state;
import java_cup.non_terminal;
import java_cup.production;
import java_cup.symbol;
import java_cup.symbol_part;
import java_cup.terminal;

public class UnifiedExample {

    public static final boolean extendedSearch = false;

    protected static final int PRODUCTION_COST = 50;
    protected static final int REDUCE_COST = 1;
    protected static final int SHIFT_COST = 1;
    protected static final int UNSHIFT_COST = 1;
    protected static final int DUPLICATE_PRODUCTION_COST = 0;
    protected static final int EXTENDED_COST = 10000;

    protected static final long ASSURANCE_LIMIT = 2 * 1000000000L;
    protected static final long TIME_LIMIT = 5 * 1000000000L;

    protected lalr_state conflict;
    protected lalr_item itm1;
    protected lalr_item itm2;
    protected terminal nextSym;
    protected boolean isShiftReduce;
    protected List<StateItem> shortestConflictPath;
    protected Set<lalr_state> scpSet;
    protected Set<lalr_state> rppSet;

    public UnifiedExample(lalr_state conflict, lalr_item itm1, lalr_item itm2,
            terminal nextSym) {
        this.conflict = conflict;
        this.nextSym = nextSym;
        if (itm1.dot_at_end()) {
            if (itm2.dot_at_end()) {
                // reduce/reduce conflict
                this.itm1 = itm1;
                this.itm2 = itm2;
                isShiftReduce = false;
            }
            else {
                // shift/reduce conflict
                this.itm1 = itm1;
                this.itm2 = itm2;
                isShiftReduce = true;
            }
        }
        else if (itm2.dot_at_end()) {
            // shift/reduce conflict
            this.itm1 = itm2;
            this.itm2 = itm1;
            isShiftReduce = true;
        }
        else throw new Error("Expected at least one reduce item.");
        shortestConflictPath = findShortestPathFromStart();
        scpSet = new HashSet<>(shortestConflictPath.size());
        production reduceProd = this.itm1.the_production();
        rppSet = new HashSet<>(reduceProd.rhs_length());
        boolean reduceProdReached = false;
        for (StateItem si : shortestConflictPath) {
            scpSet.add(si.state);
            reduceProdReached =
                    reduceProdReached || si.item.the_production() == reduceProd;
            if (reduceProdReached) rppSet.add(si.state);
        }
    }

    protected List<StateItem> findShortestPathFromStart() {
        StateItem.init();
        long start = System.nanoTime();
        lalr_state startState = lalr_state.startState();
        lalr_item startItem = lalr_state.startItem();
        StateItem source = StateItem.lookup(startState, startItem);
        StateItem target = StateItem.lookup(conflict, itm1);
        Set<StateItem> eligible = eligibleStateItemsToConflict(target);
        Queue<List<StateItemWithLookahead>> queue = new LinkedList<>();
        Set<StateItemWithLookahead> visited = new HashSet<>();
        {
            List<StateItemWithLookahead> init = new LinkedList<>();
            init.add(new StateItemWithLookahead(source,
                                                StateItem.symbolSet(source.item.lookahead())));
            queue.add(init);
        }
        while (!queue.isEmpty()) {
            List<StateItemWithLookahead> path = queue.remove();
            StateItemWithLookahead last = path.get(path.size() - 1);
            if (visited.contains(last)) continue;
            visited.add(last);
            if (target.equals(last.si) && last.lookahead.contains(nextSym)) {
                // Done
//                System.err.println(path);
                if (Main.report_cex_stats)
                    System.out.println("reachable:\n"
                            + (System.nanoTime() - start));
                System.err.println("reachable: " + (System.nanoTime() - start));
                List<StateItem> shortestConflictPath =
                        new ArrayList<>(path.size());
                for (StateItemWithLookahead sil : path)
                    shortestConflictPath.add(sil.si);
                return shortestConflictPath;
            }
            if (StateItem.trans.containsKey(last.si)) {
                for (Map.Entry<symbol, StateItem> trans : StateItem.trans.get(last.si)
                        .entrySet()) {
                    StateItem nextSI = trans.getValue();
                    if (!eligible.contains(nextSI)) continue;
                    StateItemWithLookahead next =
                            new StateItemWithLookahead(nextSI, last.lookahead);
                    List<StateItemWithLookahead> nextPath =
                            new LinkedList<>(path);
                    nextPath.add(next);
                    queue.add(nextPath);
                }
            }
            if (StateItem.prods.containsKey(last.si)) {
                production prod = last.si.item.the_production();
                int len = prod.rhs_length();
                int pos = last.si.item.dot_pos() + 1;
                Set<symbol> lookahead = new HashSet<>();
                do {
                    if (pos == len) {
                        lookahead.addAll(last.lookahead);
                        break;
                    }
                    else {
                        symbol sym = rhs(prod, pos);
                        if (sym instanceof terminal) {
                            lookahead.add(sym);
                            break;
                        }
                        else {
                            non_terminal nt = (non_terminal) sym;
                            lookahead.addAll(StateItem.symbolSet(nt.first_set()));
                            if (!nt.nullable()) break;
                        }
                    }
                    pos++;
                } while (pos <= len);
                for (lalr_item itm : StateItem.prods.get(last.si)) {
                    StateItem nextSI = StateItem.lookup(last.si.state, itm);
                    if (!eligible.contains(nextSI)) continue;
                    StateItemWithLookahead next =
                            new StateItemWithLookahead(nextSI, lookahead);
                    List<StateItemWithLookahead> nextPath =
                            new LinkedList<>(path);
                    nextPath.add(next);
                    queue.add(nextPath);
                }
            }
        }
        throw new Error("Cannot find shortest path to conflict state.");
    }

    protected Set<StateItem> eligibleStateItemsToConflict(StateItem target) {
        Set<StateItem> result = new HashSet<>();
        Queue<StateItem> queue = new LinkedList<>();
        queue.add(target);
        while (!queue.isEmpty()) {
            StateItem si = queue.remove();
            if (result.contains(si)) continue;
            result.add(si);
            // Consider reverse transitions and reverse productions.
            if (StateItem.revTrans.containsKey(si))
                for (Set<StateItem> prev : StateItem.revTrans.get(si).values())
                    queue.addAll(prev);
            if (si.item.dot_pos() == 0) {
                production prod = si.item.the_production();
                symbol lhs = prod.lhs().the_symbol();
                if (StateItem.revProds.containsKey(si.state)) {
                    Map<non_terminal, Set<lalr_item>> revProd =
                            StateItem.revProds.get(si.state);
                    if (revProd.containsKey(lhs))
                        for (lalr_item prev : revProd.get(lhs))
                            queue.add(StateItem.lookup(si.state, prev));
                }
            }
        }
        return result;
    }

    protected class StateItemWithLookahead {
        protected StateItem si;
        protected Set<symbol> lookahead;

        protected StateItemWithLookahead(StateItem si, Set<symbol> lookahead) {
            this.si = si;
            this.lookahead = lookahead;
        }

        @Override
        public String toString() {
            return si.toString() + lookahead.toString();
        }

        @Override
        public int hashCode() {
            return si.hashCode() * 31 + lookahead.hashCode();
        }

{'fraction_non_alphanumeric': 0.09292929292929293, 'fraction_numerical': 0.007386363636363636, 'mean_word_length': 1.647225935828877, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 62, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 4, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5386898', 'n_tokens_mistral': 4440, 'n_tokens_neox': 4146, 'n_words': 886}