assembler/
memorymap.rs

1//! Decide final position of blocks of code and allocate RC-words.
2use std::collections::BTreeMap;
3use std::error::Error;
4use std::fmt::{self, Display, Formatter};
5
6use base::Unsigned18Bit;
7use base::Unsigned36Bit;
8use base::prelude::Address;
9use base::prelude::IndexBy;
10
11use super::ast::InstructionSequence;
12use super::ast::Origin;
13use super::ast::RcUpdater;
14use super::listing::Listing;
15use super::source::Source;
16use super::span::{Span, Spanned};
17use super::symbol::SymbolName;
18use super::symtab::{
19    ExplicitSymbolTable, FinalSymbolTable, ImplicitSymbolTable, IndexRegisterAssigner,
20};
21use super::types::AssemblerFailure;
22use super::types::BlockIdentifier;
23use super::types::ProgramError;
24
25#[derive(Debug, PartialEq, Eq, Clone)]
26pub enum RcWordKind {
27    // Ivan Sutherland calls PipeConstruct "double addressing"
28    PipeConstruct,
29    Braces,
30    DefaultAssignment,
31}
32
33/// Indicates why we allocated an RC-word.
34#[derive(Debug, PartialEq, Eq, Clone)]
35pub struct RcWordSource {
36    pub span: Span,
37    pub kind: RcWordKind,
38}
39
40impl Spanned for RcWordSource {
41    fn span(&self) -> Span {
42        self.span
43    }
44}
45
46impl Display for RcWordKind {
47    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
48        f.write_str(match self {
49            RcWordKind::PipeConstruct => "pipe construct",
50            RcWordKind::Braces => "RC-word",
51            RcWordKind::DefaultAssignment => "default-assignment",
52        })
53    }
54}
55
56#[derive(Debug, PartialEq, Eq, Clone)]
57pub(crate) enum RcWordAllocationFailure {
58    RcBlockTooBig {
59        source: RcWordSource,
60        rc_block_len: usize,
61    },
62    InconsistentTag {
63        tag_name: SymbolName,
64        span: Span,
65        explanation: String,
66    },
67}
68
69impl Display for RcWordAllocationFailure {
70    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
71        match self {
72            RcWordAllocationFailure::RcBlockTooBig {
73                source: RcWordSource { kind, .. },
74                rc_block_len,
75            } => {
76                write!(
77                    f,
78                    "failed to allocate RC word for {kind}; RC block is already {rc_block_len} words long"
79                )
80            }
81            RcWordAllocationFailure::InconsistentTag {
82                tag_name,
83                span: _,
84                explanation,
85            } => {
86                write!(f, "failed to define tag {tag_name}: {explanation}")
87            }
88        }
89    }
90}
91
92#[derive(Debug, Clone, PartialEq, Eq)]
93pub(super) struct BlockPosition {
94    pub(super) block_identifier: BlockIdentifier,
95    // span is either the span of the origin specification if there is
96    // one, or otherwise the span of the first thing in the block.
97    pub(super) span: Span,
98    pub(super) origin: Option<Origin>,
99    pub(super) block_address: Option<Address>,
100    pub(super) block_size: Unsigned18Bit,
101}
102
103impl Spanned for BlockPosition {
104    fn span(&self) -> Span {
105        self.span
106    }
107}
108
109#[derive(Debug, Default, Clone, PartialEq, Eq)]
110pub(crate) struct MemoryMap {
111    blocks: Vec<BlockPosition>,
112}
113
114impl MemoryMap {
115    pub(crate) fn get(&self, block: &BlockIdentifier) -> Option<&BlockPosition> {
116        // We use a reference here for consistency with the get()
117        // methods of other containers.
118        #![allow(clippy::trivially_copy_pass_by_ref)]
119        let pos = usize::from(*block);
120        self.blocks.get(pos)
121    }
122
123    pub(crate) fn set_block_position(&mut self, block: BlockIdentifier, location: Address) {
124        match self.blocks.get_mut(usize::from(block)) {
125            Some(pos) => pos.block_address = Some(location),
126            None => {
127                unreachable!("attempted to set location of nonexistent block {block}");
128            }
129        }
130    }
131
132    pub(crate) fn iter(&self) -> impl Iterator<Item = &BlockPosition> {
133        self.blocks.iter()
134    }
135
136    pub(crate) fn new<I>(block_sizes: I) -> MemoryMap
137    where
138        I: IntoIterator<Item = (Span, Option<Origin>, Unsigned18Bit)>,
139    {
140        let blocks = block_sizes
141            .into_iter()
142            .enumerate()
143            .map(|(i, (span, maybe_origin, block_size))| {
144                if i > 0 {
145                    // The presence of an origin specification is what
146                    // prompts the creation of a second or later
147                    // block, so only the first block is allowed not
148                    // to have an origin.
149                    assert!(maybe_origin.is_some());
150                }
151                BlockPosition {
152                    block_identifier: BlockIdentifier::from(i),
153                    span,
154                    origin: maybe_origin,
155                    block_address: None,
156                    block_size,
157                }
158            })
159            .collect();
160        MemoryMap { blocks }
161    }
162}
163
164#[derive(Debug, Clone, PartialEq, Eq)]
165pub(crate) struct LocatedBlock {
166    pub(crate) origin: Option<Origin>,
167    pub(crate) location: Address,
168    pub(crate) sequences: Vec<InstructionSequence>,
169}
170
171impl LocatedBlock {
172    pub(super) fn emitted_word_count(&self) -> Unsigned18Bit {
173        self.sequences
174            .iter()
175            .map(InstructionSequence::emitted_word_count)
176            .sum()
177    }
178
179    pub(super) fn following_addr(&self) -> Address {
180        self.location.index_by(self.emitted_word_count())
181    }
182
183    pub(super) fn allocate_rc_words<R: RcAllocator>(
184        &mut self,
185        explicit_symtab: &mut ExplicitSymbolTable,
186        implicit_symtab: &mut ImplicitSymbolTable,
187        rc_allocator: &mut R,
188    ) -> Result<(), RcWordAllocationFailure> {
189        for seq in &mut self.sequences {
190            seq.allocate_rc_words(explicit_symtab, implicit_symtab, rc_allocator)?;
191        }
192        Ok(())
193    }
194
195    #[allow(clippy::too_many_arguments)]
196    pub(super) fn build_binary_block<R: RcUpdater>(
197        &self,
198        location: Address,
199        explicit_symtab: &ExplicitSymbolTable,
200        implicit_symtab: &mut ImplicitSymbolTable,
201        memory_map: &MemoryMap,
202        index_register_assigner: &mut IndexRegisterAssigner,
203        rc_allocator: &mut R,
204        final_symbols: &mut FinalSymbolTable,
205        body: &Source,
206        listing: &mut Listing,
207        undefined_symbols: &mut BTreeMap<SymbolName, ProgramError>,
208    ) -> Result<Vec<Unsigned36Bit>, AssemblerFailure> {
209        let word_count: usize = self
210            .sequences
211            .iter()
212            .map(|seq| usize::from(seq.emitted_word_count()))
213            .sum();
214        let mut result: Vec<Unsigned36Bit> = Vec::with_capacity(word_count);
215        for seq in &self.sequences {
216            let current_block_len: Unsigned18Bit = result
217                .len()
218                .try_into()
219                .expect("assembled code block should fit within physical memory");
220            let mut words: Vec<Unsigned36Bit> = seq.build_binary_block(
221                location,
222                current_block_len,
223                explicit_symtab,
224                implicit_symtab,
225                memory_map,
226                index_register_assigner,
227                rc_allocator,
228                final_symbols,
229                body,
230                listing,
231                undefined_symbols,
232            )?;
233            result.append(&mut words);
234        }
235        Ok(result)
236    }
237}
238
239impl Error for RcWordAllocationFailure {}
240
241pub(crate) trait RcAllocator {
242    fn allocate(
243        &mut self,
244        source: RcWordSource,
245        value: Unsigned36Bit,
246    ) -> Result<Address, RcWordAllocationFailure>;
247}
assembler/memorymap.rs

assembler/
memorymap.rs
