use cpp_parser::{CppTokenKind, SourceRange};
use crate::token::is_trivia;
use crate::{macros::MacroDef, token::Token};
pub fn is_a_builtin_operator(name: &str) -> bool {
matches!(
name,
"__has_include"
| "__has_include_next"
| "__has_cpp_attribute"
| "__has_builtin"
| "__has_feature"
| "__has_extension"
| "__has_attribute"
| "__has_declspec_attribute"
| "__is_identifier"
)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Value {
Known(i128),
Unknown,
}
impl Value {
pub fn is_true(self) -> Option<bool> {
match self {
Value::Known(value) => Some(value != 0),
Value::Unknown => None,
}
}
pub fn known(self) -> Option<i128> {
match self {
Value::Known(value) => Some(value),
Value::Unknown => None,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum EvalError {
UnexpectedEnd,
ExpectedOperand { found: CppTokenKind },
ExpectedOperator { found: CppTokenKind },
TrailingTokens { count: usize },
ExpectedDefinedName,
UnclosedParenthesis,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ConditionExpr {
Number(i128),
Defined(Box<str>),
Identifier(Box<str>),
Group(Box<ConditionExpr>),
Builtin { name: Box<str>, operand: Box<str> },
Unary {
op: UnaryOp,
operand: Box<ConditionExpr>,
},
Binary {
op: BinaryOp,
left: Box<ConditionExpr>,
right: Box<ConditionExpr>,
},
Conditional {
condition: Box<ConditionExpr>,
then_value: Box<ConditionExpr>,
else_value: Box<ConditionExpr>,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum UnaryOp {
Plus,
Minus,
LogicalNot,
BitNot,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinaryOp {
Multiply,
Divide,
Remainder,
Add,
Subtract,
ShiftLeft,
ShiftRight,
Less,
LessEqual,
Greater,
GreaterEqual,
Equal,
NotEqual,
BitAnd,
BitXor,
BitOr,
LogicalAnd,
LogicalOr,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Lookup<'a> {
Defined(&'a MacroDef),
DefinedWithoutAValue,
Undefined,
Unanswered,
}
impl<'a> Lookup<'a> {
pub fn definition(self) -> Option<&'a MacroDef> {
match self {
Lookup::Defined(definition) => Some(definition),
Lookup::DefinedWithoutAValue | Lookup::Undefined | Lookup::Unanswered => None,
}
}
pub fn is_defined(self) -> Option<bool> {
match self {
Lookup::Defined(_) | Lookup::DefinedWithoutAValue => Some(true),
Lookup::Undefined => Some(false),
Lookup::Unanswered => None,
}
}
}
pub trait MacroValues {
fn lookup(&self, name: &str) -> Lookup<'_>;
fn builtin_operator(&self, name: &str, operand: &str) -> Option<Value> {
let _ = (name, operand);
None
}
}
#[derive(Debug, Clone, Copy, Default)]
pub struct NoMacros;
impl MacroValues for NoMacros {
fn lookup(&self, _name: &str) -> Lookup<'_> {
Lookup::Undefined
}
}
impl MacroValues for crate::macros::MacroTable {
fn lookup(&self, name: &str) -> Lookup<'_> {
self.get(name).map_or(Lookup::Undefined, Lookup::Defined)
}
}
pub fn parse_condition(tokens: &[Token]) -> Result<ConditionExpr, EvalError> {
let mut parser = Parser { tokens, index: 0 };
let expr = parser.conditional()?;
if parser.index < tokens.len() {
return Err(EvalError::TrailingTokens {
count: tokens.len() - parser.index,
});
}
Ok(expr)
}
pub fn evaluate(tokens: &[Token], macros: &impl MacroValues) -> Value {
let expanded = expand_condition(tokens, macros);
match parse_condition(&expanded) {
Ok(expr) => eval(&expr, macros),
Err(_) => Value::Unknown,
}
}
pub fn evaluate_recording(
tokens: &[Token],
macros: &impl MacroValues,
) -> (Value, Option<ConditionExpr>) {
let (expanded, unchanged) = expand_condition_recording(tokens, macros);
match parse_condition(&expanded) {
Ok(expr) => {
let value = eval(&expr, macros);
(value, unchanged.then_some(expr))
}
Err(_) => (Value::Unknown, None),
}
}
fn expand_condition(tokens: &[Token], macros: &impl MacroValues) -> Vec<Token> {
expand_condition_recording(tokens, macros).0
}
fn expand_condition_recording(tokens: &[Token], macros: &impl MacroValues) -> (Vec<Token>, bool) {
let mut expanded: Vec<Token> = Vec::new();
let mut run: Vec<Token> = Vec::new();
let mut unchanged = true;
let mut index = 0;
while index < tokens.len() {
let token = tokens[index].clone();
let is_a_question_about_a_name = token.kind == CppTokenKind::Identifier
&& (token.text() == "defined" || is_a_builtin_operator(token.text()));
if !is_a_question_about_a_name {
run.push(token);
index += 1;
continue;
}
let (from_run, run_unchanged) = expand_a_run_recording(&run, macros);
expanded.extend(from_run);
unchanged &= run_unchanged;
run.clear();
expanded.push(token);
index += 1;
let mut depth = 0isize;
while index < tokens.len() {
let held = tokens[index].clone();
if held.kind == CppTokenKind::LeftParen {
depth += 1;
} else if held.kind == CppTokenKind::RightParen {
depth -= 1;
}
expanded.push(held);
index += 1;
if depth == 0 {
break;
}
}
}
let (from_run, run_unchanged) = expand_a_run_recording(&run, macros);
expanded.extend(from_run);
unchanged &= run_unchanged;
(expanded, unchanged)
}
fn expand_a_run_recording(tokens: &[Token], macros: &impl MacroValues) -> (Vec<Token>, bool) {
if tokens.is_empty() {
return (Vec::new(), true);
}
let expansion = crate::expand::expand_with_budget(tokens, macros, EXPANSION_BUDGET);
let unchanged = expansion
.tokens
.iter()
.all(|expanded| matches!(expanded.origin, crate::preprocess::expand::Origin::Source));
let tokens = expansion
.tokens
.into_iter()
.map(|expanded| expanded.token)
.collect();
(tokens, unchanged)
}
pub fn eval(expr: &ConditionExpr, macros: &impl MacroValues) -> Value {
match expr {
ConditionExpr::Number(value) => Value::Known(*value),
ConditionExpr::Defined(name) => match macros.lookup(name).is_defined() {
Some(defined) => Value::Known(i128::from(defined)),
None => Value::Unknown,
},
ConditionExpr::Identifier(name) => match macros.lookup(name) {
Lookup::Undefined => Value::Known(0),
Lookup::DefinedWithoutAValue => Value::Unknown,
Lookup::Defined(definition) => macro_value(definition, macros),
Lookup::Unanswered => Value::Unknown,
},
ConditionExpr::Group(inner) => eval(inner, macros),
ConditionExpr::Builtin { name, operand } => macros
.builtin_operator(name, operand)
.unwrap_or(Value::Unknown),
ConditionExpr::Unary { op, operand } => {
let Some(value) = eval(operand, macros).known() else {
return Value::Unknown;
};
Value::Known(match op {
UnaryOp::Plus => value,
UnaryOp::Minus => value.wrapping_neg(),
UnaryOp::LogicalNot => i128::from(value == 0),
UnaryOp::BitNot => !value,
})
}
ConditionExpr::Binary {
op: BinaryOp::LogicalAnd,
left,
right,
} => match eval(left, macros).is_true() {
Some(false) => Value::Known(0),
Some(true) => match eval(right, macros).is_true() {
Some(value) => Value::Known(i128::from(value)),
None => Value::Unknown,
},
None => Value::Unknown,
},
ConditionExpr::Binary {
op: BinaryOp::LogicalOr,
left,
right,
} => match eval(left, macros).is_true() {
Some(true) => Value::Known(1),
Some(false) => match eval(right, macros).is_true() {
Some(value) => Value::Known(i128::from(value)),
None => Value::Unknown,
},
None => Value::Unknown,
},
ConditionExpr::Binary { op, left, right } => {
let (Some(left), Some(right)) =
(eval(left, macros).known(), eval(right, macros).known())
else {
return Value::Unknown;
};
eval_binary(*op, left, right)
}
ConditionExpr::Conditional {
condition,
then_value,
else_value,
} => match eval(condition, macros).is_true() {
Some(true) => eval(then_value, macros),
Some(false) => eval(else_value, macros),
None => {
let then = eval(then_value, macros);
let otherwise = eval(else_value, macros);
match (then.known(), otherwise.known()) {
(Some(a), Some(b)) if a == b => Value::Known(a),
_ => Value::Unknown,
}
}
},
}
}
const EXPANSION_BUDGET: usize = 4096;
fn macro_value(definition: &MacroDef, macros: &impl MacroValues) -> Value {
if let Some(held) = definition.value.get() {
return match held {
Some(value) => Value::Known(*value),
None => Value::Unknown,
};
}
let body: Vec<Token> = definition.body.significant().cloned().collect();
if body.is_empty() {
return Value::Unknown;
}
if definition.params.is_none()
&& let [only] = body.as_slice()
&& only.kind == CppTokenKind::IntegerLiteral
&& let Some(value) = parse_integer(only.text())
{
let _ = definition.value.set(Some(value));
return Value::Known(value);
}
let expanded = crate::expand::expand_with_budget(&body, macros, EXPANSION_BUDGET);
let tokens: Vec<Token> = expanded
.tokens
.into_iter()
.map(|expanded| expanded.token)
.collect();
if tokens
.iter()
.any(|token| token.kind == CppTokenKind::Identifier && token.text() == &*definition.name)
{
return Value::Unknown;
}
let mut significant = tokens.iter().filter(|token| !is_trivia(token.kind));
let Some(first) = significant.next() else {
return Value::Unknown;
};
if significant.next().is_none()
&& first.kind == CppTokenKind::IntegerLiteral
&& let Some(value) = parse_integer(first.text())
{
return Value::Known(value);
}
evaluate(&tokens, macros)
}
fn eval_binary(op: BinaryOp, left: i128, right: i128) -> Value {
let value = match op {
BinaryOp::Multiply => left.wrapping_mul(right),
BinaryOp::Divide => match left.checked_div(right) {
Some(value) => value,
None => return Value::Unknown,
},
BinaryOp::Remainder => match left.checked_rem(right) {
Some(value) => value,
None => return Value::Unknown,
},
BinaryOp::Add => left.wrapping_add(right),
BinaryOp::Subtract => left.wrapping_sub(right),
BinaryOp::ShiftLeft => left.wrapping_shl(right.clamp(0, 127) as u32),
BinaryOp::ShiftRight => left.wrapping_shr(right.clamp(0, 127) as u32),
BinaryOp::Less => i128::from(left < right),
BinaryOp::LessEqual => i128::from(left <= right),
BinaryOp::Greater => i128::from(left > right),
BinaryOp::GreaterEqual => i128::from(left >= right),
BinaryOp::Equal => i128::from(left == right),
BinaryOp::NotEqual => i128::from(left != right),
BinaryOp::BitAnd => left & right,
BinaryOp::BitXor => left ^ right,
BinaryOp::BitOr => left | right,
BinaryOp::LogicalAnd => i128::from(left != 0 && right != 0),
BinaryOp::LogicalOr => i128::from(left != 0 || right != 0),
};
Value::Known(value)
}
pub fn parse_integer(text: &str) -> Option<i128> {
let cleaned: String = text.chars().filter(|c| *c != '\'').collect();
let body = cleaned.trim_end_matches(['u', 'U', 'l', 'L']);
if body.is_empty() {
return None;
}
let (digits, radix) =
if let Some(rest) = body.strip_prefix("0x").or_else(|| body.strip_prefix("0X")) {
(rest, 16)
} else if let Some(rest) = body.strip_prefix("0b").or_else(|| body.strip_prefix("0B")) {
(rest, 2)
} else if body.len() > 1 && body.starts_with('0') {
(&body[1..], 8)
} else {
(body, 10)
};
i128::from_str_radix(digits, radix).ok()
}
struct Parser<'a> {
tokens: &'a [Token],
index: usize,
}
impl<'a> Parser<'a> {
fn peek(&self) -> Option<&'a Token> {
self.tokens.get(self.index)
}
fn kind(&self) -> Option<CppTokenKind> {
self.peek().map(|token| token.kind)
}
fn operator(&self) -> (Option<CppTokenKind>, usize) {
let Some(first) = self.peek() else {
return (None, 0);
};
if first.kind != CppTokenKind::Greater {
return (Some(first.kind), 1);
}
let touches =
|left: &Token, right: &Token| left.range.end_offset() == right.range.start_offset;
let second = self.tokens.get(self.index + 1);
let third = self.tokens.get(self.index + 2);
if let (Some(second), Some(third)) = (second, third)
&& second.kind == CppTokenKind::Greater
&& third.kind == CppTokenKind::Assign
&& touches(first, second)
&& touches(second, third)
{
return (Some(CppTokenKind::RightShiftAssign), 3);
}
if let Some(second) = second
&& touches(first, second)
{
match second.kind {
CppTokenKind::Greater => return (Some(CppTokenKind::RightShift), 2),
CppTokenKind::Assign => return (Some(CppTokenKind::GreaterEqual), 2),
_ => {}
}
}
(Some(CppTokenKind::Greater), 1)
}
fn bump(&mut self) -> Option<&'a Token> {
let token = self.tokens.get(self.index);
if token.is_some() {
self.index += 1;
}
token
}
fn eat(&mut self, kind: CppTokenKind) -> bool {
if self.kind() == Some(kind) {
self.index += 1;
true
} else {
false
}
}
fn conditional(&mut self) -> Result<ConditionExpr, EvalError> {
let condition = self.logical_or()?;
if !self.eat(CppTokenKind::Question) {
return Ok(condition);
}
let then_value = self.conditional()?;
if !self.eat(CppTokenKind::Colon) {
return Err(EvalError::ExpectedOperator {
found: self.kind().unwrap_or(CppTokenKind::Eof),
});
}
let else_value = self.conditional()?;
Ok(ConditionExpr::Conditional {
condition: Box::new(condition),
then_value: Box::new(then_value),
else_value: Box::new(else_value),
})
}
fn logical_or(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.logical_and()?;
while self.eat(CppTokenKind::LogicalOr) {
let right = self.logical_and()?;
left = binary(BinaryOp::LogicalOr, left, right);
}
Ok(left)
}
fn logical_and(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.bit_or()?;
while self.eat(CppTokenKind::LogicalAnd) {
let right = self.bit_or()?;
left = binary(BinaryOp::LogicalAnd, left, right);
}
Ok(left)
}
fn bit_or(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.bit_xor()?;
while self.eat(CppTokenKind::Pipe) {
let right = self.bit_xor()?;
left = binary(BinaryOp::BitOr, left, right);
}
Ok(left)
}
fn bit_xor(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.bit_and()?;
while self.eat(CppTokenKind::Caret) {
let right = self.bit_and()?;
left = binary(BinaryOp::BitXor, left, right);
}
Ok(left)
}
fn bit_and(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.equality()?;
while self.eat(CppTokenKind::Ampersand) {
let right = self.equality()?;
left = binary(BinaryOp::BitAnd, left, right);
}
Ok(left)
}
fn equality(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.relational()?;
loop {
let op = match self.kind() {
Some(CppTokenKind::Equal) => BinaryOp::Equal,
Some(CppTokenKind::NotEqual) => BinaryOp::NotEqual,
_ => break,
};
self.index += 1;
let right = self.relational()?;
left = binary(op, left, right);
}
Ok(left)
}
fn relational(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.shift()?;
loop {
let (kind, spans) = self.operator();
let op = match kind {
Some(CppTokenKind::Less) => BinaryOp::Less,
Some(CppTokenKind::LessEqual) => BinaryOp::LessEqual,
Some(CppTokenKind::Greater) => BinaryOp::Greater,
Some(CppTokenKind::GreaterEqual) => BinaryOp::GreaterEqual,
_ => break,
};
self.index += spans;
let right = self.shift()?;
left = binary(op, left, right);
}
Ok(left)
}
fn shift(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.additive()?;
loop {
let (kind, spans) = self.operator();
let op = match kind {
Some(CppTokenKind::LeftShift) => BinaryOp::ShiftLeft,
Some(CppTokenKind::RightShift) => BinaryOp::ShiftRight,
_ => break,
};
self.index += spans;
let right = self.additive()?;
left = binary(op, left, right);
}
Ok(left)
}
fn additive(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.multiplicative()?;
loop {
let op = match self.kind() {
Some(CppTokenKind::Plus) => BinaryOp::Add,
Some(CppTokenKind::Minus) => BinaryOp::Subtract,
_ => break,
};
self.index += 1;
let right = self.multiplicative()?;
left = binary(op, left, right);
}
Ok(left)
}
fn multiplicative(&mut self) -> Result<ConditionExpr, EvalError> {
let mut left = self.unary()?;
loop {
let op = match self.kind() {
Some(CppTokenKind::Star) => BinaryOp::Multiply,
Some(CppTokenKind::Slash) => BinaryOp::Divide,
Some(CppTokenKind::Percent) => BinaryOp::Remainder,
_ => break,
};
self.index += 1;
let right = self.unary()?;
left = binary(op, left, right);
}
Ok(left)
}
fn unary(&mut self) -> Result<ConditionExpr, EvalError> {
let op = match self.kind() {
Some(CppTokenKind::Plus) => Some(UnaryOp::Plus),
Some(CppTokenKind::Minus) => Some(UnaryOp::Minus),
Some(CppTokenKind::LogicalNot) => Some(UnaryOp::LogicalNot),
Some(CppTokenKind::Tilde) => Some(UnaryOp::BitNot),
_ => None,
};
if let Some(op) = op {
self.index += 1;
let operand = self.unary()?;
return Ok(ConditionExpr::Unary {
op,
operand: Box::new(operand),
});
}
self.primary()
}
fn primary(&mut self) -> Result<ConditionExpr, EvalError> {
let Some(token) = self.peek() else {
return Err(EvalError::UnexpectedEnd);
};
match token.kind {
CppTokenKind::IntegerLiteral
| CppTokenKind::CharLiteral
| CppTokenKind::BoolLiteral => {
let token = self.bump().expect("checked");
Ok(ConditionExpr::Number(
parse_integer(token.text()).unwrap_or(0),
))
}
CppTokenKind::LeftParen => {
self.index += 1;
let inner = self.conditional()?;
if !self.eat(CppTokenKind::RightParen) {
return Err(EvalError::UnclosedParenthesis);
}
Ok(ConditionExpr::Group(Box::new(inner)))
}
CppTokenKind::Identifier => {
if token.text() == "defined" {
return self.defined();
}
if is_a_builtin_operator(token.text()) {
let name = token.text.clone();
let Some(operand) = self.parenthesised_spelling() else {
return Err(EvalError::ExpectedOperand {
found: self.kind().unwrap_or(CppTokenKind::Eof),
});
};
return Ok(ConditionExpr::Builtin { name, operand });
}
let token = self.bump().expect("checked");
Ok(ConditionExpr::Identifier(token.text.clone()))
}
CppTokenKind::TrueKeyword | CppTokenKind::FalseKeyword => {
let token = self.bump().expect("checked");
Ok(ConditionExpr::Identifier(token.text.clone()))
}
found => Err(EvalError::ExpectedOperand { found }),
}
}
fn parenthesised_spelling(&mut self) -> Option<Box<str>> {
self.index += 1;
if !self.eat(CppTokenKind::LeftParen) {
return None;
}
let mut spelling = String::new();
let mut depth = 1isize;
while let Some(token) = self.bump() {
match token.kind {
CppTokenKind::LeftParen => {
depth += 1;
spelling.push('(');
}
CppTokenKind::RightParen => {
depth -= 1;
if depth == 0 {
break;
}
spelling.push(')');
}
kind if is_trivia(kind) => {}
_ => spelling.push_str(token.text()),
}
}
(depth == 0).then(|| spelling.into_boxed_str())
}
fn defined(&mut self) -> Result<ConditionExpr, EvalError> {
self.index += 1;
let parenthesised = self.eat(CppTokenKind::LeftParen);
let Some(token) = self.peek() else {
return Err(EvalError::ExpectedDefinedName);
};
if !token.is_identifier() {
return Err(EvalError::ExpectedDefinedName);
}
let name = self.bump().expect("checked").text.clone();
if parenthesised && !self.eat(CppTokenKind::RightParen) {
return Err(EvalError::UnclosedParenthesis);
}
Ok(ConditionExpr::Defined(name))
}
}
fn binary(op: BinaryOp, left: ConditionExpr, right: ConditionExpr) -> ConditionExpr {
ConditionExpr::Binary {
op,
left: Box::new(left),
right: Box::new(right),
}
}
pub fn condition_range(tokens: &[Token]) -> Option<SourceRange> {
let first = tokens.first()?;
let last = tokens.last()?;
Some(SourceRange::new(
first.range.start_offset,
last.range.end_offset() - first.range.start_offset,
))
}