libqasm
library for handling cQASM files
cqasm-v1-analyzer.cpp
Go to the documentation of this file.
1 
5 #define _USE_MATH_DEFINES
6 #include <unordered_set>
7 #include <cctype>
8 #include <cmath>
9 #include <list>
10 #include <map>
11 #include <utility>
12 #include "cqasm-utils.hpp"
13 #include "cqasm-v1-analyzer.hpp"
16 
17 namespace cqasm {
18 namespace v1 {
19 namespace analyzer {
20 
28  if (errors.empty()) {
29  return root;
30  }
31  for (const auto &error : errors) {
32  out << error << std::endl;
33  }
34  throw AnalysisFailed();
35 }
36 
40 Analyzer::Analyzer(const std::string &api_version)
41  : api_version(api_version), resolve_instructions(false), resolve_error_model(false)
42 {
43  if (api_version.compare("1.2") > 0) {
44  throw std::invalid_argument("this analyzer only supports up to cQASM 1.2");
45  }
46 }
47 
52  : api_version(api_version), resolve_instructions(false), resolve_error_model(false)
53 {
54  if (api_version.compare("1.2") > 0) {
55  throw std::invalid_argument("this analyzer only supports up to cQASM 1.2");
56  }
57 }
58 
59 
63 void Analyzer::register_mapping(const std::string &name, const values::Value &value) {
64  mappings.add(name, value);
65 }
66 
71  const std::string &name,
72  const types::Types &param_types,
73  const resolver::FunctionImpl &impl
74 ) {
75  functions.add(name, param_types, impl);
76 }
77 
84  const std::string &name,
85  const std::string &param_types,
86  const resolver::FunctionImpl &impl
87 ) {
88  functions.add(name, types::from_spec(param_types), impl);
89 }
90 
97  register_mapping("x", tree::make<values::ConstAxis>(primitives::Axis::X));
98  register_mapping("y", tree::make<values::ConstAxis>(primitives::Axis::Y));
99  register_mapping("z", tree::make<values::ConstAxis>(primitives::Axis::Z));
100  register_mapping("true", tree::make<values::ConstBool>(true));
101  register_mapping("false", tree::make<values::ConstBool>(false));
102  register_mapping("pi", tree::make<values::ConstReal>(M_PI));
103  register_mapping("eu", tree::make<values::ConstReal>(M_E));
104  register_mapping("im", tree::make<values::ConstComplex>(primitives::Complex(0.0, 1.0)));
105  functions::register_into(functions);
106 }
107 
115  resolve_instructions = true;
116  instruction_set.add(instruction);
117 }
118 
124  const std::string &name,
125  const std::string &param_types,
126  bool allow_conditional,
127  bool allow_parallel,
128  bool allow_reused_qubits,
129  bool allow_different_index_sizes
130 ) {
132  name, param_types, allow_conditional, allow_parallel,
133  allow_reused_qubits, allow_different_index_sizes));
134 }
135 
143  resolve_error_model = true;
144  error_models.add(error_model);
145 }
146 
152  const std::string &name,
153  const std::string &param_types
154 ) {
155  register_error_model(error_model::ErrorModel(name, param_types));
156 }
157 
161 class Scope {
162 public:
163 
168 
173 
178 
186 
193 
198  const resolver::MappingTable &mappings,
199  const resolver::FunctionTable &functions,
200  const resolver::InstructionTable &instruction_set
201  ) :
202  mappings(mappings),
203  functions(functions),
204  instruction_set(instruction_set),
205  block(),
206  within_loop(false)
207  {}
208 
209 };
210 
216 public:
217 
222 
227 
231  std::list<Scope> scope_stack;
232 
237  std::list<std::pair<tree::Maybe<semantic::GotoInstruction>, std::string>> gotos;
238 
242  AnalyzerHelper(const Analyzer &analyzer, const ast::Program &ast);
243 
248  void analyze_version(const ast::Version &ast);
249 
254  void analyze_qubits(const ast::Expression &count);
255 
261  tree::Maybe<semantic::Subcircuit> get_current_subcircuit(const tree::Annotatable &source);
262 
266  Scope &get_current_scope();
267 
271  Scope &get_global_scope();
272 
276  tree::Maybe<semantic::Block> get_current_block(const tree::Annotatable &source);
277 
281  void add_to_current_block(const tree::Maybe<semantic::Statement> &stmt);
282 
287  void analyze_statements(const ast::StatementList &statements);
288 
294  tree::Maybe<semantic::Block> analyze_subblock(const ast::StatementList &statements, bool is_loop);
295 
301  void analyze_bundle(const ast::Bundle &bundle);
302 
308  void analyze_bundle_ext(const ast::Bundle &bundle);
309 
314  tree::Maybe<semantic::Instruction> analyze_instruction(const ast::Instruction &insn);
315 
321  tree::Maybe<semantic::SetInstruction> analyze_set_instruction(const ast::Instruction &insn);
322 
328  tree::Maybe<semantic::SetInstruction> analyze_set_instruction_operands(
329  const ast::Expression &lhs_expr,
330  const ast::Expression &rhs_expr
331  );
332 
338  tree::Maybe<semantic::GotoInstruction> analyze_goto_instruction(const ast::Instruction &insn);
339 
345  void analyze_error_model(const ast::Instruction &insn);
346 
352  void analyze_mapping(const ast::Mapping &mapping);
353 
359  void analyze_variables(const ast::Variables &variables);
360 
366  void analyze_subcircuit(const ast::Subcircuit &subcircuit);
367 
374  void analyze_structured(const ast::Structured &structured);
375 
380  tree::Maybe<semantic::IfElse> analyze_if_else(const ast::IfElse &if_else);
381 
386  tree::Maybe<semantic::ForLoop> analyze_for_loop(const ast::ForLoop &for_loop);
387 
392  tree::Maybe<semantic::ForeachLoop> analyze_foreach_loop(const ast::ForeachLoop &foreach_loop);
393 
398  tree::Maybe<semantic::WhileLoop> analyze_while_loop(const ast::WhileLoop &while_loop);
399 
404  tree::Maybe<semantic::RepeatUntilLoop> analyze_repeat_until_loop(const ast::RepeatUntilLoop &repeat_until_loop);
405 
411  tree::Any<semantic::AnnotationData> analyze_annotations(
412  const tree::Any<ast::AnnotationData> &annotations
413  );
414 
419  values::Value analyze_expression(const ast::Expression &expression);
420 
426  template<class Type, class... TypeArgs>
427  values::Value analyze_as(
428  const ast::Expression &expression,
429  TypeArgs... type_args
430  );
431 
435  primitives::Int analyze_as_const_int(const ast::Expression &expression);
436 
440  values::Value analyze_matrix(const ast::MatrixLiteral &matrix_lit);
441 
447  template<class ElType, class ElVal, class MatLit, class MatVal>
448  values::Value analyze_matrix_helper(
449  size_t nrows, size_t ncols,
450  const std::vector<values::Value> &vals
451  );
452 
457  values::Value analyze_index(const ast::Index &index);
458 
462  tree::Many<values::ConstInt> analyze_index_list(
463  const ast::IndexList &index_list, size_t size
464  );
465 
469  values::Value analyze_function(
470  const ast::Identifier &name,
471  const ast::ExpressionList &args
472  );
473 
477  values::Value analyze_operator(
478  const std::string &name,
482  );
483 
484 };
485 
490  auto result = AnalyzerHelper(*this, ast).result;
491  if (result.errors.empty() && !result.root.is_well_formed()) {
492  std::cerr << *result.root;
493  throw std::runtime_error("internal error: no semantic errors returned, but semantic tree is incomplete. Tree was dumped.");
494  }
495  return result;
496 }
497 
503  if (!parse_result.errors.empty()) {
504  AnalysisResult result;
505  result.errors = parse_result.errors;
506  return result;
507  } else {
508  return analyze(*parse_result.root->as_program());
509  }
510 }
511 
516  const std::function<version::Version()> &version_parser,
517  const std::function<parser::ParseResult()> &file_parser
518 ) const {
519  AnalysisResult result;
520  try {
521  auto file_version = version_parser();
522  if (file_version > api_version) {
523  std::ostringstream ss;
524  ss << "cQASM file version is " << file_version << ", but at most ";
525  ss << api_version << " is supported here";
526  result.errors.push_back(ss.str());
527  return result;
528  }
529  } catch (error::AnalysisError &e) {
530  result.errors.push_back(e.get_message());
531  return result;
532  }
533  return analyze(file_parser());
534 }
535 
539 AnalysisResult Analyzer::analyze(const std::string &filename) const {
540  return analyze(
541  [=](){ return version::parse_file(filename); },
542  [=](){ return parser::parse_file(filename); }
543  );
544 }
545 
550 AnalysisResult Analyzer::analyze(FILE *file, const std::string &filename) const {
551  return analyze(
552  [=](){ return version::parse_file(file, filename); },
553  [=](){ return parser::parse_file(file, filename); }
554  );
555 }
556 
561 AnalysisResult Analyzer::analyze_string(const std::string &data, const std::string &filename) const {
562  return analyze(
563  [=](){ return version::parse_string(data, filename); },
564  [=](){ return parser::parse_string(data, filename); }
565  );
566 }
567 
572  const Analyzer &analyzer,
573  const ast::Program &ast
574 ) :
575  analyzer(analyzer),
576  result(),
577  scope_stack({Scope(analyzer.mappings, analyzer.functions, analyzer.instruction_set)})
578 {
579  try {
580 
581  // Construct the program node.
582  result.root.set(tree::make<semantic::Program>());
583  result.root->copy_annotation<parser::SourceLocation>(ast);
584  result.root->api_version = analyzer.api_version;
585 
586  // Check and set the version.
587  analyze_version(*ast.version);
588 
589  // Handle the qubits statement. Qubit variables can be used instead of
590  // the qubits keyword, in which case num_qubits is set to 0 to indicate
591  // that it's not being used.
592  if (!ast.num_qubits.empty()) {
593  analyze_qubits(*ast.num_qubits);
594  } else if (ast.version->items.compare("1.1") < 0) {
595  throw error::AnalysisError("missing qubits statement (required until version 1.1)");
596  } else {
597  result.root->num_qubits = 0;
598  }
599 
600  // Read the statements.
601  analyze_statements(*ast.statements);
602 
603  // Resolve goto targets.
604  if (ast.version->items.compare("1.2") >= 0) {
605 
606  // Figure out all the subcircuit names and check for duplicates.
607  std::map<std::string, tree::Maybe<semantic::Subcircuit>> subcircuits;
608  for (const auto &subcircuit : result.root->subcircuits) {
609  try {
610  auto insert_result = subcircuits.insert({subcircuit->name, subcircuit});
611  if (!insert_result.second) {
612  std::ostringstream ss;
613  ss << "duplicate subcircuit name \"" << subcircuit->name << "\"";
614  if (auto loc = insert_result.first->second->get_annotation_ptr<parser::SourceLocation>()) {
615  ss << "; previous definition was at " << *loc;
616  }
617  throw error::AnalysisError(ss.str());
618  }
619  } catch (error::AnalysisError &e) {
620  e.context(*subcircuit);
621  result.errors.push_back(e.get_message());
622  }
623  }
624 
625  // Resolve the goto instruction targets.
626  for (const auto &it : gotos) {
627  try {
628  auto it2 = subcircuits.find(it.second);
629  if (it2 == subcircuits.end()) {
630  throw error::AnalysisError(
631  "failed to resolve subcircuit \"" + it.second + "\""
632  );
633  }
634  it.first->target = it2->second;
635  } catch (error::AnalysisError &e) {
636  e.context(*it.first);
637  result.errors.push_back(e.get_message());
638  }
639  }
640 
641  }
642 
643  // Save the list of final mappings.
644  for (const auto &it : get_current_scope().mappings.get_table()) {
645  const auto &name = it.first;
646  const auto &value = it.second.first;
647  const auto &ast_node = it.second.second;
648 
649  // Ignore predefined and implicit mappings.
650  if (ast_node.empty()) {
651  continue;
652  }
653 
654  // Analyze any annotations attached to the mapping.
655  auto annotations = analyze_annotations(ast_node->annotations);
656 
657  // Construct the mapping object and copy the source location.
658  auto mapping = tree::make<semantic::Mapping>(
659  name, value,
660  analyze_annotations(ast_node->annotations)
661  );
662  mapping->copy_annotation<parser::SourceLocation>(*ast_node);
663  result.root->mappings.add(mapping);
664 
665  }
666 
667  // The iteration order over the mapping table is undefined, because it's
668  // backed by an unordered_map. To get a deterministic tree, sort by
669  // source location.
670  std::sort(
671  result.root->mappings.begin(), result.root->mappings.end(),
672  [](const tree::One<semantic::Mapping> &lhs, const tree::One<semantic::Mapping> &rhs) -> bool {
673  if (auto lhsa = lhs->get_annotation_ptr<parser::SourceLocation>()) {
674  if (auto rhsa = rhs->get_annotation_ptr<parser::SourceLocation>()) {
675  if (lhsa->filename < rhsa->filename) return true;
676  if (rhsa->filename < lhsa->filename) return false;
677  if (lhsa->first_line < rhsa->first_line) return true;
678  if (rhsa->first_line < lhsa->first_line) return false;
679  return lhsa->first_column < rhsa->first_column;
680  }
681  }
682  return false;
683  });
684 
685  } catch (error::AnalysisError &e) {
686  result.errors.push_back(e.get_message());
687  }
688 }
689 
694  try {
695 
696  // Default to API version in case the version in the AST is broken.
697  result.root->version = tree::make<semantic::Version>();
698  result.root->version->items = analyzer.api_version;
699 
700  // Check API version.
701  for (auto item : ast.items) {
702  if (item < 0) {
703  throw error::AnalysisError("invalid version component");
704  }
705  }
706  if (ast.items.compare(analyzer.api_version) > 0) {
707  std::ostringstream ss{};
708  ss << "the maximum cQASM version supported is " << analyzer.api_version;
709  ss << ", but the cQASM file is version " << ast.items;
710  throw error::AnalysisError(ss.str());
711  }
712 
713  // Save the file version.
714  result.root->version->items = ast.items;
715 
716  } catch (error::AnalysisError &e) {
717  e.context(ast);
718  result.errors.push_back(e.get_message());
719  }
720  result.root->version->copy_annotation<parser::SourceLocation>(ast);
721 }
722 
728  try {
729  // Default to 0 qubits in case we get an exception or no qubit count is
730  // defined.
731  result.root->num_qubits = 0;
732 
733  // Try to load the number of qubits from the expression.
734  result.root->num_qubits = analyze_as_const_int(count);
735  if (result.root->num_qubits < 1) {
736  // Number of qubits must be positive if specified.
737  throw error::AnalysisError("invalid number of qubits");
738  }
739 
740  // Construct the special q and b mappings, that map to the whole qubit
741  // and measurement register respectively.
742  tree::Many<values::ConstInt> all_qubits;
743  for (primitives::Int i = 0; i < result.root->num_qubits; i++) {
744  auto vi = tree::make<values::ConstInt>(i);
745  vi->copy_annotation<parser::SourceLocation>(count);
746  all_qubits.add(vi);
747  }
748  get_current_scope().mappings.add("q", tree::make<values::QubitRefs>(all_qubits));
749  get_current_scope().mappings.add("b", tree::make<values::BitRefs>(all_qubits));
750 
751  } catch (error::AnalysisError &e) {
752  e.context(count);
753  result.errors.push_back(e.get_message());
754  }
755 }
756 
763  const tree::Annotatable &source
764 ) {
765 
766  // If we don't have a subcircuit yet, add a default one. Note that the
767  // original libqasm always had this default subcircuit (even if it was
768  // empty) and used the name "default" vs. the otherwise invalid empty
769  // string.
770  if (result.root->subcircuits.empty()) {
771  auto subcircuit_node = tree::make<semantic::Subcircuit>("", 1);
772  subcircuit_node->copy_annotation<parser::SourceLocation>(source);
773  if (analyzer.api_version.compare("1.2") >= 0) {
774  subcircuit_node->body = tree::make<semantic::Block>();
775  }
776  result.root->subcircuits.add(subcircuit_node);
777  }
778 
779  // Add the node to the last subcircuit.
780  return result.root->subcircuits.back();
781 
782 }
783 
788  return scope_stack.back();
789 }
790 
795  return scope_stack.front();
796 }
797 
802  const tree::Annotatable &source
803 ) {
804 
805  // If we're in a local scope/block, return that block.
806  const auto &scope = get_current_scope();
807  if (!scope.block.empty()) {
808  return scope.block;
809  }
810 
811  // Otherwise return the block belonging to the current subcircuit.
812  return get_current_subcircuit(source)->body;
813 }
814 
819 
820  // Add the statement to the current block.
821  auto block = get_current_block(*stmt);
822  block->statements.add(stmt);
823 
824  // Expand the source location annotation of the block to include the
825  // statement.
826  if (auto stmt_loc = stmt->get_annotation_ptr<parser::SourceLocation>()) {
827  if (auto block_loc = block->get_annotation_ptr<parser::SourceLocation>()) {
828  block_loc->expand_to_include(stmt_loc->first_line, stmt_loc->first_column);
829  block_loc->expand_to_include(stmt_loc->last_line, stmt_loc->last_column);
830  } else {
831  block->set_annotation<parser::SourceLocation>(*stmt_loc);
832  }
833  }
834 
835 }
836 
842  for (const auto &stmt : statements.items) {
843  try {
844  if (auto bundle = stmt->as_bundle()) {
845  if (analyzer.api_version.compare("1.2") >= 0) {
846  analyze_bundle_ext(*bundle);
847  } else {
848  analyze_bundle(*bundle);
849  }
850  } else if (auto mapping = stmt->as_mapping()) {
851  analyze_mapping(*mapping);
852  } else if (auto variables = stmt->as_variables()) {
853  analyze_variables(*variables);
854  } else if (auto subcircuit = stmt->as_subcircuit()) {
855  analyze_subcircuit(*subcircuit);
856  } else if (auto structured = stmt->as_structured()) {
857  if (result.root->version->items.compare("1.2") < 0) {
858  throw error::AnalysisError("structured control-flow is not supported (need version 1.2+)");
859  }
860  analyze_structured(*structured);
861  } else {
862  throw std::runtime_error("unexpected statement node");
863  }
864  } catch (error::AnalysisError &e) {
865  e.context(*stmt);
866  result.errors.push_back(e.get_message());
867  }
868  }
869 }
870 
877  const ast::StatementList &statements,
878  bool is_loop
879 ) {
880 
881  // Create the block.
883  block.emplace();
884 
885  // Create a scope for the block.
886  scope_stack.emplace_back(get_current_scope());
887  get_current_scope().block = block;
888  get_current_scope().within_loop |= is_loop;
889 
890  // Analyze the statements within the block. The statements will be added
891  // to the current scope, which we just updated.
892  analyze_statements(statements);
893 
894  // Pop the scope from the stack.
895  scope_stack.pop_back();
896 
897  return block;
898 }
899 
906  try {
907 
908  // The error model statement from the original cQASM grammar is a bit
909  // of a pain, because it conflicts with gates/instructions, so we have
910  // to special-case it here. Technically we could also have made it a
911  // keyword, but the less random keywords there are, the better.
912  if (bundle.items.size() == 1) {
913  if (utils::case_insensitive_equals(bundle.items[0]->name->name, "error_model")) {
914  analyze_error_model(*bundle.items[0]);
915  return;
916  }
917  }
918 
919  // Analyze and add the instructions.
920  auto node = tree::make<semantic::Bundle>();
921  for (const auto &insn : bundle.items) {
922  node->items.add(analyze_instruction(*insn));
923  }
924 
925  // If we have more than two instructions, ensure that all instructions
926  // are parallelizable.
927  if (node->items.size() > 1) {
928  for (const auto &insn : node->items) {
929  try {
930  if (!insn->instruction.empty()) {
931  if (!insn->instruction->allow_parallel) {
932  std::ostringstream ss;
933  ss << "instruction ";
934  ss << insn->instruction->name;
935  ss << " with parameter pack ";
936  ss << insn->instruction->param_types;
937  ss << " is not parallelizable, but is bundled with ";
938  ss << (node->items.size() - 1);
939  ss << " other instruction";
940  if (node->items.size() != 2) {
941  ss << "s";
942  }
943  throw error::AnalysisError(ss.str());
944  }
945  }
946  } catch (error::AnalysisError &e) {
947  e.context(*insn);
948  result.errors.push_back(e.get_message());
949  }
950  }
951  }
952 
953  // It's possible that no instructions end up being added, due to all
954  // condition codes resolving to constant false. In that case the entire
955  // bundle is removed.
956  if (node->items.empty()) {
957  return;
958  }
959 
960  // Copy annotation data.
961  node->annotations = analyze_annotations(bundle.annotations);
962  node->copy_annotation<parser::SourceLocation>(bundle);
963 
964  // Add the node to the last subcircuit.
965  get_current_subcircuit(bundle)->bundles.add(node);
966 
967  } catch (error::AnalysisError &e) {
968  e.context(bundle);
969  result.errors.push_back(e.get_message());
970  }
971 }
972 
979  try {
980 
981  // The error model statement from the original cQASM grammar is a bit
982  // of a pain, because it conflicts with gates/instructions, so we have
983  // to special-case it here. Technically we could also have made it a
984  // keyword, but the less random keywords there are, the better.
985  if (bundle.items.size() == 1) {
986  if (utils::case_insensitive_equals(bundle.items[0]->name->name, "error_model")) {
987  analyze_error_model(*bundle.items[0]);
988  return;
989  }
990  }
991 
992  // Analyze and add the instructions.
993  auto node = tree::make<semantic::BundleExt>();
994  for (const auto &insn : bundle.items) {
995  if (utils::case_insensitive_equals(insn->name->name, "set")) {
996  node->items.add(analyze_set_instruction(*insn));
997  } else if (utils::case_insensitive_equals(insn->name->name, "goto")) {
998  node->items.add(analyze_goto_instruction(*insn));
999  } else {
1000  node->items.add(analyze_instruction(*insn));
1001  }
1002  }
1003 
1004  // If we have more than two instructions, ensure that all instructions
1005  // are parallelizable.
1006  if (node->items.size() > 1) {
1007  for (const auto &insn_base : node->items) {
1008  try {
1009  if (auto insn = insn_base->as_instruction()) {
1010  if (!insn->instruction.empty()) {
1011  if (!insn->instruction->allow_parallel) {
1012  std::ostringstream ss;
1013  ss << "instruction ";
1014  ss << insn->instruction->name;
1015  ss << " with parameter pack ";
1016  ss << insn->instruction->param_types;
1017  ss << " is not parallelizable, but is bundled with ";
1018  ss << (node->items.size() - 1);
1019  ss << " other instruction";
1020  if (node->items.size() != 2) {
1021  ss << "s";
1022  }
1023  throw error::AnalysisError(ss.str());
1024  }
1025  }
1026  }
1027  } catch (error::AnalysisError &e) {
1028  e.context(*insn_base);
1029  result.errors.push_back(e.get_message());
1030  }
1031  }
1032  }
1033 
1034  // It's possible that no instructions end up being added, due to all
1035  // condition codes resolving to constant false. In that case the entire
1036  // bundle is removed.
1037  if (node->items.empty()) {
1038  return;
1039  }
1040 
1041  // Copy annotation data.
1042  node->annotations = analyze_annotations(bundle.annotations);
1043  node->copy_annotation<parser::SourceLocation>(bundle);
1044 
1045  // Add the node to the last subcircuit.
1047 
1048  } catch (error::AnalysisError &e) {
1049  e.context(bundle);
1050  result.errors.push_back(e.get_message());
1051  }
1052 }
1053 
1061  try {
1062 
1063  // Figure out the operand list.
1064  auto operands = values::Values();
1065  for (auto operand_expr : insn.operands->items) {
1066  operands.add(analyze_expression(*operand_expr));
1067  }
1068 
1069  // Resolve the instruction and/or make the instruction node.
1071  if (analyzer.resolve_instructions) {
1072  node.set(get_current_scope().instruction_set.resolve(insn.name->name, operands));
1073  } else {
1074  node.set(tree::make<semantic::Instruction>(
1076  insn.name->name, values::Value(), operands,
1078  }
1079 
1080  // Resolve the condition code.
1081  if (!insn.condition.empty()) {
1082  if (!node->instruction.empty() && !node->instruction->allow_conditional) {
1083  throw error::AnalysisError(
1084  "conditional execution is not supported for this instruction");
1085  }
1086  auto condition_val = analyze_expression(*insn.condition);
1087  node->condition = values::promote(condition_val, tree::make<types::Bool>());
1088  if (node->condition.empty()) {
1089  throw error::AnalysisError("condition must be a boolean");
1090  }
1091 
1092  // If the condition is constant false, optimize the instruction
1093  // away.
1094  if (auto x = node->condition->as_const_bool()) {
1095  if (!x->value) {
1097  }
1098  }
1099 
1100  } else {
1101  node->condition.set(tree::make<values::ConstBool>(true));
1102  }
1103 
1104  // Enforce qubit uniqueness if the instruction requires us to.
1105  if (!node->instruction.empty() && !node->instruction->allow_reused_qubits) {
1106  std::unordered_set<primitives::Int> qubits_used;
1107  for (const auto &operand : operands) {
1108  if (auto x = operand->as_qubit_refs()) {
1109  for (auto index : x->index) {
1110  if (!qubits_used.insert(index->value).second) {
1111  throw error::AnalysisError(
1112  "qubit with index " + std::to_string(index->value)
1113  + " is used more than once");
1114  }
1115  }
1116  }
1117  }
1118  }
1119 
1120  // Enforce that all qubit and bit references have the same length if
1121  // the instruction requires us to. Note that historically the condition
1122  // is NOT split across the resulting parallel instructions but is
1123  // instead copied and reduced using boolean and at runtime, so its
1124  // length does NOT have to match.
1125  if (!node->instruction.empty() && !node->instruction->allow_different_index_sizes) {
1126  size_t num_refs = 0;
1127  const parser::SourceLocation *num_refs_loc = nullptr;
1128  for (const auto &operand : operands) {
1129  const tree::Many<values::ConstInt> *indices = nullptr;
1130  if (auto x = operand->as_qubit_refs()) {
1131  indices = &x->index;
1132  } else if (auto x = operand->as_bit_refs()) {
1133  indices = &x->index;
1134  }
1135  if (indices) {
1136  if (!num_refs) {
1137  num_refs = indices->size();
1138  } else if (num_refs != indices->size()) {
1139  std::ostringstream ss;
1140  ss << "the number of indices (" << indices->size() << ") ";
1141  ss << "doesn't match previously found number of indices ";
1142  ss << "(" << num_refs << ")";
1143  if (num_refs_loc) {
1144  ss << " at " << *num_refs_loc;
1145  }
1146  throw error::AnalysisError(ss.str(), &*operand);
1147  }
1148  if (!num_refs_loc) {
1149  num_refs_loc = operand->get_annotation_ptr<parser::SourceLocation>();
1150  }
1151  }
1152  }
1153  }
1154 
1155  // Copy annotation data.
1156  node->annotations = analyze_annotations(insn.annotations);
1157  node->copy_annotation<parser::SourceLocation>(insn);
1158 
1159  return node;
1160  } catch (error::AnalysisError &e) {
1161  e.context(insn);
1162  result.errors.push_back(e.get_message());
1163  }
1165 }
1166 
1173  const ast::Instruction &insn
1174 ) {
1175  try {
1176 
1177  // Figure out the operand list.
1178  if (insn.operands->items.size() != 2) {
1179  throw error::AnalysisError("set instruction must have two operands");
1180  }
1181 
1182  // Analyze the operands.
1184  *insn.operands->items[0],
1185  *insn.operands->items[1]
1186  );
1187 
1188  // Resolve the condition code.
1189  if (!insn.condition.empty()) {
1190  auto condition_val = analyze_expression(*insn.condition);
1191  node->condition = values::promote(condition_val, tree::make<types::Bool>());
1192  if (node->condition.empty()) {
1193  throw error::AnalysisError("condition must be a boolean");
1194  }
1195 
1196  // If the condition is constant false, optimize the instruction
1197  // away.
1198  if (auto x = node->condition->as_const_bool()) {
1199  if (!x->value) {
1201  }
1202  }
1203  } else {
1204  node->condition.set(tree::make<values::ConstBool>(true));
1205  }
1206 
1207  // Copy annotation data.
1208  node->annotations = analyze_annotations(insn.annotations);
1209  node->copy_annotation<parser::SourceLocation>(insn);
1210 
1211  return node;
1212  } catch (error::AnalysisError &e) {
1213  e.context(insn);
1214  result.errors.push_back(e.get_message());
1215  }
1217 }
1218 
1225  const ast::Expression &lhs_expr,
1226  const ast::Expression &rhs_expr
1227 ) {
1228 
1229  // Analyze the expressions.
1230  auto lhs = analyze_expression(lhs_expr);
1231  auto rhs = analyze_expression(rhs_expr);
1232 
1233  // Check assignability of the left-hand side.
1234  if (!lhs->as_reference()) {
1235  throw error::AnalysisError(
1236  "left-hand side of assignment statement must be assignable"
1237  );
1238  }
1239 
1240  // Type-check/promote the right-hand side.
1241  auto target_type = values::type_of(lhs).clone();
1242  target_type->assignable = false;
1243  auto rhs_promoted = values::promote(rhs, target_type);
1244  if (rhs_promoted.empty()) {
1245  std::ostringstream ss;
1246  ss << "type of right-hand side (" << values::type_of(rhs) << ") ";
1247  ss << "could not be coerced to left-hand side (" << values::type_of(lhs) << ")";
1248  throw error::AnalysisError(ss.str());
1249  }
1250 
1251  // Create the node.
1253  node.emplace<semantic::SetInstruction>(lhs, rhs_promoted);
1254  return node;
1255 }
1256 
1263  const ast::Instruction &insn
1264 ) {
1265  try {
1266 
1267  // Parse the operands.
1268  if (insn.operands->items.size() != 1) {
1269  throw error::AnalysisError(
1270  "goto instruction must have a single operand"
1271  );
1272  }
1273  std::string target;
1274  if (auto identifier = insn.operands->items[0]->as_identifier()) {
1275  target = identifier->name;
1276  } else {
1277  throw error::AnalysisError(
1278  "goto instruction operand must be a subcircuit identifier"
1279  );
1280  }
1281 
1282  // Create the node.
1284  node.set(tree::make<semantic::GotoInstruction>());
1285 
1286  // We can't resolve the target subcircuit yet, because goto instructions
1287  // may refer forward. Instead, we maintain a list of yet-to-be resolved
1288  // goto instructions.
1289  gotos.emplace_back(node, target);
1290 
1291  // Resolve the condition code.
1292  if (!insn.condition.empty()) {
1293  auto condition_val = analyze_expression(*insn.condition);
1294  node->condition = values::promote(condition_val, tree::make<types::Bool>());
1295  if (node->condition.empty()) {
1296  throw error::AnalysisError("condition must be a boolean");
1297  }
1298 
1299  // If the condition is constant false, optimize the instruction
1300  // away.
1301  if (auto x = node->condition->as_const_bool()) {
1302  if (!x->value) {
1304  }
1305  }
1306  } else {
1307  node->condition.set(tree::make<values::ConstBool>(true));
1308  }
1309 
1310  // Copy annotation data.
1311  node->annotations = analyze_annotations(insn.annotations);
1312  node->copy_annotation<parser::SourceLocation>(insn);
1313 
1314  return node;
1315  } catch (error::AnalysisError &e) {
1316  e.context(insn);
1317  result.errors.push_back(e.get_message());
1318  }
1320 }
1321 
1328  try {
1329 
1330  // Only one error model should be specified, so throw an error
1331  // if we already have one.
1332  if (!result.root->error_model.empty()) {
1333  auto ss = std::ostringstream();
1334  ss << "error model can only be specified once";
1335  if (auto loc = result.root->error_model->get_annotation_ptr<parser::SourceLocation>()) {
1336  ss << ", previous specification was at " << *loc;
1337  }
1338  throw error::AnalysisError(ss.str());
1339  }
1340 
1341  // Figure out the name of the error model.
1342  const auto &arg_exprs = insn.operands->items;
1343  if (arg_exprs.empty()) {
1344  throw error::AnalysisError("missing error model name");
1345  }
1346  std::string name;
1347  if (auto name_ident = arg_exprs[0]->as_identifier()) {
1348  name = name_ident->name;
1349  } else {
1350  throw error::AnalysisError(
1351  "first argument of an error model must be its name as an identifier");
1352  }
1353 
1354  // Figure out the argument list.
1355  auto arg_values = values::Values();
1356  for (auto arg_expr_it = arg_exprs.begin() + 1; arg_expr_it < arg_exprs.end(); arg_expr_it++) {
1357  arg_values.add(analyze_expression(**arg_expr_it));
1358  }
1359 
1360  // Resolve the error model to one of the known models if
1361  // requested. If resolving is disabled, just make a node with
1362  // the name and values directly (without promotion/implicit
1363  // casts).
1364  if (analyzer.resolve_error_model) {
1365  result.root->error_model.set(
1366  analyzer.error_models.resolve(
1367  name, arg_values));
1368  } else {
1369  result.root->error_model.set(
1370  tree::make<semantic::ErrorModel>(
1372  name, arg_values,
1374  }
1375 
1376  // Copy annotation data.
1377  result.root->error_model->annotations = analyze_annotations(insn.annotations);
1378  result.root->error_model->copy_annotation<parser::SourceLocation>(insn);
1379 
1380  } catch (error::AnalysisError &e) {
1381  e.context(insn);
1382  result.errors.push_back(e.get_message());
1383  }
1384 }
1385 
1392  try {
1394  mapping.alias->name,
1395  analyze_expression(*mapping.expr),
1396  tree::make<ast::Mapping>(mapping)
1397  );
1398  } catch (error::AnalysisError &e) {
1399  e.context(mapping);
1400  result.errors.push_back(e.get_message());
1401  }
1402 }
1403 
1410  try {
1411 
1412  // Check version compatibility.
1413  if (result.root->version->items.compare("1.1") < 0) {
1414  throw error::AnalysisError("variables are only supported from cQASM 1.1 onwards");
1415  }
1416 
1417  // Figure out what type the variables should have.
1418  auto type_name = utils::lowercase(variables.typ->name);
1419  types::Type type{};
1420  if (type_name == "qubit") {
1421  type = tree::make<types::Qubit>();
1422  } else if (type_name == "bool" || type_name == "bit") {
1423  type = tree::make<types::Bool>();
1424  } else if (type_name == "int") {
1425  type = tree::make<types::Int>();
1426  } else if (type_name == "real") {
1427  type = tree::make<types::Real>();
1428  } else if (type_name == "complex") {
1429  type = tree::make<types::Complex>();
1430  } else {
1431  throw error::AnalysisError("unknown type \"" + type_name + "\"");
1432  }
1433  type->assignable = true;
1434 
1435  // Construct the variables and add mappings for them.
1436  for (const auto &identifier : variables.names) {
1437 
1438  // Construct variable. Use the location tag of the identifier to
1439  // record where the variable was defined.
1440  auto var = tree::make<semantic::Variable>(identifier->name, type.clone());
1441  var->copy_annotation<parser::SourceLocation>(*identifier);
1442  result.root->variables.add(var);
1443 
1444  // Add a mapping for the variable.
1446  identifier->name,
1447  tree::make<values::VariableRef>(var),
1449  );
1450  }
1451 
1452  } catch (error::AnalysisError &e) {
1453  e.context(variables);
1454  result.errors.push_back(e.get_message());
1455  }
1456 }
1457 
1464  try {
1465  if (scope_stack.size() > 1) {
1466  throw error::AnalysisError("cannot open subcircuit within subblock");
1467  }
1468  primitives::Int iterations = 1;
1469  if (!subcircuit.iterations.empty()) {
1470  iterations = analyze_as_const_int(*subcircuit.iterations);
1471  if (iterations < 1) {
1472  throw error::AnalysisError(
1473  "subcircuit iteration count must be positive, but is "
1474  + std::to_string(iterations), &*subcircuit.iterations);
1475  }
1476  }
1477  auto node = tree::make<semantic::Subcircuit>(
1478  subcircuit.name->name,
1479  iterations,
1481  analyze_annotations(subcircuit.annotations));
1482  node->copy_annotation<parser::SourceLocation>(subcircuit);
1483  if (analyzer.api_version.compare("1.2") >= 0) {
1484  node->body = tree::make<semantic::Block>();
1485  node->body->copy_annotation<parser::SourceLocation>(subcircuit);
1486  }
1487  result.root->subcircuits.add(node);
1488  } catch (error::AnalysisError &e) {
1489  e.context(subcircuit);
1490  result.errors.push_back(e.get_message());
1491  }
1492 }
1493 
1501  try {
1503 
1504  // Switch based on statement type.
1505  if (auto if_else = structured.as_if_else()) {
1506  node = analyze_if_else(*if_else);
1507  } else if (auto for_loop = structured.as_for_loop()) {
1508  node = analyze_for_loop(*for_loop);
1509  } else if (auto foreach_loop = structured.as_foreach_loop()) {
1510  node = analyze_foreach_loop(*foreach_loop);
1511  } else if (auto while_loop = structured.as_while_loop()) {
1512  node = analyze_while_loop(*while_loop);
1513  } else if (auto repeat_until_loop = structured.as_repeat_until_loop()) {
1514  node = analyze_repeat_until_loop(*repeat_until_loop);
1515  } else if (structured.as_break_statement()) {
1516 
1517  // Handle break statement.
1518  if (!get_current_scope().within_loop) {
1519  throw error::AnalysisError(
1520  "cannot use break outside of a structured loop"
1521  );
1522  }
1523  node.emplace<semantic::BreakStatement>();
1524 
1525  } else if (structured.as_continue_statement()) {
1526 
1527  // Handle continue statement.
1528  if (!get_current_scope().within_loop) {
1529  throw error::AnalysisError(
1530  "cannot use continue outside of a structured loop"
1531  );
1532  }
1533  node.emplace<semantic::ContinueStatement>();
1534 
1535  } else {
1536  throw std::runtime_error("unexpected statement node");
1537  }
1538 
1539  // Stop if the node was optimized away.
1540  if (node.empty()) {
1541  return;
1542  }
1543 
1544  // Copy annotation data.
1545  node->annotations = analyze_annotations(structured.annotations);
1546  node->copy_annotation<parser::SourceLocation>(structured);
1547 
1548  // Add the node to the current block.
1550 
1551  } catch (error::AnalysisError &e) {
1552  e.context(structured);
1553  result.errors.push_back(e.get_message());
1554  }
1555 }
1556 
1562  const ast::IfElse &if_else
1563 ) {
1564 
1565  // Create the if-else node.
1567  node.emplace();
1568 
1569  // Analyze the branches.
1570  for (const auto &branch : if_else.branches) {
1571 
1572  // Analyze the condition.
1573  auto condition = analyze_expression(*branch->condition);
1574  condition = values::promote(condition, tree::make<types::Bool>());
1575  if (condition.empty()) {
1576  throw error::AnalysisError("if/else condition must be a boolean");
1577  }
1578 
1579  // Analyze the block.
1580  auto body = analyze_subblock(*branch->body, false);
1581 
1582  // Add the branch.
1583  node->branches.emplace(condition, body);
1584 
1585  }
1586 
1587  // Analyze the otherwise block, if any.
1588  if (!if_else.otherwise.empty()) {
1589  node->otherwise = analyze_subblock(*if_else.otherwise, false);
1590  }
1591 
1592  // Remove branches that are never taken due to constant-propagated
1593  // conditions.
1594  for (size_t idx = 0; idx < node->branches.size(); ) {
1595  if (auto val = node->branches[idx]->condition->as_const_bool()) {
1596  if (val->value) {
1597 
1598  // Constant true: optimize away all subsequent branches and
1599  // replace the otherwise block with this one.
1600  node->otherwise = node->branches[idx]->body;
1601  while (node->branches.size() > idx) node->branches.remove();
1602 
1603  } else {
1604 
1605  // Constant false: remove this condition/block.
1606  node->branches.remove(idx);
1607 
1608  }
1609  } else {
1610  idx++;
1611  }
1612  }
1613 
1614  // If no branches remain, optimize the entire statement away.
1615  if (node->branches.empty()) {
1616  if (!node->otherwise.empty()) {
1617  for (const auto &stmt : node->otherwise->statements) {
1618  add_to_current_block(stmt);
1619  }
1620  }
1621  return {};
1622  }
1623 
1624  return node;
1625 }
1626 
1632  const ast::ForLoop &for_loop
1633 ) {
1634 
1635  // Create the for-loop node.
1637  node.emplace();
1638 
1639  // Analyze the initialization assignment.
1640  if (!for_loop.initialize.empty()) {
1641  node->initialize = analyze_set_instruction_operands(
1642  *for_loop.initialize->lhs,
1643  *for_loop.initialize->rhs
1644  );
1645  node->initialize->condition.emplace<values::ConstBool>(true);
1646  }
1647 
1648  // Analyze the condition.
1649  auto condition = analyze_expression(*for_loop.condition);
1650  node->condition = values::promote(condition, tree::make<types::Bool>());
1651  if (node->condition.empty()) {
1652  throw error::AnalysisError("loop condition must be a boolean");
1653  }
1654 
1655  // Analyze the update assignment.
1656  if (!for_loop.update.empty()) {
1657  node->update = analyze_set_instruction_operands(
1658  *for_loop.update->lhs,
1659  *for_loop.update->rhs
1660  );
1661  node->update->condition.emplace<values::ConstBool>(true);
1662  }
1663 
1664  // Analyze the body.
1665  node->body = analyze_subblock(*for_loop.body, true);
1666 
1667  return node;
1668 }
1669 
1675  const ast::ForeachLoop &foreach_loop
1676 ) {
1677 
1678  // Create the foreach loop node.
1680  node.emplace();
1681 
1682  // Analyze the loop variable.
1683  node->lhs = values::promote(analyze_expression(*foreach_loop.lhs), tree::make<types::Int>(true));
1684  if (node->lhs.empty()) {
1685  throw error::AnalysisError("foreach loop variable must be an assignable integer");
1686  }
1687 
1688  // Analyze the boundaries.
1689  node->frm = analyze_as_const_int(*foreach_loop.frm);
1690  node->to = analyze_as_const_int(*foreach_loop.to);
1691 
1692  // Analyze the body.
1693  node->body = analyze_subblock(*foreach_loop.body, true);
1694 
1695  return node;
1696 }
1697 
1703  const ast::WhileLoop &while_loop
1704 ) {
1705 
1706  // Create the while-loop node.
1708  node.emplace();
1709 
1710  // Analyze the condition.
1711  auto condition = analyze_expression(*while_loop.condition);
1712  node->condition = values::promote(condition, tree::make<types::Bool>());
1713  if (node->condition.empty()) {
1714  throw error::AnalysisError("loop condition must be a boolean");
1715  }
1716 
1717  // Analyze the body.
1718  node->body = analyze_subblock(*while_loop.body, true);
1719 
1720  // If the condition is constant false, optimize away.
1721  if (auto cond = node->condition->as_const_bool()) {
1722  if (!cond->value) {
1723  return {};
1724  }
1725  }
1726 
1727  return node;
1728 }
1729 
1735  const ast::RepeatUntilLoop &repeat_until_loop
1736 ) {
1737 
1738  // Create the repeat-until-loop node.
1740  node.emplace();
1741 
1742  // Analyze the body.
1743  node->body = analyze_subblock(*repeat_until_loop.body, true);
1744 
1745  // Analyze the condition.
1746  auto condition = analyze_expression(*repeat_until_loop.condition);
1747  node->condition = values::promote(condition, tree::make<types::Bool>());
1748  if (node->condition.empty()) {
1749  throw error::AnalysisError("loop condition must be a boolean");
1750  }
1751 
1752  // If the condition is constant true, optimize away.
1753  if (auto cond = node->condition->as_const_bool()) {
1754  if (cond->value) {
1755  for (const auto &stmt : node->body->statements) {
1756  add_to_current_block(stmt);
1757  }
1758  return {};
1759  }
1760  }
1761 
1762  return node;
1763 }
1764 
1771  const tree::Any<ast::AnnotationData> &annotations
1772 ) {
1773  auto retval = tree::Any<semantic::AnnotationData>();
1774  for (auto annotation_ast : annotations) {
1775  try {
1776  auto annotation = tree::make<semantic::AnnotationData>();
1777  annotation->interface = annotation_ast->interface->name;
1778  annotation->operation = annotation_ast->operation->name;
1779  for (auto expression_ast : annotation_ast->operands->items) {
1780  try {
1781  annotation->operands.add(analyze_expression(*expression_ast));
1782  } catch (error::AnalysisError &e) {
1783  e.context(*annotation_ast);
1784  result.errors.push_back(e.get_message());
1785  }
1786  }
1787  annotation->copy_annotation<parser::SourceLocation>(*annotation_ast);
1788  retval.add(annotation);
1789  } catch (error::AnalysisError &e) {
1790  e.context(*annotation_ast);
1791  result.errors.push_back(e.get_message());
1792  }
1793  }
1794  return retval;
1795 }
1796 
1802  values::Value retval;
1803  try {
1804  if (auto int_lit = expression.as_integer_literal()) {
1805  retval.set(tree::make<values::ConstInt>(int_lit->value));
1806  } else if (auto float_lit = expression.as_float_literal()) {
1807  retval.set(tree::make<values::ConstReal>(float_lit->value));
1808  } else if (auto string_lit = expression.as_string_literal()) {
1809  retval.set(tree::make<values::ConstString>(string_lit->value));
1810  } else if (auto json_lit = expression.as_json_literal()) {
1811  retval.set(tree::make<values::ConstJson>(json_lit->value));
1812  } else if (auto matrix_lit = expression.as_matrix_literal()) {
1813  retval.set(analyze_matrix(*matrix_lit));
1814  } else if (auto ident = expression.as_identifier()) {
1815  retval.set(get_current_scope().mappings.resolve(ident->name));
1816  } else if (auto index = expression.as_index()) {
1817  retval.set(analyze_index(*index));
1818  } else if (auto func = expression.as_function_call()) {
1819  retval.set(analyze_function(func->name->name, *func->arguments));
1820  } else if (auto negate = expression.as_negate()) {
1821  retval.set(analyze_operator("-", negate->expr));
1822  } else if (auto bit_not = expression.as_bitwise_not()) {
1823  retval.set(analyze_operator("~", bit_not->expr));
1824  } else if (auto log_not = expression.as_logical_not()) {
1825  retval.set(analyze_operator("!", log_not->expr));
1826  } else if (auto power = expression.as_power()) {
1827  retval.set(analyze_operator("**", power->lhs, power->rhs));
1828  } else if (auto mult = expression.as_multiply()) {
1829  retval.set(analyze_operator("*", mult->lhs, mult->rhs));
1830  } else if (auto div = expression.as_divide()) {
1831  retval.set(analyze_operator("/", div->lhs, div->rhs));
1832  } else if (auto idiv = expression.as_int_divide()) {
1833  retval.set(analyze_operator("//", idiv->lhs, idiv->rhs));
1834  } else if (auto mod = expression.as_modulo()) {
1835  retval.set(analyze_operator("%", mod->lhs, mod->rhs));
1836  } else if (auto add = expression.as_add()) {
1837  retval.set(analyze_operator("+", add->lhs, add->rhs));
1838  } else if (auto sub = expression.as_subtract()) {
1839  retval.set(analyze_operator("-", sub->lhs, sub->rhs));
1840  } else if (auto shl = expression.as_shift_left()) {
1841  retval.set(analyze_operator("<<", shl->lhs, shl->rhs));
1842  } else if (auto sra = expression.as_shift_right_arith()) {
1843  retval.set(analyze_operator(">>", sra->lhs, sra->rhs));
1844  } else if (auto srl = expression.as_shift_right_logic()) {
1845  retval.set(analyze_operator(">>>", srl->lhs, srl->rhs));
1846  } else if (auto cmpeq = expression.as_cmp_eq()) {
1847  retval.set(analyze_operator("==", cmpeq->lhs, cmpeq->rhs));
1848  } else if (auto cmpne = expression.as_cmp_ne()) {
1849  retval.set(analyze_operator("!=", cmpne->lhs, cmpne->rhs));
1850  } else if (auto cmpgt = expression.as_cmp_gt()) {
1851  retval.set(analyze_operator(">", cmpgt->lhs, cmpgt->rhs));
1852  } else if (auto cmpge = expression.as_cmp_ge()) {
1853  retval.set(analyze_operator(">=", cmpge->lhs, cmpge->rhs));
1854  } else if (auto cmplt = expression.as_cmp_lt()) {
1855  retval.set(analyze_operator("<", cmplt->lhs, cmplt->rhs));
1856  } else if (auto cmple = expression.as_cmp_le()) {
1857  retval.set(analyze_operator("<=", cmple->lhs, cmple->rhs));
1858  } else if (auto band = expression.as_bitwise_and()) {
1859  retval.set(analyze_operator("&", band->lhs, band->rhs));
1860  } else if (auto bxor = expression.as_bitwise_xor()) {
1861  retval.set(analyze_operator("^", bxor->lhs, bxor->rhs));
1862  } else if (auto bor = expression.as_bitwise_or()) {
1863  retval.set(analyze_operator("|", bor->lhs, bor->rhs));
1864  } else if (auto land = expression.as_logical_and()) {
1865  retval.set(analyze_operator("&&", land->lhs, land->rhs));
1866  } else if (auto lxor = expression.as_logical_xor()) {
1867  retval.set(analyze_operator("^^", lxor->lhs, lxor->rhs));
1868  } else if (auto lor = expression.as_logical_or()) {
1869  retval.set(analyze_operator("||", lor->lhs, lor->rhs));
1870  } else if (auto tcond = expression.as_ternary_cond()) {
1871  retval.set(analyze_operator("?:", tcond->cond, tcond->if_true, tcond->if_false));
1872  } else {
1873  throw std::runtime_error("unexpected expression node");
1874  }
1875  if (!retval.empty() && (retval->as_function() || retval->as_variable_ref())) {
1876  if (analyzer.api_version.compare("1.1") < 0) {
1877  throw error::AnalysisError("dynamic expressions are only supported from cQASM 1.1 onwards");
1878  }
1879  }
1880  } catch (error::AnalysisError &e) {
1881  e.context(expression);
1882  throw;
1883  }
1884  if (retval.empty()) {
1885  throw std::runtime_error(
1886  "analyze_expression returned nonsense, this should never happen");
1887  }
1888  retval->copy_annotation<parser::SourceLocation>(expression);
1889  return retval;
1890 }
1891 
1897 template <class Type, class... TypeArgs>
1898 values::Value AnalyzerHelper::analyze_as(const ast::Expression &expression, TypeArgs... type_args) {
1899  return values::promote(analyze_expression(expression), tree::make<Type>(type_args...));
1900 }
1901 
1906  try {
1907  auto value = analyze_as<types::Int>(expression);
1908  if (value.empty()) {
1909  throw error::AnalysisError("expected an integer");
1910  }
1911  if (auto int_value = value->as_const_int()) {
1912  return int_value->value;
1913  } else {
1914  throw error::AnalysisError("integer must be constant");
1915  }
1916  } catch (error::AnalysisError &e) {
1917  e.context(expression);
1918  throw;
1919  }
1920 }
1921 
1926 
1927  // Figure out the size of the matrix and parse the subexpressions.
1928  // Note that the number of rows is always at least 1 (Many vs Any) so
1929  // the ncols line is well-behaved.
1930  size_t nrows = matrix_lit.rows.size();
1931  size_t ncols = matrix_lit.rows[0]->items.size();
1932  for (auto row : matrix_lit.rows) {
1933  if (row->items.size() != ncols) {
1934  throw error::AnalysisError("matrix is not rectangular");
1935  }
1936  }
1937  std::vector<values::Value> vals;
1938  for (size_t row = 0; row < nrows; row++) {
1939  for (size_t col = 0; col < ncols; col++) {
1940  vals.push_back(analyze_expression(*matrix_lit.rows[row]->items[col]));
1941  }
1942  }
1943 
1944  // Try building a matrix of constant real numbers.
1945  auto value = analyze_matrix_helper<
1948  >(nrows, ncols, vals);
1949  if (!value.empty()) {
1950  return value;
1951  }
1952 
1953  // Try building a matrix of constant complex numbers.
1954  value = analyze_matrix_helper<
1957  >(nrows, ncols, vals);
1958  if (!value.empty()) {
1959  return value;
1960  }
1961 
1962  // Only real and complex are supported right now. If more is to be
1963  // added in the future, this should probably be written a little
1964  // neater.
1965  throw error::AnalysisError("only matrices of constant real or complex numbers are currently supported");
1966 
1967 }
1968 
1974 template <class ElType, class ElVal, class MatLit, class MatVal>
1976  size_t nrows, size_t ncols,
1977  const std::vector<values::Value> &vals
1978 ) {
1979  auto matrix = MatLit(nrows, ncols);
1980  for (size_t row = 0; row < nrows; row++) {
1981  for (size_t col = 0; col < ncols; col++) {
1982  auto val = values::promote(vals[row * ncols + col], tree::make<ElType>());
1983  if (val.empty()) {
1984  return values::Value();
1985  } else {
1986  auto val_real = val.template as<ElVal>();
1987  if (val_real.empty()) {
1988  return values::Value();
1989  } else {
1990  matrix.at(row + 1, col + 1) = val_real->value;
1991  }
1992  }
1993  }
1994  }
1995  return tree::make<MatVal>(matrix);
1996 }
1997 
2002  auto expr = analyze_expression(*index.expr);
2003  if (auto qubit_refs = expr->as_qubit_refs()) {
2004 
2005  // Qubit refs.
2006  auto indices = analyze_index_list(*index.indices, qubit_refs->index.size());
2007  for (auto idx : indices) {
2008  idx->value = qubit_refs->index[idx->value]->value;
2009  }
2010  return tree::make<values::QubitRefs>(indices);
2011 
2012  } else if (auto bit_refs = expr->as_bit_refs()) {
2013 
2014  // Measurement bit refs.
2015  auto indices = analyze_index_list(*index.indices, bit_refs->index.size());
2016  for (auto idx : indices) {
2017  idx->value = bit_refs->index[idx->value]->value;
2018  }
2019  return tree::make<values::BitRefs>(indices);
2020 
2021  } else {
2022 
2023  // While matrices could conceivably be indexed, this is not supported
2024  // right now.
2025  std::ostringstream ss;
2026  ss << "indexation is not supported for value of type " << values::type_of(expr);
2027  throw error::AnalysisError(ss.str());
2028 
2029  }
2030 }
2031 
2037  for (auto entry : index_list.items) {
2038  if (auto item = entry->as_index_item()) {
2039 
2040  // Single index.
2041  auto index = analyze_as_const_int(*item->index);
2042  if (index < 0 || (unsigned long)index >= size) {
2043  throw error::AnalysisError(
2044  "index " + std::to_string(index)
2045  + " out of range (size " + std::to_string(size) + ")",
2046  item);
2047  }
2048  auto index_val = tree::make<values::ConstInt>(index);
2049  index_val->copy_annotation<parser::SourceLocation>(*item);
2050  retval.add(index_val);
2051 
2052  } else if (auto range = entry->as_index_range()) {
2053 
2054  // Range notation.
2055  auto first = analyze_as_const_int(*range->first);
2056  if (first < 0 || (unsigned long)first >= size) {
2057  throw error::AnalysisError(
2058  "index " + std::to_string(first)
2059  + " out of range (size " + std::to_string(size) + ")",
2060  &*range->first);
2061  }
2062  auto last = analyze_as_const_int(*range->last);
2063  if (last < 0 || (unsigned long)last >= size) {
2064  throw error::AnalysisError(
2065  "index " + std::to_string(last)
2066  + " out of range (size " + std::to_string(size) + ")",
2067  &*range->first);
2068  }
2069  if (first > last) {
2070  throw error::AnalysisError("last index is lower than first index", range);
2071  }
2072  for (auto index = (size_t)first; index <= (size_t)last; index++) {
2073  auto index_val = tree::make<values::ConstInt>(index);
2074  index_val->copy_annotation<parser::SourceLocation>(*range);
2075  retval.add(index_val);
2076  }
2077 
2078  } else {
2079  throw std::runtime_error("unknown IndexEntry AST node");
2080  }
2081  }
2082  return retval;
2083 }
2084 
2089  auto arg_values = values::Values();
2090  for (auto arg : args.items) {
2091  arg_values.add(analyze_expression(*arg));
2092  }
2093  auto retval = get_current_scope().functions.call(name.name, arg_values);
2094  if (retval.empty()) {
2095  throw std::runtime_error("function implementation returned empty value");
2096  }
2097  return retval;
2098 }
2099 
2104  const std::string &name,
2105  const tree::One<ast::Expression> &a,
2106  const tree::One<ast::Expression> &b,
2108 ) {
2109  auto identifier = ast::Identifier("operator" + name);
2110  auto args = ast::ExpressionList();
2111  args.items.add(a);
2112  args.items.add(b);
2113  args.items.add(c);
2114  return analyze_function(identifier, args);
2115 }
2116 
2117 } // namespace analyzer
2118 } // namespace v1
2119 } // namespace cqasm
Main class used for analyzing cQASM files.
The file version identifier.
tree::Maybe< semantic::Block > block
The block associated with this scope, if any.
Many< ExpressionList > rows
The list of rows in the matrix.
void add(const error_model::ErrorModel &type)
Registers an error model.
cqasm::v1::primitives::Version items
The list of version components, ordered major to minor.
void add(const std::string &name, const values::Value &value, const tree::Maybe< ast::Mapping > &node=tree::Maybe< ast::Mapping >())
Adds a mapping.
virtual IntegerLiteral * as_integer_literal()
Interprets this node to a node of type IntegerLiteral.
virtual Identifier * as_identifier()
Interprets this node to a node of type Identifier.
One< Expression > lhs
Reference to the variable used for looping.
const std::unordered_map< std::string, std::pair< const values::Value, tree::Maybe< ast::Mapping > > > & get_table() const
Grants read access to the underlying map.
Many< Identifier > names
Name of the variables.
Many< IndexEntry > items
The list of indices.
virtual ShiftRightArith * as_shift_right_arith()
Interprets this node to a node of type ShiftRightArith.
std::complex< double > Complex
Complex number primitive used within the semantic trees.
const std::string & get_message() const
Constructs the message string.
Definition: cqasm-error.cpp:40
virtual Power * as_power()
Interprets this node to a node of type Power.
virtual IntDivide * as_int_divide()
Interprets this node to a node of type IntDivide.
This file contains the Analyzer class and support classes, used to manage semantic analysis...
A C-style for loop.
virtual Multiply * as_multiply()
Interprets this node to a node of type Multiply.
::tree::base::Maybe< T > Maybe
Definition: cqasm-tree.hpp:23
AnalysisResult analyze(const ast::Program &program) const
Analyzes the given program AST node.
Matrix< Complex > CMatrix
Matrix of complex numbers.
Type of a real number (IEEE double).
virtual TernaryCond * as_ternary_cond()
Interprets this node to a node of type TernaryCond.
values::Value analyze_index(const ast::Index &index)
Parses an index operator.
virtual FloatLiteral * as_float_literal()
Interprets this node to a node of type FloatLiteral.
Exception thrown by AnalysisResult::unwrap() when the cQASM file fails to parse.
tree::Maybe< semantic::WhileLoop > analyze_while_loop(const ast::WhileLoop &while_loop)
Analyzes the given while loop.
Maybe< Expression > iterations
An optional integer expression representing the number of iterations for this subcircuit.
One< Identifier > name
The name of the subcircuit.
resolver::InstructionTable instruction_set
The instruction set visible within this scope.
types::Type type_of(const Value &value)
Returns the type of the given value.
Analyzer(const std::string &api_version="1.0")
Creates a new semantic analyzer.
std::vector< std::string > errors
List of accumulated errors.
A list of parallel instructions.
virtual ForeachLoop * as_foreach_loop()
Interprets this node to a node of type ForeachLoop.
Version parse_file(const std::string &filename)
Parse the given file to get its version number.
virtual BitwiseOr * as_bitwise_or()
Interprets this node to a node of type BitwiseOr.
virtual Negate * as_negate()
Interprets this node to a node of type Negate.
Many< IfElseBranch > branches
The if-else branches.
Types from_spec(const std::string &spec)
Constructs a set of types from a shorthand string representation.
Toplevel namespace with entry points for the new API.
values::Value analyze_function(const ast::Identifier &name, const ast::ExpressionList &args)
Parses a function.
resolver::MappingTable mappings
The mappings visible within this scope.
Defines various utility functions.
Maybe< Assignment > initialize
The optional initializing assignment, run before the loop starts.
One< Expression > to
The last value.
Any kind of instruction.
Scope & get_current_scope()
Returns a reference to the current scope.
Header file generated by func-gen.
void analyze_subcircuit(const ast::Subcircuit &subcircuit)
Analyzes the given subcircuit header and, if valid, adds it to the subcircuit list.
A mapping (alias) for an expression.
Source location annotation object, containing source file line numbers etc.
virtual Subtract * as_subtract()
Interprets this node to a node of type Subtract.
values::Value analyze_matrix_helper(size_t nrows, size_t ncols, const std::vector< values::Value > &vals)
Helper for parsing a matrix.
virtual LogicalNot * as_logical_not()
Interprets this node to a node of type LogicalNot.
virtual ContinueStatement * as_continue_statement()
Interprets this node to a node of type ContinueStatement.
tree::Maybe< semantic::ForeachLoop > analyze_foreach_loop(const ast::ForeachLoop &foreach_loop)
Analyzes the given static for loop.
std::list< std::pair< tree::Maybe< semantic::GotoInstruction >, std::string > > gotos
List of all goto instructions in the program, for name resolution when all other analysis completes...
One< StatementList > body
The loop body.
One< Expression > expr
The expression being indexed.
void analyze_mapping(const ast::Mapping &mapping)
Analyzes the given mapping and, if valid, adds it to the current scope.
Table of the supported instructions and their overloads.
std::int64_t Int
Integer primitive used within the AST and semantic trees.
tree::Any< Node > Values
Zero or more cQASM values.
void analyze_qubits(const ast::Expression &count)
Checks the qubits statement and updates the scope accordingly.
One< Identifier > name
Name identifying the instruction.
A list of one or more indices.
tree::Maybe< semantic::IfElse > analyze_if_else(const ast::IfElse &if_else)
Analyzes the given if-else chain.
virtual LogicalOr * as_logical_or()
Interprets this node to a node of type LogicalOr.
A version 1.2+ assignment instruction.
Version number primitive used within the AST and semantic trees.
virtual CmpLt * as_cmp_lt()
Interprets this node to a node of type CmpLt.
std::vector< std::string > errors
List of accumulated errors.
ast::One< semantic::Program > root
Root node of the semantic tree, if analysis was successful.
Represents a value of type complex.
Maybe< StatementList > otherwise
The final else block, if any.
tree::Maybe< semantic::GotoInstruction > analyze_goto_instruction(const ast::Instruction &insn)
Analyzes the given cQASM 1.2+ goto instruction.
Represents a value of type bool.
One< Expression > frm
The first value.
Representation of an error model.
std::list< Scope > scope_stack
Scope stack.
Contains helper classes and objects for the lexer and parser generated by flex/bison, as well as the entry points for invoking the parser directly, in case you don&#39;t need semantic analysis.
One< Expression > condition
The condition for starting another iteration.
Representation of an available instruction (also known as gate) in the instruction set...
AnalysisResult result
The analysis result being constructed.
tree::Maybe< semantic::SetInstruction > analyze_set_instruction_operands(const ast::Expression &lhs_expr, const ast::Expression &rhs_expr)
Analyzes the given two operands as lhs and rhs of a set instruction.
void register_into(resolver::FunctionTable &table)
Registers a bunch of functions usable during constant propagation into the given function table...
One or more variable declaration for some type.
Value promote(const Value &value, const types::Type &type)
Type-checks and (if necessary) promotes the given value to the given type.
virtual CmpEq * as_cmp_eq()
Interprets this node to a node of type CmpEq.
values::Value analyze_operator(const std::string &name, const tree::One< ast::Expression > &a, const tree::One< ast::Expression > &b=tree::One< ast::Expression >(), const tree::One< ast::Expression > &c=tree::One< ast::Expression >())
Parses an operator.
values::Value analyze_as(const ast::Expression &expression, TypeArgs... type_args)
Shorthand for parsing an expression and promoting it to the given type, constructed in-place with the...
Represents a matrix literal.
tree::Many< values::ConstInt > analyze_index_list(const ast::IndexList &index_list, size_t size)
Parses an index list.
One< IndexList > indices
The list of indices.
cqasm::tree::One< T > One
Any version 1.2+ structured control-flow statement.
virtual LogicalAnd * as_logical_and()
Interprets this node to a node of type LogicalAnd.
cqasm::v1::primitives::Str name
The identifier.
Table of all overloads of all constant propagation functions.
One< ExpressionList > operands
Operands for the instruction.
Scope(const resolver::MappingTable &mappings, const resolver::FunctionTable &functions, const resolver::InstructionTable &instruction_set)
Creates the global scope.
AnalyzerHelper(const Analyzer &analyzer, const ast::Program &ast)
Analyzes the given AST using the given analyzer.
void register_error_model(const error_model::ErrorModel &error_model)
Registers an error model.
virtual CmpNe * as_cmp_ne()
Interprets this node to a node of type CmpNe.
virtual IfElse * as_if_else()
Interprets this node to a node of type IfElse.
virtual Add * as_add()
Interprets this node to a node of type Add.
Matrix< Real > RMatrix
Matrix of real numbers.
virtual RepeatUntilLoop * as_repeat_until_loop()
Interprets this node to a node of type RepeatUntilLoop.
One< StatementList > body
The loop body.
void analyze_bundle_ext(const ast::Bundle &bundle)
Analyzes the given bundle and, if valid, adds it to the current scope/block using API version 1...
void analyze_statements(const ast::StatementList &statements)
Analyzes the given statement list, adding the analyzed statements to the current subcircuit (API 1...
tree::Maybe< semantic::SetInstruction > analyze_set_instruction(const ast::Instruction &insn)
Analyzes the given cQASM 1.2+ set instruction.
Namespace for the "new" cQASM 1.x API.
virtual Modulo * as_modulo()
Interprets this node to a node of type Modulo.
bool case_insensitive_equals(const std::string &lhs, const std::string &rhs)
Case-insensitive string compare.
Definition: cqasm-utils.cpp:26
tree::Maybe< semantic::Block > get_current_block(const tree::Annotatable &source)
Returns a reference to the block that&#39;s currently being built (1.2+).
bool within_loop
Whether we&#39;re within at least one for, foreach, while, or repeat-until loop.
virtual FunctionCall * as_function_call()
Interprets this node to a node of type FunctionCall.
primitives::Int analyze_as_const_int(const ast::Expression &expression)
Shorthand for parsing an expression to a constant integer.
void analyze_variables(const ast::Variables &variables)
Analyzes the given declaration of one or more variables and, if valid, adds them to the current scope...
void analyze_structured(const ast::Structured &structured)
Analyzes the given structured control-flow statement and, if valid, adds it to the current scope/bloc...
values::Value analyze_matrix(const ast::MatrixLiteral &matrix_lit)
Parses a matrix.
ast::One< ast::Root > root
Root node of the AST, if analysis was sufficiently successful.
virtual JsonLiteral * as_json_literal()
Interprets this node to a node of type JsonLiteral.
Represents a value of type real_matrix.
void register_instruction(const instruction::Instruction &instruction)
Registers an instruction type.
tree::One< Node > Value
A cQASM value, either known at compile-time or an expression for something only known at runtime...
virtual MatrixLiteral * as_matrix_literal()
Interprets this node to a node of type MatrixLiteral.
virtual CmpLe * as_cmp_le()
Interprets this node to a node of type CmpLe.
virtual BitwiseNot * as_bitwise_not()
Interprets this node to a node of type BitwiseNot.
tree::Maybe< semantic::RepeatUntilLoop > analyze_repeat_until_loop(const ast::RepeatUntilLoop &repeat_until_loop)
Analyzes the given repeat-until loop.
One< Identifier > alias
The identifier used to refer to the expression.
tree::One< TypeBase > Type
A cQASM type.
::tree::base::Any< T > Any
Definition: cqasm-tree.hpp:29
Type of a complex number (2x IEEE double).
resolver::FunctionTable functions
The functions visible within this scope.
Table of all mappings within a certain scope.
::tree::base::Many< T > Many
Definition: cqasm-tree.hpp:32
Many< Instruction > items
The list of parallel instructions.
void add_to_current_block(const tree::Maybe< semantic::Statement > &stmt)
Adds an analyzed statement to the current block (1.2+).
virtual ShiftLeft * as_shift_left()
Interprets this node to a node of type ShiftLeft.
virtual Divide * as_divide()
Interprets this node to a node of type Divide.
tree::Any< TypeBase > Types
Zero or more cQASM types.
virtual LogicalXor * as_logical_xor()
Interprets this node to a node of type LogicalXor.
tree::One< semantic::ErrorModel > resolve(const std::string &name, const values::Values &args) const
Resolves an error model.
void add(const instruction::Instruction &type)
Registers an instruction type.
tree::Maybe< semantic::Subcircuit > get_current_subcircuit(const tree::Annotatable &source)
Returns a reference to the subcircuit that&#39;s currently being built.
tree::Maybe< semantic::Instruction > analyze_instruction(const ast::Instruction &insn)
Analyzes the given instruction.
ParseResult parse_string(const std::string &data, const std::string &filename)
Parse the given string.
virtual ShiftRightLogic * as_shift_right_logic()
Interprets this node to a node of type ShiftRightLogic.
Any< Statement > items
The list of statements.
One< Identifier > typ
Name of the type.
A complete program.
virtual BitwiseXor * as_bitwise_xor()
Interprets this node to a node of type BitwiseXor.
void register_function(const std::string &name, const types::Types &param_types, const resolver::FunctionImpl &impl)
Registers a function, usable within expressions.
tree::Maybe< semantic::ForLoop > analyze_for_loop(const ast::ForLoop &for_loop)
Analyzes the given C-style for loop.
Any< Expression > items
The list of expressions.
One< StatementList > body
The loop body.
std::string lowercase(const std::string &name)
Makes a string lowercase.
Definition: cqasm-utils.cpp:15
One< Expression > expr
The aliased expression.
Maybe< Assignment > update
The updating assignment, done at the end of the loop body and upon continue.
values::Value analyze_expression(const ast::Expression &expression)
Parses any kind of expression.
virtual CmpGt * as_cmp_gt()
Interprets this node to a node of type CmpGt.
Helper class for analyzing a single AST.
One< Expression > condition
The condition for starting another iteration.
void analyze_bundle(const ast::Bundle &bundle)
Analyzes the given bundle and, if valid, adds it to the current subcircuit using API version 1...
Maybe< Expression > condition
Optional conditional expression.
virtual Index * as_index()
Interprets this node to a node of type Index.
void register_default_functions_and_mappings()
Registers a number of default functions and mappings, such as the operator functions, the usual trigonometric functions, mappings for pi, eu (aka e, 2.718...), im (imaginary unit) and so on.
Represents a value of type real.
void analyze_version(const ast::Version &ast)
Parses the version tag.
values::Value call(const std::string &name, const values::Values &args) const
Calls a function.
::tree::base::One< T > One
Definition: cqasm-tree.hpp:26
virtual CmpGe * as_cmp_ge()
Interprets this node to a node of type CmpGe.
tree::Maybe< semantic::Block > analyze_subblock(const ast::StatementList &statements, bool is_loop)
Analyzes a statement list corresponding to a structured control-flow subblock (1.2+).
const Analyzer & analyzer
The analyzer associated with this helper.
Version parse_string(const std::string &data, const std::string &filename)
Parse the given string as a file to get its version number.
void add(const std::string &name, const types::Types &param_types, const FunctionImpl &impl)
Registers a function.
Represents a value of type complex_matrix.
Scope & get_global_scope()
Returns a reference to the global scope.
virtual StringLiteral * as_string_literal()
Interprets this node to a node of type StringLiteral.
One< StatementList > body
The loop body.
virtual ForLoop * as_for_loop()
Interprets this node to a node of type ForLoop.
void context(const tree::Annotatable &node)
Sets the context of this error to the SourceLocation annotation of the given node, if the error doesn&#39;t already have such a context.
Definition: cqasm-error.cpp:29
Indexation operator.
std::function< values::Value(const values::Values &)> FunctionImpl
C++ function representing (one of the overloads of) a function usable in cQASM constant expressions...
virtual BreakStatement * as_break_statement()
Interprets this node to a node of type BreakStatement.
int compare(const Version &other) const
Compares this version against the other version.
void analyze_error_model(const ast::Instruction &insn)
Analyzes the error model meta-instruction and, if valid, adds it to the analysis result.
Represents a comma-separated list of expressions.
::tree::annotatable::Annotatable Annotatable
Definition: cqasm-tree.hpp:19
ParseResult parse_file(const std::string &filename)
Parse the given file.
AnalysisResult analyze_string(const std::string &data, const std::string &filename="<unknown>") const
Parses and analyzes the given string.
Any kind of expression.
One< Expression > condition
The condition for stopping iteration.
virtual WhileLoop * as_while_loop()
Interprets this node to a node of type WhileLoop.
void register_mapping(const std::string &name, const values::Value &value)
Registers an initial mapping from the given name to the given value.
ast::One< semantic::Program > unwrap(std::ostream &out=std::cerr) const
"Unwraps" the result (as you would in Rust) to get the program node or an exception.
Exception used for analysis errors.
Definition: cqasm-error.hpp:27
Any< AnnotationData > annotations
Zero or more annotations attached to this object.
tree::Any< semantic::AnnotationData > analyze_annotations(const tree::Any< ast::AnnotationData > &annotations)
Analyzes the given list of annotations.
virtual BitwiseAnd * as_bitwise_and()
Interprets this node to a node of type BitwiseAnd.