Provenance: a pointer is not an integer

Store a two-bit tag in each element pointer, then recover the original value and tag without losing the pointer's provenance.

pub fn tagged_pointers(vals: Vec<u32>, tags: Vec<u64>) -> Vec<u64>

For each value at index i, use tags[i] & 3, or 0 if that tag is missing. Ignore extra tags. Return one result per value, in input order:

result = (u64::from(value) << 2) | tag

Promote the value to u64 before shifting so that all 32 value bits survive. Empty values produce an empty output. Duplicate values and tags are retained.

vals = [1, 2, 3, 4], tags = [0, 1, 2, 3] -> [4, 9, 14, 19]
vals = [5, 6],       tags = [7]          -> [23, 24]
vals = [4294967295], tags = [3]          -> [17179869183]

Build and read the pointer table as the starter does. Use addr, map_addr or with_addr for address manipulation, rather than pointer-to-integer and integer-to-pointer casts. Ordinary integer conversions for tags and outputs are still allowed. Output tests alone cannot enforce this implementation rule.

An address is not enough to justify an access

A raw pointer has an address and provenance. Provenance describes where the pointer came from and helps determine which memory it may access. It is part of Rust's abstract memory model, not necessarily an extra runtime field in the machine pointer.

Matching a numeric address does not establish validity. A pointer derived from one allocation does not gain access to a neighboring allocation simply because address arithmetic lands there. Alignment, initialization, lifetime and aliasing requirements also apply to a read.

Do not expect a particular result from an invalid access. It may appear to work in one build, but that observation is not evidence that it is defined.

Use the alignment bits temporarily

This representation requires align_of::<u32>() >= 4; the supplied code checks that requirement at compile time. A properly aligned element pointer then has two zero low address bits, which can temporarily hold a tag from 0 through 3.

&raw const *slot creates a raw pointer to the element referred to by slot. The loop already obtained slot as a shared reference from vals.iter(); the raw-borrow expression does not require creating another reference.

Set the low bits with p.map_addr(|address| address | tag). Before reading, recover the tag using tagged.addr() & TAG_MASK, then clear both tag bits using tagged.map_addr(|address| address & !TAG_MASK).

The tagged pointer itself may be misaligned. Store and manipulate it, but dereference only the cleaned pointer. Keep vals alive and unchanged so its initialized elements and allocation remain available throughout both phases.

Preserve a pointer while changing its address

Reading p.addr() does not invalidate p. The integer alone cannot carry its provenance back, but retaining the pointer lets with_addr or map_addr use it explicitly.

These methods are safe address operations. They do not make an arbitrary resulting pointer safe to dereference. Here clearing the tag restores the original element address while preserving the source pointer's provenance.

A small complete example illustrates the round trip:

fn main() {
    const MASK: usize = 3;
    assert!(align_of::<u32>() >= 4);
    let value = 42_u32;
    let pointer = &raw const value;
    let tagged = pointer.map_addr(|address| address | 2);
    assert_eq!(tagged.addr() & MASK, 2);
    let clean = tagged.with_addr(tagged.addr() & !MASK);
    assert_eq!(clean, pointer);
    // SAFETY: the mask restores the aligned address of the live, initialized
    // value, and clean retains pointer's provenance. There is no mutation.
    assert_eq!(unsafe { *clean }, 42);
}

Distinguish strict from exposed provenance

Pointer/integer casts are not automatically undefined behavior. A pointer cast to an integer exposes its provenance, and an integer cast back uses exposed-provenance semantics. The named APIs are expose_provenance and with_exposed_provenance. Whether a resulting access is valid still depends on the applicable provenance and memory-access requirements.

This exercise uses strict-provenance operations because a source pointer is available throughout. Keeping that relationship explicit makes the code easier to reason about and supports stricter analysis. It does not imply that every cast-based round trip is invalid, or that two versions must produce identical machine code.

Repair the starter's two defects

The starter's TAG_MASK is 0b1, so it stores and recovers only one tag bit. Because it uses that same mask in both phases, it loses tag information rather than necessarily leaving the cleaned pointer misaligned. Change the mask to 0b11 for the requested two-bit representation.

Separately, dereferencing clean requires an unsafe block. Add one with a safety comment covering restored alignment, original element address, retained provenance, initialized storage and the unchanged live vector.

A passing submission must compile, pass the tests, and pass clippy -D warnings. A matching output does not establish use of strict provenance or prove every unsafe operation valid. Miri can check many violations on executed paths; it is not a proof covering all possible inputs.