1use crate::{
2 DynSolType, DynSolValue, Error, Result, Specifier, eip712::typed_data::Eip712Types,
3 eip712_parser::EncodeType,
4};
5use alloc::{
6 borrow::ToOwned,
7 collections::{BTreeMap, BTreeSet},
8 string::{String, ToString},
9 vec::Vec,
10};
11use alloy_primitives::{B256, keccak256};
12use alloy_sol_types::SolStruct;
13use core::{cmp::Ordering, fmt};
14use parser::{RootType, TypeSpecifier, TypeStem};
15use serde::{Deserialize, Deserializer, Serialize};
16
17#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize)]
19pub struct PropertyDef {
20 #[serde(rename = "type")]
22 type_name: String,
23 name: String,
25}
26
27impl<'de> Deserialize<'de> for PropertyDef {
28 fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
29 #[derive(Deserialize)]
30 struct PropertyDefHelper {
31 #[serde(rename = "type")]
32 type_name: String,
33 name: String,
34 }
35 let h = PropertyDefHelper::deserialize(deserializer)?;
36 Self::new(h.type_name, h.name).map_err(serde::de::Error::custom)
37 }
38}
39
40impl PropertyDef {
41 #[inline]
43 pub fn new<T, N>(type_name: T, name: N) -> Result<Self>
44 where
45 T: Into<String>,
46 N: Into<String>,
47 {
48 let type_name = type_name.into();
49 TypeSpecifier::parse_eip712(type_name.as_str())?;
50 Ok(Self::new_unchecked(type_name, name))
51 }
52
53 #[inline]
56 pub fn new_unchecked<T, N>(type_name: T, name: N) -> Self
57 where
58 T: Into<String>,
59 N: Into<String>,
60 {
61 Self { type_name: type_name.into(), name: name.into() }
62 }
63
64 #[inline]
66 pub fn name(&self) -> &str {
67 &self.name
68 }
69
70 #[inline]
72 pub fn type_name(&self) -> &str {
73 &self.type_name
74 }
75
76 #[inline]
78 pub fn root_type_name(&self) -> &str {
79 self.type_name.split_once('[').map(|t| t.0).unwrap_or(&self.type_name)
80 }
81}
82
83#[derive(Clone, Debug, PartialEq, Eq, Hash)]
85pub struct TypeDef {
86 type_name: String,
88 props: Vec<PropertyDef>,
90}
91
92impl Ord for TypeDef {
93 fn cmp(&self, other: &Self) -> Ordering {
96 self.type_name.cmp(&other.type_name)
97 }
98}
99
100impl PartialOrd for TypeDef {
101 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
102 Some(self.cmp(other))
103 }
104}
105
106impl fmt::Display for TypeDef {
107 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108 self.fmt_eip712_encode_type(f)
109 }
110}
111
112impl TypeDef {
113 #[inline]
116 pub fn new<S: Into<String>>(type_name: S, props: Vec<PropertyDef>) -> Result<Self> {
117 let type_name = type_name.into();
118 RootType::parse_eip712(type_name.as_str())?;
119 Ok(Self { type_name, props })
120 }
121
122 #[inline]
125 pub const fn new_unchecked(type_name: String, props: Vec<PropertyDef>) -> Self {
126 Self { type_name, props }
127 }
128
129 #[inline]
131 pub fn type_name(&self) -> &str {
132 &self.type_name
133 }
134
135 #[inline]
137 pub fn props(&self) -> &[PropertyDef] {
138 &self.props
139 }
140
141 #[inline]
143 pub fn prop_names(&self) -> impl Iterator<Item = &str> + '_ {
144 self.props.iter().map(|p| p.name())
145 }
146
147 #[inline]
149 pub fn prop_root_types(&self) -> impl Iterator<Item = &str> + '_ {
150 self.props.iter().map(|p| p.root_type_name())
151 }
152
153 #[inline]
155 pub fn prop_types(&self) -> impl Iterator<Item = &str> + '_ {
156 self.props.iter().map(|p| p.type_name())
157 }
158
159 #[inline]
161 pub fn eip712_encode_type(&self) -> String {
162 let mut s = String::with_capacity(self.type_name.len() + 2 + self.props_bytes_len());
163 self.fmt_eip712_encode_type(&mut s).unwrap();
164 s
165 }
166
167 pub fn fmt_eip712_encode_type(&self, f: &mut impl fmt::Write) -> fmt::Result {
170 f.write_str(&self.type_name)?;
171 f.write_char('(')?;
172 for (i, prop) in self.props.iter().enumerate() {
173 if i > 0 {
174 f.write_char(',')?;
175 }
176
177 f.write_str(prop.type_name())?;
178 f.write_char(' ')?;
179 f.write_str(prop.name())?;
180 }
181 f.write_char(')')
182 }
183
184 #[inline]
187 pub fn props_bytes_len(&self) -> usize {
188 self.props.iter().map(|p| p.type_name.len() + p.name.len() + 2).sum()
189 }
190
191 #[inline]
193 pub fn root_type(&self) -> RootType<'_> {
194 self.type_name.as_str().try_into().expect("checked in instantiation")
195 }
196}
197
198#[derive(Debug, Default)]
199struct DfsContext<'a> {
200 visited: BTreeSet<&'a TypeDef>,
201 stack: BTreeSet<&'a str>,
202}
203
204#[derive(Clone, Debug, Default, PartialEq, Eq)]
208pub struct Resolver {
209 nodes: BTreeMap<String, TypeDef>,
214 edges: BTreeMap<String, Vec<String>>,
217}
218
219impl Serialize for Resolver {
220 #[inline]
221 fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
222 Eip712Types::from(self).serialize(serializer)
223 }
224}
225
226impl<'de> Deserialize<'de> for Resolver {
227 #[inline]
228 fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
229 Eip712Types::deserialize(deserializer).map(Into::into)
230 }
231}
232
233impl From<Eip712Types> for Resolver {
234 fn from(types: Eip712Types) -> Self {
235 Self::from(&types)
236 }
237}
238
239impl From<&Eip712Types> for Resolver {
240 #[inline]
241 fn from(types: &Eip712Types) -> Self {
242 let mut graph = Self::default();
243 graph.ingest_types(types);
244 graph
245 }
246}
247
248impl From<&Resolver> for Eip712Types {
249 fn from(resolver: &Resolver) -> Self {
250 let mut types = Self::default();
251 for (name, ty) in &resolver.nodes {
252 types.insert(name.clone(), ty.props.clone());
253 }
254 types
255 }
256}
257
258impl Resolver {
259 pub fn from_struct<S: SolStruct>() -> Self {
261 let mut resolver = Self::default();
262 resolver.ingest_sol_struct::<S>();
263 resolver
264 }
265
266 fn detect_cycle(&self, type_name: &str) -> Result<()> {
268 match self.detect_cycle_inner(type_name, &mut DfsContext::default()) {
269 true => Err(Error::circular_dependency(type_name)),
270 false => Ok(()),
271 }
272 }
273
274 fn detect_cycle_inner<'a>(&'a self, type_name: &str, context: &mut DfsContext<'a>) -> bool {
275 let Some(ty) = self.nodes.get(type_name) else { return false };
276
277 if context.stack.contains(type_name) {
279 return true;
280 }
281 if !context.visited.insert(ty) {
283 return false;
284 }
285
286 let edges = self.edges(ty);
287 if !edges.is_empty() {
288 context.stack.insert(&ty.type_name);
289 for edge in edges {
290 if self.detect_cycle_inner(edge, context) {
291 return true;
292 }
293 }
294 context.stack.remove(type_name);
295 }
296
297 false
298 }
299
300 pub fn ingest_string(&mut self, s: impl AsRef<str>) -> Result<()> {
302 let encode_type: EncodeType<'_> = s.as_ref().try_into()?;
303 for t in encode_type.types {
304 self.ingest(t.to_owned());
305 }
306 Ok(())
307 }
308
309 pub fn ingest_sol_struct<S: SolStruct>(&mut self) {
311 self.ingest_string(S::eip712_encode_type()).unwrap();
312 }
313
314 pub fn ingest(&mut self, type_def: TypeDef) {
316 let type_name = type_def.type_name.to_owned();
317
318 let entry = self.edges.entry(type_name.clone()).or_default();
320 for prop in &type_def.props {
321 entry.push(prop.root_type_name().to_owned());
322 }
323
324 self.nodes.insert(type_name, type_def);
326 }
327
328 pub fn ingest_types(&mut self, types: &Eip712Types) {
330 for (type_name, props) in types {
331 if let Ok(ty) = TypeDef::new(type_name.clone(), props.to_vec()) {
332 self.ingest(ty);
333 }
334 }
335 }
336
337 fn linearize_into<'a>(
339 &'a self,
340 resolution: &mut Vec<&'a TypeDef>,
341 root_type: &str,
342 ) -> Result<()> {
343 let this_type = match self.nodes.get(root_type) {
344 Some(ty) => ty,
345 None if RootType::parse_eip712(root_type)
346 .is_ok_and(|rt| rt.try_basic_solidity().is_ok()) =>
347 {
348 return Ok(());
349 }
350 None => return Err(Error::missing_type(root_type)),
351 };
352 if !resolution.contains(&this_type) {
353 resolution.push(this_type);
354 for edge in self.edges(this_type) {
355 self.linearize_into(resolution, edge)?;
356 }
357 }
358
359 Ok(())
360 }
361
362 pub fn linearize(&self, type_name: &str) -> Result<Vec<&TypeDef>> {
364 self.detect_cycle(type_name)?;
365 let mut resolution = vec![];
366 self.linearize_into(&mut resolution, type_name)?;
367 Ok(resolution)
368 }
369
370 pub fn resolve(&self, type_name: &str) -> Result<DynSolType> {
373 self.detect_cycle(type_name)?;
374 self.resolve_unchecked(&TypeSpecifier::parse_eip712(type_name)?)
375 }
376
377 fn resolve_unchecked(&self, type_spec: &TypeSpecifier<'_>) -> Result<DynSolType> {
379 let ty = match &type_spec.stem {
380 TypeStem::Root(root) => self.resolve_root_type(*root),
381 TypeStem::Tuple(tuple) => tuple
382 .types
383 .iter()
384 .map(|ty| self.resolve_unchecked(ty))
385 .collect::<Result<_, _>>()
386 .map(DynSolType::Tuple),
387 }?;
388 Ok(ty.array_wrap_from_iter(type_spec.sizes.iter().copied()))
389 }
390
391 fn resolve_root_type(&self, root_type: RootType<'_>) -> Result<DynSolType> {
394 if let Ok(ty) = root_type.resolve() {
395 return Ok(ty);
396 }
397
398 let ty = self
399 .nodes
400 .get(root_type.span())
401 .ok_or_else(|| Error::missing_type(root_type.span()))?;
402
403 let prop_names: Vec<_> = ty.prop_names().map(str::to_string).collect();
404 let tuple: Vec<_> = ty
405 .prop_types()
406 .map(|ty| self.resolve_unchecked(&TypeSpecifier::parse_eip712(ty)?))
407 .collect::<Result<_, _>>()?;
408
409 Ok(DynSolType::CustomStruct { name: ty.type_name.clone(), prop_names, tuple })
410 }
411
412 fn edges(&self, ty: &TypeDef) -> &[String] {
413 self.edges.get(&ty.type_name).expect("no edges for node")
414 }
415
416 pub fn encode_type(&self, name: &str) -> Result<String> {
420 let defs = self.linearize(name)?;
421 if defs.is_empty() {
422 return Err(Error::missing_type(name));
423 }
424 let mut encoded = defs.into_iter().map(|x| x.eip712_encode_type()).collect::<Vec<_>>();
425 encoded[1..].sort_unstable();
426
427 let mut output = String::new();
428 for ty in encoded {
429 output.push_str(&ty);
430 }
431 debug_assert!(!output.is_empty());
432 Ok(output)
433 }
434
435 pub fn type_hash(&self, name: &str) -> Result<B256> {
437 self.encode_type(name).map(keccak256)
438 }
439
440 pub fn encode_data(&self, value: &DynSolValue) -> Result<Option<Vec<u8>>> {
442 Ok(match value {
443 DynSolValue::CustomStruct { tuple: inner, .. }
444 | DynSolValue::Array(inner)
445 | DynSolValue::FixedArray(inner) => {
446 let mut bytes = Vec::with_capacity(inner.len() * 32);
447 for v in inner {
448 bytes.extend(self.eip712_data_word(v)?.as_slice());
449 }
450 Some(bytes)
451 }
452 DynSolValue::Bytes(buf) => Some(buf.to_vec()),
453 DynSolValue::String(s) => Some(s.as_bytes().to_vec()),
454 _ => None,
455 })
456 }
457
458 pub fn eip712_data_word(&self, value: &DynSolValue) -> Result<B256> {
462 if let Some(word) = value.as_word() {
463 return Ok(word);
464 }
465
466 let mut bytes;
467 let to_hash = match value {
468 DynSolValue::CustomStruct { name, tuple, .. } => {
469 bytes = self.type_hash(name)?.to_vec();
470 for v in tuple {
471 bytes.extend(self.eip712_data_word(v)?.as_slice());
472 }
473 &bytes[..]
474 }
475 DynSolValue::Array(inner) | DynSolValue::FixedArray(inner) => {
476 bytes = Vec::with_capacity(inner.len() * 32);
477 for v in inner {
478 bytes.extend(self.eip712_data_word(v)?);
479 }
480 &bytes[..]
481 }
482 DynSolValue::Bytes(buf) => buf,
483 DynSolValue::String(s) => s.as_bytes(),
484 _ => unreachable!("all types are words or covered in the match"),
485 };
486 Ok(keccak256(to_hash))
487 }
488
489 pub fn contains_type_name(&self, name: &str) -> bool {
495 self.nodes.contains_key(name)
496 }
497
498 pub fn non_dependent_types(&self) -> impl Iterator<Item = &TypeDef> {
500 let dependent_types: BTreeSet<&str> = self
501 .edges
502 .values()
503 .flat_map(|dep| dep.iter())
504 .map(|dep| dep.as_str())
505 .filter(|dep| self.nodes.contains_key(*dep))
506 .collect();
507
508 self.nodes.iter().filter_map(move |(node, def)| {
509 if !dependent_types.contains(node.as_str()) { Some(def) } else { None }
510 })
511 }
512}
513
514#[cfg(test)]
515mod tests {
516 use super::*;
517 use alloc::boxed::Box;
518 use alloy_sol_types::sol;
519 use serde_json::json;
520
521 #[test]
522 fn it_detects_cycles() {
523 let mut graph = Resolver::default();
524 graph.ingest(TypeDef::new_unchecked(
525 "A".to_string(),
526 vec![PropertyDef::new_unchecked("B", "myB")],
527 ));
528 graph.ingest(TypeDef::new_unchecked(
529 "B".to_string(),
530 vec![PropertyDef::new_unchecked("C", "myC")],
531 ));
532 graph.ingest(TypeDef::new_unchecked(
533 "C".to_string(),
534 vec![PropertyDef::new_unchecked("A", "myA")],
535 ));
536
537 assert!(graph.detect_cycle_inner("A", &mut DfsContext::default()));
538 }
539
540 #[test]
541 fn it_produces_encode_type_strings() {
542 let mut graph = Resolver::default();
543 graph.ingest(TypeDef::new_unchecked(
544 "A".to_string(),
545 vec![PropertyDef::new_unchecked("C", "myC"), PropertyDef::new_unchecked("B", "myB")],
546 ));
547 graph.ingest(TypeDef::new_unchecked(
548 "B".to_string(),
549 vec![PropertyDef::new_unchecked("C", "myC")],
550 ));
551 graph.ingest(TypeDef::new_unchecked(
552 "C".to_string(),
553 vec![
554 PropertyDef::new_unchecked("uint256", "myUint"),
555 PropertyDef::new_unchecked("uint256", "myUint2"),
556 ],
557 ));
558
559 assert_eq!(
563 graph.encode_type("A").unwrap(),
564 "A(C myC,B myB)B(C myC)C(uint256 myUint,uint256 myUint2)"
565 );
566 }
567
568 #[test]
569 fn it_resolves_types() {
570 let mut graph = Resolver::default();
571 graph.ingest(TypeDef::new_unchecked(
572 "A".to_string(),
573 vec![PropertyDef::new_unchecked("B", "myB")],
574 ));
575 graph.ingest(TypeDef::new_unchecked(
576 "B".to_string(),
577 vec![PropertyDef::new_unchecked("C", "myC")],
578 ));
579 graph.ingest(TypeDef::new_unchecked(
580 "C".to_string(),
581 vec![PropertyDef::new_unchecked("uint256", "myUint")],
582 ));
583
584 let c = DynSolType::CustomStruct {
585 name: "C".to_string(),
586 prop_names: vec!["myUint".to_string()],
587 tuple: vec![DynSolType::Uint(256)],
588 };
589 let b = DynSolType::CustomStruct {
590 name: "B".to_string(),
591 prop_names: vec!["myC".to_string()],
592 tuple: vec![c.clone()],
593 };
594 let a = DynSolType::CustomStruct {
595 name: "A".to_string(),
596 prop_names: vec!["myB".to_string()],
597 tuple: vec![b.clone()],
598 };
599 assert_eq!(graph.resolve("A"), Ok(a));
600 assert_eq!(graph.resolve("B"), Ok(b));
601 assert_eq!(graph.resolve("C"), Ok(c));
602 }
603
604 #[test]
605 fn it_resolves_types_with_arrays() {
606 let mut graph = Resolver::default();
607 graph.ingest(TypeDef::new_unchecked(
608 "A".to_string(),
609 vec![PropertyDef::new_unchecked("B", "myB")],
610 ));
611 graph.ingest(TypeDef::new_unchecked(
612 "B".to_string(),
613 vec![PropertyDef::new_unchecked("C[]", "myC")],
614 ));
615 graph.ingest(TypeDef::new_unchecked(
616 "C".to_string(),
617 vec![PropertyDef::new_unchecked("uint256", "myUint")],
618 ));
619
620 let c = DynSolType::CustomStruct {
621 name: "C".to_string(),
622 prop_names: vec!["myUint".to_string()],
623 tuple: vec![DynSolType::Uint(256)],
624 };
625 let b = DynSolType::CustomStruct {
626 name: "B".to_string(),
627 prop_names: vec!["myC".to_string()],
628 tuple: vec![DynSolType::Array(Box::new(c.clone()))],
629 };
630 let a = DynSolType::CustomStruct {
631 name: "A".to_string(),
632 prop_names: vec!["myB".to_string()],
633 tuple: vec![b.clone()],
634 };
635 assert_eq!(graph.resolve("C"), Ok(c));
636 assert_eq!(graph.resolve("B"), Ok(b));
637 assert_eq!(graph.resolve("A"), Ok(a));
638 }
639
640 #[test]
641 fn encode_type_round_trip() {
642 const ENCODE_TYPE: &str = "A(C myC,B myB)B(C myC)C(uint256 myUint,uint256 myUint2)";
643 let mut graph = Resolver::default();
644 graph.ingest_string(ENCODE_TYPE).unwrap();
645 assert_eq!(graph.encode_type("A").unwrap(), ENCODE_TYPE);
646
647 const ENCODE_TYPE_2: &str = "Transaction(Person from,Person to,Asset tx)Asset(address token,uint256 amount)Person(address wallet,string name)";
648 let mut graph = Resolver::default();
649 graph.ingest_string(ENCODE_TYPE_2).unwrap();
650 assert_eq!(graph.encode_type("Transaction").unwrap(), ENCODE_TYPE_2);
651 }
652
653 #[test]
654 fn it_ingests_sol_structs() {
655 sol!(
656 struct MyStruct {
657 uint256 a;
658 }
659 );
660
661 let mut graph = Resolver::default();
662 graph.ingest_sol_struct::<MyStruct>();
663 assert_eq!(graph.encode_type("MyStruct").unwrap(), MyStruct::eip712_encode_type());
664 }
665
666 #[test]
667 fn it_finds_non_dependent_nodes() {
668 const ENCODE_TYPE: &str =
669 "A(C myC,B myB)B(C myC)C(uint256 myUint,uint256 myUint2)D(bool isD)";
670 let mut graph = Resolver::default();
671 graph.ingest_string(ENCODE_TYPE).unwrap();
672 assert_eq!(
673 graph.non_dependent_types().map(|t| &t.type_name).collect::<Vec<_>>(),
674 vec!["A", "D"]
675 );
676
677 const ENCODE_TYPE_2: &str = "Transaction(Person from,Person to,Asset tx)Asset(address token,uint256 amount)Person(address wallet,string name)";
678 let mut graph = Resolver::default();
679 graph.ingest_string(ENCODE_TYPE_2).unwrap();
680 assert_eq!(
681 graph.non_dependent_types().map(|t| &t.type_name).collect::<Vec<_>>(),
682 vec!["Transaction"]
683 );
684 }
685
686 #[test]
687 fn test_deserialize_resolver_with_colon() {
688 let json = json!({
690 "EIP712Domain": [
691 {
692 "name": "name",
693 "type": "string"
694 },
695 {
696 "name": "version",
697 "type": "string"
698 },
699 {
700 "name": "chainId",
701 "type": "uint256"
702 },
703 {
704 "name": "verifyingContract",
705 "type": "address"
706 }
707 ],
708 "Test:Message": [
709 {
710 "name": "content",
711 "type": "string"
712 }
713 ]
714 });
715
716 let _result: Resolver = serde_json::from_value(json).unwrap();
717 }
718}