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

Issue:
Program equality is sensitive to calibration ordering
When checking if two programs are equal, calibrations should be compared as orderless sets. Calibrations are global state, so the order of them should not matter.

`quil-rs` current `Program` equality logic respects the order of calibrations (and possibly waveforms), which is incorrect.



Discussion / hints:

Fix patch:
diff --git a/Cargo.lock b/Cargo.lock
index 0f47e64f..7aafb63a 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -530,9 +530,9 @@ checksum = "443144c8cdadd93ebf52ddb4056d257f5b52c04d3c804e657d19eb73fc33668b"
 
 [[package]]
 name = "indexmap"
-version = "2.2.2"
+version = "2.2.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "824b2ae422412366ba479e8111fd301f7b5faece8149317bb81925979a53f520"
+checksum = "168fb715dda47215e360912c096649d23d58bf392ac62f73919e831745e40f26"
 dependencies = [
  "equivalent",
  "hashbrown",
@@ -936,6 +936,12 @@ dependencies = [
  "plotters-backend",
 ]
 
+[[package]]
+name = "portable-atomic"
+version = "1.6.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7170ef9988bc169ba16dd36a7fa041e5c4cbeb6a35b76d4c03daded371eae7c0"
+
 [[package]]
 name = "ppv-lite86"
 version = "0.2.17"
@@ -993,17 +999,19 @@ dependencies = [
 
 [[package]]
 name = "pyo3"
-version = "0.20.0"
+version = "0.20.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "04e8453b658fe480c3e70c8ed4e3d3ec33eb74988bd186561b0cc66b85c3bc4b"
+checksum = "53bdbb96d49157e65d45cc287af5f32ffadd5f4761438b527b055fb0d4bb8233"
 dependencies = [
  "cfg-if",
+ "indexmap",
  "indoc",
  "inventory",
  "libc",
  "memoffset",
  "num-complex",
  "parking_lot",
+ "portable-atomic",
  "pyo3-build-config",
  "pyo3-ffi",
  "pyo3-macros",
@@ -1012,9 +1020,9 @@ dependencies = [
 
 [[package]]
 name = "pyo3-build-config"
-version = "0.20.0"
+version = "0.20.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a96fe70b176a89cff78f2fa7b3c930081e163d5379b4dcdf993e3ae29ca662e5"
+checksum = "deaa5745de3f5231ce10517a1f5dd97d53e5a2fd77aa6b5842292085831d48d7"
 dependencies = [
  "once_cell",
  "target-lexicon",
@@ -1022,9 +1030,9 @@ dependencies = [
 
 [[package]]
 name = "pyo3-ffi"
-version = "0.20.0"
+version = "0.20.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "214929900fd25e6604661ed9cf349727c8920d47deff196c4e28165a6ef2a96b"
+checksum = "62b42531d03e08d4ef1f6e85a2ed422eb678b8cd62b762e53891c05faf0d4afa"
 dependencies = [
  "libc",
  "pyo3-build-config",
@@ -1032,9 +1040,9 @@ dependencies = [
 
 [[package]]
 name = "pyo3-macros"
-version = "0.20.0"
+version = "0.20.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "dac53072f717aa1bfa4db832b39de8c875b7c7af4f4a6fe93cdbf9264cf8383b"
+checksum = "7305c720fa01b8055ec95e484a6eca7a83c841267f0dd5280f0c8b8551d2c158"
 dependencies = [
  "proc-macro2 1.0.78",
  "pyo3-macros-backend",
@@ -1044,12 +1052,13 @@ dependencies = [
 
 [[package]]
 name = "pyo3-macros-backend"
-version = "0.20.0"
+version = "0.20.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7774b5a8282bd4f25f803b1f0d945120be959a36c72e08e7cd031c792fdfd424"
+checksum = "7c7e9b68bb9c3149c5b0cade5d07f953d6d125eb4337723c4ccdb665f1f96185"
 dependencies = [
  "heck 0.4.1",
  "proc-macro2 1.0.78",
+ "pyo3-build-config",
  "quote 1.0.35",
  "syn 2.0.48",
 ]
@@ -1062,7 +1071,7 @@ checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0"
 
 [[package]]
 name = "quil-cli"
-version = "0.1.0"
+version = "0.2.0-rc.0"
 dependencies = [
  "anyhow",
  "clap",
@@ -1073,6 +1082,7 @@ dependencies = [
 name = "quil-py"
 version = "0.7.1"
 dependencies = [
+ "indexmap",
  "ndarray",
  "numpy",
  "pyo3",
diff --git a/Cargo.toml b/Cargo.toml
index bf0f40ac..85969111 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -9,3 +9,4 @@ codegen-units = 1
 [workspace.dependencies]
 ndarray = { version = "0.15.6", features = ["approx-0_5"] }
 strum = { version = "0.26.0", features = ["derive"] }
+indexmap = "2.2.6"
diff --git a/quil-py/Cargo.toml b/quil-py/Cargo.toml
index 9e0314b9..b99387a2 100644
--- a/quil-py/Cargo.toml
+++ b/quil-py/Cargo.toml
@@ -26,8 +26,9 @@ quil-rs = { path = "../quil-rs", version = "0.23.0" }
 strum.workspace = true
 # pyo3 dependencies should be updated together
 numpy = "0.20.0"
-pyo3 = "0.20.0"
+pyo3 = { version = "0.20.3", features = ["indexmap"] }
 rigetti-pyo3 = "0.3.1"
+indexmap.workspace = true
 
 [build-dependencies]
 pyo3-build-config = "0.20.0"
diff --git a/quil-py/quil/program/__init__.pyi b/quil-py/quil/program/__init__.pyi
index 6127d47e..d51c66b7 100644
--- a/quil-py/quil/program/__init__.pyi
+++ b/quil-py/quil/program/__init__.pyi
@@ -322,14 +322,20 @@ class CalibrationSet:
     def is_empty(self) -> bool:
         """Returns ``True`` if the ``CalibrationSet`` contains no data."""
         ...
-    def push_calibration(self, calibration: Calibration):
+    def insert_calibration(self, calibration: Calibration) -> Optional[Calibration]:
         """
-        Add another gate ``Calibration`` (`DEFCAL`) to the set.
+        Insert another ``Calibration`` (`DEFCAL`) to the set.
+
+        If a calibration with the same name already exists, it is overwritten and this
+        function returns the previous calibration. Otherwise, None is returned.
         """
         ...
-    def push_measurement_calibration(self, calibration: MeasureCalibrationDefinition):
+    def insert_measurement_calibration(self, calibration: MeasureCalibrationDefinition) -> Optional[MeasureCalibrationDefinition]:
         """
         Add another ``MeasureCalibrationDefinition`` (`DEFCAL MEASURE`) to the set
+
+        If a calibration with the same name already exists, it is overwritten and this
+        function returns the previous calibration. Otherwise, None is returned.
         """
     def extend(self, other: CalibrationSet):
         """
diff --git a/quil-py/src/program/calibration.rs b/quil-py/src/program/calibration.rs
index 3444cf48..4b54cb57 100644
--- a/quil-py/src/program/calibration.rs
+++ b/quil-py/src/program/calibration.rs
@@ -1,6 +1,6 @@
 use quil_rs::{
     instruction::{Calibration, Gate, Instruction, MeasureCalibrationDefinition, Measurement},
-    program::CalibrationSet,
+    program::Calibrations,
 };
 use rigetti_pyo3::{
     impl_as_mut_for_wrapper, impl_repr, py_wrap_type,
@@ -19,7 +19,7 @@ use super::ProgramError;
 
 py_wrap_type! {
     #[derive(Debug, PartialEq)]
-    PyCalibrationSet(CalibrationSet) as "CalibrationSet"
+    PyCalibrationSet(Calibrations) as "CalibrationSet"
 }
 impl_as_mut_for_wrapper!(PyCalibrationSet);
 impl_repr!(PyCalibrationSet);
@@ -29,13 +29,20 @@ impl_eq!(PyCalibrationSet);
 impl PyCalibrationSet {
     #[new]
     pub fn new(
-        py: Python<'_>,
         calibrations: Vec<PyCalibration>,
         measure_calibrations: Vec<PyMeasureCalibrationDefinition>,
     ) -> PyResult<Self> {
-        Ok(Self(CalibrationSet {
-            calibrations: Vec::<_>::py_try_from(py, &calibrations)?,
-            measure_calibrations: Vec::<_>::py_try_from(py, &measure_calibrations)?,
+        Ok(Self(Calibrations {
+            calibrations: calibrations
+                .into_iter()
+                .map(|c| c.into_inner())
+                .collect::<Vec<Calibration>>()
+                .into(),
+            measure_calibrations: measure_calibrations
+                .into_iter()
+                .map(|c| c.into_inner())
+                .collect::<Vec<MeasureCalibrationDefinition>>()
+                .into(),
         }))
     }
 
@@ -98,26 +105,34 @@ impl PyCalibrationSet {
         self.as_inner().is_empty()
     }
 
-    pub fn push_calibration(&mut self, py: Python<'_>, calibration: PyCalibration) -> PyResult<()> {
-        self.as_inner_mut()
-            .push_calibration(Calibration::py_try_from(py, &calibration)?);
-        Ok(())
+    pub fn insert_calibration(
+        &mut self,
+        py: Python<'_>,
+        calibration: PyCalibration,
+    ) -> PyResult<Option<PyCalibration>> {
+        Ok(self
+            .as_inner_mut()
+            .insert_calibration(Calibration::py_try_from(py, &calibration)?)
+            .map(PyCalibration::from))
     }
 
-    pub fn push_measurement_calibration(
+    pub fn insert_measurement_calibration(
         &mut self,
         py: Python<'_>,
         calibration: PyMeasureCalibrationDefinition,
-    ) -> PyResult<()> {
-        self.as_inner_mut().push_measurement_calibration(
-            MeasureCalibrationDefinition::py_try_from(py, &calibration)?,
-        );
-        Ok(())
+    ) -> PyResult<Option<PyMeasureCalibrationDefinition>> {
+        Ok(self
+            .as_inner_mut()
+            .insert_measurement_calibration(MeasureCalibrationDefinition::py_try_from(
+                py,
+                &calibration,
+            )?)
+            .map(PyMeasureCalibrationDefinition::from))
     }
 
     pub fn extend(&mut self, py: Python<'_>, other: PyCalibrationSet) -> PyResult<()> {
         self.as_inner_mut()
-            .extend(CalibrationSet::py_try_from(py, &other)?);
+            .extend(Calibrations::py_try_from(py, &other)?);
         Ok(())
     }
 
diff --git a/quil-py/src/program/mod.rs b/quil-py/src/program/mod.rs
index 6a0ac92a..4f406c7d 100644
--- a/quil-py/src/program/mod.rs
+++ b/quil-py/src/program/mod.rs
@@ -8,7 +8,7 @@ use quil_rs::{
     instruction::{Instruction, QubitPlaceholder, TargetPlaceholder, Waveform},
     program::{
         analysis::{ControlFlowGraph, ControlFlowGraphOwned},
-        CalibrationSet, FrameSet, MemoryRegion,
+        Calibrations, FrameSet, MemoryRegion,
     },
     Program,
 };
@@ -109,7 +109,7 @@ impl PyProgram {
         calibrations: PyCalibrationSet,
     ) -> PyResult<()> {
         let program = self.as_inner_mut();
-        program.calibrations = CalibrationSet::py_try_from(py, &calibrations)?;
+        program.calibrations = Calibrations::py_try_from(py, &calibrations)?;
         Ok(())
     }
 
diff --git a/quil-rs/Cargo.toml b/quil-rs/Cargo.toml
index 87267f88..856659c8 100644
--- a/quil-rs/Cargo.toml
+++ b/quil-rs/Cargo.toml
@@ -12,7 +12,6 @@ categories = ["parser-implementations", "science", "compilers", "emulators"]
 [dependencies]
 approx = { version = "0.5.1", features = ["num-complex"] }
 dot-writer = { version = "0.1.2", optional = true }
-indexmap = "2.2.2"
 itertools = "0.12.1"
 lexical = "6.1.1"
 ndarray.workspace = true
@@ -25,6 +24,7 @@ regex = "1.7.1"
 serde = { version = "1.0.125", features = ["derive"] }
 strum.workspace = true
 thiserror = "1.0.56"
+indexmap.workspace = true
 
 [dev-dependencies]
 clap = { version = "4.3.19", features = ["derive", "string"] }
diff --git a/quil-rs/src/instruction/calibration.rs b/quil-rs/src/instruction/calibration.rs
index 4aac5b6e..88b5f3e0 100644
--- a/quil-rs/src/instruction/calibration.rs
+++ b/quil-rs/src/instruction/calibration.rs
@@ -9,6 +9,15 @@ use crate::{
 
 use super::write_qubit_parameters;
 
+pub trait CalibrationSignature {
+    type Signature<'a>
+    where
+        Self: 'a;
+
+    fn signature(&self) -> Self::Signature<'_>;
+    fn has_signature(&self, signature: &Self::Signature<'_>) -> bool;
+}
+
 #[derive(Clone, Debug, Default, PartialEq)]
 pub struct Calibration {
     pub instructions: Vec<Instruction>,
@@ -60,6 +69,23 @@ impl Quil for Calibration {
     }
 }
 
+impl CalibrationSignature for Calibration {
+    type Signature<'a> = (&'a str, &'a [Expression], &'a [Qubit]);
+
+    fn signature(&self) -> Self::Signature<'_> {
+        (
+            self.name.as_str(),
+            self.parameters.as_slice(),
+            self.qubits.as_slice(),
+        )
+    }
+
+    fn has_signature(&self, signature: &Self::Signature<'_>) -> bool {
+        let (name, parameters, qubits) = signature;
+        self.name == *name && self.parameters == *parameters && self.qubits == *qubits
+    }
+}
+
 #[derive(Clone, Debug, PartialEq)]
 pub struct MeasureCalibrationDefinition {
     pub qubit: Option<Qubit>,
@@ -77,6 +103,19 @@ impl MeasureCalibrationDefinition {
     }
 }
 
+impl CalibrationSignature for MeasureCalibrationDefinition {
+    type Signature<'a> = (Option<&'a Qubit>, &'a str);
+
+    fn signature(&self) -> Self::Signature<'_> {
+        (self.qubit.as_ref(), self.parameter.as_str())
+    }
+
+    fn has_signature(&self, signature: &Self::Signature<'_>) -> bool {
+        let (qubit, parameter) = signature;
+        self.qubit.as_ref() == *qubit && self.parameter == *parameter
+    }
+}
+
 impl Quil for MeasureCalibrationDefinition {
     fn write(
         &self,
diff --git a/quil-rs/src/instruction/mod.rs b/quil-rs/src/instruction/mod.rs
index 30adb1c1..09a781d3 100644
--- a/quil-rs/src/instruction/mod.rs
+++ b/quil-rs/src/instruction/mod.rs
@@ -40,7 +40,7 @@ mod reset;
 mod timing;
 mod waveform;
 
-pub use self::calibration::{Calibration, MeasureCalibrationDefinition};
+pub use self::calibration::{Calibration, CalibrationSignature, MeasureCalibrationDefinition};
 pub use self::circuit::CircuitDefinition;
 pub use self::classical::{
     Arithmetic, ArithmeticOperand, ArithmeticOperator, BinaryLogic, BinaryOperand, BinaryOperands,
diff --git a/quil-rs/src/program/calibration.rs b/quil-rs/src/program/calibration.rs
index ad7b18e8..2e0bccbe 100644
--- a/quil-rs/src/program/calibration.rs
+++ b/quil-rs/src/program/calibration.rs
@@ -17,24 +17,23 @@ use std::collections::HashMap;
 use itertools::FoldWhile::{Continue, Done};
 use itertools::Itertools;
 
-use crate::instruction::Fence;
 use crate::quil::Quil;
 use crate::{
     expression::Expression,
     instruction::{
-        Calibration, Capture, Delay, FrameIdentifier, Gate, Instruction,
+        Calibration, Capture, Delay, Fence, FrameIdentifier, Gate, Instruction,
         MeasureCalibrationDefinition, Measurement, Pulse, Qubit, RawCapture, SetFrequency,
         SetPhase, SetScale, ShiftFrequency, ShiftPhase,
     },
 };
 
-use super::ProgramError;
+use super::{CalibrationSet, ProgramError};
 
 /// A collection of Quil calibrations (`DEFCAL` instructions) with utility methods.
 #[derive(Clone, Debug, Default, PartialEq)]
-pub struct CalibrationSet {
-    pub calibrations: Vec<Calibration>,
-    pub measure_calibrations: Vec<MeasureCalibrationDefinition>,
+pub struct Calibrations {
+    pub calibrations: CalibrationSet<Calibration>,
+    pub measure_calibrations: CalibrationSet<MeasureCalibrationDefinition>,
 }
 
 struct MatchedCalibration<'a> {
@@ -58,15 +57,26 @@ impl<'a> MatchedCalibration<'a> {
     }
 }
 
-impl CalibrationSet {
-    /// Return all [`Calibration`]s in the set
-    pub fn calibrations(&self) -> &[Calibration] {
-        self.calibrations.as_ref()
+impl Calibrations {
+    /// Return a vector containing a reference to all [`Calibration`]s in the set.
+    pub fn calibrations(&self) -> Vec<&Calibration> {
+        self.iter_calibrations().collect()
     }
 
-    /// Return all [`MeasureCalibrationDefinition`]s in the set
-    pub fn measure_calibrations(&self) -> &[MeasureCalibrationDefinition] {
-        self.measure_calibrations.as_ref()
+    /// Return a vector containing a reference to all [`MeasureCalibrationDefinition`]s
+    /// in the set.
+    pub fn measure_calibrations(&self) -> Vec<&MeasureCalibrationDefinition> {
+        self.iter_measure_calibrations().collect()
+    }
+
+    /// Iterate over all [`Calibration`]s in the set
+    pub fn iter_calibrations(&self) -> impl Iterator<Item = &Calibration> {
+        self.calibrations.iter()
+    }
+
+    /// Iterate over all [`MeasureCalibrationDefinition`]s calibrations in the set
+    pub fn iter_measure_calibrations(&self) -> impl Iterator<Item = &MeasureCalibrationDefinition> {
+        self.measure_calibrations.iter()
     }
 
     /// Given an instruction, return the instructions to which it is expanded if there is a match.
@@ -251,7 +261,7 @@ impl CalibrationSet {
         measurement.target.as_ref()?;
 
         self.measure_calibrations()
-            .iter()
+            .into_iter()
             .rev()
             .fold_while(None, |best_match, calibration| {
                 if let Some(qubit) = &calibration.qubit {
@@ -286,7 +296,7 @@ impl CalibrationSet {
     pub fn get_match_for_gate(&self, gate: &Gate) -> Option<&Calibration> {
         let mut matched_calibration: Option<MatchedCalibration> = None;
 
-        for calibration in &self.calibrations {
+        for calibration in self.iter_calibrations() {
             // Filter out non-matching calibrations: check rules 1-4
             if calibration.name != gate.name
                 || calibration.modifiers != gate.modifiers
@@ -371,30 +381,36 @@ impl CalibrationSet {
         self.calibrations.is_empty()
     }
 
-    /// Add another gate calibration to the set.
-    /// Deprecated in favor of [`Self::push_calibration`]
-    #[deprecated = "use ScheduledProgram#push_calibration instead"]
-    pub fn push(&mut self, calibration: Calibration) {
-        self.push_calibration(calibration)
-    }
-
-    /// Add another gate calibration (`DEFCAL`) to the set.
-    pub fn push_calibration(&mut self, calibration: Calibration) {
-        self.calibrations.push(calibration)
+    /// Insert a [`Calibration`] into the set.
+    ///
+    /// If a calibration with the same [`CalibrationSignature`] already exists in the set, it will
+    /// be replaced, and the old calibration is returned.
+    pub fn insert_calibration(&mut self, calibration: Calibration) -> Option<Calibration> {
+        self.calibrations.replace(calibration)
     }
 
-    /// Add another measurement calibration (`DEFCAL MEASURE`) to the set.
-    pub fn push_measurement_calibration(&mut self, calibration: MeasureCalibrationDefinition) {
-        self.measure_calibrations.push(calibration)
+    /// Insert a [`MeasureCalibration`] into the set.
+    ///
+    /// If a calibration with the same [`CalibrationSignature`] already exists in the set, it will
+    /// be replaced, and the old calibration is returned.
+    pub fn insert_measurement_calibration(
+        &mut self,
+        calibration: MeasureCalibrationDefinition,
+    ) -> Option<MeasureCalibrationDefinition> {
+        self.measure_calibrations.replace(calibration)
     }
 
-    /// Append another [`CalibrationSet`] onto this one
-    pub fn extend(&mut self, other: CalibrationSet) {
+    /// Append another [`CalibrationSet`] onto this one.
+    ///
+    /// Calibrations with conflicting [`CalibrationSignature`]s are overwritten by the ones in the
+    /// given set.
+    pub fn extend(&mut self, other: Calibrations) {
         self.calibrations.extend(other.calibrations);
         self.measure_calibrations.extend(other.measure_calibrations);
     }
 
-    /// Return the Quil instructions which describe the contained calibrations, consuming the [`CalibrationSet`].
+    /// Return the Quil instructions which describe the contained calibrations, consuming the
+    /// [`CalibrationSet`]
     pub fn into_instructions(self) -> Vec<Instruction> {
         self.calibrations
             .into_iter()
@@ -409,13 +425,11 @@ impl CalibrationSet {
 
     /// Return the Quil instructions which describe the contained calibrations.
     pub fn to_instructions(&self) -> Vec<Instruction> {
-        self.calibrations
-            .iter()
+        self.iter_calibrations()
             .cloned()
             .map(Instruction::CalibrationDefinition)
             .chain(
-                self.measure_calibrations
-                    .iter()
+                self.iter_measure_calibrations()
                     .cloned()
                     .map(Instruction::MeasureCalibrationDefinition),
             )
diff --git a/quil-rs/src/program/calibration_set.rs b/quil-rs/src/program/calibration_set.rs
new file mode 100644
index 00000000..3be59e6f
--- /dev/null
+++ b/quil-rs/src/program/calibration_set.rs
@@ -0,0 +1,267 @@
+use crate::instruction::CalibrationSignature;
+
+/// A [`CalibrationSet`] is a collection of calibration instructions that respect how
+/// calibrations work in a Quil program.
+///
+/// During calibration expansion, Calibrations are matched to instructions using their unique
+/// [`CalibrationSignature`]. This means only one calibration can be matched to a particular
+/// instruction. While the Quil specification doesn't explicitly define the behavior of
+/// signature conflicts, [`CalibrationSet`] takes the liberty of only allowing one calibration
+/// per [`CalibrationSignature`].
+///
+/// In addition, calibration instructions are global. That is, their order or location in a
+/// program make no semantic difference. This means two program [`CalibrationSet`]s
+/// should be considered equal if they contain the same set of calibrations, regardless of
+/// order.
+///
+/// As a matter of convenience, the insertion order of calibrations is maintained. This
+/// allows for the same set of calibrations to be deterministically serialized to Quil.
+#[derive(Clone, Debug)]
+pub struct CalibrationSet<T> {
+    // The amount of calibrations in a program tends to be small enough that a Vec is more
+    // performant than a typical set.
+    // Sets also have trait bounds that `Instruction`s don't meet, which hampers utility.
+    data: Vec<T>,
+}
+
+impl<T> Default for CalibrationSet<T>
+where
+    T: CalibrationSignature,
+{
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<T> IntoIterator for CalibrationSet<T> {
+    type IntoIter = std::vec::IntoIter<Self::Item>;
+    type Item = T;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.data.into_iter()
+    }
+}
+
+impl<T> From<Vec<T>> for CalibrationSet<T>
+where
+    T: CalibrationSignature,
+{
+    fn from(data: Vec<T>) -> Self {
+        let mut set = Self::with_capacity(data.len());
+        for element in data {
+            set.replace(element);
+        }
+        set
+    }
+}
+
+impl<T> CalibrationSet<T>
+where
+    T: CalibrationSignature,
+{
+    /// Creates an empty [`ProgramCalibrationSet`].
+    pub fn new() -> Self {
+        Self { data: Vec::new() }
+    }
+
+    /// Creates a [`InnerCalibrationSet`] with the specified capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self {
+            data: Vec::with_capacity(capacity),
+        }
+    }
+
+    /// Returns the capacity of the [`ProgramCalibrationSet`].
+    pub fn capacity(&self) -> usize {
+        self.data.capacity()
+    }
+
+    /// Returns the length of the [`ProgramCalibrationSet`].
+    pub fn len(&self) -> usize {
+        self.data.len()
+    }
+
+    /// Returns whether the [`ProgramCalibrationSet`] is empty.
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// Returns an iterator of references to the values in the set.
+    pub fn iter(&self) -> std::slice::Iter<'_, T> {
+        self.data.iter()
+    }
+
+    /// Get a reference to a value that has a matching signature, if it exists.
+    pub fn get(&self, signature: &<T as CalibrationSignature>::Signature<'_>) -> Option<&T> {
+        if let Some(index) = self.signature_position(signature) {
+            Some(&self.data[index])
+        } else {
+            None
+        }
+    }
+
+    /// Adds a value to the set, replacing and returning an existing value with a matching
+    /// [`CalibrationSignature`], if it exists.
+    pub fn replace(&mut self, value: T) -> Option<T> {
+        let position = self.signature_position(&value.signature());
+        if let Some(index) = position {
+            let replaced = std::mem::replace(&mut self.data[index], value);
+            Some(replaced)
+        } else {
+            self.data.push(value);
+            None
+        }
+    }
+
+    /// Removes a value from the set. Returns whether the value was present in the set.
+    pub fn remove(&mut self, signature: &<T as CalibrationSignature>::Signature<'_>) -> bool {
+        if let Some(index) = self.signature_position(signature) {
+            self.data.remove(index);
+            true
+        } else {
+            false
+        }
+    }
+
+    /// Returns the index of an element whose [`CalibrationSignature`] matches the given value, if one exists.
+    fn signature_position(
+        &self,
+        signature: &<T as CalibrationSignature>::Signature<'_>,
+    ) -> Option<usize> {
+        for (i, element) in self.data.iter().enumerate() {
+            if element.has_signature(signature) {
+                return Some(i);
+            }
+        }
+
+        None
+        //self.data
+        //    .iter()
+        //    .position(move |element| { signature == element.signature() })
+    }
+}
+
+impl<T> Extend<T> for CalibrationSet<T>
+where
+    T: CalibrationSignature,
+{
+    fn extend<I>(&mut self, iter: I)
+    where
+        I: IntoIterator<Item = T>,
+    {
+        for value in iter {
+            self.replace(value);
+        }
+    }
+}
+
+impl<T> PartialEq for CalibrationSet<T>
+where
+    T: CalibrationSignature + PartialEq,
+    for<'a> <T as CalibrationSignature>::Signature<'a>: std::hash::Hash + Eq,
+{
+    fn eq(&self, other: &Self) -> bool {
+        let self_map: std::collections::HashMap<T::Signature<'_>, &T> = self
+            .data
+            .iter()
+            .map(|element| (element.signature(), element))
+            .collect();
+        let other_map: std::collections::HashMap<T::Signature<'_>, &T> = other
+            .data
+            .iter()
+            .map(|element| (element.signature(), element))
+            .collect();
+        self_map == other_map
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::instruction::CalibrationSignature;
+
+    #[derive(Clone, Debug, PartialEq)]
+    struct TestCalibration {
+        signature: String,
+        /// Optional byte, can be used to differentiate between two TestCalibrations with the same
+        /// signature.
+        data: Option<u8>,
+    }
+
+    impl TestCalibration {
+        fn new(signature: &str, data: Option<u8>) -> Self {
+            Self {
+                signature: signature.to_string(),
+                data,
+            }
+        }
+    }
+
+    impl CalibrationSignature for TestCalibration {
+        type Signature<'a> = &'a str;
+
+        fn signature(&self) -> Self::Signature<'_> {
+            self.signature.as_str()
+        }
+
+        fn has_signature(&self, signature: &Self::Signature<'_>) -> bool {
+            self.signature == *signature
+        }
+    }
+
+    #[test]
+    fn test_replace() {
+        let mut set = CalibrationSet::new();
+        let calib = TestCalibration::new("Signature", None);
+        set.replace(calib.clone());
+        assert_eq!(set.len(), 1);
+        assert!(set.iter().all(|item| item == &calib));
+
+        let calib2 = TestCalibration::new("Signature", Some(42));
+        let replaced = set
+            .replace(calib2.clone())
+            .expect("The original calibration should have been replaced.");
+        assert_eq!(replaced, calib);
+        assert_eq!(set.len(), 1);
+        assert!(set.iter().all(|item| item == &calib2));
+    }
+
+    #[test]
+    fn test_remove_signature() {
+        let mut set = CalibrationSet::new();
+        let calib = TestCalibration::new("Original", None);
+        set.replace(calib.clone());
+        assert!(set.remove(&calib.signature()));
+        assert!(set.is_empty());
+    }
+
+    #[test]
+    fn test_equality() {
+        let mut set1 = CalibrationSet::new();
+        let mut set2 = CalibrationSet::new();
+        let calib1 = TestCalibration::new("1", None);
+        let calib2 = TestCalibration::new("2", None);
+        set1.extend(vec![calib1.clone(), calib2.clone()]);
+        set2.extend(vec![calib2, calib1]); // Reverse order
+        assert_eq!(set1, set2); // They should be equal
+    }
+
+    #[test]
+    fn test_maintains_insert_order() {
+        let calibs = vec![
+            TestCalibration::new("1", None),
+            TestCalibration::new("2", None),
+            TestCalibration::new("3", None),
+        ];
+        let set = CalibrationSet::from(calibs.clone());
+        let calibs_from_set: Vec<TestCalibration> = set.into_iter().collect();
+        assert_eq!(calibs_from_set, calibs);
+    }
+
+    #[test]
+    fn test_with_capacity() {
+        let capacity = 10;
+        let set: CalibrationSet<TestCalibration> = CalibrationSet::with_capacity(capacity);
+        assert_eq!(set.capacity(), capacity);
+    }
+}
diff --git a/quil-rs/src/program/mod.rs b/quil-rs/src/program/mod.rs
index 74152da1..c492e2d4 100644
--- a/quil-rs/src/program/mod.rs
+++ b/quil-rs/src/program/mod.rs
@@ -29,7 +29,8 @@ use crate::instruction::{
 use crate::parser::{lex, parse_instructions, ParseError};
 use crate::quil::Quil;
 
-pub use self::calibration::CalibrationSet;
+pub use self::calibration::Calibrations;
+pub use self::calibration_set::CalibrationSet;
 pub use self::error::{disallow_leftover, map_parsed, recover, ParseProgramError, SyntaxError};
 pub use self::frame::FrameSet;
 pub use self::frame::MatchedFrames;
@@ -37,6 +38,7 @@ pub use self::memory::{MemoryAccesses, MemoryRegion};
 
 pub mod analysis;
 mod calibration;
+mod calibration_set;
 mod error;
 pub(crate) mod frame;
 mod memory;
@@ -70,7 +72,7 @@ type Result<T> = std::result::Result<T, ProgramError>;
 /// and frame definitions.
 #[derive(Clone, Debug, Default, PartialEq)]
 pub struct Program {
-    pub calibrations: CalibrationSet,
+    pub calibrations: Calibrations,
     pub frames: FrameSet,
     pub memory_regions: BTreeMap<String, MemoryRegion>,
     pub waveforms: BTreeMap<String, Waveform>,
@@ -83,7 +85,7 @@ pub struct Program {
 impl Program {
     pub fn new() -> Self {
         Program {
-            calibrations: CalibrationSet::default(),
+            calibrations: Calibrations::default(),
             frames: FrameSet::new(),
             memory_regions: BTreeMap::new(),
             waveforms: BTreeMap::new(),
@@ -136,7 +138,7 @@ impl Program {
 
         match instruction {
             Instruction::CalibrationDefinition(calibration) => {
-                self.calibrations.push_calibration(calibration);
+                self.calibrations.insert_calibration(calibration);
             }
             Instruction::FrameDefinition(FrameDefinition {
                 identifier,
@@ -157,7 +159,8 @@ impl Program {
                     .insert(gate_definition.name.clone(), gate_definition);
             }
             Instruction::MeasureCalibrationDefinition(calibration) => {
-                self.calibrations.push_measurement_calibration(calibration);
+                self.calibrations
+                    .insert_measurement_calibration(calibration);
             }
             Instruction::WaveformDefinition(WaveformDefinition { name, definition }) => {
                 self.waveforms.insert(name, definition);
@@ -336,7 +339,7 @@ impl Program {
         instructions.extend(self.waveforms.into_iter().map(|(name, definition)| {
             Instruction::WaveformDefinition(WaveformDefinition { name, definition })
         }));
-        instructions.extend(self.calibrations.into_instructions());
+        instructions.extend(self.calibrations.to_instructions());
         instructions.extend(
             self.gate_definitions
                 .into_values()
@@ -360,7 +363,7 @@ impl Program {
         // Remove calibrations such that the resulting program contains
         // only instructions. Calibrations have already been expanded, so
         // technically there is no need to keep them around anyway.
-        expanded_program.calibrations = CalibrationSet::default();
+        expanded_program.calibrations = Calibrations::default();
 
         let mut frames_used: HashSet<&FrameIdentifier> = HashSet::new();
         let mut waveforms_used: HashSet<&String> = HashSet::new();
@@ -1355,4 +1358,64 @@ I 0
 
         assert_snapshot!(program.to_quil().unwrap())
     }
+
+    #[test]
+    fn test_equality() {
+        let input = "DECLARE foo REAL[1]
+DEFFRAME 1 \"rx\":
+\tHARDWARE-OBJECT: \"hardware\"
+DEFCAL I 0:
+\tDELAY 0 1
+DEFCAL I 1:
+\tDELAY 0 1
+DEFCAL I 2:
+\tDELAY 0 1
+DEFCAL MEASURE 0 addr:
+\tCAPTURE 0 \"ro_rx\" custom addr
+DEFCAL MEASURE 1 addr:
+\tCAPTURE 1 \"ro_rx\" custom addr
+DEFWAVEFORM custom:
+\t1,2
+DEFWAVEFORM custom2:
+\t3,4
+DEFWAVEFORM another1:
+\t4,5
+DEFGATE BAR AS MATRIX:
+\t0, 1
+\t1, 0
+DEFGATE FOO AS MATRIX:
+\t0, 1
+\t1, 0
+
+H 1
+CNOT 2 3";
+
+        let program = Program::from_str(input).unwrap();
+
+        // The order of definitions are global in the sense that where they are defined in a
+        // program does not matter.
+        let is_global_state_instruction = move |i: &Instruction| -> bool {
+            matches!(
+                i,
+                Instruction::CalibrationDefinition(_)
+                    | Instruction::MeasureCalibrationDefinition(_)
+                    | Instruction::WaveformDefinition(_)
+                    | Instruction::GateDefinition(_)
+                    | Instruction::FrameDefinition(_)
+            )
+        };
+        // Create a copy of the program, but insert the "global" instructions in reverse order.
+        // Since where these instructions are defined doesn't matter, this should be an
+        // equivalent program.
+        let mut program2 = program.filter_instructions(|i| !is_global_state_instruction(i));
+        let global_instructions: Vec<Instruction> = program
+            .filter_instructions(is_global_state_instruction)
+            .into_instructions()
+            .into_iter()
+            .rev()
+            .collect();
+        program2.add_instructions(global_instructions);
+
+        assert_eq!(program, program2);
+    }
 }


Test patch:
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Measure-Calibration.snap b/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Measure-Calibration.snap
index 66862b03..fb8a6421 100644
--- a/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Measure-Calibration.snap
+++ b/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Measure-Calibration.snap
@@ -1,10 +1,7 @@
 ---
 source: quil-rs/src/program/calibration.rs
-expression: calibrated_program.to_string()
+expression: calibrated_program.to_quil_or_debug()
 ---
-DEFCAL MEASURE 0 addr:
-	PRAGMA INCORRECT_ORDERING
-
 DEFCAL MEASURE 0 addr:
 	PRAGMA CORRECT
 
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Precedence-Fixed-Match.snap b/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Precedence-Fixed-Match.snap
index ded50dae..60562669 100644
--- a/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Precedence-Fixed-Match.snap
+++ b/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Precedence-Fixed-Match.snap
@@ -1,6 +1,6 @@
 ---
 source: quil-rs/src/program/calibration.rs
-expression: calibrated_program.to_string()
+expression: calibrated_program.to_quil_or_debug()
 ---
 DEFCAL MEASURE addr:
 	PRAGMA INCORRECT_PRECEDENCE
@@ -8,9 +8,6 @@ DEFCAL MEASURE addr:
 DEFCAL MEASURE q addr:
 	PRAGMA INCORRECT_PRECEDENCE
 
-DEFCAL MEASURE 0 addr:
-	PRAGMA INCORRECT_ORDER
-
 DEFCAL MEASURE 0 addr:
 	PRAGMA CORRECT
 
diff --git a/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Precedence-No-Qubit-Match.snap b/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Precedence-No-Qubit-Match.snap
index 9e3c1c73..4c5c2d7d 100644
--- a/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Precedence-No-Qubit-Match.snap
+++ b/quil-rs/src/program/snapshots/quil_rs__program__calibration__tests__expansion@Precedence-No-Qubit-Match.snap
@@ -1,10 +1,7 @@
 ---
 source: quil-rs/src/program/calibration.rs
-expression: calibrated_program.to_string()
+expression: calibrated_program.to_quil_or_debug()
 ---
-DEFCAL MEASURE addr:
-	PRAGMA INCORRECT_PRECEDENCE
-
 DEFCAL MEASURE addr:
 	PRAGMA CORRECT