sim_lib_machine/
code.rs

1use std::collections::BTreeMap;
2
3use sha2::{Digest, Sha256};
4use sim_kernel::{Origin, SourceId};
5
6use crate::InstructionPolicy;
7
8/// Source units used to locate a decoded instruction.
9#[derive(Clone, Debug, PartialEq, Eq)]
10pub enum SourceLocation {
11    /// A byte range described by the kernel's lossless source contract.
12    Bytes(Origin),
13    /// A half-open token range, with the enclosing byte origin retained for diagnostics.
14    Tokens {
15        /// The enclosing source origin.
16        origin: Origin,
17        /// Inclusive first token index.
18        start: usize,
19        /// Exclusive token index.
20        end: usize,
21    },
22}
23
24impl SourceLocation {
25    fn source(&self) -> &SourceId {
26        match self {
27            Self::Bytes(origin) | Self::Tokens { origin, .. } => &origin.source,
28        }
29    }
30
31    fn range(&self) -> (LocationUnit, usize, usize) {
32        match self {
33            Self::Bytes(origin) => (LocationUnit::Byte, origin.span.start, origin.span.end),
34            Self::Tokens { start, end, .. } => (LocationUnit::Token, *start, *end),
35        }
36    }
37}
38
39#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
40enum LocationUnit {
41    Byte,
42    Token,
43}
44
45/// Stable metadata used to associate execution with a coverage counter.
46#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
47pub struct CoverageMetadata {
48    /// Stable counter identity assigned by the preparing consumer.
49    pub counter: u64,
50}
51
52/// A decoded instruction and all immutable metadata required before execution.
53#[derive(Clone, Debug, PartialEq, Eq)]
54pub struct LocatedInstruction<I, Id> {
55    instruction: I,
56    id: Id,
57    location: SourceLocation,
58    safepoint: bool,
59    coverage: Option<CoverageMetadata>,
60}
61
62impl<I, Id> LocatedInstruction<I, Id> {
63    /// Prepares one instruction. Its identity is checked against the policy while code is frozen.
64    pub fn new(
65        instruction: I,
66        id: Id,
67        location: SourceLocation,
68        safepoint: bool,
69        coverage: Option<CoverageMetadata>,
70    ) -> Self {
71        Self {
72            instruction,
73            id,
74            location,
75            safepoint,
76            coverage,
77        }
78    }
79
80    /// Returns the decoded instruction.
81    pub fn instruction(&self) -> &I {
82        &self.instruction
83    }
84
85    /// Returns its stable identity.
86    pub fn id(&self) -> &Id {
87        &self.id
88    }
89
90    /// Returns its source location.
91    pub fn location(&self) -> &SourceLocation {
92        &self.location
93    }
94
95    /// Returns whether this is a semantic safepoint.
96    pub fn is_safepoint(&self) -> bool {
97        self.safepoint
98    }
99
100    /// Returns the optional stable coverage-counter metadata.
101    pub fn coverage(&self) -> Option<CoverageMetadata> {
102        self.coverage
103    }
104}
105
106/// An unresolved branch destination supplied by a code preparer.
107#[derive(Clone, Debug, PartialEq, Eq)]
108pub enum TargetLocation<Id> {
109    /// A stable instruction identity.
110    Instruction(Id),
111    /// An exact byte boundary in a kernel-identified source.
112    Byte {
113        /// Source containing the destination.
114        source: SourceId,
115        /// Requested byte offset.
116        offset: usize,
117    },
118    /// An exact token boundary in a kernel-identified source.
119    Token {
120        /// Source containing the destination.
121        source: SourceId,
122        /// Requested token index.
123        index: usize,
124    },
125}
126
127/// A branch edge to validate and freeze into the target map.
128#[derive(Clone, Debug, PartialEq, Eq)]
129pub struct BranchTarget<Id> {
130    /// Identity of the instruction containing the branch.
131    pub from: Id,
132    /// Requested destination.
133    pub to: TargetLocation<Id>,
134}
135
136/// A protected-region declaration using half-open instruction identities.
137#[derive(Clone, Debug, PartialEq, Eq)]
138pub struct RegionSpec<Id> {
139    /// First protected instruction.
140    pub start: Id,
141    /// First instruction after the protected range, or `None` for code end.
142    pub end: Option<Id>,
143    /// Handler entry, which must resolve to an instruction boundary.
144    pub handler: TargetLocation<Id>,
145}
146
147/// A validated protected region whose positions can only be valid cursors.
148#[derive(Clone, Copy, Debug, PartialEq, Eq)]
149pub struct ProtectedRegion {
150    /// First protected instruction.
151    pub start: CodeCursor,
152    /// First instruction after the region; equal to `instruction_count` at code end.
153    pub end_index: usize,
154    /// Validated handler entry.
155    pub handler: CodeCursor,
156}
157
158/// An instruction position minted only by validated [`LocatedCode`].
159///
160/// Raw offsets cannot create cursors:
161///
162/// ```compile_fail
163/// use sim_lib_machine::CodeCursor;
164/// let cursor = CodeCursor(7);
165/// ```
166#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
167pub struct CodeCursor(usize);
168
169/// Exact refusal evidence produced while freezing located code.
170#[derive(Clone, Debug, PartialEq, Eq)]
171pub enum CodeError<Id> {
172    /// No instructions were supplied.
173    Empty,
174    /// An instruction's location is empty or reversed.
175    MalformedLocation {
176        /// Instruction carrying the malformed location.
177        instruction: Id,
178        /// Supplied inclusive start.
179        start: usize,
180        /// Supplied exclusive end.
181        end: usize,
182    },
183    /// Two instruction source ranges overlap.
184    OverlappingLocations {
185        /// Earlier instruction in preparation order.
186        first: Id,
187        /// Conflicting instruction.
188        second: Id,
189    },
190    /// The supplied stable identity does not match the instruction policy.
191    IdentityMismatch {
192        /// Identity supplied with the location.
193        supplied: Id,
194        /// Identity derived by the instruction policy.
195        derived: Id,
196    },
197    /// A stable instruction identity occurs more than once.
198    DuplicateIdentity {
199        /// Repeated identity.
200        instruction: Id,
201    },
202    /// A branch source, region boundary, or identity target is unknown.
203    UnknownInstruction {
204        /// Identity that is absent from the code.
205        instruction: Id,
206    },
207    /// A raw target lies strictly inside an instruction rather than on its boundary.
208    InteriorTarget {
209        /// Instruction containing the branch or region declaration.
210        from: Id,
211        /// Rejected raw source position.
212        target: usize,
213        /// Instruction whose interior contains the position.
214        containing: Id,
215    },
216    /// A raw target is outside every instruction boundary.
217    OutOfRangeTarget {
218        /// Instruction containing the branch or region declaration.
219        from: Id,
220        /// Rejected raw source position.
221        target: usize,
222    },
223    /// A protected region is empty or reversed.
224    MalformedRegion {
225        /// Declared first instruction.
226        start: Id,
227        /// Resolved exclusive end index.
228        end_index: usize,
229    },
230    /// Protected regions overlap.
231    OverlappingRegions {
232        /// Start identity of the first region.
233        first_start: Id,
234        /// Start identity of the conflicting region.
235        second_start: Id,
236    },
237}
238
239/// Immutable, fully validated located instructions and their control metadata.
240pub struct LocatedCode<P: InstructionPolicy> {
241    instructions: Box<[LocatedInstruction<P::Instruction, P::InstructionId>]>,
242    cursors: BTreeMap<P::InstructionId, CodeCursor>,
243    targets: BTreeMap<P::InstructionId, Box<[CodeCursor]>>,
244    regions: Box<[ProtectedRegion]>,
245}
246
247impl<P> LocatedCode<P>
248where
249    P: InstructionPolicy,
250    P::InstructionId: Copy + Eq + Ord,
251{
252    /// Validates every location and edge before freezing the code.
253    pub fn freeze(
254        instructions: Vec<LocatedInstruction<P::Instruction, P::InstructionId>>,
255        targets: Vec<BranchTarget<P::InstructionId>>,
256        regions: Vec<RegionSpec<P::InstructionId>>,
257    ) -> Result<Self, CodeError<P::InstructionId>> {
258        if instructions.is_empty() {
259            return Err(CodeError::Empty);
260        }
261
262        let mut cursors = BTreeMap::new();
263        for (index, located) in instructions.iter().enumerate() {
264            let derived = P::instruction_id(&located.instruction);
265            if derived != located.id {
266                return Err(CodeError::IdentityMismatch {
267                    supplied: located.id,
268                    derived,
269                });
270            }
271            if cursors.insert(located.id, CodeCursor(index)).is_some() {
272                return Err(CodeError::DuplicateIdentity {
273                    instruction: located.id,
274                });
275            }
276            let (unit, start, end) = located.location.range();
277            if start >= end {
278                return Err(CodeError::MalformedLocation {
279                    instruction: located.id,
280                    start,
281                    end,
282                });
283            }
284            for previous in &instructions[..index] {
285                let (previous_unit, previous_start, previous_end) = previous.location.range();
286                if previous.location.source() == located.location.source()
287                    && previous_unit == unit
288                    && start < previous_end
289                    && previous_start < end
290                {
291                    return Err(CodeError::OverlappingLocations {
292                        first: previous.id,
293                        second: located.id,
294                    });
295                }
296            }
297        }
298
299        let mut frozen_targets = BTreeMap::<P::InstructionId, Vec<CodeCursor>>::new();
300        for target in targets {
301            if !cursors.contains_key(&target.from) {
302                return Err(CodeError::UnknownInstruction {
303                    instruction: target.from,
304                });
305            }
306            let cursor = resolve_target::<P>(&target.to, target.from, &instructions, &cursors)?;
307            frozen_targets.entry(target.from).or_default().push(cursor);
308        }
309
310        let mut frozen_regions = Vec::with_capacity(regions.len());
311        for region in regions {
312            let start = *cursors
313                .get(&region.start)
314                .ok_or(CodeError::UnknownInstruction {
315                    instruction: region.start,
316                })?;
317            let end_index = match region.end {
318                Some(end) => {
319                    cursors
320                        .get(&end)
321                        .ok_or(CodeError::UnknownInstruction { instruction: end })?
322                        .0
323                }
324                None => instructions.len(),
325            };
326            if start.0 >= end_index {
327                return Err(CodeError::MalformedRegion {
328                    start: region.start,
329                    end_index,
330                });
331            }
332            let handler =
333                resolve_target::<P>(&region.handler, region.start, &instructions, &cursors)?;
334            frozen_regions.push((
335                region.start,
336                ProtectedRegion {
337                    start,
338                    end_index,
339                    handler,
340                },
341            ));
342        }
343        frozen_regions.sort_by_key(|(_, region)| (region.start, usize::MAX - region.end_index));
344        for pair in frozen_regions.windows(2) {
345            let earlier = pair[0].1;
346            let later = pair[1].1;
347            let crosses = earlier.start.0 < later.start.0
348                && later.start.0 < earlier.end_index
349                && earlier.end_index < later.end_index;
350            let same_start_not_nested =
351                earlier.start == later.start && earlier.end_index == later.end_index;
352            if crosses || same_start_not_nested {
353                return Err(CodeError::OverlappingRegions {
354                    first_start: pair[0].0,
355                    second_start: pair[1].0,
356                });
357            }
358        }
359
360        Ok(Self {
361            instructions: instructions.into_boxed_slice(),
362            cursors,
363            targets: frozen_targets
364                .into_iter()
365                .map(|(from, targets)| (from, targets.into_boxed_slice()))
366                .collect(),
367            regions: frozen_regions
368                .into_iter()
369                .map(|(_, region)| region)
370                .collect(),
371        })
372    }
373
374    /// Returns the entry cursor, always an instruction boundary.
375    pub fn entry(&self) -> CodeCursor {
376        CodeCursor(0)
377    }
378
379    /// Resolves a stable instruction identity to a valid cursor.
380    pub fn cursor(&self, id: P::InstructionId) -> Option<CodeCursor> {
381        self.cursors.get(&id).copied()
382    }
383
384    /// Returns the instruction addressed by `cursor`.
385    pub fn instruction(
386        &self,
387        cursor: CodeCursor,
388    ) -> &LocatedInstruction<P::Instruction, P::InstructionId> {
389        &self.instructions[cursor.0]
390    }
391
392    /// Advances to the next instruction boundary, or returns `None` at code end.
393    pub fn next(&self, cursor: CodeCursor) -> Option<CodeCursor> {
394        (cursor.0 + 1 < self.instructions.len()).then(|| CodeCursor(cursor.0 + 1))
395    }
396
397    /// Returns every validated branch target for an instruction in declaration order.
398    pub fn branch_targets(&self, from: P::InstructionId) -> &[CodeCursor] {
399        self.targets.get(&from).map_or(&[], Box::as_ref)
400    }
401
402    /// Returns the immutable protected-region table.
403    pub fn protected_regions(&self) -> &[ProtectedRegion] {
404        &self.regions
405    }
406
407    /// Selects the most deeply nested protected region containing `cursor`.
408    pub fn innermost_protected_region(&self, cursor: CodeCursor) -> Option<ProtectedRegion> {
409        self.regions
410            .iter()
411            .copied()
412            .filter(|region| region.start.0 <= cursor.0 && cursor.0 < region.end_index)
413            .max_by_key(|region| region.start.0)
414    }
415
416    /// Returns the number of instructions.
417    pub fn len(&self) -> usize {
418        self.instructions.len()
419    }
420
421    /// Returns whether there are no instructions. Valid located code is never empty.
422    pub fn is_empty(&self) -> bool {
423        self.instructions.is_empty()
424    }
425
426    pub(crate) fn instructions(&self) -> &[LocatedInstruction<P::Instruction, P::InstructionId>] {
427        &self.instructions
428    }
429
430    pub(crate) fn hash_structure(
431        &self,
432        digest: &mut Sha256,
433        mut encode_instruction: impl FnMut(&P::Instruction, &mut Vec<u8>),
434    ) {
435        digest.update(self.instructions.len().to_le_bytes());
436        for located in &self.instructions {
437            let mut bytes = Vec::new();
438            encode_instruction(&located.instruction, &mut bytes);
439            digest.update(bytes.len().to_le_bytes());
440            digest.update(bytes);
441            let (unit, start, end) = located.location.range();
442            digest.update([match unit {
443                LocationUnit::Byte => 0,
444                LocationUnit::Token => 1,
445            }]);
446            digest.update(start.to_le_bytes());
447            digest.update(end.to_le_bytes());
448            digest.update([u8::from(located.safepoint)]);
449            digest.update(
450                located
451                    .coverage
452                    .map_or(u64::MAX, |value| value.counter)
453                    .to_le_bytes(),
454            );
455        }
456        digest.update(self.targets.len().to_le_bytes());
457        for (from, targets) in &self.targets {
458            digest.update(self.cursors[from].0.to_le_bytes());
459            digest.update(targets.len().to_le_bytes());
460            for target in targets.iter() {
461                digest.update(target.0.to_le_bytes());
462            }
463        }
464        digest.update(self.regions.len().to_le_bytes());
465        for region in &self.regions {
466            digest.update(region.start.0.to_le_bytes());
467            digest.update(region.end_index.to_le_bytes());
468            digest.update(region.handler.0.to_le_bytes());
469        }
470    }
471}
472
473fn resolve_target<P: InstructionPolicy>(
474    target: &TargetLocation<P::InstructionId>,
475    from: P::InstructionId,
476    instructions: &[LocatedInstruction<P::Instruction, P::InstructionId>],
477    cursors: &BTreeMap<P::InstructionId, CodeCursor>,
478) -> Result<CodeCursor, CodeError<P::InstructionId>>
479where
480    P::InstructionId: Copy + Eq + Ord,
481{
482    if let TargetLocation::Instruction(id) = target {
483        return cursors
484            .get(id)
485            .copied()
486            .ok_or(CodeError::UnknownInstruction { instruction: *id });
487    }
488    let (source, unit, position) = match target {
489        TargetLocation::Byte { source, offset } => (source, LocationUnit::Byte, *offset),
490        TargetLocation::Token { source, index } => (source, LocationUnit::Token, *index),
491        TargetLocation::Instruction(_) => unreachable!(),
492    };
493    for (index, located) in instructions.iter().enumerate() {
494        let (located_unit, start, end) = located.location.range();
495        if located.location.source() == source && located_unit == unit {
496            if position == start {
497                return Ok(CodeCursor(index));
498            }
499            if start < position && position < end {
500                return Err(CodeError::InteriorTarget {
501                    from,
502                    target: position,
503                    containing: located.id,
504                });
505            }
506        }
507    }
508    Err(CodeError::OutOfRangeTarget {
509        from,
510        target: position,
511    })
512}
sim_lib_machine/code.rs

sim_lib_machine/
code.rs
