Skip to main content

offlineasm_backend/
transform.rs

1//! Rewrites the syntax tree toward lowering.
2//!
3//! [`resolve_settings`] folds `if` branches, [`demacroify`] expands macros,
4//! [`resolve_offsets`] substitutes offsets, and [`fold`] folds constants.
5//! [`validate`] checks earlier stages left nothing behind. [`resolve`] runs
6//! the demacroify, offset, and fold stages in order.
7
8use crate::ast::Node;
9use std::collections::HashMap;
10
11fn predicate_value(node: &Node) -> Result<bool, String> {
12    match node {
13        Node::True => Ok(true),
14        Node::False => Ok(false),
15        other => Err(format!(
16            "expected predicate, got {} at {}",
17            other.dump(),
18            other.origin_string()
19        )),
20    }
21}
22
23/// Substitutes each `Node::Setting` in `node` per `settings`.
24///
25/// Each setting becomes `True` or `False`, then predicates fold.
26///
27/// # Errors
28///
29/// - Returns an error if `node` references a setting absent from `settings`.
30/// - Returns an error if a predicate does not fold to `True`/`False`.
31pub fn resolve_settings(node: &Node, settings: &HashMap<String, bool>) -> Result<Node, String> {
32    match node {
33        Node::True | Node::False => Ok(node.clone()),
34        Node::Setting { origin: _, name } => match settings.get(name) {
35            Some(true) => Ok(Node::True),
36            Some(false) => Ok(Node::False),
37            None => Err(format!(
38                "unknown setting {} at {}",
39                name,
40                node.origin_string()
41            )),
42        },
43        Node::AndPred { left, right, .. } => {
44            let l = resolve_settings(left, settings)?;
45            let r = resolve_settings(right, settings)?;
46            Ok(if predicate_value(&l)? && predicate_value(&r)? {
47                Node::True
48            } else {
49                Node::False
50            })
51        }
52        Node::OrPred { left, right, .. } => {
53            let l = resolve_settings(left, settings)?;
54            let r = resolve_settings(right, settings)?;
55            Ok(if predicate_value(&l)? || predicate_value(&r)? {
56                Node::True
57            } else {
58                Node::False
59            })
60        }
61        Node::NotPred { child, .. } => {
62            let c = resolve_settings(child, settings)?;
63            Ok(if !predicate_value(&c)? {
64                Node::True
65            } else {
66                Node::False
67            })
68        }
69        Node::IfThenElse {
70            predicate,
71            then_case,
72            else_case,
73            ..
74        } => {
75            let p = resolve_settings(predicate, settings)?;
76            if predicate_value(&p)? {
77                resolve_settings(then_case, settings)
78            } else {
79                resolve_settings(else_case, settings)
80            }
81        }
82        Node::Sequence { origin, list } => {
83            let mut new_list = Vec::new();
84            for item in list {
85                let resolved = resolve_settings(item, settings)?;
86                match resolved {
87                    Node::Sequence { list: inner, .. } => new_list.extend(inner),
88                    other => new_list.push(other),
89                }
90            }
91            Ok(Node::Sequence {
92                origin: origin.clone(),
93                list: new_list,
94            })
95        }
96        _ => map_children(node, &mut |child| resolve_settings(child, settings)),
97    }
98}
99
100#[allow(clippy::redundant_closure)]
101fn map_children(
102    node: &Node,
103    f: &mut dyn FnMut(&Node) -> Result<Node, String>,
104) -> Result<Node, String> {
105    match node {
106        Node::Add {
107            origin,
108            left,
109            right,
110        } => Ok(Node::Add {
111            origin: origin.clone(),
112            left: Box::new(f(left)?),
113            right: Box::new(f(right)?),
114        }),
115        Node::Sub {
116            origin,
117            left,
118            right,
119        } => Ok(Node::Sub {
120            origin: origin.clone(),
121            left: Box::new(f(left)?),
122            right: Box::new(f(right)?),
123        }),
124        Node::Mul {
125            origin,
126            left,
127            right,
128        } => Ok(Node::Mul {
129            origin: origin.clone(),
130            left: Box::new(f(left)?),
131            right: Box::new(f(right)?),
132        }),
133        Node::Or {
134            origin,
135            left,
136            right,
137        } => Ok(Node::Or {
138            origin: origin.clone(),
139            left: Box::new(f(left)?),
140            right: Box::new(f(right)?),
141        }),
142        Node::And {
143            origin,
144            left,
145            right,
146        } => Ok(Node::And {
147            origin: origin.clone(),
148            left: Box::new(f(left)?),
149            right: Box::new(f(right)?),
150        }),
151        Node::Xor {
152            origin,
153            left,
154            right,
155        } => Ok(Node::Xor {
156            origin: origin.clone(),
157            left: Box::new(f(left)?),
158            right: Box::new(f(right)?),
159        }),
160        Node::Neg { origin, child } => Ok(Node::Neg {
161            origin: origin.clone(),
162            child: Box::new(f(child)?),
163        }),
164        Node::Bitnot { origin, child } => Ok(Node::Bitnot {
165            origin: origin.clone(),
166            child: Box::new(f(child)?),
167        }),
168        Node::Address {
169            origin,
170            base,
171            offset,
172        } => Ok(Node::Address {
173            origin: origin.clone(),
174            base: Box::new(f(base)?),
175            offset: Box::new(f(offset)?),
176        }),
177        Node::BaseIndex {
178            origin,
179            base,
180            index,
181            scale,
182            offset,
183        } => Ok(Node::BaseIndex {
184            origin: origin.clone(),
185            base: Box::new(f(base)?),
186            index: Box::new(f(index)?),
187            scale: Box::new(f(scale)?),
188            offset: Box::new(f(offset)?),
189        }),
190        Node::Instruction {
191            origin,
192            opcode,
193            operands,
194            annotation,
195        } => Ok(Node::Instruction {
196            origin: origin.clone(),
197            opcode: opcode.clone(),
198            operands: operands
199                .iter()
200                .map(|c| f(c))
201                .collect::<Result<Vec<_>, _>>()?,
202            annotation: annotation.clone(),
203        }),
204        Node::ConstDecl {
205            origin,
206            variable,
207            value,
208        } => Ok(Node::ConstDecl {
209            origin: origin.clone(),
210            variable: Box::new(f(variable)?),
211            value: Box::new(f(value)?),
212        }),
213        Node::Sequence { origin, list } => Ok(Node::Sequence {
214            origin: origin.clone(),
215            list: list.iter().map(|c| f(c)).collect::<Result<Vec<_>, _>>()?,
216        }),
217        Node::AndPred {
218            origin,
219            left,
220            right,
221        } => Ok(Node::AndPred {
222            origin: origin.clone(),
223            left: Box::new(f(left)?),
224            right: Box::new(f(right)?),
225        }),
226        Node::OrPred {
227            origin,
228            left,
229            right,
230        } => Ok(Node::OrPred {
231            origin: origin.clone(),
232            left: Box::new(f(left)?),
233            right: Box::new(f(right)?),
234        }),
235        Node::NotPred { origin, child } => Ok(Node::NotPred {
236            origin: origin.clone(),
237            child: Box::new(f(child)?),
238        }),
239        Node::IfThenElse {
240            origin,
241            predicate,
242            then_case,
243            else_case,
244        } => Ok(Node::IfThenElse {
245            origin: origin.clone(),
246            predicate: Box::new(f(predicate)?),
247            then_case: Box::new(f(then_case)?),
248            else_case: Box::new(f(else_case)?),
249        }),
250        Node::Macro {
251            origin,
252            name,
253            variables,
254            body,
255        } => Ok(Node::Macro {
256            origin: origin.clone(),
257            name: name.clone(),
258            variables: variables
259                .iter()
260                .map(|c| f(c))
261                .collect::<Result<Vec<_>, _>>()?,
262            body: Box::new(f(body)?),
263        }),
264        Node::MacroCall {
265            origin,
266            name,
267            operands,
268            annotation,
269            original_name,
270        } => Ok(Node::MacroCall {
271            origin: origin.clone(),
272            name: name.clone(),
273            operands: operands
274                .iter()
275                .map(|c| f(c))
276                .collect::<Result<Vec<_>, _>>()?,
277            annotation: annotation.clone(),
278            original_name: original_name.clone(),
279        }),
280        _ => Ok(node.clone()),
281    }
282}
283
284/// Substitutes each `$param` reference in `name` that `mapping` covers.
285fn expand_concatenation(name: &str, mapping: &HashMap<String, Node>, for_fresh: bool) -> String {
286    let mut out = String::new();
287    let bytes = name.as_bytes();
288    let mut i = 0;
289    while i < bytes.len() {
290        if bytes[i] == b'$' {
291            let start = i + 1;
292            let mut end = start;
293            while end < bytes.len() && (bytes[end].is_ascii_alphanumeric() || bytes[end] == b'_') {
294                end += 1;
295            }
296            if end > start {
297                let var = &name[start..end];
298                if let Some(rep) = mapping.get(var) {
299                    let rep_name = rep.variable_name().unwrap_or(var);
300                    if for_fresh {
301                        out.push('$');
302                        out.push_str(rep_name);
303                    } else {
304                        out.push_str(rep_name);
305                    }
306                    i = end;
307                    continue;
308                }
309            }
310        }
311        out.push(bytes[i] as char);
312        i += 1;
313    }
314    out
315}
316
317fn contains_concat(s: &str) -> bool {
318    s.contains('$')
319}
320
321/// Substitutes each `$param` token pair (`Punct('$')` immediately followed
322/// by an `Ident`) that `mapping` covers, walking into nested groups. This
323/// is the token-level equivalent of `expand_concatenation`, used for
324/// `Node::ConstExpr`'s token-stream value (an embedded Rust expression,
325/// not a plain name) so substitution never has to round-trip through text.
326fn expand_concatenation_tokens(
327    tokens: &proc_macro2::TokenStream,
328    mapping: &HashMap<String, Node>,
329    for_fresh: bool,
330) -> proc_macro2::TokenStream {
331    use proc_macro2::{Group, TokenTree};
332    let mut out = Vec::new();
333    let mut iter = tokens.clone().into_iter().peekable();
334    while let Some(tt) = iter.next() {
335        match tt {
336            TokenTree::Punct(p) if p.as_char() == '$' => {
337                if let Some(TokenTree::Ident(id)) = iter.peek() {
338                    let param = id.to_string();
339                    if let Some(rep) = mapping.get(&param) {
340                        let rep_name = rep.variable_name().unwrap_or(&param).to_string();
341                        let id_span = id.span();
342                        iter.next();
343                        if for_fresh {
344                            out.push(TokenTree::Punct(p));
345                        }
346                        out.push(TokenTree::Ident(proc_macro2::Ident::new(
347                            &rep_name, id_span,
348                        )));
349                        continue;
350                    }
351                }
352                out.push(TokenTree::Punct(p));
353            }
354            TokenTree::Group(g) => {
355                let inner = expand_concatenation_tokens(&g.stream(), mapping, for_fresh);
356                let mut new_group = Group::new(g.delimiter(), inner);
357                new_group.set_span(g.span());
358                out.push(TokenTree::Group(new_group));
359            }
360            other => out.push(other),
361        }
362    }
363    out.into_iter().collect()
364}
365
366fn fresh_variables(
367    node: &Node,
368    mapping: &HashMap<String, Node>,
369    next_id: &mut usize,
370    label_renames: &mut Vec<(String, String)>,
371) -> Node {
372    match node {
373        Node::Macro {
374            origin,
375            name,
376            variables,
377            body,
378        } => {
379            let mut my_mapping = mapping.clone();
380            let mut new_vars = Vec::new();
381            for var in variables {
382                if let Some(var_name) = var.variable_name() {
383                    *next_id += 1;
384                    let new_name = format!("_var{}", next_id);
385                    let new_var = Node::Variable {
386                        origin: var
387                            .origin()
388                            .cloned()
389                            .unwrap_or_else(crate::ast::builtin_origin),
390                        name: new_name.clone(),
391                        original_name: var_name.to_string(),
392                    };
393                    my_mapping.insert(var_name.to_string(), new_var.clone());
394                    new_vars.push(new_var);
395                }
396            }
397            Node::Macro {
398                origin: origin.clone(),
399                name: name.clone(),
400                variables: new_vars,
401                body: Box::new(fresh_variables(body, &my_mapping, next_id, label_renames)),
402            }
403        }
404        Node::MacroCall {
405            origin,
406            name,
407            operands,
408            annotation,
409            original_name,
410        } => {
411            let new_name = match mapping.get(name) {
412                Some(Node::Variable { name: rep, .. }) => rep.clone(),
413                _ => name.clone(),
414            };
415            Node::MacroCall {
416                origin: origin.clone(),
417                name: new_name,
418                operands: operands
419                    .iter()
420                    .map(|o| fresh_variables(o, mapping, next_id, label_renames))
421                    .collect(),
422                annotation: annotation.clone(),
423                original_name: original_name.clone(),
424            }
425        }
426        Node::Variable {
427            origin,
428            name,
429            original_name,
430        } => {
431            if contains_concat(name) {
432                let expanded = expand_concatenation(name, mapping, true);
433                Node::Variable {
434                    origin: origin.clone(),
435                    name: expanded,
436                    original_name: original_name.clone(),
437                }
438            } else if let Some(rep) = mapping.get(name) {
439                rep.clone()
440            } else {
441                node.clone()
442            }
443        }
444        Node::StructOffset {
445            origin,
446            struct_name,
447            field,
448        } => {
449            let dump = format!("{}::{}", struct_name, field);
450            if contains_concat(&dump) {
451                let expanded = expand_concatenation(&dump, mapping, true);
452                let mut parts: Vec<&str> = expanded.split("::").collect();
453                let f = parts.pop().unwrap_or("").to_string();
454                Node::StructOffset {
455                    origin: origin.clone(),
456                    struct_name: parts.join("::"),
457                    field: f,
458                }
459            } else {
460                node.clone()
461            }
462        }
463        Node::Label { origin, name } => {
464            // Align data lives in the LabelTable, so only rename `%` names here.
465            if contains_concat(name) {
466                let new_name = expand_concatenation(name, mapping, true);
467                // `Label#freshVariables` re-interns the renamed label through
468                // `Label.forName`, carrying the original's flags along.
469                label_renames.push((name.clone(), new_name.clone()));
470                Node::Label {
471                    origin: origin.clone(),
472                    name: new_name,
473                }
474            } else {
475                node.clone()
476            }
477        }
478        Node::LabelReference {
479            origin,
480            label,
481            offset,
482        } => {
483            if contains_concat(label) {
484                let new_label = expand_concatenation(label, mapping, true);
485                label_renames.push((label.clone(), new_label.clone()));
486                Node::LabelReference {
487                    origin: origin.clone(),
488                    label: new_label,
489                    offset: *offset,
490                }
491            } else {
492                node.clone()
493            }
494        }
495        Node::ConstExpr { origin, value } => Node::ConstExpr {
496            origin: origin.clone(),
497            value: expand_concatenation_tokens(value, mapping, true),
498        },
499        Node::Sizeof {
500            origin,
501            struct_name,
502        } => {
503            if contains_concat(struct_name) {
504                Node::Sizeof {
505                    origin: origin.clone(),
506                    struct_name: expand_concatenation(struct_name, mapping, true),
507                }
508            } else {
509                node.clone()
510            }
511        }
512        _ => match node {
513            Node::Add {
514                origin,
515                left,
516                right,
517            } => Node::Add {
518                origin: origin.clone(),
519                left: Box::new(fresh_variables(left, mapping, next_id, label_renames)),
520                right: Box::new(fresh_variables(right, mapping, next_id, label_renames)),
521            },
522            Node::Sequence { origin, list } => Node::Sequence {
523                origin: origin.clone(),
524                list: list
525                    .iter()
526                    .map(|n| fresh_variables(n, mapping, next_id, label_renames))
527                    .collect(),
528            },
529            Node::Instruction {
530                origin,
531                opcode,
532                operands,
533                annotation,
534            } => Node::Instruction {
535                origin: origin.clone(),
536                opcode: opcode.clone(),
537                operands: operands
538                    .iter()
539                    .map(|n| fresh_variables(n, mapping, next_id, label_renames))
540                    .collect(),
541                annotation: annotation.clone(),
542            },
543            _ => map_children(node, &mut |c| {
544                Ok(fresh_variables(c, mapping, next_id, label_renames))
545            })
546            .unwrap_or_else(|_| node.clone()),
547        },
548    }
549}
550
551fn substitute(
552    node: &Node,
553    mapping: &HashMap<String, Node>,
554    label_renames: &mut Vec<(String, String)>,
555) -> Node {
556    match node {
557        Node::Variable { origin, name, .. } => {
558            if contains_concat(name) {
559                let expanded = expand_concatenation(name, mapping, false);
560                Node::Variable {
561                    origin: origin.clone(),
562                    name: expanded.clone(),
563                    original_name: expanded,
564                }
565            } else if let Some(rep) = mapping.get(name) {
566                rep.clone()
567            } else {
568                node.clone()
569            }
570        }
571        Node::StructOffset {
572            origin,
573            struct_name,
574            field,
575        } => {
576            let dump = format!("{}::{}", struct_name, field);
577            if contains_concat(&dump) {
578                let expanded = expand_concatenation(&dump, mapping, false);
579                let mut parts: Vec<&str> = expanded.split("::").collect();
580                let f = parts.pop().unwrap_or("").to_string();
581                Node::StructOffset {
582                    origin: origin.clone(),
583                    struct_name: parts.join("::"),
584                    field: f,
585                }
586            } else {
587                node.clone()
588            }
589        }
590        Node::Macro {
591            origin,
592            name,
593            variables,
594            body,
595        } => {
596            let var_names: Vec<String> = variables
597                .iter()
598                .filter_map(|v| v.variable_name().map(|s| s.to_string()))
599                .collect();
600            let mut my_mapping = HashMap::new();
601            for (k, v) in mapping {
602                if !var_names.contains(k) {
603                    my_mapping.insert(k.clone(), v.clone());
604                }
605            }
606            Node::Macro {
607                origin: origin.clone(),
608                name: name.clone(),
609                variables: variables.clone(),
610                body: Box::new(substitute(body, &my_mapping, label_renames)),
611            }
612        }
613        Node::LabelReference {
614            origin,
615            label,
616            offset,
617        } => {
618            if contains_concat(label) {
619                let new_label = expand_concatenation(label, mapping, false);
620                label_renames.push((label.clone(), new_label.clone()));
621                Node::LabelReference {
622                    origin: origin.clone(),
623                    label: new_label,
624                    offset: *offset,
625                }
626            } else {
627                node.clone()
628            }
629        }
630        Node::ConstExpr { origin, value } => Node::ConstExpr {
631            origin: origin.clone(),
632            value: expand_concatenation_tokens(value, mapping, false),
633        },
634        Node::Sizeof {
635            origin,
636            struct_name,
637        } => {
638            if contains_concat(struct_name) {
639                Node::Sizeof {
640                    origin: origin.clone(),
641                    struct_name: expand_concatenation(struct_name, mapping, false),
642                }
643            } else {
644                node.clone()
645            }
646        }
647        Node::Label { origin, name } => {
648            if contains_concat(name) {
649                let new_name = expand_concatenation(name, mapping, false);
650                label_renames.push((name.clone(), new_name.clone()));
651                Node::Label {
652                    origin: origin.clone(),
653                    name: new_name,
654                }
655            } else {
656                node.clone()
657            }
658        }
659        Node::Sequence { origin, list } => {
660            // ConstDecls substitute lexically here.
661            let mut my_constants = mapping.clone();
662            let mut new_list = Vec::new();
663            for item in list {
664                if let Node::ConstDecl {
665                    variable, value, ..
666                } = item
667                {
668                    if let Some(name) = variable.variable_name() {
669                        let resolved = substitute(value, &my_constants, label_renames);
670                        my_constants.insert(name.to_string(), resolved);
671                    }
672                } else {
673                    new_list.push(substitute(item, &my_constants, label_renames));
674                }
675            }
676            Node::Sequence {
677                origin: origin.clone(),
678                list: new_list,
679            }
680        }
681        _ => map_children(node, &mut |c| Ok(substitute(c, mapping, label_renames)))
682            .unwrap_or_else(|_| node.clone()),
683    }
684}
685
686fn substitute_labels(
687    node: &Node,
688    mapping: &HashMap<String, String>,
689    seq_origin: &crate::code_origin::CodeOrigin,
690) -> Node {
691    match node {
692        Node::LocalLabel { name, .. } => {
693            let new_name = mapping.get(name).cloned().unwrap_or_else(|| name.clone());
694            Node::LocalLabel {
695                origin: seq_origin.clone(),
696                name: new_name,
697            }
698        }
699        Node::LocalLabelReference { origin, label } => {
700            let new_label = mapping.get(label).cloned().unwrap_or_else(|| label.clone());
701            Node::LocalLabelReference {
702                origin: origin.clone(),
703                label: new_label,
704            }
705        }
706        _ => map_children(node, &mut |c| Ok(substitute_labels(c, mapping, seq_origin)))
707            .unwrap_or_else(|_| node.clone()),
708    }
709}
710
711/// Tracks macro-expansion state across recursive calls.
712#[derive(Default)]
713struct DemacroState {
714    next_var_id: usize,
715    stack: Vec<Node>,
716    label_names: std::collections::HashSet<String>,
717    next_unique_label_id: usize,
718    /// Records `(old, new)` pairs `substitute` makes for `%...%` label names.
719    label_renames: Vec<(String, String)>,
720}
721
722impl DemacroState {
723    fn unique_local_label(&mut self, comment: &str) -> String {
724        let mut candidate = format!("_{}", comment);
725        if self.label_names.contains(&candidate) {
726            loop {
727                candidate = format!("_{}_{}", self.next_unique_label_id, comment);
728                if !self.label_names.contains(&candidate) {
729                    break;
730                }
731                self.next_unique_label_id += 1;
732            }
733        }
734        self.label_names.insert(candidate.clone());
735        candidate
736    }
737}
738
739#[derive(Default)]
740struct MacroEnv {
741    scopes: Vec<HashMap<String, std::rc::Rc<Node>>>,
742}
743
744impl MacroEnv {
745    fn push(&mut self) {
746        self.scopes.push(HashMap::new());
747    }
748
749    fn pop(&mut self) {
750        self.scopes.pop();
751    }
752
753    fn insert(&mut self, name: String, macro_node: std::rc::Rc<Node>) {
754        match self.scopes.last_mut() {
755            Some(scope) => {
756                scope.insert(name, macro_node);
757            }
758            None => {
759                let mut scope = HashMap::new();
760                scope.insert(name, macro_node);
761                self.scopes.push(scope);
762            }
763        }
764    }
765
766    fn lookup(&self, name: &str) -> Option<std::rc::Rc<Node>> {
767        for scope in self.scopes.iter().rev() {
768            if let Some(found) = scope.get(name) {
769                return Some(found.clone());
770            }
771        }
772        None
773    }
774}
775
776/// Expands every macro invocation in `node`.
777///
778/// Inlines `const` declarations. Only core instruction and
779/// control-flow nodes remain.
780///
781/// # Errors
782///
783/// - Returns an error if a macro call passes the wrong number of arguments.
784/// - Returns an error if an unresolved variable or macro name survives expansion.
785/// - Returns an error if a settings predicate does not fold to `True`/`False`.
786pub fn demacroify(node: &Node) -> Result<Node, String> {
787    Ok(demacroify_recording(node)?.0)
788}
789
790/// Expands macros like [`demacroify`], also returning label renames.
791///
792/// Each `(old, new)` pair records a local label freshened per call site.
793///
794/// # Errors
795///
796/// Returns an error for any reason [`demacroify`] can.
797pub fn demacroify_recording(node: &Node) -> Result<(Node, Vec<(String, String)>), String> {
798    let mut state = DemacroState::default();
799    collect_local_label_names(node, &mut state.label_names);
800    let mut env = MacroEnv::default();
801    let result = demacroify_with(node, &mut env, &mut state)?;
802    Ok((result, state.label_renames))
803}
804
805fn collect_local_label_names(node: &Node, out: &mut std::collections::HashSet<String>) {
806    if let Node::LocalLabel { name, .. } = node {
807        out.insert(name.clone());
808    }
809    for child in node.children() {
810        collect_local_label_names(child, out);
811    }
812}
813
814fn demacroify_with(
815    node: &Node,
816    env: &mut MacroEnv,
817    state: &mut DemacroState,
818) -> Result<Node, String> {
819    match node {
820        Node::Sequence { origin, list } => {
821            env.push();
822            for item in list {
823                if let Node::Macro {
824                    name: Some(name), ..
825                } = item
826                {
827                    let fresh = fresh_variables(
828                        item,
829                        &HashMap::new(),
830                        &mut state.next_var_id,
831                        &mut state.label_renames,
832                    );
833                    env.insert(name.clone(), std::rc::Rc::new(fresh));
834                }
835            }
836            let mut new_list = Vec::new();
837            for item in list {
838                match item {
839                    Node::Macro { .. } => {}
840                    Node::MacroCall {
841                        origin: call_origin,
842                        name,
843                        operands,
844                        annotation,
845                        original_name,
846                    } => {
847                        state.stack.push(item.clone());
848                        let def = env.lookup(name).ok_or_else(|| {
849                            format!(
850                                "Could not find macro {} at {}",
851                                original_name,
852                                call_origin.origin_string()
853                            )
854                        })?;
855                        let (params, body) = match def.as_ref() {
856                            Node::Macro {
857                                variables, body, ..
858                            } => (variables.clone(), body.clone()),
859                            _ => {
860                                return Err(format!(
861                                    "macro {} is not a macro at {}",
862                                    name,
863                                    call_origin.origin_string()
864                                ))
865                            }
866                        };
867                        if operands.len() != params.len() {
868                            return Err(format!(
869                                "Argument count mismatch for call to {} (expected {} but got {}) at {}",
870                                original_name,
871                                params.len(),
872                                operands.len(),
873                                call_origin.origin_string()
874                            ));
875                        }
876                        let mut mapping: HashMap<String, Node> = HashMap::new();
877                        env.push();
878                        for (idx, param) in params.iter().enumerate() {
879                            let param_name = param
880                                .variable_name()
881                                .ok_or_else(|| {
882                                    format!("bad macro param at {}", param.origin_string())
883                                })?
884                                .to_string();
885                            let arg = &operands[idx];
886                            if let Some(arg_name) = arg.variable_name() {
887                                if let Some(target) = env.lookup(arg_name) {
888                                    env.insert(param_name.clone(), target);
889                                    continue;
890                                }
891                            }
892                            if matches!(arg, Node::Macro { .. }) {
893                                let fresh = fresh_variables(
894                                    arg,
895                                    &HashMap::new(),
896                                    &mut state.next_var_id,
897                                    &mut state.label_renames,
898                                );
899                                // The passed macro may be anonymous (e.g.
900                                // `forEachGPCalleeSave(macro (reg, index) ... end)`),
901                                // so it cannot be keyed by name. It is bound
902                                // under the *parameter's* (freshened) name.
903                                env.insert(param_name.clone(), std::rc::Rc::new(fresh));
904                                continue;
905                            }
906                            // Value arguments bind in `mapping` only. The macro
907                            // environment stays untouched so an outer macro
908                            // of the same name survives.
909                            mapping.insert(param_name, arg.clone());
910                        }
911                        if let Some(ann) = annotation {
912                            new_list.push(Node::Instruction {
913                                origin: call_origin.clone(),
914                                opcode: "localAnnotation".to_string(),
915                                operands: vec![],
916                                annotation: Some(ann.clone()),
917                            });
918                        }
919                        let expanded = substitute(&body, &mapping, &mut state.label_renames);
920                        let expanded = demacroify_with(&expanded, env, state)?;
921                        env.pop();
922                        let renamed = rename_labels(&expanded, Some(original_name), state);
923                        match renamed {
924                            Node::Sequence { list: inner, .. } => new_list.extend(inner),
925                            other => new_list.push(other),
926                        }
927                        state.stack.pop();
928                    }
929                    other => new_list.push(demacroify_with(other, env, state)?),
930                }
931            }
932            env.pop();
933            let seq = Node::Sequence {
934                origin: origin.clone(),
935                list: new_list,
936            };
937            Ok(substitute(&seq, &HashMap::new(), &mut state.label_renames))
938        }
939        _ => map_children(node, &mut |c| demacroify_with(c, env, state)),
940    }
941}
942
943fn rename_labels(node: &Node, comment: Option<&str>, state: &mut DemacroState) -> Node {
944    let (seq_origin, seq) = match node {
945        Node::Sequence { origin, list } => (origin, list),
946        _ => return node.clone(),
947    };
948    let mut mapping: HashMap<String, String> = HashMap::new();
949    for item in seq {
950        if let Node::LocalLabel { name, .. } = item {
951            // `LocalLabel#cleanName`: `.foo` -> `_foo`, otherwise unchanged.
952            let clean = match name.strip_prefix('.') {
953                Some(rest) => format!("_{}", rest),
954                None => name.clone(),
955            };
956            let comment_prefix = match comment {
957                Some(c) => format!("{}_", c),
958                None => String::new(),
959            };
960            let new_name = state.unique_local_label(&format!("{}{}", comment_prefix, clean));
961            mapping.insert(name.clone(), new_name);
962        }
963    }
964    substitute_labels(node, &mapping, seq_origin)
965}
966
967fn offset_key(node: &Node) -> String {
968    node.dump()
969}
970
971/// Collects the offset, size, and const keys `node` references.
972///
973/// Groups run offsets, then sizes, then consts. Keys are node dumps, sorted
974/// within each group.
975pub fn offset_keys(node: &Node) -> Vec<String> {
976    let mut offsets = std::collections::BTreeSet::new();
977    let mut sizes = std::collections::BTreeSet::new();
978    let mut consts = std::collections::BTreeSet::new();
979    collect_offset_keys(node, &mut offsets, &mut sizes, &mut consts);
980    let mut out: Vec<String> = offsets.into_iter().chain(sizes).chain(consts).collect();
981    let _ = &mut out;
982    out
983}
984
985fn collect_offset_keys(
986    node: &Node,
987    offsets: &mut std::collections::BTreeSet<String>,
988    sizes: &mut std::collections::BTreeSet<String>,
989    consts: &mut std::collections::BTreeSet<String>,
990) {
991    match node {
992        Node::StructOffset { .. } => {
993            offsets.insert(offset_key(node));
994        }
995        Node::Sizeof { .. } => {
996            sizes.insert(offset_key(node));
997        }
998        Node::ConstExpr { .. } => {
999            consts.insert(offset_key(node));
1000        }
1001        _ => {}
1002    }
1003    for child in node.children() {
1004        collect_offset_keys(child, offsets, sizes, consts);
1005    }
1006}
1007
1008/// Substitutes each offset node in `node` with the integer `map` holds.
1009///
1010/// Offset nodes are `StructOffset`, `Sizeof`, and `ConstExpr`, keyed by node
1011/// dump.
1012///
1013/// # Errors
1014///
1015/// Returns an error if `map` lacks the key for an offset node.
1016pub fn resolve_offsets(node: &Node, map: &HashMap<String, i64>) -> Result<Node, String> {
1017    match node {
1018        Node::StructOffset { .. } | Node::Sizeof { .. } | Node::ConstExpr { .. } => {
1019            let key = offset_key(node);
1020            match map.get(&key) {
1021                Some(v) => Ok(Node::Immediate {
1022                    origin: node.origin_cloned(),
1023                    value: *v as i128,
1024                }),
1025                None => Err(format!(
1026                    "Could not find {} in offsets map at {}",
1027                    node.dump(),
1028                    node.origin_string()
1029                )),
1030            }
1031        }
1032        _ => map_children(node, &mut |c| resolve_offsets(c, map)),
1033    }
1034}
1035fn symbolic_operand(node: &Node) -> Option<String> {
1036    match node {
1037        Node::RustConst { expr, .. } => Some(quote::quote!(#expr).to_string()),
1038        Node::Immediate { value, .. } => Some(value.to_string()),
1039        _ => None,
1040    }
1041}
1042
1043/// Builds the `Node::RustConst` for a folded symbolic expression. The ident
1044/// is derived from the expression text so identical sub-expressions share one
1045/// `global_asm!` const argument.
1046///
1047/// `expr` is built by this module purely from immediate values and other
1048/// `RustConst` expressions rendered back to text (see `symbolic_operand`),
1049/// so it is always syntactically valid Rust; the `Verbatim` fallback below
1050/// only guards against that invariant somehow not holding, rather than
1051/// being an expected path.
1052fn symbolic_fold(origin: &crate::code_origin::CodeOrigin, expr: String) -> Node {
1053    let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
1054    for byte in expr.as_bytes() {
1055        hash ^= *byte as u64;
1056        hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
1057    }
1058    let parsed = syn::parse_str::<syn::Expr>(&expr)
1059        .unwrap_or_else(|_| syn::Expr::Verbatim(expr.parse().unwrap_or_default()));
1060    Node::RustConst {
1061        origin: origin.clone(),
1062        ident: format!("OFFLINE_ASM_EXPR_{:016x}", hash),
1063        expr: parsed,
1064    }
1065}
1066
1067/// Folds constant sub-expressions in `node` with wrapping arithmetic.
1068///
1069/// Label-relative additions fold into the reference offset. Symbolic operands
1070/// fold into shared `Node::RustConst` nodes.
1071pub fn fold(node: &Node) -> Node {
1072    match node {
1073        Node::Add {
1074            origin,
1075            left,
1076            right,
1077        } => {
1078            let l = fold(left);
1079            let r = fold(right);
1080            match (&l, &r) {
1081                (Node::Immediate { value: lv, .. }, Node::LabelReference { .. }) => {
1082                    return r.plus_offset(*lv).unwrap_or_else(|| node.clone())
1083                }
1084                (Node::LabelReference { .. }, Node::Immediate { value: rv, .. }) => {
1085                    return l.plus_offset(*rv).unwrap_or_else(|| node.clone())
1086                }
1087                _ => {}
1088            }
1089            match (l.immediate_value(), r.immediate_value()) {
1090                (Some(a), Some(b)) => Node::Immediate {
1091                    origin: origin.clone(),
1092                    value: a.wrapping_add(b),
1093                },
1094                _ => match (symbolic_operand(&l), symbolic_operand(&r)) {
1095                    (Some(a), Some(b)) => symbolic_fold(origin, format!("({} + {})", a, b)),
1096                    _ => Node::Add {
1097                        origin: origin.clone(),
1098                        left: Box::new(l),
1099                        right: Box::new(r),
1100                    },
1101                },
1102            }
1103        }
1104        Node::Sub {
1105            origin,
1106            left,
1107            right,
1108        } => {
1109            let l = fold(left);
1110            let r = fold(right);
1111            if let (Node::LabelReference { .. }, Some(b)) = (&l, r.immediate_value()) {
1112                return l.plus_offset(-b).unwrap_or_else(|| node.clone());
1113            }
1114            match (l.immediate_value(), r.immediate_value()) {
1115                (Some(a), Some(b)) => Node::Immediate {
1116                    origin: origin.clone(),
1117                    value: a.wrapping_sub(b),
1118                },
1119                _ => match (symbolic_operand(&l), symbolic_operand(&r)) {
1120                    (Some(a), Some(b)) => symbolic_fold(origin, format!("({} - {})", a, b)),
1121                    _ => Node::Sub {
1122                        origin: origin.clone(),
1123                        left: Box::new(l),
1124                        right: Box::new(r),
1125                    },
1126                },
1127            }
1128        }
1129        Node::Mul {
1130            origin,
1131            left,
1132            right,
1133        } => {
1134            let (l, r) = (fold(left), fold(right));
1135            match (l.immediate_value(), r.immediate_value()) {
1136                (Some(a), Some(b)) => Node::Immediate {
1137                    origin: origin.clone(),
1138                    value: a.wrapping_mul(b),
1139                },
1140                _ => match (symbolic_operand(&l), symbolic_operand(&r)) {
1141                    (Some(a), Some(b)) => symbolic_fold(origin, format!("({} * {})", a, b)),
1142                    _ => Node::Mul {
1143                        origin: origin.clone(),
1144                        left: Box::new(l),
1145                        right: Box::new(r),
1146                    },
1147                },
1148            }
1149        }
1150        Node::Neg { origin, child } => {
1151            let c = fold(child);
1152            match c.immediate_value() {
1153                Some(v) => Node::Immediate {
1154                    origin: origin.clone(),
1155                    value: v.wrapping_neg(),
1156                },
1157                None => match symbolic_operand(&c) {
1158                    Some(v) => symbolic_fold(origin, format!("-({})", v)),
1159                    None => Node::Neg {
1160                        origin: origin.clone(),
1161                        child: Box::new(c),
1162                    },
1163                },
1164            }
1165        }
1166        Node::Or {
1167            origin,
1168            left,
1169            right,
1170        } => {
1171            let (l, r) = (fold(left), fold(right));
1172            match (l.immediate_value(), r.immediate_value()) {
1173                (Some(a), Some(b)) => Node::Immediate {
1174                    origin: origin.clone(),
1175                    value: a | b,
1176                },
1177                _ => match (symbolic_operand(&l), symbolic_operand(&r)) {
1178                    (Some(a), Some(b)) => symbolic_fold(origin, format!("({} | {})", a, b)),
1179                    _ => Node::Or {
1180                        origin: origin.clone(),
1181                        left: Box::new(l),
1182                        right: Box::new(r),
1183                    },
1184                },
1185            }
1186        }
1187        Node::And {
1188            origin,
1189            left,
1190            right,
1191        } => {
1192            let (l, r) = (fold(left), fold(right));
1193            match (l.immediate_value(), r.immediate_value()) {
1194                (Some(a), Some(b)) => Node::Immediate {
1195                    origin: origin.clone(),
1196                    value: a & b,
1197                },
1198                _ => match (symbolic_operand(&l), symbolic_operand(&r)) {
1199                    (Some(a), Some(b)) => symbolic_fold(origin, format!("({} & {})", a, b)),
1200                    _ => Node::And {
1201                        origin: origin.clone(),
1202                        left: Box::new(l),
1203                        right: Box::new(r),
1204                    },
1205                },
1206            }
1207        }
1208        Node::Xor {
1209            origin,
1210            left,
1211            right,
1212        } => {
1213            let (l, r) = (fold(left), fold(right));
1214            match (l.immediate_value(), r.immediate_value()) {
1215                (Some(a), Some(b)) => Node::Immediate {
1216                    origin: origin.clone(),
1217                    value: a ^ b,
1218                },
1219                _ => match (symbolic_operand(&l), symbolic_operand(&r)) {
1220                    (Some(a), Some(b)) => symbolic_fold(origin, format!("({} ^ {})", a, b)),
1221                    _ => Node::Xor {
1222                        origin: origin.clone(),
1223                        left: Box::new(l),
1224                        right: Box::new(r),
1225                    },
1226                },
1227            }
1228        }
1229        Node::Bitnot { origin, child } => {
1230            let c = fold(child);
1231            match c.immediate_value() {
1232                Some(v) => Node::Immediate {
1233                    origin: origin.clone(),
1234                    value: !v,
1235                },
1236                None => match symbolic_operand(&c) {
1237                    Some(v) => symbolic_fold(origin, format!("!({})", v)),
1238                    None => Node::Bitnot {
1239                        origin: origin.clone(),
1240                        child: Box::new(c),
1241                    },
1242                },
1243            }
1244        }
1245        _ => map_children(node, &mut |c| Ok(fold(c))).unwrap_or_else(|_| node.clone()),
1246    }
1247}
1248
1249/// Runs [`demacroify`], then [`resolve_offsets`], then constant-folds the
1250/// result.
1251///
1252/// # Errors
1253///
1254/// Returns an error for any reason [`demacroify`] or [`resolve_offsets`] can.
1255pub fn resolve(node: &Node, map: &HashMap<String, i64>) -> Result<Node, String> {
1256    let demacroed = demacroify(node)?;
1257    let resolved = resolve_offsets(&demacroed, map)?;
1258    Ok(fold(&resolved))
1259}
1260
1261/// Checks that expansion and offset stages already ran over `node`.
1262///
1263/// Rejects any surviving macro, offset, or settings node.
1264///
1265/// # Errors
1266///
1267/// Returns an error naming the first node an earlier stage should have
1268/// eliminated.
1269pub fn validate(node: &Node) -> Result<(), String> {
1270    match node {
1271        Node::Sequence { list, .. } => {
1272            for item in list {
1273                validate(item)?;
1274                match item {
1275                    Node::Instruction { .. }
1276                    | Node::Label { .. }
1277                    | Node::LocalLabel { .. }
1278                    | Node::Skip { .. } => {}
1279                    other => {
1280                        return Err(format!(
1281                            "Unexpected {} at {}",
1282                            other.dump(),
1283                            other.origin_string()
1284                        ))
1285                    }
1286                }
1287            }
1288            Ok(())
1289        }
1290        Node::Immediate { .. }
1291        | Node::StringLiteral { .. }
1292        | Node::Register { .. }
1293        | Node::FpRegister { .. }
1294        | Node::VecRegister { .. }
1295        | Node::SpecialRegister { .. }
1296        | Node::Error { .. }
1297        | Node::LabelReference { .. }
1298        | Node::LocalLabelReference { .. }
1299        | Node::Skip { .. }
1300        | Node::Label { .. }
1301        | Node::LocalLabel { .. }
1302        | Node::RustConst { .. } => {
1303            if let Node::Label { name, .. } = node {
1304                if name.contains('%') {
1305                    return Err(format!(
1306                        "Unresolved substitution in Label {} at {}",
1307                        name,
1308                        node.origin_string()
1309                    ));
1310                }
1311            }
1312            Ok(())
1313        }
1314        Node::Address { base, offset, .. } => {
1315            validate(base)?;
1316            validate(offset)?;
1317            Ok(())
1318        }
1319        Node::BaseIndex {
1320            base,
1321            index,
1322            scale,
1323            offset,
1324            ..
1325        } => {
1326            validate(base)?;
1327            validate(index)?;
1328            validate(scale)?;
1329            validate(offset)?;
1330            Ok(())
1331        }
1332        Node::AbsoluteAddress { address, .. } => validate(address),
1333        Node::Instruction { operands, .. } => {
1334            for op in operands {
1335                validate(op)?;
1336            }
1337            Ok(())
1338        }
1339        Node::Sub { left, right, .. } => {
1340            if !left.is_immediate_operand() {
1341                return Err(format!(
1342                    "Invalid operand {} to immediate subtraction",
1343                    left.dump()
1344                ));
1345            }
1346            if !right.is_immediate_operand() {
1347                return Err(format!(
1348                    "Invalid operand {} to immediate subtraction",
1349                    right.dump()
1350                ));
1351            }
1352            Ok(())
1353        }
1354        Node::Variable { name, .. } if is_bare_arg_name(name) => Err(format!(
1355            "{name} is not a register; offlineasm has no built-in argument-register \
1356             aliases, declare it yourself, e.g. `const {name} = t6`"
1357        )),
1358        other => Err(format!(
1359            "Unresolved '{}' at {}",
1360            other.dump(),
1361            other.origin_string()
1362        )),
1363    }
1364}
1365
1366/// Whether `name` is exactly `arg0`-`arg7`: the removed non-upstream ABI
1367/// aliases, called out with a specific hint instead of the generic
1368/// "Unresolved" error an arbitrary unbound variable gets.
1369fn is_bare_arg_name(name: &str) -> bool {
1370    matches!(
1371        name,
1372        "arg0" | "arg1" | "arg2" | "arg3" | "arg4" | "arg5" | "arg6" | "arg7"
1373    )
1374}