neo_solidity/solidity/analyse/inheritance/
linearization.rs

1fn c3_merge(
2    contract_name: &str,
3    mut sequences: Vec<Vec<String>>,
4) -> Result<Vec<String>, SolidityError> {
5    let mut result = Vec::new();
6
7    loop {
8        sequences.retain(|seq| !seq.is_empty());
9        if sequences.is_empty() {
10            break;
11        }
12
13        let mut candidate: Option<String> = None;
14        for seq in &sequences {
15            let head = &seq[0];
16            let is_in_tail = sequences.iter().any(|other| other.iter().skip(1).any(|v| v == head));
17            if !is_in_tail {
18                candidate = Some(head.clone());
19                break;
20            }
21        }
22
23        let Some(candidate) = candidate else {
24            return Err(SolidityError::Analysis(format!(
25                "inheritance linearization failed for '{contract_name}': inconsistent base order"
26            )));
27        };
28
29        result.push(candidate.clone());
30        for seq in sequences.iter_mut() {
31            if seq.first().map(|v| v == &candidate).unwrap_or(false) {
32                seq.remove(0);
33            }
34        }
35    }
36
37    Ok(result)
38}
39
40fn contract_linearization_mro(
41    contract_name: &str,
42    contract_map: &std::collections::HashMap<String, ContractIR>,
43    visiting: &mut std::collections::HashSet<String>,
44    cache: &mut std::collections::HashMap<String, Vec<String>>,
45) -> Result<Vec<String>, SolidityError> {
46    if let Some(cached) = cache.get(contract_name) {
47        return Ok(cached.clone());
48    }
49
50    if !visiting.insert(contract_name.to_string()) {
51        return Err(SolidityError::Analysis(format!(
52            "inheritance cycle detected at '{contract_name}'"
53        )));
54    }
55
56    let contract = contract_map.get(contract_name).ok_or_else(|| {
57        SolidityError::Analysis(format!(
58            "internal error: contract '{contract_name}' missing from analysis map"
59        ))
60    })?;
61
62    let mut direct_bases: Vec<String> = Vec::new();
63    for base in &contract.bases {
64        let Some(base_name) = base_last_name(base) else {
65            continue;
66        };
67
68        let Some(base_contract) = contract_map.get(&base_name) else {
69            return Err(SolidityError::Analysis(format!(
70                "contract '{}' inherits from unknown base '{}'",
71                contract.name, base_name
72            )));
73        };
74
75        match (contract.kind, base_contract.kind) {
76            (ContractKind::Contract | ContractKind::AbstractContract, ContractKind::Interface) => {
77                // Interfaces do not influence contract storage layout or constructor order.
78            }
79            (
80                ContractKind::Contract | ContractKind::AbstractContract,
81                ContractKind::Contract | ContractKind::AbstractContract,
82            ) => {
83                direct_bases.push(base_name);
84            }
85            (ContractKind::Interface, ContractKind::Interface) => {
86                direct_bases.push(base_name);
87            }
88            (ContractKind::Interface, ContractKind::Contract | ContractKind::AbstractContract) => {
89                return Err(SolidityError::Analysis(format!(
90                    "interface '{}' cannot inherit from contract '{}'",
91                    contract.name, base_name
92                )));
93            }
94            (_, ContractKind::Library) => {
95                return Err(SolidityError::Analysis(format!(
96                    "contract '{}' cannot inherit from library '{}'",
97                    contract.name, base_name
98                )));
99            }
100            (ContractKind::Library, _) => {
101                return Err(SolidityError::Analysis(format!(
102                    "library '{}' cannot use inheritance",
103                    contract.name
104                )));
105            }
106        }
107    }
108
109    let mut sequences: Vec<Vec<String>> = Vec::new();
110    for base_name in &direct_bases {
111        sequences.push(contract_linearization_mro(
112            base_name,
113            contract_map,
114            visiting,
115            cache,
116        )?);
117    }
118    sequences.push(direct_bases.clone());
119
120    let merged = c3_merge(contract_name, sequences)?;
121    let mut linearization = Vec::with_capacity(1 + merged.len());
122    linearization.push(contract_name.to_string());
123    linearization.extend(merged);
124
125    visiting.remove(contract_name);
126    cache.insert(contract_name.to_string(), linearization.clone());
127    Ok(linearization)
128}
129
130fn contract_linearization_base_to_derived(
131    contract_name: &str,
132    contract_map: &std::collections::HashMap<String, ContractIR>,
133) -> Result<Vec<String>, SolidityError> {
134    let mut cache = std::collections::HashMap::new();
135    let mut visiting = std::collections::HashSet::new();
136    let mro = contract_linearization_mro(contract_name, contract_map, &mut visiting, &mut cache)?;
137    Ok(mro.into_iter().rev().collect())
138}
neo_solidity/solidity/analyse/inheritance/linearization.rs

neo_solidity/solidity/analyse/inheritance/
linearization.rs
