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 <stdio.h>
23 #include <time.h>
24 #include <algorithm>
25 #include <fstream>
26 #include <iostream>
27
28 #include "exception.hh"
29 #include "global.hh"
30 #include "ppsig.hh"
31 #include "prim2.hh"
32 #include "recursivness.hh"
33 #include "sigprint.hh"
34 #include "sigtype.hh"
35 #include "sigtyperules.hh"
36 #include "tlib.hh"
37 #include "xtended.hh"
38
39 //--------------------------------------------------------------------------
40 // prototypes
41
42 static void setSigType(Tree sig, Type t);
43 static Type getSigType(Tree sig);
44 static TupletType* initialRecType(Tree t);
45 static TupletType* maximalRecType(Tree t);
46
47 static Type T(Tree term, Tree env);
48
49 static Type infereSigType(Tree term, Tree env);
50 static Type infereFFType(Tree ff, Tree ls, Tree env);
51 static Type infereFConstType(Tree type);
52 static Type infereFVarType(Tree type);
53 static Type infereRecType(Tree var, Tree body, Tree env);
54 static Type infereReadTableType(Type tbl, Type ri);
55 static Type infereWriteTableType(Type tbl, Type wi, Type wd);
56 static Type infereProjType(Type t, int i, int vec);
57 static Type infereXType(Tree sig, Tree env);
58 static Type infereDocConstantTblType(Type size, Type init);
59 static Type infereDocWriteTblType(Type size, Type init, Type widx, Type wsig);
60 static Type infereDocAccessTblType(Type tbl, Type ridx);
61 static Type infereWaveformType(Tree lv, Tree env);
62
63 TupletType derefRecCert(Type t);
64
65 static interval arithmetic(int opcode, const interval& x, const interval& y);
66
67 // Uncomment to activate type inferrence tracing
68 // #define TRACE(x) x
69
70 #define TRACE(x) \
71 { \
72 ; \
73 }
74
75 /**
76 * The empty type environment (also property key for closed term type)
77 */
78
79 /**
80 * Do one step of type inference on the recursive signal groups of a signal
81 * The types of the recursive signals are updated to vtype and then vtype is updated to the next step.
82 *
83 * @param vrec array of all the recursive signal groups
84 * @param vdef definitions of all the recursive signal groups (vector of _lists_)
85 * @param vdefSizes number of signals in each recursive signal groups
86 * @param vtype types of the recursive signals
87 * @param inter if set to false, the interval of the new type is the union of the old one and the computed one, otherwise it is the intersection
88 */
89
updateRecTypes(vector<Tree> & vrec,const vector<Tree> & vdef,const vector<int> & vdefSizes,vector<Type> & vtype,const bool inter)90 void updateRecTypes(vector<Tree>& vrec, const vector<Tree>& vdef, const vector<int>& vdefSizes,
91 vector<Type>& vtype, const bool inter)
92 {
93 Type newType;
94 vector<Type> newTuplet;
95 TupletType newRecType;
96 TupletType oldRecType;
97 interval newI;
98 interval oldI;
99
100 const int n = vdef.size();
101
102 CTree::startNewVisit();
103
104 // init recursive types
105 for (int i = 0; i < n; i++) {
106 setSigType(vrec[i], vtype[i]);
107 // cerr << i << "-" << *getSigType(vrec[i]) << endl;
108 vrec[i]->setVisited();
109 }
110
111 // cerr << "compute recursive types" << endl;
112 for (int i = 0; i < n; i++) {
113 newType = T(vdef[i], gGlobal->NULLTYPEENV);
114 newTuplet.clear();
115 oldRecType = derefRecCert(getSigType(vrec[i]));
116 newRecType = derefRecCert(newType);
117
118 for (int j = 0; j < vdefSizes[i]; j++) {
119 newTuplet.push_back(newRecType[j]);
120 newI = newRecType[j]->getInterval();
121 oldI = oldRecType[j]->getInterval();
122
123 newI = inter ? intersection(newI, oldI) : reunion(newI, oldI);
124 newTuplet[j] = newTuplet[j]->promoteInterval(newI);
125 }
126 vtype[i] = new TupletType(newTuplet);
127 }
128 }
129
130 /**
131 * Fully annotate every subtree of term with type information.
132 * @param sig the signal term tree to annotate
133 * @param causality when true check causality issues
134 */
135
typeAnnotation(Tree sig,bool causality)136 void typeAnnotation(Tree sig, bool causality)
137 {
138 gGlobal->gCausality = causality;
139 Tree sl = symlist(sig);
140 int n = len(sl);
141
142 int size;
143 bool finished = false;
144
145 vector<Tree> vrec; ///< array of all the recursive signal groups
146 vector<Tree> vdef; ///< definitions of all the recursive signal groups (vector of _lists_)
147 vector<int> vdefSizes; ///< number of signals for each group
148 vector<Type> vtype; ///< type of the recursive signals
149 vector<Type> vtypeUp; ///< an upperbound of the recursive signals type
150 vector<TupletType> vUp; ///< the unfolded version of the variable above
151
152 vector<vector<int>> vAgeMin; ///< age of the minimum of every subsignal of the recursive signal
153 vector<vector<int>> vAgeMax; ///< age of the maximum of every subsignal of the recursive signal
154
155 // work variables used in widening loop
156
157 Type newType;
158 vector<Type> newTuplet;
159 TupletType newRecType;
160 TupletType oldRecType;
161 interval newI;
162 interval oldI;
163
164 // cerr << "Symlist " << *sl << endl;
165 for (Tree l = sl; isList(l); l = tl(l)) {
166 Tree id, body;
167 faustassert(isRec(hd(l), id, body));
168 if (!isRec(hd(l), id, body)) {
169 continue;
170 }
171 vrec.push_back(hd(l));
172 vdef.push_back(body);
173
174 size = len(body);
175 vdefSizes.push_back(size);
176 vAgeMin.push_back(vector<int>(size, 0));
177 vAgeMax.push_back(vector<int>(size, 0));
178 }
179
180 // init recursive types
181 for (int i = 0; i < n; i++) {
182 vtypeUp.push_back(maximalRecType(vdef[i]));
183 vtype.push_back(initialRecType(vdef[i]));
184 }
185
186 faustassert(int(vrec.size()) == n);
187 faustassert(int(vdef.size()) == n);
188 faustassert(int(vtype.size()) == n);
189 faustassert((int)vAgeMin.size() == n);
190 faustassert((int)vAgeMax.size() == n);
191
192 // cerr << "compute upper bounds for recursive types" << endl;
193
194 for (int k=0; k < gGlobal->gNarrowingLimit; k++) {
195 updateRecTypes(vrec, vdef, vdefSizes, vtypeUp, true);
196 }
197
198 for (auto ty : vtypeUp) {
199 vUp.push_back(derefRecCert(ty));
200 }
201
202 // cerr << "find an upperbound of the least fixpoint" << endl;
203
204 while (!finished) {
205 updateRecTypes(vrec, vdef, vdefSizes, vtype, false);
206
207 // check finished
208 finished = true;
209 for (int i = 0; i < n; i++) {
210 newTuplet.clear();
211 // cerr << i << "-" << *vrec[i] << ":" << *getSigType(vrec[i]) << " => " << *vtype[i] << endl;
212 if (vtype[i] != getSigType(vrec[i])) {
213 finished = false;
214 newRecType = derefRecCert(vtype[i]);
215 oldRecType = derefRecCert(getSigType(vrec[i]));
216 for (int j = 0; j < vdefSizes[i]; j++) {
217 newTuplet.push_back(newRecType[j]);
218 newI = newRecType[j]->getInterval();
219 oldI = oldRecType[j]->getInterval();
220
221 TRACE(cerr << gGlobal->TABBER << "inspecting " << newTuplet[j] << endl;)
222 if (newI.lo != oldI.lo) {
223 faustassert(newI.lo < oldI.lo);
224 vAgeMin[i][j]++;
225 if (vAgeMin[i][j] > gGlobal->gWideningLimit) {
226 TRACE(cerr << gGlobal->TABBER << "low widening of " << newTuplet[j] << endl;)
227 newI.lo = vUp[i][j]->getInterval().lo;
228 }
229 }
230
231 if (newI.hi != oldI.hi) {
232 faustassert(newI.hi > oldI.hi);
233 vAgeMax[i][j]++;
234 if (vAgeMax[i][j] > gGlobal->gWideningLimit) {
235 TRACE(cerr << gGlobal->TABBER << "up widening of " << newTuplet[j] << endl;)
236 newI.hi = vUp[i][j]->getInterval().hi;
237 }
238 }
239
240 newTuplet[j] = newTuplet[j]->promoteInterval(newI);
241 TRACE(cerr << gGlobal->TABBER << "widening ended : " << newTuplet[j] << endl;)
242 }
243 vtype[i] = new TupletType(newTuplet);
244 }
245 }
246 }
247 // type full term
248 T(sig, gGlobal->NULLTYPEENV);
249 TRACE(cerr << "type success : " << endl << "BYE" << endl;)
250 }
251
annotationStatistics()252 void annotationStatistics()
253 {
254 cerr << gGlobal->TABBER << "COUNT INFERENCE " << gGlobal->gCountInferences << " AT TIME "
255 << clock() / CLOCKS_PER_SEC << 's' << endl;
256 cerr << gGlobal->TABBER << "COUNT ALLOCATION " << gGlobal->gAllocationCount << endl;
257 cerr << gGlobal->TABBER << "COUNT MAXIMAL " << gGlobal->gCountMaximal << endl;
258 }
259
260 /**
261 * Retrieve the type of sig and check it exists. Produces an
262 * error if the signal has no type associated
263 * @param sig the signal we want to know the type
264 * @return the type of the signal
265 */
266
getCertifiedSigType(Tree sig)267 ::Type getCertifiedSigType(Tree sig)
268 {
269 Type ty = getSigType(sig);
270 faustassert(ty);
271 return ty;
272 }
273
274 /***********************************************
275 * Set and get the type property of a signal
276 * (we suppose the signal have been previously
277 * annotated with type information)
278 ***********************************************/
279
280 /**
281 * Set the type annotation of sig
282 * @param sig the signal we want to type
283 * @param t the type of the signal
284 */
setSigType(Tree sig,Type t)285 static void setSigType(Tree sig, Type t)
286 {
287 TRACE(cerr << gGlobal->TABBER << "SET FIX TYPE OF " << *sig << " TO TYPE " << *t << endl;)
288 sig->setType(t);
289 }
290
291 /**
292 * Retrieve the type annotation of sig
293 * @param sig the signal we want to know the type
294 */
getSigType(Tree sig)295 static Type getSigType(Tree sig)
296 {
297 AudioType* ty = (AudioType*)sig->getType();
298 if (ty == 0) {
299 TRACE(cerr << gGlobal->TABBER << "GET FIX TYPE OF " << *sig << " HAS NO TYPE YET" << endl;)
300 } else {
301 TRACE(cerr << gGlobal->TABBER << "GET FIX TYPE OF " << *sig << " IS TYPE " << *ty << endl;)
302 }
303 return ty;
304 }
305
306 /**
307 * dereference a Type to AudioType and promote its type to TupletType
308 * if the AudioType is not a TupletType, then fails
309 * @param t the type to promote
310 * @return the *t as a TupletType
311 */
312
derefRecCert(Type t)313 ::TupletType derefRecCert(Type t)
314 {
315 TupletType* p = isTupletType(t);
316 faustassert(p);
317 return *p;
318 }
319
320 /**************************************************************************
321
322 Type Inference System
323
324 ***************************************************************************/
325
326 /**************************************************************************
327
328 Infered Type property
329
330 ***************************************************************************/
331
332 /**
333 * Shortcut to getOrInferType, retrieve or infere the type of a term according to its surrounding type environment
334 * @param sig the signal to analyze
335 * @param env the type environment
336 * @return the type of sig according to environment env
337 * @see getCertifiedSigType
338 */
T(Tree term,Tree ignoreenv)339 static Type T(Tree term, Tree ignoreenv)
340 {
341 TRACE(cerr << ++gGlobal->TABBER << "ENTER T() " << *term << endl;)
342
343 if (term->isAlreadyVisited()) {
344 Type ty = getSigType(term);
345 TRACE(cerr << --gGlobal->TABBER << "EXIT 1 T() " << *term << " AS TYPE " << *ty << endl);
346 return ty;
347
348 } else {
349 Type ty = infereSigType(term, ignoreenv);
350 setSigType(term, ty);
351 term->setVisited();
352 TRACE(cerr << --gGlobal->TABBER << "EXIT 2 T() " << *term << " AS TYPE " << *ty << endl);
353 return ty;
354 }
355 }
356
CheckPartInterval(Tree s,Type t)357 static void CheckPartInterval(Tree s, Type t)
358 {
359 interval i = t->getInterval();
360 if (!i.valid || (i.lo < 0) || (i.hi >= MAX_SOUNDFILE_PARTS)) {
361 stringstream error;
362 error << "ERROR : out of range soundfile part number (" << i << " instead of interval(0,"
363 << MAX_SOUNDFILE_PARTS - 1 << ")) in expression : " << ppsig(s) << endl;
364 throw faustexception(error.str());
365 }
366 }
367
368 /**
369 * Infere the type of a term according to its surrounding type environment
370 * @param sig the signal to analyse
371 * @param env the type environment
372 * @return the type of sig according to environment env
373 */
374
infereSigType(Tree sig,Tree env)375 static Type infereSigType(Tree sig, Tree env)
376 {
377 int i;
378 double r;
379 Tree sel, s1, s2, s3, ff, id, ls, l, x, y, z, part, u, var, body, type, name, file, sf;
380 Tree label, cur, min, max, step;
381
382 gGlobal->gCountInferences++;
383
384 if (getUserData(sig))
385 return infereXType(sig, env);
386
387 else if (isSigInt(sig, &i)) {
388 Type t = makeSimpleType(kInt, kKonst, kComp, kVect, kNum, interval(i));
389 /*sig->setType(t);*/ return t;
390 }
391
392 else if (isSigReal(sig, &r)) {
393 Type t = makeSimpleType(kReal, kKonst, kComp, kVect, kNum, interval(r));
394 /*sig->setType(t);*/ return t;
395 }
396
397 else if (isSigWaveform(sig)) {
398 return infereWaveformType(sig, env);
399 }
400
401 else if (isSigInput(sig, &i)) { /*sig->setType(TINPUT);*/
402 return gGlobal->TINPUT;
403 }
404
405 else if (isSigOutput(sig, &i, s1))
406 return sampCast(T(s1, env));
407
408 else if (isSigDelay1(sig, s1)) {
409 Type t = T(s1, env);
410 return castInterval(sampCast(t), reunion(t->getInterval(), interval(0, 0)));
411 }
412
413 else if (isSigPrefix(sig, s1, s2)) {
414 Type t1 = T(s1, env);
415 Type t2 = T(s2, env);
416 checkInit(t1);
417 return castInterval(sampCast(t1 | t2), reunion(t1->getInterval(), t2->getInterval()));
418 }
419
420 else if (isSigDelay(sig, s1, s2)) {
421 Type t1 = T(s1, env);
422 Type t2 = T(s2, env);
423 interval i1 = t2->getInterval();
424
425 // cerr << "for sig fix delay : s1 = "
426 // << t1 << ':' << ppsig(s1) << ", s2 = "
427 // << t2 << ':' << ppsig(s2) << endl;
428 if (gGlobal->gCausality) {
429 if (!(i1.valid) || !(i1.isbounded())) {
430 stringstream error;
431 error << "ERROR : can't compute the min and max values of : " << ppsig(s2) << endl
432 << " used in delay expression : " << ppsig(sig) << endl
433 << " (probably a recursive signal)" << endl;
434 throw faustexception(error.str());
435 } else if (i1.lo < 0) {
436 stringstream error;
437 error << "ERROR : possible negative values of : " << ppsig(s2) << endl
438 << " used in delay expression : " << ppsig(sig) << endl
439 << " " << i1 << endl;
440 throw faustexception(error.str());
441 }
442 }
443
444 return castInterval(sampCast(t1), reunion(t1->getInterval(), interval(0, 0)));
445 }
446
447 else if (isSigBinOp(sig, &i, s1, s2)) {
448 // Type t = T(s1,env)|T(s2,env);
449 Type t1 = T(s1, env);
450 Type t2 = T(s2, env);
451 Type t3 = castInterval(t1 | t2, arithmetic(i, t1->getInterval(), t2->getInterval()));
452 // cerr <<"type rule for : " << ppsig(sig) << " -> " << *t3 << endl;
453
454 if (i == kDiv) {
455 return floatCast(t3); // division always result in a float even with int arguments
456 } else if ((i >= kGT) && (i <= kNE)) {
457 return boolCast(t3); // comparison always result in a boolean int
458 } else {
459 return t3; // otherwise most general of t1 and t2
460 }
461 }
462
463 else if (isSigIntCast(sig, s1))
464 return intCast(T(s1, env));
465
466 else if (isSigFloatCast(sig, s1))
467 return floatCast(T(s1, env));
468
469 else if (isSigFFun(sig, ff, ls))
470 return infereFFType(ff, ls, env);
471
472 else if (isSigFConst(sig, type, name, file))
473 return infereFConstType(type);
474
475 else if (isSigFVar(sig, type, name, file))
476 return infereFVarType(type);
477
478 else if (isSigButton(sig)) { /*sig->setType(TGUI01);*/
479 return gGlobal->TGUI01;
480 }
481
482 else if (isSigCheckbox(sig)) { /*sig->setType(TGUI01);*/
483 return gGlobal->TGUI01;
484 }
485
486 else if (isSigVSlider(sig, label, cur, min, max, step)) {
487 Type t1 = T(cur, env);
488 Type t2 = T(min, env);
489 Type t3 = T(max, env);
490 Type t4 = T(step, env);
491 return castInterval(gGlobal->TGUI, interval(tree2float(min), tree2float(max)));
492 }
493
494 else if (isSigHSlider(sig, label, cur, min, max, step)) {
495 Type t1 = T(cur, env);
496 Type t2 = T(min, env);
497 Type t3 = T(max, env);
498 Type t4 = T(step, env);
499 return castInterval(gGlobal->TGUI, interval(tree2float(min), tree2float(max)));
500 }
501
502 else if (isSigNumEntry(sig, label, cur, min, max, step)) {
503 Type t1 = T(cur, env);
504 Type t2 = T(min, env);
505 Type t3 = T(max, env);
506 Type t4 = T(step, env);
507 return castInterval(gGlobal->TGUI, interval(tree2float(min), tree2float(max)));
508 }
509
510 else if (isSigHBargraph(sig, l, x, y, s1)) {
511 Type t1 = T(x, env);
512 Type t2 = T(y, env);
513 return T(s1, env)->promoteVariability(kBlock);
514 }
515
516 else if (isSigVBargraph(sig, l, x, y, s1)) {
517 Type t1 = T(x, env);
518 Type t2 = T(y, env);
519 return T(s1, env)->promoteVariability(kBlock);
520 }
521
522 else if (isSigSoundfile(sig, l)) {
523 return makeSimpleType(kInt, kBlock, kExec, kVect, kNum, interval(0, 0x7FFFFFFF));
524 }
525
526 else if (isSigSoundfileLength(sig, sf, part)) {
527 Type t1 = T(sf, env);
528 Type t2 = T(part, env);
529 CheckPartInterval(sig, t2);
530 int c = std::max(int(kBlock), t2->variability());
531 return makeSimpleType(kInt, c, kExec, kVect, kNum, interval(0, 0x7FFFFFFF)); // A REVOIR (YO)
532 }
533
534 else if (isSigSoundfileRate(sig, sf, part)) {
535 Type t1 = T(sf, env);
536 Type t2 = T(part, env);
537 CheckPartInterval(sig, t2);
538 int c = std::max(int(kBlock), t2->variability());
539 return makeSimpleType(kInt, c, kExec, kVect, kNum, interval(0, 0x7FFFFFFF));
540 }
541
542 else if (isSigSoundfileBuffer(sig, sf, x, part, z)) {
543 T(sf, env);
544 T(x, env);
545 Type tp = T(part, env);
546 T(z, env);
547
548 CheckPartInterval(sig, tp);
549 return makeSimpleType(kReal, kSamp, kExec, kVect, kNum, interval());
550 }
551
552 else if (isSigAttach(sig, s1, s2)) {
553 T(s2, env);
554 return T(s1, env);
555 }
556
557 else if (isSigEnable(sig, s1, s2)) {
558 T(s2, env);
559 return T(s1, env);
560 }
561
562 else if (isSigControl(sig, s1, s2)) {
563 T(s2, env);
564 return T(s1, env);
565 }
566
567 else if (isRec(sig, var, body))
568 return infereRecType(sig, body, env);
569
570 else if (isProj(sig, &i, s1))
571 return infereProjType(T(s1, env), i, kScal);
572
573 else if (isSigTable(sig, id, s1, s2)) {
574 checkInt(checkInit(T(s1, env)));
575 return makeTableType(checkInit(T(s2, env)));
576 }
577
578 else if (isSigWRTbl(sig, id, s1, s2, s3))
579 return infereWriteTableType(T(s1, env), T(s2, env), T(s3, env));
580
581 else if (isSigRDTbl(sig, s1, s2))
582 return infereReadTableType(T(s1, env), T(s2, env));
583
584 else if (isSigGen(sig, s1))
585 return T(s1, gGlobal->NULLTYPEENV);
586
587 else if (isSigDocConstantTbl(sig, x, y))
588 return infereDocConstantTblType(T(x, env), T(y, env));
589 else if (isSigDocWriteTbl(sig, x, y, z, u))
590 return infereDocWriteTblType(T(x, env), T(y, env), T(z, env), T(u, env));
591 else if (isSigDocAccessTbl(sig, x, y))
592 return infereDocAccessTblType(T(x, env), T(y, env));
593
594 else if (isSigSelect2(sig, sel, s1, s2)) {
595 SimpleType *st1, *st2, *stsel;
596
597 st1 = isSimpleType(T(s1, env));
598 st2 = isSimpleType(T(s2, env));
599 stsel = isSimpleType(T(sel, env));
600
601 return makeSimpleType(st1->nature() | st2->nature(),
602 st1->variability() | st2->variability() | stsel->variability(),
603 st1->computability() | st2->computability() | stsel->computability(),
604 st1->vectorability() | st2->vectorability() | stsel->vectorability(),
605 st1->boolean() | st2->boolean(), reunion(st1->getInterval(), st2->getInterval()));
606 }
607
608 else if (isNil(sig)) {
609 Type t = new TupletType(); /*sig->setType(t);*/
610 return t;
611 }
612
613 else if (isList(sig)) {
614 return T(hd(sig), env) * T(tl(sig), env);
615 }
616
617 else if (isSigAssertBounds(sig, min, max, cur)){
618 Type t1 = T(min, env);
619 Type t2 = T(max, env);
620 Type t3 = T(cur, env);
621 interval i3 = t3->getInterval();
622 interval iEnd;
623 constSig2double(min);
624 if (i3.valid) {
625 iEnd = interval(std::max(i3.lo, constSig2double(min)), std::min(i3.hi, constSig2double(max)));
626 } else {
627 iEnd = interval(constSig2double(min), constSig2double(max));
628 }
629 return t3->promoteInterval(iEnd);
630 }
631
632 else if (isSigLowest(sig, s1)) {
633 interval i1 = T(s1, env)->getInterval();
634 return makeSimpleType(kReal, kKonst, kComp, kVect, kNum, interval(i1.lo));
635 // change this part ^^^^^ once there are interval bounds depending on signal type
636 }
637
638 else if (isSigHighest(sig, s1)) {
639 interval i1 = T(s1, env)->getInterval();
640 return makeSimpleType(kReal, kKonst, kComp, kVect, kNum, interval(i1.hi));
641 // change this part ^^^^^ once there are interval bounds depending on signal type
642 }
643
644 // unrecognized signal here
645 throw faustexception("ERROR inferring signal type : unrecognized signal\n");
646 return 0;
647 }
648
649 /**
650 * Infere the type of a projection (selection) of a tuplet element
651 */
infereProjType(Type t,int i,int vec)652 static Type infereProjType(Type t, int i, int vec)
653 {
654 TupletType* tt = isTupletType(t);
655 if (tt == 0) {
656 stringstream error;
657 error << "ERROR inferring projection type, not a tuplet type : " << t << endl;
658 throw faustexception(error.str());
659 }
660 // return (*tt)[i] ->promoteVariability(t->variability())
661 // ->promoteComputability(t->computability());
662 Type temp = (*tt)[i]
663 ->promoteVariability(t->variability())
664 ->promoteComputability(t->computability())
665 ->promoteVectorability(vec /*t->vectorability()*/);
666 //->promoteBooleanity(t->boolean());
667
668 if (vec == kVect) temp = vecCast(temp);
669 // cerr << "infereProjType(" << t << ',' << i << ',' << vec << ")" << " -> " << temp << endl;
670
671 return temp;
672 }
673
674 /**
675 * Infere the type of the result of writing into a table
676 */
infereWriteTableType(Type tbl,Type wi,Type wd)677 static Type infereWriteTableType(Type tbl, Type wi, Type wd)
678 {
679 TableType* tt = isTableType(tbl);
680 if (tt == 0) {
681 stringstream error;
682 error << "ERROR inferring write table type, wrong table type : " << tbl << endl;
683 throw faustexception(error.str());
684 }
685 SimpleType* st = isSimpleType(wi);
686 if (st == 0 || st->nature() > kInt) {
687 stringstream error;
688 error << "ERROR inferring write table type, wrong write index type : " << wi << endl;
689 throw faustexception(error.str());
690 }
691
692 int n = tt->nature();
693 int v = wi->variability() | wd->variability();
694 int c = wi->computability() | wd->computability();
695 int vec = wi->vectorability() | wd->vectorability();
696
697 return makeTableType(tt->content(), n, v, c, vec);
698 }
699
700 /**
701 * Infere the type of the result of reading a table
702 */
infereReadTableType(Type tbl,Type ri)703 static Type infereReadTableType(Type tbl, Type ri)
704 {
705 TableType* tt = isTableType(tbl);
706 if (tt == 0) {
707 stringstream error;
708 error << "ERROR inferring read table type, wrong table type : " << tbl << endl;
709 throw faustexception(error.str());
710 }
711 SimpleType* st = isSimpleType(ri);
712 if (st == 0 || st->nature() > kInt) {
713 stringstream error;
714 error << "ERROR inferring read table type, wrong write index type : " << ri << endl;
715 throw faustexception(error.str());
716 }
717 Type temp = makeSimpleType(tbl->nature(), ri->variability(), kInit | ri->computability(), ri->vectorability(), tbl->boolean(), tbl->getInterval());
718
719 return temp;
720 }
721
infereDocConstantTblType(Type size,Type init)722 static Type infereDocConstantTblType(Type size, Type init)
723 {
724 checkKonst(checkInt(checkInit(size)));
725
726 return init;
727 }
728
infereDocWriteTblType(Type size,Type init,Type widx,Type wsig)729 static Type infereDocWriteTblType(Type size, Type init, Type widx, Type wsig)
730 {
731 checkKonst(checkInt(checkInit(size)));
732
733 Type temp = init->promoteVariability(kSamp) // difficult to tell, therefore kSamp to be safe
734 ->promoteComputability(widx->computability() | wsig->computability())
735 ->promoteVectorability(kScal) // difficult to tell, therefore kScal to be safe
736 ->promoteNature(wsig->nature()) // nature of the initial and written signal
737 ->promoteBoolean(wsig->boolean()); // booleanity of the initial and written signal
738 return temp;
739 }
740
infereDocAccessTblType(Type tbl,Type ridx)741 static Type infereDocAccessTblType(Type tbl, Type ridx)
742 {
743 Type temp = tbl->promoteVariability(ridx->variability())
744 ->promoteComputability(ridx->computability())
745 ->promoteVectorability(ridx->vectorability());
746 return temp;
747 }
748
749 /**
750 * Compute an initial type solution for a recursive block
751 * E1,E2,...En -> TREC,TREC,...TREC
752 */
initialRecType(Tree t)753 static TupletType* initialRecType(Tree t)
754 {
755 faustassert(isList(t));
756 return new TupletType(vector<Type>(len(t), gGlobal->TREC));
757 }
758
759 /**
760 * Compute a maximal type solution for a recursive block
761 * useful for widening approx
762 * E1,E2,...En -> TRECMAX,TRECMAX,...TRECMAX
763 */
maximalRecType(Tree t)764 static TupletType* maximalRecType(Tree t)
765 {
766 faustassert(isList(t));
767 return new TupletType(vector<Type>(len(t), gGlobal->TRECMAX));
768 }
769
770 /**
771 * Infere the type of a recursive block by trying solutions of
772 * increasing generality
773 */
infereRecType(Tree sig,Tree body,Tree env)774 static Type infereRecType(Tree sig, Tree body, Tree env)
775 {
776 faustassert(false); // we should not come here
777 return 0;
778 }
779
780 /**
781 * Infere the type of a foreign function call
782 */
infereFFType(Tree ff,Tree ls,Tree env)783 static Type infereFFType(Tree ff, Tree ls, Tree env)
784 {
785 // An external primitive can't be computed earlier than at initialization.
786 // Its variability depends on the variability of its arguments unless it has no arguments,
787 // in which case it is considered as rand(), i.e. the result varies at each call.
788
789 if (ffarity(ff) == 0) {
790 // case of functions like rand()
791 return makeSimpleType(ffrestype(ff), kSamp, kInit, kVect, kNum, interval());
792 } else {
793 // otherwise variability and computability depends
794 // arguments (OR of all arg types)
795 Type t = makeSimpleType(kInt, kKonst, kInit, kVect, kNum, interval());
796 while (isList(ls)) {
797 t = t | T(hd(ls), env);
798 ls = tl(ls);
799 }
800 // but the result type is defined by the function
801 return makeSimpleType(ffrestype(ff), t->variability(), t->computability(), t->vectorability(), t->boolean(),
802 interval());
803 }
804 }
805
806 /**
807 * Infere the type of a foreign constant
808 */
infereFConstType(Tree type)809 static Type infereFConstType(Tree type)
810 {
811 // An external constant cannot be calculated at the earliest possible time the initialization.
812 // It is constant, in which case it is considered a rand() i.e. the result varies at each call.
813 return makeSimpleType(tree2int(type), kKonst, kInit, kVect, kNum, interval());
814 }
815
816 /**
817 * Infere the type of a foreign variable
818 */
infereFVarType(Tree type)819 static Type infereFVarType(Tree type)
820 {
821 // An external variable cannot be calculated as soon as it is executed.
822 // It varies by blocks like the user interface elements.
823 return makeSimpleType(tree2int(type), kBlock, kExec, kVect, kNum, interval());
824 }
825
826 /**
827 * Infere the type of a waveform:
828 * - the nature is int if all values are int, otherwise it is float
829 * - the variability is by samples
830 * - the waveform is known at compile time
831 * - it can be vectorized because all values are known
832 * - knum ???
833 * - the interval is min and max of values
834 */
infereWaveformType(Tree wfsig,Tree env)835 static Type infereWaveformType(Tree wfsig, Tree env)
836 {
837 bool iflag = true;
838 int n = wfsig->arity();
839 double lo, hi;
840
841 if (n == 0) {
842 throw faustexception("ERROR empty waveform\n");
843 }
844
845 lo = hi = tree2float(wfsig->branch(0));
846 iflag = isInt(wfsig->branch(0)->node());
847 T(wfsig->branch(0), env);
848
849 for (int i = 1; i < n; i++) {
850 Tree v = wfsig->branch(i);
851 T(v, env);
852 // compute range
853 double f = tree2float(v);
854 if (f < lo) {
855 lo = f;
856 } else if (f > hi) {
857 hi = f;
858 }
859 iflag &= isInt(v->node());
860 }
861
862 return makeSimpleType((iflag) ? kInt : kReal, kSamp, kComp, kScal, kNum, interval(lo, hi));
863 }
864
865 /**
866 * Infere the type of an extended (primitive) block
867 */
infereXType(Tree sig,Tree env)868 static Type infereXType(Tree sig, Tree env)
869 {
870 // cerr << "infereXType :" << endl;
871 // cerr << "infereXType of " << *sig << endl;
872 xtended* p = (xtended*)getUserData(sig);
873 vector<Type> vt;
874
875 for (int i = 0; i < sig->arity(); i++) vt.push_back(T(sig->branch(i), env));
876 return p->infereSigType(vt);
877 }
878
879 /**
880 * Compute the resulting interval of an arithmetic operation
881 * @param op code of the operation
882 * @param s1 interval of the left operand
883 * @param s2 interval of the right operand
884 * @return the resulting interval
885 */
arithmetic(int opcode,const interval & x,const interval & y)886 static interval arithmetic(int opcode, const interval& x, const interval& y)
887 {
888 switch (opcode) {
889 case kAdd:
890 return x + y;
891 case kSub:
892 return x - y;
893 case kMul:
894 return x * y;
895 case kDiv:
896 return x / y;
897 case kRem:
898 return x % y;
899 case kLsh:
900 return x << y;
901 case kARsh:
902 return x >> y;
903 case kGT:
904 return x > y;
905 case kLT:
906 return x < y;
907 case kGE:
908 return x >= y;
909 case kLE:
910 return x <= y;
911 case kEQ:
912 return x == y;
913 case kNE:
914 return x != y;
915 case kAND:
916 return x & y;
917 case kOR:
918 return x | y;
919 case kXOR:
920 return x ^ y;
921 default:
922 stringstream error;
923 error << "ERROR : unrecognized opcode : " << opcode << endl;
924 throw faustexception(error.str());
925 }
926
927 return interval();
928 }
929
constSig2double(Tree sig)930 double constSig2double(Tree sig)
931 {
932 Type ty = getSigType(sig);
933 if (ty->variability() != kKonst) {
934 throw faustexception("ERROR : constSig2double, the parameter must be a constant value"
935 " known at compile time\n");
936 }
937 interval bds = ty->getInterval();
938 if (bds.lo != bds.hi) {
939 throw faustexception(
940 "ERROR : constSig2double, constant value with non-singleton interval, don't know what"
941 " to do, please report");
942 }
943 return bds.lo;
944 }
945