use std::collections::HashMap;
use crate::ast::*;
use crate::source::*;
#[derive(Debug, Clone)]
pub struct Scope {
pub symbol_table: HashMap<String, Symbol>,
pub branch: usize,
}
#[derive(Debug, Clone)]
pub struct Symbol {
pub ty: Type,
pub consume_count: usize,
pub stack_position: usize,
}
pub fn build_symbol_table(
stack_vec: &Vec<StackParam>,
) -> Result<HashMap<String, Symbol>, CompileError> {
let mut symbol_table: HashMap<String, Symbol> = HashMap::new();
let mut has_sig: bool = false;
for (i, stack_item) in stack_vec.iter().enumerate().rev() {
let item = stack_item.to_owned();
if item.ty == Type::Signature {
has_sig = true;
}
if symbol_table.get(&stack_item.identifier.0).is_some() {
return Err(CompileError {
loc: item.loc,
kind: ErrorKind::DuplicateVariable(format!(
"The name of argument cannot be duplicate: {:?} already exists.",
item.identifier.0,
)),
});
}
symbol_table.insert(
item.to_owned().identifier.0,
Symbol {
ty: item.ty,
consume_count: 0,
stack_position: stack_vec.len() - 1 - i, },
);
}
if has_sig {
Ok(symbol_table)
} else {
Err(CompileError {
loc: stack_vec[0].clone().loc,
kind: ErrorKind::NoSigRequired(format!(
"At least one signature required for stack but: {:?}.",
stack_vec,
)),
})
}
}
pub fn analyze(
ast: &Vec<Statement>,
input: Vec<Vec<StackParam>>,
target: &Target,
) -> Result<(), CompileError> {
let mut scope_vec: Vec<Scope> = vec![];
for (branch, stack) in input.iter().enumerate() {
scope_vec.push(Scope {
symbol_table: build_symbol_table(&stack)?,
branch: branch,
});
}
analyze_statement(ast, &mut scope_vec, target, 0)?;
check_flow(ast)?;
for (i, stack) in input.iter().enumerate() {
check_unused_variable(&stack, &scope_vec[i].symbol_table)?;
}
Ok(())
}
pub fn analyze_statement(
ast: &Vec<Statement>,
scope_vec: &mut Vec<Scope>,
target: &Target,
mut branch: usize,
) -> Result<usize, CompileError> {
for stmt in ast {
match stmt {
Statement::LocktimeStatement { loc, operand, op } => {
if matches!(op, LocktimeOp::Csv) {
if *operand < 0 || *operand > u16::MAX as i64 {
return Err(CompileError {
loc: loc.to_owned(),
kind: ErrorKind::IntegerOverflow(format!(
"Relative locktime (older) cannot exceed 65,535 blocks due to BIP 68 limits but got: {}.",
operand
)),
});
}
}
if *operand < 0 || *operand > u32::MAX as i64 {
return Err(CompileError {
loc: loc.to_owned(),
kind: ErrorKind::IntegerOverflow(format!(
"Locktime must be a 32-bit unsigned integer (0-4294967295), but got: {}.",
operand
)),
});
}
}
Statement::VerifyStatement(loc, expr) => {
check_variable(expr, &mut scope_vec[branch].symbol_table)?;
check_type(expr, &mut scope_vec[branch].symbol_table)?;
check_security(expr)?
}
Statement::ExpressionStatement(loc, expr) => {
check_variable(expr, &mut scope_vec[branch].symbol_table)?;
check_type(expr, &mut scope_vec[branch].symbol_table)?;
check_security(expr)?
}
Statement::IfStatement {
loc,
condition_expr,
if_block,
else_block,
} => {
check_variable(condition_expr, &mut scope_vec[branch].symbol_table)?;
check_type(condition_expr, &mut scope_vec[branch].symbol_table)?;
check_security(condition_expr)?;
branch = analyze_statement(&if_block, scope_vec, target, branch)?;
if else_block.is_some() {
branch += 1;
let [before, current]: &mut [Scope; 2] = (&mut scope_vec[branch - 1..=branch])
.try_into()
.expect("Non existing stack look up.");
let before_stack = &mut before.symbol_table;
let current_stack = &mut current.symbol_table;
mark_consumed_stack(before_stack, current_stack)?;
branch = analyze_statement(
else_block.to_owned().unwrap().as_ref(),
scope_vec,
target,
branch,
)?;
}
}
}
}
Ok(branch)
}
pub fn check_unused_variable(
stack_vec: &Vec<StackParam>,
stack_table: &HashMap<String, Symbol>,
) -> Result<(), CompileError> {
for e in stack_vec {
if stack_table
.get(&e.identifier.0)
.is_some_and(|v| v.consume_count == 0)
{
return Err(CompileError {
loc: e.to_owned().loc(),
kind: ErrorKind::UnusedVariable(format!("Variable unused: {:?}.", e.identifier)),
});
}
}
return Ok(());
}
pub fn mark_consumed_stack(
before_stack: &mut HashMap<String, Symbol>,
current_stack: &mut HashMap<String, Symbol>,
) -> Result<(), CompileError> {
for (k, v) in before_stack {
if current_stack.get(k).is_some() {
let consumed_item = current_stack.get(k).unwrap().clone();
current_stack.insert(
k.to_string(),
Symbol {
ty: consumed_item.ty,
consume_count: 1,
stack_position: consumed_item.stack_position,
},
);
}
}
return Ok(());
}
pub fn check_flow(ast: &Vec<Statement>) -> Result<(), CompileError> {
for (i, statement) in ast.iter().enumerate() {
match statement {
Statement::IfStatement { .. } => {
if i != ast.len() - 1 {
let next = ast[i + 1].to_owned();
return Err(CompileError {
loc: next.to_owned().loc(),
kind: ErrorKind::UnreachableCode(format!(
"No statement after if/else block but: {:?}.",
next
)),
});
}
}
Statement::ExpressionStatement(..) => {
if i != ast.len() - 1 {
let next = ast[i + 1].to_owned();
return Err(CompileError {
loc: next.to_owned().loc(),
kind: ErrorKind::UnreachableCode(format!(
"Unreachable code after return statement: {:?}. Move return statement at the last scope of execution path",
next
)),
});
}
}
_ => (),
}
}
let last = ast.last().unwrap().to_owned();
match last {
Statement::IfStatement {
if_block,
else_block,
..
} => {
check_flow(&if_block)?;
if else_block.is_some() {
check_flow(&else_block.unwrap())?;
}
}
Statement::ExpressionStatement(..) => (),
_ => {
return Err(CompileError {
loc: last.to_owned().loc(),
kind: ErrorKind::NoReturn(format!(
"Return statement must exist for each possible execution path: {:?}.",
last
)),
});
}
}
Ok(())
}
pub fn check_variable(
expression: &Expression,
symbol_table: &mut HashMap<String, Symbol>,
) -> Result<(), CompileError> {
match expression {
Expression::Variable(loc, id) => {
let id_string = id.0.to_owned();
if symbol_table.get(&id_string).is_none() {
return Err(CompileError {
loc: expression.to_owned().loc(),
kind: ErrorKind::UndefinedVariable(format!(
"Undefined variable: {:?}.",
id_string
)),
});
}
let item = symbol_table.get(&id_string).unwrap().to_owned();
if item.consume_count != 0 {
return Err(CompileError {
loc: expression.to_owned().loc(),
kind: ErrorKind::VariableConsumed(format!(
"Consumed variable: {:?}.",
id_string
)),
});
}
let is_invalid_consumption_order = symbol_table
.values()
.any(|v| v.stack_position < item.stack_position && v.consume_count == 0);
if is_invalid_consumption_order {
return Err(CompileError {
loc: expression.to_owned().loc(),
kind: ErrorKind::InvalidConsumptionOrder(format!(
"Invalid Variable Consumption Order: {:?}th {:?} is used despite of preceding unused variable.",
item.stack_position,
id_string,
)),
});
}
symbol_table.insert(
id_string,
Symbol {
ty: item.ty,
consume_count: 1,
stack_position: item.stack_position,
},
);
Ok(())
}
Expression::CheckSigExpression {
loc: _,
operand,
op: _,
} => match &**operand {
Factor::SingleSigFactor {
loc: _,
sig,
pubkey,
} => {
check_variable(&sig, symbol_table)?;
check_variable(&pubkey, symbol_table)
}
Factor::MultiSigFactor { loc: _, m: _, n } => {
for factor in n {
match factor {
Factor::SingleSigFactor {
loc: _,
sig,
pubkey,
} => {
check_variable(&sig, symbol_table)?;
check_variable(&pubkey, symbol_table)?
}
_ => continue,
}
}
return Ok(());
}
},
Expression::UnaryCryptoExpression {
loc: _,
operand,
op,
} => check_variable(&operand, symbol_table),
Expression::LogicalExpression {
loc: _,
lhs,
op,
rhs,
} => {
check_variable(&lhs, symbol_table)?;
check_variable(&rhs, symbol_table)
}
Expression::CompareExpression {
loc: _,
lhs,
op,
rhs,
} => {
check_variable(&lhs, symbol_table)?;
check_variable(&rhs, symbol_table)
}
Expression::UnaryMathExpression {
loc: _,
operand,
op,
} => check_variable(&operand, symbol_table),
Expression::BinaryMathExpression {
loc: _,
lhs,
op,
rhs,
} => {
check_variable(&lhs, symbol_table)?;
check_variable(&rhs, symbol_table)
}
Expression::ByteExpression {
loc: _,
operand,
op: _,
} => check_variable(&operand, symbol_table),
_ => Ok(()),
}
}
pub fn check_type(
expression: &Expression,
symbol_table: &HashMap<String, Symbol>,
) -> Result<(), CompileError> {
match expression {
Expression::CheckSigExpression {
loc: _,
operand,
op: _,
} => match &**operand {
Factor::SingleSigFactor {
loc: _,
sig,
pubkey,
} => check_type_sig_pubkey(sig, pubkey, symbol_table),
Factor::MultiSigFactor { loc: _, m: _, n } => {
for factor in n {
match factor {
Factor::SingleSigFactor {
loc: _,
sig,
pubkey,
} => check_type_sig_pubkey(sig, pubkey, symbol_table)?,
_ => continue,
}
}
return Ok(());
}
},
Expression::LogicalExpression {
loc: _,
lhs,
op,
rhs,
} => {
check_type_numeric(lhs, symbol_table)?;
check_type_numeric(rhs, symbol_table)
}
Expression::CompareExpression { loc, lhs, op, rhs } => {
if check_type_string(&lhs, symbol_table).is_ok()
&& check_type_string(&rhs, symbol_table).is_ok()
{
if *op != BinaryCompareOp::Equal && *op != BinaryCompareOp::NotEqual {
return Err(CompileError {
loc: loc.to_owned(),
kind: ErrorKind::InvalidOperation(format!(
"Compare opeation for string must be either == or != but: {:?}.",
op
)),
});
}
return Ok(());
}
if check_type_numeric(&lhs, symbol_table).is_ok()
&& check_type_numeric(&rhs, symbol_table).is_ok()
{
return Ok(());
}
Err(CompileError {
loc: loc.to_owned(),
kind: ErrorKind::InvalidOperation(format!(
"Compare type must be same but: {:?} to {:?}.",
lhs, rhs
)),
})
}
Expression::UnaryMathExpression {
loc: _,
operand,
op,
} => check_type_numeric(&operand, symbol_table),
Expression::BinaryMathExpression {
loc: _,
lhs,
op,
rhs,
} => {
check_type_numeric(&lhs, symbol_table)?;
check_type_numeric(&rhs, symbol_table)
}
Expression::ByteExpression {
loc: _,
operand,
op: _,
} => {
check_type_string(&operand, symbol_table)?;
match *operand.to_owned() {
Expression::StringLiteral(loc, val) => {
if !(val.is_ascii()) {
return Err(CompileError {
loc: loc,
kind: ErrorKind::InvalidOperation(format!(
"Operand must be ascii string but: {:?}.",
val,
)),
});
}
Ok(())
}
_ => Ok(()),
}
}
_ => Ok(()),
}
}
pub fn check_type_numeric(
expression: &Expression,
symbol_table: &HashMap<String, Symbol>,
) -> Result<(), CompileError> {
match expression.to_owned() {
Expression::UnaryCryptoExpression { loc, .. } => {
return Err(CompileError {
loc: loc,
kind: ErrorKind::InvalidOperation(format!(
"Operand must be number or boolean but: {:?}.",
expression,
)),
});
}
Expression::StringLiteral(loc, ..) => {
return Err(CompileError {
loc: loc,
kind: ErrorKind::InvalidOperation(format!(
"Operand must be number or boolean but: {:?}.",
expression,
)),
});
}
Expression::Variable(loc, id) => {
let id_string = id.0.to_owned();
let var_type = symbol_table.get(&id_string).unwrap().ty.to_owned();
if var_type == Type::Signature || var_type == Type::String {
return Err(CompileError {
loc: loc,
kind: ErrorKind::InvalidOperation(format!(
"Operand must be number or boolean but: {:?}.",
expression,
)),
});
}
Ok(())
}
Expression::ByteExpression { loc, operand, op } => check_type(&expression, symbol_table),
Expression::CheckSigExpression { loc, operand, op } => {
check_type(&expression, symbol_table)
}
Expression::CompareExpression { loc, lhs, op, rhs } => {
check_type(&expression, symbol_table)
}
Expression::LogicalExpression { loc, lhs, op, rhs } => {
check_type_numeric(&lhs, symbol_table)?;
check_type_numeric(&rhs, symbol_table)
}
Expression::BinaryMathExpression { loc, lhs, op, rhs } => {
check_type_numeric(&lhs, symbol_table)?;
check_type_numeric(&rhs, symbol_table)
}
Expression::UnaryMathExpression { loc, operand, op } => {
check_type_numeric(&operand, symbol_table)
}
_ => Ok(()),
}
}
pub fn check_type_string(
expression: &Expression,
symbol_table: &HashMap<String, Symbol>,
) -> Result<(), CompileError> {
match expression.to_owned() {
Expression::StringLiteral(loc, val) => Ok(()),
Expression::UnaryCryptoExpression { .. } => Ok(()),
Expression::Variable(loc, id) => {
let id_string = id.0.to_owned();
let var_type = symbol_table.get(&id_string).unwrap().ty.to_owned();
if var_type == Type::Boolean || var_type == Type::Number {
return Err(CompileError {
loc: loc,
kind: ErrorKind::InvalidOperation(format!(
"Operand must be string but: {:?}.",
expression,
)),
});
}
Ok(())
}
_ => {
return Err(CompileError {
loc: expression.to_owned().loc(),
kind: ErrorKind::InvalidOperation(format!(
"Operand must be string but: {:?}.",
expression,
)),
});
}
}
}
pub fn check_type_sig_pubkey(
sig: &Expression,
pubkey: &Expression,
symbol_table: &HashMap<String, Symbol>,
) -> Result<(), CompileError> {
match sig {
Expression::Variable(loc, id) => {
let id_string = id.0.to_owned();
let var_type = symbol_table.get(&id_string).unwrap().ty.to_owned();
if var_type != Type::Signature {
return Err(CompileError {
loc: sig.to_owned().loc(),
kind: ErrorKind::InvalidOperation(format!(
"Signature must be type of signature but: {:?}.",
sig,
)),
});
}
}
_ => {
return Err(CompileError {
loc: sig.to_owned().loc(),
kind: ErrorKind::TypeMismatch(format!(
"Signature must be from arguments but: {:?}.",
sig
)),
});
}
};
match pubkey {
Expression::StringLiteral(loc, data) => {
let hex_pubkey = hex::decode(&data);
if hex_pubkey.is_ok() {
let pubkey_bytes = hex_pubkey.unwrap();
if bitcoin::XOnlyPublicKey::from_slice(
if pubkey_bytes.len() == 33 && (pubkey_bytes[0] == 2 || pubkey_bytes[0] == 3) {
&pubkey_bytes[1..]
} else {
&pubkey_bytes
},
)
.is_ok()
{
return Ok(());
}
}
Err(CompileError {
loc: loc.to_owned(),
kind: ErrorKind::MalformedPubkey(format!("Public key is malformed: {:?}.", data)),
})
}
_ => {
return Err(CompileError {
loc: pubkey.to_owned().loc(),
kind: ErrorKind::TypeMismatch(format!(
"Public Key must be from string literal but: {:?}.",
pubkey
)),
});
}
}
}
pub fn check_security(expression: &Expression) -> Result<(), CompileError> {
check_overflow(expression)?;
check_useless_sig(expression)?;
match expression {
Expression::BinaryMathExpression { loc, lhs, op, rhs } => {
check_security(&lhs)?;
check_security(&rhs)?;
}
Expression::ByteExpression { loc, operand, op } => {
check_security(&operand)?;
}
Expression::CompareExpression { loc, lhs, op, rhs } => {
check_security(&lhs)?;
check_security(&rhs)?;
}
Expression::LogicalExpression { loc, lhs, op, rhs } => {
check_security(&lhs)?;
check_security(&rhs)?;
}
Expression::UnaryMathExpression { loc, operand, op } => {
check_security(&operand)?;
}
Expression::UnaryCryptoExpression { loc, operand, op } => {
check_security(&operand)?;
}
_ => (),
}
Ok(())
}
pub fn check_overflow(expression: &Expression) -> Result<(), CompileError> {
match expression.to_owned() {
Expression::NumberLiteral(loc, val) => {
if val > i32::MAX as i64 || val <= i32::MIN as i64 {
return Err(CompileError {
loc: loc,
kind: ErrorKind::IntegerOverflow(format!(
"Number is 32 bit sign magnitude int: {:?}.",
val,
)),
});
}
Ok(())
}
_ => Ok(()),
}
}
pub fn check_useless_sig(expression: &Expression) -> Result<(), CompileError> {
match expression.to_owned() {
Expression::UnaryMathExpression { loc, operand, op } => {
if op == UnaryMathOp::Not && matches!(*operand, Expression::CheckSigExpression { .. }) {
return Err(CompileError {
loc: loc,
kind: ErrorKind::UselessSig(format!(
"! makes checksig operation useless: {:?}.",
expression,
)),
});
}
Ok(())
}
_ => Ok(()),
}
}
pub fn check_consensus() {}
pub fn check_fee() {}