gbf_core/
basic_block.rs

1#![deny(missing_docs)]
2
3use std::{
4    fmt::{self, Write},
5    ops::{Deref, Index},
6    vec,
7};
8
9use serde::{Deserialize, Serialize};
10
11use crate::{
12    cfg_dot::RenderableNode,
13    instruction::Instruction,
14    utils::{
15        GBF_BLUE, GBF_GREEN, GBF_RED, GBF_YELLOW, Gs2BytecodeAddress, OPERAND_TRUNCATE_LENGTH,
16        html_encode,
17    },
18};
19
20/// Represents the type of basic block.
21#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
22pub enum BasicBlockType {
23    /// Used for blocks that are entry blocks of a function.
24    Entry,
25    /// Used for blocks that are exit blocks of a function.
26    Exit,
27    /// Used for blocks that are neither entry nor exit blocks to a function.
28    Normal,
29    /// Used for blocks that are both entry and exit blocks. This is
30    /// possible when a function has a single block, or when a block
31    /// is both the entry and exit block of a function.
32    ///
33    /// Example:
34    /// ```js, no_run
35    /// function onCreated()
36    /// {
37    ///   temp.foo = 1;
38    ///   return temp.foo == 1 ? 1 : 0;
39    /// }
40    /// ```
41    EntryAndExit,
42    /// Special case for a block that is at the end of a module
43    ModuleEnd,
44}
45
46/// Represents the identifier of a basic block.
47#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
48pub struct BasicBlockId {
49    index: usize,
50
51    /// The type of the basic block.
52    pub block_type: BasicBlockType,
53
54    /// The offset of the block
55    pub address: Gs2BytecodeAddress,
56}
57
58/// Represents the edge type between two basic blocks.
59#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
60pub enum BasicBlockConnectionType {
61    /// The connection represents a conditional branch.
62    Conditional,
63
64    /// The edge represents a fallthrough.
65    Fallthrough,
66
67    /// The edge represents an unconditional branch.
68    Unconditional,
69
70    /// The edge represents the start of a "With" block.
71    With,
72
73    /// The edge represents the start of a "ForEach" block.
74    ForEach,
75
76    /// The edge represents a short-circuit
77    ShortCircuit,
78}
79
80/// Represents an edge between two basic blocks.
81#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
82pub struct BasicBlockConnection {
83    /// The type of the connection.
84    pub connection_type: BasicBlockConnectionType,
85}
86
87impl BasicBlockId {
88    /// Create a new `BasicBlockId`.
89    ///
90    /// # Arguments
91    /// - `index`: The index of the basic block in the function.
92    ///
93    /// # Returns
94    /// - A new `BasicBlockId` instance.
95    ///
96    /// Example
97    /// ```
98    /// use gbf_core::basic_block::BasicBlockId;
99    /// use gbf_core::basic_block::BasicBlockType;
100    ///
101    /// let block = BasicBlockId::new(0, BasicBlockType::Normal, 0);
102    /// ```
103    pub fn new(index: usize, block_type: BasicBlockType, offset: Gs2BytecodeAddress) -> Self {
104        Self {
105            index,
106            block_type,
107            address: offset,
108        }
109    }
110}
111
112/// Represents a basic block in a function.
113#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
114pub struct BasicBlock {
115    /// The identifier of the basic block.
116    pub id: BasicBlockId,
117    /// The instructions in the basic block.
118    pub instructions: Vec<Instruction>,
119}
120
121impl BasicBlock {
122    /// Create a new `BasicBlock`.
123    ///
124    /// # Arguments
125    /// - `id`: The `BasicBlockId` of the block.
126    ///
127    /// # Returns
128    /// - A new `BasicBlock` instance.
129    ///
130    /// # Example
131    /// ```
132    /// use gbf_core::basic_block::{BasicBlock, BasicBlockId, BasicBlockType};
133    ///
134    /// let block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 0));
135    /// ```
136    pub fn new(id: BasicBlockId) -> Self {
137        Self {
138            id,
139            instructions: Vec::new(),
140        }
141    }
142
143    /// Add an instruction to the basic block.
144    ///
145    /// # Arguments
146    /// - `instruction`: The instruction to add.
147    ///
148    /// # Example
149    /// ```
150    /// use gbf_core::basic_block::{BasicBlock, BasicBlockId, BasicBlockType};
151    /// use gbf_core::instruction::Instruction;
152    /// use gbf_core::opcode::Opcode;
153    /// use gbf_core::operand::Operand;
154    ///
155    /// let mut block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 0));
156    /// block.add_instruction(Instruction::new_with_operand(Opcode::PushNumber, 0, Operand::new_number(42)));
157    /// ```
158    pub fn add_instruction(&mut self, instruction: Instruction) {
159        self.instructions.push(instruction);
160    }
161
162    /// Gets the last instruction in the block.
163    ///
164    /// # Returns
165    /// - A reference to the last instruction in the block
166    ///
167    /// # Example
168    /// ```
169    /// use gbf_core::basic_block::{BasicBlock, BasicBlockId, BasicBlockType};
170    /// use gbf_core::instruction::Instruction;
171    /// use gbf_core::opcode::Opcode;
172    ///
173    /// let mut block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 0));
174    /// block.add_instruction(Instruction::new(Opcode::PushNumber, 0));
175    /// block.add_instruction(Instruction::new(Opcode::Ret, 1));
176    /// let last_instruction = block.last_instruction();
177    /// assert_eq!(last_instruction.unwrap().opcode, Opcode::Ret);
178    /// ```
179    pub fn last_instruction(&self) -> Option<&Instruction> {
180        self.instructions.last()
181    }
182
183    /// Get the number of instructions in the block.
184    ///
185    /// # Returns
186    /// - The number of instructions in the block.
187    ///
188    /// # Example
189    /// ```
190    /// use gbf_core::basic_block::{BasicBlock, BasicBlockId, BasicBlockType};
191    ///
192    /// let mut block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 0));
193    /// assert_eq!(block.len(), 0);
194    /// ```
195    pub fn len(&self) -> usize {
196        self.instructions.len()
197    }
198
199    /// Check if the block is empty.
200    ///
201    /// # Returns
202    /// - `true` if the block is empty, `false` otherwise.
203    ///
204    /// # Example
205    /// ```
206    /// use gbf_core::basic_block::{BasicBlock, BasicBlockId, BasicBlockType};
207    ///
208    /// let mut block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 0));
209    /// assert!(block.is_empty());
210    /// ```
211    pub fn is_empty(&self) -> bool {
212        self.instructions.is_empty()
213    }
214}
215
216// == Implementations ==
217impl fmt::Display for BasicBlockId {
218    /// Display the `BasicBlockId`.
219    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
220        write!(f, "Block at address 0x{:X}", self.address)
221    }
222}
223
224impl Default for BasicBlockId {
225    /// Create a default `BasicBlockId`.
226    fn default() -> Self {
227        Self {
228            index: 0,
229            block_type: BasicBlockType::Normal,
230            address: 0,
231        }
232    }
233}
234
235/// Implement Deref
236impl Deref for BasicBlock {
237    type Target = Vec<Instruction>;
238
239    /// Get a reference to the instructions in the block.
240    ///
241    /// # Returns
242    /// - A reference to the instructions in the block.
243    fn deref(&self) -> &Self::Target {
244        &self.instructions
245    }
246}
247
248impl Index<usize> for BasicBlock {
249    type Output = Instruction;
250
251    /// Get an instruction by index.
252    ///
253    /// # Arguments
254    /// - `index`: The index of the instruction to get.
255    ///
256    /// # Returns
257    /// - A reference to the instruction at the given index.
258    fn index(&self, index: usize) -> &Self::Output {
259        &self.instructions[index]
260    }
261}
262
263/// IntoIterator implementation immutable reference
264impl<'a> IntoIterator for &'a BasicBlock {
265    type Item = &'a Instruction;
266    type IntoIter = vec::IntoIter<&'a Instruction>;
267
268    /// Get an iterator over the instructions in the block.
269    ///
270    /// # Returns
271    /// - An iterator over the instructions in the block.
272    fn into_iter(self) -> Self::IntoIter {
273        self.instructions.iter().collect::<Vec<_>>().into_iter()
274    }
275}
276
277/// IntoIterator implementation mutable reference
278impl<'a> IntoIterator for &'a mut BasicBlock {
279    type Item = &'a mut Instruction;
280    type IntoIter = vec::IntoIter<&'a mut Instruction>;
281
282    /// Get a mutable iterator over the instructions in the block.
283    ///
284    /// # Returns
285    /// - A mutable iterator over the instructions in the block.
286    fn into_iter(self) -> Self::IntoIter {
287        self.instructions.iter_mut().collect::<Vec<_>>().into_iter()
288    }
289}
290
291impl RenderableNode for BasicBlock {
292    /// Render the block's node representation for Graphviz with customizable padding.
293    ///
294    /// # Arguments
295    ///
296    /// * `padding` - The number of spaces to use for indentation.
297    fn render_node(&self, padding: usize) -> String {
298        let mut label = String::new();
299        let indent = " ".repeat(padding);
300
301        // Start the HTML-like table for Graphviz.
302        writeln!(
303            &mut label,
304            r#"{indent}<TABLE BORDER="0" CELLBORDER="0" CELLSPACING="0" CELLPADDING="0">"#,
305            indent = indent
306        )
307        .unwrap();
308
309        if self.id.block_type == BasicBlockType::ModuleEnd {
310            writeln!(
311                &mut label,
312                r#"{indent}    <TR>
313{indent}        <TD ALIGN="CENTER"><FONT COLOR="{GBF_RED}">Module End</FONT></TD>
314{indent}    </TR>"#,
315                indent = indent
316            )
317            .unwrap();
318        } else {
319            // Render each instruction as a table row with indentation.
320            for inst in &self.instructions {
321                // Get the string of an operand, if it exists, or a space.
322                // If the resulting operand exceeds OPERAND_TRUNCATE_LENGTH,
323                // truncate it and append an ellipsis.
324
325                let operand = inst
326                    .operand
327                    .as_ref()
328                    .map(|op| {
329                        let mut op_str = op.to_string();
330                        if op_str.len() > OPERAND_TRUNCATE_LENGTH {
331                            op_str.truncate(OPERAND_TRUNCATE_LENGTH);
332                            op_str.push_str("...");
333                        }
334
335                        if !op_str.is_empty() {
336                            op_str
337                        } else {
338                            " ".to_string()
339                        }
340                    })
341                    .unwrap_or_else(|| " ".to_string());
342                let operand = html_encode(operand);
343
344                writeln!(
345                    &mut label,
346                    r##"{indent}    <TR>
347{indent}        <TD ALIGN="LEFT"><FONT COLOR="{GBF_GREEN}">{:04X}</FONT></TD>
348{indent}        <TD ALIGN="LEFT">  </TD>
349{indent}        <TD ALIGN="LEFT"><FONT COLOR="{GBF_YELLOW}">{}</FONT></TD>
350{indent}        <TD ALIGN="LEFT">  </TD>
351{indent}        <TD ALIGN="LEFT"><FONT COLOR="{GBF_BLUE}">{} </FONT></TD>
352{indent}    </TR>"##,
353                    inst.address,
354                    inst.opcode,
355                    operand,
356                    indent = indent
357                )
358                .unwrap();
359            }
360        }
361
362        // Close the HTML-like table.
363        writeln!(&mut label, "{indent}</TABLE>", indent = indent).unwrap();
364
365        label
366    }
367}
368
369#[cfg(test)]
370mod tests {
371    use super::*;
372    use crate::{instruction::Instruction, opcode::Opcode, operand::Operand};
373
374    #[test]
375    fn test_basic_block_id_display() {
376        let block = BasicBlockId::new(0, BasicBlockType::Normal, 3);
377        assert_eq!(block.to_string(), "Block at address 0x3");
378    }
379
380    #[test]
381    fn test_basic_block_new() {
382        let block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 4));
383        assert_eq!(block.id.index, 0);
384        assert_eq!(block.id.block_type, BasicBlockType::Normal);
385        assert!(block.instructions.is_empty());
386    }
387
388    #[test]
389    fn test_basic_block_add_instruction() {
390        let mut block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 7));
391        block.add_instruction(Instruction::new_with_operand(
392            Opcode::PushNumber,
393            0,
394            Operand::new_number(42),
395        ));
396        assert_eq!(block.instructions.len(), 1);
397    }
398
399    #[test]
400    fn test_basic_block_len() {
401        let mut block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 32));
402        block.add_instruction(Instruction::new_with_operand(
403            Opcode::PushNumber,
404            0,
405            Operand::new_number(42),
406        ));
407        assert_eq!(block.len(), 1);
408    }
409
410    #[test]
411    fn test_basic_block_is_empty() {
412        let block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 23));
413        assert!(block.is_empty());
414    }
415
416    #[test]
417    fn test_basic_block_into_iter() {
418        let mut block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 11));
419        block.add_instruction(Instruction::new_with_operand(
420            Opcode::PushNumber,
421            0,
422            Operand::new_number(42),
423        ));
424        block.add_instruction(Instruction::new_with_operand(
425            Opcode::PushNumber,
426            1,
427            Operand::new_number(42),
428        ));
429        let mut iter = block.into_iter();
430        assert_eq!(iter.next().unwrap().address, 0);
431        assert_eq!(iter.next().unwrap().address, 1);
432        assert!(iter.next().is_none());
433    }
434
435    #[test]
436    fn test_basic_block_into_iter_ref() {
437        let mut block = BasicBlock::new(BasicBlockId::new(0, BasicBlockType::Normal, 42));
438        block.add_instruction(Instruction::new_with_operand(
439            Opcode::PushNumber,
440            0,
441            Operand::new_number(42),
442        ));
443        block.add_instruction(Instruction::new_with_operand(
444            Opcode::PushNumber,
445            1,
446            Operand::new_number(42),
447        ));
448        let mut iter = block.iter();
449        assert_eq!(iter.next().unwrap().address, 0);
450        assert_eq!(iter.next().unwrap().address, 1);
451        assert!(iter.next().is_none());
452    }
453}
gbf_core/basic_block.rs

gbf_core/
basic_block.rs
