Skip to main content

assembler/
ast.rs

1//! Abstract syntax representation.   It's mostly not actually a tree.
2//!
3//! In the AST, terminology follows the TX-2 assembler's
4//! documentation, and this doesn't always match modern usage.  In
5//! particular, "block" is used to refer to a contiguously-allocated
6//! sequence of instructions which share an origin statement.  Such as
7//! the RC-block.  This is not the same as a block in a language like
8//! C, where "block" is also a declaration-scoping construct.
9//!
10//! Instead, in the TX-2 assembler, scopes are introduced by macro
11//! expansion.  So, a "block" may contain some instructions followed
12//! by a macro-expansion (which has an associated scope) which itself
13//! might contain a macro-expansion, with another scope.
14use std::borrow::Cow;
15use std::cmp::Ordering;
16use std::collections::BTreeMap;
17use std::error::Error;
18use std::fmt::{self, Display, Formatter, Octal, Write};
19use std::hash::Hash;
20use std::ops::{Shl, Shr};
21
22use tracing::{Level, event};
23
24use base::charset::{Script, subscript_char, superscript_char};
25use base::prelude::*;
26use base::u18;
27
28use super::collections::OneOrMore;
29use super::eval::{
30    Evaluate, EvaluationContext, EvaluationFailure, HereValue, ScopeIdentifier,
31    evaluate_elevated_symbol,
32};
33use super::glyph;
34use super::listing::{Listing, ListingLine};
35use super::manuscript::{MacroParameterBindings, MacroParameterValue};
36use super::memorymap::MemoryMap;
37use super::memorymap::RcAllocator;
38use super::memorymap::RcWordAllocationFailure;
39use super::memorymap::{RcWordKind, RcWordSource};
40use super::source::Source;
41use super::span::{Span, Spanned, span};
42use super::state::MacroLookup;
43use super::symbol::{InconsistentSymbolUse, SymbolContext, SymbolName};
44use super::symtab::{
45    BadSymbolDefinition, ExplicitDefinition, ExplicitSymbolTable, FinalSymbolDefinition,
46    FinalSymbolTable, FinalSymbolType, ImplicitSymbolTable, IndexRegisterAssigner, TagDefinition,
47    record_undefined_symbol_or_return_failure,
48};
49use super::types::{AssemblerFailure, BlockIdentifier, ProgramError};
50mod asteval;
51
52/// Indicates the action to be taken when a macro invocation does not
53/// specify a value for one of its dummy parameters.
54#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
55pub(crate) enum OnUnboundMacroParameter {
56    ElideReference,
57    SubstituteZero,
58}
59
60/// Records a reference to or definition of a symbol.
61#[derive(Debug, PartialEq, Eq, Clone)]
62pub(crate) enum SymbolUse {
63    Reference(SymbolContext),
64    Definition(ExplicitDefinition),
65}
66
67/// Allows updates to the values of RC-words.
68///
69/// We use this to separate the activities of selecting addresses for
70/// RC-words, and determining their values.
71pub(crate) trait RcUpdater {
72    fn update(&mut self, address: Address, value: Unsigned36Bit);
73}
74
75/// Eventually we will support symbolic expressions.
76#[derive(Debug, Clone, PartialEq, Eq)]
77pub(crate) struct LiteralValue {
78    span: Span,
79    elevation: Script,
80    value: Unsigned36Bit,
81}
82
83impl LiteralValue {
84    pub(super) fn value(&self) -> Unsigned36Bit {
85        self.value << self.elevation.shift()
86    }
87
88    #[cfg(test)]
89    pub(super) fn unshifted_value(&self) -> Unsigned36Bit {
90        self.value
91    }
92}
93
94impl Spanned for LiteralValue {
95    fn span(&self) -> Span {
96        self.span
97    }
98}
99
100impl From<(Span, Script, Unsigned36Bit)> for LiteralValue {
101    fn from((span, elevation, value): (Span, Script, Unsigned36Bit)) -> LiteralValue {
102        LiteralValue {
103            span,
104            elevation,
105            value,
106        }
107    }
108}
109
110impl std::fmt::Display for LiteralValue {
111    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
112        let s = self.value.to_string();
113        format_elevated_chars(f, self.elevation, &s)
114    }
115}
116
117/// Write the name of a glyph with optional superscript / subscript
118/// indicator.
119fn write_glyph_name(f: &mut Formatter<'_>, elevation: Script, ch: char) -> fmt::Result {
120    let prefix: &'static str = match elevation {
121        Script::Sub => "sub_",
122        Script::Super => "sup_",
123        Script::Normal => "",
124    };
125    let name: &'static str = match glyph::name_from_glyph(ch) {
126        Some(n) => n,
127        None => {
128            panic!("There is no glyph name for character '{ch}'");
129        }
130    };
131    write!(f, "@{prefix}{name}@")
132}
133
134/// Convert a normal string to subscript or superscript (or leave it as-is).
135fn elevated_string(s: &str, elevation: Script) -> Cow<'_, str> {
136    match elevation {
137        Script::Normal => Cow::Borrowed(s),
138        Script::Super => Cow::Owned(
139            s.chars()
140                .map(|ch| superscript_char(ch).unwrap_or(ch))
141                .collect(),
142        ),
143        Script::Sub => Cow::Owned(
144            s.chars()
145                .map(|ch| subscript_char(ch).unwrap_or(ch))
146                .collect(),
147        ),
148    }
149}
150/// Format a string in super/sub/normal script, using `@...@` where necessary.
151fn format_elevated_chars(f: &mut Formatter<'_>, elevation: Script, s: &str) -> fmt::Result {
152    // TODO: do we really need both this and elevated_string?
153    match elevation {
154        Script::Normal => {
155            f.write_str(s)?;
156        }
157        Script::Super => {
158            for ch in s.chars() {
159                match superscript_char(ch) {
160                    Ok(superchar) => {
161                        f.write_char(superchar)?;
162                    }
163                    Err(_) => {
164                        write_glyph_name(f, elevation, ch)?;
165                    }
166                }
167            }
168        }
169        Script::Sub => {
170            for ch in s.chars() {
171                match subscript_char(ch) {
172                    Ok(sub) => {
173                        f.write_char(sub)?;
174                    }
175                    Err(_) => {
176                        write_glyph_name(f, elevation, ch)?;
177                    }
178                }
179            }
180        }
181    }
182    Ok(())
183}
184
185/// The Users Handbook specifies that the operators are the four
186/// arithmetic operators (+-×/) and the logical operators ∧ (AND), ∨
187/// (OR), and a circled ∨ meaning XOR.
188#[derive(Debug, Clone, Copy, PartialEq, Eq)]
189pub(crate) enum Operator {
190    Add,
191    LogicalAnd,
192    LogicalOr, // "union" in the Users Handbook
193    LogicalXor,
194    Multiply,
195    Subtract,
196    Divide,
197}
198
199impl std::fmt::Display for Operator {
200    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
201        f.write_str(match self {
202            Operator::Add => "+",
203            Operator::LogicalAnd => "∧",
204            Operator::LogicalOr => "∨",
205            // For LogicalXor we would ideally like to use
206            // "\u{20DD}\u{2228}" to reflect the symbol the TX-2 used.
207            // However, the terminals I have checked don't seem to
208            // supoprt this.  Other choices include U+22BB (⊻) and
209            // "@xor@".  We choose @xor@ so that diagnostic messages
210            // relate more closely to the assembler input.
211            Operator::LogicalXor => "@xor@",
212            Operator::Multiply => "\u{00D7}",
213            Operator::Subtract => "-",
214            Operator::Divide => "/",
215        })
216    }
217}
218
219#[test]
220fn test_display_operators() {
221    let mut output = String::new();
222    for op in [
223        Operator::Add,
224        Operator::LogicalAnd,
225        Operator::LogicalOr,
226        Operator::LogicalXor,
227        Operator::Multiply,
228        Operator::Subtract,
229        Operator::Divide,
230    ] {
231        let _ = write!(output, "{op}");
232    }
233    assert_eq!(output, "+∧∨@xor@\u{00D7}-/");
234}
235
236#[derive(Debug, Clone, PartialEq, Eq)]
237pub(crate) struct SignedAtom {
238    pub(super) negated: bool,
239    pub(super) span: Span,
240    pub(super) magnitude: Atom,
241}
242
243impl From<Atom> for SignedAtom {
244    fn from(magnitude: Atom) -> Self {
245        Self {
246            negated: false,
247            span: magnitude.span(),
248            magnitude,
249        }
250    }
251}
252
253impl SignedAtom {
254    fn symbol_uses(
255        &self,
256        block_id: BlockIdentifier,
257        block_offset: Unsigned18Bit,
258    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
259    {
260        self.magnitude.symbol_uses(block_id, block_offset)
261    }
262
263    fn substitute_macro_parameters<M: MacroLookup>(
264        &self,
265        param_values: &MacroParameterBindings,
266        on_missing: OnUnboundMacroParameter,
267        macros: &M,
268    ) -> Option<SignedAtom> {
269        self.magnitude
270            .substitute_macro_parameters(param_values, on_missing, macros)
271            .map(|magnitude| SignedAtom {
272                magnitude,
273                ..self.clone()
274            })
275    }
276
277    fn allocate_rc_words<R: RcAllocator>(
278        &mut self,
279        explicit_symtab: &mut ExplicitSymbolTable,
280        implicit_symtab: &mut ImplicitSymbolTable,
281        rc_allocator: &mut R,
282    ) -> Result<(), RcWordAllocationFailure> {
283        self.magnitude
284            .allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)
285    }
286}
287
288impl Spanned for SignedAtom {
289    fn span(&self) -> Span {
290        self.span
291    }
292}
293
294impl std::fmt::Display for SignedAtom {
295    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
296        if self.negated {
297            write!(f, "-{}", self.magnitude)
298        } else {
299            write!(f, "{}", self.magnitude)
300        }
301    }
302}
303
304/// Represents an arithmetic expression.
305///
306/// In the TX-2's M4 assembly language, arithmetic expressions are
307/// constants.  In other words, the assembler evaluates them to a
308/// specific 36-bit value which is emitted into the output.
309#[derive(Debug, Clone, PartialEq, Eq)]
310pub(crate) struct ArithmeticExpression {
311    pub(crate) first: SignedAtom,
312    pub(crate) tail: Vec<(Operator, SignedAtom)>,
313}
314
315impl std::fmt::Display for ArithmeticExpression {
316    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
317        write!(f, "{}", self.first)?;
318        for (op, atom) in &self.tail {
319            write!(f, "{op}{atom}")?;
320        }
321        Ok(())
322    }
323}
324
325impl From<SignedAtom> for ArithmeticExpression {
326    fn from(a: SignedAtom) -> ArithmeticExpression {
327        ArithmeticExpression {
328            first: a,
329            tail: Vec::new(),
330        }
331    }
332}
333
334impl From<Atom> for ArithmeticExpression {
335    fn from(a: Atom) -> ArithmeticExpression {
336        ArithmeticExpression::from(SignedAtom::from(a))
337    }
338}
339
340impl From<SymbolOrLiteral> for ArithmeticExpression {
341    fn from(value: SymbolOrLiteral) -> Self {
342        ArithmeticExpression::from(Atom::from(value))
343    }
344}
345
346impl Spanned for ArithmeticExpression {
347    fn span(&self) -> Span {
348        let start = self.first.span().start;
349        let end = self
350            .tail
351            .last()
352            .map_or(self.first.span().end, |(_op, atom)| atom.span().end);
353        span(start..end)
354    }
355}
356
357impl ArithmeticExpression {
358    pub(super) fn with_tail(
359        first: SignedAtom,
360        tail: Vec<(Operator, SignedAtom)>,
361    ) -> ArithmeticExpression {
362        ArithmeticExpression { first, tail }
363    }
364
365    fn symbol_uses(
366        &self,
367        block_id: BlockIdentifier,
368        block_offset: Unsigned18Bit,
369    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
370    {
371        let mut result = Vec::with_capacity(1 + self.tail.len());
372        result.extend(self.first.symbol_uses(block_id, block_offset));
373        result.extend(
374            self.tail
375                .iter()
376                .flat_map(|(_op, x)| x.symbol_uses(block_id, block_offset)),
377        );
378        result.into_iter()
379    }
380
381    fn eval_binop(left: Unsigned36Bit, binop: Operator, right: Unsigned36Bit) -> Unsigned36Bit {
382        match binop {
383            Operator::Add => match left.checked_add(right) {
384                Some(result) => result,
385                None => {
386                    // TODO: checked_add doesn't currently match the
387                    // operation of the TX-2 ADD instruction with
388                    // respect to (for example) overflow.  See
389                    // examples 4 and 5 for the ADD instruciton in the
390                    // Users Handbook, for instance.
391                    //
392                    // We also come here for cases like 4 + -2,
393                    // because (in the context of this function) -2
394                    // appears to be a large unsigned number.
395                    todo!(
396                        "{left:>012o}+{right:>012o} overflowed; please fix https://github.com/TX-2/TX-2-simulator/issues/146"
397                    )
398                }
399            },
400            Operator::Subtract => match left.checked_sub(right) {
401                Some(result) => result,
402                None => {
403                    todo!(
404                        "{left:>012o}-{right:>012o} overflowed; please fix https://github.com/TX-2/TX-2-simulator/issues/146"
405                    )
406                }
407            },
408            Operator::Multiply => match left.checked_mul(right) {
409                Some(result) => result,
410                None => {
411                    todo!("multiplication overflow occurred but this is not implemented")
412                }
413            },
414            Operator::Divide => {
415                let sleft: Signed36Bit = left.reinterpret_as_signed();
416                let sright: Signed36Bit = right.reinterpret_as_signed();
417                match sleft.checked_div(sright) {
418                    Some(result) => result.reinterpret_as_unsigned(),
419                    None => {
420                        if sright.is_positive_zero() {
421                            !left
422                        } else if sright.is_negative_zero() {
423                            left
424                        } else {
425                            unreachable!("division overflow occurred but RHS is not zero")
426                        }
427                    }
428                }
429            }
430            Operator::LogicalAnd => left.and(right.into()),
431            Operator::LogicalOr => left.bitor(right.into()),
432            Operator::LogicalXor => left ^ right,
433        }
434    }
435
436    fn substitute_macro_parameters<M: MacroLookup>(
437        &self,
438        param_values: &MacroParameterBindings,
439        on_missing: OnUnboundMacroParameter,
440        macros: &M,
441    ) -> Option<ArithmeticExpression> {
442        match self
443            .first
444            .substitute_macro_parameters(param_values, on_missing, macros)
445        {
446            None => None,
447            Some(first) => {
448                let mut tail: Vec<(Operator, SignedAtom)> = Vec::with_capacity(self.tail.len());
449                for (op, atom) in &self.tail {
450                    match atom.substitute_macro_parameters(param_values, on_missing, macros) {
451                        Some(atom) => {
452                            tail.push((*op, atom));
453                        }
454                        None => {
455                            return None;
456                        }
457                    }
458                }
459                Some(ArithmeticExpression { first, tail })
460            }
461        }
462    }
463
464    fn allocate_rc_words<R: RcAllocator>(
465        &mut self,
466        explicit_symtab: &mut ExplicitSymbolTable,
467        implicit_symtab: &mut ImplicitSymbolTable,
468        rc_allocator: &mut R,
469    ) -> Result<(), RcWordAllocationFailure> {
470        self.first
471            .allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)?;
472        for (_op, atom) in &mut self.tail {
473            atom.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)?;
474        }
475        Ok(())
476    }
477}
478
479#[cfg(test)]
480mod binop_tests {
481    use super::{ArithmeticExpression, Operator};
482    use base::prelude::*;
483
484    const ALL_BIT_POSITIONS: [Unsigned36Bit; 36] = [
485        u36!(0b000_000_000_000_000_000_000_000_000_000_000_001),
486        u36!(0b000_000_000_000_000_000_000_000_000_000_000_010),
487        u36!(0b000_000_000_000_000_000_000_000_000_000_000_100),
488        u36!(0b000_000_000_000_000_000_000_000_000_000_001_000),
489        u36!(0b000_000_000_000_000_000_000_000_000_000_010_000),
490        u36!(0b000_000_000_000_000_000_000_000_000_000_100_000),
491        u36!(0b000_000_000_000_000_000_000_000_000_001_000_000),
492        u36!(0b000_000_000_000_000_000_000_000_000_010_000_000),
493        u36!(0b000_000_000_000_000_000_000_000_000_100_000_000),
494        u36!(0b000_000_000_000_000_000_000_000_001_000_000_000),
495        u36!(0b000_000_000_000_000_000_000_000_010_000_000_000),
496        u36!(0b000_000_000_000_000_000_000_000_100_000_000_000),
497        u36!(0b000_000_000_000_000_000_000_001_000_000_000_000),
498        u36!(0b000_000_000_000_000_000_000_010_000_000_000_000),
499        u36!(0b000_000_000_000_000_000_000_100_000_000_000_000),
500        u36!(0b000_000_000_000_000_000_001_000_000_000_000_000),
501        u36!(0b000_000_000_000_000_000_010_000_000_000_000_000),
502        u36!(0b000_000_000_000_000_000_100_000_000_000_000_000),
503        u36!(0b000_000_000_000_000_001_000_000_000_000_000_000),
504        u36!(0b000_000_000_000_000_010_000_000_000_000_000_000),
505        u36!(0b000_000_000_000_000_100_000_000_000_000_000_000),
506        u36!(0b000_000_000_000_001_000_000_000_000_000_000_000),
507        u36!(0b000_000_000_000_010_000_000_000_000_000_000_000),
508        u36!(0b000_000_000_000_100_000_000_000_000_000_000_000),
509        u36!(0b000_000_000_001_000_000_000_000_000_000_000_000),
510        u36!(0b000_000_000_010_000_000_000_000_000_000_000_000),
511        u36!(0b000_000_000_100_000_000_000_000_000_000_000_000),
512        u36!(0b000_000_001_000_000_000_000_000_000_000_000_000),
513        u36!(0b000_000_010_000_000_000_000_000_000_000_000_000),
514        u36!(0b000_000_100_000_000_000_000_000_000_000_000_000),
515        u36!(0b000_001_000_000_000_000_000_000_000_000_000_000),
516        u36!(0b000_010_000_000_000_000_000_000_000_000_000_000),
517        u36!(0b000_100_000_000_000_000_000_000_000_000_000_000),
518        u36!(0b001_000_000_000_000_000_000_000_000_000_000_000),
519        u36!(0b010_000_000_000_000_000_000_000_000_000_000_000),
520        u36!(0b100_000_000_000_000_000_000_000_000_000_000_000),
521    ];
522    const SOME_ARBITRARY_VALUES: [Unsigned36Bit; 9] = [
523        u36!(0o000_002),
524        u36!(0o000_005),
525        u36!(0o000_000_000_007),
526        u36!(0o000_000_007_000),
527        u36!(0o000_007_000_000),
528        u36!(0o007_000_000_000),
529        u36!(0o070_000_000_000),
530        u36!(0o700_000_000_000),
531        u36!(0o700_000_300_001),
532    ];
533
534    #[cfg(test)]
535    fn some_positive_values() -> impl Iterator<Item = Unsigned36Bit> {
536        ALL_BIT_POSITIONS
537            .iter()
538            .chain(SOME_ARBITRARY_VALUES.iter())
539            .copied()
540    }
541
542    #[test]
543    fn test_eval_binop_xor_12() {
544        assert_eq!(
545            ArithmeticExpression::eval_binop(u36!(0o1), Operator::LogicalXor, u36!(0o2)),
546            u36!(3)
547        );
548    }
549
550    #[test]
551    fn test_eval_binop_xor_55() {
552        assert_eq!(
553            ArithmeticExpression::eval_binop(u36!(0o5), Operator::LogicalXor, u36!(0o5)),
554            Unsigned36Bit::ZERO,
555        );
556    }
557
558    fn check_binop(
559        left: Unsigned36Bit,
560        op: Operator,
561        right: Unsigned36Bit,
562        expected: Unsigned36Bit,
563    ) {
564        let got = ArithmeticExpression::eval_binop(left, op, right);
565        assert_eq!(
566            got, expected,
567            "{left} {op} {right} should produce {expected} but it actually produced {got}"
568        );
569    }
570
571    fn check_commutative_binop(
572        left: Unsigned36Bit,
573        op: Operator,
574        right: Unsigned36Bit,
575        expected: Unsigned36Bit,
576    ) {
577        check_binop(left, op, right, expected);
578        check_binop(right, op, left, expected);
579    }
580
581    #[test]
582    fn test_all_bit_positions_coverage() {
583        let mut or_accumulator = Unsigned36Bit::ZERO;
584        let mut xor_accumulator = Unsigned36Bit::ZERO;
585        for input in ALL_BIT_POSITIONS {
586            or_accumulator = or_accumulator | input;
587            xor_accumulator = xor_accumulator ^ input;
588        }
589        // Verify that we have used each of the bits of the 36-bit word, just once.
590        assert_eq!(
591            xor_accumulator,
592            Unsigned36Bit::MAX,
593            "a bit position occcurs twice in the inputs"
594        );
595        assert_eq!(
596            or_accumulator,
597            Unsigned36Bit::MAX,
598            "a bit position is missing from the test inputs"
599        );
600    }
601
602    #[test]
603    fn test_eval_binop_add_identities() {
604        for input in some_positive_values() {
605            check_commutative_binop(input, Operator::Add, Unsigned36Bit::ZERO, input);
606            if input < u36!(0o1 << 35) {
607                let expected: Unsigned36Bit =
608                    input.checked_add(input).expect("should not overflow");
609                check_commutative_binop(input, Operator::Add, input, expected);
610            }
611        }
612        check_commutative_binop(
613            Unsigned36Bit::ZERO,
614            Operator::Add,
615            Unsigned36Bit::ZERO,
616            Unsigned36Bit::ZERO,
617        );
618    }
619
620    #[test]
621    fn test_eval_binop_logical_and_identities() {
622        for input in some_positive_values() {
623            check_commutative_binop(
624                input,
625                Operator::LogicalAnd,
626                Unsigned36Bit::ZERO,
627                Unsigned36Bit::ZERO,
628            );
629            check_commutative_binop(input, Operator::LogicalAnd, input, input);
630        }
631        check_commutative_binop(
632            Unsigned36Bit::ZERO,
633            Operator::LogicalAnd,
634            Unsigned36Bit::ZERO,
635            Unsigned36Bit::ZERO,
636        );
637    }
638
639    #[test]
640    fn test_eval_binop_logical_and_120() {
641        check_commutative_binop(
642            u36!(0o1),
643            Operator::LogicalAnd,
644            u36!(0o2),
645            Unsigned36Bit::ZERO,
646        );
647    }
648
649    #[test]
650    fn test_eval_binop_xor_identities() {
651        for input in some_positive_values() {
652            check_commutative_binop(input, Operator::LogicalXor, Unsigned36Bit::ZERO, input);
653            check_commutative_binop(input, Operator::LogicalXor, input, Unsigned36Bit::ZERO);
654        }
655        check_commutative_binop(
656            Unsigned36Bit::ZERO,
657            Operator::LogicalXor,
658            Unsigned36Bit::ZERO,
659            Unsigned36Bit::ZERO,
660        );
661    }
662
663    #[test]
664    fn test_eval_binop_logical_or_identities() {
665        for input in some_positive_values() {
666            check_commutative_binop(input, Operator::LogicalOr, Unsigned36Bit::ZERO, input);
667            check_commutative_binop(input, Operator::LogicalOr, input, input);
668        }
669        check_commutative_binop(
670            Unsigned36Bit::ZERO,
671            Operator::LogicalOr,
672            Unsigned36Bit::ZERO,
673            Unsigned36Bit::ZERO,
674        );
675    }
676
677    #[test]
678    fn test_eval_binop_logical_or_123() {
679        check_commutative_binop(u36!(0o1), Operator::LogicalOr, u36!(0o2), u36!(0o3));
680    }
681
682    #[test]
683    fn test_eval_binop_multiply_identities() {
684        for input in some_positive_values() {
685            check_commutative_binop(
686                input,
687                Operator::Multiply,
688                Unsigned36Bit::ZERO,
689                Unsigned36Bit::ZERO,
690            );
691            check_commutative_binop(input, Operator::Multiply, u36!(1), input);
692        }
693        check_commutative_binop(
694            Unsigned36Bit::ZERO,
695            Operator::Multiply,
696            Unsigned36Bit::ZERO,
697            Unsigned36Bit::ZERO,
698        );
699    }
700
701    #[test]
702    fn test_eval_binop_multiply_examples() {
703        check_commutative_binop(u36!(2), Operator::Multiply, u36!(3), u36!(6));
704    }
705
706    #[test]
707    fn test_eval_binop_subtract_identities() {
708        for input in some_positive_values() {
709            check_binop(input, Operator::Subtract, Unsigned36Bit::ZERO, input);
710            check_binop(input, Operator::Subtract, input, Unsigned36Bit::ZERO);
711        }
712        check_commutative_binop(
713            Unsigned36Bit::ZERO,
714            Operator::Subtract,
715            Unsigned36Bit::ZERO,
716            Unsigned36Bit::ZERO,
717        );
718    }
719
720    #[test]
721    fn test_eval_binop_subtract_examples() {
722        check_binop(u36!(0o7), Operator::Subtract, u36!(0o2), u36!(0o5));
723    }
724
725    #[test]
726    fn test_eval_binop_divide_identities() {
727        for input in some_positive_values() {
728            check_binop(input, Operator::Divide, u36!(1), input); // x/1 = x
729            check_binop(input, Operator::Divide, input, u36!(1)); // x/x = 1
730        }
731        check_commutative_binop(
732            Unsigned36Bit::ZERO,
733            Operator::Subtract,
734            Unsigned36Bit::ZERO,
735            Unsigned36Bit::ZERO,
736        );
737    }
738}
739
740/// An expression used to specify the configuration bits of an instruction.
741///
742/// A configuration syllable can be specified by putting it in a
743/// superscript, or by putting it in normal script after a ‖ symbol
744/// (‖x or ‖2, for example).  This is described in section 6-2.1 of
745/// the Users Handbook.
746///
747/// In the description of the parts of an instruction (section 6-2.1,
748/// "INSTRUCTION WORDS" of the Users Handbook) we see the
749/// specification that the configuration syllable cannot contain any
750/// spaces.  But this doesn't prevent the config syllable containing,
751/// say, an arithmetic expression.  Indeed, Leonard Kleinrock's
752/// program for network simulation does exactly that (by using a
753/// negated symbol as a configuration value).
754///
755#[derive(Debug, Clone, PartialEq, Eq)]
756pub(crate) struct ConfigValue {
757    /// Indicates that the value was already in superscript.
758    pub(crate) already_superscript: bool,
759    /// Holds the configuration syllable value.
760    pub(crate) expr: ArithmeticExpression,
761}
762
763impl ConfigValue {
764    fn symbol_uses(
765        &self,
766        block_id: BlockIdentifier,
767        block_offset: Unsigned18Bit,
768    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
769    {
770        self.expr
771            .symbol_uses(block_id, block_offset)
772            .map(|r| match r {
773                Ok((name, span, _ignore_symbol_use)) => Ok((
774                    name,
775                    span,
776                    SymbolUse::Reference(SymbolContext::configuration(span)),
777                )),
778                Err(e) => Err(e),
779            })
780    }
781
782    fn substitute_macro_parameters<M: MacroLookup>(
783        &self,
784        param_values: &MacroParameterBindings,
785        on_missing: OnUnboundMacroParameter,
786        macros: &M,
787    ) -> Option<ConfigValue> {
788        self.expr
789            .substitute_macro_parameters(param_values, on_missing, macros)
790            .map(|expr| ConfigValue {
791                expr,
792                already_superscript: self.already_superscript,
793            })
794    }
795
796    fn allocate_rc_words<R: RcAllocator>(
797        &mut self,
798        explicit_symtab: &mut ExplicitSymbolTable,
799        implicit_symtab: &mut ImplicitSymbolTable,
800        rc_allocator: &mut R,
801    ) -> Result<(), RcWordAllocationFailure> {
802        self.expr
803            .allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)
804    }
805}
806
807impl Spanned for ConfigValue {
808    fn span(&self) -> Span {
809        self.expr.span()
810    }
811}
812
813#[derive(Debug, Clone, PartialEq, Eq)]
814pub(crate) struct RegistersContaining(OneOrMore<RegisterContaining>);
815
816impl RegistersContaining {
817    pub(super) fn from_words(words: OneOrMore<RegisterContaining>) -> RegistersContaining {
818        Self(words)
819    }
820
821    pub(super) fn words(&self) -> impl Iterator<Item = &RegisterContaining> {
822        self.0.iter()
823    }
824
825    pub(crate) fn words_mut(&mut self) -> impl Iterator<Item = &mut RegisterContaining> {
826        self.0.iter_mut()
827    }
828
829    fn symbol_uses(
830        &self,
831        block_id: BlockIdentifier,
832        block_offset: Unsigned18Bit,
833    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<'_>
834    {
835        self.0
836            .iter()
837            .flat_map(move |rc| rc.symbol_uses(block_id, block_offset))
838    }
839
840    fn substitute_macro_parameters<M: MacroLookup>(
841        &self,
842        param_values: &MacroParameterBindings,
843        on_missing: OnUnboundMacroParameter,
844        macros: &M,
845    ) -> Option<RegistersContaining> {
846        // TODO: this implementation probably requires more thought.
847        // At the moment, if the contents of {...} yield any single
848        // item that gets omitted because it references an unbound
849        // macro paramter, then the whole {...} (and therefore
850        // anything containing it) gets omitted.
851        //
852        // This may not match the required behaviour of the TX-2's M4
853        // assembler, which might instead just omit that RC-word.
854        // However, if we switch to that option, then this could
855        // create a situation in which {...} results in zero words of
856        // the RC-block being reserved.  In that case, what is the
857        // resulting numerical value of the {...} expression?  If it
858        // actually does reserve zero words, then it means that two or
859        // more instances of {...} could resolve to the same address,
860        // and that is likely not intended.  It wold also mean trouble
861        // for the current implementation of the Spanned trait for
862        // RegistersContaining.
863        let tmp_rc: OneOrMore<Option<RegisterContaining>> = self
864            .0
865            .map(|rc| rc.substitute_macro_parameters(param_values, on_missing, macros));
866        if tmp_rc.iter().all(Option::is_some) {
867            Some(RegistersContaining(tmp_rc.into_map(|maybe_rc| {
868                maybe_rc.expect("we already checked this wasn't None")
869            })))
870        } else {
871            None
872        }
873    }
874
875    fn allocate_rc_words<R: RcAllocator>(
876        &mut self,
877        span: Span,
878        explicit_symtab: &mut ExplicitSymbolTable,
879        implicit_symtab: &mut ImplicitSymbolTable,
880        rc_allocator: &mut R,
881    ) -> Result<(), RcWordAllocationFailure> {
882        let source = RcWordSource {
883            span,
884            kind: RcWordKind::Braces,
885        };
886        for rc in self.words_mut() {
887            *rc = rc.clone().assign_rc_word(
888                source.clone(),
889                explicit_symtab,
890                implicit_symtab,
891                rc_allocator,
892            )?;
893        }
894        Ok(())
895    }
896}
897
898impl Spanned for RegistersContaining {
899    fn span(&self) -> Span {
900        use chumsky::span::Span;
901        let mut it = self.0.iter();
902        match it.next() {
903            Some(rc) => it.fold(rc.span(), |acc, rc| acc.union(rc.span())),
904            None => {
905                unreachable!(
906                    "invariant broken: RegistersContaining contains no RegisterContaining instances"
907                )
908            }
909        }
910    }
911}
912
913/// An RC-word.
914///
915/// See section 6-2.6 ("RC WORDS - RC BLOCK").
916///
917/// Section 6-4.7 ("Use of Macro Instructions") states that macro
918/// expansion may occur inside an RC-word and can expand to more than one
919/// word in the output binary.
920#[derive(Debug, Clone, PartialEq, Eq)]
921pub(crate) enum RegisterContaining {
922    Unallocated(Box<TaggedProgramInstruction>),
923    Allocated(Address, Box<TaggedProgramInstruction>),
924}
925
926impl From<TaggedProgramInstruction> for RegisterContaining {
927    fn from(inst: TaggedProgramInstruction) -> Self {
928        RegisterContaining::Unallocated(Box::new(inst))
929    }
930}
931
932impl Spanned for RegisterContaining {
933    fn span(&self) -> Span {
934        match self {
935            RegisterContaining::Unallocated(b) | RegisterContaining::Allocated(_, b) => b.span(),
936        }
937    }
938}
939
940impl RegisterContaining {
941    fn instruction(&self) -> &TaggedProgramInstruction {
942        match self {
943            RegisterContaining::Unallocated(tpi) | RegisterContaining::Allocated(_, tpi) => tpi,
944        }
945    }
946
947    fn symbol_uses(
948        &self,
949        block_id: BlockIdentifier,
950        block_offset: Unsigned18Bit,
951    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<'_>
952    {
953        let mut result: Vec<Result<_, _>> = Vec::new();
954        for r in self.instruction().symbol_uses(block_id, block_offset) {
955            match r {
956                Ok((name, span, symbol_definition)) => {
957                    match symbol_definition {
958                        def @ SymbolUse::Reference(_) => {
959                            result.push(Ok((name, span, def)));
960                        }
961                        SymbolUse::Definition(ExplicitDefinition::Tag { .. }) => {
962                            // Here we have a tag definition inside an
963                            // RC-word.  Therefore the passed-in value of
964                            // `block_id` is wrong (it refers to the block
965                            // containing the RC-word, not to the RC-block)
966                            // and the offset is similarly wrong.
967                            //
968                            // Therefore we will process these uses of symbols
969                            // at the time we allocate addresses for RC-block
970                            // words.
971                        }
972                        SymbolUse::Definition(ExplicitDefinition::Origin(_, _)) => {
973                            unreachable!(
974                                "Found origin {name} inside an RC-word; the parser should have rejected this."
975                            );
976                        }
977                        SymbolUse::Definition(_) => {
978                            // e.g. we have an input like
979                            //
980                            // { X = 2 }
981                            //
982                            //
983                            // Ideally we would issue an error for
984                            // this, but since this function cannot
985                            // fail, it's better to do that at the
986                            // time we parse the RC-word reference
987                            // (thus eliminating this case).
988                            //
989                            // When working on this case we should
990                            // figure out if an equality is allowed
991                            // inside a macro expansion.
992                            panic!(
993                                "Found unexpected definition of {name} inside RC-word reference at {span:?}"
994                            );
995                        }
996                    }
997                }
998                Err(e) => {
999                    result.push(Err(e));
1000                }
1001            }
1002        }
1003        result.into_iter()
1004    }
1005
1006    fn substitute_macro_parameters<M: MacroLookup>(
1007        &self,
1008        param_values: &MacroParameterBindings,
1009        on_missing: OnUnboundMacroParameter,
1010        macros: &M,
1011    ) -> Option<RegisterContaining> {
1012        match self {
1013            RegisterContaining::Unallocated(tagged_program_instruction) => {
1014                tagged_program_instruction
1015                    .substitute_macro_parameters(param_values, on_missing, macros)
1016                    .map(|tagged_program_instruction| {
1017                        RegisterContaining::Unallocated(Box::new(tagged_program_instruction))
1018                    })
1019            }
1020            RegisterContaining::Allocated(_address, _tagged_program_instruction) => {
1021                // One reason we don't support this is because if we
1022                // twice instantiate a macro which contains {...} or a
1023                // pipe construct, then both of those RC-words would
1024                // have the same address, and this is likely not
1025                // intended.  It's certainly user-surprising.
1026                //
1027                // The second reason we don't support this (and the
1028                // reason why we don't need to issue an error message
1029                // for the user) is that the assembler implementation
1030                // does in fact perform macro-expansion before
1031                // RC-words are allocated.
1032                unreachable!(
1033                    "macro expansion must be completed before any RC-block addresses are allocated"
1034                )
1035            }
1036        }
1037    }
1038
1039    fn assign_rc_word<R: RcAllocator>(
1040        self,
1041        source: RcWordSource,
1042        explicit_symtab: &mut ExplicitSymbolTable,
1043        implicit_symtab: &mut ImplicitSymbolTable,
1044        rc_allocator: &mut R,
1045    ) -> Result<RegisterContaining, RcWordAllocationFailure> {
1046        match self {
1047            RegisterContaining::Unallocated(mut tpibox) => {
1048                let address: Address = rc_allocator.allocate(source, Unsigned36Bit::ZERO)?;
1049                for tag in &tpibox.tags {
1050                    eprintln!(
1051                        "assigning RC-word at address {address} serves as defnition of tag {}",
1052                        tag.name
1053                    );
1054                    implicit_symtab.remove(&tag.name);
1055                    let new_tag_definition = TagDefinition::Resolved {
1056                        span: tag.span,
1057                        address,
1058                    };
1059                    match explicit_symtab.define(
1060                        tag.name.clone(),
1061                        ExplicitDefinition::Tag(new_tag_definition.clone()),
1062                    ) {
1063                        Ok(()) => (),
1064                        Err(BadSymbolDefinition {
1065                            symbol_name,
1066                            span,
1067                            existing,
1068                            proposed: _,
1069                        }) => {
1070                            return Err(RcWordAllocationFailure::InconsistentTag {
1071                                tag_name: symbol_name,
1072                                span,
1073                                explanation: format!(
1074                                    "previous definition {existing} is incompatible with new definition {new_tag_definition}"
1075                                ),
1076                            });
1077                        }
1078                    }
1079                }
1080                tpibox.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)?;
1081                let tpi: Box<TaggedProgramInstruction> = tpibox;
1082                Ok(RegisterContaining::Allocated(address, tpi))
1083            }
1084            other @ RegisterContaining::Allocated(..) => Ok(other),
1085        }
1086    }
1087}
1088
1089/// A component of an arithmetic expression.
1090///
1091/// A symbol, numeric literal, address of an RC-word, or a
1092/// parenthesised arithmetic expression.
1093#[derive(Debug, Clone, PartialEq, Eq)]
1094pub(crate) enum Atom {
1095    SymbolOrLiteral(SymbolOrLiteral),
1096    Parens(Span, Script, Box<ArithmeticExpression>),
1097    RcRef(Span, RegistersContaining),
1098}
1099
1100impl From<(Span, Script, SymbolName)> for Atom {
1101    fn from((span, script, name): (Span, Script, SymbolName)) -> Self {
1102        Atom::SymbolOrLiteral(SymbolOrLiteral::Symbol(script, name, span))
1103    }
1104}
1105
1106impl From<SymbolOrLiteral> for Atom {
1107    fn from(value: SymbolOrLiteral) -> Self {
1108        Atom::SymbolOrLiteral(value)
1109    }
1110}
1111
1112impl Atom {
1113    fn symbol_uses(
1114        &self,
1115        block_id: BlockIdentifier,
1116        block_offset: Unsigned18Bit,
1117    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
1118    {
1119        let mut result: Vec<Result<_, _>> = Vec::with_capacity(1);
1120        match self {
1121            Atom::SymbolOrLiteral(SymbolOrLiteral::Symbol(script, name, span)) => {
1122                result.push(Ok((
1123                    name.clone(),
1124                    *span,
1125                    SymbolUse::Reference(SymbolContext::from((script, *span))),
1126                )));
1127            }
1128            Atom::SymbolOrLiteral(SymbolOrLiteral::Literal(_) | SymbolOrLiteral::Here(_, _)) => (),
1129            Atom::Parens(_span, _script, expr) => {
1130                result.extend(expr.symbol_uses(block_id, block_offset));
1131            }
1132            Atom::RcRef(_span, rc_words) => {
1133                result.extend(rc_words.symbol_uses(block_id, block_offset));
1134            }
1135        }
1136        result.into_iter()
1137    }
1138
1139    fn substitute_macro_parameters<M: MacroLookup>(
1140        &self,
1141        param_values: &MacroParameterBindings,
1142        on_missing: OnUnboundMacroParameter,
1143        macros: &M,
1144    ) -> Option<Atom> {
1145        match self {
1146            Atom::SymbolOrLiteral(symbol_or_literal) => {
1147                match symbol_or_literal.substitute_macro_parameters(param_values, on_missing) {
1148                    SymbolSubstitution::AsIs(symbol_or_literal) => {
1149                        Some(Atom::SymbolOrLiteral(symbol_or_literal))
1150                    }
1151                    SymbolSubstitution::Hit(span, script, arithmetic_expression) => Some(
1152                        Atom::Parens(span, script, Box::new(arithmetic_expression.clone())),
1153                    ),
1154                    SymbolSubstitution::Omit => {
1155                        // The parameter was not set, and this atom is
1156                        // being used in a context where omitted
1157                        // parameters cause the affected instruction
1158                        // to be omitted.  That is, this expression is
1159                        // not on the right-hand-side of an equality.
1160                        None
1161                    }
1162                    SymbolSubstitution::Zero(span) => {
1163                        Some(Atom::SymbolOrLiteral(SymbolOrLiteral::Literal(
1164                            LiteralValue {
1165                                span,
1166                                // Since the value is zero the elevation actually doesn't matter.
1167                                elevation: Script::Normal,
1168                                value: Unsigned36Bit::ZERO,
1169                            },
1170                        )))
1171                    }
1172                }
1173            }
1174            Atom::Parens(span, script, arithmetic_expression) => arithmetic_expression
1175                .substitute_macro_parameters(param_values, on_missing, macros)
1176                .map(|arithmetic_expression| {
1177                    Atom::Parens(*span, *script, Box::new(arithmetic_expression))
1178                }),
1179            Atom::RcRef(span, registers_containing) => registers_containing
1180                .substitute_macro_parameters(param_values, on_missing, macros)
1181                .map(|registers_containing| Atom::RcRef(*span, registers_containing)),
1182        }
1183    }
1184
1185    fn allocate_rc_words<R: RcAllocator>(
1186        &mut self,
1187        explicit_symtab: &mut ExplicitSymbolTable,
1188        implicit_symtab: &mut ImplicitSymbolTable,
1189        rc_allocator: &mut R,
1190    ) -> Result<(), RcWordAllocationFailure> {
1191        match self {
1192            Atom::SymbolOrLiteral(thing) => {
1193                thing.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)
1194            }
1195            Atom::Parens(_, _, expr) => {
1196                expr.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)
1197            }
1198            Atom::RcRef(span, rc) => {
1199                rc.allocate_rc_words(*span, explicit_symtab, implicit_symtab, rc_allocator)
1200            }
1201        }
1202    }
1203}
1204
1205impl Spanned for Atom {
1206    fn span(&self) -> Span {
1207        match self {
1208            Atom::SymbolOrLiteral(value) => value.span(),
1209            Atom::Parens(span, _script, _bae) => *span,
1210            Atom::RcRef(span, _) => *span,
1211        }
1212    }
1213}
1214
1215impl From<LiteralValue> for Atom {
1216    fn from(literal: LiteralValue) -> Atom {
1217        Atom::SymbolOrLiteral(SymbolOrLiteral::Literal(literal))
1218    }
1219}
1220
1221impl From<(Span, Script, Unsigned36Bit)> for Atom {
1222    fn from((span, script, v): (Span, Script, Unsigned36Bit)) -> Atom {
1223        Atom::from(LiteralValue::from((span, script, v)))
1224    }
1225}
1226
1227impl std::fmt::Display for Atom {
1228    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1229        match self {
1230            Atom::SymbolOrLiteral(value) => write!(f, "{value}"),
1231            Atom::Parens(_span, script, expr) => elevated_string(&expr.to_string(), *script).fmt(f),
1232            Atom::RcRef(_span, _rc_reference) => {
1233                // The RcRef doesn't itself record the content of the
1234                // {...} because that goes into the rc-block itself.
1235                write!(f, "{{...}}")
1236            }
1237        }
1238    }
1239}
1240
1241/// Indicates how some particular macro parameter should be processed.
1242#[derive(Debug, Clone, PartialEq, Eq)]
1243pub(crate) enum SymbolSubstitution<T> {
1244    AsIs(T),
1245    Hit(Span, Script, ArithmeticExpression),
1246    Omit,
1247    Zero(Span),
1248}
1249
1250/// A symbol name or a numeric literal, or `#`.
1251///
1252/// A `#` represents the address of the program word whose value the
1253/// assembler is currently trying to determine.
1254#[derive(Debug, Clone, PartialEq, Eq)]
1255pub(crate) enum SymbolOrLiteral {
1256    Symbol(Script, SymbolName, Span),
1257    Literal(LiteralValue),
1258    Here(Script, Span),
1259}
1260
1261impl SymbolOrLiteral {
1262    fn symbol_uses(
1263        &self,
1264    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
1265    {
1266        let mut result = Vec::with_capacity(1);
1267        match self {
1268            SymbolOrLiteral::Here(_, _) | SymbolOrLiteral::Literal(_) => (),
1269            SymbolOrLiteral::Symbol(script, name, span) => {
1270                let context: SymbolContext = (script, *span).into();
1271                let sym_use: SymbolUse = SymbolUse::Reference(context);
1272                result.push(Ok((name.clone(), *span, sym_use)));
1273            }
1274        }
1275        result.into_iter()
1276    }
1277
1278    fn substitute_macro_parameters(
1279        &self,
1280        param_values: &MacroParameterBindings,
1281        on_missing: OnUnboundMacroParameter,
1282    ) -> SymbolSubstitution<SymbolOrLiteral> {
1283        match self {
1284            SymbolOrLiteral::Symbol(_script, symbol_name, _span) => {
1285                match param_values.get(symbol_name) {
1286                    Some((
1287                        span,
1288                        Some(MacroParameterValue::Value(script, arithmetic_expression)),
1289                    )) => {
1290                        // symbol_name was a parameter name, and the
1291                        // macro invocation specified it, so
1292                        // substitute it.
1293                        SymbolSubstitution::Hit(*span, *script, arithmetic_expression.clone())
1294                    }
1295                    Some((span, None)) => {
1296                        // symbol_name was a parameter name, but the
1297                        // macro invocation did not specify it, so we
1298                        // either elide the instruction or behave if
1299                        // it is zero, according to on_missing.
1300                        match on_missing {
1301                            OnUnboundMacroParameter::ElideReference => SymbolSubstitution::Omit,
1302                            OnUnboundMacroParameter::SubstituteZero => {
1303                                SymbolSubstitution::Zero(*span)
1304                            }
1305                        }
1306                    }
1307                    None => {
1308                        // symbol_name is not a macro parameter.
1309                        SymbolSubstitution::AsIs(self.clone())
1310                    }
1311                }
1312            }
1313            SymbolOrLiteral::Literal(literal) => {
1314                SymbolSubstitution::AsIs(SymbolOrLiteral::Literal(literal.clone()))
1315            }
1316            SymbolOrLiteral::Here(script, span) => {
1317                SymbolSubstitution::AsIs(SymbolOrLiteral::Here(*script, *span))
1318            }
1319        }
1320    }
1321
1322    fn allocate_rc_words<R: RcAllocator>(
1323        &mut self,
1324        _explicit_symtab: &ExplicitSymbolTable,
1325        _implicit_symtab: &mut ImplicitSymbolTable,
1326        _rc_allocator: &mut R,
1327    ) -> Result<(), RcWordAllocationFailure> {
1328        // We use Result for consistency with the allocate_rc_words()
1329        // methods of other AST elements.
1330        #![allow(clippy::unnecessary_wraps)]
1331        // SymbolOrliteral doesn't contain anything that would reserve
1332        // RC-words, so there is nothing to do here.
1333        let _ = self; // placate the unused_self Clippy lint.
1334        Ok(())
1335    }
1336}
1337
1338impl Spanned for SymbolOrLiteral {
1339    fn span(&self) -> Span {
1340        match self {
1341            SymbolOrLiteral::Literal(literal_value) => literal_value.span,
1342            SymbolOrLiteral::Symbol(_, _, span) | SymbolOrLiteral::Here(_, span) => *span,
1343        }
1344    }
1345}
1346
1347impl Display for SymbolOrLiteral {
1348    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1349        match self {
1350            SymbolOrLiteral::Here(script, _span) => match script {
1351                Script::Super => f.write_str("@super_hash@"),
1352                Script::Normal => f.write_char('#'),
1353                Script::Sub => f.write_str("@sub_hash@"),
1354            },
1355            SymbolOrLiteral::Symbol(script, name, _) => {
1356                elevated_string(&name.to_string(), *script).fmt(f)
1357            }
1358            SymbolOrLiteral::Literal(value) => value.fmt(f),
1359        }
1360    }
1361}
1362
1363#[derive(Debug, PartialEq, Eq, Clone)]
1364pub(crate) struct SpannedSymbolOrLiteral {
1365    pub(crate) item: SymbolOrLiteral,
1366    pub(crate) span: Span,
1367}
1368
1369impl SpannedSymbolOrLiteral {
1370    fn substitute_macro_parameters(
1371        &self,
1372        param_values: &MacroParameterBindings,
1373        on_missing: OnUnboundMacroParameter,
1374    ) -> SymbolSubstitution<SpannedSymbolOrLiteral> {
1375        match self
1376            .item
1377            .substitute_macro_parameters(param_values, on_missing)
1378        {
1379            SymbolSubstitution::AsIs(item) => SymbolSubstitution::AsIs(SpannedSymbolOrLiteral {
1380                item,
1381                span: self.span,
1382            }),
1383            SymbolSubstitution::Hit(span, script, arithmetic_expression) => {
1384                SymbolSubstitution::Hit(span, script, arithmetic_expression)
1385            }
1386            SymbolSubstitution::Omit => SymbolSubstitution::Omit,
1387            SymbolSubstitution::Zero(span) => SymbolSubstitution::Zero(span),
1388        }
1389    }
1390}
1391
1392/// Part of a TX-2 instruction.
1393///
1394/// In the M4 assembly language, each part is evaluated separately and
1395/// then they are combined.
1396#[derive(Debug, Clone, PartialEq, Eq)]
1397pub(crate) enum InstructionFragment {
1398    /// Arithmetic expressions are permitted in normal case according
1399    /// to the Users Handbook, but currently this implementation
1400    /// allows them in subscript/superscript too.
1401    Arithmetic(ArithmeticExpression),
1402    /// Insicates that the current instruction should use the deferred
1403    /// addressing mode.
1404    ///
1405    /// The programmer indicates this with `*`.  The
1406    /// programmer can also make use of deferred addressing by using
1407    /// the "pipe construct" (which is represented by
1408    /// [`InstructionFragment::PipeConstruct`])
1409    DeferredAddressing(Span),
1410    /// A configuration syllable (specified either in superscript or with a ‖).
1411    Config(ConfigValue),
1412    /// Described in section 6-2.8 "SPECIAL SYMBOLS" of the Users Handbook.
1413    PipeConstruct {
1414        index: SpannedSymbolOrLiteral,
1415        rc_word_span: Span,
1416        rc_word_value: RegisterContaining,
1417    },
1418    /// Purely an implementation artifact.
1419    ///
1420    /// Used by the assembler when parsing a
1421    /// [`CommaDelimitedFragment`] to represent the commas at the
1422    /// beginning or end of a part of the input program which gets
1423    /// parsed as an [`UntaggedProgramInstruction`].
1424    Null(Span),
1425}
1426
1427impl Spanned for InstructionFragment {
1428    fn span(&self) -> Span {
1429        match self {
1430            InstructionFragment::Arithmetic(arithmetic_expression) => arithmetic_expression.span(),
1431            InstructionFragment::Config(config_value) => config_value.span(),
1432            InstructionFragment::PipeConstruct {
1433                index,
1434                rc_word_span,
1435                rc_word_value: _,
1436            } => {
1437                let start = index.span.start;
1438                let end = rc_word_span.end;
1439                span(start..end)
1440            }
1441            InstructionFragment::DeferredAddressing(span) | InstructionFragment::Null(span) => {
1442                *span
1443            }
1444        }
1445    }
1446}
1447
1448impl InstructionFragment {
1449    fn symbol_uses(
1450        &self,
1451        block_id: BlockIdentifier,
1452        block_offset: Unsigned18Bit,
1453    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
1454    {
1455        let mut uses: Vec<Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> =
1456            Vec::new();
1457        match self {
1458            InstructionFragment::Arithmetic(expr) => {
1459                uses.extend(expr.symbol_uses(block_id, block_offset));
1460            }
1461            InstructionFragment::Null(_) | InstructionFragment::DeferredAddressing(_) => (),
1462            InstructionFragment::Config(value) => {
1463                uses.extend(value.symbol_uses(block_id, block_offset));
1464            }
1465            InstructionFragment::PipeConstruct {
1466                index,
1467                rc_word_span: _,
1468                rc_word_value,
1469            } => {
1470                for r in index.item.symbol_uses() {
1471                    match r {
1472                        Ok((name, span, mut symbol_use)) => {
1473                            if let SymbolUse::Reference(context) = &mut symbol_use {
1474                                assert!(!context.is_address());
1475                                if let Err(e) = context.also_set_index(&name, span) {
1476                                    uses.push(Err(e));
1477                                } else {
1478                                    uses.push(Ok((name, span, symbol_use)));
1479                                }
1480                            } else {
1481                                uses.push(Ok((name, span, symbol_use)));
1482                            }
1483                        }
1484                        Err(e) => {
1485                            uses.push(Err(e));
1486                        }
1487                    }
1488                }
1489                uses.extend(rc_word_value.symbol_uses(block_id, block_offset));
1490            }
1491        }
1492        uses.into_iter()
1493    }
1494
1495    fn substitute_macro_parameters<M: MacroLookup>(
1496        &self,
1497        param_values: &MacroParameterBindings,
1498        on_missing: OnUnboundMacroParameter,
1499        macros: &M,
1500    ) -> Option<InstructionFragment> {
1501        match self {
1502            InstructionFragment::Arithmetic(arithmetic_expression) => arithmetic_expression
1503                .substitute_macro_parameters(param_values, on_missing, macros)
1504                .map(InstructionFragment::Arithmetic),
1505            InstructionFragment::DeferredAddressing(span) => {
1506                Some(InstructionFragment::DeferredAddressing(*span))
1507            }
1508            InstructionFragment::Config(config_value) => config_value
1509                .substitute_macro_parameters(param_values, on_missing, macros)
1510                .map(InstructionFragment::Config),
1511            InstructionFragment::PipeConstruct {
1512                index,
1513                rc_word_span,
1514                rc_word_value,
1515            } => match index.substitute_macro_parameters(param_values, on_missing) {
1516                SymbolSubstitution::AsIs(index) => rc_word_value
1517                    .substitute_macro_parameters(param_values, on_missing, macros)
1518                    .map(|rc_word_value| InstructionFragment::PipeConstruct {
1519                        index,
1520                        rc_word_span: *rc_word_span,
1521                        rc_word_value,
1522                    }),
1523                SymbolSubstitution::Hit(_span, _script, _arithmetic_expression) => {
1524                    todo!(
1525                        "macro parameter expansion is not yet fully supported in the index part of pipe constructs"
1526                    )
1527                }
1528                SymbolSubstitution::Omit => None,
1529                SymbolSubstitution::Zero(span) => Some(InstructionFragment::Null(span)),
1530            },
1531            InstructionFragment::Null(span) => Some(InstructionFragment::Null(*span)),
1532        }
1533    }
1534
1535    fn allocate_rc_words<R: RcAllocator>(
1536        &mut self,
1537        explicit_symtab: &mut ExplicitSymbolTable,
1538        implicit_symtab: &mut ImplicitSymbolTable,
1539        rc_allocator: &mut R,
1540    ) -> Result<(), RcWordAllocationFailure> {
1541        match self {
1542            InstructionFragment::Null(_) | InstructionFragment::DeferredAddressing(_) => Ok(()),
1543            InstructionFragment::Arithmetic(expr) => {
1544                expr.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)
1545            }
1546            InstructionFragment::Config(cfg) => {
1547                cfg.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)
1548            }
1549            InstructionFragment::PipeConstruct {
1550                index: _,
1551                rc_word_span,
1552                rc_word_value,
1553            } => {
1554                let span: Span = *rc_word_span;
1555                let w = rc_word_value.clone();
1556                *rc_word_value = w.assign_rc_word(
1557                    RcWordSource {
1558                        span,
1559                        kind: RcWordKind::PipeConstruct,
1560                    },
1561                    explicit_symtab,
1562                    implicit_symtab,
1563                    rc_allocator,
1564                )?;
1565                Ok(())
1566            }
1567        }
1568    }
1569}
1570
1571impl From<(Span, Script, Unsigned36Bit)> for InstructionFragment {
1572    fn from((span, script, v): (Span, Script, Unsigned36Bit)) -> InstructionFragment {
1573        // TODO: use the atomic variant instead.
1574        InstructionFragment::Arithmetic(ArithmeticExpression::from(Atom::from((span, script, v))))
1575    }
1576}
1577
1578impl From<ArithmeticExpression> for InstructionFragment {
1579    fn from(expr: ArithmeticExpression) -> Self {
1580        InstructionFragment::Arithmetic(expr)
1581    }
1582}
1583
1584/// Represents the origin of a block of program code.
1585#[derive(Debug, Clone, Eq, PartialEq, Hash)]
1586pub(crate) enum Origin {
1587    /// An origin specified directly as a number.
1588    Literal(Span, Address),
1589    /// An origin specified by name (which would refer to e.g. an
1590    /// equality).
1591    Symbolic(Span, SymbolName),
1592    /// A symbolic origin where the symbol had no definition and
1593    /// therefore the origin value had to be deduced (hence providing
1594    /// an implicit definition for the symbol).
1595    Deduced(Span, SymbolName, Address),
1596}
1597
1598impl Display for Origin {
1599    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), fmt::Error> {
1600        match self {
1601            Origin::Literal(_span, addr) => fmt::Display::fmt(&addr, f),
1602            Origin::Symbolic(_span, sym) => fmt::Display::fmt(&sym, f),
1603            Origin::Deduced(_span, name, addr) => {
1604                write!(f, "{name} (deduced to be at address {addr:o})")
1605            }
1606        }
1607    }
1608}
1609
1610impl Origin {
1611    pub(super) fn default_address() -> Address {
1612        // Section 6-2.5 of the User Manual states that if the
1613        // manuscript contains no origin specification (no vertical
1614        // bar) the whole program is located (correctly) at 200_000
1615        // octal.
1616        Address::new(u18!(0o200_000))
1617    }
1618
1619    pub(super) fn symbol_uses(
1620        &self,
1621        block_id: BlockIdentifier,
1622    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
1623    {
1624        let mut result = Vec::with_capacity(1);
1625        match self {
1626            Origin::Literal(_span, _) => (),
1627            org @ Origin::Deduced(span, name, _) => {
1628                // We won't have any deduced origin values at this
1629                // time the symbol uses are enumerate, but this case
1630                // is just here for completeness.
1631                event!(
1632                    Level::WARN,
1633                    "unexpectedly saw a deduced value for origin {name} in symbol_uses"
1634                );
1635                result.push(Ok((
1636                    name.clone(),
1637                    *span,
1638                    SymbolUse::Definition(ExplicitDefinition::Origin(org.clone(), block_id)),
1639                )));
1640            }
1641            org @ Origin::Symbolic(span, name) => {
1642                result.push(Ok((
1643                    name.clone(),
1644                    *span,
1645                    SymbolUse::Definition(ExplicitDefinition::Origin(org.clone(), block_id)),
1646                )));
1647            }
1648        }
1649        result.into_iter()
1650    }
1651}
1652
1653impl Spanned for Origin {
1654    fn span(&self) -> Span {
1655        match self {
1656            Origin::Deduced(span, _, _) | Origin::Literal(span, _) | Origin::Symbolic(span, _) => {
1657                *span
1658            }
1659        }
1660    }
1661}
1662
1663impl Octal for Origin {
1664    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1665        match self {
1666            Origin::Deduced(_span, name, address) => {
1667                write!(f, "{name} (deduced to be at {address:o})")
1668            }
1669            Origin::Literal(_span, address) => fmt::Octal::fmt(&address, f),
1670            Origin::Symbolic(_span, name) => fmt::Display::fmt(&name, f),
1671        }
1672    }
1673}
1674
1675/// Indicates whether the hold bit is set, cleared or unspecified.
1676///
1677/// The hold bit is bit 4.9 of the instruction word (see section 6-2
1678/// of the Users Handbook).
1679///
1680/// The effect of the hold bit is explained in section 4-3.2 of the
1681/// Users Handbook.
1682#[derive(Debug, Copy, Clone, PartialEq, Eq)]
1683pub(crate) enum HoldBit {
1684    /// The value of the hold bit was not specified.
1685    Unspecified,
1686    /// The hold bit should be set.
1687    Hold,
1688    /// The hold bit should be cleared.  The user might want to do
1689    /// this because some opcodes (`LDE`, `ITE`, `JPX`, `JNX`) would
1690    /// otherwise automatically set it.
1691    NotHold,
1692}
1693
1694/// One, two or three commas.
1695#[derive(Debug, Clone, PartialEq, Eq)]
1696pub(crate) enum Commas {
1697    One(Span),
1698    Two(Span),
1699    Three(Span),
1700}
1701
1702impl Spanned for Commas {
1703    fn span(&self) -> Span {
1704        match &self {
1705            Commas::One(span) | Commas::Two(span) | Commas::Three(span) => *span,
1706        }
1707    }
1708}
1709
1710/// Part of a TX-2 instruction, convertible to a 36-bit value.
1711#[derive(Debug, Clone, PartialEq, Eq)]
1712pub(super) struct FragmentWithHold {
1713    /// Location within the source code
1714    pub(super) span: Span,
1715    /// Indicates that this fragment sets the hold bit.
1716    pub(super) holdbit: HoldBit,
1717    /// The remaining value of the instruction fragment (without the
1718    /// possible hold bit).
1719    pub(super) fragment: InstructionFragment,
1720}
1721
1722/// An instruction fragment ([`FragmentWithHold`]) or one or more
1723/// commas.
1724#[derive(Debug, Clone, PartialEq, Eq)]
1725pub(crate) enum CommasOrInstruction {
1726    I(FragmentWithHold),
1727    C(Option<Commas>),
1728}
1729
1730/// A component (usually a number) of an assembly-language instruction
1731/// with possible leading or trailing commas.
1732///
1733/// These are described in section 6-2.4 of the Users Handbook.
1734#[derive(Debug, Clone, PartialEq, Eq)]
1735pub(super) struct CommaDelimitedFragment {
1736    /// Indicates where in the input we found it.
1737    pub(super) span: Span,
1738    /// Indicates how many commas preceded it (if any).
1739    pub(super) leading_commas: Option<Commas>,
1740    /// Indicates whether the item inside the commas includes a hold
1741    /// bit.
1742    pub(super) holdbit: HoldBit,
1743    /// The quantity itself, within the commas
1744    pub(super) fragment: InstructionFragment,
1745    /// Indicates how many commas followed it (if any).
1746    pub(super) trailing_commas: Option<Commas>,
1747}
1748
1749impl CommaDelimitedFragment {
1750    pub(super) fn new(
1751        leading_commas: Option<Commas>,
1752        instruction: FragmentWithHold,
1753        trailing_commas: Option<Commas>,
1754    ) -> Self {
1755        let span: Span = {
1756            let spans: [Option<Span>; 3] = [
1757                leading_commas.as_ref().map(Spanned::span),
1758                Some(instruction.span),
1759                trailing_commas.as_ref().map(Spanned::span),
1760            ];
1761            match spans {
1762                [_, None, _] => {
1763                    unreachable!("CommaDelimitedInstruction cannot be completely empty")
1764                }
1765                [None, Some(m), None] => m,
1766                [None, Some(m), Some(r)] => span(m.start..r.end),
1767                [Some(l), _, Some(r)] => span(l.start..r.end),
1768                [Some(l), Some(m), None] => span(l.start..m.end),
1769            }
1770        };
1771        Self {
1772            span,
1773            leading_commas,
1774            holdbit: instruction.holdbit,
1775            fragment: instruction.fragment,
1776            trailing_commas,
1777        }
1778    }
1779
1780    fn symbol_uses(
1781        &self,
1782        block_id: BlockIdentifier,
1783        block_offset: Unsigned18Bit,
1784    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + '_
1785    {
1786        self.fragment.symbol_uses(block_id, block_offset)
1787    }
1788
1789    fn substitute_macro_parameters<M: MacroLookup>(
1790        &self,
1791        param_values: &MacroParameterBindings,
1792        on_missing: OnUnboundMacroParameter,
1793        macros: &M,
1794    ) -> Option<CommaDelimitedFragment> {
1795        self.fragment
1796            .substitute_macro_parameters(param_values, on_missing, macros)
1797            .map(|fragment| Self {
1798                fragment,
1799                ..self.clone()
1800            })
1801    }
1802
1803    fn allocate_rc_words<R: RcAllocator>(
1804        &mut self,
1805        explicit_symtab: &mut ExplicitSymbolTable,
1806        implicit_symtab: &mut ImplicitSymbolTable,
1807        rc_allocator: &mut R,
1808    ) -> Result<(), RcWordAllocationFailure> {
1809        self.fragment
1810            .allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)
1811    }
1812}
1813
1814impl Spanned for CommaDelimitedFragment {
1815    fn span(&self) -> Span {
1816        self.span
1817    }
1818}
1819
1820/// An instruction word in a TX-2 program.
1821#[derive(Debug, Clone, PartialEq, Eq)]
1822pub(crate) struct UntaggedProgramInstruction {
1823    pub(crate) fragments: OneOrMore<CommaDelimitedFragment>,
1824}
1825
1826impl From<OneOrMore<CommaDelimitedFragment>> for UntaggedProgramInstruction {
1827    fn from(fragments: OneOrMore<CommaDelimitedFragment>) -> Self {
1828        Self { fragments }
1829    }
1830}
1831
1832impl UntaggedProgramInstruction {
1833    fn symbol_uses(
1834        &self,
1835        block_id: BlockIdentifier,
1836        offset: Unsigned18Bit,
1837    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<'_>
1838    {
1839        self.fragments
1840            .iter()
1841            .flat_map(move |fragment| fragment.symbol_uses(block_id, offset))
1842    }
1843
1844    fn allocate_rc_words<R: RcAllocator>(
1845        &mut self,
1846        explicit_symtab: &mut ExplicitSymbolTable,
1847        implicit_symtab: &mut ImplicitSymbolTable,
1848        rc_allocator: &mut R,
1849    ) -> Result<(), RcWordAllocationFailure> {
1850        for inst in self.fragments.iter_mut() {
1851            inst.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)?;
1852        }
1853        Ok(())
1854    }
1855
1856    fn substitute_macro_parameters<M: MacroLookup>(
1857        &self,
1858        param_values: &MacroParameterBindings,
1859        on_missing: OnUnboundMacroParameter,
1860        macros: &M,
1861    ) -> Option<UntaggedProgramInstruction> {
1862        let tmp_frags: OneOrMore<Option<CommaDelimitedFragment>> = self
1863            .fragments
1864            .map(|frag| frag.substitute_macro_parameters(param_values, on_missing, macros));
1865        if tmp_frags.iter().any(Option::is_none) {
1866            None
1867        } else {
1868            Some(UntaggedProgramInstruction {
1869                fragments: tmp_frags.into_map(|mut maybe_frag| {
1870                    maybe_frag
1871                        .take()
1872                        .expect("we already checked this fragment wasn't None")
1873                }),
1874            })
1875        }
1876    }
1877}
1878
1879impl Spanned for UntaggedProgramInstruction {
1880    fn span(&self) -> Span {
1881        span(self.fragments.first().span.start..self.fragments.last().span.end)
1882    }
1883}
1884
1885/// The right-hand-side of an [`Equality`].
1886///
1887/// In other words, the value being assigned.
1888///
1889/// Equalities are described in section 6-2.2 of the Users Handbook.
1890#[derive(Debug, Clone, PartialEq, Eq)]
1891pub(super) struct EqualityValue {
1892    // Implementation choices:
1893    //
1894    // The RHS of an equality can be "any 36-bit value" (see TX-2 Users
1895    // Handbook, section 6-2.2, page 156 = 6-6).  Therefore it needs to
1896    // be possible to specify the value of the hold bit (since that is
1897    // one of those 36 bits).
1898    //
1899    // That means that if the right-hand-side of the assignment is
1900    // symbolic, the user needs to be able to set the hold bit with "h",
1901    // and we need to use in the representation something that records
1902    // that the hold bit is set.
1903    //
1904    // Although a [`TaggedProgramInstruction`] meets this requirement,
1905    // we do not use that, since we don't allow tags on the RHS, the
1906    // value cannot be a [`TaggedProgramInstruction`].
1907    //
1908    /// Location in the source code.
1909    pub(super) span: Span,
1910    /// The value which is assigned.
1911    pub(super) inner: UntaggedProgramInstruction,
1912}
1913
1914impl Spanned for EqualityValue {
1915    fn span(&self) -> Span {
1916        self.span
1917    }
1918}
1919
1920impl From<(Span, UntaggedProgramInstruction)> for EqualityValue {
1921    fn from((span, inner): (Span, UntaggedProgramInstruction)) -> Self {
1922        Self { span, inner }
1923    }
1924}
1925
1926impl EqualityValue {
1927    pub(super) fn substitute_macro_parameters<M: MacroLookup>(
1928        &self,
1929        param_values: &MacroParameterBindings,
1930        macros: &M,
1931    ) -> EqualityValue {
1932        // If we set an equality to the value of an unspecified macro
1933        // parameter, then that equality is set to zero.  This is
1934        // required by item (7) of section 6-4.6 ("The Defining
1935        // Subprogram") of the TX-2 User's Handbook.
1936        //
1937        // However, that item does not cover more complex cases like
1938        // "G = DUM2 + 4".  Our current interpretation will assign G
1939        // the value 4 when DUM2 is an unspecified macro parameter.
1940        // However, analysis of actual TX-2 programs may show that
1941        // this is not the correct interpretation.
1942        if let Some(inner) = self.inner.substitute_macro_parameters(
1943            param_values,
1944            // We use SubstituteZero here for the reasons
1945            // described in the block comment above.
1946            OnUnboundMacroParameter::SubstituteZero,
1947            macros,
1948        ) {
1949            EqualityValue {
1950                span: self.span,
1951                inner,
1952            }
1953        } else {
1954            unreachable!(
1955                "substitute_macro_parameters should not return None when OnUnboundMacroParameter::SubstituteZero is in effect"
1956            )
1957        }
1958    }
1959}
1960
1961/// A "Tag" is a symex used as a name for a place in a program.  A tag
1962/// is always terminated by an arrow ("->") and [in the symbol table]
1963/// it set to the numerical location of the word that it tags. [from
1964/// section 6-2.2 of the User's Handbook].
1965#[derive(Debug, Clone, PartialEq, Eq)]
1966pub(crate) struct Tag {
1967    pub(crate) name: SymbolName,
1968    pub(crate) span: Span,
1969}
1970
1971impl Tag {
1972    fn symbol_uses(
1973        &self,
1974        block_id: BlockIdentifier,
1975        block_offset: Unsigned18Bit,
1976    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
1977    {
1978        [Ok((
1979            self.name.clone(),
1980            self.span,
1981            SymbolUse::Definition(ExplicitDefinition::Tag(TagDefinition::Unresolved {
1982                block_id,
1983                block_offset,
1984                span: self.span,
1985            })),
1986        ))]
1987        .into_iter()
1988    }
1989}
1990
1991impl PartialOrd for Tag {
1992    /// Ordering for tags ignores the span.
1993    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1994        Some(self.cmp(other))
1995    }
1996}
1997
1998impl Ord for Tag {
1999    /// Ordering for tags ignores the span.
2000    fn cmp(&self, other: &Self) -> Ordering {
2001        self.name.cmp(&other.name)
2002    }
2003}
2004
2005/// A TX-2 instruction with zero or more [`Tag`]s.
2006#[derive(Debug, Clone, PartialEq, Eq)]
2007pub(crate) struct TaggedProgramInstruction {
2008    /// Location in the program
2009    pub(crate) span: Span,
2010    /// Tags which point to this instruction.
2011    pub(crate) tags: Vec<Tag>,
2012    /// The instruction itself.
2013    pub(crate) instruction: UntaggedProgramInstruction,
2014}
2015
2016impl TaggedProgramInstruction {
2017    pub(crate) fn symbol_uses(
2018        &self,
2019        block_id: BlockIdentifier,
2020        offset: Unsigned18Bit,
2021    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
2022    {
2023        let mut result: Vec<Result<_, _>> = Vec::new();
2024        result.extend(
2025            self.tags
2026                .iter()
2027                .flat_map(|tag| tag.symbol_uses(block_id, offset)),
2028        );
2029        result.extend(self.instruction.symbol_uses(block_id, offset));
2030        result.into_iter()
2031    }
2032
2033    #[cfg(test)]
2034    pub(crate) fn single(
2035        tags: Vec<Tag>,
2036        holdbit: HoldBit,
2037        inst_span: Span,
2038        frag_span: Span,
2039        frag: InstructionFragment,
2040    ) -> TaggedProgramInstruction {
2041        TaggedProgramInstruction {
2042            tags,
2043            span: inst_span,
2044            instruction: UntaggedProgramInstruction::from(OneOrMore::new(CommaDelimitedFragment {
2045                span: frag_span,
2046                leading_commas: None,
2047                holdbit,
2048                fragment: frag,
2049                trailing_commas: None,
2050            })),
2051        }
2052    }
2053
2054    #[cfg(test)]
2055    pub(crate) fn multiple(
2056        tags: Vec<Tag>,
2057        span: Span,
2058        first_fragment: CommaDelimitedFragment,
2059        more_fragments: Vec<CommaDelimitedFragment>,
2060    ) -> TaggedProgramInstruction {
2061        TaggedProgramInstruction {
2062            tags,
2063            span,
2064            instruction: UntaggedProgramInstruction::from(OneOrMore::with_tail(
2065                first_fragment,
2066                more_fragments,
2067            )),
2068        }
2069    }
2070
2071    fn emitted_word_count(&self) -> Unsigned18Bit {
2072        let _ = self;
2073        Unsigned18Bit::ONE
2074    }
2075
2076    pub(super) fn substitute_macro_parameters<M: MacroLookup>(
2077        &self,
2078        param_values: &MacroParameterBindings,
2079        on_missing: OnUnboundMacroParameter,
2080        macros: &M,
2081    ) -> Option<TaggedProgramInstruction> {
2082        self.instruction
2083            .substitute_macro_parameters(param_values, on_missing, macros)
2084            .map(|instruction| TaggedProgramInstruction {
2085                span: self.span,
2086                tags: self.tags.clone(),
2087                instruction,
2088            })
2089    }
2090
2091    fn allocate_rc_words<R: RcAllocator>(
2092        &mut self,
2093        explicit_symtab: &mut ExplicitSymbolTable,
2094        implicit_symtab: &mut ImplicitSymbolTable,
2095        rc_allocator: &mut R,
2096    ) -> Result<(), RcWordAllocationFailure> {
2097        self.instruction
2098            .allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)
2099    }
2100}
2101
2102impl Spanned for TaggedProgramInstruction {
2103    fn span(&self) -> Span {
2104        let begin = match self.tags.first() {
2105            Some(t) => t.span.start,
2106            None => self.instruction.span().start,
2107        };
2108        let end = self.instruction.span().end;
2109        Span::from(begin..end)
2110    }
2111}
2112
2113#[derive(Debug, Clone, PartialEq, Eq)]
2114pub(crate) struct InstructionSequence {
2115    pub(super) local_symbols: Option<ExplicitSymbolTable>,
2116    pub(super) instructions: Vec<TaggedProgramInstruction>,
2117}
2118
2119#[cfg(test)]
2120impl From<Vec<TaggedProgramInstruction>> for InstructionSequence {
2121    fn from(v: Vec<TaggedProgramInstruction>) -> Self {
2122        InstructionSequence {
2123            local_symbols: None,
2124            instructions: v,
2125        }
2126    }
2127}
2128
2129impl FromIterator<TaggedProgramInstruction> for InstructionSequence {
2130    fn from_iter<T>(iter: T) -> Self
2131    where
2132        T: IntoIterator<Item = TaggedProgramInstruction>,
2133    {
2134        InstructionSequence {
2135            local_symbols: None,
2136            instructions: iter.into_iter().collect(),
2137        }
2138    }
2139}
2140
2141/// Enumerate a sequence of items, decorating each with an
2142/// `Unsigned18Bit` offset value.
2143pub(crate) fn block_items_with_offset<T, I>(items: I) -> impl Iterator<Item = (Unsigned18Bit, T)>
2144where
2145    I: Iterator<Item = T>,
2146{
2147    items.enumerate().map(|(offset, item)| {
2148        let off: Unsigned18Bit = Unsigned18Bit::try_from(offset)
2149            .expect("block should not be larger than the TX-2's memory");
2150        (off, item)
2151    })
2152}
2153
2154/// We failed to build a local symbol table.
2155#[derive(Debug, PartialEq, Eq, Clone)]
2156pub(crate) enum LocalSymbolTableBuildFailure {
2157    InconsistentUsage(InconsistentSymbolUse),
2158    BadDefinition(BadSymbolDefinition),
2159}
2160
2161impl Spanned for LocalSymbolTableBuildFailure {
2162    fn span(&self) -> Span {
2163        match self {
2164            LocalSymbolTableBuildFailure::InconsistentUsage(inconsistent_symbol_use) => {
2165                inconsistent_symbol_use.span()
2166            }
2167            LocalSymbolTableBuildFailure::BadDefinition(bad_symbol_definition) => {
2168                bad_symbol_definition.span()
2169            }
2170        }
2171    }
2172}
2173
2174impl Display for LocalSymbolTableBuildFailure {
2175    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
2176        match self {
2177            LocalSymbolTableBuildFailure::InconsistentUsage(inconsistent_symbol_use) => {
2178                write!(f, "{inconsistent_symbol_use}")
2179            }
2180            LocalSymbolTableBuildFailure::BadDefinition(bad_symbol_definition) => {
2181                write!(f, "{bad_symbol_definition}")
2182            }
2183        }
2184    }
2185}
2186
2187impl Error for LocalSymbolTableBuildFailure {}
2188
2189impl InstructionSequence {
2190    pub(super) fn iter(&self) -> impl Iterator<Item = &TaggedProgramInstruction> {
2191        self.instructions.iter()
2192    }
2193
2194    pub(super) fn first(&self) -> Option<&TaggedProgramInstruction> {
2195        self.instructions.first()
2196    }
2197
2198    pub(crate) fn allocate_rc_words<R: RcAllocator>(
2199        &mut self,
2200        explicit_symtab: &mut ExplicitSymbolTable,
2201        implicit_symtab: &mut ImplicitSymbolTable,
2202        rc_allocator: &mut R,
2203    ) -> Result<(), RcWordAllocationFailure> {
2204        for ref mut statement in &mut self.instructions {
2205            statement.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)?;
2206        }
2207        Ok(())
2208    }
2209
2210    pub(crate) fn symbol_uses(
2211        &self,
2212        block_id: BlockIdentifier,
2213    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
2214    {
2215        let no_symbols = ExplicitSymbolTable::default();
2216        let local_scope: &ExplicitSymbolTable = self.local_symbols.as_ref().unwrap_or(&no_symbols);
2217        let mut result: Vec<Result<_, _>> = Vec::new();
2218
2219        for (off, statement) in block_items_with_offset(self.instructions.iter()) {
2220            result.extend(statement.symbol_uses(block_id, off).filter(|r| match r {
2221                Ok((symbol, _, _)) => !local_scope.is_defined(symbol),
2222                Err(_) => true,
2223            }));
2224        }
2225        result.into_iter()
2226    }
2227
2228    pub(crate) fn emitted_word_count(&self) -> Unsigned18Bit {
2229        self.iter()
2230            .map(TaggedProgramInstruction::emitted_word_count)
2231            .sum()
2232    }
2233
2234    #[allow(clippy::too_many_arguments)]
2235    pub(crate) fn build_binary_block<R: RcUpdater>(
2236        &self,
2237        location: Address,
2238        start_offset: Unsigned18Bit,
2239        explicit_symtab: &ExplicitSymbolTable,
2240        implicit_symtab: &mut ImplicitSymbolTable,
2241        memory_map: &MemoryMap,
2242        index_register_assigner: &mut IndexRegisterAssigner,
2243        rc_allocator: &mut R,
2244        final_symbols: &mut FinalSymbolTable,
2245        body: &Source<'_>,
2246        listing: &mut Listing,
2247        bad_symbol_definitions: &mut BTreeMap<SymbolName, ProgramError>,
2248    ) -> Result<Vec<Unsigned36Bit>, AssemblerFailure> {
2249        let mut words: Vec<Unsigned36Bit> = Vec::with_capacity(self.emitted_word_count().into());
2250        for (offset, instruction) in self.iter().enumerate() {
2251            let offset: Unsigned18Bit = Unsigned18Bit::try_from(offset)
2252                .ok()
2253                .and_then(|offset| offset.checked_add(start_offset))
2254                .expect("assembled code block should fit within physical memory");
2255            let address: Address = location.index_by(offset);
2256            for tag in &instruction.tags {
2257                final_symbols.define(
2258                    tag.name.clone(),
2259                    FinalSymbolType::Tag,
2260                    body.extract(tag.span.start..tag.span.end).to_string(),
2261                    FinalSymbolDefinition::PositionIndependent(address.into()),
2262                );
2263            }
2264
2265            if self.local_symbols.is_some() {
2266                unimplemented!(
2267                    "InstructionSequence::build_binary_block: evaluation with local symbol tables is not yet implemented"
2268                );
2269            }
2270            let mut ctx = EvaluationContext {
2271                explicit_symtab,
2272                implicit_symtab,
2273                memory_map,
2274                here: HereValue::Address(address),
2275                index_register_assigner,
2276                rc_updater: rc_allocator,
2277                lookup_operation: Default::default(),
2278            };
2279            let scope = ScopeIdentifier::global();
2280            match instruction.evaluate(&mut ctx, scope) {
2281                Ok(word) => {
2282                    listing.push_line(ListingLine {
2283                        span: Some(instruction.span),
2284                        rc_source: None,
2285                        content: Some((address, word)),
2286                    });
2287                    words.push(word);
2288                }
2289                Err(e) => {
2290                    record_undefined_symbol_or_return_failure(body, e, bad_symbol_definitions)?;
2291                }
2292            }
2293        }
2294        Ok(words)
2295    }
2296}
2297
2298/// An "Equality" (modern term: assignment).
2299///
2300#[derive(Debug, Clone, PartialEq, Eq)]
2301pub(crate) struct Equality {
2302    pub(crate) span: Span,
2303    pub(crate) name: SymbolName,
2304    pub(crate) value: EqualityValue,
2305}
2306
2307impl Equality {
2308    pub(super) fn symbol_uses(
2309        &self,
2310    ) -> impl Iterator<Item = Result<(SymbolName, Span, SymbolUse), InconsistentSymbolUse>> + use<>
2311    {
2312        [Ok((
2313            self.name.clone(),
2314            self.span,
2315            SymbolUse::Definition(
2316                // TODO: the expression.clone() on the next line is expensive.
2317                ExplicitDefinition::Equality(self.value.clone()),
2318            ),
2319        ))]
2320        .into_iter()
2321    }
2322}