1:
2: // Copyright (c) 1999-2010 by Digital Mars
3: // All Rights Reserved
4: // written by Walter Bright
5: // http://www.digitalmars.com
6: // License for redistribution is by either the Artistic License
7: // in artistic.txt, or the GNU General Public License in gnu.txt.
8: // See the included readme.txt for details.
9:
10: #include <stdio.h>
11: #include <string.h>
12: static char __file__[] = __FILE__; /* for tassert.h */
13: #include "tassert.h"
14:
15: #include "rmem.h"
16:
17: #include "stringtable.h"
18:
19: #include "expression.h"
20: #include "statement.h"
21: #include "mtype.h"
22: #include "declaration.h"
23: #include "scope.h"
24: #include "id.h"
25: #include "module.h"
26: #include "init.h"
27:
28: extern int binary(const char *p , const char **tab, int high);
29:
30: /**************************************
31: * Hash table of array op functions already generated or known about.
32: */
33:
34: StringTable arrayfuncs;
35:
36: /**********************************************
37: * Check that there are no uses of arrays without [].
38: */
39: bool isArrayOpValid(Expression *e)
40: {
41: if (e->op == TOKslice)
42: return true;
43: Type *tb = e->type->toBasetype();
44:
45: if ( (tb->ty == Tarray) || (tb->ty == Tsarray) )
46: {
47: switch (e->op)
48: {
49: case TOKadd:
50: case TOKmin:
51: case TOKmul:
52: case TOKdiv:
53: case TOKmod:
54: case TOKxor:
55: case TOKand:
56: case TOKor:
57: case TOKassign:
58: case TOKaddass:
59: case TOKminass:
60: case TOKmulass:
61: case TOKdivass:
62: case TOKmodass:
63: case TOKxorass:
64: case TOKandass:
65: case TOKorass:
66: #if DMDV2
67: case TOKpow:
68: case TOKpowass:
69: #endif
70: return isArrayOpValid(((BinExp *)e)->e1) && isArrayOpValid(((BinExp *)e)->e2);
71:
72: case TOKcall:
73: return false; // TODO: Decide if [] is required after arrayop calls.
74:
75: case TOKneg:
76: case TOKtilde:
77: return isArrayOpValid(((UnaExp *)e)->e1);
78:
79: default:
80: return false;
81: }
82: }
83: return true;
84: }
85:
86: /***********************************
87: * Construct the array operation expression.
88: */
89:
90: Expression *BinExp::arrayOp(Scope *sc)
91: {
92: //printf("BinExp::arrayOp() %s\n", toChars());
93:
94: Type *tb = type->toBasetype();
95: assert(tb->ty == Tarray || tb->ty == Tsarray);
96: if (tb->nextOf()->toBasetype()->ty == Tvoid)
97: {
98: error("Cannot perform array operations on void[] arrays");
99: return new ErrorExp();
100: }
101:
102: if (!isArrayOpValid(e2))
103: {
104: e2->error("invalid array operation %s (did you forget a [] ?)", toChars());
105: return new ErrorExp();
106: }
107:
108: Expressions *arguments = new Expressions();
109:
110: /* The expression to generate an array operation for is mangled
111: * into a name to use as the array operation function name.
112: * Mangle in the operands and operators in RPN order, and type.
113: */
114: OutBuffer buf;
115: buf.writestring("_array");
116: buildArrayIdent(&buf, arguments);
117: buf.writeByte('_');
118:
119: /* Append deco of array element type
120: */
121: #if DMDV2
122: buf.writestring(type->toBasetype()->nextOf()->toBasetype()->mutableOf()->deco);
123: #else
124: buf.writestring(type->toBasetype()->nextOf()->toBasetype()->deco);
125: #endif
126:
127: size_t namelen = buf.offset;
128: buf.writeByte(0);
129: char *name = (char *)buf.extractData();
130:
131: /* Look up name in hash table
132: */
133: StringValue *sv = arrayfuncs.update(name, namelen);
134: FuncDeclaration *fd = (FuncDeclaration *)sv->ptrvalue;
135: if (!fd)
136: {
137: /* Some of the array op functions are written as library functions,
138: * presumably to optimize them with special CPU vector instructions.
139: * List those library functions here, in alpha order.
140: */
141: static const char *libArrayopFuncs[] =
142: {
143: "_arrayExpSliceAddass_a",
144: "_arrayExpSliceAddass_d", // T[]+=T
145: "_arrayExpSliceAddass_f", // T[]+=T
146: "_arrayExpSliceAddass_g",
147: "_arrayExpSliceAddass_h",
148: "_arrayExpSliceAddass_i",
149: "_arrayExpSliceAddass_k",
150: "_arrayExpSliceAddass_s",
151: "_arrayExpSliceAddass_t",
152: "_arrayExpSliceAddass_u",
153: "_arrayExpSliceAddass_w",
154:
155: "_arrayExpSliceDivass_d", // T[]/=T
156: "_arrayExpSliceDivass_f", // T[]/=T
157:
158: "_arrayExpSliceMinSliceAssign_a",
159: "_arrayExpSliceMinSliceAssign_d", // T[]=T-T[]
160: "_arrayExpSliceMinSliceAssign_f", // T[]=T-T[]
161: "_arrayExpSliceMinSliceAssign_g",
162: "_arrayExpSliceMinSliceAssign_h",
163: "_arrayExpSliceMinSliceAssign_i",
164: "_arrayExpSliceMinSliceAssign_k",
165: "_arrayExpSliceMinSliceAssign_s",
166: "_arrayExpSliceMinSliceAssign_t",
167: "_arrayExpSliceMinSliceAssign_u",
168: "_arrayExpSliceMinSliceAssign_w",
169:
170: "_arrayExpSliceMinass_a",
171: "_arrayExpSliceMinass_d", // T[]-=T
172: "_arrayExpSliceMinass_f", // T[]-=T
173: "_arrayExpSliceMinass_g",
174: "_arrayExpSliceMinass_h",
175: "_arrayExpSliceMinass_i",
176: "_arrayExpSliceMinass_k",
177: "_arrayExpSliceMinass_s",
178: "_arrayExpSliceMinass_t",
179: "_arrayExpSliceMinass_u",
180: "_arrayExpSliceMinass_w",
181:
182: "_arrayExpSliceMulass_d", // T[]*=T
183: "_arrayExpSliceMulass_f", // T[]*=T
184: "_arrayExpSliceMulass_i",
185: "_arrayExpSliceMulass_k",
186: "_arrayExpSliceMulass_s",
187: "_arrayExpSliceMulass_t",
188: "_arrayExpSliceMulass_u",
189: "_arrayExpSliceMulass_w",
190:
191: "_arraySliceExpAddSliceAssign_a",
192: "_arraySliceExpAddSliceAssign_d", // T[]=T[]+T
193: "_arraySliceExpAddSliceAssign_f", // T[]=T[]+T
194: "_arraySliceExpAddSliceAssign_g",
195: "_arraySliceExpAddSliceAssign_h",
196: "_arraySliceExpAddSliceAssign_i",
197: "_arraySliceExpAddSliceAssign_k",
198: "_arraySliceExpAddSliceAssign_s",
199: "_arraySliceExpAddSliceAssign_t",
200: "_arraySliceExpAddSliceAssign_u",
201: "_arraySliceExpAddSliceAssign_w",
202:
203: "_arraySliceExpDivSliceAssign_d", // T[]=T[]/T
204: "_arraySliceExpDivSliceAssign_f", // T[]=T[]/T
205:
206: "_arraySliceExpMinSliceAssign_a",
207: "_arraySliceExpMinSliceAssign_d", // T[]=T[]-T
208: "_arraySliceExpMinSliceAssign_f", // T[]=T[]-T
209: "_arraySliceExpMinSliceAssign_g",
210: "_arraySliceExpMinSliceAssign_h",
211: "_arraySliceExpMinSliceAssign_i",
212: "_arraySliceExpMinSliceAssign_k",
213: "_arraySliceExpMinSliceAssign_s",
214: "_arraySliceExpMinSliceAssign_t",
215: "_arraySliceExpMinSliceAssign_u",
216: "_arraySliceExpMinSliceAssign_w",
217:
218: "_arraySliceExpMulSliceAddass_d", // T[] += T[]*T
219: "_arraySliceExpMulSliceAddass_f",
220: "_arraySliceExpMulSliceAddass_r",
221:
222: "_arraySliceExpMulSliceAssign_d", // T[]=T[]*T
223: "_arraySliceExpMulSliceAssign_f", // T[]=T[]*T
224: "_arraySliceExpMulSliceAssign_i",
225: "_arraySliceExpMulSliceAssign_k",
226: "_arraySliceExpMulSliceAssign_s",
227: "_arraySliceExpMulSliceAssign_t",
228: "_arraySliceExpMulSliceAssign_u",
229: "_arraySliceExpMulSliceAssign_w",
230:
231: "_arraySliceExpMulSliceMinass_d", // T[] -= T[]*T
232: "_arraySliceExpMulSliceMinass_f",
233: "_arraySliceExpMulSliceMinass_r",
234:
235: "_arraySliceSliceAddSliceAssign_a",
236: "_arraySliceSliceAddSliceAssign_d", // T[]=T[]+T[]
237: "_arraySliceSliceAddSliceAssign_f", // T[]=T[]+T[]
238: "_arraySliceSliceAddSliceAssign_g",
239: "_arraySliceSliceAddSliceAssign_h",
240: "_arraySliceSliceAddSliceAssign_i",
241: "_arraySliceSliceAddSliceAssign_k",
242: "_arraySliceSliceAddSliceAssign_r", // T[]=T[]+T[]
243: "_arraySliceSliceAddSliceAssign_s",
244: "_arraySliceSliceAddSliceAssign_t",
245: "_arraySliceSliceAddSliceAssign_u",
246: "_arraySliceSliceAddSliceAssign_w",
247:
248: "_arraySliceSliceAddass_a",
249: "_arraySliceSliceAddass_d", // T[]+=T[]
250: "_arraySliceSliceAddass_f", // T[]+=T[]
251: "_arraySliceSliceAddass_g",
252: "_arraySliceSliceAddass_h",
253: "_arraySliceSliceAddass_i",
254: "_arraySliceSliceAddass_k",
255: "_arraySliceSliceAddass_s",
256: "_arraySliceSliceAddass_t",
257: "_arraySliceSliceAddass_u",
258: "_arraySliceSliceAddass_w",
259:
260: "_arraySliceSliceMinSliceAssign_a",
261: "_arraySliceSliceMinSliceAssign_d", // T[]=T[]-T[]
262: "_arraySliceSliceMinSliceAssign_f", // T[]=T[]-T[]
263: "_arraySliceSliceMinSliceAssign_g",
264: "_arraySliceSliceMinSliceAssign_h",
265: "_arraySliceSliceMinSliceAssign_i",
266: "_arraySliceSliceMinSliceAssign_k",
267: "_arraySliceSliceMinSliceAssign_r", // T[]=T[]-T[]
268: "_arraySliceSliceMinSliceAssign_s",
269: "_arraySliceSliceMinSliceAssign_t",
270: "_arraySliceSliceMinSliceAssign_u",
271: "_arraySliceSliceMinSliceAssign_w",
272:
273: "_arraySliceSliceMinass_a",
274: "_arraySliceSliceMinass_d", // T[]-=T[]
275: "_arraySliceSliceMinass_f", // T[]-=T[]
276: "_arraySliceSliceMinass_g",
277: "_arraySliceSliceMinass_h",
278: "_arraySliceSliceMinass_i",
279: "_arraySliceSliceMinass_k",
280: "_arraySliceSliceMinass_s",
281: "_arraySliceSliceMinass_t",
282: "_arraySliceSliceMinass_u",
283: "_arraySliceSliceMinass_w",
284:
285: "_arraySliceSliceMulSliceAssign_d", // T[]=T[]*T[]
286: "_arraySliceSliceMulSliceAssign_f", // T[]=T[]*T[]
287: "_arraySliceSliceMulSliceAssign_i",
288: "_arraySliceSliceMulSliceAssign_k",
289: "_arraySliceSliceMulSliceAssign_s",
290: "_arraySliceSliceMulSliceAssign_t",
291: "_arraySliceSliceMulSliceAssign_u",
292: "_arraySliceSliceMulSliceAssign_w",
293:
294: "_arraySliceSliceMulass_d", // T[]*=T[]
295: "_arraySliceSliceMulass_f", // T[]*=T[]
296: "_arraySliceSliceMulass_i",
297: "_arraySliceSliceMulass_k",
298: "_arraySliceSliceMulass_s",
299: "_arraySliceSliceMulass_t",
300: "_arraySliceSliceMulass_u",
301: "_arraySliceSliceMulass_w",
302: };
303:
304: int i = binary(name, libArrayopFuncs, sizeof(libArrayopFuncs) / sizeof(char *));
305: if (i == -1)
306: {
307: #ifdef DEBUG // Make sure our array is alphabetized
308: for (i = 0; i < sizeof(libArrayopFuncs) / sizeof(char *); i++)
309: {
310: if (strcmp(name, libArrayopFuncs[i]) == 0)
311: assert(0);
312: }
313: #endif
314: /* Not in library, so generate it.
315: * Construct the function body:
316: * foreach (i; 0 .. p.length) for (size_t i = 0; i < p.length; i++)
317: * loopbody;
318: * return p;
319: */
320:
321: Parameters *fparams = new Parameters();
322: Expression *loopbody = buildArrayLoop(fparams);
323: Parameter *p = fparams->tdata()[0 /*fparams->dim - 1*/];
324: #if DMDV1
325: // for (size_t i = 0; i < p.length; i++)
326: Initializer *init = new ExpInitializer(0, new IntegerExp(0, 0, Type::tsize_t));
327: Dsymbol *d = new VarDeclaration(0, Type::tsize_t, Id::p, init);
328: Statement *s1 = new ForStatement(0,
329: new DeclarationStatement(0, d),
330: new CmpExp(TOKlt, 0, new IdentifierExp(0, Id::p), new ArrayLengthExp(0, new IdentifierExp(0, p->ident))),
331: new PostExp(TOKplusplus, 0, new IdentifierExp(0, Id::p)),
332: new ExpStatement(0, loopbody));
333: #else
334: // foreach (i; 0 .. p.length)
335: Statement *s1 = new ForeachRangeStatement(0, TOKforeach,
warning C6211: Leaking memory 's1' due to an exception. Consider using a local catch block to clean up memory: Lines: 94, 95, 96, 102, 108, 114, 115, 116, 117, 122, 127, 128, 129, 133, 134, 135, 141, 304, 305, 321, 322, 323, 335, 341
336: new Parameter(0, NULL, Id::p, NULL),
337: new IntegerExp(0, 0, Type::tint32),
338: new ArrayLengthExp(0, new IdentifierExp(0, p->ident)),
339: new ExpStatement(0, loopbody));
340: #endif
341: Statement *s2 = new ReturnStatement(0, new IdentifierExp(0, p->ident));
342: //printf("s2: %s\n", s2->toChars());
343: Statement *fbody = new CompoundStatement(0, s1, s2);
warning C6211: Leaking memory 'fbody' due to an exception. Consider using a local catch block to clean up memory: Lines: 94, 95, 96, 102, 108, 114, 115, 116, 117, 122, 127, 128, 129, 133, 134, 135, 141, 304, 305, 321, 322, 323, 335, 341, 343, 347
344:
345: /* Construct the function
346: */
347: TypeFunction *ftype = new TypeFunction(fparams, type, 0, LINKc);
348: //printf("ftype: %s\n", ftype->toChars());
349: fd = new FuncDeclaration(loc, 0, Lexer::idPool(name), STCundefined, ftype);
350: fd->fbody = fbody;
351: fd->protection = PROTpublic;
352: fd->linkage = LINKc;
353: fd->isArrayOp = 1;
354:
355: sc->module->importedFrom->members->push(fd);
356:
357: sc = sc->push();
358: sc->parent = sc->module->importedFrom;
359: sc->stc = 0;
360: sc->linkage = LINKc;
361: fd->semantic(sc);
362: fd->semantic2(sc);
363: fd->semantic3(sc);
364: sc->pop();
365: }
366: else
367: { /* In library, refer to it.
368: */
369: fd = FuncDeclaration::genCfunc(type, name);
370: }
371: sv->ptrvalue = fd; // cache symbol in hash table
372: }
373:
374: /* Call the function fd(arguments)
375: */
376: Expression *ec = new VarExp(0, fd);
377: Expression *e = new CallExp(loc, ec, arguments);
378: e->type = type;
379: return e;
380: }
381:
382: /******************************************
383: * Construct the identifier for the array operation function,
384: * and build the argument list to pass to it.
385: */
386:
387: void Expression::buildArrayIdent(OutBuffer *buf, Expressions *arguments)
388: {
389: buf->writestring("Exp");
390: arguments->shift(this);
391: }
392:
393: void CastExp::buildArrayIdent(OutBuffer *buf, Expressions *arguments)
394: {
395: Type *tb = type->toBasetype();
396: if (tb->ty == Tarray || tb->ty == Tsarray)
397: {
398: e1->buildArrayIdent(buf, arguments);
399: }
400: else
401: Expression::buildArrayIdent(buf, arguments);
402: }
403:
404: void SliceExp::buildArrayIdent(OutBuffer *buf, Expressions *arguments)
405: {
406: buf->writestring("Slice");
407: arguments->shift(this);
408: }
409:
410: void AssignExp::buildArrayIdent(OutBuffer *buf, Expressions *arguments)
411: {
412: /* Evaluate assign expressions right to left
413: */
414: e2->buildArrayIdent(buf, arguments);
415: e1->buildArrayIdent(buf, arguments);
416: buf->writestring("Assign");
417: }
418:
419: #define X(Str) \
420: void Str##AssignExp::buildArrayIdent(OutBuffer *buf, Expressions *arguments) \
421: { \
422: /* Evaluate assign expressions right to left \
423: */ \
424: e2->buildArrayIdent(buf, arguments); \
425: e1->buildArrayIdent(buf, arguments); \
426: buf->writestring(#Str); \
427: buf->writestring("ass"); \
428: }
429:
430: X(Add)
431: X(Min)
432: X(Mul)
433: X(Div)
434: X(Mod)
435: X(Xor)
436: X(And)
437: X(Or)
438:
439: #undef X
440:
441: void NegExp::buildArrayIdent(OutBuffer *buf, Expressions *arguments)
442: {
443: e1->buildArrayIdent(buf, arguments);
444: buf->writestring("Neg");
445: }
446:
447: void ComExp::buildArrayIdent(OutBuffer *buf, Expressions *arguments)
448: {
449: e1->buildArrayIdent(buf, arguments);
450: buf->writestring("Com");
451: }
452:
453: #define X(Str) \
454: void Str##Exp::buildArrayIdent(OutBuffer *buf, Expressions *arguments) \
455: { \
456: /* Evaluate assign expressions left to right \
457: */ \
458: e1->buildArrayIdent(buf, arguments); \
459: e2->buildArrayIdent(buf, arguments); \
460: buf->writestring(#Str); \
461: }
462:
463: X(Add)
464: X(Min)
465: X(Mul)
466: X(Div)
467: X(Mod)
468: X(Xor)
469: X(And)
470: X(Or)
471:
472: #undef X
473:
474: /******************************************
475: * Construct the inner loop for the array operation function,
476: * and build the parameter list.
477: */
478:
479: Expression *Expression::buildArrayLoop(Parameters *fparams)
480: {
481: Identifier *id = Identifier::generateId("c", fparams->dim);
482: Parameter *param = new Parameter(0, type, id, NULL);
483: fparams->shift(param);
484: Expression *e = new IdentifierExp(0, id);
485: return e;
486: }
487:
488: Expression *CastExp::buildArrayLoop(Parameters *fparams)
489: {
490: Type *tb = type->toBasetype();
491: if (tb->ty == Tarray || tb->ty == Tsarray)
492: {
493: return e1->buildArrayLoop(fparams);
494: }
495: else
496: return Expression::buildArrayLoop(fparams);
497: }
498:
499: Expression *SliceExp::buildArrayLoop(Parameters *fparams)
500: {
501: Identifier *id = Identifier::generateId("p", fparams->dim);
502: Parameter *param = new Parameter(STCconst, type, id, NULL);
503: fparams->shift(param);
504: Expression *e = new IdentifierExp(0, id);
warning C6211: Leaking memory 'e' due to an exception. Consider using a local catch block to clean up memory: Lines: 501, 502, 503, 504, 505
505: Expressions *arguments = new Expressions();
warning C6211: Leaking memory 'arguments' due to an exception. Consider using a local catch block to clean up memory: Lines: 501, 502, 503, 504, 505, 506
506: Expression *index = new IdentifierExp(0, Id::p);
507: arguments->push(index);
508: e = new ArrayExp(0, e, arguments);
509: return e;
510: }
511:
512: Expression *AssignExp::buildArrayLoop(Parameters *fparams)
513: {
514: /* Evaluate assign expressions right to left
515: */
516: Expression *ex2 = e2->buildArrayLoop(fparams);
517: #if DMDV2
518: /* Need the cast because:
519: * b = c + p[i];
520: * where b is a byte fails because (c + p[i]) is an int
521: * which cannot be implicitly cast to byte.
522: */
523: ex2 = new CastExp(0, ex2, e1->type->nextOf());
524: #endif
525: Expression *ex1 = e1->buildArrayLoop(fparams);
526: Parameter *param = fparams->tdata()[0];
527: param->storageClass = 0;
528: Expression *e = new AssignExp(0, ex1, ex2);
529: return e;
530: }
531:
532: #define X(Str) \
533: Expression *Str##AssignExp::buildArrayLoop(Parameters *fparams) \
534: { \
535: /* Evaluate assign expressions right to left \
536: */ \
537: Expression *ex2 = e2->buildArrayLoop(fparams); \
538: Expression *ex1 = e1->buildArrayLoop(fparams); \
539: Parameter *param = fparams->tdata()[0]; \
540: param->storageClass = 0; \
541: Expression *e = new Str##AssignExp(0, ex1, ex2); \
542: return e; \
543: }
544:
545: X(Add)
546: X(Min)
547: X(Mul)
548: X(Div)
549: X(Mod)
550: X(Xor)
551: X(And)
552: X(Or)
553:
554: #undef X
555:
556: Expression *NegExp::buildArrayLoop(Parameters *fparams)
557: {
558: Expression *ex1 = e1->buildArrayLoop(fparams);
559: Expression *e = new NegExp(0, ex1);
560: return e;
561: }
562:
563: Expression *ComExp::buildArrayLoop(Parameters *fparams)
564: {
565: Expression *ex1 = e1->buildArrayLoop(fparams);
566: Expression *e = new ComExp(0, ex1);
567: return e;
568: }
569:
570: #define X(Str) \
571: Expression *Str##Exp::buildArrayLoop(Parameters *fparams) \
572: { \
573: /* Evaluate assign expressions left to right \
574: */ \
575: Expression *ex1 = e1->buildArrayLoop(fparams); \
576: Expression *ex2 = e2->buildArrayLoop(fparams); \
577: Expression *e = new Str##Exp(0, ex1, ex2); \
578: return e; \
579: }
580:
581: X(Add)
582: X(Min)
583: X(Mul)
584: X(Div)
585: X(Mod)
586: X(Xor)
587: X(And)
588: X(Or)
589:
590: #undef X
591:
592:
593: /***********************************************
594: * Test if operand is a valid array op operand.
595: */
596:
597: int Expression::isArrayOperand()
598: {
599: //printf("Expression::isArrayOperand() %s\n", toChars());
600: if (op == TOKslice)
601: return 1;
602: if (type->toBasetype()->ty == Tarray)
603: {
604: switch (op)
605: {
606: case TOKadd:
607: case TOKmin:
608: case TOKmul:
609: case TOKdiv:
610: case TOKmod:
611: case TOKxor:
612: case TOKand:
613: case TOKor:
614: case TOKassign:
615: case TOKaddass:
616: case TOKminass:
617: case TOKmulass:
618: case TOKdivass:
619: case TOKmodass:
620: case TOKxorass:
621: case TOKandass:
622: case TOKorass:
623: #if DMDV2
624: case TOKpow:
625: case TOKpowass:
626: #endif
627: case TOKneg:
628: case TOKtilde:
629: return 1;
630:
631: default:
632: break;
633: }
634: }
635: return 0;
636: }
637: