1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
use std::collections::HashMap;
use bit_set::BitSet;
use crate::atn::INVALID_ALT;
use crate::atn_config::ATNConfig;
use crate::atn_config_set::ATNConfigSet;
use crate::atn_state::ATNStateRef;
use crate::prediction_context::PredictionContext;
use crate::semantic_context::SemanticContext;
/// This enum defines the prediction modes available in ANTLR 4 along with
/// utility methods for analyzing configuration sets for conflicts and/or
/// ambiguities.
///
/// It is set through `ParserATNSimulator::
#[allow(non_camel_case_types)]
#[derive(Eq, PartialEq, Copy, Clone, Debug)]
pub enum PredictionMode {
/// The SLL(*) prediction mode. This prediction mode ignores the current
/// parser context when making predictions. This is the fastest prediction
/// mode, and provides correct results for many grammars. This prediction
/// mode is more powerful than the prediction mode provided by ANTLR 3, but
/// may result in syntax errors for grammar and input combinations which are
/// not SLL.
///
/// <p>
/// When using this prediction mode, the parser will either return a correct
/// parse tree (i.e. the same parse tree that would be returned with the
/// {@link #LL} prediction mode), or it will report a syntax error. If a
/// syntax error is encountered when using the {@link #SLL} prediction mode,
/// it may be due to either an actual syntax error in the input or indicate
/// that the particular combination of grammar and input requires the more
/// powerful {@link #LL} prediction abilities to complete successfully.</p>
///
/// <p>
/// This prediction mode does not provide any guarantees for prediction
/// behavior for syntactically-incorrect inputs.</p>
///
SLL = 0,
///
/// The LL(*) prediction mode. This prediction mode allows the current parser
/// context to be used for resolving SLL conflicts that occur during
/// prediction. This is the fastest prediction mode that guarantees correct
/// parse results for all combinations of grammars with syntactically correct
/// inputs.
///
/// <p>
/// When using this prediction mode, the parser will make correct decisions
/// for all syntactically-correct grammar and input combinations. However, in
/// cases where the grammar is truly ambiguous this prediction mode might not
/// report a precise answer for <em>exactly which</em> alternatives are
/// ambiguous.</p>
///
/// <p>
/// This prediction mode does not provide any guarantees for prediction
/// behavior for syntactically-incorrect inputs.</p>
///
LL,
///
/// The LL(*) prediction mode with exact ambiguity detection. In addition to
/// the correctness guarantees provided by the {@link #LL} prediction mode,
/// this prediction mode instructs the prediction algorithm to determine the
/// complete and exact set of ambiguous alternatives for every ambiguous
/// decision encountered while parsing.
///
/// <p>
/// This prediction mode may be used for diagnosing ambiguities during
/// grammar development. Due to the performance overhead of calculating sets
/// of ambiguous alternatives, this prediction mode should be avoided when
/// the exact results are not necessary.</p>
///
/// <p>
/// This prediction mode does not provide any guarantees for prediction
/// behavior for syntactically-incorrect inputs.</p>
///
LL_EXACT_AMBIG_DETECTION,
}
impl PredictionMode {
//todo move everything here
}
//
//
pub(crate) fn has_sll_conflict_terminating_prediction(
mode: PredictionMode,
configs: &ATNConfigSet,
) -> bool {
// if all_configs_in_rule_stop_states(configs) {
// return true checked outside
// }
let mut dup = ATNConfigSet::new_base_atnconfig_set(true);
let mut configs = &*configs;
if mode == PredictionMode::SLL {
if configs.has_semantic_context() {
configs.get_items().for_each(|it| {
let c = ATNConfig::new_with_semantic(
it.get_state(),
it.get_alt(),
it.get_context().cloned(),
Box::new(SemanticContext::NONE),
);
dup.add(Box::new(c));
});
configs = &dup;
}
}
let altsets = get_conflicting_alt_subsets(&configs);
let heuristic =
has_conflicting_alt_set(&altsets) && !has_state_associated_with_one_alt(&configs);
return heuristic;
}
//fn all_configs_in_rule_stop_states(configs: &ATNConfigSet) -> bool {
// for co
//}
pub(crate) fn resolves_to_just_one_viable_alt(altsets: &Vec<BitSet>) -> isize {
get_single_viable_alt(altsets)
}
pub(crate) fn all_subsets_conflict(altsets: &Vec<BitSet>) -> bool {
!has_non_conflicting_alt_set(altsets)
}
pub(crate) fn all_subsets_equal(altsets: &Vec<BitSet>) -> bool {
let mut iter = altsets.iter();
let first = iter.next();
iter.all(|it| it == first.unwrap())
}
fn has_non_conflicting_alt_set(altsets: &Vec<BitSet>) -> bool {
altsets.iter().any(|it| it.len() == 1)
}
fn has_conflicting_alt_set(altsets: &Vec<BitSet>) -> bool {
for alts in altsets {
if alts.len() > 1 {
return true;
}
}
false
}
//fn get_unique_alt(altsets: &Vec<BitSet>) -> int { unimplemented!() }
//
pub(crate) fn get_alts(altsets: &Vec<BitSet>) -> BitSet {
altsets.iter().fold(BitSet::new(), |mut acc, it| {
acc.extend(it);
acc
})
}
//
pub(crate) fn get_conflicting_alt_subsets(configs: &ATNConfigSet) -> Vec<BitSet> {
let mut configs_to_alts: HashMap<(ATNStateRef, &PredictionContext), BitSet> = HashMap::new();
for c in configs.get_items() {
let alts = configs_to_alts
.entry((c.get_state(), c.get_context().unwrap()))
.or_default();
alts.insert(c.get_alt() as usize);
}
configs_to_alts.drain().map(|(_, x)| x).collect()
}
fn get_state_to_alt_map(configs: &ATNConfigSet) -> HashMap<ATNStateRef, BitSet> {
let mut m = HashMap::new();
for c in configs.get_items() {
let alts = m.entry(c.get_state()).or_insert(BitSet::new());
alts.insert(c.get_alt() as usize);
}
m
}
fn has_state_associated_with_one_alt(configs: &ATNConfigSet) -> bool {
let x = get_state_to_alt_map(configs);
for alts in x.values() {
if alts.len() == 1 {
return true;
}
}
false
}
pub(crate) fn get_single_viable_alt(altsets: &Vec<BitSet>) -> isize {
let mut viable_alts = BitSet::new();
let mut min_alt = INVALID_ALT as usize;
for alt in altsets {
min_alt = alt.iter().next().unwrap();
viable_alts.insert(min_alt);
if viable_alts.len() > 1 {
return INVALID_ALT;
}
}
min_alt as isize
}