use crate::error::ParseError;
use crate::gates;
use crate::Circuit;
use std::collections::HashMap;
use std::f64::consts::{FRAC_PI_2, FRAC_PI_4, PI};
const MAX_QUBITS: usize = 30;
pub fn parse(src: &str) -> Result<Circuit, ParseError> {
parse_inner(src).map_err(ParseError::new)
}
fn parse_inner(src: &str) -> Result<Circuit, String> {
let clean = strip_comments(src);
let statements = split_statements(&clean)?;
let mut regs: HashMap<String, Reg> = HashMap::new();
let mut total = 0usize;
for stmt in &statements {
if keyword(stmt) == "qreg" {
let (name, size) = parse_reg_decl(stmt)?;
if regs.contains_key(&name) {
return Err(format!("duplicate register `{name}`"));
}
if size > MAX_QUBITS || total + size > MAX_QUBITS {
return Err(format!(
"register total exceeds the maximum of {MAX_QUBITS} qubits"
));
}
regs.insert(
name,
Reg {
offset: total,
size,
},
);
total += size;
}
}
if total == 0 {
return Err("no `qreg` declared".to_string());
}
let mut circuit = Circuit::new(total);
let mut cregs: HashMap<String, Reg> = HashMap::new();
let mut clbits = 0usize;
for stmt in &statements {
if keyword(stmt) == "creg" {
let (name, size) = parse_reg_decl(stmt.replacen("creg", "qreg", 1).as_str())?;
if cregs.contains_key(&name) {
return Err(format!("duplicate classical register `{name}`"));
}
if clbits + size > total {
return Err(format!(
"classical registers total {} bits, more than the {total} qubits this \
engine models",
clbits + size
));
}
cregs.insert(
name,
Reg {
offset: clbits,
size,
},
);
clbits += size;
}
}
let mut defs: HashMap<String, GateDef> = HashMap::new();
for stmt in &statements {
if keyword(stmt) == "gate" {
let (name, def) = parse_gate_def(stmt)?;
if defs.contains_key(&name) {
return Err(format!("duplicate `gate {name}` declaration"));
}
defs.insert(name, def);
}
}
let mut budget = MAX_EXPANDED_OPS;
for stmt in &statements {
match keyword(stmt) {
"OPENQASM" | "include" | "qreg" | "creg" | "barrier" | "gate" => continue,
"measure" => apply_measure(&mut circuit, stmt, ®s, &cregs)?,
"reset" => apply_reset(&mut circuit, stmt, ®s)?,
"if" => apply_if(&mut circuit, stmt, ®s, &cregs, &defs, &mut budget)?,
"opaque" => {
return Err(format!("unsupported OpenQASM feature `{}`", keyword(stmt)));
}
_ => apply_gate(&mut circuit, stmt, ®s, &defs, &mut budget)?,
}
}
Ok(circuit)
}
pub(crate) fn split_statements(src: &str) -> Result<Vec<&str>, String> {
let mut statements = Vec::new();
let mut depth = 0usize;
let mut start = 0usize;
for (i, c) in src.char_indices() {
match c {
'{' => depth += 1,
'}' => {
depth = depth
.checked_sub(1)
.ok_or_else(|| "unexpected `}`".to_string())?;
if depth == 0 {
statements.push(&src[start..=i]);
start = i + c.len_utf8();
}
}
';' if depth == 0 => {
statements.push(&src[start..i]);
start = i + c.len_utf8();
}
_ => {}
}
}
if depth != 0 {
return Err("unterminated `{` (missing `}`)".to_string());
}
statements.push(&src[start..]);
Ok(statements
.into_iter()
.map(str::trim)
.filter(|s| !s.is_empty())
.collect())
}
struct Reg {
offset: usize,
size: usize,
}
fn keyword(stmt: &str) -> &str {
stmt.split(|c: char| c.is_whitespace() || c == '(' || c == '[')
.next()
.unwrap_or("")
}
fn parse_reg_decl(stmt: &str) -> Result<(String, usize), String> {
let rest = stmt
.strip_prefix("qreg")
.ok_or_else(|| format!("malformed register declaration `{stmt}`"))?
.trim();
let open = rest
.find('[')
.ok_or_else(|| format!("register declaration needs a size: `{stmt}`"))?;
let close = rest
.find(']')
.ok_or_else(|| format!("register declaration needs `]`: `{stmt}`"))?;
if close < open {
return Err(format!("malformed register declaration `{stmt}`"));
}
let name = rest[..open].trim().to_string();
if name.is_empty() {
return Err(format!("register needs a name: `{stmt}`"));
}
let size: usize = rest[open + 1..close]
.trim()
.parse()
.map_err(|_| format!("invalid register size in `{stmt}`"))?;
if size == 0 {
return Err(format!("register size must be >= 1: `{stmt}`"));
}
Ok((name, size))
}
struct GateDef {
params: Vec<String>,
qargs: Vec<String>,
body: Vec<String>,
}
const MAX_GATE_DEPTH: usize = 64;
const MAX_EXPANDED_OPS: usize = 100_000;
fn parse_gate_def(stmt: &str) -> Result<(String, GateDef), String> {
let rest = stmt
.strip_prefix("gate")
.ok_or_else(|| format!("malformed gate declaration `{stmt}`"))?;
let open = rest
.find('{')
.ok_or_else(|| format!("gate declaration needs a `{{ ... }}` body: `{stmt}`"))?;
let close = rest
.rfind('}')
.ok_or_else(|| format!("gate declaration needs `}}`: `{stmt}`"))?;
if close < open {
return Err(format!("malformed gate declaration `{stmt}`"));
}
let (head, qargs_str) = split_head(rest[..open].trim());
let (name, params) = parse_head(head);
if name.is_empty() {
return Err(format!("gate declaration needs a name: `{stmt}`"));
}
let params = parse_identifiers(params.unwrap_or(""), "parameter", stmt)?;
let qargs = parse_identifiers(qargs_str, "qubit argument", stmt)?;
if qargs.is_empty() {
return Err(format!("`gate {name}` needs at least one qubit argument"));
}
let body = rest[open + 1..close]
.split(';')
.map(str::trim)
.filter(|s| !s.is_empty())
.map(str::to_string)
.collect();
Ok((
name.to_string(),
GateDef {
params,
qargs,
body,
},
))
}
fn apply_measure(
circuit: &mut Circuit,
stmt: &str,
regs: &HashMap<String, Reg>,
cregs: &HashMap<String, Reg>,
) -> Result<(), String> {
let rest = stmt
.strip_prefix("measure")
.ok_or_else(|| format!("malformed measurement `{stmt}`"))?;
let (source, dest) = rest
.split_once("->")
.ok_or_else(|| format!("measurement needs `-> target`: `{stmt}`"))?;
if dest.trim().is_empty() {
return Err(format!("measurement needs a classical target: `{stmt}`"));
}
let qubits = resolve_qubits(source.trim(), regs, stmt)?;
let clbits = resolve_qubits(dest.trim(), cregs, stmt)?;
if qubits.len() != clbits.len() {
return Err(format!(
"measurement maps {} qubit(s) onto {} classical bit(s) in `{stmt}`",
qubits.len(),
clbits.len()
));
}
for (qubit, clbit) in qubits.into_iter().zip(clbits) {
circuit.measure_into(qubit, clbit);
}
Ok(())
}
fn apply_if(
circuit: &mut Circuit,
stmt: &str,
regs: &HashMap<String, Reg>,
cregs: &HashMap<String, Reg>,
defs: &HashMap<String, GateDef>,
budget: &mut usize,
) -> Result<(), String> {
let rest = stmt
.strip_prefix("if")
.ok_or_else(|| format!("malformed conditional `{stmt}`"))?
.trim_start();
let close = rest
.find(')')
.ok_or_else(|| format!("conditional needs `(c==value)`: `{stmt}`"))?;
let condition = rest[..close].trim_start_matches('(').trim();
let (name, value) = condition
.split_once("==")
.ok_or_else(|| format!("conditional must compare with `==`: `{stmt}`"))?;
let name = name.trim();
if !cregs.contains_key(name) {
return Err(format!("unknown classical register `{name}` in `{stmt}`"));
}
let value: u64 = value
.trim()
.parse()
.map_err(|_| format!("conditional value must be a non-negative integer: `{stmt}`"))?;
let guarded = rest[close + 1..].trim();
if guarded.is_empty() {
return Err(format!("conditional has no statement: `{stmt}`"));
}
match keyword(guarded) {
"measure" | "reset" | "if" => {
return Err(format!(
"only a gate may be conditional, not `{}`, in `{stmt}`",
keyword(guarded)
))
}
_ => {}
}
let mut block = Circuit::new(circuit.n_qubits());
apply_gate(&mut block, guarded, regs, defs, budget)?;
circuit.if_classical_eq(value, |c| c.extend_from(&block));
Ok(())
}
fn apply_reset(
circuit: &mut Circuit,
stmt: &str,
regs: &HashMap<String, Reg>,
) -> Result<(), String> {
let target = stmt
.strip_prefix("reset")
.ok_or_else(|| format!("malformed reset `{stmt}`"))?
.trim();
for qubit in resolve_qubits(target, regs, stmt)? {
circuit.reset(qubit);
}
Ok(())
}
fn resolve_qubits(
operand: &str,
regs: &HashMap<String, Reg>,
stmt: &str,
) -> Result<Vec<usize>, String> {
if operand.is_empty() {
return Err(format!("expected a qubit in `{stmt}`"));
}
if operand.contains('[') {
let qubits = parse_operands(operand, regs)?;
if qubits.len() != 1 {
return Err(format!(
"expected one qubit, got {} in `{stmt}`",
qubits.len()
));
}
return Ok(qubits);
}
let reg = regs
.get(operand)
.ok_or_else(|| format!("unknown register `{operand}` in `{stmt}`"))?;
Ok((0..reg.size).map(|i| reg.offset + i).collect())
}
fn parse_identifiers(list: &str, kind: &str, stmt: &str) -> Result<Vec<String>, String> {
let list = list.trim();
if list.is_empty() {
return Ok(Vec::new());
}
let mut names = Vec::new();
for raw in list.split(',') {
let name = raw.trim();
let is_identifier = !name.is_empty()
&& name.starts_with(|c: char| c.is_ascii_alphabetic() || c == '_')
&& name.chars().all(|c| c.is_ascii_alphanumeric() || c == '_');
if !is_identifier {
return Err(format!("invalid {kind} `{name}` in `{stmt}`"));
}
if names.iter().any(|n| n == name) {
return Err(format!("duplicate {kind} `{name}` in `{stmt}`"));
}
names.push(name.to_string());
}
Ok(names)
}
fn parse_angle_list(
params: Option<&str>,
vars: &HashMap<String, f64>,
stmt: &str,
) -> Result<Vec<f64>, String> {
match params {
Some(p) if !p.trim().is_empty() => p
.split(',')
.map(|a| crate::expr::eval(a.trim(), vars))
.collect::<Result<_, _>>()
.map_err(|e| format!("{e} in `{stmt}`")),
_ => Ok(Vec::new()),
}
}
fn apply_gate(
circuit: &mut Circuit,
stmt: &str,
regs: &HashMap<String, Reg>,
defs: &HashMap<String, GateDef>,
budget: &mut usize,
) -> Result<(), String> {
let (head, operands_str) = split_head(stmt);
let (name, params) = parse_head(head);
let q = parse_operands(operands_str, regs)?;
let angles = parse_angle_list(params, &HashMap::new(), stmt)?;
apply_resolved(circuit, name, &angles, &q, defs, budget, 0, stmt)
}
#[allow(clippy::too_many_arguments)]
fn apply_resolved(
circuit: &mut Circuit,
name: &str,
angles: &[f64],
q: &[usize],
defs: &HashMap<String, GateDef>,
budget: &mut usize,
depth: usize,
stmt: &str,
) -> Result<(), String> {
if let Some(def) = defs.get(name) {
return expand_user_gate(circuit, name, def, angles, q, defs, budget, depth, stmt);
}
*budget = budget.checked_sub(1).ok_or_else(|| {
format!("program expands to more than {MAX_EXPANDED_OPS} gates; is a `gate` recursive?")
})?;
apply_builtin(circuit, name, angles, q, stmt)
}
#[allow(clippy::too_many_arguments)]
fn expand_user_gate(
circuit: &mut Circuit,
name: &str,
def: &GateDef,
angles: &[f64],
q: &[usize],
defs: &HashMap<String, GateDef>,
budget: &mut usize,
depth: usize,
stmt: &str,
) -> Result<(), String> {
if depth >= MAX_GATE_DEPTH {
return Err(format!(
"`gate` calls nested more than {MAX_GATE_DEPTH} deep at `{name}`; is it recursive?"
));
}
if def.params.len() != angles.len() || def.qargs.len() != q.len() {
return Err(format!(
"`{name}` takes {} qubit(s) and {} angle(s), got {} and {} in `{stmt}`",
def.qargs.len(),
def.params.len(),
q.len(),
angles.len()
));
}
let vars: HashMap<String, f64> = def
.params
.iter()
.cloned()
.zip(angles.iter().copied())
.collect();
let qubits: HashMap<&str, usize> = def
.qargs
.iter()
.map(String::as_str)
.zip(q.iter().copied())
.collect();
for body_stmt in &def.body {
let (head, operands_str) = split_head(body_stmt);
let (body_name, body_params) = parse_head(head);
if body_name == "barrier" {
continue;
}
let body_angles = parse_angle_list(body_params, &vars, body_stmt)?;
let body_qubits = operands_str
.split(',')
.map(str::trim)
.filter(|s| !s.is_empty())
.map(|operand| {
qubits.get(operand).copied().ok_or_else(|| {
format!("`{operand}` is not a qubit argument of `{name}` in `{body_stmt}`")
})
})
.collect::<Result<Vec<_>, _>>()?;
apply_resolved(
circuit,
body_name,
&body_angles,
&body_qubits,
defs,
budget,
depth + 1,
body_stmt,
)?;
}
Ok(())
}
fn apply_builtin(
circuit: &mut Circuit,
name: &str,
angles: &[f64],
q: &[usize],
stmt: &str,
) -> Result<(), String> {
let want = |nq: usize, na: usize| -> Result<(), String> {
if q.len() != nq {
return Err(format!(
"`{name}` takes {nq} qubit(s), got {} in `{stmt}`",
q.len()
));
}
if angles.len() != na {
return Err(format!(
"`{name}` takes {na} angle(s), got {} in `{stmt}`",
angles.len()
));
}
Ok(())
};
match name {
"id" => {
want(1, 0)?;
circuit.id(q[0]);
}
"x" => {
want(1, 0)?;
circuit.x(q[0]);
}
"y" => {
want(1, 0)?;
circuit.y(q[0]);
}
"z" => {
want(1, 0)?;
circuit.z(q[0]);
}
"h" => {
want(1, 0)?;
circuit.h(q[0]);
}
"s" => {
want(1, 0)?;
circuit.s(q[0]);
}
"t" => {
want(1, 0)?;
circuit.t(q[0]);
}
"sdg" => {
want(1, 0)?;
circuit.sdg(q[0]);
}
"tdg" => {
want(1, 0)?;
circuit.tdg(q[0]);
}
"u1" | "p" => {
want(1, 1)?;
circuit.p(angles[0], q[0]);
}
"u2" => {
want(1, 2)?;
circuit.u2(angles[0], angles[1], q[0]);
}
"u3" | "U" => {
want(1, 3)?;
circuit.u3(angles[0], angles[1], angles[2], q[0]);
}
"rx" => {
want(1, 1)?;
circuit.rx(angles[0], q[0]);
}
"ry" => {
want(1, 1)?;
circuit.ry(angles[0], q[0]);
}
"rz" => {
want(1, 1)?;
circuit.rz(angles[0], q[0]);
}
"cx" | "CX" => {
want(2, 0)?;
require_distinct(q, stmt)?;
circuit.cnot(q[0], q[1]);
}
"cy" => {
want(2, 0)?;
require_distinct(q, stmt)?;
circuit.cy(q[0], q[1]);
}
"cz" => {
want(2, 0)?;
require_distinct(q, stmt)?;
circuit.cz(q[0], q[1]);
}
"ch" => {
want(2, 0)?;
require_distinct(q, stmt)?;
circuit.ch(q[0], q[1]);
}
"crz" => {
want(2, 1)?;
require_distinct(q, stmt)?;
circuit.crz(angles[0], q[0], q[1]);
}
"cu1" | "cp" => {
want(2, 1)?;
require_distinct(q, stmt)?;
circuit.cp(angles[0], q[0], q[1]);
}
"cu3" => {
want(2, 3)?;
require_distinct(q, stmt)?;
circuit.cu3(angles[0], angles[1], angles[2], q[0], q[1]);
}
"swap" => {
want(2, 0)?;
require_distinct(q, stmt)?;
circuit.swap(q[0], q[1]);
}
"cswap" => {
want(3, 0)?;
require_distinct(q, stmt)?;
circuit.cswap(q[0], q[1], q[2]);
}
"ccx" => {
want(3, 0)?;
require_distinct(q, stmt)?;
circuit.toffoli(q[0], q[1], q[2]);
}
"u" => {
want(1, 3)?;
circuit.u3(angles[0], angles[1], angles[2], q[0]);
}
"u0" => {
want(1, 1)?;
circuit.id(q[0]);
}
"sx" => {
want(1, 0)?;
circuit.sx(q[0]);
}
"sxdg" => {
want(1, 0)?;
circuit.sxdg(q[0]);
}
"crx" => {
want(2, 1)?;
require_distinct(q, stmt)?;
circuit.cu(gates::rx(angles[0]), q[0], q[1]);
}
"cry" => {
want(2, 1)?;
require_distinct(q, stmt)?;
circuit.cu(gates::ry(angles[0]), q[0], q[1]);
}
"csx" => {
want(2, 0)?;
require_distinct(q, stmt)?;
circuit.cu(gates::sx(), q[0], q[1]);
}
"cu" => {
want(2, 4)?;
require_distinct(q, stmt)?;
circuit.p(angles[3], q[0]);
circuit.cu3(angles[0], angles[1], angles[2], q[0], q[1]);
}
"rxx" => {
want(2, 1)?;
require_distinct(q, stmt)?;
let theta = angles[0];
circuit.u3(FRAC_PI_2, theta, 0.0, q[0]).h(q[1]);
circuit.cnot(q[0], q[1]).p(-theta, q[1]).cnot(q[0], q[1]);
circuit.h(q[1]).u2(-PI, PI - theta, q[0]);
}
"rzz" => {
want(2, 1)?;
require_distinct(q, stmt)?;
circuit.cnot(q[0], q[1]).p(angles[0], q[1]).cnot(q[0], q[1]);
}
"rccx" => {
want(3, 0)?;
require_distinct(q, stmt)?;
let (a, b, c) = (q[0], q[1], q[2]);
circuit.u2(0.0, PI, c).p(FRAC_PI_4, c);
circuit.cnot(b, c).p(-FRAC_PI_4, c);
circuit.cnot(a, c).p(FRAC_PI_4, c);
circuit.cnot(b, c).p(-FRAC_PI_4, c);
circuit.u2(0.0, PI, c);
}
"rc3x" => {
want(4, 0)?;
require_distinct(q, stmt)?;
let (a, b, c, d) = (q[0], q[1], q[2], q[3]);
circuit.u2(0.0, PI, d).p(FRAC_PI_4, d);
circuit.cnot(c, d).p(-FRAC_PI_4, d).u2(0.0, PI, d);
circuit.cnot(a, d).p(FRAC_PI_4, d);
circuit.cnot(b, d).p(-FRAC_PI_4, d);
circuit.cnot(a, d).p(FRAC_PI_4, d);
circuit.cnot(b, d).p(-FRAC_PI_4, d);
circuit.u2(0.0, PI, d).p(FRAC_PI_4, d);
circuit.cnot(c, d).p(-FRAC_PI_4, d).u2(0.0, PI, d);
}
"c3x" => {
want(4, 0)?;
require_distinct(q, stmt)?;
circuit.mcx(&q[..3], q[3]);
}
"c3sqrtx" => {
want(4, 0)?;
require_distinct(q, stmt)?;
circuit.mcu(gates::sx(), &q[..3], q[3]);
}
"c4x" => {
want(5, 0)?;
require_distinct(q, stmt)?;
circuit.mcx(&q[..4], q[4]);
}
other => return Err(format!("unsupported gate `{other}` in `{stmt}`")),
}
Ok(())
}
fn require_distinct(q: &[usize], stmt: &str) -> Result<(), String> {
for i in 0..q.len() {
for j in (i + 1)..q.len() {
if q[i] == q[j] {
return Err(format!("operands must be distinct qubits: `{stmt}`"));
}
}
}
Ok(())
}
fn split_head(stmt: &str) -> (&str, &str) {
let mut depth = 0i32;
for (i, c) in stmt.char_indices() {
match c {
'(' => depth += 1,
')' => depth -= 1,
_ if c.is_whitespace() && depth == 0 => {
return (stmt[..i].trim(), stmt[i..].trim());
}
_ => {}
}
}
(stmt.trim(), "")
}
fn parse_head(head: &str) -> (&str, Option<&str>) {
match (head.find('('), head.rfind(')')) {
(Some(open), Some(close)) if close > open => {
(head[..open].trim(), Some(head[open + 1..close].trim()))
}
_ => (head.trim(), None),
}
}
fn parse_operands(operands: &str, regs: &HashMap<String, Reg>) -> Result<Vec<usize>, String> {
if operands.trim().is_empty() {
return Ok(Vec::new());
}
operands
.split(',')
.map(|op| parse_qubit_ref(op.trim(), regs))
.collect()
}
fn parse_qubit_ref(op: &str, regs: &HashMap<String, Reg>) -> Result<usize, String> {
let open = op
.find('[')
.ok_or_else(|| format!("expected a qubit reference like `q[0]`, got `{op}`"))?;
let close = op
.find(']')
.ok_or_else(|| format!("qubit reference missing `]`: `{op}`"))?;
if close < open {
return Err(format!("malformed qubit reference `{op}`"));
}
let name = op[..open].trim();
let index: usize = op[open + 1..close]
.trim()
.parse()
.map_err(|_| format!("invalid qubit index in `{op}`"))?;
let reg = regs
.get(name)
.ok_or_else(|| format!("unknown register `{name}`"))?;
if index >= reg.size {
return Err(format!(
"qubit {name}[{index}] out of range (register size {})",
reg.size
));
}
Ok(reg.offset + index)
}
pub(crate) fn strip_comments(src: &str) -> String {
let mut out = String::with_capacity(src.len());
let mut chars = src.chars().peekable();
let mut in_block = false;
while let Some(c) = chars.next() {
if in_block {
if c == '*' && chars.peek() == Some(&'/') {
chars.next();
in_block = false;
}
continue;
}
if c == '/' {
match chars.peek() {
Some('*') => {
chars.next();
in_block = true;
continue;
}
Some('/') => {
for nc in chars.by_ref() {
if nc == '\n' {
out.push('\n');
break;
}
}
continue;
}
_ => {}
}
}
out.push(c);
}
out
}