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
use petgraph::{algo::toposort, Directed, Graph};
use solana_libra_types::vm_error::{StatusCode, VMStatus};
use solana_libra_vm::{
access::ModuleAccess,
errors::verification_error,
file_format::{CompiledModule, StructDefinitionIndex, StructHandleIndex, TableIndex},
internals::ModuleIndex,
views::StructDefinitionView,
IndexKind,
};
use std::collections::BTreeMap;
pub struct RecursiveStructDefChecker<'a> {
module: &'a CompiledModule,
}
impl<'a> RecursiveStructDefChecker<'a> {
pub fn new(module: &'a CompiledModule) -> Self {
Self { module }
}
pub fn verify(self) -> Vec<VMStatus> {
let graph_builder = StructDefGraphBuilder::new(self.module);
let graph = graph_builder.build();
match toposort(&graph, None) {
Ok(_) => {
vec![]
}
Err(cycle) => {
let sd_idx = graph[cycle.node_id()];
vec![verification_error(
IndexKind::StructDefinition,
sd_idx.into_index(),
StatusCode::RECURSIVE_STRUCT_DEFINITION,
)]
}
}
}
}
pub struct StructDefGraphBuilder<'a> {
module: &'a CompiledModule,
handle_to_def: BTreeMap<StructHandleIndex, StructDefinitionIndex>,
}
impl<'a> StructDefGraphBuilder<'a> {
pub fn new(module: &'a CompiledModule) -> Self {
let mut handle_to_def = BTreeMap::new();
for (idx, struct_def) in module.struct_defs().iter().enumerate() {
let sh_idx = struct_def.struct_handle;
handle_to_def.insert(sh_idx, StructDefinitionIndex::new(idx as TableIndex));
}
Self {
module,
handle_to_def,
}
}
pub fn build(self) -> Graph<StructDefinitionIndex, (), Directed, u32> {
let mut graph = Graph::new();
let struct_def_count = self.module.struct_defs().len();
let nodes: Vec<_> = (0..struct_def_count)
.map(|idx| graph.add_node(StructDefinitionIndex::new(idx as TableIndex)))
.collect();
for idx in 0..struct_def_count {
let sd_idx = StructDefinitionIndex::new(idx as TableIndex);
for followed_idx in self.member_struct_defs(sd_idx) {
graph.add_edge(nodes[idx], nodes[followed_idx.into_index()], ());
}
}
graph
}
fn member_struct_defs(
&'a self,
idx: StructDefinitionIndex,
) -> impl Iterator<Item = StructDefinitionIndex> + 'a {
let struct_def = self.module.struct_def_at(idx);
let struct_def = StructDefinitionView::new(self.module, struct_def);
let fields = struct_def.fields().into_iter().flatten();
let handle_to_def = &self.handle_to_def;
fields.filter_map(move |field| {
let type_signature = field.type_signature();
let sh_idx = match type_signature.token().struct_index() {
Some(sh_idx) => sh_idx,
None => {
return None;
}
};
match handle_to_def.get(&sh_idx) {
Some(sd_idx) => Some(*sd_idx),
None => {
None
}
}
})
}
}