1use std::collections::HashMap;
2
3use itertools::Itertools;
4use libafl_bolts::rands::Rand;
5use once_cell::sync::Lazy;
6
7use super::atoms::Function;
8use crate::algebra::atoms::Variable;
9use crate::algebra::dynamic_function::{
10 make_dynamic, DescribableFunction, DynamicFunction, DynamicFunctionShape, FunctionAttributes,
11 TypeShape,
12};
13use crate::algebra::Matcher;
14use crate::protocol::ProtocolTypes;
15use crate::trace::{Query, Source};
16
17pub type FunctionDefinition<PT> = (DynamicFunctionShape<PT>, Box<dyn DynamicFunction<PT>>);
18
19pub struct Signature<PT: ProtocolTypes> {
23 pub functions_by_name: HashMap<&'static str, FunctionDefinition<PT>>,
24 pub functions_by_typ: HashMap<TypeShape<PT>, Vec<FunctionDefinition<PT>>>,
25 pub functions: Vec<FunctionDefinition<PT>>,
26 pub types_by_name: HashMap<&'static str, TypeShape<PT>>,
27 pub attrs_by_name: HashMap<&'static str, FunctionAttributes>,
28 min_cost_by_name: HashMap<&'static str, Cost>,
31 min_cost_by_typ: HashMap<TypeShape<PT>, Cost>,
34 functions_by_typ_by_depth: HashMap<TypeShape<PT>, DepthOrdered<PT>>,
37}
38
39#[derive(Clone, Copy, Debug, PartialEq, Eq)]
41struct Cost {
42 depth: u16,
44 size: usize,
46}
47
48struct DepthOrdered<PT: ProtocolTypes> {
51 functions: Vec<FunctionDefinition<PT>>,
52 costs: Vec<Cost>,
54}
55
56impl<PT: ProtocolTypes> DepthOrdered<PT> {
57 fn choose_within<R: Rand>(
59 &self,
60 depth: u16,
61 size: usize,
62 rand: &mut R,
63 ) -> Option<&FunctionDefinition<PT>> {
64 let deep_enough = self.costs.partition_point(|cost| cost.depth <= depth);
67 let mut seen = 0usize;
68 let mut chosen: Option<usize> = None;
69 for (index, cost) in self.costs[..deep_enough].iter().enumerate() {
70 if cost.size <= size {
71 seen += 1;
72 if rand.below_or_zero(seen) == 0 {
73 chosen = Some(index);
74 }
75 }
76 }
77 chosen.map(|index| &self.functions[index])
78 }
79}
80
81impl<PT: ProtocolTypes> std::fmt::Debug for Signature<PT> {
82 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
83 writeln!(f, "functions; {:?}", self.functions)
84 }
85}
86
87impl<PT: ProtocolTypes> Signature<PT> {
88 #[must_use]
90 pub fn new(definitions: Vec<(FunctionDefinition<PT>, FunctionAttributes)>) -> Self {
91 let attrs_by_name: HashMap<&'static str, FunctionAttributes> = definitions
92 .clone()
93 .iter()
94 .map(|((shape, _dynamic_fn), attrs)| (shape.name, *attrs))
95 .collect();
96 let functions_by_name: HashMap<&'static str, FunctionDefinition<PT>> = definitions
97 .clone()
98 .into_iter()
99 .map(|((shape, dynamic_fn), _attrs)| (shape.name, (shape, dynamic_fn)))
100 .collect();
101
102 let functions_by_typ: HashMap<TypeShape<PT>, Vec<FunctionDefinition<PT>>> = definitions
103 .clone()
104 .into_iter()
105 .map(|(fd, _attrs)| fd)
106 .into_group_map_by(|(shape, _dynamic_fn)| shape.return_type.clone());
107
108 let types_by_name: HashMap<&'static str, TypeShape<PT>> = definitions
109 .clone()
110 .into_iter()
111 .map(|((shape, _dynamic_fn), _attrs)| {
112 let used_types: Vec<TypeShape<PT>> = shape .argument_types
114 .iter()
115 .cloned()
116 .chain(vec![shape.return_type])
117 .collect::<Vec<TypeShape<PT>>>();
118 used_types
119 })
120 .unique()
121 .flatten()
122 .map(|typ| (typ.name, typ))
123 .collect();
124
125 let (min_cost_by_name, min_cost_by_typ) = Self::compute_min_costs(&definitions);
126
127 let functions_by_typ_by_depth = functions_by_typ
128 .iter()
129 .map(|(typ, functions)| {
130 let mut ordered: Vec<(Cost, FunctionDefinition<PT>)> = functions
133 .iter()
134 .filter_map(|function| {
135 min_cost_by_name
136 .get(function.0.name)
137 .map(|cost| (*cost, function.clone()))
138 })
139 .collect();
140 ordered.sort_by_key(|(cost, _)| cost.depth);
141 let (costs, functions) = ordered.into_iter().unzip();
142 (typ.clone(), DepthOrdered { functions, costs })
143 })
144 .collect();
145
146 Self {
147 functions_by_name,
148 functions_by_typ,
149 functions: definitions.into_iter().map(|(fd, _attrs)| fd).collect(),
150 types_by_name,
151 attrs_by_name,
152 min_cost_by_name,
153 min_cost_by_typ,
154 functions_by_typ_by_depth,
155 }
156 }
157
158 fn compute_min_costs(
166 definitions: &[(FunctionDefinition<PT>, FunctionAttributes)],
167 ) -> (HashMap<&'static str, Cost>, HashMap<TypeShape<PT>, Cost>) {
168 use std::collections::hash_map::Entry;
169
170 fn improve<K: Eq + std::hash::Hash>(
173 map: &mut HashMap<K, Cost>,
174 key: K,
175 cost: Cost,
176 ) -> bool {
177 match map.entry(key) {
178 Entry::Vacant(entry) => {
179 entry.insert(cost);
180 true
181 }
182 Entry::Occupied(mut entry) => {
183 let best = Cost {
184 depth: entry.get().depth.min(cost.depth),
185 size: entry.get().size.min(cost.size),
186 };
187 let changed = best != *entry.get();
188 entry.insert(best);
189 changed
190 }
191 }
192 }
193
194 let mut by_name: HashMap<&'static str, Cost> = HashMap::new();
195 let mut by_typ: HashMap<TypeShape<PT>, Cost> = HashMap::new();
196
197 loop {
201 let mut changed = false;
202
203 for ((shape, _dynamic_fn), _attrs) in definitions {
204 let mut cost = Cost { depth: 1, size: 1 };
205 let mut buildable = true;
206 for argument in &shape.argument_types {
207 match by_typ.get(argument) {
208 Some(argument_cost) => {
209 cost.depth = cost.depth.max(argument_cost.depth.saturating_add(1));
210 cost.size = cost.size.saturating_add(argument_cost.size);
211 }
212 None => {
213 buildable = false;
215 break;
216 }
217 }
218 }
219 if !buildable {
220 continue;
221 }
222
223 changed |= improve(&mut by_name, shape.name, cost);
224 changed |= improve(&mut by_typ, shape.return_type.clone(), cost);
225 }
226
227 if !changed {
228 break;
229 }
230 }
231
232 (by_name, by_typ)
233 }
234
235 #[must_use]
243 pub fn min_gen_depth(&self, name: &str) -> Option<u16> {
244 self.min_cost_by_name.get(name).map(|cost| cost.depth)
245 }
246
247 #[must_use]
250 pub fn min_gen_size(&self, name: &str) -> Option<usize> {
251 self.min_cost_by_name.get(name).map(|cost| cost.size)
252 }
253
254 #[must_use]
256 pub fn min_gen_depth_of_type(&self, typ: &TypeShape<PT>) -> Option<u16> {
257 self.min_cost_by_typ.get(typ).map(|cost| cost.depth)
258 }
259
260 #[must_use]
265 pub fn min_gen_size_of_type(&self, typ: &TypeShape<PT>) -> Option<usize> {
266 self.min_cost_by_typ.get(typ).map(|cost| cost.size)
267 }
268
269 pub fn choose_function_within<R: Rand>(
274 &self,
275 typ: &TypeShape<PT>,
276 depth: u16,
277 size: usize,
278 rand: &mut R,
279 ) -> Option<&FunctionDefinition<PT>> {
280 self.functions_by_typ_by_depth
281 .get(typ)?
282 .choose_within(depth, size, rand)
283 }
284
285 pub fn new_function<F: 'static + DescribableFunction<PT, Types>, Types>(
287 f: &'static F,
288 ) -> Function<PT> {
289 let (shape, dynamic_fn) = make_dynamic(f);
290
291 Function::new(shape, dynamic_fn.clone())
292 }
293
294 #[must_use]
295 pub fn new_var_with_type<T: 'static, M: Matcher>(
296 source: Option<Source>,
297 matcher: Option<M>,
298 counter: u16,
299 ) -> Variable<PT>
300 where
301 PT: ProtocolTypes<Matcher = M>,
302 {
303 let type_shape = TypeShape::<PT>::of::<T>();
304 Self::new_var(type_shape, source, matcher, counter)
305 }
306
307 #[must_use]
308 pub fn new_var<M: Matcher>(
309 type_shape: TypeShape<PT>,
310 source: Option<Source>,
311 matcher: Option<M>,
312 counter: u16,
313 ) -> Variable<PT>
314 where
315 PT: ProtocolTypes<Matcher = M>,
316 {
317 let query = Query {
318 source,
319 matcher,
320 counter,
321 };
322 Variable::new(type_shape, query)
323 }
324}
325
326pub type StaticSignature<PT> = Lazy<Signature<PT>>;
327
328pub const fn create_static_signature<PT: ProtocolTypes>(
329 init: fn() -> Signature<PT>,
330) -> StaticSignature<PT> {
331 Lazy::new(init)
332}
333
334#[macro_export]
335macro_rules! define_signature {
336 ($name_signature:ident<$protocol_types:ident>, $($f:path $([$flags:expr])*)+) => {
337 use $crate::algebra::signature::create_static_signature;
338 use $crate::algebra::signature::StaticSignature;
339 use $crate::algebra::signature::Signature;
340
341 #[allow(unused_mut)]
346 pub static $name_signature: StaticSignature<$protocol_types> = create_static_signature(|| {
347
348 let definitions = vec![
349 $(
350 {
351 let mut attrs = FunctionAttributes::default();
352 { $(
354 let flag = stringify!($flags);
355 match flag {
356 "opaque" => attrs.is_opaque = true,
357 "list" => attrs.is_list = true,
358 "get" => attrs.is_get = true,
359 "no_gen" => attrs.no_gen = true,
360 "no_bit" => attrs.no_bit = true,
361 "no_det" => attrs.no_det = true,
362 _ => {},
363 }
364 )*
365 }
366 ($crate::algebra::dynamic_function::make_dynamic(&$f), attrs)
367 }
368 ),+
369 ];
370 Signature::new(definitions)
371 });
372 };
373}