<commit_before>//! This module is for recovering CCFG from RadecoFunction.
//!
//! Usage of this module is to call `c_cfg_builder::recover_simple_ast(rfn)`
//! where `rfn` is an instance of `RadecoFunction`, the function returns an instance of
//! CCFG and we can obtain higher level representation than Radeco IR.

use super::c_ast;
use super::c_ast::Ty;
use super::c_cfg::{CCFGRef, CCFG};
use frontend::radeco_containers::RadecoFunction;
use middle::ir::{MAddress, MOpcode};
use middle::ssa::cfg_traits::CFG;
use middle::ssa::ssa_traits::{SSAWalk, SSA};
use middle::ssa::ssastorage::{NodeData, SSAStorage};
use middle::ssa::utils;
use petgraph::graph::NodeIndex;
use std::collections::{HashMap, HashSet};

fn is_debug() -> bool {
    cfg!(feature = "trace_log")
}

/// This constructs CCFG from an instance of RadecoFunction.
pub fn recover_c_cfg(
    rfn: &RadecoFunction,
    fname_map: &HashMap<u64, String>,
    strings: &HashMap<u64, String>,
) -> CCFG {
    let mut builder = CCFGBuilder::new(rfn, fname_map);
    let data_graph = CCFGDataMap::recover_data(rfn, &mut builder.cfg, strings);
    builder.datamap = data_graph;
    builder.cfg_from_ssa();
    builder.insert_jumps();
    builder.cfg
}

fn ret_value_string(rfn: &RadecoFunction) -> Option<String> {
    let ret_reg_opt = rfn.callconv.clone();
    if ret_reg_opt.is_none() {
        return None;
    }
    ret_reg_opt.unwrap().ret
}

type SSARef = NodeIndex;
// CCFGBuilder constructs CCFG from RadecoFunction
struct CCFGBuilder<'a> {
    cfg: CCFG,
    last_action: CCFGRef,
    rfn: &'a RadecoFunction,
    // SSA of RadecoFunction
    ssa: &'a SSAStorage,
    fname_map: &'a HashMap<u64, String>,
    action_map: HashMap<SSARef, CCFGRef>,
    datamap: CCFGDataMap<'a>,
}

