GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
fc18cc36fceb28438976110616dfee7b8b01bd85

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/compiler/qsc_stim_parser/src

source/compiler/qsc_stim_parser/src/parser.rs

379lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4use crate::lex::Delim::Brace;
5use crate::lex::Delim::Paren;
6use crate::lex::Lexer;
7use crate::lex::Token;
8use crate::lex::TokenKind;
9use qsc_data_structures::span::Span;
10use std::{iter::Peekable, str::FromStr};
11
12#[derive(Debug)]
13pub struct Circuit {
14 pub span: Span,
15 pub items: Vec<Item>,
16}
17
18#[derive(Debug)]
19pub enum Item {
20 Line(Line),
21 Block(Block),
22}
23
24#[derive(Debug)]
25pub struct Line {
26 pub span: Span,
27 pub instruction: Instruction,
28}
29
30#[derive(Debug)]
31pub struct Block {
32 pub span: Span,
33 pub block_instruction: Instruction, // currently, only the "REPEAT" instruction is supported
34 pub items: Vec<Item>,
35}
36
37#[derive(Debug)]
38pub struct Instruction {
39 pub span: Span,
40 pub name: String,
41 pub tag: Option<String>,
42 pub args: Vec<f64>,
43 pub targets: Vec<Target>,
44}
45
46#[derive(Debug)]
47pub struct Target {
48 pub span: Span,
49 pub kind: TargetKind,
50}
51
52#[derive(Debug)]
53pub enum TargetKind {
54 Qubit {
55 negated: bool,
56 value: u32,
57 },
58 MeasurementRecord {
59 value: u32,
60 },
61 SweepBit {
62 value: u32,
63 },
64 Pauli {
65 negated: bool,
66 pauli: Pauli,
67 value: u32,
68 },
69 Combiner,
70}
71
72#[derive(Debug)]
73pub enum Pauli {
74 X,
75 Y,
76 Z,
77}
78
79impl FromStr for Pauli {
80 type Err = ();
81
82 fn from_str(s: &str) -> Result<Self, Self::Err> {
83 match s {
84 "X" => Ok(Pauli::X),
85 "Y" => Ok(Pauli::Y),
86 "Z" => Ok(Pauli::Z),
87 _ => Err(()),
88 }
89 }
90}
91
92pub fn parse(input: &str) -> Circuit {
93 Parser::new(input).parse()
94}
95
96struct Parser<'a> {
97 input: &'a str,
98 tokens: Peekable<Lexer<'a>>,
99}
100
101impl<'a> Parser<'a> {
102 pub fn new(input: &'a str) -> Self {
103 Self {
104 input,
105 tokens: Lexer::new(input).peekable(),
106 }
107 }
108
109 pub fn expect(&mut self, kind: TokenKind) -> Token {
110 let token = self.tokens.next().expect("expected token");
111 if token.kind != kind {
112 panic!("expected token of kind {:?}", kind);
113 }
114 token
115 }
116
117 fn expect_number(&mut self) -> Token {
118 let token = self.tokens.next().expect("expected number");
119 if token.kind != TokenKind::Uint && token.kind != TokenKind::Double {
120 panic!("expected number, got {:?}", token.kind);
121 }
122 token
123 }
124
125 pub fn parse(&mut self) -> Circuit {
126 let input_len = self
127 .input
128 .len()
129 .try_into()
130 .expect("input length should fit into u32");
131
132 let mut items = Vec::new();
133 while let Some(item) = self.parse_item() {
134 items.push(item);
135 }
136
137 Circuit {
138 span: Span {
139 lo: 0,
140 hi: input_len,
141 },
142 items,
143 }
144 }
145
146 fn parse_item(&mut self) -> Option<Item> {
147 // Skip any leading newlines
148 while self
149 .tokens
150 .peek()
151 .is_some_and(|t| t.kind == TokenKind::Newline)
152 {
153 self.tokens.next();
154 }
155
156 if let TokenKind::InstructionName = self.tokens.peek()?.kind {
157 // Could be the start of a block or of a line
158 let instruction = self.parse_instruction();
159 if let Some(token) = self.tokens.peek()
160 && token.kind == TokenKind::Open(Brace)
161 {
162 return Some(Item::Block(self.parse_block(instruction)));
163 }
164
165 Some(Item::Line(self.parse_line(instruction)))
166 } else {
167 // TODO error! The start of every item should be an instruction;
168 None
169 }
170 }
171
172 fn parse_block(&mut self, instruction: Instruction) -> Block {
173 let lo = instruction.span.lo;
174 let mut items = Vec::new();
175 self.expect(TokenKind::Open(Brace));
176 self.expect(TokenKind::Newline);
177 loop {
178 if self
179 .tokens
180 .peek()
181 .is_some_and(|t| t.kind == TokenKind::Close(Brace))
182 {
183 break;
184 }
185 match self.parse_item() {
186 Some(item) => items.push(item),
187 None => break,
188 }
189 }
190 let closing_brace = self.expect(TokenKind::Close(Brace));
191 self.expect(TokenKind::Newline);
192 let hi = closing_brace.span.hi;
193 Block {
194 span: Span { lo, hi },
195 block_instruction: instruction,
196 items,
197 }
198 }
199
200 fn parse_line(&mut self, instruction: Instruction) -> Line {
201 self.expect(TokenKind::Newline);
202 Line {
203 span: instruction.span,
204 instruction,
205 }
206 }
207
208 fn parse_instruction(&mut self) -> Instruction {
209 let name_token = self.expect(TokenKind::InstructionName);
210 let lo = name_token.span.lo;
211 let name = self.extract_string(name_token, None);
212
213 let tag_token = self.tokens.next_if(|t| t.kind == TokenKind::Tag);
214 let tag: Option<String> = tag_token.map(|tag_token| {
215 self.extract_string(
216 tag_token,
217 Some(Span {
218 lo: tag_token.span.lo + 1,
219 hi: tag_token.span.hi - 1,
220 }),
221 )
222 });
223
224 let mut args = Vec::new();
225 let mut targets = Vec::new();
226
227 if self
228 .tokens
229 .peek()
230 .is_some_and(|t| t.kind == TokenKind::Open(Paren))
231 {
232 self.expect(TokenKind::Open(Paren)); // consume '('
233 // Parse first arg (no leading comma)
234 if self
235 .tokens
236 .peek()
237 .is_some_and(|t| t.kind != TokenKind::Close(Paren))
238 {
239 let arg = self.expect_number();
240 args.push(self.extract_double(arg, None));
241 }
242 // Each subsequent arg must be preceded by a comma
243 while self
244 .tokens
245 .peek()
246 .is_some_and(|t| t.kind != TokenKind::Close(Paren))
247 {
248 self.expect(TokenKind::Comma);
249 let arg = self.expect_number();
250 args.push(self.extract_double(arg, None));
251 }
252 self.expect(TokenKind::Close(Paren));
253 }
254
255 while let Some(&token) = self.tokens.peek() {
256 if !self.is_target_start(&token) {
257 break;
258 }
259 targets.push(self.parse_target());
260 }
261
262 let hi = targets
263 .last()
264 .map(|t| t.span.hi)
265 .unwrap_or(name_token.span.hi);
266
267 Instruction {
268 span: Span { lo, hi },
269 name,
270 tag,
271 args,
272 targets,
273 }
274 }
275
276 fn is_target_start(&self, token: &Token) -> bool {
277 match token.kind {
278 TokenKind::Uint
279 | TokenKind::Rec
280 | TokenKind::Sweep
281 | TokenKind::Bang
282 | TokenKind::Star => true,
283 TokenKind::InstructionName => {
284 let text = self.extract_string(*token, None);
285 text.starts_with('X') || text.starts_with('Y') || text.starts_with('Z') // STARTS WITH PAULI
286 }
287 _ => false,
288 }
289 }
290
291 fn parse_target(&mut self) -> Target {
292 let negated_token = self.tokens.next_if(|t| t.kind == TokenKind::Bang);
293 let negated = negated_token.is_some();
294 let first_token = self.tokens.next().expect("target empty");
295 let lo = negated_token.map_or(first_token.span.lo, |t| t.span.lo);
296 let span = Span {
297 lo,
298 hi: first_token.span.hi,
299 };
300
301 match first_token.kind {
302 TokenKind::Uint => Target {
303 span,
304 kind: TargetKind::Qubit {
305 negated,
306 value: self.extract_uint(first_token, None),
307 },
308 },
309 TokenKind::InstructionName => Target {
310 span,
311 kind: TargetKind::Pauli {
312 negated,
313 pauli: self
314 .extract_string(
315 first_token,
316 Some(Span {
317 lo: span.lo,
318 hi: span.lo + 1,
319 }),
320 )
321 .parse::<Pauli>()
322 .unwrap(),
323 value: self.extract_uint(
324 first_token,
325 Some(Span {
326 lo: span.lo + 1,
327 hi: span.hi,
328 }),
329 ),
330 },
331 }, // Already validated
332 TokenKind::Rec => Target {
333 span,
334 kind: TargetKind::MeasurementRecord {
335 value: self.extract_uint(
336 first_token,
337 Some(Span {
338 lo: span.lo + 5,
339 hi: span.hi - 1,
340 }),
341 ), // Strips 'rec[-' prefix and trailing ']' TODO validate it
342 },
343 },
344 TokenKind::Sweep => Target {
345 span,
346 kind: TargetKind::SweepBit {
347 value: self.extract_uint(
348 first_token,
349 Some(Span {
350 lo: span.lo + 6,
351 hi: span.hi - 1,
352 }),
353 ),
354 }, // Strips 'sweep[' prefix and trailing ']' TODO validate it
355 },
356 TokenKind::Star => Target {
357 span,
358 kind: TargetKind::Combiner,
359 },
360 _ => panic!("Unexpected target kind"),
361 }
362 }
363
364 fn extract_uint(&mut self, token: Token, span: Option<Span>) -> u32 {
365 self.extract_string(token, span).parse().unwrap()
366 }
367
368 fn extract_double(&mut self, token: Token, span: Option<Span>) -> f64 {
369 self.extract_string(token, span).parse().unwrap()
370 }
371
372 fn extract_string(&self, token: Token, span: Option<Span>) -> String {
373 if let Some(span) = span {
374 self.input[span.lo as usize..span.hi as usize].to_string()
375 } else {
376 self.input[token.span.lo as usize..token.span.hi as usize].to_string()
377 }
378 }
379}