use dbt_antlr_runtime::dfa::static_parser_dfa::{MAX_TABLE_CELLS, MAX_TABLE_STATES};
use crate::grammar::model::OptionDecl;
pub(crate) const DEFAULT_MAX_STATES: usize = 1000;
pub(crate) const DEFAULT_VISIT_BUDGET: u64 = 2_000_000;
const VISITS_PER_STATE: u64 = DEFAULT_VISIT_BUDGET / DEFAULT_MAX_STATES as u64;
pub(crate) const MAX_STATES_OPTION: &str = "max_dfa_states";
pub(crate) const MAX_STATES_ALIAS: &str = "max_states";
pub(crate) const MAX_K_OPTION: &str = "max_k";
pub(crate) const MAX_VISITS_OPTION: &str = "max_dfa_visits";
pub(crate) const BUDGET_OPTIONS: &[&str] = &[
MAX_STATES_OPTION,
MAX_STATES_ALIAS,
MAX_K_OPTION,
MAX_VISITS_OPTION,
];
pub(crate) fn is_budget_option(name: &str) -> bool {
BUDGET_OPTIONS.contains(&name)
}
pub(crate) fn has_non_budget_option(options: &[OptionDecl]) -> bool {
options
.iter()
.any(|option| !is_budget_option(&option.name.value))
}
pub(crate) fn budget_option_problem(name: &str, value: &str) -> Option<String> {
match name {
MAX_STATES_OPTION | MAX_STATES_ALIAS => parse_limit(value, MAX_TABLE_STATES as u64).err(),
MAX_K_OPTION => parse_limit(value, u64::from(u32::MAX)).err(),
MAX_VISITS_OPTION => parse_limit(value, u64::MAX).err(),
_ => None,
}
}
fn parse_limit(value: &str, max: u64) -> Result<u64, String> {
let parsed = value
.parse::<u64>()
.map_err(|_| format!("'{value}' is not a positive integer"))?;
if parsed == 0 {
return Err("the value must be at least 1".to_owned());
}
if parsed > max {
return Err(format!("the value must be at most {max}"));
}
Ok(parsed)
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub(crate) struct BudgetLimits {
pub(crate) max_states: Option<usize>,
pub(crate) max_k: Option<usize>,
pub(crate) max_visits: Option<u64>,
}
impl BudgetLimits {
pub(crate) const fn or(self, fallback: Self) -> Self {
Self {
max_states: match self.max_states {
Some(value) => Some(value),
None => fallback.max_states,
},
max_k: match self.max_k {
Some(value) => Some(value),
None => fallback.max_k,
},
max_visits: match self.max_visits {
Some(value) => Some(value),
None => fallback.max_visits,
},
}
}
pub(crate) fn from_options(options: &[OptionDecl]) -> Self {
let mut limits = Self::default();
for option in options {
limits.set(&option.name.value, &option.value.value);
}
limits
}
fn set(&mut self, name: &str, value: &str) {
if !is_budget_option(name) || budget_option_problem(name, value).is_some() {
return;
}
let Ok(parsed) = value.parse::<u64>() else {
return;
};
match name {
MAX_STATES_OPTION | MAX_STATES_ALIAS => self.max_states = usize::try_from(parsed).ok(),
MAX_K_OPTION => self.max_k = usize::try_from(parsed).ok(),
_ => self.max_visits = Some(parsed),
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct DecisionBudget {
pub(crate) max_states: usize,
pub(crate) max_k: Option<usize>,
pub(crate) max_visits: u64,
pub(crate) explicit_max_states: bool,
}
impl Default for DecisionBudget {
fn default() -> Self {
Self {
max_states: DEFAULT_MAX_STATES,
max_k: None,
max_visits: DEFAULT_VISIT_BUDGET,
explicit_max_states: false,
}
}
}
impl DecisionBudget {
pub(crate) fn resolve(limits: BudgetLimits, max_token_type: i32) -> Self {
let row_width = usize::try_from(max_token_type).unwrap_or(0) + 2;
let image_cap = MAX_TABLE_STATES.min(MAX_TABLE_CELLS / row_width).max(1);
let max_states = limits
.max_states
.unwrap_or(DEFAULT_MAX_STATES)
.clamp(1, image_cap);
let max_visits = limits
.max_visits
.unwrap_or_else(|| DEFAULT_VISIT_BUDGET.max(max_states as u64 * VISITS_PER_STATE));
Self {
max_states,
max_k: limits.max_k,
max_visits,
explicit_max_states: limits.max_states.is_some(),
}
}
}
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub(crate) struct ParserDfaBudgets {
pub(crate) global: BudgetLimits,
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn resolved_budgets_clamp_to_the_table_image() {
let budget = DecisionBudget::resolve(BudgetLimits::default(), 100);
assert_eq!(budget, DecisionBudget::default());
let budget = DecisionBudget::resolve(
BudgetLimits {
max_states: Some(4000),
..BudgetLimits::default()
},
100,
);
assert_eq!(budget.max_states, 4000);
assert_eq!(budget.max_visits, 8_000_000);
let budget = DecisionBudget::resolve(
BudgetLimits {
max_states: Some(MAX_TABLE_STATES),
max_visits: Some(10),
..BudgetLimits::default()
},
2000,
);
assert_eq!(budget.max_states, MAX_TABLE_CELLS / 2002);
assert_eq!(budget.max_visits, 10);
}
}