impl<'a> CCFGBuilder<'a> {
    fn new(rfn: &'a RadecoFunction, fname_map: &'a HashMap<u64, String>) -> CCFGBuilder<'a> {
        let cfg = CCFG::new(rfn.name.as_ref());
        CCFGBuilder {
            last_action: cfg.entry,
            cfg: cfg,
            rfn: rfn,
            ssa: rfn.ssa(),
            fname_map: fname_map,
            action_map: HashMap::new(),
            datamap: CCFGDataMap::new(rfn),
        }
    }

    fn basic_block(&mut self) -> CCFGRef {
        self.last_action = self.cfg.basic_block(self.last_action);
        self.last_action
    }

    fn assign(&mut self, dst: CCFGRef, src: CCFGRef) -> CCFGRef {
        self.last_action = self.cfg.assign(dst, src, self.last_action);
        self.last_action
    }

    // Retrieve CCFG's return value node of function call
    fn return_node(&self, call_node: SSARef) -> Option<SSARef> {
        let ret_reg_name_opt = ret_value_string(self.rfn);
        if ret_reg_name_opt.is_none() {
            return None;
        }
        let ret_reg_name = ret_reg_name_opt.unwrap();
        let reg_map = utils::call_rets(call_node, self.ssa);
        for (idx, (node, _)) in reg_map.into_iter() {
            if let Some(name) = self.ssa.regfile.get_name(idx) {
                if name == ret_reg_name {
                    return self.datamap.var_map.get(&node).cloned();
                }
            }
        }
        return None;
    }

    fn args_inorder(&self, call_node: SSARef) -> Vec<SSARef> {
        let call_info = utils::call_info(call_node, self.ssa).expect("This should not be `None`");
        if self.rfn.callconv.is_none() {
            return Vec::new();
        }
        let regs_order = self
            .rfn
            .callconv
            .clone()
            .unwrap()
            .args
            .unwrap_or(Vec::new())
            .into_iter()
            .enumerate()
            .map(|(i, s)| (s, i))
            .collect::<HashMap<_, _>>();
        let mut args = Vec::new();
        let reg_map = call_info.register_args;
        for (idx, node) in reg_map.into_iter() {
            let name = self.ssa.regfile.get_name(idx).unwrap_or("mem").to_string();
            if let Some(&i) = regs_order.get(&name) {
                args.push((i, node));
            }
        }
        args.sort_by_key(|k| k.0);
        args.into_iter().map(|(_, n)| n).collect()
    }

    fn call_action(&mut self, call_node: SSARef) -> CCFGRef {
        let call_info = utils::call_info(call_node, self.ssa).expect("This should not be `None`");
        let callee_node = call_info.target;
        let func_name = {
            if self.datamap.const_nodes.contains(&callee_node) {
                let addr = self.ssa.constant_value(callee_node).unwrap_or(0);
                self.fname_map
                    .get(&addr)
                    .cloned()
                    .unwrap_or("invalid".to_string())
            } else {
                "unknown".to_string()
            }
        };
        let args = self
            .args_inorder(call_node)
            .into_iter()
            .map(|n| {
                self.datamap
                    .var_map
                    .get(&n)
                    .cloned()
                    .unwrap_or(self.cfg.unknown)
            }).collect::<Vec<_>>();
        let ret_val_node = self.return_node(call_node);
        self.last_action =
            self.cfg
                .call_func(&func_name, args.as_slice(), self.last_action, ret_val_node);
        self.last_action
    }

    fn addr_str(&self, node: SSARef) -> String {
        self.ssa
            .address(node)
            .map(|a| format!("{}", a))
            .unwrap_or("unknown".to_string())
    }

    fn recover_action(&mut self, node: SSARef) -> CCFGRef {
        debug_assert!(self.is_recover_action(node));
        let op = self.ssa.opcode(node).unwrap_or(MOpcode::OpInvalid);
        radeco_trace!("CCFGBuilder::recover {:?} @ {:?}", op, node);
        match op {
            MOpcode::OpCall => {
                let ret = self.call_action(node);
                if is_debug() {
                    let addr = self.addr_str(node);
                    let ops_dbg = self.ssa.operands_of(node);
                    self.cfg
                        .debug_info_at(ret, format!("Call {:?} @ {}", ops_dbg, addr));
                }
                ret
            }
            MOpcode::OpStore => {
                let ops = self.ssa.operands_of(node);
                let dst = self
                    .datamap
                    .var_map
                    .get(&ops[1])
                    .map(|&x| self.cfg.derefed_node(x).unwrap_or(x))
                    .unwrap_or(self.cfg.unknown);
                let src = self
                    .datamap
                    .var_map
                    .get(&ops[2])
                    .cloned()
                    .unwrap_or(self.cfg.unknown);
                let ret = self.assign(dst, src);
                if is_debug() {
                    let addr = self.addr_str(node);
                    self.cfg
                        .debug_info_at(ret, format!("*({:?}) = {:?} @ {}", dst, src, addr));
                }
                ret
            }
            _ => unreachable!(),
        }
    }

    fn is_recover_action(&self, node: SSARef) -> bool {
        let op = self.ssa.opcode(node).unwrap_or(MOpcode::OpInvalid);
        match op {
            MOpcode::OpCall | MOpcode::OpStore => true,
            _ => false,
        }
    }

    fn get_block_addr(&self, block: SSARef) -> Option<MAddress> {
        match self.ssa.g[block] {
            NodeData::BasicBlock(addr, _) => Some(addr),
            _ => None,
        }
    }

    fn gen_label(&self, block: SSARef) -> String {
        if let Some(addr) = self.get_block_addr(block) {
            format!("addr_{:}", addr).to_string()
        } else {
            "addr_unknown".to_string()
        }
    }

    fn handle_goto(&mut self, _next: SSARef, succ: SSARef) {
        radeco_trace!("CCFGBuilder::handle goto");
        let next = self
            .action_map
            .get(&_next)
            .cloned()
            .expect("The node should be added to action_map");
        let succ_node = self
            .action_map
            .get(&succ)
            .cloned()
            .expect("This should not be None");
        let label = self.gen_label(succ);
        let goto_node = self.cfg.insert_goto_before(next, succ_node, &label);
        if is_debug() {
            let addr = self.addr_str(_next);
            self.cfg
                .debug_info_at(goto_node, format!("JMP {:?} @ {}", succ_node, addr));
        }
    }

    fn handle_if(
        &mut self,
        _prev: SSARef,
        selector: SSARef,
        true_node: SSARef,
        false_node: SSARef,
    ) {
        radeco_trace!("CCFGBuilder::handle_if");
        let prev = self
            .action_map
            .get(&_prev)
            .and_then(|&n| self.cfg.preds_of(n).first().cloned())
            .expect("This should not be `None`");
        // Add goto statement as `if then` node
        let goto_then = {
            let dst_node = self
                .action_map
                .get(&true_node)
                .cloned()
                .expect("This should not be None");
            // Edge from `unknown` will be removed later.
            let unknown = self.cfg.unknown;
            let label = self.gen_label(true_node);
            self.cfg.add_goto(dst_node, &label, unknown)
        };
        // Add goto statement as `if else` node
        let goto_else = {
            let dst_node = self
                .action_map
                .get(&false_node)
                .cloned()
                .expect("This should not be None");
            // Edge from `unknown` will be removed later.
            let unknown = self.cfg.unknown;
            let label = self.gen_label(false_node);
            self.cfg.add_goto(dst_node, &label, unknown)
        };
        // Add condition node to if statement
        let cond = self
            .datamap
            .var_map
            .get(&selector)
            .cloned()
            .unwrap_or(self.cfg.unknown);
        let if_node = self
            .cfg
            .insert_conditional(cond, goto_then, Some(goto_else), prev);
        if is_debug() {
            let addr = self.addr_str(prev);
            self.cfg
                .debug_info_at(goto_then, format!("IF JMP {:?} @ {}", if_node, addr));
        }
    }

    fn handle_return(&mut self, block: SSARef) {
        let prev = self
            .action_map
            .get(&block)
            .and_then(|&n| self.cfg.preds_of(n).first().cloned())
            .expect("This should not be `None`");
        // TODO specify return value if it exists
        self.cfg.add_return(None, prev);
    }

    fn insert_jump(&mut self, cur_block: SSARef, prev_block: SSARef) {
        if let Some(succ) = self.ssa.unconditional_block(prev_block) {
            if let Some(_) = self.ssa.selector_in(prev_block) {
                // TODO
                radeco_trace!("CCFGBuilder::insert_jump INDIRET JMP");
            } else if self.ssa.exit_node().map_or(false, |en| en == succ) {
                self.handle_return(cur_block);
            } else {
                self.handle_goto(cur_block, succ);
            }
        } else if let Some(blk_cond_info) = self.ssa.conditional_blocks(prev_block) {
            if let Some(selector) = self.ssa.selector_in(prev_block) {
                self.handle_if(
                    cur_block,
                    selector,
                    blk_cond_info.true_side,
                    blk_cond_info.false_side,
                );
            } else {
                radeco_warn!(
                    "block with conditional successors has no selector {:?}",
                    prev_block
                );
            }
        } else {
            radeco_err!("Unreachable node {:?}", prev_block);
        }
    }

    // Insert goto, if statements
    fn insert_jumps(&mut self) {
        let mut last = None;
        let entry_node = entry_node_err!(self.ssa);
        let exit_node = exit_node_err!(self.ssa);
        for cur_node in self.ssa.inorder_walk() {
            if cur_node == entry_node {
                continue;
            }
            if self.ssa.is_action(cur_node) {
                if let Some(prev_block) = last {
                    self.insert_jump(cur_node, prev_block);
                }
                last = Some(cur_node);
            }
        }
        if let Some(prev_block) = last {
            if prev_block != exit_node {
                self.insert_jump(exit_node, prev_block);
            }
        }
    }

    fn cfg_from_ssa(&mut self) {
        for node in self.ssa.inorder_walk() {
            if self.is_recover_action(node) {
                let n = self.recover_action(node);
                self.action_map.insert(node, n);
            } else if self.ssa.is_action(node) {
                let n = self.basic_block();
                self.action_map.insert(node, n);
            };
        }
    }
}

