1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

use super::{
    statement::{self, IRStatement},
    IsIRStatement,
};
use crate::{
    ir::RegisterName,
    utility::{data_type::Type, parsing},
};
use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::multispace0,
    combinator::{map, opt},
    multi::{many0, many1},
    sequence::{pair, tuple},
    IResult,
};
use serde::{Deserialize, Serialize};
use std::fmt;

/// A basic block.
#[derive(Debug, Eq, PartialEq, Clone, Hash, Default, Serialize, Deserialize)]
pub struct BasicBlock {
    /// Name of the basic block.
    pub name: Option<String>,
    /// Statements of the basic block.
    pub content: Vec<IRStatement>,
}

impl BasicBlock {
    pub fn new(name: String) -> Self {
        Self {
            name: Some(name),
            content: Vec::new(),
        }
    }
    /// Append a statement to the basic block.
    pub fn append_statement(&mut self, statement: impl Into<IRStatement>) {
        self.content.push(statement.into());
    }

    /// Whether the basic block is empty.
    pub fn empty(&self) -> bool {
        self.name.is_none() && self.content.is_empty()
    }

    /// Remove a statement from the basic block.
    pub fn remove(&mut self, index: usize) {
        self.content.remove(index);
    }

    pub fn is_branch(&self) -> bool {
        matches!(self.content.last(), Some(IRStatement::Branch(_)))
    }

    pub fn created_registers(&self) -> Vec<(RegisterName, Type)> {
        self.content
            .iter()
            .flat_map(|it| it.generate_register())
            .collect()
    }
}

impl fmt::Display for BasicBlock {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Some(name) = &self.name {
            writeln!(f, "  {name}:")?;
        }
        for statement in &self.content {
            writeln!(f, "    {statement}")?;
        }
        Ok(())
    }
}

/// Parse a basic block's name.
fn parse_tag(code: &str) -> IResult<&str, String> {
    map(pair(parsing::ident, tag(":")), |(name, _)| name)(code)
}

/// Parse the ir code to get a [`BasicBlock`].
pub fn parse(code: &str) -> IResult<&str, BasicBlock> {
    // `Basicblock` which
    //   - Has only a name and no content or
    //   - Has no name but only content
    //  are both valid.
    // However, `(opt(parse_tag), many0(IRStatement::parse))` can match literal nothing, which is not valid.
    // So we need to construct two parsers which stands for these two cases:

    // There is a tag, but the body can be empty.
    let has_tag = tuple((
        map(parse_tag, Some),
        multispace0,
        many0(parsing::in_multispace(statement::parse)),
    ));
    // There is no tag, but there exists at least one statement in the body.
    let has_ir = tuple((
        opt(parse_tag),
        multispace0,
        many1(parsing::in_multispace(statement::parse)),
    ));
    map(alt((has_tag, has_ir)), |(name, _, content)| BasicBlock {
        name,
        content,
    })(code)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn can_parse() {
        let code = "%1 = alloca i32
        store i32 1, address %1
        %2 = alloca i32
        store i32 2, address %2
        %3 = alloca i32
        %4 = load i32 %1
        %5 = load i32 %2
        %6 = add i32 %3, %4";
        let bb = parse(code).unwrap();
        assert_eq!(bb.0, "");
        let code = "WHILE_0_JUDGE:
        %7 = load i32 @g
        blt 0, %7, WHILE_0_TRUE, WHILE_0_FALSE";
        let bb = parse(code).unwrap();
        assert_eq!(bb.0, "");
        let mut multiple_parser = many0(parse);
        let code = "    %1 = alloca i32
    store i32 1, address %1
    %2 = alloca i32
    store i32 2, address %2
    %3 = alloca i32
    %4 = load i32 %1
    %5 = load i32 %2
    %6 = add i32 %3, %4
WHILE_0_JUDGE:
    %7 = load i32 @g
    blt 0, %7, WHILE_0_TRUE, WHILE_0_FALSE
    ";
        let bbs = multiple_parser(code).unwrap();
        assert_eq!(bbs.0.trim(), "");
        assert_eq!(bbs.1.len(), 2);
    }
}