GCC Code Coverage Report

Directory: ./
File: Utils/Expression.cpp
Date: 2022-10-15 05:10:18
Warnings: 4 unchecked decisions!
Exec Total Coverage
Lines: 81 84 96.4%
Functions: 16 16 100.0%
Branches: 102 170 60.0%
Decisions: 16 26 61.5%
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 "Expression.hpp"
16
17 #include <optional>
18
19 #include "Constants.hpp"
20 #include "Symbols.hpp"
21 #include "symengine/symengine_exception.h"
22
23 namespace tket {
24
25 71468 bool approx_0(const Expr& e, double tol) {
26
1/2
✓ Branch 1 taken 71468 times.
✗ Branch 2 not taken.
 71468 std::optional<double> v = eval_expr(e);
27
5/6
✓ Branch 1 taken 71022 times.
✓ Branch 2 taken 446 times.
✓ Branch 4 taken 71022 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12394 times.
✓ Branch 8 taken 58628 times.
 71468 return v && (std::abs(v.value()) < tol);
28 }
29
30 1966705 double fmodn(double x, unsigned n) {
31 1966705 x /= n;
32 1966705 x -= floor(x);
33 1966705 return n * x;
34 }
35
36 1182417 bool approx_eq(double x, double y, unsigned mod, double tol) {
37 1182417 double r = fmodn(x - y, mod);
38
4/4
✓ Branch 0 taken 900098 times.
✓ Branch 1 taken 282319 times.
✓ Branch 2 taken 1122 times.
✓ Branch 3 taken 898976 times.
 1182417 return r < tol || r > mod - tol;
39 }
40
41 126 SymSet expr_free_symbols(const Expr& e) {
42 126 SymSet symbols;
43
5/8
✓ Branch 1 taken 126 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 126 times.
✗ Branch 5 not taken.
✓ Branch 10 taken 8 times.
✗ Branch 11 not taken.
✓ Branch 14 taken 8 times.
✓ Branch 15 taken 126 times.
0/1
? Decision couldn't be analyzed.
 134 for (auto x : SymEngine::free_symbols(e)) {
44
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 symbols.insert(SymEngine::rcp_static_cast<const SymEngine::Symbol>(x));
45 134 }
46 126 return symbols;
47 }
48
49 1237978 SymSet expr_free_symbols(const std::vector<Expr>& es) {
50 1237978 SymSet symbols;
51
3/4
✓ Branch 4 taken 1090118 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 1090118 times.
✓ Branch 9 taken 1237978 times.
0/1
? Decision couldn't be analyzed.
 2328096 for (auto e : es) {
52
5/8
✓ Branch 1 taken 1090118 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1090118 times.
✗ Branch 5 not taken.
✓ Branch 10 taken 2664 times.
✗ Branch 11 not taken.
✓ Branch 14 taken 2664 times.
✓ Branch 15 taken 1090118 times.
0/1
? Decision couldn't be analyzed.
 1092782 for (auto x : SymEngine::free_symbols(e)) {
53
2/4
✓ Branch 1 taken 2664 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2664 times.
✗ Branch 5 not taken.
 2664 symbols.insert(SymEngine::rcp_static_cast<const SymEngine::Symbol>(x));
54 1092782 }
55 1090118 }
56 1237978 return symbols;
57 }
58
59 2469899 std::optional<double> eval_expr(const Expr& e) {
60
2/2
✓ Branch 4 taken 6165 times.
✓ Branch 5 taken 2463734 times.
2/2
✓ Decision 'true' taken 6165 times.
✓ Decision 'false' taken 2463734 times.
 2469899 if (!SymEngine::free_symbols(e).empty()) {
61 6165 return std::nullopt;
62 } else {
63 try {
64
2/4
✓ Branch 1 taken 2463734 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2463734 times.
✗ Branch 5 not taken.
 2463734 return SymEngine::eval_double(e);
65 ✗ } catch (SymEngine::NotImplementedError&) {
66 ✗ return std::nullopt;
67 }
68 }
69 }
70
71 39 std::optional<Complex> eval_expr_c(const Expr& e) {
72
1/2
✗ Branch 4 not taken.
✓ Branch 5 taken 39 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 39 times.
 39 if (!SymEngine::free_symbols(e).empty()) {
73 ✗ return std::nullopt;
74 } else {
75 39 return SymEngine::eval_complex_double(e);
76 }
77 }
78
79 741899 std::optional<double> eval_expr_mod(const Expr& e, unsigned n) {
80
1/2
✓ Branch 1 taken 741899 times.
✗ Branch 2 not taken.
 741899 std::optional<double> reduced_val = eval_expr(e);
81
2/2
✓ Branch 1 taken 909 times.
✓ Branch 2 taken 740990 times.
2/2
✓ Decision 'true' taken 740990 times.
✓ Decision 'false' taken 909 times.
 741899 if (!reduced_val) return std::nullopt;
82
1/2
✓ Branch 1 taken 740990 times.
✗ Branch 2 not taken.
 740990 double val = reduced_val.value();
83 740990 double val4 = 4 * val;
84 740990 long nearest_val4 = std::lrint(val4);
85
2/2
✓ Branch 1 taken 675277 times.
✓ Branch 2 taken 65713 times.
2/2
✓ Decision 'true' taken 675277 times.
✓ Decision 'false' taken 65713 times.
 740990 if (std::abs(val4 - nearest_val4) < 4 * EPS) {
86 675277 val = nearest_val4 * 0.25;
87 }
88
1/2
✓ Branch 1 taken 740990 times.
✗ Branch 2 not taken.
 740990 return fmodn(val, n);
89 }
90
91 // Evaluate cos(pi x / 12). If x is close to a multiple of pi/12, it is clamped
92 // to that exact multiple and the return value is exact.
93 // Is is assumed that 0 <= x < 24.
94 213278 static Expr cos_pi_by_12_times(double x) {
95 static const double pi_by_12 = PI / 12;
96 static const Expr pi_by_12_sym =
97
8/16
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 213277 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 1 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 1 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
 213278 SymEngine::div(SymEngine::pi, SymEngine::integer(12));
98 213278 int n(x + 0.5); // nearest integer to x (assuming x >= 0)
99
2/2
✓ Branch 1 taken 158726 times.
✓ Branch 2 taken 54552 times.
0/1
? Decision couldn't be analyzed.
 213278 if (std::abs(x - n) < EPS) {
100
4/8
✓ Branch 1 taken 158726 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 158726 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 158726 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 158726 times.
✗ Branch 12 not taken.
 317452 Expr z = SymEngine::cos(n * pi_by_12_sym);
101 158726 return z;
102 158726 } else {
103 54552 return Expr(cos(pi_by_12 * x));
104 }
105 }
106
107 214008 Expr cos_halfpi_times(const Expr& e) {
108
3/6
✓ Branch 1 taken 214008 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 214008 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 214008 times.
✗ Branch 8 not taken.
 214008 std::optional<double> x = eval_expr_mod(e / 2); // >= 0
109
2/2
✓ Branch 1 taken 213278 times.
✓ Branch 2 taken 730 times.
2/2
✓ Decision 'true' taken 213278 times.
✓ Decision 'false' taken 730 times.
 214008 if (x) {
110
2/4
✓ Branch 1 taken 213278 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 213278 times.
✗ Branch 5 not taken.
 213278 return cos_pi_by_12_times(12 * x.value());
111 } else {
112
7/14
✓ Branch 1 taken 730 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 730 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 730 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 730 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 730 times.
✗ Branch 14 not taken.
✓ Branch 17 taken 730 times.
✗ Branch 18 not taken.
✓ Branch 20 taken 730 times.
✗ Branch 21 not taken.
 1460 return SymEngine::cos(SymEngine::expand(e * SymEngine::pi / 2));
113 }
114 }
115
116 107004 Expr sin_halfpi_times(const Expr& e) {
117
4/8
✓ Branch 2 taken 107004 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 107004 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 107004 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 107004 times.
✗ Branch 12 not taken.
 214008 return cos_halfpi_times(SymEngine::expand(SymEngine::integer(1) - e));
118 }
119
120 322737 Expr minus_times(const Expr& e) {
121
1/2
✓ Branch 1 taken 322737 times.
✗ Branch 2 not taken.
 322737 Expr e1 = -e;
122
1/2
✓ Branch 1 taken 322737 times.
✗ Branch 2 not taken.
 322737 Expr e2 = SymEngine::expand(e1);
123
124
2/4
✓ Branch 2 taken 322737 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 322737 times.
✗ Branch 6 not taken.
 322737 unsigned e1_size = e1.get_basic()->dumps().size();
125
2/4
✓ Branch 2 taken 322737 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 322737 times.
✗ Branch 6 not taken.
 322737 unsigned e2_size = e2.get_basic()->dumps().size();
126
127
3/4
✓ Branch 0 taken 3484 times.
✓ Branch 1 taken 319253 times.
✓ Branch 3 taken 322737 times.
✗ Branch 4 not taken.
 645474 return e2_size < e1_size ? e2 : e1;
128 322737 }
129
130 55829 bool equiv_expr(const Expr& e0, const Expr& e1, unsigned n, double tol) {
131
1/2
✓ Branch 1 taken 55829 times.
✗ Branch 2 not taken.
 55829 std::optional<double> eval0 = eval_expr(e0);
132
1/2
✓ Branch 1 taken 55829 times.
✗ Branch 2 not taken.
 55829 std::optional<double> eval1 = eval_expr(e1);
133
7/8
✓ Branch 1 taken 55689 times.
✓ Branch 2 taken 140 times.
✓ Branch 4 taken 42 times.
✓ Branch 5 taken 55647 times.
✓ Branch 6 taken 182 times.
✓ Branch 7 taken 55647 times.
✓ Branch 9 taken 182 times.
✗ Branch 10 not taken.
2/2
✓ Decision 'true' taken 55647 times.
✓ Decision 'false' taken 182 times.
 55829 if (!eval0 || !eval1) return e0 == e1;
134
3/6
✓ Branch 1 taken 55647 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 55647 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 55647 times.
✗ Branch 8 not taken.
 55647 return approx_eq(eval0.value(), eval1.value(), n, tol);
135 }
136
137 1130968 bool equiv_val(const Expr& e, double x, unsigned n, double tol) {
138
1/2
✓ Branch 1 taken 1130968 times.
✗ Branch 2 not taken.
 1130968 std::optional<double> eval = eval_expr(e);
139
2/2
✓ Branch 1 taken 4200 times.
✓ Branch 2 taken 1126768 times.
2/2
✓ Decision 'true' taken 1126768 times.
✓ Decision 'false' taken 4200 times.
 1130968 if (!eval) return false;
140
2/4
✓ Branch 1 taken 1126768 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1126768 times.
✗ Branch 5 not taken.
 1126768 return approx_eq(eval.value(), x, n, tol);
141 }
142
143 947770 bool equiv_0(const Expr& e, unsigned n, double tol) {
144 947770 return equiv_val(e, 0., n, tol);
145 }
146
147 590 std::optional<unsigned> equiv_Clifford(const Expr& e, unsigned n, double tol) {
148
1/2
✓ Branch 1 taken 590 times.
✗ Branch 2 not taken.
 590 std::optional<double> eval = eval_expr_mod(e, n);
149
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 590 times.
1/2
✓ Decision 'true' taken 590 times.
✗ Decision 'false' not taken.
 590 if (!eval) return std::nullopt;
150
1/2
✓ Branch 1 taken 590 times.
✗ Branch 2 not taken.
 590 double v_mod_n = eval.value();
151 590 unsigned nearest = lround(v_mod_n * 2);
152
2/2
✓ Branch 1 taken 370 times.
✓ Branch 2 taken 220 times.
2/2
✓ Decision 'true' taken 370 times.
✓ Decision 'false' taken 220 times.
 590 if (std::abs(v_mod_n - (nearest * 0.5)) < tol)
153 370 return nearest;
154 else
155 220 return std::nullopt;
156 }
157
158 } // namespace tket
159