struct CCFGDataMap<'a> {
    rfn: &'a RadecoFunction,
    ssa: &'a SSAStorage,
    // Hashmap from node of SSAStorage to one of self.data_graph
    // a map from node of data_graph to one of CCFG's value
    pub var_map: HashMap<SSARef, CCFGRef>,
    // a map from node of data_graph to one of CCFG's register
    pub reg_map: HashMap<String, CCFGRef>,
    pub const_nodes: HashSet<SSARef>,
    seen: HashSet<SSARef>,
}

impl<'a> CCFGDataMap<'a> {
    fn new(rfn: &'a RadecoFunction) -> CCFGDataMap<'a> {
        CCFGDataMap {
            ssa: rfn.ssa(),
            rfn: rfn,
            var_map: HashMap::new(),
            reg_map: HashMap::new(),
            const_nodes: HashSet::new(),
            seen: HashSet::new(),
        }
    }

    fn recover_data(
        rfn: &'a RadecoFunction,
        ast: &mut CCFG,
        strings: &'a HashMap<u64, String>,
    ) -> Self {
        let mut s = Self::new(rfn);
        s.prepare_consts(ast, strings);
        s.prepare_regs(ast);
        for node in s.ssa.inorder_walk() {
            if s.ssa.is_phi(node) {
                s.handle_phi(node);
            } else if s.ssa.is_expr(node) {
                s.update_values(node, ast);
            }
        }
        s
    }

    fn handle_binop(
        &mut self,
        ret_node: SSARef,
        ops: Vec<SSARef>,
        expr: c_ast::Expr,
        ast: &mut CCFG,
    ) {
        debug_assert!(ops.len() == 2);
        let ops_mapped = ops
            .iter()
            .map(|op| self.var_map.get(op).map(|n| *n).unwrap_or(ast.unknown))
            .collect::<Vec<_>>();
        let expr_node = ast.expr(ops_mapped.as_slice(), expr.clone());
        radeco_trace!(
            "Add {:?} to {:?}, Operator: {:?}",
            ret_node,
            expr_node,
            expr
        );
        self.var_map.insert(ret_node, expr_node);
    }

    fn handle_uniop(&mut self, ret_node: SSARef, op: SSARef, expr: c_ast::Expr, ast: &mut CCFG) {
        if let Some(&n) = self.var_map.get(&op) {
            let expr_node = ast.expr(&[n], expr);
            self.var_map.insert(ret_node, expr_node);
        } else {
            radeco_warn!("Operand not found: {:?}", op);
        }
    }

    fn handle_cast(&mut self, ret_node: SSARef, op: SSARef, expr: c_ast::Expr, ast: &mut CCFG) {
        if self.const_nodes.contains(&op) {
            let cfg_node = self.var_map.get(&op).cloned().unwrap_or(ast.unknown);
            self.var_map.insert(ret_node, cfg_node);
        } else {
            self.handle_uniop(ret_node, op, expr, ast);
        }
    }

    fn deref(&self, node: SSARef, ast: &mut CCFG) -> CCFGRef {
        radeco_trace!("DeRef {:?}", node);
        let n = self.var_map.get(&node).cloned().unwrap_or(ast.unknown);
        ast.deref(n)
    }

    fn handle_phi(&mut self, node: SSARef) {
        debug_assert!(self.ssa.is_phi(node));
        radeco_trace!("CCFGBuilder::handle_phi {:?}", node);
        let ops = self.ssa.operands_of(node);
        // Take first available/mappable node of CCFG's node from phi node
        if let Some(&head) = ops.into_iter().filter_map(|n| self.var_map.get(&n)).next() {
            self.var_map.insert(node, head);
        }
    }

    fn type_from_str(type_str: &str) -> Option<Ty> {
        // TODO More types
        match type_str {
            "int" => Some(Ty::new(c_ast::BTy::Int, true, 0)),
            _ => None,
        }
    }

    fn update_values(&mut self, ret_node: SSARef, ast: &mut CCFG) {
        debug_assert!(self.ssa.is_expr(ret_node));
        radeco_trace!("CCFGBuilder::update_values {:?}", ret_node);
        if self.seen.contains(&ret_node) {
            return;
        }
        self.seen.insert(ret_node);
        // Checking whether `ret_node` is a local variable.
        if let Some(bindings) = self.rfn.local_at(ret_node, true) {
            // TODO add type
            let type_info = Self::type_from_str(&bindings[0].type_str);
            let cfg_node = ast.var(bindings[0].name(), type_info);
            self.var_map.insert(ret_node, cfg_node);
            return;
        }
        let ops = self.ssa.operands_of(ret_node);

        radeco_trace!(
            "CCFGBuilder::update_values opcode: {:?}",
            self.ssa.opcode(ret_node)
        );<commit_msg>WIP impl c_cfg_builder::def_of, c_cfG_builder::op_to_expr<commit_after>//! This module is for recovering CCFG from RadecoFunction.
//!
//! Usage of this module is to call `c_cfg_builder::recover_simple_ast(rfn)`
//! where `rfn` is an instance of `RadecoFunction`, the function returns an instance of
//! CCFG and we can obtain higher level representation than Radeco IR.

use super::c_ast;
use super::c_ast::Ty;
use super::c_cfg::{CCFGRef, CCFG};
use frontend::radeco_containers::RadecoFunction;
use middle::ir::{MAddress, MOpcode};
use middle::ssa::cfg_traits::CFG;
use middle::ssa::ssa_traits::{SSAWalk, SSA};
use middle::ssa::ssastorage::{NodeData, SSAStorage};
use middle::ssa::utils;
use petgraph::graph::NodeIndex;
use std::collections::{HashMap, HashSet};

fn is_debug() -> bool {
    cfg!(feature = "trace_log")
}

/// This constructs CCFG from an instance of RadecoFunction.
pub fn recover_c_cfg(
    rfn: &RadecoFunction,
    fname_map: &HashMap<u64, String>,
    strings: &HashMap<u64, String>,
) -> CCFG {
    let mut builder = CCFGBuilder::new(rfn, fname_map);
    let data_graph = CCFGDataMap::recover_data(rfn, &mut builder.cfg, strings);
    builder.datamap = data_graph;
    builder.cfg_from_ssa();
    builder.insert_jumps();
    builder.cfg
}

fn ret_value_string(rfn: &RadecoFunction) -> Option<String> {
    let ret_reg_opt = rfn.callconv.clone();
    if ret_reg_opt.is_none() {
        return None;
    }
    ret_reg_opt.unwrap().ret
}

type SSARef = NodeIndex;
// CCFGBuilder constructs CCFG from RadecoFunction
struct CCFGBuilder<'a> {
    cfg: CCFG,
    last_action: CCFGRef,
    rfn: &'a RadecoFunction,
    // SSA of RadecoFunction
    ssa: &'a SSAStorage,
    fname_map: &'a HashMap<u64, String>,
    action_map: HashMap<SSARef, CCFGRef>,
    datamap: CCFGDataMap<'a>,
}

impl<'a> CCFGBuilder<'a> {
    fn new(rfn: &'a RadecoFunction, fname_map: &'a HashMap<u64, String>) -> CCFGBuilder<'a> {
        let cfg = CCFG::new(rfn.name.as_ref());
        CCFGBuilder {
            last_action: cfg.entry,
            cfg: cfg,
            rfn: rfn,
            ssa: rfn.ssa(),
            fname_map: fname_map,
            action_map: HashMap::new(),
            datamap: CCFGDataMap::new(rfn),
        }
    }

    fn basic_block(&mut self) -> CCFGRef {
        self.last_action = self.cfg.basic_block(self.last_action);
        self.last_action
    }

    fn assign(&mut self, dst: CCFGRef, src: CCFGRef) -> CCFGRef {
        self.last_action = self.cfg.assign(dst, src, self.last_action);
        self.last_action
    }

    // Retrieve CCFG's return value node of function call
    fn return_node(&self, call_node: SSARef) -> Option<SSARef> {
        let ret_reg_name_opt = ret_value_string(self.rfn);
        if ret_reg_name_opt.is_none() {
            return None;
        }
        let ret_reg_name = ret_reg_name_opt.unwrap();
        let reg_map = utils::call_rets(call_node, self.ssa);
        for (idx, (node, _)) in reg_map.into_iter() {
            if let Some(name) = self.ssa.regfile.get_name(idx) {
                if name == ret_reg_name {
                    return self.datamap.var_map.get(&node).cloned();
                }
            }
        }
        return None;
    }

    fn args_inorder(&self, call_node: SSARef) -> Vec<SSARef> {
        let call_info = utils::call_info(call_node, self.ssa).expect("This should not be `None`");
        if self.rfn.callconv.is_none() {
            return Vec::new();
        }
        let regs_order = self
            .rfn
            .callconv
            .clone()
            .unwrap()
            .args
            .unwrap_or(Vec::new())
            .into_iter()
            .enumerate()
            .map(|(i, s)| (s, i))
            .collect::<HashMap<_, _>>();
        let mut args = Vec::new();
        let reg_map = call_info.register_args;
        for (idx, node) in reg_map.into_iter() {
            let name = self.ssa.regfile.get_name(idx).unwrap_or("mem").to_string();
            if let Some(&i) = regs_order.get(&name) {
                args.push((i, node));
            }
        }
        args.sort_by_key(|k| k.0);
        args.into_iter().map(|(_, n)| n).collect()
    }

    fn call_action(&mut self, call_node: SSARef) -> CCFGRef {
        let call_info = utils::call_info(call_node, self.ssa).expect("This should not be `None`");
        let callee_node = call_info.target;
        let func_name = {
            if self.datamap.const_nodes.contains(&callee_node) {
                let addr = self.ssa.constant_value(callee_node).unwrap_or(0);
                self.fname_map
                    .get(&addr)
                    .cloned()
                    .unwrap_or("invalid".to_string())
            } else {
                "unknown".to_string()
            }
        };
        let args = self
            .args_inorder(call_node)
            .into_iter()
            .map(|n| {
                self.datamap
                    .var_map
                    .get(&n)
                    .cloned()
                    .unwrap_or(self.cfg.unknown)
            }).collect::<Vec<_>>();
        let ret_val_node = self.return_node(call_node);
        self.last_action =
            self.cfg
                .call_func(&func_name, args.as_slice(), self.last_action, ret_val_node);
        self.last_action
    }

    fn addr_str(&self, node: SSARef) -> String {
        self.ssa
            .address(node)
            .map(|a| format!("{}", a))
            .unwrap_or("unknown".to_string())
    }

    fn recover_action(&mut self, node: SSARef) -> CCFGRef {
        debug_assert!(self.is_recover_action(node));
        let op = self.ssa.opcode(node).unwrap_or(MOpcode::OpInvalid);
        radeco_trace!("CCFGBuilder::recover {:?} @ {:?}", op, node);
        match op {
            MOpcode::OpCall => {
                let ret = self.call_action(node);
                if is_debug() {
                    let addr = self.addr_str(node);
                    let ops_dbg = self.ssa.operands_of(node);
                    self.cfg
                        .debug_info_at(ret, format!("Call {:?} @ {}", ops_dbg, addr));
                }
                ret
            }
            MOpcode::OpStore => {
                let ops = self.ssa.operands_of(node);
                let dst = self
                    .datamap
                    .var_map
                    .get(&ops[1])
                    .map(|&x| self.cfg.derefed_node(x).unwrap_or(x))
                    .unwrap_or(self.cfg.unknown);
                let src = self
                    .datamap
                    .var_map
                    .get(&ops[2])
                    .cloned()
                    .unwrap_or(self.cfg.unknown);
                let ret = self.assign(dst, src);
                if is_debug() {
                    let addr = self.addr_str(node);
                    self.cfg
                        .debug_info_at(ret, format!("*({:?}) = {:?} @ {}", dst, src, addr));
                }
                ret
            }
            _ => unreachable!(),
        }
    }

    fn is_recover_action(&self, node: SSARef) -> bool {
        let op = self.ssa.opcode(node).unwrap_or(MOpcode::OpInvalid);
        match op {
            MOpcode::OpCall | MOpcode::OpStore => true,
            _ => false,
        }
    }

    fn get_block_addr(&self, block: SSARef) -> Option<MAddress> {
        match self.ssa.g[block] {
            NodeData::BasicBlock(addr, _) => Some(addr),
            _ => None,
        }
    }

    fn gen_label(&self, block: SSARef) -> String {
        if let Some(addr) = self.get_block_addr(block) {
            format!("addr_{:}", addr).to_string()
        } else {
            "addr_unknown".to_string()
        }
    }

    fn handle_goto(&mut self, _next: SSARef, succ: SSARef) {
        radeco_trace!("CCFGBuilder::handle goto");
        let next = self
            .action_map
            .get(&_next)
            .cloned()
            .expect("The node should be added to action_map");
        let succ_node = self
            .action_map
            .get(&succ)
            .cloned()
            .expect("This should not be None");
        let label = self.gen_label(succ);
        let goto_node = self.cfg.insert_goto_before(next, succ_node, &label);
        if is_debug() {
            let addr = self.addr_str(_next);
            self.cfg
                .debug_info_at(goto_node, format!("JMP {:?} @ {}", succ_node, addr));
        }
    }

    fn handle_if(
        &mut self,
        _prev: SSARef,
        selector: SSARef,
        true_node: SSARef,
        false_node: SSARef,
    ) {
        radeco_trace!("CCFGBuilder::handle_if");
        let prev = self
            .action_map
            .get(&_prev)
            .and_then(|&n| self.cfg.preds_of(n).first().cloned())
            .expect("This should not be `None`");
        // Add goto statement as `if then` node
        let goto_then = {
            let dst_node = self
                .action_map
                .get(&true_node)
                .cloned()
                .expect("This should not be None");
            // Edge from `unknown` will be removed later.
            let unknown = self.cfg.unknown;
            let label = self.gen_label(true_node);
            self.cfg.add_goto(dst_node, &label, unknown)
        };
        // Add goto statement as `if else` node
        let goto_else = {
            let dst_node = self
                .action_map
                .get(&false_node)
                .cloned()
                .expect("This should not be None");
            // Edge from `unknown` will be removed later.
            let unknown = self.cfg.unknown;
            let label = self.gen_label(false_node);
            self.cfg.add_goto(dst_node, &label, unknown)
        };
        // Add condition node to if statement
        let cond = self
            .datamap
            .var_map
            .get(&selector)
            .cloned()
            .unwrap_or(self.cfg.unknown);
        let if_node = self
            .cfg
            .insert_conditional(cond, goto_then, Some(goto_else), prev);
        if is_debug() {
            let addr = self.addr_str(prev);
            self.cfg
                .debug_info_at(goto_then, format!("IF JMP {:?} @ {}", if_node, addr));
        }
    }

    fn handle_return(&mut self, block: SSARef) {
        let prev = self
            .action_map
            .get(&block)
            .and_then(|&n| self.cfg.preds_of(n).first().cloned())
            .expect("This should not be `None`");
        // TODO specify return value if it exists
        self.cfg.add_return(None, prev);
    }

    fn insert_jump(&mut self, cur_block: SSARef, prev_block: SSARef) {
        if let Some(succ) = self.ssa.unconditional_block(prev_block) {
            if let Some(_) = self.ssa.selector_in(prev_block) {
                // TODO
                radeco_trace!("CCFGBuilder::insert_jump INDIRET JMP");
            } else if self.ssa.exit_node().map_or(false, |en| en == succ) {
                self.handle_return(cur_block);
            } else {
                self.handle_goto(cur_block, succ);
            }
        } else if let Some(blk_cond_info) = self.ssa.conditional_blocks(prev_block) {
            if let Some(selector) = self.ssa.selector_in(prev_block) {
                self.handle_if(
                    cur_block,
                    selector,
                    blk_cond_info.true_side,
                    blk_cond_info.false_side,
                );
            } else {
                radeco_warn!(
                    "block with conditional successors has no selector {:?}",
                    prev_block
                );
            }
        } else {
            radeco_err!("Unreachable node {:?}", prev_block);
        }
    }

    // Insert goto, if statements
    fn insert_jumps(&mut self) {
        let mut last = None;
        let entry_node = entry_node_err!(self.ssa);
        let exit_node = exit_node_err!(self.ssa);
        for cur_node in self.ssa.inorder_walk() {
            if cur_node == entry_node {
                continue;
            }
            if self.ssa.is_action(cur_node) {
                if let Some(prev_block) = last {
                    self.insert_jump(cur_node, prev_block);
                }
                last = Some(cur_node);
            }
        }
        if let Some(prev_block) = last {
            if prev_block != exit_node {
                self.insert_jump(exit_node, prev_block);
            }
        }
    }

    fn cfg_from_ssa(&mut self) {
        for node in self.ssa.inorder_walk() {
            if self.is_recover_action(node) {
                let n = self.recover_action(node);
                self.action_map.insert(node, n);
            } else if self.ssa.is_action(node) {
                let n = self.basic_block();
                self.action_map.insert(node, n);
            };
        }
    }
}

struct CCFGDataMap<'a> {
    rfn: &'a RadecoFunction,
    ssa: &'a SSAStorage,
    // Hashmap from node of SSAStorage to one of self.data_graph
    // a map from node of data_graph to one of CCFG's value
    pub var_map: HashMap<SSARef, CCFGRef>,
    // a map from node of data_graph to one of CCFG's register
    pub reg_map: HashMap<String, CCFGRef>,
    pub const_nodes: HashSet<SSARef>,
    seen: HashSet<SSARef>,
}

