Repository: rigetti/quil-rs (language: python)

Issue:
Expand calibrations with source mapping
Currently, calibration expansion happens somewhat opaquely: a `Vec<Instruction>` goes in, and another `Vec<Instruction>` comes out. In complex programs, it can be hard for a user to discern which post-calibration instructions originated from which pre-calibration instructions.

This can be fixed with a source map. Perhaps it can be structured like this:

```
struct SourceMap<SourceIndex, TargetIndex> {
    entries: Vec<SourceMapEntry<SourceIndex, TargetIndex>>
}

struct SourceMapEntry<Label, SourceIndex, TargetIndex> {
    /// A description of the mapping, such the calibration used to perform the expansion
    label: Label,

    source_location: Vec<SourceIndex>,
    target_location: Vec<TargetIndex>,
}
```

these are generic over `*Index` in order to be re-used for other mappings, such as in parsing a program (mapping `nom::locate` information such as line and column span). `Label`, likewise, would be a different type in these situations:

* For calibration expansion, may be the calibration used to perform the expansion. Users like @bramathon have often wondered about which DEFCAL was actually being used, and this could help make that explicit. We'd have to figure out how this works for nested expansions.
* For parsing, might just be `()`, I don't see a need for a label

This type would be made available for other libraries to use as well, such as compilers which consume Quil.

Finally, `SourceMap`s should be able to be folded, such that a program can undergo multiple transformations in series and emit a single mapping from the original text down to the final artifact.


Discussion / hints:

Fix patch:
diff --git a/Cargo.lock b/Cargo.lock
index 0e2effee..b98d7afe 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -332,6 +332,12 @@ dependencies = [
  "powerfmt",
 ]
 
+[[package]]
+name = "diff"
+version = "0.1.13"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "56254986775e3233ffa9c4d7d3faaf6d36a2c09d30b20687e9f88bc8bafc16c8"
+
 [[package]]
 name = "dot-writer"
 version = "0.1.3"
@@ -1009,6 +1015,16 @@ version = "0.2.17"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de"
 
+[[package]]
+name = "pretty_assertions"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "af7cee1a6c8a5b9208b3cb1061f10c0cb689087b3d8ce85fb9d2dd7a29b6ba66"
+dependencies = [
+ "diff",
+ "yansi",
+]
+
 [[package]]
 name = "proc-macro2"
 version = "0.4.30"
@@ -1132,7 +1148,7 @@ checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0"
 
 [[package]]
 name = "quil-cli"
