alloy_dyn_abi/eip712/
resolver.rs

1use crate::{
2    eip712::typed_data::Eip712Types, eip712_parser::EncodeType, DynSolType, DynSolValue, Error,
3    Result, Specifier,
4};
5use alloc::{
6    borrow::ToOwned,
7    collections::{BTreeMap, BTreeSet},
8    string::{String, ToString},
9    vec::Vec,
10};
11use alloy_primitives::{keccak256, B256};
12use alloy_sol_types::SolStruct;
13use core::{cmp::Ordering, fmt};
14use parser::{RootType, TypeSpecifier, TypeStem};
15use serde::{Deserialize, Deserializer, Serialize};
16
17/// An EIP-712 property definition.
18#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize)]
19pub struct PropertyDef {
20    /// Typename.
21    #[serde(rename = "type")]
22    type_name: String,
23    /// Property Name.
24    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    /// Instantiate a new name-type pair.
42    #[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(type_name.as_str())?;
50        Ok(Self::new_unchecked(type_name, name))
51    }
52
53    /// Instantiate a new name-type pair, without checking that the type name
54    /// is a valid root type.
55    #[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    /// Returns the name of the property.
65    #[inline]
66    pub fn name(&self) -> &str {
67        &self.name
68    }
69
70    /// Returns the type name of the property.
71    #[inline]
72    pub fn type_name(&self) -> &str {
73        &self.type_name
74    }
75
76    /// Returns the root type of the name/type pair, stripping any array.
77    #[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/// An EIP-712 type definition.
84#[derive(Clone, Debug, PartialEq, Eq, Hash)]
85pub struct TypeDef {
86    /// Must always be a ROOT type name with any array stripped.
87    type_name: String,
88    /// A list of property definitions.
89    props: Vec<PropertyDef>,
90}
91
92impl Ord for TypeDef {
93    // This is not a logic error because we know type names cannot be duplicated in
94    // the resolver map
95    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    /// Instantiate a new type definition, checking that the type name is a
114    /// valid root type.
115    #[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(type_name.as_str())?;
119        Ok(Self { type_name, props })
120    }
121
122    /// Instantiate a new type definition, without checking that the type name
123    /// is a valid root type. This may result in bad behavior in a resolver.
124    #[inline]
125    pub const fn new_unchecked(type_name: String, props: Vec<PropertyDef>) -> Self {
126        Self { type_name, props }
127    }
128
129    /// Returns the type name of the type definition.
130    #[inline]
131    pub fn type_name(&self) -> &str {
132        &self.type_name
133    }
134
135    /// Returns the property definitions of the type definition.
136    #[inline]
137    pub fn props(&self) -> &[PropertyDef] {
138        &self.props
139    }
140
141    /// Returns the property names of the type definition.
142    #[inline]
143    pub fn prop_names(&self) -> impl Iterator<Item = &str> + '_ {
144        self.props.iter().map(|p| p.name())
145    }
146
147    /// Returns the root property types of the type definition.
148    #[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    /// Returns the property types of the type definition.
154    #[inline]
155    pub fn prop_types(&self) -> impl Iterator<Item = &str> + '_ {
156        self.props.iter().map(|p| p.type_name())
157    }
158
159    /// Produces the EIP-712 `encodeType` typestring for this type definition.
160    #[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    /// Formats the EIP-712 `encodeType` typestring for this type definition
168    /// into `f`.
169    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    /// Returns the number of bytes that the properties of this type definition
185    /// will take up when formatted in the EIP-712 `encodeType` typestring.
186    #[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    /// Return the root type.
192    #[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/// A dependency graph built from the `Eip712Types` object. This is used to
205/// safely resolve JSON into a [`crate::DynSolType`] by detecting cycles in the
206/// type graph and traversing the dep graph.
207#[derive(Clone, Debug, Default, PartialEq, Eq)]
208pub struct Resolver {
209    /// Nodes in the graph
210    // NOTE: Non-duplication of names must be enforced. See note on impl of Ord
211    // for TypeDef
212    nodes: BTreeMap<String, TypeDef>,
213    /// Edges from a type name to its dependencies.
214    edges: BTreeMap<String, Vec<String>>,
215}
216
217impl Serialize for Resolver {
218    #[inline]
219    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
220        Eip712Types::from(self).serialize(serializer)
221    }
222}
223
224impl<'de> Deserialize<'de> for Resolver {
225    #[inline]
226    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
227        Eip712Types::deserialize(deserializer).map(Into::into)
228    }
229}
230
231impl From<Eip712Types> for Resolver {
232    fn from(types: Eip712Types) -> Self {
233        Self::from(&types)
234    }
235}
236
237impl From<&Eip712Types> for Resolver {
238    #[inline]
239    fn from(types: &Eip712Types) -> Self {
240        let mut graph = Self::default();
241        graph.ingest_types(types);
242        graph
243    }
244}
245
246impl From<&Resolver> for Eip712Types {
247    fn from(resolver: &Resolver) -> Self {
248        let mut types = Self::default();
249        for (name, ty) in &resolver.nodes {
250            types.insert(name.clone(), ty.props.clone());
251        }
252        types
253    }
254}
255
256impl Resolver {
257    /// Instantiate a new resolver from a `SolStruct` type.
258    pub fn from_struct<S: SolStruct>() -> Self {
259        let mut resolver = Self::default();
260        resolver.ingest_sol_struct::<S>();
261        resolver
262    }
263
264    /// Detect cycles in the subgraph rooted at `type_name`
265    fn detect_cycle<'a>(&'a self, type_name: &str, context: &mut DfsContext<'a>) -> bool {
266        let ty = match self.nodes.get(type_name) {
267            Some(ty) => ty,
268            None => return false,
269        };
270
271        if context.stack.contains(type_name) {
272            return true;
273        }
274        if context.visited.contains(ty) {
275            return false;
276        }
277
278        // update visited and stack
279        context.visited.insert(ty);
280        context.stack.insert(&ty.type_name);
281
282        if self
283            .edges
284            .get(&ty.type_name)
285            .unwrap()
286            .iter()
287            .any(|edge| self.detect_cycle(edge, context))
288        {
289            return true;
290        }
291
292        context.stack.remove(type_name);
293        false
294    }
295
296    /// Ingest types from an EIP-712 `encodeType`.
297    pub fn ingest_string(&mut self, s: impl AsRef<str>) -> Result<()> {
298        let encode_type: EncodeType<'_> = s.as_ref().try_into()?;
299        for t in encode_type.types {
300            self.ingest(t.to_owned());
301        }
302        Ok(())
303    }
304
305    /// Ingest a sol struct typedef.
306    pub fn ingest_sol_struct<S: SolStruct>(&mut self) {
307        self.ingest_string(S::eip712_encode_type()).unwrap();
308    }
309
310    /// Ingest a type.
311    pub fn ingest(&mut self, type_def: TypeDef) {
312        let type_name = type_def.type_name.to_owned();
313        // Insert the edges into the graph
314        {
315            let entry = self.edges.entry(type_name.clone()).or_default();
316            for prop in &type_def.props {
317                entry.push(prop.root_type_name().to_owned());
318            }
319        } // entry dropped here
320
321        // Insert the node into the graph
322        self.nodes.insert(type_name, type_def);
323    }
324
325    /// Ingest a `Types` object into the resolver, discarding any invalid types.
326    pub fn ingest_types(&mut self, types: &Eip712Types) {
327        for (type_name, props) in types {
328            if let Ok(ty) = TypeDef::new(type_name.clone(), props.to_vec()) {
329                self.ingest(ty);
330            }
331        }
332    }
333
334    // This function assumes that the graph is acyclic.
335    fn linearize_into<'a>(
336        &'a self,
337        resolution: &mut Vec<&'a TypeDef>,
338        root_type: RootType<'_>,
339    ) -> Result<()> {
340        if root_type.try_basic_solidity().is_ok() {
341            return Ok(());
342        }
343
344        let this_type = self
345            .nodes
346            .get(root_type.span())
347            .ok_or_else(|| Error::missing_type(root_type.span()))?;
348
349        let edges: &Vec<String> = self.edges.get(root_type.span()).unwrap();
350
351        if !resolution.contains(&this_type) {
352            resolution.push(this_type);
353            for edge in edges {
354                let rt = edge.as_str().try_into()?;
355                self.linearize_into(resolution, rt)?;
356            }
357        }
358
359        Ok(())
360    }
361
362    /// This function linearizes a type into a list of typedefs of its
363    /// dependencies.
364    pub fn linearize(&self, type_name: &str) -> Result<Vec<&TypeDef>> {
365        let mut context = DfsContext::default();
366        if self.detect_cycle(type_name, &mut context) {
367            return Err(Error::circular_dependency(type_name));
368        }
369        let root_type = type_name.try_into()?;
370        let mut resolution = vec![];
371        self.linearize_into(&mut resolution, root_type)?;
372        Ok(resolution)
373    }
374
375    /// Resolve a typename into a [`crate::DynSolType`] or return an error if
376    /// the type is missing, or contains a circular dependency.
377    pub fn resolve(&self, type_name: &str) -> Result<DynSolType> {
378        if self.detect_cycle(type_name, &mut Default::default()) {
379            return Err(Error::circular_dependency(type_name));
380        }
381        self.unchecked_resolve(&type_name.try_into()?)
382    }
383
384    /// Resolve a type into a [`crate::DynSolType`] without checking for cycles.
385    fn unchecked_resolve(&self, type_spec: &TypeSpecifier<'_>) -> Result<DynSolType> {
386        let ty = match &type_spec.stem {
387            TypeStem::Root(root) => self.resolve_root_type(*root),
388            TypeStem::Tuple(tuple) => tuple
389                .types
390                .iter()
391                .map(|ty| self.unchecked_resolve(ty))
392                .collect::<Result<_, _>>()
393                .map(DynSolType::Tuple),
394        }?;
395        Ok(ty.array_wrap_from_iter(type_spec.sizes.iter().copied()))
396    }
397
398    /// Resolves a root Solidity type into either a basic type or a custom
399    /// struct.
400    fn resolve_root_type(&self, root_type: RootType<'_>) -> Result<DynSolType> {
401        if let Ok(ty) = root_type.resolve() {
402            return Ok(ty);
403        }
404
405        let ty = self
406            .nodes
407            .get(root_type.span())
408            .ok_or_else(|| Error::missing_type(root_type.span()))?;
409
410        let prop_names: Vec<_> = ty.prop_names().map(str::to_string).collect();
411        let tuple: Vec<_> = ty
412            .prop_types()
413            .map(|ty| self.unchecked_resolve(&ty.try_into()?))
414            .collect::<Result<_, _>>()?;
415
416        Ok(DynSolType::CustomStruct { name: ty.type_name.clone(), prop_names, tuple })
417    }
418
419    /// Encode the type into an EIP-712 `encodeType` string
420    ///
421    /// <https://eips.ethereum.org/EIPS/eip-712#definition-of-encodetype>
422    pub fn encode_type(&self, name: &str) -> Result<String> {
423        let linear = self.linearize(name)?;
424        let first = linear.first().unwrap().eip712_encode_type();
425
426        // Sort references by name (eip-712 encodeType spec)
427        let mut sorted_refs =
428            linear[1..].iter().map(|t| t.eip712_encode_type()).collect::<Vec<String>>();
429        sorted_refs.sort();
430
431        Ok(sorted_refs.iter().fold(first, |mut acc, s| {
432            acc.push_str(s);
433            acc
434        }))
435    }
436
437    /// Compute the keccak256 hash of the EIP-712 `encodeType` string.
438    pub fn type_hash(&self, name: &str) -> Result<B256> {
439        self.encode_type(name).map(keccak256)
440    }
441
442    /// Encode the data according to EIP-712 `encodeData` rules.
443    pub fn encode_data(&self, value: &DynSolValue) -> Result<Option<Vec<u8>>> {
444        Ok(match value {
445            DynSolValue::CustomStruct { tuple: inner, .. }
446            | DynSolValue::Array(inner)
447            | DynSolValue::FixedArray(inner) => {
448                let mut bytes = Vec::with_capacity(inner.len() * 32);
449                for v in inner {
450                    bytes.extend(self.eip712_data_word(v)?.as_slice());
451                }
452                Some(bytes)
453            }
454            DynSolValue::Bytes(buf) => Some(buf.to_vec()),
455            DynSolValue::String(s) => Some(s.as_bytes().to_vec()),
456            _ => None,
457        })
458    }
459
460    /// Encode the data as a struct property according to EIP-712 `encodeData`
461    /// rules. Atomic types are encoded as-is, while non-atomic types are
462    /// encoded as their `encodeData` hash.
463    pub fn eip712_data_word(&self, value: &DynSolValue) -> Result<B256> {
464        if let Some(word) = value.as_word() {
465            return Ok(word);
466        }
467
468        let mut bytes;
469        let to_hash = match value {
470            DynSolValue::CustomStruct { name, tuple, .. } => {
471                bytes = self.type_hash(name)?.to_vec();
472                for v in tuple {
473                    bytes.extend(self.eip712_data_word(v)?.as_slice());
474                }
475                &bytes[..]
476            }
477            DynSolValue::Array(inner) | DynSolValue::FixedArray(inner) => {
478                bytes = Vec::with_capacity(inner.len() * 32);
479                for v in inner {
480                    bytes.extend(self.eip712_data_word(v)?);
481                }
482                &bytes[..]
483            }
484            DynSolValue::Bytes(buf) => buf,
485            DynSolValue::String(s) => s.as_bytes(),
486            _ => unreachable!("all types are words or covered in the match"),
487        };
488        Ok(keccak256(to_hash))
489    }
490
491    /// Check if the resolver graph contains a type by its name.
492    ///
493    /// ## Warning
494    ///
495    /// This checks by NAME only. It does NOT check for type
496    pub fn contains_type_name(&self, name: &str) -> bool {
497        self.nodes.contains_key(name)
498    }
499}
500
501#[cfg(test)]
502mod tests {
503    use super::*;
504    use alloc::boxed::Box;
505    use alloy_sol_types::sol;
506
507    #[test]
508    fn it_detects_cycles() {
509        let mut graph = Resolver::default();
510        graph.ingest(TypeDef::new_unchecked(
511            "A".to_string(),
512            vec![PropertyDef::new_unchecked("B", "myB")],
513        ));
514        graph.ingest(TypeDef::new_unchecked(
515            "B".to_string(),
516            vec![PropertyDef::new_unchecked("C", "myC")],
517        ));
518        graph.ingest(TypeDef::new_unchecked(
519            "C".to_string(),
520            vec![PropertyDef::new_unchecked("A", "myA")],
521        ));
522
523        assert!(graph.detect_cycle("A", &mut DfsContext::default()));
524    }
525
526    #[test]
527    fn it_produces_encode_type_strings() {
528        let mut graph = Resolver::default();
529        graph.ingest(TypeDef::new_unchecked(
530            "A".to_string(),
531            vec![PropertyDef::new_unchecked("C", "myC"), PropertyDef::new_unchecked("B", "myB")],
532        ));
533        graph.ingest(TypeDef::new_unchecked(
534            "B".to_string(),
535            vec![PropertyDef::new_unchecked("C", "myC")],
536        ));
537        graph.ingest(TypeDef::new_unchecked(
538            "C".to_string(),
539            vec![
540                PropertyDef::new_unchecked("uint256", "myUint"),
541                PropertyDef::new_unchecked("uint256", "myUint2"),
542            ],
543        ));
544
545        // This tests specific adherence to EIP-712 specified ordering.
546        // Referenced types are sorted by name, the Primary type is at the
547        // start of the string
548        assert_eq!(
549            graph.encode_type("A").unwrap(),
550            "A(C myC,B myB)B(C myC)C(uint256 myUint,uint256 myUint2)"
551        );
552    }
553
554    #[test]
555    fn it_resolves_types() {
556        let mut graph = Resolver::default();
557        graph.ingest(TypeDef::new_unchecked(
558            "A".to_string(),
559            vec![PropertyDef::new_unchecked("B", "myB")],
560        ));
561        graph.ingest(TypeDef::new_unchecked(
562            "B".to_string(),
563            vec![PropertyDef::new_unchecked("C", "myC")],
564        ));
565        graph.ingest(TypeDef::new_unchecked(
566            "C".to_string(),
567            vec![PropertyDef::new_unchecked("uint256", "myUint")],
568        ));
569
570        let c = DynSolType::CustomStruct {
571            name: "C".to_string(),
572            prop_names: vec!["myUint".to_string()],
573            tuple: vec![DynSolType::Uint(256)],
574        };
575        let b = DynSolType::CustomStruct {
576            name: "B".to_string(),
577            prop_names: vec!["myC".to_string()],
578            tuple: vec![c.clone()],
579        };
580        let a = DynSolType::CustomStruct {
581            name: "A".to_string(),
582            prop_names: vec!["myB".to_string()],
583            tuple: vec![b.clone()],
584        };
585        assert_eq!(graph.resolve("A"), Ok(a));
586        assert_eq!(graph.resolve("B"), Ok(b));
587        assert_eq!(graph.resolve("C"), Ok(c));
588    }
589
590    #[test]
591    fn it_resolves_types_with_arrays() {
592        let mut graph = Resolver::default();
593        graph.ingest(TypeDef::new_unchecked(
594            "A".to_string(),
595            vec![PropertyDef::new_unchecked("B", "myB")],
596        ));
597        graph.ingest(TypeDef::new_unchecked(
598            "B".to_string(),
599            vec![PropertyDef::new_unchecked("C[]", "myC")],
600        ));
601        graph.ingest(TypeDef::new_unchecked(
602            "C".to_string(),
603            vec![PropertyDef::new_unchecked("uint256", "myUint")],
604        ));
605
606        let c = DynSolType::CustomStruct {
607            name: "C".to_string(),
608            prop_names: vec!["myUint".to_string()],
609            tuple: vec![DynSolType::Uint(256)],
610        };
611        let b = DynSolType::CustomStruct {
612            name: "B".to_string(),
613            prop_names: vec!["myC".to_string()],
614            tuple: vec![DynSolType::Array(Box::new(c.clone()))],
615        };
616        let a = DynSolType::CustomStruct {
617            name: "A".to_string(),
618            prop_names: vec!["myB".to_string()],
619            tuple: vec![b.clone()],
620        };
621        assert_eq!(graph.resolve("C"), Ok(c));
622        assert_eq!(graph.resolve("B"), Ok(b));
623        assert_eq!(graph.resolve("A"), Ok(a));
624    }
625
626    #[test]
627    fn encode_type_round_trip() {
628        const ENCODE_TYPE: &str = "A(C myC,B myB)B(C myC)C(uint256 myUint,uint256 myUint2)";
629        let mut graph = Resolver::default();
630        graph.ingest_string(ENCODE_TYPE).unwrap();
631        assert_eq!(graph.encode_type("A").unwrap(), ENCODE_TYPE);
632
633        const ENCODE_TYPE_2: &str = "Transaction(Person from,Person to,Asset tx)Asset(address token,uint256 amount)Person(address wallet,string name)";
634        let mut graph = Resolver::default();
635        graph.ingest_string(ENCODE_TYPE_2).unwrap();
636        assert_eq!(graph.encode_type("Transaction").unwrap(), ENCODE_TYPE_2);
637    }
638
639    #[test]
640    fn it_ingests_sol_structs() {
641        sol!(
642            struct MyStruct {
643                uint256 a;
644            }
645        );
646
647        let mut graph = Resolver::default();
648        graph.ingest_sol_struct::<MyStruct>();
649        assert_eq!(graph.encode_type("MyStruct").unwrap(), MyStruct::eip712_encode_type());
650    }
651}
alloy_dyn_abi/eip712/resolver.rs

alloy_dyn_abi/eip712/
resolver.rs