impl<'a> CCFGDataMap<'a> {
    fn new(rfn: &'a RadecoFunction) -> CCFGDataMap<'a> {
        CCFGDataMap {
            ssa: rfn.ssa(),
            rfn: rfn,
            var_map: HashMap::new(),
            reg_map: HashMap::new(),
            const_nodes: HashSet::new(),
            seen: HashSet::new(),
        }
    }

    fn recover_data(
        rfn: &'a RadecoFunction,
        ast: &mut CCFG,
        strings: &'a HashMap<u64, String>,
    ) -> Self {
        let mut s = Self::new(rfn);
        s.prepare_consts(ast, strings);
        s.prepare_regs(ast);
        for node in s.ssa.inorder_walk() {
            if s.ssa.is_phi(node) {
                s.handle_phi(node);
            } else if s.ssa.is_expr(node) {
                s.update_values(node, ast);
            }
        }
        s
    }

    fn handle_binop(
        &mut self,
        ret_node: SSARef,
        ops: Vec<SSARef>,
        expr: c_ast::Expr,
        ast: &mut CCFG,
    ) {
        debug_assert!(ops.len() == 2);
        let ops_mapped = ops
            .iter()
            .map(|op| self.var_map.get(op).map(|n| *n).unwrap_or(ast.unknown))
            .collect::<Vec<_>>();
        let expr_node = ast.expr(ops_mapped.as_slice(), expr.clone());
        radeco_trace!(
            "Add {:?} to {:?}, Operator: {:?}",
            ret_node,
            expr_node,
            expr
        );
        self.var_map.insert(ret_node, expr_node);
    }

    fn handle_uniop(&mut self, ret_node: SSARef, op: SSARef, expr: c_ast::Expr, ast: &mut CCFG) {
        if let Some(&n) = self.var_map.get(&op) {
            let expr_node = ast.expr(&[n], expr);
            self.var_map.insert(ret_node, expr_node);
        } else {
            radeco_warn!("Operand not found: {:?}", op);
        }
    }

    fn handle_cast(&mut self, ret_node: SSARef, op: SSARef, expr: c_ast::Expr, ast: &mut CCFG) {
        if self.const_nodes.contains(&op) {
            let cfg_node = self.var_map.get(&op).cloned().unwrap_or(ast.unknown);
            self.var_map.insert(ret_node, cfg_node);
        } else {
            self.handle_uniop(ret_node, op, expr, ast);
        }
    }

    fn deref(&self, node: SSARef, ast: &mut CCFG) -> CCFGRef {
        radeco_trace!("DeRef {:?}", node);
        let n = self.var_map.get(&node).cloned().unwrap_or(ast.unknown);
        ast.deref(n)
    }

    fn handle_phi(&mut self, node: SSARef) {
        debug_assert!(self.ssa.is_phi(node));
        radeco_trace!("CCFGBuilder::handle_phi {:?}", node);
        let ops = self.ssa.operands_of(node);
        // Take first available/mappable node of CCFG's node from phi node
        if let Some(&head) = ops.into_iter().filter_map(|n| self.var_map.get(&n)).next() {
            self.var_map.insert(node, head);
        }
    }

    fn type_from_str(type_str: &str) -> Option<Ty> {
        // TODO More types
        match type_str {
            "int" => Some(Ty::new(c_ast::BTy::Int, true, 0)),
            _ => None,
        }
    }

    fn op_to_expr(op: &MOpcode) -> Option<c_ast::Expr> {
        match op {
            MOpcode::OpAdd => c_ast::Expr::Add,
            MOpcode::OpAnd => c_ast::Expr::And,
            MOpcode::OpDiv => c_ast::Expr::Div,
            MOpcode::OpEq => c_ast::Expr::Eq,
            MOpcode::OpGt => c_ast::Expr::Gt,
            MOpcode::OpLsl => c_ast::Expr::Shl,
            MOpcode::OpLsr => c_ast::Expr::Shr,
            MOpcode::OpLt => c_ast::Expr::Lt,
            MOpcode::OpMod => c_ast::Expr::Mod,
            MOpcode::OpMul => c_ast::Expr::Mul,
            MOpcode::OpNot => c_ast::Expr::Not,
            MOpcode::OpOr => c_ast::Expr::Or,
            MOpcode::OpRol => unimplemented!(),
            MOpcode::OpRor => unimplemented!(),
            MOpcode::OpSub => c_ast::Expr::Sub,
            MOpcode::OpXor => c_ast::Expr::Xor,
            // TODO Add `Narrow` info
            MOpcode::OpNarrow(size) => c_ast::Expr::Cast(size as usize),
            // TODO Add `SignExt`
            MOpcode::OpSignExt(size) => c_ast::Expr::Cast(size as usize),
            // TODO Add `ZeroExt`
            MOpcode::OpZeroExt(size) => c_ast::Expr::Cast(size as usize),
            _ => None,
        }
    }

    fn def_of(&self, node: SSARef) -> (c_ast::Expr, Vec<SSARef>) {
        let op = self.ssa.opcode(node).unwrap_or(MOpcode::OpInvalid);
        match (&op, op_to_expr(&op)) {
            (MOpcode::OpStore, None) => unimplemented!(),
            (MOpcode::OpLoad, None) => unimplemented!(),
            (MOpcode::OpNarrow(size), exp)
            | (MOpcode::OpSignExt(size), exp)
            | (MOpcode::OpZeroExt(size), exp) => unimplemented!(),
            (_, exp) if op.is_ternary() => unimplemented!(),
            (_, exp) if op.is_binary() => unimplemented!(),
            (_, exp) if op.is_unary() => unimplemented!(),
            (MOpcode::OpCall, None) => unimplemented!(),
            _ => unimplemented!(),
        }
    }

    fn update_values(&mut self, ret_node: SSARef, ast: &mut CCFG) {
        debug_assert!(self.ssa.is_expr(ret_node));
        radeco_trace!("CCFGBuilder::update_values {:?}", ret_node);
        if self.seen.contains(&ret_node) {
            return;
        }
        self.seen.insert(ret_node);
        // Checking whether `ret_node` is a local variable.
        if let Some(bindings) = self.rfn.local_at(ret_node, true) {
            // TODO add type
            let type_info = Self::type_from_str(&bindings[0].type_str);
            let cfg_node = ast.var(bindings[0].name(), type_info);
            self.var_map.insert(ret_node, cfg_node);
            return;
        }
        let ops = self.ssa.operands_of(ret_node);

        radeco_trace!(
            "CCFGBuilder::update_values opcode: {:?}",
            self.ssa.opcode(ret_node)
        );
{'fraction_non_alphanumeric': 0.13165806967699226, 'fraction_numerical': 0.0009930212672054726, 'mean_word_length': 1.7203421625272004, 'pattern_counts': {'":': 0, '<': 67, '<?xml version=': 0, '>': 151, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '506195', 'n_tokens_mistral': 11855, 'n_tokens_neox': 11721, 'n_words': 2305}