1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2018 GRAME, Centre National de Creation Musicale
5 ---------------------------------------------------------------------
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 ************************************************************************
20 ************************************************************************/
21
22 #include <iostream>
23 #include <vector>
24
25 #include "dcond.hh"
26 #include "global.hh"
27 #include "ppsig.hh"
28
29 /*
30 * Dcond are conditions, boolean expressions in disjunctive normal form implemented
31 * as set of set of Tree
32 *
33 * disjoint: two boolean expressions a and b are disjoint if : a != a|b != b
34 * less specific : a is less specific than b if : a == a|b. True is the less specific condition.
35 *
36 * {{a,b,c},{d,e,..},...} = (a & b & c) | (d & e &...) | ...
37 * where {a,b,c}, {d,e,...} etc. are all disjoint two by two
38 * {{}} = True
39 *
40 * if A={a1,a2,a3...} denotes a1&a2&a3, and B={b1,b2,b3,..} denotes b1&b2&b3&...
41 * A and B are disjoint if A inter B != A and != B
42 * if B superset of A then A|B = A
43 * if A n B = A
44 */
45
46 // create a dnfCond from a simple expression
dnfCond(Tree c)47 Tree dnfCond(Tree c)
48 {
49 return singleton(singleton(c));
50 }
51
52 // create a cnfCond from a simple expression
cnfCond(Tree c)53 Tree cnfCond(Tree c)
54 {
55 return singleton(singleton(c));
56 }
57
58 // OR operation between two boolean expressions in CNF
59 // x&y v z = (x v z) & (y v z)
60 // x&y v a&b = (x v a&b) & (y v a&b)
61 // = (x v a) & (x v b) & (y v a) & (y v b)
62
63 // (a & b & c) v (e & f & g) =
64
65 // A*b + c*d
66 // a v c&d)
67 #if 0
68 Tree cnfOr(Tree c1, Tree c2)
69 {
70 if (isNil(c1)) { return c1; }
71 else if (isNil(c2)) { return c2; }
72 else {
73 std::vector<Tree> A;
74 while (isList(c1)) {
75 Tree h1 = hd(c1); c1 = tl(c1);
76 Tree t2 = c2;
77 while (isList(t2)) {
78 Tree h2 = hd(t2); t2 = tl(t2);
79 A.push_back(setUnion(h1,h2));
80 }
81 }
82 for(auto t1 : A) {
83 for (auto t2 : A) {
84 Tree ii = setUnion(t1,t2);
85 if (t1 == ii) {
86 t2 = ii;
87 } else if (t2 == ii) {
88 t1 = ii;
89 }
90 }
91 }
92 Tree c3 = gGlobal->nil;
93 for (auto t1 : A) { c3 = addElement(t1,c3); }
94 return c3;
95 }
96 }
97 #else
98
cnfOr(Tree c1,Tree c2)99 Tree cnfOr(Tree c1, Tree c2)
100 {
101 if (isNil(c1)) {
102 return c1;
103 } else if (isNil(c2)) {
104 return c2;
105 } else {
106 std::vector<Tree> A;
107 while (isList(c1)) {
108 Tree h1 = hd(c1);
109 c1 = tl(c1);
110 Tree t2 = c2;
111 while (isList(t2)) {
112 Tree h2 = hd(t2);
113 t2 = tl(t2);
114 A.push_back(setUnion(h1, h2));
115 }
116 }
117
118 // simplify conditions that can be simplied
119 size_t n = A.size();
120 for (size_t i = 0; i < n; i++) { // for each A[i]
121 for (size_t j = i + 1; j < n; j++) { // for each A[i]
122 Tree ii = setUnion(A[i], A[j]);
123 if (A[j] == ii) {
124 A[i] = A[j]; // A[j] is more general and replace A[i]
125 } else if (A[i] == ii) {
126 A[j] = A[i]; // A[i] is more general and replace A[j]
127 }
128 }
129 }
130
131 Tree c3 = gGlobal->nil;
132 for (auto t1 : A) {
133 c3 = addElement(t1, c3);
134 }
135 return c3;
136 }
137 }
138 #endif
139
140 // AND operation between two boolean expressions in CNF
cnfAnd(Tree c1,Tree c2)141 Tree cnfAnd(Tree c1, Tree c2)
142 {
143 if (isNil(c1)) {
144 return c2;
145 } else if (isNil(c2)) {
146 return c1;
147 } else {
148 // convert sets to vectors for convenient manipulations
149 int n = 0;
150 std::vector<Tree> A;
151 while (isList(c1)) {
152 A.push_back(hd(c1));
153 c1 = tl(c1);
154 n++;
155 }
156 int m = 0;
157 std::vector<Tree> B;
158 while (isList(c2)) {
159 B.push_back(hd(c2));
160 c2 = tl(c2);
161 m++;
162 }
163
164 // simplify conditions that can be simplied
165 for (int i = 0; i < n; i++) { // for each A[i]
166 for (int j = 0; j < m; j++) { // for each B[i]
167 Tree ii = setUnion(A[i], B[j]);
168 if (B[j] == ii) {
169 A[i] = B[j]; // B[j] is more general and replace A[i]
170 } else if (A[i] == ii) {
171 B[j] = A[i]; // A[i] is more general and replace B[j]
172 }
173 }
174 }
175
176 // compute the resulting expression
177 Tree c3 = gGlobal->nil;
178 for (int i = 0; i < n; i++) {
179 c3 = addElement(A[i], c3);
180 }
181 for (int j = 0; j < m; j++) {
182 c3 = addElement(B[j], c3);
183 }
184 return c3;
185 }
186 }
187
188 // True c1 is less specific (i.e. more general) than c2
cnfLess(Tree c1,Tree c2)189 bool cnfLess(Tree c1, Tree c2)
190 {
191 return c1 == cnfOr(c1, c2);
192 }
193
194 // And operation between two boolean expressions in DNF : A REVOIR !!!
TRACE_dnfAnd(Tree c1,Tree c2)195 Tree TRACE_dnfAnd(Tree c1, Tree c2)
196 {
197 if (isNil(c1)) {
198 return c2;
199 } else if (isNil(c2)) {
200 return c1;
201 } else {
202 int n = 0;
203 std::vector<Tree> A;
204 while (isList(c1)) {
205 Tree h1 = hd(c1);
206 c1 = tl(c1);
207 Tree t2 = c2;
208 while (isList(t2)) {
209 Tree h2 = hd(t2);
210 t2 = tl(t2);
211 A.push_back(setUnion(h1, h2));
212 n++;
213 }
214 }
215 // simplify conditions that can be simplied
216 for (int i = 0; i < n; i++) { // for each A[i]
217 for (int j = i + 1; j < n; j++) { // for each B[i]
218 Tree ii = setIntersection(A[i], A[j]);
219 if (A[j] == ii) {
220 A[i] = A[j]; // B[j] is more general and replace A[i]
221 } else if (A[i] == ii) {
222 A[j] = A[i]; // A[i] is more general and replace B[j]
223 }
224 }
225 }
226
227 // compute the resulting expression
228 Tree c3 = gGlobal->nil;
229 for (int i = 0; i < n; i++) {
230 c3 = addElement(A[i], c3);
231 }
232 return c3;
233 }
234 }
235
dnfAnd(Tree c1,Tree c2)236 Tree dnfAnd(Tree c1, Tree c2)
237 {
238 // std::cout << ppsig(c1) << " .AND. " << ppsig(c2) << " = ";
239 Tree r = TRACE_dnfAnd(c1, c2);
240 // std::cout << ppsig(r) << std::endl;
241 return r;
242 }
243
244 // Or operation between two boolean expressions in DNF
TRACE_dnfOr(Tree c1,Tree c2)245 Tree TRACE_dnfOr(Tree c1, Tree c2)
246 {
247 if (isNil(c1)) {
248 return c1;
249 } else if (isNil(c2)) {
250 return c2;
251 } else {
252 // convert sets to vectors for convenient manipulations
253 int n = 0;
254 std::vector<Tree> A;
255 while (isList(c1)) {
256 A.push_back(hd(c1));
257 c1 = tl(c1);
258 n++;
259 }
260 int m = 0;
261 std::vector<Tree> B;
262 while (isList(c2)) {
263 B.push_back(hd(c2));
264 c2 = tl(c2);
265 m++;
266 }
267
268 // simplify conditions that can be simplied
269 for (int i = 0; i < n; i++) { // for each A[i]
270 for (int j = 0; j < m; j++) { // for each B[i]
271 Tree ii = setIntersection(A[i], B[j]);
272 if (B[j] == ii) {
273 A[i] = B[j]; // B[j] is more general and replace A[i]
274 } else if (A[i] == ii) {
275 B[j] = A[i]; // A[i] is more general and replace B[j]
276 }
277 }
278 }
279 // compute the resulting expression
280 Tree c3 = gGlobal->nil;
281 for (int i = 0; i < n; i++) {
282 c3 = addElement(A[i], c3);
283 }
284 for (int j = 0; j < m; j++) {
285 c3 = addElement(B[j], c3);
286 }
287 return c3;
288 }
289 }
290
dnfOr(Tree c1,Tree c2)291 Tree dnfOr(Tree c1, Tree c2)
292 {
293 // std::cout << ppsig(c1) << " .OR. " << ppsig(c2) << " = ";
294 Tree r = TRACE_dnfOr(c1, c2);
295 // std::cout << ppsig(r) << std::endl;
296 return r;
297 }
298
299 // True c1 is less specific (i.e. more general) than c2
dnfLess(Tree c1,Tree c2)300 bool dnfLess(Tree c1, Tree c2)
301 {
302 return c1 == dnfOr(c1, c2);
303 }
304