use std::{
cmp::Ordering,
collections::HashMap,
convert::TryInto,
fmt, mem,
ops::{BitAnd, BitOr, Shl, Shr},
};
use crate::{forest::NodeId, Endianness, Ident, Shaped, Value, R};
pub type Expr = crate::Expr<R<usize>>;
pub type TypeExpr = crate::TypeExpr<ExecNodeId, Expr>;
pub type Type = crate::Type<TypeId>;
pub type NodeApp = crate::NodeApp<ExecNodeId, Expr>;
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
pub struct TypeId(usize);
#[derive(Debug, Default)]
pub struct Tree {
nodes: Vec<ExecNode>,
}
#[derive(Debug, Clone)]
pub enum CowValue<'a> {
Syntactic(&'a lexpr::Value),
Decoded(&'a Value),
Owned(Value),
}
impl<'a> PartialEq for CowValue<'a> {
fn eq(&self, other: &CowValue) -> bool {
use CowValue::*;
match (self, other) {
(Syntactic(v1), Syntactic(v2)) => v1 == v2,
(Syntactic(v1), Decoded(v2)) => v1 == v2,
(Syntactic(v1), Owned(v2)) => *v1 == v2,
(Decoded(v1), Decoded(v2)) => v1 == v2,
(Decoded(v1), Owned(v2)) => *v1 == v2,
(Decoded(v1), Syntactic(v2)) => v1 == v2,
(Owned(v1), Owned(v2)) => v1 == v2,
(Owned(v1), Decoded(v2)) => v1 == *v2,
(Owned(v1), Syntactic(v2)) => v1 == *v2,
}
}
}
impl<'a> From<Value> for CowValue<'a> {
fn from(v: Value) -> Self {
CowValue::Owned(v)
}
}
impl<'a> CowValue<'a> {
fn is_true(&self) -> bool {
use CowValue::*;
match self {
Syntactic(v) => match v {
lexpr::Value::Bool(false) => false,
_ => true,
},
Decoded(v) => v.is_true(),
Owned(v) => v.is_true(),
}
}
fn as_u64(&self) -> Option<u64> {
use CowValue::*;
match self {
Syntactic(value) => value.as_u64(),
Decoded(value) => value.as_u64(),
Owned(value) => value.as_u64(),
}
}
fn as_endianness(&self) -> Option<Endianness> {
use CowValue::*;
match self {
Syntactic(value) => match *value {
lexpr::Value::Symbol(sym) => match sym.as_ref() {
"be" => Some(Endianness::Big),
"le" => Some(Endianness::Little),
_ => None,
},
_ => None,
},
Decoded(_) => None,
Owned(_) => None,
}
}
fn to_sexp(&self) -> lexpr::Value {
use CowValue::*;
match self {
Syntactic(value) => (*value).to_owned(),
Decoded(value) => value.to_sexp(),
Owned(_value) => unimplemented!("decoded owned type arguments"),
}
}
}
#[derive(Debug, Clone)]
pub enum EvalError {
ExpectedType(&'static str, Expr),
ResultOutOfRange(&'static str, u64, u64),
UnsupportedIntWidth(u64),
MissingTypeProperty(String),
}
impl EvalError {
fn expected_u64(arg: &Expr) -> Self {
EvalError::ExpectedType("unsigned integer", arg.clone())
}
fn expected_array_len(arg: &Expr) -> Self {
EvalError::ExpectedType("array length", arg.clone())
}
fn unsupported_int_width(width: u64) -> Self {
EvalError::UnsupportedIntWidth(width)
}
fn expected_endianness(arg: &Expr) -> Self {
EvalError::ExpectedType("endianness", arg.clone())
}
fn missing_type_property(property_name: &str) -> Self {
EvalError::MissingTypeProperty(property_name.into())
}
fn result_out_of_range(op: &'static str, n1: u64, n2: u64) -> Self {
EvalError::ResultOutOfRange(op, n1, n2)
}
}
impl fmt::Display for EvalError {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
use EvalError::*;
match self {
ExpectedType(expected, got) => write!(f, "expected {}, got {:?}", expected, got),
UnsupportedIntWidth(n) => write!(f, "unsupported int width {}", n),
ResultOutOfRange(op, n1, n2) => write!(
f,
"result of applying `{}` to {} and {} out range",
op, n1, n2
),
MissingTypeProperty(name) => write!(f, "type is missing property '{}'", name),
}
}
}
impl std::error::Error for EvalError {}
impl NodeApp {
fn eval(&self, tree: &Tree, ctx: &mut DecodeContext) -> Result<TypeId, EvalError> {
let args: Vec<_> = self
.args
.iter()
.map(|arg| eval_expr(arg, tree, ctx).map(|value| value.to_sexp()))
.collect::<Result<_, _>>()?;
Ok(ctx.register_type(self.id, args))
}
}
impl TypeExpr {
fn eval(&self, tree: &Tree, ctx: &mut DecodeContext) -> Result<Type, EvalError> {
use crate::TypeExpr::*;
match self {
U(width, endianness) => {
let (width, endianness) = eval_int_type_args(width, endianness, tree, ctx)?;
Ok(Type::U(width, endianness))
}
ArrayN(n, et) => {
let n = eval_expr(n, tree, ctx)?
.as_u64()
.ok_or_else(|| EvalError::expected_array_len(n))?
.try_into()
.map_err(|_| EvalError::expected_array_len(n))?;
let et = et.eval(tree, ctx)?;
Ok(Type::ArrayN(n, Box::new(et)))
}
ArrayV(et) => {
let et = et.eval(tree, ctx)?;
Ok(Type::ArrayV(Box::new(et)))
}
App(app) => Ok(Type::Ident(app.eval(tree, ctx)?)),
_ => unimplemented!("type expression {:?}", self),
}
}
}
impl Type {
pub fn convert_from(&self, value: &lexpr::Value, ctx: &DecodeContext) -> Option<Value> {
use lexpr::Value::*;
match self {
Type::U(width, _) => match value {
Bool(b) => Some(Value::U32(*b as u32)),
Number(n) => {
if let Some(n) = n.as_u64() {
let required_width = 64 - n.leading_zeros();
if required_width > u32::from(*width) {
None
} else if required_width < 32 {
Some(Value::U32(n as u32))
} else {
Some(Value::U64(n as u64))
}
} else {
None
}
}
_ => None,
},
Type::I(width, _) => match value {
Bool(b) => Some(Value::I32(*b as i32)),
Number(n) => {
if let Some(n) = n.as_i64() {
if *width < 64 {
let min_value = -(1i64 << width);
let max_value = (1i64 << width) - 1;
if n >= min_value && n <= max_value {
Some(Value::from(n))
} else {
None
}
} else {
Some(Value::from(n))
}
} else {
None
}
}
_ => None,
},
Type::ArrayN(n, et) => match value {
Bytes(bytes) => {
let elements: Vec<_> = bytes
.iter()
.map(|&octet| et.convert_from(&lexpr::Value::from(octet), ctx))
.collect::<Option<_>>()?;
if elements.len() != *n {
return None;
}
Some(Value::Array(elements))
}
String(s) => {
let elements: Vec<_> = s
.as_bytes()
.iter()
.map(|&octet| et.convert_from(&lexpr::Value::from(octet), ctx))
.collect::<Option<_>>()?;
if elements.len() != *n {
return None;
}
Some(Value::Array(elements))
}
_ => None,
},
Type::ArrayV(_et) => None,
Type::Ident(_node_id) => None,
}
}
}
fn eval_int_type_args(
width: &Expr,
endianness: &Expr,
tree: &Tree,
ctx: &DecodeContext,
) -> Result<(u8, Endianness), EvalError> {
let width = eval_expr(width, tree, ctx)?
.as_u64()
.ok_or_else(|| EvalError::expected_u64(width))?;
let endianness = eval_expr(endianness, tree, ctx)?
.as_endianness()
.ok_or_else(|| EvalError::expected_endianness(endianness))?;
if width > 128 {
return Err(EvalError::unsupported_int_width(width));
}
Ok((width as u8, endianness))
}
fn eval_expr<'a>(
expr: &'a Expr,
tree: &'a Tree,
ctx: &'a DecodeContext,
) -> Result<CowValue<'a>, EvalError> {
use crate::Expr::*;
match expr {
Ref(r) => match r {
R::Field(field_idx) => {
let value = ctx.value(*field_idx);
Ok(CowValue::Decoded(value))
}
R::Param(param_idx) => Ok(CowValue::Syntactic(&ctx.param_values[*param_idx])),
},
Const(value) => Ok(CowValue::Syntactic(value)),
TypeProperty(type_r, property_name) => match type_r {
R::Param(_param_idx) => unimplemented!(),
R::Field(field_idx) => {
let item = ctx.item(*field_idx);
let property_value = match (&item.ty, &item.value) {
(Type::Ident(_type_id), Value::Shaped(shaped)) => ctx
.lookup_property(&shaped.trace, property_name, tree)
.ok_or_else(|| EvalError::missing_type_property(property_name))?,
_ => {
return Err(EvalError::missing_type_property(property_name));
}
};
Ok(CowValue::Syntactic(property_value))
}
},
Eq(args) => {
let v1 = eval_expr(&args[0], tree, ctx)?;
let v2 = eval_expr(&args[1], tree, ctx)?;
Ok(CowValue::Owned(Value::Bool(v1 == v2)))
}
Not(arg) => Ok(CowValue::Owned(Value::Bool(
!eval_expr(arg, tree, ctx)?.is_true(),
))),
And(args) => {
let mut last = None;
for arg in args {
let value = eval_expr(arg, tree, ctx)?;
if !value.is_true() {
return Ok(value);
}
last = Some(value);
}
if let Some(last) = last {
Ok(last)
} else {
Ok(CowValue::Owned(Value::Bool(true)))
}
}
Or(args) => {
for arg in args {
let value = eval_expr(arg, tree, ctx)?;
if value.is_true() {
return Ok(value);
}
}
Ok(CowValue::Owned(Value::Bool(false)))
}
Add(args) => numeric_binop("+", u64::checked_add, args, tree, ctx)
.map(|n| CowValue::Owned(Value::U64(n))),
Sub(args) => numeric_binop("-", u64::checked_sub, args, tree, ctx)
.map(|n| CowValue::Owned(Value::U64(n))),
Mul(args) => numeric_binop("*", u64::checked_mul, args, tree, ctx)
.map(|n| CowValue::Owned(Value::U64(n))),
BitNot(arg) => {
let n = eval_expr(arg, tree, ctx)?
.as_u64()
.ok_or_else(|| EvalError::expected_u64(arg))?;
Ok(CowValue::Owned(Value::U64(!n)))
}
BitAnd(args) => {
bit_binop(u64::bitand, args, tree, ctx).map(|n| CowValue::Owned(Value::U64(n)))
}
BitOr(args) => {
bit_binop(u64::bitor, args, tree, ctx).map(|n| CowValue::Owned(Value::U64(n)))
}
BitShl(args) => {
bit_binop(u64::shl, args, tree, ctx).map(|n| CowValue::Owned(Value::U64(n)))
}
BitShr(args) => {
bit_binop(u64::shr, args, tree, ctx).map(|n| CowValue::Owned(Value::U64(n)))
}
}
}
fn numeric_binop<F>(
op: &'static str,
f: F,
args: &[Expr; 2],
tree: &Tree,
ctx: &DecodeContext,
) -> Result<u64, EvalError>
where
F: FnOnce(u64, u64) -> Option<u64>,
{
let n1 = eval_expr(&args[0], tree, ctx)?;
let n2 = eval_expr(&args[1], tree, ctx)?;
match (n1.as_u64(), n2.as_u64()) {
(Some(n1), Some(n2)) => f(n1, n2).ok_or_else(|| EvalError::result_out_of_range(op, n1, n2)),
(None, _) => Err(EvalError::expected_u64(&args[0])),
(Some(_), _) => Err(EvalError::expected_u64(&args[1])),
}
}
fn bit_binop<F>(f: F, args: &[Expr; 2], tree: &Tree, ctx: &DecodeContext) -> Result<u64, EvalError>
where
F: FnOnce(u64, u64) -> u64,
{
let n1 = eval_expr(&args[0], tree, ctx)?;
let n2 = eval_expr(&args[1], tree, ctx)?;
match (n1.as_u64(), n2.as_u64()) {
(Some(n1), Some(n2)) => Ok(f(n1, n2)),
(None, _) => Err(EvalError::expected_u64(&args[0])),
(Some(_), _) => Err(EvalError::expected_u64(&args[1])),
}
}
macro_rules! decode_u_octets {
($data:expr, $n_octets:expr, $from_bytes:ident) => {{
let data = $data;
let n_octets = $n_octets;
let value = match n_octets {
1 => Value::U32(data[0].into()),
2 => {
if data.len() < 2 {
return Ok(None);
}
Value::U32(u16::$from_bytes(data[0..2].try_into().unwrap()).into())
}
4 => {
if data.len() < 4 {
return Ok(None);
}
Value::U32(u32::$from_bytes(data[0..4].try_into().unwrap()))
}
8 => {
if data.len() < 8 {
return Ok(None);
}
Value::U64(u64::$from_bytes(data[0..8].try_into().unwrap()))
}
_ => unimplemented!("integer width {} not yet supported", n_octets * 8),
};
Ok(Some((value, usize::from(n_octets) * 8)))
}};
}
impl Tree {
pub fn decode_into(
&self,
ctx: &mut DecodeContext,
node_id: ExecNodeId,
data: &[u8],
start_bit: usize,
) -> Result<Option<usize>, EvalError> {
let node = &self.nodes[node_id.0];
let mut bit_pos = start_bit;
let n_fields_start = ctx.decoded.len();
for app in &node.implications {
let type_id = app.eval(self, ctx)?;
let (node_id, args) = &ctx.type_infos[type_id.0];
let node_id = *node_id;
let mut params = args.clone();
mem::swap(&mut params, &mut ctx.param_values);
let result = self.decode_into(ctx, node_id, data, bit_pos);
mem::swap(&mut params, &mut ctx.param_values);
match result {
Ok(Some(n_bits)) => bit_pos += n_bits,
Ok(None) => {
ctx.backoff(ctx.decoded.len() - n_fields_start);
return Ok(None);
}
Err(e) => {
ctx.backoff(ctx.decoded.len() - n_fields_start);
return Err(e);
}
}
}
let n_implied_fields = ctx.decoded.len() - n_fields_start;
for (i, field) in node.fields.iter().enumerate() {
let ty = field.ty.eval(self, ctx)?;
if let Some((value, n_bits)) = self.decode_as(&ty, data, bit_pos, ctx)? {
if let Some(constant) = field.constant() {
let constant = ty
.convert_from(constant.value(), ctx)
.ok_or_else(|| unimplemented!("type error"))?;
if value != constant {
ctx.backoff(n_implied_fields + i);
return Ok(None);
}
}
let end_bit = bit_pos + n_bits;
ctx.push(ty, value, bit_pos, end_bit);
bit_pos = end_bit;
} else {
ctx.backoff(i);
return Ok(None);
}
}
for (branch_idx, branch) in node.branches.iter().enumerate() {
if eval_expr(&branch.condition, self, ctx)?.is_true() {
ctx.push_branch(branch_idx);
if let Some(n_bits) = self.decode_into(ctx, branch.target, data, bit_pos)? {
return Ok(Some((bit_pos + n_bits) - start_bit));
} else {
ctx.pop_branch();
}
}
}
if node.branches.is_empty() {
Ok(Some(bit_pos - start_bit))
} else {
ctx.backoff(node.fields.len());
Ok(None)
}
}
fn push_node(&mut self, node: ExecNode) -> ExecNodeId {
let id = self.nodes.len();
self.nodes.push(node);
ExecNodeId(id)
}
fn decode_as(
&self,
ty: &Type,
data: &[u8],
bit_pos: usize,
ctx: &DecodeContext,
) -> Result<Option<(Value, usize)>, EvalError> {
let start_octet = bit_pos / 8;
let bit_offset = bit_pos % 8;
match ty {
Type::U(width, endianness) => {
if start_octet >= data.len() {
return Ok(None);
}
if bit_offset == 0 && (width % 8) == 0 {
let n_octets = width / 8;
match endianness {
Endianness::Big => {
decode_u_octets!(&data[start_octet..], n_octets, from_be_bytes)
}
Endianness::Little => {
decode_u_octets!(&data[start_octet..], n_octets, from_le_bytes)
}
Endianness::Native => {
decode_u_octets!(&data[start_octet..], n_octets, from_ne_bytes)
}
}
} else {
let n_bits = usize::from(*width);
match endianness {
Endianness::Big => match n_bits.cmp(&(8 - bit_offset)) {
Ordering::Less => {
let mask = (1 << (8 - bit_offset)) - 1;
let shift = 8 - (n_bits - bit_offset);
Ok(Some((
Value::U32((u32::from(data[start_octet]) & mask) >> shift),
usize::from(*width),
)))
}
Ordering::Equal => {
let mask = (1 << (8 - bit_offset)) - 1;
Ok(Some((
Value::U32(u32::from(data[start_octet]) & mask),
usize::from(*width),
)))
}
Ordering::Greater => {
let mask = (1 << (8 - bit_offset)) - 1;
let mut value =
((u64::from(data[start_octet])) & mask) >> bit_offset;
let mut n_bits = n_bits - (8 - bit_offset);
let mut octet_idx = start_octet + 1;
while n_bits >= 8 {
value <<= 8;
value |= u64::from(data[octet_idx]);
octet_idx += 1;
n_bits -= 8;
}
if n_bits > 0 {
unimplemented!(
"granular big-endianess integer (width {}, {} bits left)",
bit_offset,
n_bits
);
}
Ok(Some((Value::U64(value), usize::from(*width))))
}
},
Endianness::Little => {
unimplemented!(
"granular little-endianness integers (offset {}, width {})",
bit_offset,
width
);
}
Endianness::Native => {
unimplemented!(
"granular native-endianness integers (offset {}, width {})",
bit_offset,
width
);
}
}
}
}
Type::I(_width, _endianness) => unimplemented!(),
Type::ArrayN(n, et) => Ok(self
.decode_array_n(*n, et, data, bit_pos, ctx)?
.map(|(elements, n_bits)| (Value::Array(elements), n_bits))),
Type::ArrayV(et) => Ok(self
.decode_array_v(et, data, bit_pos, ctx)?
.map(|(elements, n_bits)| (Value::Array(elements), n_bits))),
Type::Ident(type_id) => {
let (node_id, args) = &ctx.type_infos[type_id.0];
let mut ctx = DecodeContext::new(*node_id, args.clone());
Ok(self
.decode_into(&mut ctx, *node_id, data, bit_pos)?
.map(|n_bits| (Value::Shaped(ctx.into_shaped()), n_bits)))
}
}
}
fn decode_array_n(
&self,
n: usize,
et: &Type,
data: &[u8],
start_bit: usize,
ctx: &DecodeContext,
) -> Result<Option<(Vec<Value>, usize)>, EvalError> {
let mut elts = Vec::with_capacity(n);
let mut bit_pos = start_bit;
for _ in 0..n {
let (value, n_bits) = match self.decode_as(et, data, bit_pos, ctx)? {
Some(result) => result,
None => return Ok(None),
};
elts.push(value);
bit_pos += n_bits;
}
Ok(Some((elts, bit_pos - start_bit)))
}
fn decode_array_v(
&self,
et: &Type,
data: &[u8],
start_bit: usize,
ctx: &DecodeContext,
) -> Result<Option<(Vec<Value>, usize)>, EvalError> {
let mut elts = Vec::new();
let mut bit_pos = start_bit;
loop {
let (value, n_bits) = match self.decode_as(et, data, bit_pos, ctx)? {
Some(result) => result,
None => return Ok(Some((elts, bit_pos - start_bit))),
};
elts.push(value);
bit_pos += n_bits;
}
}
pub fn follow<'a>(&'a self, node: &'a ExecNode, branch_ids: &'a [usize]) -> BranchIter<'a> {
BranchIter {
tree: self,
node,
branch_ids,
}
}
}
impl std::ops::Index<ExecNodeId> for Tree {
type Output = ExecNode;
fn index(&self, node_id: ExecNodeId) -> &Self::Output {
&self.nodes[node_id.0]
}
}
#[derive(Debug)]
pub struct ExecNode {
node_id: NodeId,
properties: HashMap<String, lexpr::Value>,
implications: Vec<NodeApp>,
fields: Vec<Field>,
branches: Vec<Branch>,
}
#[derive(Debug)]
pub struct Field {
ty: TypeExpr,
constant: Option<lexpr::Datum>,
}
impl Field {
pub fn new(ty: TypeExpr, constant: Option<lexpr::Datum>) -> Self {
Field { ty, constant }
}
pub fn ty(&self) -> &TypeExpr {
&self.ty
}
pub fn constant(&self) -> Option<lexpr::datum::Ref<'_>> {
self.constant.as_ref().map(|datum| datum.as_ref())
}
}
#[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
pub struct ExecNodeId(usize);
impl ExecNode {
pub fn new(
node_id: NodeId,
properties: HashMap<String, lexpr::Value>,
implications: Vec<NodeApp>,
fields: Vec<Field>,
) -> Self {
ExecNode {
properties,
node_id,
implications,
fields,
branches: Vec::new(),
}
}
pub fn property(&self, name: &str) -> Option<&lexpr::Value> {
self.properties.get(name)
}
pub fn node_id(&self) -> NodeId {
self.node_id
}
pub fn fields(&self) -> &[Field] {
&self.fields
}
pub fn branches(&self) -> &[Branch] {
&self.branches
}
}
#[derive(Debug)]
pub struct BranchIter<'a> {
tree: &'a Tree,
node: &'a ExecNode,
branch_ids: &'a [usize],
}
impl<'a> BranchIter<'a> {
pub fn is_empty(&self) -> bool {
self.branch_ids.is_empty()
}
}
impl<'a> Iterator for BranchIter<'a> {
type Item = &'a Branch;
fn next(&mut self) -> Option<Self::Item> {
if let Some((&branch_id, branch_ids)) = self.branch_ids.split_first() {
let branch = &self.node.branches[branch_id];
self.branch_ids = branch_ids;
Some(branch)
} else {
None
}
}
}
#[derive(Debug, Clone)]
pub struct Trace {
pub root_id: ExecNodeId,
pub branch_ids: Vec<usize>,
}
impl Trace {
pub fn new(root_id: ExecNodeId) -> Self {
Trace {
root_id,
branch_ids: Vec::new(),
}
}
pub fn push(&mut self, branch_idx: usize) {
self.branch_ids.push(branch_idx)
}
}
#[derive(Debug)]
pub struct Branch {
pub condition: Expr,
pub target: ExecNodeId,
}
impl Branch {
pub fn new(condition: Expr, target: ExecNodeId) -> Self {
Branch { condition, target }
}
}
#[derive(Debug)]
pub enum ResolveError {
UnknownField(Ident),
}
impl ResolveError {
pub fn unknown_field(field_name: &Ident) -> Self {
ResolveError::UnknownField(field_name.clone())
}
}
impl fmt::Display for ResolveError {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
use ResolveError::*;
match self {
UnknownField(name) => write!(f, "no such field: '{}'", name),
}
}
}
#[derive(Debug, Default)]
pub struct PrepareContext {
roots: HashMap<NodeId, ExecNodeId>,
tree: Tree,
}
impl PrepareContext {
pub fn new() -> Self {
Default::default()
}
pub fn include<E, F>(&mut self, root_id: NodeId, f: F) -> Result<ExecNodeId, E>
where
F: FnOnce(&mut Self) -> Result<ExecNodeId, E>,
{
if let Some(exec_id) = self.roots.get(&root_id) {
Ok(*exec_id)
} else {
let exec_id = f(self)?;
self.roots.insert(root_id, exec_id);
Ok(exec_id)
}
}
pub fn push_node(&mut self, node: ExecNode, is_root: bool) -> ExecNodeId {
let node_id = node.node_id();
let exec_id = self.tree.push_node(node);
if is_root {
self.roots.insert(node_id, exec_id);
}
exec_id
}
pub fn finish(self, root_id: ExecNodeId) -> PreparedRoot {
PreparedRoot {
root_id,
roots: self.roots,
tree: self.tree,
}
}
pub fn set_branches(&mut self, node_id: ExecNodeId, branches: Vec<Branch>) {
self.tree.nodes[node_id.0].branches = branches;
}
}
#[derive(Debug)]
pub struct PreparedRoot {
root_id: ExecNodeId,
roots: HashMap<NodeId, ExecNodeId>,
tree: Tree,
}
impl PreparedRoot {
pub fn nodes(&self) -> std::slice::Iter<'_, ExecNode> {
self.tree.nodes.iter()
}
pub(crate) fn tree(&self) -> &Tree {
&self.tree
}
pub fn decode(
&self,
data: &[u8],
start_bit: usize,
) -> Result<Option<(Shaped, usize)>, EvalError> {
let mut ctx = DecodeContext::new(self.root_id, vec![]);
Ok(self
.tree
.decode_into(&mut ctx, self.root_id, data, start_bit)?
.map(|n_bits| (ctx.into_shaped(), n_bits)))
}
}
#[derive(Debug, Clone, Default)]
pub struct FieldEnv {
resolved: Vec<(Ident, TypeExpr)>,
unresolved: Vec<Ident>,
}
impl FieldEnv {
pub fn new() -> Self {
Default::default()
}
pub fn push_names<'a, T>(&mut self, iter: T)
where
T: IntoIterator<Item = &'a Ident>,
{
self.unresolved.extend(iter.into_iter().cloned());
}
pub fn extend(&mut self, env: FieldEnv) {
assert!(env.unresolved.is_empty());
self.resolved.extend(env.resolved);
}
pub fn truncate(&mut self, n: usize) {
assert!(self.unresolved.is_empty());
self.resolved.truncate(n);
}
pub fn resolve_types<T>(&mut self, types: T) -> usize
where
T: IntoIterator<Item = TypeExpr>,
{
let prev_len = self.resolved.len();
let mut types = types.into_iter();
for ident in self.unresolved.drain(0..) {
let ty = types.next().expect("inconsistemt use of FieldEnv");
self.resolved.push((ident, ty));
}
assert!(self.unresolved.is_empty());
prev_len
}
pub fn find_idx(&self, name: &Ident) -> Option<usize> {
for (i, field_name) in self.unresolved.iter().enumerate().rev() {
if field_name == name {
return Some(self.resolved.len() + i);
}
}
for (i, (field_name, _)) in self.resolved.iter().enumerate().rev() {
if field_name == name {
return Some(i);
}
}
None
}
}
#[derive(Debug)]
pub struct DecodeContext {
param_values: Vec<lexpr::Value>,
type_infos: Vec<(ExecNodeId, Vec<lexpr::Value>)>,
type_ids: HashMap<ExecNodeId, Vec<TypeId>>,
trace: Trace,
decoded: Vec<DecodedItem>,
}
#[derive(Debug, Clone)]
pub struct DecodedItem {
ty: Type,
value: Value,
start_bit: usize,
end_bit: usize,
}
impl DecodedItem {
pub fn ty(&self) -> &Type {
&self.ty
}
pub fn value(&self) -> &Value {
&self.value
}
pub fn start_bit(&self) -> usize {
self.start_bit
}
pub fn end_bit(&self) -> usize {
self.end_bit
}
}
impl DecodeContext {
fn new(root_id: ExecNodeId, param_values: Vec<lexpr::Value>) -> Self {
DecodeContext {
param_values,
type_infos: Vec::new(),
type_ids: HashMap::new(),
decoded: Vec::new(),
trace: Trace::new(root_id),
}
}
fn item(&self, i: usize) -> &DecodedItem {
&self.decoded[i]
}
fn value(&self, i: usize) -> &Value {
&self.decoded[i].value
}
fn backoff(&mut self, n: usize) {
let new_len = self.decoded.len() - n;
self.decoded.truncate(new_len);
}
fn push(&mut self, ty: Type, value: Value, start_bit: usize, end_bit: usize) {
self.decoded.push(DecodedItem {
ty,
value,
start_bit,
end_bit,
});
}
fn push_branch(&mut self, branch_id: usize) {
self.trace.push(branch_id)
}
fn pop_branch(&mut self) {
self.trace
.branch_ids
.pop()
.expect("unbalanced usage of decode context");
}
fn lookup_property<'a>(
&self,
trace: &Trace,
name: &str,
tree: &'a Tree,
) -> Option<&'a lexpr::Value> {
let root_node = &tree[trace.root_id];
let final_branch = tree.follow(root_node, &trace.branch_ids).last().unwrap();
let node = &tree[final_branch.target];
node.property(name)
}
fn register_type(&mut self, node_id: ExecNodeId, args: Vec<lexpr::Value>) -> TypeId {
use std::collections::hash_map::Entry::*;
match self.type_ids.entry(node_id) {
Vacant(vacant) => {
let type_id = TypeId(self.type_infos.len());
self.type_infos.push((node_id, args));
vacant.insert(vec![type_id]);
type_id
}
Occupied(mut occupied) => {
for type_id in occupied.get() {
let (_node_id, registered_args) = &self.type_infos[type_id.0];
if args == *registered_args {
return *type_id;
}
}
let type_id = TypeId(self.type_infos.len());
self.type_infos.push((node_id, args));
occupied.get_mut().push(type_id);
type_id
}
}
}
fn into_shaped(self) -> Shaped {
Shaped {
trace: self.trace,
decoded: self.decoded,
}
}
}