quil_rs/program/frame.rs
1// Copyright 2021 Rigetti Computing
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::collections::{HashMap, HashSet};
16
17use crate::instruction::{FrameAttributes, FrameDefinition, FrameIdentifier, Instruction, Qubit};
18
19/// A collection of Quil frames (`DEFFRAME` instructions) with utility methods.
20#[derive(Clone, Debug, Default, PartialEq, Eq)]
21pub struct FrameSet {
22 frames: HashMap<FrameIdentifier, FrameAttributes>,
23}
24
25impl FrameSet {
26 pub fn new() -> Self {
27 FrameSet {
28 frames: HashMap::new(),
29 }
30 }
31
32 /// Retrieve the attributes of a frame by its identifier.
33 pub fn get(&self, identifier: &FrameIdentifier) -> Option<&FrameAttributes> {
34 self.frames.get(identifier)
35 }
36
37 /// Return a list of all frame IDs described by this FrameSet.
38 pub fn get_keys(&self) -> Vec<&FrameIdentifier> {
39 self.frames.keys().collect()
40 }
41
42 pub(crate) fn get_matching_keys_for_conditions<'s>(
43 &'s self,
44 condition: FrameMatchConditions,
45 ) -> MatchedFrames<'s> {
46 let used = condition
47 .used
48 .map_or_else(HashSet::new, |c| self.get_matching_keys_for_condition(c));
49
50 let blocked = condition.blocked.map_or_else(HashSet::new, |c| {
51 let mut blocked = self.get_matching_keys_for_condition(c);
52
53 if !used.is_empty() {
54 blocked.retain(|&f| !used.contains(&f));
55 }
56
57 blocked
58 });
59
60 MatchedFrames { used, blocked }
61 }
62
63 /// Return all frames in the set which match all of these conditions. If a frame _would_ match, but is
64 /// not present in this [FrameSet], then it is not returned (notably, the [FrameMatchCondition::Specific]
65 /// match condition).
66 pub(crate) fn get_matching_keys_for_condition<'s>(
67 &'s self,
68 condition: FrameMatchCondition,
69 ) -> HashSet<&'s FrameIdentifier> {
70 let keys = self.frames.keys();
71
72 match condition {
73 FrameMatchCondition::All => keys.collect(),
74 FrameMatchCondition::AnyOfNames(names) => {
75 keys.filter(|&f| names.contains(f.name.as_str())).collect()
76 }
77 FrameMatchCondition::AnyOfQubits(qubits) => keys
78 .filter(|&f| f.qubits.iter().any(|q| qubits.contains(&q)))
79 .collect(),
80 FrameMatchCondition::ExactQubits(qubits) => keys
81 .filter(|&f| f.qubits.iter().collect::<HashSet<_>>() == qubits)
82 .collect(),
83 FrameMatchCondition::Specific(frame) => {
84 // This unusual pattern (fetch key & value by key, discard value) allows us to return
85 // a reference to `self` rather than `condition`, keeping lifetimes simpler.
86 if let Some((frame, _)) = self.frames.get_key_value(frame) {
87 HashSet::from([frame])
88 } else {
89 HashSet::new()
90 }
91 }
92 FrameMatchCondition::And(conditions) => conditions
93 .into_iter()
94 .map(|c| self.get_matching_keys_for_condition(c))
95 .reduce(|acc, el| acc.into_iter().filter(|&v| el.contains(v)).collect())
96 .unwrap_or_default(),
97 FrameMatchCondition::Or(conditions) => conditions
98 .into_iter()
99 .flat_map(|c| self.get_matching_keys_for_condition(c))
100 .collect(),
101 }
102 }
103
104 /// Insert a new frame by ID, overwriting any existing one.
105 pub fn insert(&mut self, identifier: FrameIdentifier, attributes: FrameAttributes) {
106 self.frames.insert(identifier, attributes);
107 }
108
109 /// Merge another [FrameSet] with this one, overwriting any existing keys
110 pub fn merge(&mut self, other: FrameSet) {
111 self.frames.extend(other.frames);
112 }
113
114 /// Return a new [FrameSet] which describes only the given [FrameIdentifier]s.
115 pub fn intersection(&self, identifiers: &HashSet<&FrameIdentifier>) -> Self {
116 let mut new_frameset = Self::new();
117
118 for (identifier, definition) in &self.frames {
119 if identifiers.contains(&identifier) {
120 new_frameset.insert(identifier.clone(), definition.clone())
121 }
122 }
123
124 new_frameset
125 }
126
127 /// Iterate through the contained frames.
128 pub fn iter(&self) -> std::collections::hash_map::Iter<'_, FrameIdentifier, FrameAttributes> {
129 self.frames.iter()
130 }
131
132 /// Return the number of frames described within.
133 pub fn len(&self) -> usize {
134 self.frames.len()
135 }
136
137 /// Return true if this describes no frames.
138 pub fn is_empty(&self) -> bool {
139 self.frames.is_empty()
140 }
141
142 /// Return the Quil instructions which describe the contained frames, consuming the [`FrameSet`].
143 pub fn into_instructions(self) -> Vec<Instruction> {
144 self.frames
145 .into_iter()
146 .map(|(identifier, attributes)| {
147 Instruction::FrameDefinition(FrameDefinition {
148 identifier,
149 attributes,
150 })
151 })
152 .collect()
153 }
154
155 /// Return the Quil instructions which describe the contained frames.
156 pub fn to_instructions(&self) -> Vec<Instruction> {
157 self.frames
158 .iter()
159 .map(|(identifier, attributes)| {
160 Instruction::FrameDefinition(FrameDefinition {
161 identifier: identifier.clone(),
162 attributes: attributes.clone(),
163 })
164 })
165 .collect()
166 }
167}
168
169#[derive(Debug)]
170pub(crate) enum FrameMatchCondition<'a> {
171 /// Match all frames in the set
172 All,
173
174 /// Match all frames which share any one of these names
175 AnyOfNames(HashSet<&'a str>),
176
177 /// Match all frames which contain any of these qubits
178 AnyOfQubits(HashSet<&'a Qubit>),
179
180 /// Match all frames which contain exactly these qubits
181 ExactQubits(HashSet<&'a Qubit>),
182
183 /// Return this specific frame, if present in the set
184 Specific(&'a FrameIdentifier),
185
186 /// Return all frames which match all of these conditions
187 And(Vec<FrameMatchCondition<'a>>),
188
189 /// Return all frames which match any of these conditions
190 Or(Vec<FrameMatchCondition<'a>>),
191}
192
193/// A pair of conditions to match frames within a [`crate::Program`] (or another scope).
194///
195/// This allows for deferred evaluation of matching an instruction against available frames.
196pub(crate) struct FrameMatchConditions<'a> {
197 /// A condition to identify which frames within a [`crate::Program`] (or another scope)
198 /// are actively used by an [`Instruction`].
199 ///
200 /// If `None`, then this [`Instruction`] does not use any frames, regardless of which are available.
201 pub used: Option<FrameMatchCondition<'a>>,
202
203 /// A condition to identify which frames within a [`crate::Program`] (or another scope)
204 /// are blocked by an [`Instruction`]. A "blocked" frame is one which is not used by the
205 /// `Instruction` but is not available for use by other instructions while this one executes.
206 ///
207 /// **Note**: for efficiency in computation, this may match frames also matched by `used`.
208 /// In order to query which frames are _blocked but not used_, both conditions must first
209 /// be evaluated in the scope of the available frames.
210 pub blocked: Option<FrameMatchCondition<'a>>,
211}
212
213/// The product of evaluating [`FrameMatchConditions`] in the scope of available frames (such as within a [`crate::Program`]).
214#[derive(Debug)]
215pub struct MatchedFrames<'a> {
216 /// Which concrete frames are blocked and not used.
217 /// This set is mutually exclusive with `used`.
218 pub blocked: HashSet<&'a FrameIdentifier>,
219
220 /// Which concrete frames are used by the [`Instruction`]
221 pub used: HashSet<&'a FrameIdentifier>,
222}
223
224impl<'a> MatchedFrames<'a> {
225 /// Which concrete frames are blocked and not used.
226 /// This set is mutually exclusive with `used`.
227 pub fn blocked(&self) -> &HashSet<&'a FrameIdentifier> {
228 &self.blocked
229 }
230
231 /// Which concrete frames are used by the [`Instruction`]
232 pub fn used(&self) -> &HashSet<&'a FrameIdentifier> {
233 &self.used
234 }
235}