charon_lib/ast/
llbc_ast_utils.rs

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
//! Implementations for [crate::llbc_ast]

use crate::llbc_ast::*;
use crate::meta;
use crate::meta::Span;
use derive_generic_visitor::*;
use std::mem;

/// Combine the span information from a [Switch]
pub fn combine_switch_targets_span(targets: &Switch) -> Span {
    match targets {
        Switch::If(_, st1, st2) => meta::combine_span(&st1.span, &st2.span),
        Switch::SwitchInt(_, _, branches, otherwise) => {
            let branches = branches.iter().map(|b| &b.1.span);
            let mbranches = meta::combine_span_iter(branches);
            meta::combine_span(&mbranches, &otherwise.span)
        }
        Switch::Match(_, branches, otherwise) => {
            let branches = branches.iter().map(|b| &b.1.span);
            let mbranches = meta::combine_span_iter(branches);
            if let Some(otherwise) = otherwise {
                meta::combine_span(&mbranches, &otherwise.span)
            } else {
                mbranches
            }
        }
    }
}

impl Switch {
    pub fn iter_targets(&self) -> impl Iterator<Item = &Block> {
        use itertools::Either;
        match self {
            Switch::If(_, exp1, exp2) => Either::Left([exp1, exp2].into_iter()),
            Switch::SwitchInt(_, _, targets, otherwise) => Either::Right(Either::Left(
                targets.iter().map(|(_, tgt)| tgt).chain([otherwise]),
            )),
            Switch::Match(_, targets, otherwise) => Either::Right(Either::Right(
                targets.iter().map(|(_, tgt)| tgt).chain(otherwise.as_ref()),
            )),
        }
    }

    pub fn iter_targets_mut(&mut self) -> impl Iterator<Item = &mut Block> {
        use itertools::Either;
        match self {
            Switch::If(_, exp1, exp2) => Either::Left([exp1, exp2].into_iter()),
            Switch::SwitchInt(_, _, targets, otherwise) => Either::Right(Either::Left(
                targets.iter_mut().map(|(_, tgt)| tgt).chain([otherwise]),
            )),
            Switch::Match(_, targets, otherwise) => Either::Right(Either::Right(
                targets
                    .iter_mut()
                    .map(|(_, tgt)| tgt)
                    .chain(otherwise.as_mut()),
            )),
        }
    }
}

impl Statement {
    pub fn new(span: Span, content: RawStatement) -> Self {
        Statement {
            span,
            content,
            comments_before: vec![],
        }
    }

    pub fn into_box(self) -> Box<Self> {
        Box::new(self)
    }

    pub fn into_block(self) -> Block {
        Block {
            span: self.span,
            statements: vec![self],
        }
    }
}

impl Block {
    pub fn from_seq(seq: Vec<Statement>) -> Option<Self> {
        if seq.is_empty() {
            None
        } else {
            let span = seq
                .iter()
                .map(|st| st.span)
                .reduce(|a, b| meta::combine_span(&a, &b))
                .unwrap();
            Some(Block {
                span,
                statements: seq,
            })
        }
    }

    pub fn merge(mut self, mut other: Self) -> Self {
        self.span = meta::combine_span(&self.span, &other.span);
        self.statements.append(&mut other.statements);
        self
    }

    pub fn then(mut self, r: Statement) -> Self {
        self.span = meta::combine_span(&self.span, &r.span);
        self.statements.push(r);
        self
    }

    pub fn then_opt(self, other: Option<Statement>) -> Self {
        if let Some(other) = other {
            self.then(other)
        } else {
            self
        }
    }

    /// Apply a function to all the statements, in a top-down manner.
    pub fn visit_statements<F: FnMut(&mut Statement)>(&mut self, f: F) {
        BlockVisitor::new(|_| {}, f).visit(self);
    }

    /// Apply a transformer to all the statements, in a bottom-up manner.
    ///
    /// The transformer should:
    /// - mutate the current statement in place
    /// - return the sequence of statements to introduce before the current statement
    pub fn transform<F: FnMut(&mut Statement) -> Vec<Statement>>(&mut self, mut f: F) {
        self.transform_sequences(|slice| f(&mut slice[0]));
    }

    /// Apply a transformer to all the statements, in a bottom-up manner. Compared to `transform`,
    /// this also gives access to the following statements if any. Statements that are not part of
    /// a sequence will be traversed as `[st]`. Statements that are will be traversed twice: once
    /// as `[st]`, and then as `[st, ..]` with the following statements if any.
    ///
    /// The transformer should:
    /// - mutate the current statements in place
    /// - return the sequence of statements to introduce before the current statements
    pub fn transform_sequences<F: FnMut(&mut [Statement]) -> Vec<Statement>>(&mut self, mut f: F) {
        self.visit_blocks_bwd(|blk: &mut Block| {
            let mut final_len = blk.statements.len();
            let mut to_insert = vec![];
            for i in (0..blk.statements.len()).rev() {
                let new_to_insert = f(&mut blk.statements[i..]);
                final_len += new_to_insert.len();
                to_insert.push((i, new_to_insert));
            }
            if !to_insert.is_empty() {
                to_insert.sort_by_key(|(i, _)| *i);
                // Make it so the first element is always at the end so we can pop it.
                to_insert.reverse();
                // Construct the merged list of statements.
                let old_statements =
                    mem::replace(&mut blk.statements, Vec::with_capacity(final_len));
                for (i, stmt) in old_statements.into_iter().enumerate() {
                    while let Some((j, _)) = to_insert.last()
                        && *j == i
                    {
                        let (_, mut stmts) = to_insert.pop().unwrap();
                        blk.statements.append(&mut stmts);
                    }
                    blk.statements.push(stmt);
                }
            }
        })
    }

    /// Visit `self` and its sub-blocks in a bottom-up (post-order) traversal.
    pub fn visit_blocks_bwd<F: FnMut(&mut Block)>(&mut self, f: F) {
        BlockVisitor::new(f, |_| {}).visit(self);
    }
}

/// Small visitor to visit statements and blocks.
#[derive(Visitor)]
pub struct BlockVisitor<F: FnMut(&mut Block), G: FnMut(&mut Statement)> {
    exit_blk: F,
    enter_stmt: G,
}

impl<F: FnMut(&mut Block), G: FnMut(&mut Statement)> BlockVisitor<F, G> {
    pub fn new(exit_blk: F, enter_stmt: G) -> Self {
        Self {
            exit_blk,
            enter_stmt,
        }
    }
}

impl<F: FnMut(&mut Block), G: FnMut(&mut Statement)> VisitBodyMut for BlockVisitor<F, G> {
    fn exit_llbc_block(&mut self, x: &mut Block) {
        (self.exit_blk)(x)
    }
    fn enter_llbc_statement(&mut self, x: &mut Statement) {
        (self.enter_stmt)(x)
    }
}