GCC Code Coverage Report

Directory: ./
File: Circuit/DAGProperties.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 65 69 94.2%
Functions: 2 2 100.0%
Branches: 123 268 45.9%
Decisions: 22 24 91.7%
Line Branch Decision Exec Source
1 // Copyright 2019-2022 Cambridge Quantum Computing
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "DAGProperties.hpp"
16
17 #include <algorithm>
18 #include <tklog/TketLog.hpp>
19
20 #include "OpType/EdgeType.hpp"
21 #include "Utils/GraphHeaders.hpp"
22
23 namespace tket {
24
25 #ifdef CHECK
26 #error "Macro already defined!"
27 #endif
28 #define CHECK(p) \
29 do { \
30 if (!(p)) { \
31 tket_log()->warn("Invalid DAG: check (" #p ") failed."); \
32 return false; \
33 } \
34 } while (0)
35
36 enum class VertexType { Quantum, Classical, Measure };
37
38 57 bool is_valid(const DAG &G) {
39
7/8
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 799 times.
✓ Branch 6 taken 57 times.
✓ Branch 8 taken 799 times.
✓ Branch 9 taken 57 times.
✓ Branch 11 taken 57 times.
✓ Branch 12 taken 57 times.
 913 BGL_FORALL_VERTICES(v, G, DAG) {
40 799 EdgeSet q_in, c_in, b_in;
41
12/18
✓ Branch 1 taken 799 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 596 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 809 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1405 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 809 times.
✓ Branch 13 taken 596 times.
✓ Branch 15 taken 809 times.
✗ Branch 16 not taken.
✓ Branch 17 taken 809 times.
✓ Branch 18 taken 596 times.
✓ Branch 20 taken 1395 times.
✗ Branch 21 not taken.
✓ Branch 22 taken 596 times.
✓ Branch 23 taken 799 times.
 2204 BGL_FORALL_INEDGES(v, e, G, DAG) {
42
4/6
✓ Branch 1 taken 809 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 658 times.
✓ Branch 4 taken 92 times.
✓ Branch 5 taken 59 times.
✗ Branch 6 not taken.
 809 switch (G[e].type) {
43
1/1
✓ Decision 'true' taken 658 times.
 658 case EdgeType::Quantum:
44
1/2
✓ Branch 1 taken 658 times.
✗ Branch 2 not taken.
 658 q_in.insert(e);
45 658 break;
46
1/1
✓ Decision 'true' taken 92 times.
 92 case EdgeType::Classical:
47
1/2
✓ Branch 1 taken 92 times.
✗ Branch 2 not taken.
 92 c_in.insert(e);
48 92 break;
49
1/1
✓ Decision 'true' taken 59 times.
 59 case EdgeType::Boolean:
50
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 b_in.insert(e);
51 59 break;
52
0/1
✗ Decision 'true' not taken.
 ✗ default:
53 ✗ CHECK(!"unknown edge type");
54 }
55 }
56 799 EdgeSet q_out, c_out, b_out;
57
12/18
✓ Branch 1 taken 799 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 596 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 809 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1405 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 809 times.
✓ Branch 13 taken 596 times.
✓ Branch 15 taken 809 times.
✗ Branch 16 not taken.
✓ Branch 17 taken 809 times.
✓ Branch 18 taken 596 times.
✓ Branch 20 taken 1395 times.
✗ Branch 21 not taken.
✓ Branch 22 taken 596 times.
✓ Branch 23 taken 799 times.
 2204 BGL_FORALL_OUTEDGES(v, e, G, DAG) {
58
4/6
✓ Branch 1 taken 809 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 658 times.
✓ Branch 4 taken 92 times.
✓ Branch 5 taken 59 times.
✗ Branch 6 not taken.
 809 switch (G[e].type) {
59
1/1
✓ Decision 'true' taken 658 times.
 658 case EdgeType::Quantum:
60
1/2
✓ Branch 1 taken 658 times.
✗ Branch 2 not taken.
 658 q_out.insert(e);
61 658 break;
62
1/1
✓ Decision 'true' taken 92 times.
 92 case EdgeType::Classical:
63
1/2
✓ Branch 1 taken 92 times.
✗ Branch 2 not taken.
 92 c_out.insert(e);
64 92 break;
65
1/1
✓ Decision 'true' taken 59 times.
 59 case EdgeType::Boolean:
66
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 b_out.insert(e);
67 59 break;
68
0/1
✗ Decision 'true' not taken.
 ✗ default:
69 ✗ CHECK(!"unknown edge type");
70 }
71 }
72 799 std::set<port_t> in_ports, q_in_ports, q_out_ports, c_in_ports, c_out_ports,
73 799 b_in_ports;
74
2/2
✓ Branch 5 taken 658 times.
✓ Branch 6 taken 799 times.
2/2
✓ Decision 'true' taken 658 times.
✓ Decision 'false' taken 799 times.
 1457 for (const auto &e : q_in) {
75
1/2
✓ Branch 1 taken 658 times.
✗ Branch 2 not taken.
 658 port_t p = G[e].ports.second;
76
1/2
✓ Branch 1 taken 658 times.
✗ Branch 2 not taken.
 658 in_ports.insert(p);
77
1/2
✓ Branch 1 taken 658 times.
✗ Branch 2 not taken.
 658 q_in_ports.insert(p);
78 }
79
2/2
✓ Branch 5 taken 658 times.
✓ Branch 6 taken 799 times.
2/2
✓ Decision 'true' taken 658 times.
✓ Decision 'false' taken 799 times.
 1457 for (const auto &e : q_out) {
80
2/4
✓ Branch 1 taken 658 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 658 times.
✗ Branch 5 not taken.
 658 q_out_ports.insert(G[e].ports.first);
81 }
82
2/2
✓ Branch 5 taken 92 times.
✓ Branch 6 taken 799 times.
2/2
✓ Decision 'true' taken 92 times.
✓ Decision 'false' taken 799 times.
 891 for (const auto &e : c_in) {
83
1/2
✓ Branch 1 taken 92 times.
✗ Branch 2 not taken.
 92 port_t p = G[e].ports.second;
84
1/2
✓ Branch 1 taken 92 times.
✗ Branch 2 not taken.
 92 in_ports.insert(p);
85
1/2
✓ Branch 1 taken 92 times.
✗ Branch 2 not taken.
 92 c_in_ports.insert(p);
86 }
87
2/2
✓ Branch 5 taken 92 times.
✓ Branch 6 taken 799 times.
2/2
✓ Decision 'true' taken 92 times.
✓ Decision 'false' taken 799 times.
 891 for (const auto &e : c_out) {
88
2/4
✓ Branch 1 taken 92 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 92 times.
✗ Branch 5 not taken.
 92 c_out_ports.insert(G[e].ports.first);
89 }
90
2/2
✓ Branch 5 taken 59 times.
✓ Branch 6 taken 799 times.
2/2
✓ Decision 'true' taken 59 times.
✓ Decision 'false' taken 799 times.
 858 for (const auto &e : b_in) {
91
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 port_t p = G[e].ports.second;
92
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 in_ports.insert(p);
93
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 b_in_ports.insert(p);
94 }
95
96 // Now check the required properties.
97
98
1/8
✗ Branch 4 not taken.
✓ Branch 5 taken 799 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
 799 CHECK(
99 in_ports.size() ==
100 q_in_ports.size() + c_in_ports.size() + b_in_ports.size());
101
102 // Every Boolean out port matches a Classical out port.
103
2/2
✓ Branch 5 taken 59 times.
✓ Branch 6 taken 799 times.
2/2
✓ Decision 'true' taken 59 times.
✓ Decision 'false' taken 799 times.
 858 for (const Edge &e : b_out) {
104
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 port_t p = G[e].ports.first;
105
2/10
✓ Branch 3 taken 59 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 59 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
 121 CHECK(std::any_of(c_out.cbegin(), c_out.cend(), [&](const Edge &f) {
106 return G[f].ports.first == p;
107 }));
108 }
109
110
6/6
✓ Branch 1 taken 715 times.
✓ Branch 2 taken 84 times.
✓ Branch 4 taken 668 times.
✓ Branch 5 taken 47 times.
✓ Branch 6 taken 668 times.
✓ Branch 7 taken 131 times.
2/2
✓ Decision 'true' taken 668 times.
✓ Decision 'false' taken 131 times.
 799 if (c_in.empty() && c_out.empty()) {
111 // It is a Quantum vertex.
112 668 unsigned in_deg = q_in.size();
113 668 unsigned out_deg = q_out.size();
114
1/8
✗ Branch 1 not taken.
✓ Branch 2 taken 668 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 668 CHECK(q_in_ports.size() == in_deg);
115
1/8
✗ Branch 1 not taken.
✓ Branch 2 taken 668 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 668 CHECK(q_out_ports.size() == out_deg);
116
10/20
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 512 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 156 times.
✓ Branch 4 taken 391 times.
✓ Branch 5 taken 121 times.
✓ Branch 6 taken 235 times.
✓ Branch 7 taken 156 times.
✓ Branch 9 taken 356 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 356 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 668 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
 668 CHECK(
117 (in_deg == 0 && out_deg == 1) || (in_deg == 1 && out_deg == 0) ||
118 (q_in_ports == q_out_ports)); // bijection between in and out ports
119
1/8
✗ Branch 1 not taken.
✓ Branch 2 taken 668 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 668 CHECK(b_out.empty());
120
5/6
✓ Branch 1 taken 110 times.
✓ Branch 2 taken 21 times.
✓ Branch 4 taken 110 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 110 times.
✓ Branch 7 taken 21 times.
2/2
✓ Decision 'true' taken 110 times.
✓ Decision 'false' taken 21 times.
 131 } else if (q_in.empty() && q_out.empty()) {
121 // It is a Classical vertex.
122 110 unsigned in_deg = c_in.size();
123 110 unsigned out_deg = c_out.size();
124
1/8
✗ Branch 1 not taken.
✓ Branch 2 taken 110 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 110 CHECK(c_in_ports.size() == in_deg);
125
1/8
✗ Branch 1 not taken.
✓ Branch 2 taken 110 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 110 CHECK(c_out_ports.size() == out_deg);
126
10/20
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 47 times.
✓ Branch 4 taken 58 times.
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 11 times.
✓ Branch 7 taken 47 times.
✓ Branch 9 taken 16 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 16 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 110 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
 110 CHECK(
127 (in_deg == 0 && out_deg == 1) || (in_deg == 1 && out_deg == 0) ||
128 (c_in_ports == c_out_ports)); // bijection between in and out ports
129 } else {
130 // Check that it is a Measure vertex.
131
5/16
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 21 times.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 21 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 21 times.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
 21 CHECK(
132 q_in.size() == 1 && q_out.size() == 1 && c_in.size() == 1 &&
133 c_out.size() == 1);
134
5/16
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 21 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 21 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 21 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 21 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 21 CHECK(q_in_ports == q_out_ports && c_in_ports == c_out_ports);
135 }
136
3/6
✓ Branch 1 taken 799 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 799 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 799 times.
✗ Branch 8 not taken.
 799 }
137 57 return true;
138 }
139
140 #undef CHECK
141
142 } // namespace tket
143