-version = "0.6.0-rc.1"
+version = "0.6.1"
 dependencies = [
  "anyhow",
  "clap",
@@ -1141,7 +1157,7 @@ dependencies = [
 
 [[package]]
 name = "quil-py"
-version = "0.13.0-rc.1"
+version = "0.13.1"
 dependencies = [
  "indexmap",
  "ndarray",
@@ -1156,7 +1172,7 @@ dependencies = [
 
 [[package]]
 name = "quil-rs"
-version = "0.29.0-rc.1"
+version = "0.29.1"
 dependencies = [
  "approx",
  "clap",
@@ -1172,6 +1188,7 @@ dependencies = [
  "num-complex",
  "once_cell",
  "petgraph",
+ "pretty_assertions",
  "proptest",
  "proptest-derive",
  "rand",
@@ -2036,3 +2053,9 @@ name = "windows_x86_64_msvc"
 version = "0.52.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "32b752e52a2da0ddfbdbcc6fceadfeede4c939ed16d13e648833a61dfb611ed8"
+
+[[package]]
+name = "yansi"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "09041cd90cf85f7f8b2df60c646f853b7f535ce68f85244eb6731cf89fa498ec"
diff --git a/quil-py/README-py.md b/quil-py/README-py.md
index b51f462a..18340fba 100644
--- a/quil-py/README-py.md
+++ b/quil-py/README-py.md
@@ -4,7 +4,7 @@
 
 The `quil` package provides tools for constructing, manipulating, parsing, and printing [Quil](https://github.com/quil-lang/quil) programs. Internally, it is powered by [quil-rs](https://github.com/rigetti/quil-rs).
 
-This package is still in early development and breaking changes should be expected between minor versions.
+This package is still in development and breaking changes should be expected between minor versions.
 
 # Documentation
 
diff --git a/quil-py/quil/instructions/__init__.pyi b/quil-py/quil/instructions/__init__.pyi
index 1e8f253b..ba491304 100644
--- a/quil-py/quil/instructions/__init__.pyi
+++ b/quil-py/quil/instructions/__init__.pyi
@@ -837,11 +837,8 @@ class UnaryLogic:
 class Calibration:
     def __new__(
         cls,
-        name: str,
-        parameters: Sequence[Expression],
-        qubits: Sequence[Qubit],
+        identifier: CalibrationIdentifier,
         instructions: Sequence[Instruction],
-        modifiers: Sequence[GateModifier],
     ) -> Self: ...
     @property
     def name(self) -> str: ...
@@ -856,6 +853,10 @@ class Calibration:
     @qubits.setter
     def qubits(self, qubits: Sequence[Qubit]) -> None: ...
     @property
+    def identifier(self) -> CalibrationIdentifier: ...
+    @identifier.setter
+    def identifier(self, identifier: CalibrationIdentifier) -> None: ...
+    @property
     def instructions(self) -> List[Instruction]: ...
     @instructions.setter
     def instructions(self, instructions: Sequence[Instruction]) -> None: ...
@@ -884,11 +885,55 @@ class Calibration:
     def __copy__(self) -> Self:
         """Returns a shallow copy of the class."""
 
+class CalibrationIdentifier:
+    def __new__(
+        cls,
+        name: str,
+        parameters: Sequence[Expression],
+        qubits: Sequence[Qubit],
+        modifiers: Sequence[GateModifier],
+    ) -> Self: ...
+    @property
+    def name(self) -> str: ...
+    @name.setter
+    def name(self, name: str) -> None: ...
+    @property
+    def parameters(self) -> List[Expression]: ...
+    @parameters.setter
+    def parameters(self, parameters: Sequence[Expression]) -> None: ...
+    @property
+    def qubits(self) -> List[Qubit]: ...
+    @qubits.setter
+    def qubits(self, qubits: Sequence[Qubit]) -> None: ...
+    @property
+    def modifiers(self) -> List[GateModifier]: ...
+    @modifiers.setter
+    def modifiers(self, modifiers: Sequence[GateModifier]) -> None: ...
+    def to_quil(self) -> str:
+        """Attempt to convert the instruction to a valid Quil string.
+
+        Raises an exception if the instruction can't be converted to valid Quil.
+        """
+        ...
+    def to_quil_or_debug(self) -> str:
+        """Convert the instruction to a Quil string.
+
+        If any part of the instruction can't be converted to valid Quil, it will be printed in a human-readable debug format.
+        """
+    def __deepcopy__(self, _: Dict) -> Self:
+        """Creates and returns a deep copy of the class.
+
+        If the instruction contains any ``QubitPlaceholder`` or ``TargetPlaceholder``, then they will be replaced with
+        new placeholders so resolving them in the copy will not resolve them in the original.
+        Should be used by passing an instance of the class to ``copy.deepcopy``
+        """
+    def __copy__(self) -> Self:
+        """Returns a shallow copy of the class."""
+
 class MeasureCalibrationDefinition:
     def __new__(
         cls,
-        qubit: Optional[Qubit],
-        parameter: str,
+        identifier: MeasureCalibrationIdentifier,
         instructions: Sequence[Instruction],
     ) -> Self: ...
     @property
@@ -900,6 +945,10 @@ class MeasureCalibrationDefinition:
     @parameter.setter
     def parameter(self, parameter: str) -> None: ...
     @property
+    def identifier(self) -> MeasureCalibrationIdentifier: ...
+    @identifier.setter
+    def identifier(self, identifier: MeasureCalibrationIdentifier) -> None: ...
+    @property
     def instructions(self) -> List[Instruction]: ...
     @instructions.setter
     def instructions(self, instructions: Sequence[Instruction]) -> None: ...
@@ -924,6 +973,41 @@ class MeasureCalibrationDefinition:
     def __copy__(self) -> Self:
         """Returns a shallow copy of the class."""
 
+class MeasureCalibrationIdentifier:
+    def __new__(
+        cls,
+        qubit: Optional[Qubit],
+        parameter: str,
+    ) -> Self: ...
+    @property
+    def qubit(self) -> Optional[Qubit]: ...
+    @qubit.setter
+    def qubit(self, qubit: Optional[Qubit]) -> None: ...
+    @property
+    def parameter(self) -> str: ...
+    @parameter.setter
+    def parameter(self, parameter: str) -> None: ...
+    def to_quil(self) -> str:
+        """Attempt to convert the instruction to a valid Quil string.
+
+        Raises an exception if the instruction can't be converted to valid Quil.
+        """
+        ...
+    def to_quil_or_debug(self) -> str:
+        """Convert the instruction to a Quil string.
+
+        If any part of the instruction can't be converted to valid Quil, it will be printed in a human-readable debug format.
+        """
+    def __deepcopy__(self, _: Dict) -> Self:
+        """Creates and returns a deep copy of the class.
+
+        If the instruction contains any ``QubitPlaceholder`` or ``TargetPlaceholder``, then they will be replaced with
+        new placeholders so resolving them in the copy will not resolve them in the original.
+        Should be used by passing an instance of the class to ``copy.deepcopy``
+        """
+    def __copy__(self) -> Self:
+        """Returns a shallow copy of the class."""
+
 class CircuitDefinition:
     def __new__(
         cls,
diff --git a/quil-py/quil/program/__init__.pyi b/quil-py/quil/program/__init__.pyi
index 87f83ef8..9f6a9d47 100644
--- a/quil-py/quil/program/__init__.pyi
+++ b/quil-py/quil/program/__init__.pyi
@@ -1,4 +1,74 @@
-from typing import Callable, Dict, FrozenSet, List, Optional, Sequence, Set, final
+"""
+The `quil.program` module contains classes for constructing and representing a Quil program.
+
+# Examples
+
+## Source Mapping for Calibration Expansion
+
+```py
+import inspect
+from quil.program import Program
+
+program_text = inspect.cleandoc(
+    \"\"\"
+    DEFCAL X 0:
+        Y 0
+
+    DEFCAL Y 0:
+        Z 0
+
+    X 0 # This instruction is index 0
+    Y 0 # This instruction is index 1
+    \"\"\"
+)
+
+# First, we parse the program and expand its calibrations
+program = Program.parse(program_text)
+expansion = program.expand_calibrations_with_source_map()
+source_map = expansion.source_map()
+
+# This is what we expect the expanded program to be. X and Y have each been replaced by Z.
+expected_program_text = inspect.cleandoc(
+    \"\"\"
+    DEFCAL X 0:
+        Y 0
+
+    DEFCAL Y 0:
+        Z 0
+
+    Z 0 # This instruction is index 0
+    Z 0 # This instruction is index 1
+    \"\"\"
+)
+assert expansion.program().to_quil() == Program.parse(expected_program_text).to_quil()
+
+# In order to discover _which_ calibration led to the first Z in the resulting program, we
+# can interrogate the expansion source mapping.
+# 
+# For instance, the X at index 0 should have been replaced with a Z at index 0.
+# Here's how we can confirm that:
+
+# First, we list the calibration expansion targets for that first instruction...
+targets = source_map.list_targets_for_source_index(0)
+
+# ...then we extract the expanded instruction.
+# If the instruction had _not_ been expanded (i.e. there was no matching calibration), then `as_expanded()` would return `None`.
+expanded = targets[0].as_expanded()
+
+# This line shows how that `X 0` was expanded into instruction index 0 (only) within the expanded program.
+# The end of the range is exclusive.
+assert expanded.range() == range(0, 1)
+
+# We can also map instructions in reverse: given an instruction index in the expanded program, we can find the source index.
+# This is useful for understanding the provenance of instructions in the expanded program.
+sources = source_map.list_sources_for_target_index(1)
+
+# In this case, the instruction was expanded from the source program at index 1.
+assert sources == [1]
+```
+"""
+
+from typing import Callable, Dict, FrozenSet, List, Optional, Sequence, Set, Union, final
 
 import numpy as np
 from numpy.typing import NDArray
@@ -7,12 +77,14 @@ from typing_extensions import Self
 from quil.instructions import (
     AttributeValue,
     Calibration,
+    CalibrationIdentifier,
     Declaration,
     FrameIdentifier,
     Gate,
     GateDefinition,
     Instruction,
     MeasureCalibrationDefinition,
+    MeasureCalibrationIdentifier,
     Measurement,
     MemoryReference,
     Qubit,
@@ -65,6 +137,12 @@ class Program:
         expands directly or indirectly into itself)
         """
         ...
+    def expand_calibrations_with_source_map(self) -> ProgramCalibrationExpansion:
+        """Expand any instructions in the program which have a matching calibration, leaving the others unchanged.
+
+        Return the expanded copy of the program and a source mapping describing the expansions made.
+        """
+        ...
     def into_simplified(self) -> "Program":
         """Simplify this program into a new `Program` which contains only instructions and definitions which are executed; effectively, perform dead code removal.
 
@@ -258,6 +336,97 @@ class BasicBlock:
         If this is ``None``, the implicit behavior is to "continue" to the subsequent block.
         """
 
+@final
+class CalibrationExpansion:
+    def calibration_used(self) -> CalibrationSource: ...
+    """The calibration which was used to expand the instruction."""
+    def range(self) -> range: ...
+    """The range of instructions in the expanded list which were generated by this expansion."""
+    def expansions(self) -> CalibrationExpansionSourceMap: ...
+    """The source map describing the nested expansions made."""
+
+@final
+class CalibrationExpansionSourceMap:
+    def entries(self) -> List[CalibrationExpansionSourceMapEntry]: ...
+    def list_sources_for_target_index(self, target_index: int) -> List[int]:
+        """Return the locations in the source which were expanded to generate that instruction.
+
+        This is `O(n)` where `n` is the number of first-level calibration expansions performed.
+        """
+        ...
+
+    def list_sources_for_calibration_used(self, calibration_used: CalibrationSource) -> List[int]:
+        """Return the locations in the source program which were expanded using a calibration.
+
+        This is `O(n)` where `n` is the number of first-level calibration expansions performed.
+        """
+        ...
+
+    def list_targets_for_source_index(self, source_index: int) -> List[CalibrationExpansion]:
+        """Given a source index, return information about its expansion.
+
+        This is `O(n)` where `n` is the number of first-level calibration expansions performed.
+        """
+        ...
+
+@final
+class CalibrationExpansionSourceMapEntry:
+    """A description of the expansion of one instruction into other instructions.
+
+    If present, the instruction located at `source_location` was expanded using calibrations
+    into the instructions located at `target_location`.
+
+    Note that both `source_location` and `target_location` are relative to the scope of expansion.
+    In the case of a nested expansion, both describe the location relative only to that
+    level of expansion and *not* the original program.
+
+    Consider the following example:
+
+    ```
+    DEFCAL A:
+        NOP
+        B
+        HALT
+
+
+    DEFCAL B:
+        NOP
+        WAIT
+
+    NOP
+    NOP
+    NOP
+    A
+    ```
+
+    In this program, `A` will expand into `NOP`, `B`, and `HALT`. Then, `B` will expand into `NOP` and `WAIT`.
+    Each level of this expansion will have its own `CalibrationExpansionSourceMap` describing the expansion.
+    In the map of `B` to `NOP` and `WAIT`, the `source_location` will be `1` because `B` is the second instruction
+    in `DEFCAL A`, even though `A` is the 4th instruction (index = 3) in the original program.
+    """
+    def source_location(self) -> int: ...
+    """The instruction index within the source program's body instructions."""
+    def target_location(self) -> CalibrationExpansion: ...
+    """The location of the expanded instruction within the target program's body instructions."""
+
+@final
+class CalibrationSource:
+    """The source of a calibration expansion.
+
+    Can be either a calibration (`DEFCAL`) or a measure calibration (`DEFCAL MEASURE`).
+    """
+    def as_calibration(self) -> CalibrationIdentifier: ...
+    def as_measure_calibration(self) -> MeasureCalibrationIdentifier: ...
+    def is_calibration(self) -> bool: ...
+    def is_measure_calibration(self) -> bool: ...
+    def to_calibration(self) -> CalibrationIdentifier: ...
+    def to_measure_calibration(self) -> MeasureCalibrationIdentifier: ...
+    @staticmethod
+    def from_calibration(inner: CalibrationIdentifier): ...
+    @staticmethod
+    def from_measure_calibration(inner: MeasureCalibrationIdentifier): ...
+    def inner(self) -> Union[CalibrationIdentifier, MeasureCalibrationIdentifier]: ...
+
 @final
 class CalibrationSet:
     @staticmethod
@@ -318,6 +487,28 @@ class CalibrationSet:
         """Return the Quil instructions which describe the contained calibrations."""
         ...
 
+@final
+class MaybeCalibrationExpansion:
+    """The result of having expanded a certain instruction within a program.
+
+    Has two variants:
+
+    - `expanded`: The instruction was expanded into other instructions, described by a `CalibrationExpansion`.
+    - `int`: The instruction was not expanded and is described by an integer, the index of the instruction
+        within the resulting program's body instructions.
+    """
+    def as_expanded(self) -> CalibrationExpansion: ...
+    def as_unexpanded(self) -> int: ...
+    @staticmethod
+    def from_expanded(inner: CalibrationExpansion): ...
+    @staticmethod
+    def from_unexpanded(inner: int): ...
+    def inner(self) -> Union[CalibrationExpansion, int]: ...
+    def is_expanded(self) -> bool: ...
+    def is_unexpanded(self) -> bool: ...
+    def to_expanded(self) -> CalibrationExpansion: ...
+    def to_unexpanded(self) -> int: ...
+
 class ScheduleSecondsItem:
     """A single item within a fixed schedule, representing a single instruction within a basic block."""
 
@@ -412,3 +603,45 @@ class MemoryRegion:
     def sharing(self) -> Optional[Sharing]: ...
     @sharing.setter
     def sharing(self, sharing: Optional[Sharing]): ...
+
+@final
+class ProgramCalibrationExpansion:
+    def program(self) -> Program: ...
+    """The program containing the expanded instructions"""
+    def source_map(self) -> ProgramCalibrationExpansionSourceMap: ...
+    """The source mapping describing the expansions made"""
+
+@final
+class ProgramCalibrationExpansionSourceMap:
+    def entries(self) -> List[ProgramCalibrationExpansionSourceMapEntry]: ...
+    def list_sources_for_target_index(self, target_index: int) -> List[int]:
+        """Return the locations in the source which were expanded to generate that instruction.
+
+        This is `O(n)` where `n` is the number of source instructions.
+        """
+        ...
+
+    def list_sources_for_calibration_used(self, calibration_used: CalibrationSource) -> List[int]:
+        """Return the locations in the source program which were expanded using a calibration.
+
+        This is `O(n)` where `n` is the number of source instructions.
+        """
+        ...
+
+    def list_targets_for_source_index(self, source_index: int) -> List[MaybeCalibrationExpansion]:
+        """Given a source index, return information about its expansion.
+
+        This is `O(n)` where `n` is the number of source instructions.
+        """
+        ...
+
+@final
+class ProgramCalibrationExpansionSourceMapEntry:
+    """A description of the possible expansion of one instruction into other instructions.
+
+    Valid within the scope of a program's calibrations.
+    """
+    def source_location(self) -> int: ...
+    """The instruction index within the source program's body instructions."""
+    def target_location(self) -> MaybeCalibrationExpansion: ...
+    """The location of the possibly-expanded instruction within the target program's body instructions."""
diff --git a/quil-py/src/instruction/calibration.rs b/quil-py/src/instruction/calibration.rs
index f9db3ce3..eba397c3 100644
--- a/quil-py/src/instruction/calibration.rs
+++ b/quil-py/src/instruction/calibration.rs
@@ -1,12 +1,15 @@
 use quil_rs::{
     expression::Expression,
-    instruction::{Calibration, GateModifier, Instruction, MeasureCalibrationDefinition, Qubit},
+    instruction::{
+        Calibration, CalibrationIdentifier, GateModifier, Instruction,
+        MeasureCalibrationDefinition, MeasureCalibrationIdentifier, Qubit,
+    },
 };
 
 use rigetti_pyo3::{
     impl_repr, py_wrap_data_struct,
     pyo3::{pymethods, types::PyString, Py, PyResult, Python},
-    PyTryFrom, ToPythonError,
+    PyTryFrom, PyWrapper, ToPythonError,
 };
 
 use crate::{
@@ -20,11 +23,8 @@ py_wrap_data_struct! {
     #[derive(Debug, PartialEq)]
     #[pyo3(subclass, module = "quil.instructions")]
     PyCalibration(Calibration) as "Calibration" {
-        instructions: Vec<Instruction> => Vec<PyInstruction>,
-        modifiers: Vec<GateModifier> => Vec<PyGateModifier>,
-        name: String => Py<PyString>,
-        parameters: Vec<Expression> => Vec<PyExpression>,
-        qubits: Vec<Qubit> => Vec<PyQubit>
+        identifier: CalibrationIdentifier => PyCalibrationIdentifier,
+        instructions: Vec<Instruction> => Vec<PyInstruction>
     }
 }
 impl_repr!(PyCalibration);
@@ -35,22 +35,88 @@ impl_pickle_for_instruction!(PyCalibration);
 
 #[pymethods]
 impl PyCalibration {
+    #[new]
+    pub fn new(
+        py: Python<'_>,
+        identifier: PyCalibrationIdentifier,
+        instructions: Vec<PyInstruction>,
+    ) -> PyResult<Self> {
+        Ok(Self(
+            Calibration::new(
+                CalibrationIdentifier::py_try_from(py, &identifier)?,
+                Vec::<Instruction>::py_try_from(py, &instructions)?,
+            )
+            .map_err(RustIdentifierValidationError::from)
+            .map_err(RustIdentifierValidationError::to_py_err)?,
+        ))
+    }
+
+    pub fn name(&self) -> &str {
+        &self.as_inner().identifier.name
+    }
+
+    pub fn parameters(&self) -> Vec<PyExpression> {
+        self.as_inner()
+            .identifier
+            .parameters
+            .clone()
+            .into_iter()
+            .map(Into::into)
+            .collect()
+    }
+
+    pub fn qubits(&self) -> Vec<PyQubit> {
+        self.as_inner()
+            .identifier
+            .qubits
+            .clone()
+            .into_iter()
+            .map(Into::into)
+            .collect()
+    }
+
+    pub fn modifiers(&self) -> Vec<PyGateModifier> {
+        self.as_inner()
+            .identifier
+            .modifiers
+            .clone()
+            .into_iter()
+            .map(Into::into)
+            .collect()
+    }
+}
+
+py_wrap_data_struct! {
+    #[derive(Debug, PartialEq)]
+    #[pyo3(subclass)]
+    PyCalibrationIdentifier(CalibrationIdentifier) as "CalibrationIdentifier" {
+        modifiers: Vec<GateModifier> => Vec<PyGateModifier>,
+        name: String => Py<PyString>,
+        parameters: Vec<Expression> => Vec<PyExpression>,
+        qubits: Vec<Qubit> => Vec<PyQubit>
+    }
+}
+impl_repr!(PyCalibrationIdentifier);
+impl_to_quil!(PyCalibrationIdentifier);
+impl_copy_for_instruction!(PyCalibrationIdentifier);
+impl_eq!(PyCalibrationIdentifier);
+
+#[pymethods]
+impl PyCalibrationIdentifier {
     #[new]
     pub fn new(
         py: Python<'_>,
         name: &str,
         parameters: Vec<PyExpression>,
         qubits: Vec<PyQubit>,
-        instructions: Vec<PyInstruction>,
         modifiers: Vec<PyGateModifier>,
     ) -> PyResult<Self> {
         Ok(Self(
-            Calibration::new(
-                name,
+            CalibrationIdentifier::new(
+                name.to_string(),
+                Vec::<GateModifier>::py_try_from(py, &modifiers)?,
                 Vec::<Expression>::py_try_from(py, &parameters)?,
                 Vec::<Qubit>::py_try_from(py, &qubits)?,
-                Vec::<Instruction>::py_try_from(py, &instructions)?,
-                Vec::<GateModifier>::py_try_from(py, &modifiers)?,
             )
             .map_err(RustIdentifierValidationError::from)
             .map_err(RustIdentifierValidationError::to_py_err)?,
@@ -62,8 +128,7 @@ py_wrap_data_struct! {
     #[derive(Debug, PartialEq)]
     #[pyo3(subclass, module = "quil.instructions")]
     PyMeasureCalibrationDefinition(MeasureCalibrationDefinition) as "MeasureCalibrationDefinition" {
-        qubit: Option<Qubit> => Option<PyQubit>,
-        parameter: String => Py<PyString>,
+        identifier: MeasureCalibrationIdentifier => PyMeasureCalibrationIdentifier,
         instructions: Vec<Instruction> => Vec<PyInstruction>
     }
 }
@@ -76,17 +141,48 @@ impl_pickle_for_instruction!(PyMeasureCalibrationDefinition);
 #[pymethods]
 impl PyMeasureCalibrationDefinition {
     #[new]
-    #[pyo3(signature = (qubit, parameter, instructions))]
+    #[pyo3(signature = (identifier, instructions))]
     pub fn new(
         py: Python<'_>,
-        qubit: Option<PyQubit>,
-        parameter: String,
+        identifier: PyMeasureCalibrationIdentifier,
         instructions: Vec<PyInstruction>,
     ) -> PyResult<Self> {
         Ok(Self(MeasureCalibrationDefinition::new(
+            MeasureCalibrationIdentifier::py_try_from(py, &identifier)?,
+            Vec::<Instruction>::py_try_from(py, &instructions)?,
+        )))
+    }
+
+    pub fn qubit(&self) -> Option<PyQubit> {
+        self.as_inner().identifier.qubit.clone().map(Into::into)
+    }
+
+    pub fn parameter(&self) -> String {
+        self.as_inner().identifier.parameter.clone()
+    }
+}
+
+py_wrap_data_struct! {
+    #[derive(Debug, PartialEq)]
+    #[pyo3(subclass)]
+    PyMeasureCalibrationIdentifier(MeasureCalibrationIdentifier) as "MeasureCalibrationIdentifier" {
+        qubit: Option<Qubit> => Option<PyQubit>,
+        parameter: String => Py<PyString>
+    }
+}
+impl_repr!(PyMeasureCalibrationIdentifier);
+impl_to_quil!(PyMeasureCalibrationIdentifier);
+impl_copy_for_instruction!(PyMeasureCalibrationIdentifier);
+impl_eq!(PyMeasureCalibrationIdentifier);
+
+#[pymethods]
+impl PyMeasureCalibrationIdentifier {
+    #[new]
+    #[pyo3(signature = (qubit, parameter))]
+    pub fn new(py: Python<'_>, qubit: Option<PyQubit>, parameter: String) -> PyResult<Self> {
+        Ok(Self(MeasureCalibrationIdentifier::new(
             Option::<Qubit>::py_try_from(py, &qubit)?,
             parameter,
-            Vec::<Instruction>::py_try_from(py, &instructions)?,
         )))
     }
 }
diff --git a/quil-py/src/instruction/mod.rs b/quil-py/src/instruction/mod.rs
index e0ea02d1..594edba4 100644
--- a/quil-py/src/instruction/mod.rs
+++ b/quil-py/src/instruction/mod.rs
@@ -11,7 +11,10 @@ use rigetti_pyo3::{
 use crate::{impl_eq, impl_to_quil};
 
 pub use self::{
-    calibration::{PyCalibration, PyMeasureCalibrationDefinition},
+    calibration::{
+        PyCalibration, PyCalibrationIdentifier, PyMeasureCalibrationDefinition,
+        PyMeasureCalibrationIdentifier,
+    },
     circuit::PyCircuitDefinition,
     classical::{
         PyArithmetic, PyArithmeticOperand, PyArithmeticOperator, PyBinaryLogic, PyBinaryOperand,
@@ -169,8 +172,10 @@ create_init_submodule! {
         PyUnaryLogic,
         PyUnaryOperator,
         PyCalibration,
+        PyCalibrationIdentifier,
         PyCircuitDefinition,
         PyMeasureCalibrationDefinition,
+        PyMeasureCalibrationIdentifier,
         PyDeclaration,
         PyLoad,
         PyOffset,
diff --git a/quil-py/src/program/mod.rs b/quil-py/src/program/mod.rs
index 9df4ab7d..d9c744c7 100644
--- a/quil-py/src/program/mod.rs
+++ b/quil-py/src/program/mod.rs
@@ -37,6 +37,12 @@ use crate::{
 use self::{
     analysis::{PyBasicBlock, PyControlFlowGraph},
     scheduling::{PyScheduleSeconds, PyScheduleSecondsItem, PyTimeSpanSeconds},
+    source_map::{
+        PyCalibrationExpansion, PyCalibrationExpansionSourceMap,
+        PyCalibrationExpansionSourceMapEntry, PyCalibrationSource, PyMaybeCalibrationExpansion,
+        PyProgramCalibrationExpansion, PyProgramCalibrationExpansionSourceMap,
+        PyProgramCalibrationExpansionSourceMapEntry,
+    },
 };
 pub use self::{calibration::PyCalibrationSet, frame::PyFrameSet, memory::PyMemoryRegion};
 
@@ -45,6 +51,7 @@ mod calibration;
 mod frame;
 mod memory;
 mod scheduling;
+mod source_map;
 
 wrap_error!(ProgramError(quil_rs::program::ProgramError));
 py_wrap_error!(quil, ProgramError, PyProgramError, PyValueError);
@@ -87,6 +94,15 @@ impl PyProgram {
         ControlFlowGraphOwned::from(ControlFlowGraph::from(self.as_inner())).into()
     }
 
+    pub fn expand_calibrations_with_source_map(&self) -> PyResult<PyProgramCalibrationExpansion> {
+        let expansion = self
+            .as_inner()
+            .expand_calibrations_with_source_map()
+            .map_err(ProgramError::from)
+            .map_err(ProgramError::to_py_err)?;
+        Ok(expansion.into())
+    }
+
     #[getter]
     pub fn body_instructions<'a>(&self, py: Python<'a>) -> PyResult<&'a PyList> {
         Ok(PyList::new(
@@ -374,5 +390,23 @@ impl PyProgram {
 }
 
 create_init_submodule! {
-    classes: [ PyFrameSet, PyProgram, PyCalibrationSet, PyMemoryRegion, PyBasicBlock, PyControlFlowGraph, PyScheduleSeconds, PyScheduleSecondsItem, PyTimeSpanSeconds ],
+    classes: [
+        PyFrameSet,
+        PyProgram,
+        PyCalibrationExpansion,
+        PyCalibrationExpansionSourceMap,
+        PyCalibrationExpansionSourceMapEntry,
+        PyCalibrationSource,
+        PyMaybeCalibrationExpansion,
+        PyProgramCalibrationExpansion,
+        PyProgramCalibrationExpansionSourceMap,
+        PyProgramCalibrationExpansionSourceMapEntry,
+        PyCalibrationSet,
+        PyMemoryRegion,
+        PyBasicBlock,
+        PyControlFlowGraph,
+        PyScheduleSeconds,
+        PyScheduleSecondsItem,
+        PyTimeSpanSeconds
+    ],
 }
diff --git a/quil-py/src/program/source_map.rs b/quil-py/src/program/source_map.rs
new file mode 100644
index 00000000..14167226
--- /dev/null
+++ b/quil-py/src/program/source_map.rs
@@ -0,0 +1,359 @@
+use std::ops::Range;
+
+use pyo3::{
+    conversion, exceptions,
+    types::{PyModule, PyTuple},
+    IntoPy, Py, PyAny, PyResult, Python,
+};
+use quil_rs::program::{
+    CalibrationExpansion, CalibrationSource, InstructionIndex, MaybeCalibrationExpansion,
+    ProgramCalibrationExpansion, ProgramCalibrationExpansionSourceMap, SourceMap, SourceMapEntry,
+};
+use rigetti_pyo3::{
+    impl_as_mut_for_wrapper, impl_repr, py_wrap_type, py_wrap_union_enum, pyo3::pymethods,
+    PyTryFrom, PyWrapper, ToPython,
+};
+
+use crate::{
+    impl_eq,
+    instruction::{PyCalibrationIdentifier, PyMeasureCalibrationIdentifier},
+};
+
+use super::PyProgram;
+
+type CalibrationExpansionSourceMap = SourceMap<InstructionIndex, CalibrationExpansion>;
+type CalibrationExpansionSourceMapEntry = SourceMapEntry<InstructionIndex, CalibrationExpansion>;
+type ProgramCalibrationExpansionSourceMapEntry =
+    SourceMapEntry<InstructionIndex, MaybeCalibrationExpansion>;
+
+py_wrap_type! {
+    #[derive(Debug, PartialEq)]
+    PyCalibrationExpansion(CalibrationExpansion) as "CalibrationExpansion"
+}
+
+impl_repr!(PyCalibrationExpansion);
+impl_eq!(PyCalibrationExpansion);
+
+#[pymethods]
+impl PyCalibrationExpansion {
+    pub fn calibration_used(&self) -> PyCalibrationSource {
+        self.as_inner().calibration_used().into()
+    }
+
+    pub fn range<'py>(&self, py: Python<'py>) -> PyResult<&'py PyAny> {
+        let range = PyModule::import(py, "builtins")?.getattr("range")?;
+        let Range { start, end } = self.as_inner().range();
+        let tuple = PyTuple::new(py, [start.0, end.0]);
+        range.call1(tuple)?.extract()
+    }
+
+    pub fn expansions(&self) -> PyCalibrationExpansionSourceMap {
+        self.as_inner().expansions().into()
+    }
+}
+
+py_wrap_type! {
+    #[derive(Debug, PartialEq)]
+    PyCalibrationExpansionSourceMap(CalibrationExpansionSourceMap) as "CalibrationExpansionSourceMap"
+}
+
+impl_repr!(PyCalibrationExpansionSourceMap);
+impl_eq!(PyCalibrationExpansionSourceMap);
+
+#[pymethods]
+impl PyCalibrationExpansionSourceMap {
+    pub fn entries(&self) -> Vec<PyCalibrationExpansionSourceMapEntry> {
+        self.as_inner()
+            .entries()
+            .iter()
+            .map(|entry| entry.into())
+            .collect()
+    }
+
+    /// Given an instruction index within the resulting expansion, return the locations in the source
+    /// which were expanded to generate that instruction.
+    ///
+    /// This is `O(n)` where `n` is the number of first-level calibration expansions performed.
+    pub fn list_sources_for_target_index(&self, target_index: usize) -> Vec<usize> {
+        self.as_inner()
+            .list_sources(&InstructionIndex(target_index))
+            .into_iter()
+            .map(|index| index.0)
+            .collect()
+    }
+
+    /// Given a particular calibration (`DEFCAL` or `DEFCAL MEASURE`), return the locations in the source
+    /// program which were expanded using that calibration.
+    ///
+    /// This is `O(n)` where `n` is the number of first-level calibration expansions performed.
+    pub fn list_sources_for_calibration_used(
+        &self,
+        calibration_used: PyCalibrationSource,
+    ) -> Vec<usize> {
+        self.as_inner()
+            .list_sources(calibration_used.as_inner())
+            .into_iter()
+            .map(|index| index.0)
+            .collect()
+    }
+
+    /// Given a source index, return information about its expansion.
+    ///
+    /// This is `O(n)` where `n` is the number of first-level calibration expansions performed.
+    pub fn list_targets_for_source_index(
+        &self,
+        source_index: usize,
+    ) -> Vec<PyCalibrationExpansion> {
+        self.as_inner()
+            .list_targets(&InstructionIndex(source_index))
+            .into_iter()
+            .map(|expansion| expansion.into())
+            .collect()
+    }
+}
+
+py_wrap_type! {
+    #[derive(Debug, PartialEq)]
+    PyCalibrationExpansionSourceMapEntry(CalibrationExpansionSourceMapEntry) as "CalibrationExpansionSourceMapEntry"
+}
+
+impl_repr!(PyCalibrationExpansionSourceMapEntry);
+impl_eq!(PyCalibrationExpansionSourceMapEntry);
+
+#[pymethods]
+impl PyCalibrationExpansionSourceMapEntry {
+    pub fn source_location(&self) -> usize {
+        self.as_inner().source_location().0
+    }
+
+    pub fn target_location(&self) -> PyCalibrationExpansion {
+        self.as_inner().target_location().into()
+    }
+}
+
+py_wrap_union_enum! {
+    #[derive(Debug, PartialEq)]
+    PyCalibrationSource(CalibrationSource) as "CalibrationSource" {
+        calibration: Calibration => PyCalibrationIdentifier,
+        measure_calibration: MeasureCalibration => PyMeasureCalibrationIdentifier
+    }
+}
+
+impl_repr!(PyCalibrationSource);
+impl_eq!(PyCalibrationSource);
+
+// Note: this type is manually implemented below because there is no `Into` conversion from `InstructionIndex` to `usize`
+// This manual implementation follows the same API as this invocation otherwise would:
+// ```
+// py_wrap_union_enum! {
+//     #[derive(Debug, PartialEq)]
+//     PyMaybeCalibrationExpansion(MaybeCalibrationExpansion) as "MaybeCalibrationExpansion" {
+//         expanded: Expanded => PyCalibrationExpansion,
+//         unexpanded: Unexpanded => InstructionIndex => usize
+//     }
+// }
+// ```
+py_wrap_type! {
+    #[derive(Debug, PartialEq)]
+    PyMaybeCalibrationExpansion(MaybeCalibrationExpansion) as "MaybeCalibrationExpansion"
+}
+
+impl_as_mut_for_wrapper!(PyMaybeCalibrationExpansion);
+
+#[pymethods]
+impl PyMaybeCalibrationExpansion {
+    #[new]
+    pub fn new(py: Python, input: &PyAny) -> PyResult<Self> {
+        if let Ok(inner) = <_ as PyTryFrom<PyAny>>::py_try_from(py, input) {
+            let inner = &inner;
+            if let Ok(item) = PyTryFrom::py_try_from(py, inner) {
+                return Ok(Self::from(MaybeCalibrationExpansion::Expanded(item)));
+            }
+        }
+
+        if let Ok(inner) = <_ as PyTryFrom<PyAny>>::py_try_from(py, input) {
+            if let Ok(item) = PyTryFrom::<usize>::py_try_from(py, &inner) {
+                return Ok(Self::from(MaybeCalibrationExpansion::Unexpanded(
+                    InstructionIndex(item),
+                )));
+            }
+        }
+
+        Err(exceptions::PyValueError::new_err(format!(
+            "could not create {} from {}",
+            stringify!($name),
+            input.repr()?
+        )))
+    }
+
+    #[allow(unreachable_code, unreachable_patterns)]
+    pub fn inner(&self, py: Python) -> PyResult<Py<PyAny>> {
+        match &self.0 {
+            MaybeCalibrationExpansion::Expanded(inner) => Ok(
+                conversion::IntoPy::<Py<PyAny>>::into_py(ToPython::to_python(&inner, py)?, py),
+            ),
+            MaybeCalibrationExpansion::Unexpanded(inner) => Ok(inner.0.into_py(py)),
+            _ => {
+                use exceptions::PyRuntimeError;
+                Err(PyRuntimeError::new_err(
+                    "Enum variant has no inner data or is unimplemented",
+                ))
+            }
+        }
+    }
+
+    pub fn as_expanded(&self) -> Option<PyCalibrationExpansion> {
+        match &self.0 {
+            MaybeCalibrationExpansion::Expanded(inner) => {
+                Some(PyCalibrationExpansion(inner.clone()))
+            }
+            _ => None,
+        }
+    }
+
+    pub fn as_unexpanded(&self) -> Option<usize> {
+        match &self.0 {
+            MaybeCalibrationExpansion::Unexpanded(inner) => Some(inner.0),
+            _ => None,
+        }
+    }
+
+    #[staticmethod]
+    pub fn from_expanded(inner: PyCalibrationExpansion) -> Self {
+        Self(MaybeCalibrationExpansion::Expanded(inner.into_inner()))
+    }
+
+    #[staticmethod]
+    pub fn from_unexpanded(inner: usize) -> Self {
+        Self(MaybeCalibrationExpansion::Unexpanded(InstructionIndex(
+            inner,
+        )))
+    }
+
+    pub fn is_expanded(&self) -> bool {
+        matches!(self.0, MaybeCalibrationExpansion::Expanded(_))
+    }
+
+    pub fn is_unexpanded(&self) -> bool {
+        matches!(self.0, MaybeCalibrationExpansion::Unexpanded(_))
+    }
+
+    pub fn to_expanded(&self) -> PyResult<PyCalibrationExpansion> {
+        match &self.0 {
+            MaybeCalibrationExpansion::Expanded(inner) => Ok(PyCalibrationExpansion(inner.clone())),
+            _ => Err(pyo3::exceptions::PyValueError::new_err(
+                "expected self to be an Expanded variant",
+            )),
+        }
+    }
+
+    pub fn to_unexpanded(&self) -> PyResult<usize> {
+        match &self.0 {
+            MaybeCalibrationExpansion::Unexpanded(inner) => Ok(inner.0),
+            _ => Err(pyo3::exceptions::PyValueError::new_err(
+                "expected self to be an Unexpanded variant",
+            )),
+        }
+    }
+}
+
+impl_repr!(PyMaybeCalibrationExpansion);
+impl_eq!(PyMaybeCalibrationExpansion);
+
+py_wrap_type! {
+    #[derive(Debug, PartialEq)]
+    PyProgramCalibrationExpansion(ProgramCalibrationExpansion) as "ProgramCalibrationExpansion"
+}
+
+impl_repr!(PyProgramCalibrationExpansion);
+impl_eq!(PyProgramCalibrationExpansion);
+
+#[pymethods]
+impl PyProgramCalibrationExpansion {
+    pub fn program(&self) -> PyProgram {
+        self.as_inner().program().into()
+    }
+
+    pub fn source_map(&self) -> PyProgramCalibrationExpansionSourceMap {
+        self.as_inner().source_map().clone().into()
+    }
+}
+
+py_wrap_type! {
+    #[derive(Debug, PartialEq)]
+    PyProgramCalibrationExpansionSourceMap(ProgramCalibrationExpansionSourceMap) as "ProgramCalibrationExpansionSourceMap"
+}
+
+impl_repr!(PyProgramCalibrationExpansionSourceMap);
+impl_eq!(PyProgramCalibrationExpansionSourceMap);
+
+#[pymethods]
+impl PyProgramCalibrationExpansionSourceMap {
+    pub fn entries(&self) -> Vec<PyProgramCalibrationExpansionSourceMapEntry> {
+        self.as_inner()
+            .entries()
+            .iter()
+            .map(|entry| entry.into())
+            .collect()
+    }
+
+    /// Given an instruction index within the resulting expansion, return the locations in the source
+    /// which were expanded to generate that instruction.
+    ///
+    /// This is `O(n)` where `n` is the number of source instructions.
+    pub fn list_sources_for_target_index(&self, target_index: usize) -> Vec<usize> {
+        self.as_inner()
+            .list_sources(&InstructionIndex(target_index))
+            .into_iter()
+            .map(|index| index.0)
+            .collect()
+    }
+
+    /// Given a particular calibration (`DEFCAL` or `DEFCAL MEASURE`), return the locations in the source
+    /// program which were expanded using that calibration.
+    ///
+    /// This is `O(n)` where `n` is the number of source instructions.
+    pub fn list_sources_for_calibration_used(
+        &self,
+        calibration_used: PyCalibrationSource,
+    ) -> Vec<usize> {
+        self.as_inner()
+            .list_sources(calibration_used.as_inner())
+            .into_iter()
+            .map(|index| index.0)
+            .collect()
+    }
+
+    /// Given a source index, return information about its expansion.
+    ///
+    /// This is `O(n)` where `n` is the number of source instructions.
+    pub fn list_targets_for_source_index(
+        &self,
+        source_index: usize,
+    ) -> Vec<PyMaybeCalibrationExpansion> {
+        self.as_inner()
+            .list_targets(&InstructionIndex(source_index))
+            .into_iter()
+            .map(|expansion| expansion.into())
+            .collect()
+    }
+}
+
+py_wrap_type! {
+    #[derive(Debug, PartialEq)]
+    PyProgramCalibrationExpansionSourceMapEntry(ProgramCalibrationExpansionSourceMapEntry) as "ProgramCalibrationExpansionSourceMapEntry"
+}
+
+impl_repr!(PyProgramCalibrationExpansionSourceMapEntry);
+impl_eq!(PyProgramCalibrationExpansionSourceMapEntry);
+
+#[pymethods]
+impl PyProgramCalibrationExpansionSourceMapEntry {
+    pub fn source_location(&self) -> usize {
+        self.as_inner().source_location().0
+    }
+
+    pub fn target_location(&self) -> PyMaybeCalibrationExpansion {
+        self.as_inner().target_location().clone().into()
+    }
+}
diff --git a/quil-rs/Cargo.toml b/quil-rs/Cargo.toml
index c2022b9e..4f77ada9 100644
--- a/quil-rs/Cargo.toml
+++ b/quil-rs/Cargo.toml
@@ -32,6 +32,7 @@ clap = { version = "4.3.19", features = ["derive", "string"] }
 criterion = { version = "0.5.1", features = ["html_reports"] }
 insta = "1.37.0"
 petgraph = "0.6.2"
+pretty_assertions = "1.4.0"
 proptest = "1.0.0"
 proptest-derive = "0.3.0"
 rand = "0.8.5"
diff --git a/quil-rs/src/instruction/calibration.rs b/quil-rs/src/instruction/calibration.rs
index ee75d4d6..67432ffa 100644
--- a/quil-rs/src/instruction/calibration.rs
+++ b/quil-rs/src/instruction/calibration.rs
@@ -7,7 +7,7 @@ use crate::{
     validation::identifier::{validate_identifier, IdentifierValidationError},
 };
 
-use super::write_qubit_parameters;
+use super::{write_qubit_parameters, Gate};
 
 pub trait CalibrationSignature {
     type Signature<'a>
@@ -20,46 +20,42 @@ pub trait CalibrationSignature {
 
 #[derive(Clone, Debug, Default, PartialEq)]
 pub struct Calibration {
+    pub identifier: CalibrationIdentifier,
     pub instructions: Vec<Instruction>,
-    pub modifiers: Vec<GateModifier>,
-    pub name: String,
-    pub parameters: Vec<Expression>,
-    pub qubits: Vec<Qubit>,
 }
 
 impl Calibration {
     /// Builds a new calibration definition.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the given name isn't a valid Quil identifier.
     pub fn new(
-        name: &str,
-        parameters: Vec<Expression>,
-        qubits: Vec<Qubit>,
+        identifier: CalibrationIdentifier,
         instructions: Vec<Instruction>,
-        modifiers: Vec<GateModifier>,
     ) -> Result<Self, IdentifierValidationError> {
-        validate_identifier(name)?;
         Ok(Self {
+            identifier,
             instructions,
-            modifiers,
-            name: name.to_string(),
-            parameters,
-            qubits,
         })
     }
 }
 
+impl CalibrationSignature for Calibration {
+    type Signature<'a> = (&'a str, &'a [Expression], &'a [Qubit]);
+
+    fn signature(&self) -> Self::Signature<'_> {
+        self.identifier.signature()
+    }
+
+    fn has_signature(&self, signature: &Self::Signature<'_>) -> bool {
+        self.identifier.has_signature(signature)
+    }
+}
+
 impl Quil for Calibration {
     fn write(
         &self,
         f: &mut impl std::fmt::Write,
         fall_back_to_debug: bool,
     ) -> crate::quil::ToQuilResult<()> {
-        write!(f, "DEFCAL {}", self.name)?;
-        write_expression_parameter_string(f, fall_back_to_debug, &self.parameters)?;
-        write_qubit_parameters(f, fall_back_to_debug, &self.qubits)?;
+        self.identifier.write(f, fall_back_to_debug)?;
         write!(f, ":")?;
         for instruction in &self.instructions {
             write!(f, "\n{INDENT}")?;
@@ -69,7 +65,99 @@ impl Quil for Calibration {
     }
 }
 
-impl CalibrationSignature for Calibration {
+/// Unique identifier for a calibration definition within a program
+#[derive(Clone, Debug, Default, PartialEq)]
+pub struct CalibrationIdentifier {
+    /// The modifiers applied to the gate
+    pub modifiers: Vec<GateModifier>,
+
+    /// The name of the gate
+    pub name: String,
+
+    /// The parameters of the gate - these are the variables in the calibration definition
+    pub parameters: Vec<Expression>,
+
+    /// The qubits on which the gate is applied
+    pub qubits: Vec<Qubit>,
+}
+
+impl CalibrationIdentifier {
+    /// Builds a new calibration identifier.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the given name isn't a valid Quil identifier.
+    pub fn new(
+        name: String,
+        modifiers: Vec<GateModifier>,
+        parameters: Vec<Expression>,
+        qubits: Vec<Qubit>,
+    ) -> Result<Self, IdentifierValidationError> {
+        validate_identifier(name.as_str())?;
+        Ok(Self {
+            modifiers,
+            name,
+            parameters,
+            qubits,
+        })
+    }
+
+    pub fn matches(&self, gate: &Gate) -> bool {
+        // Filter out non-matching calibrations: check rules 1-4
+        if self.name != gate.name
+            || self.modifiers != gate.modifiers
+            || self.parameters.len() != gate.parameters.len()
+            || self.qubits.len() != gate.qubits.len()
+        {
+            return false;
+        }
+
+        let fixed_qubits_match = self
+            .qubits
+            .iter()
+            .enumerate()
+            .all(|(calibration_index, _)| {
+                match (
+                    &self.qubits[calibration_index],
+                    &gate.qubits[calibration_index],
+                ) {
+                    // Placeholders never match
+                    (Qubit::Placeholder(_), _) | (_, Qubit::Placeholder(_)) => false,
+                    // If they're both fixed, test if they're fixed to the same qubit
+                    (Qubit::Fixed(calibration_fixed_qubit), Qubit::Fixed(gate_fixed_qubit)) => {
+                        calibration_fixed_qubit == gate_fixed_qubit
+                    }
+                    // If the calibration is variable, it matches any fixed qubit
+                    (Qubit::Variable(_), _) => true,
+                    // If the calibration is fixed, but the gate's qubit is variable, it's not a match
+                    (Qubit::Fixed(_), _) => false,
+                }
+            });
+        if !fixed_qubits_match {
+            return false;
+        }
+
+        let fixed_parameters_match =
+            self.parameters
+                .iter()
+                .enumerate()
+                .all(|(calibration_index, _)| {
+                    let calibration_parameters =
+                        self.parameters[calibration_index].clone().into_simplified();
+                    let gate_parameters =
+                        gate.parameters[calibration_index].clone().into_simplified();
+                    match (calibration_parameters, gate_parameters) {
+                        // If the calibration is variable, it matches any fixed qubit
+                        (Expression::Variable(_), _) => true,
+                        // If the calibration is fixed, but the gate's qubit is variable, it's not a match
+                        (calib, gate) => calib == gate,
+                    }
+                });
+        fixed_parameters_match
+    }
+}
+
+impl CalibrationSignature for CalibrationIdentifier {
     type Signature<'a> = (&'a str, &'a [Expression], &'a [Qubit]);
 
     fn signature(&self) -> Self::Signature<'_> {
@@ -86,18 +174,29 @@ impl CalibrationSignature for Calibration {
     }
 }
 
+impl Quil for CalibrationIdentifier {
+    fn write(
+        &self,
+        f: &mut impl std::fmt::Write,
+        fall_back_to_debug: bool,
+    ) -> crate::quil::ToQuilResult<()> {
+        write!(f, "DEFCAL {}", self.name)?;
+        write_expression_parameter_string(f, fall_back_to_debug, &self.parameters)?;
+        write_qubit_parameters(f, fall_back_to_debug, &self.qubits)?;
+        Ok(())
+    }
+}
+
 #[derive(Clone, Debug, PartialEq)]
 pub struct MeasureCalibrationDefinition {
-    pub qubit: Option<Qubit>,
-    pub parameter: String,
+    pub identifier: MeasureCalibrationIdentifier,
     pub instructions: Vec<Instruction>,
 }
 
 impl MeasureCalibrationDefinition {
-    pub fn new(qubit: Option<Qubit>, parameter: String, instructions: Vec<Instruction>) -> Self {
+    pub fn new(identifier: MeasureCalibrationIdentifier, instructions: Vec<Instruction>) -> Self {
         Self {
-            qubit,
-            parameter,
+            identifier,
             instructions,
         }
     }
@@ -106,6 +205,49 @@ impl MeasureCalibrationDefinition {
 impl CalibrationSignature for MeasureCalibrationDefinition {
     type Signature<'a> = (Option<&'a Qubit>, &'a str);
 
+    fn signature(&self) -> Self::Signature<'_> {
+        self.identifier.signature()
+    }
+
+    fn has_signature(&self, signature: &Self::Signature<'_>) -> bool {
+        self.identifier.has_signature(signature)
+    }
+}
+
+impl Quil for MeasureCalibrationDefinition {
+    fn write(
+        &self,
+        f: &mut impl std::fmt::Write,
+        fall_back_to_debug: bool,
+    ) -> crate::quil::ToQuilResult<()> {
+        self.identifier.write(f, fall_back_to_debug)?;
+        writeln!(f, ":")?;
+
+        write_instruction_block(f, fall_back_to_debug, &self.instructions)?;
+        writeln!(f)?;
+        Ok(())
+    }
+}
+
+/// A unique identifier for a measurement calibration definition within a program
+#[derive(Clone, Debug, Default, PartialEq)]
+pub struct MeasureCalibrationIdentifier {
+    /// The qubit which is the target of measurement, if any
+    pub qubit: Option<Qubit>,
+
+    /// The memory region name to which the measurement result is written
+    pub parameter: String,
+}
+
+impl MeasureCalibrationIdentifier {
+    pub fn new(qubit: Option<Qubit>, parameter: String) -> Self {
+        Self { qubit, parameter }
+    }
+}
+
+impl CalibrationSignature for MeasureCalibrationIdentifier {
+    type Signature<'a> = (Option<&'a Qubit>, &'a str);
+
     fn signature(&self) -> Self::Signature<'_> {
         (self.qubit.as_ref(), self.parameter.as_str())
     }
@@ -116,7 +258,7 @@ impl CalibrationSignature for MeasureCalibrationDefinition {
     }
 }
 
-impl Quil for MeasureCalibrationDefinition {
+impl Quil for MeasureCalibrationIdentifier {
     fn write(
         &self,
         f: &mut impl std::fmt::Write,
@@ -127,11 +269,7 @@ impl Quil for MeasureCalibrationDefinition {
             write!(f, " ")?;
             qubit.write(f, fall_back_to_debug)?;
         }
-
-        writeln!(f, " {}:", self.parameter,)?;
-
-        write_instruction_block(f, fall_back_to_debug, &self.instructions)?;
-        writeln!(f)?;
+        write!(f, " {}", self.parameter,)?;
         Ok(())
     }
 }
@@ -140,6 +278,7 @@ impl Quil for MeasureCalibrationDefinition {
 mod test_measure_calibration_definition {
     use super::MeasureCalibrationDefinition;
     use crate::expression::Expression;
+    use crate::instruction::calibration::MeasureCalibrationIdentifier;
     use crate::instruction::{Gate, Instruction, Qubit};
     use crate::quil::Quil;
     use insta::assert_snapshot;
@@ -149,8 +288,10 @@ mod test_measure_calibration_definition {
     #[case(
         "With Fixed Qubit",
         MeasureCalibrationDefinition {
-            qubit: Some(Qubit::Fixed(0)),
-            parameter: "theta".to_string(),
+            identifier: MeasureCalibrationIdentifier {
+                qubit: Some(Qubit::Fixed(0)),
+                parameter: "theta".to_string(),
+            },
             instructions: vec![Instruction::Gate(Gate {
                 name: "X".to_string(),
                 parameters: vec![Expression::Variable("theta".to_string())],
@@ -162,8 +303,10 @@ mod test_measure_calibration_definition {
     #[case(
         "With Variable Qubit",
         MeasureCalibrationDefinition {
-            qubit: Some(Qubit::Variable("q".to_string())),
-            parameter: "theta".to_string(),
+            identifier: MeasureCalibrationIdentifier {
+                qubit: Some(Qubit::Variable("q".to_string())),
+                parameter: "theta".to_string(),
+            },
             instructions: vec![Instruction::Gate(Gate {
                 name: "X".to_string(),
                 parameters: vec![Expression::Variable("theta".to_string())],
diff --git a/quil-rs/src/instruction/classical.rs b/quil-rs/src/instruction/classical.rs
index e2c31d06..fc0dbc68 100644
--- a/quil-rs/src/instruction/classical.rs
+++ b/quil-rs/src/instruction/classical.rs
@@ -68,6 +68,12 @@ impl Quil for ArithmeticOperand {
     }
 }
 
+impl From<MemoryReference> for ArithmeticOperand {
+    fn from(memory_reference: MemoryReference) -> Self {
+        ArithmeticOperand::MemoryReference(memory_reference)
+    }
+}
+
 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
 pub enum ArithmeticOperator {
     Add,
diff --git a/quil-rs/src/instruction/mod.rs b/quil-rs/src/instruction/mod.rs
index 1914b666..67583f8f 100644
--- a/quil-rs/src/instruction/mod.rs
+++ b/quil-rs/src/instruction/mod.rs
@@ -41,7 +41,10 @@ mod reset;
 mod timing;
 mod waveform;
 
-pub use self::calibration::{Calibration, CalibrationSignature, MeasureCalibrationDefinition};
+pub use self::calibration::{
+    Calibration, CalibrationIdentifier, CalibrationSignature, MeasureCalibrationDefinition,
+    MeasureCalibrationIdentifier,
+};
 pub use self::circuit::CircuitDefinition;
 pub use self::classical::{
     Arithmetic, ArithmeticOperand, ArithmeticOperator, BinaryLogic, BinaryOperand, BinaryOperator,
@@ -407,7 +410,10 @@ impl Instruction {
     /// ```
     pub fn apply_to_expressions(&mut self, mut closure: impl FnMut(&mut Expression)) {
         match self {
-            Instruction::CalibrationDefinition(Calibration { parameters, .. })
+            Instruction::CalibrationDefinition(Calibration {
+                identifier: CalibrationIdentifier { parameters, .. },
+                ..
+            })
             | Instruction::Gate(Gate { parameters, .. }) => {
                 parameters.iter_mut().for_each(closure);
             }
@@ -592,6 +598,7 @@ impl Instruction {
         match self {
             Instruction::Gate(gate) => gate.qubits.iter_mut().collect(),
             Instruction::CalibrationDefinition(calibration) => calibration
+                .identifier
                 .qubits
                 .iter_mut()
                 .chain(
@@ -602,6 +609,7 @@ impl Instruction {
                 )
                 .collect(),
             Instruction::MeasureCalibrationDefinition(measurement) => measurement
+                .identifier
                 .qubit
                 .iter_mut()
                 .chain(
diff --git a/quil-rs/src/parser/command.rs b/quil-rs/src/parser/command.rs
index 4a943157..0234fd44 100644
--- a/quil-rs/src/parser/command.rs
+++ b/quil-rs/src/parser/command.rs
@@ -5,12 +5,13 @@ use nom::sequence::{delimited, pair, preceded, tuple};
 
 use crate::expression::Expression;
 use crate::instruction::{
-    Arithmetic, ArithmeticOperator, BinaryLogic, BinaryOperator, Calibration, Call, Capture,
-    CircuitDefinition, Comparison, ComparisonOperator, Convert, Declaration, Delay, Exchange,
-    Fence, FrameDefinition, GateDefinition, GateSpecification, GateType, Include, Instruction,
-    Jump, JumpUnless, JumpWhen, Label, Load, MeasureCalibrationDefinition, Measurement, Move,
-    PauliSum, Pragma, PragmaArgument, Pulse, Qubit, RawCapture, Reset, SetFrequency, SetPhase,
-    SetScale, ShiftFrequency, ShiftPhase, Store, SwapPhases, Target, UnaryLogic, UnaryOperator,
+    Arithmetic, ArithmeticOperator, BinaryLogic, BinaryOperator, Calibration,
+    CalibrationIdentifier, Call, Capture, CircuitDefinition, Comparison, ComparisonOperator,
+    Convert, Declaration, Delay, Exchange, Fence, FrameDefinition, GateDefinition,
+    GateSpecification, GateType, Include, Instruction, Jump, JumpUnless, JumpWhen, Label, Load,
+    MeasureCalibrationDefinition, MeasureCalibrationIdentifier, Measurement, Move, PauliSum,
+    Pragma, PragmaArgument, Pulse, Qubit, RawCapture, Reset, SetFrequency, SetPhase, SetScale,
+    ShiftFrequency, ShiftPhase, Store, SwapPhases, Target, UnaryLogic, UnaryOperator,
     UnresolvedCallArgument, ValidationError, Waveform, WaveformDefinition,
 };
 
@@ -220,11 +221,13 @@ pub(crate) fn parse_defcal_gate<'a>(
     Ok((
         input,
         Instruction::CalibrationDefinition(Calibration {
-            name,
-            parameters,
-            qubits,
+            identifier: CalibrationIdentifier {
+                name,
+                parameters,
+                qubits,
+                modifiers,
+            },
             instructions,
-            modifiers,
         }),
     ))
 }
@@ -243,8 +246,10 @@ pub(crate) fn parse_defcal_measure<'a>(
     Ok((
         input,
         Instruction::MeasureCalibrationDefinition(MeasureCalibrationDefinition {
-            qubit,
-            parameter: destination,
+            identifier: MeasureCalibrationIdentifier {
+                qubit,
+                parameter: destination,
+            },
             instructions,
         }),
     ))
diff --git a/quil-rs/src/parser/instruction.rs b/quil-rs/src/parser/instruction.rs
index d9900d92..313611b9 100644
--- a/quil-rs/src/parser/instruction.rs
+++ b/quil-rs/src/parser/instruction.rs
@@ -160,12 +160,12 @@ mod tests {
     };
     use crate::instruction::{
         Arithmetic, ArithmeticOperand, ArithmeticOperator, AttributeValue, BinaryLogic,
-        BinaryOperand, BinaryOperator, Calibration, Capture, Comparison, ComparisonOperand,
-        ComparisonOperator, Convert, FrameDefinition, FrameIdentifier, Gate, GateDefinition,
-        GateSpecification, Include, Instruction, Jump, JumpWhen, Label, MemoryReference, Move,
-        Pulse, Qubit, RawCapture, Reset, SetFrequency, SetPhase, SetScale, ShiftFrequency,
-        ShiftPhase, SwapPhases, Target, UnaryLogic, UnaryOperator, Waveform, WaveformDefinition,
-        WaveformInvocation, WaveformParameters,
+        BinaryOperand, BinaryOperator, Calibration, CalibrationIdentifier, Capture, Comparison,
+        ComparisonOperand, ComparisonOperator, Convert, FrameDefinition, FrameIdentifier, Gate,
+        GateDefinition, GateSpecification, Include, Instruction, Jump, JumpWhen, Label,
+        MemoryReference, Move, Pulse, Qubit, RawCapture, Reset, SetFrequency, SetPhase, SetScale,
+        ShiftFrequency, ShiftPhase, SwapPhases, Target, UnaryLogic, UnaryOperator, Waveform,
+        WaveformDefinition, WaveformInvocation, WaveformParameters,
     };
     use crate::parser::common::tests::KITCHEN_SINK_QUIL;
     use crate::parser::lexer::lex;
@@ -555,10 +555,12 @@ mod tests {
         parse_instructions,
         "DEFCAL RX(%theta) %qubit:\n\tPULSE 1 \"xy\" custom_waveform(a: 1)",
         vec![Instruction::CalibrationDefinition(Calibration {
-            name: "RX".to_owned(),
-            parameters: vec![Expression::Variable("theta".to_owned())],
-            qubits: vec![Qubit::Variable("qubit".to_owned())],
-            modifiers: vec![],
+            identifier: CalibrationIdentifier {
+                name: "RX".to_owned(),
+                parameters: vec![Expression::Variable("theta".to_owned())],
+                qubits: vec![Qubit::Variable("qubit".to_owned())],
+                modifiers: vec![],
+            },
             instructions: vec![Instruction::Pulse(Pulse {
                 blocking: true,
                 frame: FrameIdentifier {
diff --git a/quil-rs/src/program/calibration.rs b/quil-rs/src/program/calibration.rs
index 2e0bccbe..57f48c9a 100644
--- a/quil-rs/src/program/calibration.rs
+++ b/quil-rs/src/program/calibration.rs
@@ -13,10 +13,12 @@
 // limitations under the License.
 
 use std::collections::HashMap;
+use std::ops::Range;
 
 use itertools::FoldWhile::{Continue, Done};
 use itertools::Itertools;
 
+use crate::instruction::{CalibrationIdentifier, MeasureCalibrationIdentifier};
 use crate::quil::Quil;
 use crate::{
     expression::Expression,
@@ -27,7 +29,8 @@ use crate::{
     },
 };
 
-use super::{CalibrationSet, ProgramError};
+use super::source_map::{SourceMap, SourceMapEntry, SourceMapIndexable};
+use super::{CalibrationSet, InstructionIndex, ProgramError};
 
 /// A collection of Quil calibrations (`DEFCAL` instructions) with utility methods.
 #[derive(Clone, Debug, Default, PartialEq)]
@@ -46,6 +49,7 @@ impl<'a> MatchedCalibration<'a> {
         Self {
             calibration,
             fixed_qubit_count: calibration
+                .identifier
                 .qubits
                 .iter()
                 .filter(|q| match q {
@@ -57,6 +61,136 @@ impl<'a> MatchedCalibration<'a> {
     }
 }
 
+/// The product of expanding an instruction using a calibration
+#[derive(Clone, Debug, PartialEq)]
+pub struct CalibrationExpansionOutput {
+    /// The new instructions resulting from the expansion
+    pub new_instructions: Vec<Instruction>,
+
+    /// Details about the expansion process
+    pub detail: CalibrationExpansion,
+}
+
+/// Details about the expansion of a calibration
+#[derive(Clone, Debug, PartialEq)]
+pub struct CalibrationExpansion {
+    /// The calibration used to expand the instruction
+    pub(crate) calibration_used: CalibrationSource,
+
+    /// The target instruction indices produced by the expansion
+    pub(crate) range: Range<InstructionIndex>,
+
+    /// A map of source locations to the expansions they produced
+    pub(crate) expansions: SourceMap<InstructionIndex, CalibrationExpansion>,
+}
+
+impl CalibrationExpansion {
+    /// Remove the given target index from all entries, recursively.
+    ///
+    /// This is to be used when the given index is removed from the target program
+    /// in the process of calibration expansion (for example, a `DECLARE`).
+    pub(crate) fn remove_target_index(&mut self, target_index: InstructionIndex) {
+        // Adjust the start of the range if the target index is before the range
+        if self.range.start >= target_index {
+            self.range.start = self.range.start.map(|v| v.saturating_sub(1));
+        }
+
+        // Adjust the end of the range if the target index is before the end of the range
+        if self.range.end > target_index {
+            self.range.end = self.range.end.map(|v| v.saturating_sub(1));
+        }
+
+        // Then walk through all entries expanded for this calibration and remove the
+        // index as well. This is needed when a recursively-expanded instruction contains
+        // an instruction which is excised from the overall calibration.
+        if let Some(target_within_expansion) = target_index.0.checked_sub(self.range.start.0) {
+            self.expansions.entries.retain_mut(
+                |entry: &mut SourceMapEntry<InstructionIndex, CalibrationExpansion>| {
+                    entry
+                        .target_location
+                        .remove_target_index(InstructionIndex(target_within_expansion));
+
+                    !entry.target_location.range.is_empty()
+                },
+            );
+        }
+    }
+
+    pub fn calibration_used(&self) -> &CalibrationSource {
+        &self.calibration_used
+    }
+
+    pub fn range(&self) -> &Range<InstructionIndex> {
+        &self.range
+    }
+
+    pub fn expansions(&self) -> &SourceMap<InstructionIndex, CalibrationExpansion> {
+        &self.expansions
+    }
+}
+
+impl SourceMapIndexable<InstructionIndex> for CalibrationExpansion {
+    fn intersects(&self, other: &InstructionIndex) -> bool {
+        self.range.contains(other)
+    }
+}
+
+impl SourceMapIndexable<CalibrationSource> for CalibrationExpansion {
+    fn intersects(&self, other: &CalibrationSource) -> bool {
+        self.calibration_used() == other
+    }
+}
+
+/// The result of an attempt to expand an instruction within a [`Program`]
+#[derive(Clone, Debug, PartialEq)]
+pub enum MaybeCalibrationExpansion {
+    /// The instruction was expanded into others
+    Expanded(CalibrationExpansion),
+
+    /// The instruction was not expanded, but was simply copied over into the target program at the given instruction index
+    Unexpanded(InstructionIndex),
+}
+
+impl SourceMapIndexable<InstructionIndex> for MaybeCalibrationExpansion {
+    fn intersects(&self, other: &InstructionIndex) -> bool {
+        match self {
+            MaybeCalibrationExpansion::Expanded(expansion) => expansion.intersects(other),
+            MaybeCalibrationExpansion::Unexpanded(index) => index == other,
+        }
+    }
+}
+
+impl SourceMapIndexable<CalibrationSource> for MaybeCalibrationExpansion {
+    fn intersects(&self, other: &CalibrationSource) -> bool {
+        match self {
+            MaybeCalibrationExpansion::Expanded(expansion) => expansion.intersects(other),
+            MaybeCalibrationExpansion::Unexpanded(_) => false,
+        }
+    }
+}
+
+/// A source of a calibration, either a [`Calibration`] or a [`MeasureCalibrationDefinition`]
+#[derive(Clone, Debug, PartialEq)]
+pub enum CalibrationSource {
+    /// Describes a `DEFCAL` instruction
+    Calibration(CalibrationIdentifier),
+
+    /// Describes a `DEFCAL MEASURE` instruction
+    MeasureCalibration(MeasureCalibrationIdentifier),
+}
+
+impl From<CalibrationIdentifier> for CalibrationSource {
+    fn from(value: CalibrationIdentifier) -> Self {
+        Self::Calibration(value)
+    }
+}
+
+impl From<MeasureCalibrationIdentifier> for CalibrationSource {
+    fn from(value: MeasureCalibrationIdentifier) -> Self {
+        Self::MeasureCalibration(value)
+    }
+}
+
 impl Calibrations {
     /// Return a vector containing a reference to all [`Calibration`]s in the set.
     pub fn calibrations(&self) -> Vec<&Calibration> {
@@ -82,22 +216,58 @@ impl Calibrations {
     /// Given an instruction, return the instructions to which it is expanded if there is a match.
     /// Recursively calibrate instructions, returning an error if a calibration directly or indirectly
     /// expands into itself.
+    ///
+    /// Return only the expanded instructions; for more information about the expansion process,
+    /// see [`Self::expand_with_detail`].
     pub fn expand(
         &self,
         instruction: &Instruction,
         previous_calibrations: &[Instruction],
     ) -> Result<Option<Vec<Instruction>>, ProgramError> {
+        self.expand_inner(instruction, previous_calibrations, false)
+            .map(|expansion| expansion.map(|expansion| expansion.new_instructions))
+    }
+
+    /// Given an instruction, return the instructions to which it is expanded if there is a match.
+    /// Recursively calibrate instructions, returning an error if a calibration directly or indirectly
+    /// expands into itself.
+    ///
+    /// Also return information about the expansion.
+    pub fn expand_with_detail(
+        &self,
+        instruction: &Instruction,
+        previous_calibrations: &[Instruction],
+    ) -> Result<Option<CalibrationExpansionOutput>, ProgramError> {
+        self.expand_inner(instruction, previous_calibrations, true)
+    }
+
+    /// Expand an instruction, returning an error if a calibration directly or indirectly
+    /// expands into itself. Return `None` if there are no matching calibrations in `self`.
+    ///
+    /// # Arguments
+    ///
+    /// * `instruction` - The instruction to expand.
+    /// * `previous_calibrations` - The calibrations that were invoked to yield this current instruction.
+    /// * `build_source_map` - Whether to build a source map of the expansion.
+    fn expand_inner(
+        &self,
+        instruction: &Instruction,
+        previous_calibrations: &[Instruction],
+        build_source_map: bool,
+    ) -> Result<Option<CalibrationExpansionOutput>, ProgramError> {
         if previous_calibrations.contains(instruction) {
             return Err(ProgramError::RecursiveCalibration(instruction.clone()));
         }
-        let expanded_once_instructions = match instruction {
+        let expansion_result = match instruction {
             Instruction::Gate(gate) => {
                 let matching_calibration = self.get_match_for_gate(gate);
 
                 match matching_calibration {
                     Some(calibration) => {
                         let mut qubit_expansions: HashMap<&String, Qubit> = HashMap::new();
-                        for (index, calibration_qubit) in calibration.qubits.iter().enumerate() {
+                        for (index, calibration_qubit) in
+                            calibration.identifier.qubits.iter().enumerate()
+                        {
                             if let Qubit::Variable(identifier) = calibration_qubit {
                                 qubit_expansions.insert(identifier, gate.qubits[index].clone());
                             }
@@ -106,6 +276,7 @@ impl Calibrations {
                         // Variables used within the calibration's definition should be replaced with the actual expressions used by the gate.
                         // That is, `DEFCAL RX(%theta): ...` should have `%theta` replaced by `pi` throughout if it's used to expand `RX(pi)`.
                         let variable_expansions: HashMap<String, Expression> = calibration
+                            .identifier
                             .parameters
                             .iter()
                             .zip(gate.parameters.iter())
@@ -180,7 +351,10 @@ impl Calibrations {
                             })
                         }
 
-                        Some(instructions)
+                        Some((
+                            instructions,
+                            CalibrationSource::Calibration(calibration.identifier.clone()),
+                        ))
                     }
                     None => None,
                 }
@@ -195,7 +369,8 @@ impl Calibrations {
                             match instruction {
                                 Instruction::Pragma(pragma) => {
                                     if pragma.name == "LOAD-MEMORY"
-                                        && pragma.data.as_ref() == Some(&calibration.parameter)
+                                        && pragma.data.as_ref()
+                                            == Some(&calibration.identifier.parameter)
                                     {
                                         if let Some(target) = &measurement.target {
                                             pragma.data = Some(target.to_quil_or_debug())
@@ -210,7 +385,10 @@ impl Calibrations {
                                 _ => {}
                             }
                         }
-                        Some(instructions)
+                        Some((
+                            instructions,
+                            CalibrationSource::MeasureCalibration(calibration.identifier.clone()),
+                        ))
                     }
                     None => None,
                 }
@@ -219,25 +397,80 @@ impl Calibrations {
         };
 
         // Add this instruction to the breadcrumb trail before recursion
-        let mut downstream_previous_calibrations =
-            Vec::with_capacity(previous_calibrations.len() + 1);
-        downstream_previous_calibrations.push(instruction.clone());
-        downstream_previous_calibrations.extend_from_slice(previous_calibrations);
+        let mut calibration_path = Vec::with_capacity(previous_calibrations.len() + 1);
+        calibration_path.push(instruction.clone());
+        calibration_path.extend_from_slice(previous_calibrations);
 
-        Ok(match expanded_once_instructions {
-            Some(instructions) => {
-                let mut recursively_expanded_instructions = vec![];
+        self.recursively_expand_inner(expansion_result, &calibration_path, build_source_map)
+    }
 
-                for instruction in instructions {
+    fn recursively_expand_inner(
+        &self,
+        expansion_result: Option<(Vec<Instruction>, CalibrationSource)>,
+        calibration_path: &[Instruction],
+        build_source_map: bool,
+    ) -> Result<Option<CalibrationExpansionOutput>, ProgramError> {
+        Ok(match expansion_result {
+            Some((instructions, matched_calibration)) => {
+                let mut recursively_expanded_instructions = CalibrationExpansionOutput {
+                    new_instructions: Vec::new(),
+                    detail: CalibrationExpansion {
+                        calibration_used: matched_calibration,
+                        range: InstructionIndex(0)..InstructionIndex(0),
+                        expansions: SourceMap::default(),
+                    },
+                };
+
+                for (expanded_index, instruction) in instructions.into_iter().enumerate() {
                     let expanded_instructions =
-                        self.expand(&instruction, &downstream_previous_calibrations)?;
+                        self.expand_inner(&instruction, calibration_path, build_source_map)?;
                     match expanded_instructions {
-                        Some(instructions) => {
-                            recursively_expanded_instructions.extend(instructions)
+                        Some(mut output) => {
+                            if build_source_map {
+                                let range_start = InstructionIndex(
+                                    recursively_expanded_instructions.new_instructions.len(),
+                                );
+
+                                recursively_expanded_instructions
+                                    .new_instructions
+                                    .extend(output.new_instructions);
+
+                                let range_end = InstructionIndex(
+                                    recursively_expanded_instructions.new_instructions.len(),
+                                );
+                                output.detail.range = range_start..range_end;
+
+                                recursively_expanded_instructions
+                                    .detail
+                                    .expansions
+                                    .entries
+                                    .push(SourceMapEntry {
+                                        source_location: InstructionIndex(expanded_index),
+                                        target_location: output.detail,
+                                    });
+                            } else {
+                                recursively_expanded_instructions
+                                    .new_instructions
+                                    .extend(output.new_instructions);
+                            }
+                        }
+                        None => {
+                            recursively_expanded_instructions
+                                .new_instructions
+                                .push(instruction);
                         }
-                        None => recursively_expanded_instructions.push(instruction),
                     };
                 }
+
+                if build_source_map {
+                    // While this appears to be duplicated information at this point, it's useful when multiple
+                    // source mappings are merged together.
+                    recursively_expanded_instructions.detail.range = InstructionIndex(0)
+                        ..InstructionIndex(
+                            recursively_expanded_instructions.new_instructions.len(),
+                        );
+                }
+
                 Some(recursively_expanded_instructions)
             }
             None => None,
@@ -264,12 +497,12 @@ impl Calibrations {
             .into_iter()
             .rev()
             .fold_while(None, |best_match, calibration| {
-                if let Some(qubit) = &calibration.qubit {
+                if let Some(qubit) = &calibration.identifier.qubit {
                     match qubit {
                         Qubit::Fixed(_) if qubit == &measurement.qubit => Done(Some(calibration)),
                         Qubit::Variable(_)
                             if best_match.is_none()
-                                || best_match.is_some_and(|c| c.qubit.is_none()) =>
+                                || best_match.is_some_and(|c| c.identifier.qubit.is_none()) =>
                         {
                             Continue(Some(calibration))
                         }
@@ -296,65 +529,10 @@ impl Calibrations {
     pub fn get_match_for_gate(&self, gate: &Gate) -> Option<&Calibration> {
         let mut matched_calibration: Option<MatchedCalibration> = None;
 
-        for calibration in self.iter_calibrations() {
-            // Filter out non-matching calibrations: check rules 1-4
-            if calibration.name != gate.name
-                || calibration.modifiers != gate.modifiers
-                || calibration.parameters.len() != gate.parameters.len()
-                || calibration.qubits.len() != gate.qubits.len()
-            {
-                continue;
-            }
-
-            let fixed_qubits_match =
-                calibration
-                    .qubits
-                    .iter()
-                    .enumerate()
-                    .all(|(calibration_index, _)| {
-                        match (
-                            &calibration.qubits[calibration_index],
-                            &gate.qubits[calibration_index],
-                        ) {
-                            // Placeholders never match
-                            (Qubit::Placeholder(_), _) | (_, Qubit::Placeholder(_)) => false,
-                            // If they're both fixed, test if they're fixed to the same qubit
-                            (
-                                Qubit::Fixed(calibration_fixed_qubit),
-                                Qubit::Fixed(gate_fixed_qubit),
-                            ) => calibration_fixed_qubit == gate_fixed_qubit,
-                            // If the calibration is variable, it matches any fixed qubit
-                            (Qubit::Variable(_), _) => true,
-                            // If the calibration is fixed, but the gate's qubit is variable, it's not a match
-                            (Qubit::Fixed(_), _) => false,
-                        }
-                    });
-            if !fixed_qubits_match {
-                continue;
-            }
-
-            let fixed_parameters_match =
-                calibration
-                    .parameters
-                    .iter()
-                    .enumerate()
-                    .all(|(calibration_index, _)| {
-                        let calibration_parameters = calibration.parameters[calibration_index]
-                            .clone()
-                            .into_simplified();
-                        let gate_parameters =
-                            gate.parameters[calibration_index].clone().into_simplified();
-                        match (calibration_parameters, gate_parameters) {
-                            // If the calibration is variable, it matches any fixed qubit
-                            (Expression::Variable(_), _) => true,
-                            // If the calibration is fixed, but the gate's qubit is variable, it's not a match
-                            (calib, gate) => calib == gate,
-                        }
-                    });
-            if !fixed_parameters_match {
-                continue;
-            }
-
+        for calibration in self
+            .iter_calibrations()
+            .filter(|calibration| calibration.identifier.matches(gate))
+        {
             matched_calibration = match matched_calibration {
                 None => Some(MatchedCalibration::new(calibration)),
                 Some(previous_match) => {
@@ -441,12 +619,16 @@ impl Calibrations {
 mod tests {
     use std::str::FromStr;
 
-    use crate::program::Program;
+    use crate::program::calibration::{CalibrationSource, MeasureCalibrationIdentifier};
+    use crate::program::source_map::{SourceMap, SourceMapEntry};
+    use crate::program::{InstructionIndex, Program};
     use crate::quil::Quil;
 
     use insta::assert_snapshot;
     use rstest::rstest;
 
+    use super::{CalibrationExpansion, CalibrationExpansionOutput, CalibrationIdentifier};
+
     #[rstest]
     #[case(
         "Calibration-Param-Precedence",
@@ -533,7 +715,6 @@ mod tests {
             "    PRAGMA CORRECT\n",
             "MEASURE 0 ro\n",
         )
-
     )]
     #[case(
         "Precedence-No-Qubit-Match",
@@ -572,6 +753,139 @@ mod tests {
         })
     }
 
+    /// Assert that instruction expansion yields the expected [`SourceMap`] and resulting instructions.
+    #[test]
+    fn expand_with_detail_recursive() {
+        let input = r#"
+DEFCAL X 0:
+    Y 0
+    MEASURE 0 ro
+    Y 0
+
+DEFCAL Y 0:
+    NOP
+    Z 0
+
+DEFCAL Z 0:
+    WAIT
+
+DEFCAL MEASURE 0 addr:
+    HALT
+
+X 0
+"#;
+
+        let program = Program::from_str(input).unwrap();
+        let instruction = program.instructions.last().unwrap();
+        let expansion = program
+            .calibrations
+            .expand_with_detail(instruction, &[])
+            .unwrap();
+        let expected = CalibrationExpansionOutput {
+            new_instructions: vec![
+                crate::instruction::Instruction::Nop,
+                crate::instruction::Instruction::Wait,
+                crate::instruction::Instruction::Halt,
+                crate::instruction::Instruction::Nop,
+                crate::instruction::Instruction::Wait,
+            ],
+            detail: CalibrationExpansion {
+                calibration_used: CalibrationSource::Calibration(CalibrationIdentifier {
+                    modifiers: vec![],
+                    name: "X".to_string(),
+                    parameters: vec![],
+                    qubits: vec![crate::instruction::Qubit::Fixed(0)],
+                }),
+                range: InstructionIndex(0)..InstructionIndex(5),
+                expansions: SourceMap {
+                    entries: vec![
+                        SourceMapEntry {
+                            source_location: InstructionIndex(0),
+                            target_location: CalibrationExpansion {
+                                calibration_used: CalibrationSource::Calibration(
+                                    CalibrationIdentifier {
+                                        modifiers: vec![],
+                                        name: "Y".to_string(),
+                                        parameters: vec![],
+                                        qubits: vec![crate::instruction::Qubit::Fixed(0)],
+                                    },
+                                ),
+                                range: InstructionIndex(0)..InstructionIndex(2),
+                                expansions: SourceMap {
+                                    entries: vec![SourceMapEntry {
+                                        source_location: InstructionIndex(1),
+                                        target_location: CalibrationExpansion {
+                                            calibration_used: CalibrationSource::Calibration(
+                                                CalibrationIdentifier {
+                                                    modifiers: vec![],
+                                                    name: "Z".to_string(),
+                                                    parameters: vec![],
+                                                    qubits: vec![crate::instruction::Qubit::Fixed(
+                                                        0,
+                                                    )],
+                                                },
+                                            ),
+                                            range: InstructionIndex(1)..InstructionIndex(2),
+                                            expansions: SourceMap::default(),
+                                        },
+                                    }],
+                                },
+                            },
+                        },
+                        SourceMapEntry {
+                            source_location: InstructionIndex(1),
+                            target_location: CalibrationExpansion {
+                                calibration_used: CalibrationSource::MeasureCalibration(
+                                    MeasureCalibrationIdentifier {
+                                        qubit: Some(crate::instruction::Qubit::Fixed(0)),
+                                        parameter: "addr".to_string(),
+                                    },
+                                ),
+                                range: InstructionIndex(2)..InstructionIndex(3),
+                                expansions: SourceMap::default(),
+                            },
+                        },
+                        SourceMapEntry {
+                            source_location: InstructionIndex(2),
+                            target_location: CalibrationExpansion {
+                                calibration_used: CalibrationSource::Calibration(
+                                    CalibrationIdentifier {
+                                        modifiers: vec![],
+                                        name: "Y".to_string(),
+                                        parameters: vec![],
+                                        qubits: vec![crate::instruction::Qubit::Fixed(0)],
+                                    },
+                                ),
+                                range: InstructionIndex(3)..InstructionIndex(5),
+                                expansions: SourceMap {
+                                    entries: vec![SourceMapEntry {
+                                        source_location: InstructionIndex(1),
+                                        target_location: CalibrationExpansion {
+                                            calibration_used: CalibrationSource::Calibration(
+                                                CalibrationIdentifier {
+                                                    modifiers: vec![],
+                                                    name: "Z".to_string(),
+                                                    parameters: vec![],
+                                                    qubits: vec![crate::instruction::Qubit::Fixed(
+                                                        0,
+                                                    )],
+                                                },
+                                            ),
+                                            range: InstructionIndex(1)..InstructionIndex(2),
+                                            expansions: SourceMap::default(),
+                                        },
+                                    }],
+                                },
+                            },
+                        },
+                    ],
+                },
+            },
+        };
+
+        pretty_assertions::assert_eq!(expansion, Some(expected));
+    }
+
     #[test]
     fn test_eq() {
         let input = "DEFCAL X 0:
diff --git a/quil-rs/src/program/memory.rs b/quil-rs/src/program/memory.rs
index efc56e91..63bba8e9 100644
--- a/quil-rs/src/program/memory.rs
+++ b/quil-rs/src/program/memory.rs
@@ -183,6 +183,7 @@ impl Instruction {
             },
             Instruction::CalibrationDefinition(definition) => {
                 let references: Vec<&MemoryReference> = definition
+                    .identifier
                     .parameters
                     .iter()
                     .flat_map(|expr| expr.get_memory_references())
diff --git a/quil-rs/src/program/mod.rs b/quil-rs/src/program/mod.rs
index ca940bdc..2a8ad747 100644
--- a/quil-rs/src/program/mod.rs
+++ b/quil-rs/src/program/mod.rs
@@ -13,7 +13,7 @@
 // limitations under the License.
 
 use std::collections::{HashMap, HashSet};
-use std::ops;
+use std::ops::{self};
 use std::str::FromStr;
 
 use indexmap::{IndexMap, IndexSet};
@@ -31,6 +31,9 @@ use crate::parser::{lex, parse_instructions, ParseError};
 use crate::quil::Quil;
 
 pub use self::calibration::Calibrations;
+pub use self::calibration::{
+    CalibrationExpansion, CalibrationExpansionOutput, CalibrationSource, MaybeCalibrationExpansion,
+};
 pub use self::calibration_set::CalibrationSet;
 pub use self::error::{
     disallow_leftover, map_parsed, recover, LeftoverError, ParseProgramError, SyntaxError,
@@ -40,6 +43,7 @@ pub use self::frame::MatchedFrames;
 pub use self::memory::{
     MemoryAccess, MemoryAccesses, MemoryAccessesError, MemoryAccessesResult, MemoryRegion,
 };
+pub use self::source_map::{SourceMap, SourceMapEntry};
 
 pub mod analysis;
 mod calibration;
@@ -48,6 +52,7 @@ mod error;
 pub(crate) mod frame;
 mod memory;
 pub mod scheduling;
+mod source_map;
 pub mod type_check;
 
 #[derive(Clone, Debug, PartialEq, thiserror::Error)]
@@ -251,22 +256,36 @@ impl Program {
     }
 
     /// Expand any instructions in the program which have a matching calibration, leaving the others
-    /// unchanged. Recurses though each instruction while ensuring there is no cycle in the expansion
-    /// graph (i.e. no calibration expands directly or indirectly into itself)
+    /// unchanged. Return the expanded copy of the program.
+    ///
+    /// Return an error if any instruction expands into itself.
+    ///
+    /// See [`Program::expand_calibrations_with_source_map`] for a version that returns a source mapping.
     pub fn expand_calibrations(&self) -> Result<Self> {
-        let mut expanded_instructions: Vec<Instruction> = vec![];
+        self.expand_calibrations_inner(None)
+    }
 
-        for instruction in &self.instructions {
-            match self.calibrations.expand(instruction, &[])? {
-                Some(expanded) => {
-                    expanded_instructions.extend(expanded);
-                }
-                None => {
-                    expanded_instructions.push(instruction.clone());
-                }
-            }
-        }
+    /// Expand any instructions in the program which have a matching calibration, leaving the others
+    /// unchanged. Return the expanded copy of the program and a source mapping of the expansions made.
+    pub fn expand_calibrations_with_source_map(&self) -> Result<ProgramCalibrationExpansion> {
+        let mut source_mapping = ProgramCalibrationExpansionSourceMap::default();
+        let new_program = self.expand_calibrations_inner(Some(&mut source_mapping))?;
+
+        Ok(ProgramCalibrationExpansion {
+            program: new_program,
+            source_map: source_mapping,
+        })
+    }
 
+    /// Expand calibrations, writing expansions to a [`SourceMap`] if provided.
+    ///
+    /// Return an error if any instruction expands into itself.
+    ///
+    /// Source map may be omitted for faster performance.
+    fn expand_calibrations_inner(
+        &self,
+        mut source_mapping: Option<&mut ProgramCalibrationExpansionSourceMap>,
+    ) -> Result<Self> {
         let mut new_program = Self {
             calibrations: self.calibrations.clone(),
             extern_pragma_map: self.extern_pragma_map.clone(),
@@ -278,11 +297,79 @@ impl Program {
             used_qubits: HashSet::new(),
         };
 
-        new_program.add_instructions(expanded_instructions);
+        for (index, instruction) in self.instructions.iter().enumerate() {
+            let index = InstructionIndex(index);
+
+            match self.calibrations.expand_with_detail(instruction, &[])? {
+                Some(expanded) => {
+                    new_program.append_calibration_expansion_output_inner(
+                        expanded,
+                        index,
+                        &mut source_mapping,
+                    );
+                }
+                None => {
+                    new_program.add_instruction(instruction.clone());
+                    if let Some(source_mapping) = source_mapping.as_mut() {
+                        source_mapping.entries.push(SourceMapEntry {
+                            source_location: index,
+                            target_location: MaybeCalibrationExpansion::Unexpanded(
+                                InstructionIndex(new_program.instructions.len() - 1),
+                            ),
+                        });
+                    }
+                }
+            }
+        }
 
         Ok(new_program)
     }
 
+    /// Append the result of a calibration expansion to this program, being aware of which expanded instructions
+    /// land in the program body (and thus merit inclusion within a target range) and which do not.
+    ///
+    /// For example, `DECLARE` instructions are hoisted to a specialized data structure and thus do not appear in
+    /// the program body. Thus, they should not be counted in the `target_index` range within a [`SourceMapEntry`].
+    fn append_calibration_expansion_output_inner(
+        &mut self,
+        mut expansion_output: CalibrationExpansionOutput,
+        source_index: InstructionIndex,
+        source_mapping: &mut Option<&mut ProgramCalibrationExpansionSourceMap>,
+    ) {
+        if let Some(source_mapping) = source_mapping.as_mut() {
+            let previous_program_instruction_body_length = self.instructions.len();
+
+            for instruction in expansion_output.new_instructions {
+                let start_length = self.instructions.len();
+                self.add_instruction(instruction.clone());
+                let end_length = self.instructions.len();
+
+                // If the instruction was not added to the program body, remove its target index from the source map
+                // so that the map stays correct.
+                if start_length == end_length {
+                    let relative_target_index =
+                        InstructionIndex(start_length - previous_program_instruction_body_length);
+                    expansion_output
+                        .detail
+                        .remove_target_index(relative_target_index);
+                }
+            }
+
+            expansion_output.detail.range =
+                InstructionIndex(previous_program_instruction_body_length)
+                    ..InstructionIndex(self.instructions.len());
+
+            if !expansion_output.detail.range.is_empty() {
+                source_mapping.entries.push(SourceMapEntry {
+                    source_location: source_index,
+                    target_location: MaybeCalibrationExpansion::Expanded(expansion_output.detail),
+                });
+            }
+        } else {
+            self.add_instructions(expansion_output.new_instructions);
+        }
+    }
+
     /// Build a program from a list of instructions
     pub fn from_instructions(instructions: Vec<Instruction>) -> Self {
         let mut program = Self::default();
@@ -751,17 +838,50 @@ impl ops::AddAssign<Program> for Program {
     }
 }
 
+#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
+pub struct InstructionIndex(pub usize);
+
+impl InstructionIndex {
+    fn map(self, f: impl FnOnce(usize) -> usize) -> Self {
+        Self(f(self.0))
+    }
+}
+
+pub type ProgramCalibrationExpansionSourceMap =
+    SourceMap<InstructionIndex, MaybeCalibrationExpansion>;
+
+#[derive(Clone, Debug, PartialEq)]
+pub struct ProgramCalibrationExpansion {
+    program: Program,
+    source_map: ProgramCalibrationExpansionSourceMap,
+}
+
+impl ProgramCalibrationExpansion {
+    pub fn program(&self) -> &Program {
+        &self.program
+    }
+
+    pub fn source_map(&self) -> &ProgramCalibrationExpansionSourceMap {
+        &self.source_map
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use super::Program;
     use crate::{
         imag,
         instruction::{
-            Call, Declaration, ExternSignatureMap, Gate, Instruction, Jump, JumpUnless, JumpWhen,
-            Label, Matrix, MemoryReference, Qubit, QubitPlaceholder, ScalarType, Target,
-            TargetPlaceholder, UnresolvedCallArgument, Vector, RESERVED_PRAGMA_EXTERN,
+            CalibrationIdentifier, Call, Declaration, ExternSignatureMap, Gate, Instruction, Jump,
+            JumpUnless, JumpWhen, Label, Matrix, MemoryReference, Qubit, QubitPlaceholder,
+            ScalarType, Target, TargetPlaceholder, UnresolvedCallArgument, Vector,
+            RESERVED_PRAGMA_EXTERN,
+        },
+        program::{
+            calibration::{CalibrationExpansion, CalibrationSource, MaybeCalibrationExpansion},
+            source_map::{SourceMap, SourceMapEntry},
+            InstructionIndex, MemoryAccesses,
         },
-        program::MemoryAccesses,
         quil::{Quil, INDENT},
         real,
     };
@@ -885,6 +1005,121 @@ DECLARE ec BIT
         assert!(program1.lines().eq(program2.lines()));
     }
 
+    /// Assert that a program's instructions are correctly expanded using its calibrations,
+    /// emitting the expected [`SourceMap`] for the expansion.
+    #[test]
+    fn expand_calibrations() {
+        let input = r#"DECLARE ro BIT[1]
+DEFFRAME 0 "a":
+    HARDWARE-OBJECT: "hardware"
+
+DEFCAL I 0:
+    DECLAREMEM
+    NOP
+    NOP
+
+DEFCAL DECLAREMEM:
+    DECLARE mem BIT[1]
+    NOP
+
+I 0
+PULSE 0 "a" custom_waveform
+I 0
+"#;
+
+        let expected = "DECLARE ro BIT[1]
+DECLARE mem BIT[1]
+DEFFRAME 0 \"a\":
+    HARDWARE-OBJECT: \"hardware\"
+DEFCAL I 0:
+    DECLAREMEM
+    NOP
+    NOP
+DEFCAL DECLAREMEM:
+    DECLARE mem BIT[1]
+    NOP
+NOP
+NOP
+NOP
+PULSE 0 \"a\" custom_waveform
+NOP
+NOP
+NOP
+";
+
+        let expected_source_map = SourceMap {
+            entries: vec![
+                SourceMapEntry {
+                    source_location: InstructionIndex(0),
+                    target_location: MaybeCalibrationExpansion::Expanded(CalibrationExpansion {
+                        calibration_used: CalibrationIdentifier {
+                            name: "I".to_string(),
+                            qubits: vec![Qubit::Fixed(0)],
+                            ..CalibrationIdentifier::default()
+                        }
+                        .into(),
+                        range: InstructionIndex(0)..InstructionIndex(3),
+                        expansions: SourceMap {
+                            entries: vec![SourceMapEntry {
+                                source_location: InstructionIndex(0),
+                                target_location: CalibrationExpansion {
+                                    calibration_used: CalibrationSource::Calibration(
+                                        CalibrationIdentifier {
+                                            modifiers: vec![],
+                                            name: "DECLAREMEM".to_string(),
+                                            parameters: vec![],
+                                            qubits: vec![],
+                                        },
+                                    ),
+                                    range: InstructionIndex(0)..InstructionIndex(1),
+                                    expansions: SourceMap { entries: vec![] },
+                                },
+                            }],
+                        },
+                    }),
+                },
+                SourceMapEntry {
+                    source_location: InstructionIndex(1),
+                    target_location: MaybeCalibrationExpansion::Unexpanded(InstructionIndex(3)),
+                },
+                SourceMapEntry {
+                    source_location: InstructionIndex(2),
+                    target_location: MaybeCalibrationExpansion::Expanded(CalibrationExpansion {
+                        calibration_used: CalibrationIdentifier {
+                            name: "I".to_string(),
+                            qubits: vec![Qubit::Fixed(0)],
+                            ..CalibrationIdentifier::default()
+                        }
+                        .into(),
+                        range: InstructionIndex(4)..InstructionIndex(7),
+                        expansions: SourceMap {
+                            entries: vec![SourceMapEntry {
+                                source_location: InstructionIndex(0),
+                                target_location: CalibrationExpansion {
+                                    calibration_used: CalibrationSource::Calibration(
+                                        CalibrationIdentifier {
+                                            modifiers: vec![],
+                                            name: "DECLAREMEM".to_string(),
+                                            parameters: vec![],
+                                            qubits: vec![],
+                                        },
+                                    ),
+                                    range: InstructionIndex(0)..InstructionIndex(1),
+                                    expansions: SourceMap { entries: vec![] },
+                                },
+                            }],
+                        },
+                    }),
+                },
+            ],
+        };
+
+        let program = Program::from_str(input).unwrap();
+        let expanded_program = program.expand_calibrations_with_source_map().unwrap();
+        pretty_assertions::assert_eq!(expanded_program.program.to_quil().unwrap(), expected);
+        pretty_assertions::assert_eq!(expanded_program.source_map, expected_source_map);
+    }
+
     #[test]
     fn frame_blocking() {
         let input = "DEFFRAME 0 \"a\":
diff --git a/quil-rs/src/program/source_map.rs b/quil-rs/src/program/source_map.rs
new file mode 100644
index 00000000..eb3aa336
--- /dev/null
+++ b/quil-rs/src/program/source_map.rs
@@ -0,0 +1,101 @@
+use super::InstructionIndex;
+
+/// A SourceMap provides information necessary to understand which parts of a target
+/// were derived from which parts of a source artifact, in such a way that they can be
+/// mapped in either direction.
+///
+/// The behavior of such mappings depends on the implementations of the generic `Index` types,
+/// but this may be a many-to-many mapping, where one element of the source is mapped (contributes)
+/// to zero or many elements of the target, and vice versa.
+///
+/// This is also intended to be mergeable in a chain, such that the combined result of a series
+/// of transformations can be expressed within a single source mapping.
+#[derive(Clone, Debug, PartialEq)]
+pub struct SourceMap<SourceIndex, TargetIndex> {
+    pub(crate) entries: Vec<SourceMapEntry<SourceIndex, TargetIndex>>,
+}
+
+impl<SourceIndex, TargetIndex> SourceMap<SourceIndex, TargetIndex> {
+    /// Return all source ranges in the source map which were used to generate the target range.
+    ///
+    /// This is `O(n)` where `n` is the number of entries in the map.
+    pub fn list_sources<QueryIndex>(&self, target_index: &QueryIndex) -> Vec<&SourceIndex>
+    where
+        TargetIndex: SourceMapIndexable<QueryIndex>,
+    {
+        self.entries
+            .iter()
+            .filter_map(|entry| {
+                if entry.target_location().intersects(target_index) {
+                    Some(entry.source_location())
+                } else {
+                    None
+                }
+            })
+            .collect()
+    }
+
+    /// Return all target ranges in the source map which were used to generate the source range.
+    ///
+    /// This is `O(n)` where `n` is the number of entries in the map.
+    pub fn list_targets<QueryIndex>(&self, source_index: &QueryIndex) -> Vec<&TargetIndex>
+    where
+        SourceIndex: SourceMapIndexable<QueryIndex>,
+    {
+        self.entries
+            .iter()
+            .filter_map(|entry| {
+                if entry.source_location().intersects(source_index) {
+                    Some(entry.target_location())
+                } else {
+                    None
+                }
+            })
+            .collect()
+    }
+}
+
+impl<SourceIndex, TargetIndex> Default for SourceMap<SourceIndex, TargetIndex> {
+    fn default() -> Self {
+        Self {
+            entries: Vec::new(),
+        }
+    }
+}
+
+impl<SourceIndex, TargetIndex> SourceMap<SourceIndex, TargetIndex> {
+    pub fn entries(&self) -> &[SourceMapEntry<SourceIndex, TargetIndex>] {
+        &self.entries
+    }
+}
+
+#[derive(Clone, Debug, PartialEq)]
+pub struct SourceMapEntry<SourceIndex, TargetIndex> {
+    /// The locator within the source artifact
+    pub(crate) source_location: SourceIndex,
+
+    /// The locator within the target artifact
+    pub(crate) target_location: TargetIndex,
+}
+
+impl<SourceIndex, TargetIndex> SourceMapEntry<SourceIndex, TargetIndex> {
+    pub fn source_location(&self) -> &SourceIndex {
+        &self.source_location
+    }
+
+    pub fn target_location(&self) -> &TargetIndex {
+        &self.target_location
+    }
+}
+
+/// A trait for types which can be used as lookup indices in a `SourceMap.`
+pub trait SourceMapIndexable<Index> {
+    /// Return `true` if a source or target index intersects `other`.
+    fn intersects(&self, other: &Index) -> bool;
+}
+
+impl SourceMapIndexable<InstructionIndex> for InstructionIndex {
+    fn intersects(&self, other: &InstructionIndex) -> bool {
+        self == other
+    }
+}


Test patch:
diff --git a/quil-py/tests_py/instructions/test_copy.py b/quil-py/tests_py/instructions/test_copy.py
index e43ed78b..f36e87f3 100644
--- a/quil-py/tests_py/instructions/test_copy.py
+++ b/quil-py/tests_py/instructions/test_copy.py
@@ -3,6 +3,7 @@
 from quil.expression import Expression
 from quil.instructions import (
     Calibration,
+    CalibrationIdentifier,
     Delay,
     FrameIdentifier,
     Instruction,
@@ -38,11 +39,8 @@ def test_instruction_with_duplicate_placeholders():
     placeholder = Qubit.from_placeholder(QubitPlaceholder())
 
     calibration = Calibration(
-        "MYCAL",
-        [],
-        [placeholder],
+        CalibrationIdentifier("MYCAL", [], [placeholder], []),
         [Instruction.from_delay(Delay(Expression.from_number(complex(0.5)), [], [placeholder]))],
-        [],
     )
 
     calibration_copy = copy(calibration)
@@ -51,4 +49,4 @@ def test_instruction_with_duplicate_placeholders():
     calibration_deepcopy = deepcopy(calibration)
     assert calibration_deepcopy != calibration
 
-    assert calibration_deepcopy.qubits == calibration_deepcopy.instructions[0].to_delay().qubits
+    assert calibration_deepcopy.identifier.qubits == calibration_deepcopy.instructions[0].to_delay().qubits
diff --git a/quil-py/tests_py/program/test_program.py b/quil-py/tests_py/program/test_program.py
index 93e35247..042d2951 100644
--- a/quil-py/tests_py/program/test_program.py
+++ b/quil-py/tests_py/program/test_program.py
@@ -186,3 +186,58 @@ def test_filter_instructions(snapshot: SnapshotAssertion):
     program = Program.parse(input)
     program_without_quil_t = program.filter_instructions(lambda instruction: not instruction.is_quil_t())
     assert program_without_quil_t.to_quil() == snapshot
+
+
+def test_calibration_expansion():
+    """
+    Assert that program calibration expansion happens as expected and that the source map is correct.
+    """
+    import inspect
+
+    program_text = inspect.cleandoc(
+        """
+        DEFCAL X 0:
+            Y 0
+
+        DEFCAL Y 0:
+            Z 0
+
+        X 0
+        Y 0
+        """
+    )
+    program = Program.parse(program_text)
+    expansion = program.expand_calibrations_with_source_map()
+    source_map = expansion.source_map()
+
+    expected_program_text = inspect.cleandoc(
+        """
+        DEFCAL X 0:
+            Y 0
+
+        DEFCAL Y 0:
+            Z 0
+
+        Z 0
+        Z 0
+        """
+    )
+
+    assert expansion.program().to_quil() == Program.parse(expected_program_text).to_quil()
+
+    # The X at index 0 should have been replaced with a Z at index 0
+    targets = source_map.list_targets_for_source_index(0)
+    assert len(targets) == 1
+    expanded = targets[0].as_expanded()
+    assert expanded.range() == range(0, 1)
+    assert source_map.list_sources_for_target_index(0) == [0]
+
+    # The Y at index 1 should have been replaced with a Z at index 1
+    targets = source_map.list_targets_for_source_index(1)
+    assert len(targets) == 1
+    expanded = targets[0].as_expanded()
+    assert expanded.range() == range(1, 2)
+    assert source_map.list_sources_for_target_index(1) == [1]
+
+    # There is no source index 2 and so there should be no mapping
+    assert source_map.list_targets_for_source_index(2) == []
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__tests__to_instructions.snap b/quil-rs/src/program/snapshots/quil_rs__program__tests__to_instructions.snap
index b0428176..1e6f2f6e 100644
--- a/quil-rs/src/program/snapshots/quil_rs__program__tests__to_instructions.snap
+++ b/quil-rs/src/program/snapshots/quil_rs__program__tests__to_instructions.snap
@@ -54,6 +54,16 @@ expression: program.to_instructions()
     ),
     CalibrationDefinition(
         Calibration {
+            identifier: CalibrationIdentifier {
+                modifiers: [],
+                name: "I",
+                parameters: [],
+                qubits: [
+                    Fixed(
+                        1,
+                    ),
+                ],
+            },
             instructions: [
                 Delay(
                     Delay {
@@ -72,14 +82,6 @@ expression: program.to_instructions()
                     },
                 ),
             ],
-            modifiers: [],
-            name: "I",
-            parameters: [],
-            qubits: [
-                Fixed(
-                    1,
-                ),
-            ],
         },
     ),
     GateDefinition(