1/*********************************************************************
2 *   Copyright 1993, UCAR/Unidata
3 *   See netcdf/COPYRIGHT file for copying and redistribution conditions.
4 *********************************************************************/
5
6#include "config.h"
7
8#include <stdlib.h>
9#include <stdio.h>
10#include <string.h>
11#include <assert.h>
12
13#include "nclist.h"
14#include "ncbytes.h"
15#include "nclog.h"
16
17#include "netcdf.h"
18#include "dceconstraints.h"
19#include "dapdebug.h"
20#include "dceparselex.h"
21
22#define DEBUG
23
24#define LBRACE "{"
25#define RBRACE "}"
26
27int dceverbose = 0;
28
29static char* opstrings[] = OPSTRINGS ;
30
31static void ceallnodesr(DCEnodenodeNClistallnodesCEsort which);
32static void dcedump(DCEnodenodeNCbytesbuf);
33static void dcedumpraw(DCEnodenodeNCbytesbuf);
34static void dcedumprawlist(NClistlistNCbytesbuf);
35
36#if 0 /*not currently used */
37/* Parse incoming url constraints, if any,
38   to check for syntactic correctness
39*/
40int
41dapparseconstraints(char* constraintsDCEconstraintdapconstraint)
42{
43    int ncstat = NC_NOERR;
44    char* errmsg;
45
46    assert(dapconstraint != NULL);
47    nclistclear(dapconstraint->projections);
48    nclistclear(dapconstraint->selections);
49
50    ncstat = dapceparse(constraints,dapconstraint,&errmsg);
51    if(ncstat) {
52 nclog(NCLOGWARN,"DAP constraint parse failure: %s",errmsg);
53 if(errmsg) free(errmsg);
54        nclistclear(dapconstraint->projections);
55        nclistclear(dapconstraint->selections);
56    }
57
58#ifdef DEBUG
59fprintf(stderr,"constraint: %s",dcetostring((DCEnode*)dapconstraint));
60#endif
61    return ncstat;
62}
63#endif
64
65#ifdef DEBUG1
66static void
67slicedump(const char* prefixDCEslices)
68{
69#if 1
70    int v = dceverbose;
71    dceverbose = 1;
72    fprintf(stderr,"%s: %s\n",prefix,dcetostring((DCEnode*)s));
73    dceverbose = v;
74#else
75    size_t last = (s->first+s->length)-1;
76    fprintf(stderr,"%s: [%lu:%lu:%lu p=%lu l=%lu c=%lu]\n",
77 prefix,s->first,s->stride,last,s->stop,s->length,s->count);
78#endif
79}
80#endif
81
82
83/*
84Compose slice s1 with slice s2 -> sr
85Compose means that the s2 constraint is applied
86to the output of the s1 constraint.
87
88Logical derivation of s1 compose s2 = sr
89We have three index sequences to deal with,
90where the sequence is the range [0..last].
91
921. the original data indices [0..N]
932. the indices resulting from applying slice s1;
94   this will be a subset of #1 with the sequence
95   [s1.first .. s1.last] where s1.last = s1.first + s1.length - 1
963. the indices resulting from applying s2:[0..s2.last] wrt
97   to output of s2
98   [s2.first .. s2.last]
99   We can convert #3 into index sequence wrt
100   #1 as follows
101   [s2.first .. s2.last] -> [map(s2.first)..map(s2.last)]
102   where map(int index) = s1.first + (s1.stride * index)
103   Note that map(i) is undefined if map(i) > s1.last
104
105
106So, we can compute the result (sr) stride and first as follows
107
108. sr.stride = s1.stride * s2.stride
109
110. sr.first   = map(s2.first) =  s1.first * (s1.stride * s2.first)
111  This throws an exception if sr.first > s1.last
112
113. compute the s1.last wrt original data
114   last1 = s1.first + (s1.length - 1)
115
116. compute the s2.last wrt s2
117   last2 = s2.first + (s2.length - 1)
118
119. compute candidate last wrt original index sequence
120   lastx = map(last2) = s1.first + (s1.stride * last2)
121
122. It is possible that lastx is outside of the range (s1.first..s1.last)
123  so we take the min of last2 and lastx to ensure no overrun wrt s1
124   sr.last = min(last1,lastx)
125
126. If we want to be pedantic, we need to reduce
127  sr.last so that it is on an exact multiple of sr.stride
128  starting at sr.first
129    delta = ((sr.last + (sr.stride-1)) / sr.stride) * sr.stride
130    sr.last = sr.first + delta
131
132. compute result length using sr.last
133   sr.len = (sr.last + 1) - sr.first
134
135Example 1:
1360000000000111111111
1370123456789012345678
138 xxxxxxxxx
139 0 1 2 3 4                s1=(f=1 st=2 len=9)
140 0 1 2 3 4                s2=(f=0 st=1 len=5)
141 xxxxxxxxxy
142 0 1 3 4 5   sr=(f=1 st=2 len=9..10)
143
144Example 2:
1450000000000111111111122222222223
1460123456789012345678901234567890
147 xxxxxxxxxxxxxxxxxxxxxxxxx
148 0  1  2  3  4  5  6  7  8  _  _  _  s1=(f=1 st=3 len=25)
149          0     1     2     3     4  s2=(f=3 st=2 len=5)
150          xxxxxxxxxxxxxyyyyy
151          0     1     2              sr=(f=10 st=6 l=13..17)
152
153Example 3:
1540000000000111111
1550123456789012345
156 xxxxxxxxx
157 0 1 2 3 4 _ _            s1=(f=1 st=2 len=9)
158     0 1 2 3 4            s2=(f=2 st=1 len=4)
159     xxxxxy               ----------------------------
160   sr=(f=5 st=2 len=5..6)
161Example 4:
1620000000000111111111
1630123456789012345678
164 xxxxxxxxx
165 0 1 2 3 4 _ _ _ _       s1=(f=1 st=2 len=9)
166     0   1   2   3       s2=(f=2 st=2 len=4)
167     xxxxxxyy
168                          sr=(f=5 st=4 len=6..8)
169
170Example 5:
17100000000001
17201234567890
173xxx
174012                       s1=(f=0 st=1 l=3)
175012                       s2=(f=0 st=1 l=3)
176xxx           ----------------------------
177012                       sr=(f=0 st=1 l=3)
178
179Example 6:
18000000
18101234
182xx
18301                        s1=(f=0 st=1 l=2)
1840                         s2=(f=0 st=1 l=1)
185x           ----------------------------
186                          sr=(f=0 st=1 l=1)
187
188*/
189
190#define MAP(s1,i) ((s1)->first + ((s1)->stride*(i)))
191#define XMIN(x,y) ((x) < (y) ? (x) : (y))
192#define XMAX(x,y) ((x) > (y) ? (x) : (y))
193
194int
195dceslicecompose(DCEslices1DCEslices2DCEsliceresult)
196{
197    int err = NC_NOERR;
198    size_t lastx = 0;
199    DCEslice sr; /* For back compatibility so s1 and result can be same object */
200#ifdef DEBUG1
201slicedump("compose: s1",s1);
202slicedump("compose: s2",s2);
203#endif
204    sr.node.sort = CES_SLICE;
205    sr.stride    = s1->stride * s2->stride;
206    sr.first     = MAP(s1,s2->first);
207    if(sr.first > s1->last)
208 return NC_EINVALCOORDS;
209    lastx        = MAP(s1,s2->last);
210    sr.last      = XMIN(s1->last,lastx);
211    sr.length    = (sr.last + 1) - sr.first;
212    sr.declsize = XMAX(s1->declsize,s2->declsize); /* use max declsize */
213    /* fill in other fields */
214    sr.count = (sr.length + (sr.stride - 1))/sr.stride;
215    *result = sr;
216#ifdef DEBUG1
217slicedump("compose: result",result);
218#endif
219    return err;
220}
221
222/*
223Given two projection lists, merge
224src into dst taking
225overlapping projections into acct.
226Dst will be modified.
227*/
228
229int
230dcemergeprojectionlists(NClistdstNClistsrc)
231{
232    int i;
233    NClistcat = nclistnew();
234    int ncstat = NC_NOERR;
235
236#ifdef DEBUG
237fprintf(stderr,"dapmergeprojection: dst = %s\n",dcetostring((DCEnode*)dst));
238fprintf(stderr,"dapmergeprojection: src = %s\n",dcetostring((DCEnode*)src));
239#endif
240
241    /* get dst concat clone(src) */
242    nclistsetalloc(cat,nclistlength(dst)+nclistlength(src));
243    for(i=0;i<nclistlength(dst);i++) {
244 DCEprojectionp = (DCEprojection*)nclistget(dst,i);
245 nclistpush(cat,(void*)p);
246    }
247    for(i=0;i<nclistlength(src);i++) {
248 DCEprojectionp = (DCEprojection*)nclistget(src,i);
249 nclistpush(cat,(void*)dceclone((DCEnode*)p));
250    }
251
252    nclistclear(dst);
253
254    /* Repeatedly pull elements from the concat,
255       merge with all duplicates, and stick into
256       the dst
257    */
258    while(nclistlength(cat) > 0) {
259 DCEprojectiontarget = (DCEprojection*)nclistremove(cat,0);
260 if(target == NULL) continue;
261        if(target->discrim != CES_VAR) continue;
262        for(i=0;i<nclistlength(cat);i++) {
263     DCEprojectionp2 = (DCEprojection*)nclistget(cat,i);
264     if(p2 == NULL) continue;
265     if(p2->discrim != CES_VAR) continue;
266     if(dcesamepath(target->var->segments,
267    p2->var->segments)!=0) continue;
268     /* This entry matches our current target; merge  */
269     ncstat = dcemergeprojections(target,p2);
270     /* null out this merged entry and release it */
271     nclistset(cat,i,(void*)NULL);
272     dcefree((DCEnode*)p2);
273 }
274 /* Capture the clone */
275 nclistpush(dst,(void*)target);
276    }
277    nclistfree(cat);
278    return ncstat;
279}
280
281/* Modify merged projection to include "addition" projection */
282int
283dcemergeprojections(DCEprojectionmergedDCEprojectionaddition)
284{
285    int ncstat = NC_NOERR;
286    int i,j;
287
288    ASSERT((merged->discrim == CES_VAR && addition->discrim == CES_VAR));
289    ASSERT((nclistlength(merged->var->segments) == nclistlength(addition->var->segments)));
290    for(i=0;i<nclistlength(merged->var->segments);i++) {
291 DCEsegmentmergedseg = (DCEsegment*)nclistget(merged->var->segments,i);
292 DCEsegmentaddedseg = (DCEsegment*)nclistget(addition->var->segments,i);
293 /* If one segment has larger rank, then copy the extra slices unchanged */
294 for(j=0;j<addedseg->rank;j++) {
295     if(j < mergedseg->rank)
296         dceslicecompose(mergedseg->slices+j,addedseg->slices+j,mergedseg->slices+j);
297     else
298 mergedseg->slices[j] = addedseg->slices[j];
299 }
300 if(addedseg->rank > mergedseg->rank)
301     mergedseg->rank = addedseg->rank;
302    }
303    return ncstat;
304}
305
306/* Convert a DCEprojection instance into a string
307   that can be used with the url
308*/
309
310char*
311dcebuildprojectionstring(NClistprojections)
312{
313    char* pstring;
314    NCbytesbuf = ncbytesnew();
315    dcelisttobuffer(projections,buf,",");
316    pstring = ncbytesdup(buf);
317    ncbytesfree(buf);
318    return pstring;
319}
320
321char*
322dcebuildselectionstring(NClistselections)
323{
324    NCbytesbuf = ncbytesnew();
325    char* sstring;
326    dcelisttobuffer(selections,buf,",");
327    sstring = ncbytesdup(buf);
328    ncbytesfree(buf);
329    return sstring;
330}
331
332char*
333dcebuildconstraintstring(DCEconstraintconstraints)
334{
335    NCbytesbuf = ncbytesnew();
336    char* result = NULL;
337    dcetobuffer((DCEnode*)constraints,buf);
338    result = ncbytesdup(buf);
339    ncbytesfree(buf);
340    return result;
341}
342
343DCEnode*
344dceclone(DCEnodenode)
345{
346    DCEnoderesult = NULL;
347
348    result = (DCEnode*)dcecreate(node->sort);
349    if(result == NULL) goto done;
350
351    switch (node->sort) {
352
353    case CES_SLICE: {
354 DCEsliceclone = (DCEslice*)result;
355 DCEsliceorig = (DCEslice*)node;
356 *clone = *orig;
357    } break;
358
359    case CES_SEGMENT: {
360 DCEsegmentclone = (DCEsegment*)result;
361 DCEsegmentorig = (DCEsegment*)node;
362 *clone = *orig;
363        clone->name = nulldup(orig->name);
364 if(orig->rank > 0)
365     memcpy(clone->slices,orig->slices,orig->rank*sizeof(DCEslice));
366    } break;
367
368    case CES_VAR: {
369 DCEvarclone = (DCEvar*)result;
370 DCEvarorig = (DCEvar*)node;
371 *clone = *orig;
372 clone->segments = dceclonelist(clone->segments);
373    } break;
374
375    case CES_FCN: {
376 DCEfcnclone = (DCEfcn*)result;
377 DCEfcnorig = (DCEfcn*)node;
378 *clone = *orig;
379        clone->name = nulldup(orig->name);
380 clone->args = dceclonelist(orig->args);
381    } break;
382
383    case CES_CONST: {
384 DCEconstantclone = (DCEconstant*)result;
385 DCEconstantorig = (DCEconstant*)node;
386 *clone = *orig;
387        if(clone->discrim ==  CES_STR)
388     clone->text = nulldup(clone->text);
389    } break;
390
391    case CES_VALUE: {
392 DCEvalueclone = (DCEvalue*)result;
393 DCEvalueorig = (DCEvalue*)node;
394 *clone = *orig;
395        switch (clone->discrim) {
396        case CES_CONST:
397     clone->constant = (DCEconstant*)dceclone((DCEnode*)orig->constant); break;
398        case CES_VAR:
399     clone->var = (DCEvar*)dceclone((DCEnode*)orig->var); break;
400        case CES_FCN:
401     clone->fcn = (DCEfcn*)dceclone((DCEnode*)orig->fcn); break;
402        default: assert(0);
403        }
404    } break;
405
406    case CES_PROJECT: {
407 DCEprojectionclone = (DCEprojection*)result;
408 DCEprojectionorig = (DCEprojection*)node;
409 *clone = *orig;
410 switch (orig->discrim) {
411 case CES_VAR:
412            clone->var = (DCEvar*)dceclone((DCEnode*)orig->var); break;
413 case CES_FCN:
414            clone->fcn = (DCEfcn*)dceclone((DCEnode*)orig->fcn); break;
415 default: assert(0);
416 }
417    } break;
418
419    case CES_SELECT: {
420 DCEselectionclone = (DCEselection*)result;
421 DCEselectionorig = (DCEselection*)node;
422 *clone = *orig;
423 clone->lhs = (DCEvalue*)dceclone((DCEnode*)orig->lhs);
424 clone->rhs = dceclonelist(orig->rhs);
425    } break;
426
427    case CES_CONSTRAINT: {
428 DCEconstraintclone = (DCEconstraint*)result;
429 DCEconstraintorig = (DCEconstraint*)node;
430 *clone = *orig;
431 clone->projections = dceclonelist(orig->projections);
432 clone->selections = dceclonelist(orig->selections);
433    } break;
434
435    default:
436 assert(0);
437    }
438
439done:
440    return result;
441}
442
443NClist*
444dceclonelist(NClistlist)
445{
446    int i;
447    NClistclone;
448    if(list == NULL) return NULL;
449    clone = nclistnew();
450    for(i=0;i<nclistlength(list);i++) {
451 DCEnodenode = (DCEnode*)nclistget(list,i);
452 DCEnodenewnode = dceclone((DCEnode*)node);
453 nclistpush(clone,(void*)newnode);
454    }
455    return clone;
456}
457
458void
459dcefree(DCEnodenode)
460{
461    if(node == NULL) return;
462
463    switch (node->sort) {
464
465    case CES_VAR: {
466 DCEvartarget = (DCEvar*)node;
467 dcefreelist(target->segments);
468    } break;
469
470    case CES_FCN: {
471 DCEfcntarget = (DCEfcn*)node;
472 dcefreelist(target->args);
473        nullfree(target->name);
474    } break;
475
476    case CES_CONST: {
477 DCEconstanttarget = (DCEconstant*)node;
478 if(target->discrim == CES_STR)
479     nullfree(target->text);
480    } break;
481
482    case CES_VALUE: {
483 DCEvaluetarget = (DCEvalue*)node;
484 switch(target->discrim) {
485        case CES_CONSTdcefree((DCEnode*)target->constant); break;
486        case CES_VARdcefree((DCEnode*)target->var); break;
487        case CES_FCNdcefree((DCEnode*)target->fcn); break;
488        default: assert(0);
489        }
490    } break;
491
492    case CES_PROJECT: {
493 DCEprojectiontarget = (DCEprojection*)node;
494 switch (target->discrim) {
495 case CES_VARdcefree((DCEnode*)target->var); break;
496 case CES_FCNdcefree((DCEnode*)target->fcn); break;
497 default: assert(0);
498 }
499    } break;
500
501    case CES_SELECT: {
502 DCEselectiontarget = (DCEselection*)node;
503 dcefreelist(target->rhs);
504 dcefree((DCEnode*)target->lhs);
505    } break;
506
507    case CES_CONSTRAINT: {
508 DCEconstrainttarget = (DCEconstraint*)node;
509 dcefreelist(target->projections);
510 dcefreelist(target->selections);
511    } break;
512
513    case CES_SEGMENT: {
514 DCEsegmenttarget = (DCEsegment*)node;
515 target->rank = 0;
516        nullfree(target->name);
517    } break;
518
519    case CES_SLICE: {
520    } break;
521
522    default:
523 assert(0);
524    }
525
526    /* final action */
527    free(node);
528}
529
530void
531dcefreelist(NClistlist)
532{
533    int i;
534    if(list == NULL) return;
535    for(i=0;i<nclistlength(list);i++) {
536 DCEnodenode = (DCEnode*)nclistget(list,i);
537 dcefree((DCEnode*)node);
538    }
539    nclistfree(list);
540}
541
542char*
543dcetostring(DCEnodenode)
544{
545    char* s;
546    NCbytesbuf = ncbytesnew();
547    dcetobuffer(node,buf);
548    s = ncbytesextract(buf);
549    ncbytesfree(buf);
550    return s;
551}
552
553/* Mostly for debugging */
554char*
555dcerawtostring(void* node)
556{
557    char* s;
558    NCbytesbuf = ncbytesnew();
559    dcedumpraw((DCEnode*)node,buf);
560    s = ncbytesextract(buf);
561    ncbytesfree(buf);
562    return s;
563}
564
565char*
566dcerawlisttostring(NClistlist)
567{
568    char* s;
569    NCbytesbuf = ncbytesnew();
570    dcedumprawlist(list,buf);
571    s = ncbytesextract(buf);
572    ncbytesfree(buf);
573    return s;
574}
575
576/* For debugging */
577#ifdef DEBUG
578static char*
579dimdecl(size_t declsize)
580{
581    static char tag[16];
582    tag[0] = '\0';
583    if(dceverbose)
584        snprintf(tag,sizeof(tag),"/%lu",(unsigned long)declsize);
585    return tag;
586}
587#else
588static char*
589dimdecl(size_t declsize)
590{
591    return "";
592}
593#endif
594
595void
596dcetobuffer(DCEnodenodeNCbytesbuf)
597{
598    dcedump(node,buf);
599}
600
601static void
602dcedump(DCEnodenodeNCbytesbuf)
603{
604    int i;
605    char tmp[1024];
606
607    if(buf == NULL) return;
608    if(node == NULL) {ncbytescat(buf,"<null>"); return;}
609
610    switch (node->sort) {
611
612    case CES_SLICE: {
613     DCEsliceslice = (DCEslice*)node;
614     size_t last = (slice->first+slice->length)-1;
615            if(slice->count == 1) {
616                snprintf(tmp,sizeof(tmp),"[%lu%s]",
617             (unsigned long)slice->first,dimdecl(slice->declsize));
618            } else if(slice->stride == 1) {
619                snprintf(tmp,sizeof(tmp),"[%lu:%lu%s]",
620             (unsigned long)slice->first,
621             (unsigned long)last,
622             dimdecl(slice->declsize));
623            } else {
624         snprintf(tmp,sizeof(tmp),"[%lu:%lu:%lu%s]",
625     (unsigned long)slice->first,
626     (unsigned long)slice->stride,
627     (unsigned long)last,
628             dimdecl(slice->declsize));
629     }
630            ncbytescat(buf,tmp);
631    } break;
632
633    case CES_SEGMENT: {
634 DCEsegmentsegment = (DCEsegment*)node;
635        int rank = segment->rank;
636 char* name = (segment->name?segment->name:"<unknown>");
637 name = nulldup(name);
638 ncbytescat(buf,name);
639 nullfree(name);
640        if(dceverbose && dceiswholesegment(segment))
641     ncbytescat(buf,"*");
642        if(dceverbose || !dceiswholesegment(segment)) {
643            for(i=0;i<rank;i++) {
644         DCEsliceslice = segment->slices+i;
645                dcetobuffer((DCEnode*)slice,buf);
646     }
647 }
648    } break;
649
650    case CES_VAR: {
651 DCEvarvar = (DCEvar*)node;
652 dcelisttobuffer(var->segments,buf,".");
653    } break;
654
655    case CES_FCN: {
656 DCEfcnfcn = (DCEfcn*)node;
657        ncbytescat(buf,fcn->name);
658        ncbytescat(buf,"(");
659 dcelisttobuffer(fcn->args,buf,",");
660        ncbytescat(buf,")");
661    } break;
662
663    case CES_CONST: {
664 DCEconstantvalue = (DCEconstant*)node;
665        switch (value->discrim) {
666        case CES_STR:
667     ncbytescat(buf,value->text);
668     break;
669        case CES_INT:
670            snprintf(tmp,sizeof(tmp),"%lld",value->intvalue);
671            ncbytescat(buf,tmp);
672     break;
673        case CES_FLOAT:
674            snprintf(tmp,sizeof(tmp),"%g",value->floatvalue);
675            ncbytescat(buf,tmp);
676     break;
677        default: assert(0);
678 }
679    } break;
680
681    case CES_VALUE: {
682 DCEvaluevalue = (DCEvalue*)node;
683        switch (value->discrim) {
684        case CES_CONST:
685         dcetobuffer((DCEnode*)value->constant,buf);
686           break;
687        case CES_VAR:
688         dcetobuffer((DCEnode*)value->var,buf);
689         break;
690        case CES_FCN:
691         dcetobuffer((DCEnode*)value->fcn,buf);
692         break;
693        default: assert(0);
694        }
695    } break;
696
697    case CES_PROJECT: {
698 DCEprojectiontarget = (DCEprojection*)node;
699 switch (target->discrim) {
700 case CES_VAR:
701     dcetobuffer((DCEnode*)target->var,buf);
702     break;
703 case CES_FCNdcetobuffer((DCEnode*)target->fcn,buf); break;
704 default: assert(0);
705 }
706    } break;
707
708    case CES_SELECT: {
709 DCEselectionsel = (DCEselection*)node;
710 dcetobuffer((DCEnode*)sel->lhs,buf);
711        if(sel->operator == CES_NIL) break;
712        ncbytescat(buf,opstrings[(int)sel->operator]);
713        if(nclistlength(sel->rhs) > 1)
714            ncbytescat(buf,"{");
715 dcelisttobuffer(sel->rhs,buf,",");
716        if(nclistlength(sel->rhs) > 1)
717     ncbytescat(buf,"}");
718    } break;
719
720    case CES_CONSTRAINT: {
721 DCEconstraintcon = (DCEconstraint*)node;
722        if(con->projections != NULL && nclistlength(con->projections) > 0) {
723            dcelisttobuffer(con->projections,buf,",");
724 }
725        if(con->selections != NULL && nclistlength(con->selections) > 0) {
726     ncbytescat(buf,"&"); /* because & is really a prefix */
727            dcelisttobuffer(con->selections,buf,"&");
728 }
729    } break;
730
731    case CES_NIL: {
732 ncbytescat(buf,"<nil>");
733    } break;
734
735    default:
736 assert(0);
737    }
738}
739
740char*
741dcelisttostring(NClistlist, char* sep)
742{
743    char* s;
744    NCbytesbuf = ncbytesnew();
745    dcelisttobuffer(list,buf,sep);
746    s = ncbytesextract(buf);
747    ncbytesfree(buf);
748    return s;
749}
750
751void
752dcelisttobuffer(NClistlistNCbytesbuf, char* sep)
753{
754    int i;
755    if(list == NULL || buf == NULL) return;
756    if(sep == NULLsep = ",";
757    for(i=0;i<nclistlength(list);i++) {
758 DCEnodenode = (DCEnode*)nclistget(list,i);
759 if(node == NULL) continue;
760 if(i>0) ncbytescat(buf,sep);
761 dcetobuffer((DCEnode*)node,buf);
762    }
763}
764
765/* Collect all nodes within a specified constraint tree */
766/* Caller frees result */
767NClist*
768dceallnodes(DCEnodenodeCEsort which)
769{
770    NClistallnodes = nclistnew();
771    ceallnodesr(node,allnodes,which);
772    return allnodes;
773}
774
775static void
776ceallnodesr(DCEnodenodeNClistallnodesCEsort which)
777{
778    int i;
779    if(node == NULL) return;
780    if(nclistcontains(allnodes,(void*)node)) return;
781    if(which == CES_NIL || node->sort == which)
782        nclistpush(allnodes,(void*)node);
783    switch(node->sort) {
784    case CES_FCN: {
785 DCEfcnfcn = (DCEfcn*)node;
786 for(i=0;i<nclistlength(fcn->args);i++) {
787     ceallnodesr((DCEnode*)nclistget(fcn->args,i),allnodes,which);
788 }
789    } break;
790    case CES_VAR: {
791 DCEvarvar = (DCEvar*)node;
792 for(i=0;i<nclistlength(var->segments);i++) {
793     ceallnodesr((DCEnode*)nclistget(var->segments,i),allnodes,which);
794 }
795    } break;
796    case CES_VALUE: {
797 DCEvaluevalue = (DCEvalue*)node;
798 if(value->discrim == CES_VAR)
799     ceallnodesr((DCEnode*)value->var,allnodes,which);
800 else if(value->discrim == CES_FCN)
801     ceallnodesr((DCEnode*)value->fcn,allnodes,which);
802 else
803     ceallnodesr((DCEnode*)value->constant,allnodes,which);
804    } break;
805    case CES_SELECT: {
806 DCEselectionselection = (DCEselection*)node;
807        ceallnodesr((DCEnode*)selection->lhs,allnodes,which);
808 for(i=0;i<nclistlength(selection->rhs);i++)
809            ceallnodesr((DCEnode*)nclistget(selection->rhs,i),allnodes,which);
810    } break;
811    case CES_PROJECT: {
812 DCEprojectionprojection = (DCEprojection*)node;
813 if(projection->discrim == CES_VAR)
814     ceallnodesr((DCEnode*)projection->var,allnodes,which);
815 else
816     ceallnodesr((DCEnode*)projection->fcn,allnodes,which);
817    } break;
818    case CES_CONSTRAINT: {
819 DCEconstraintconstraint = (DCEconstraint*)node;
820 for(i=0;i<nclistlength(constraint->projections);i++)
821     ceallnodesr((DCEnode*)nclistget(constraint->projections,i),allnodes,which);
822 for(i=0;i<nclistlength(constraint->selections);i++)
823     ceallnodesr((DCEnode*)nclistget(constraint->selections,i),allnodes,which);
824    } break;
825
826    /* All others have no subnodes */
827    default:
828 break;
829    }
830}
831
832DCEnode*
833dcecreate(CEsort sort)
834{
835    DCEnodenode = NULL;
836
837    switch (sort) {
838
839    case CES_SLICE: {
840 DCEslicetarget = (DCEslice*)calloc(1,sizeof(DCEslice));
841 if(target == NULL) return NULL;
842 node = (DCEnode*)target;
843    } break;
844
845    case CES_SEGMENT: {
846 int i;
847 DCEsegmenttarget = (DCEsegment*)calloc(1,sizeof(DCEsegment));
848 if(target == NULL) return NULL;
849 /* Initialize the sort of the slices */
850 for(i=0;i<NC_MAX_VAR_DIMS;i++)
851     target->slices[i].node.sort = CES_SLICE;
852 node = (DCEnode*)target;
853    } break;
854
855    case CES_CONST: {
856 DCEconstanttarget = (DCEconstant*)calloc(1,sizeof(DCEconstant));
857 if(target == NULL) return NULL;
858 node = (DCEnode*)target;
859 target->discrim = CES_NIL;
860    } break;
861
862    case CES_VALUE: {
863 DCEvaluetarget = (DCEvalue*)calloc(1,sizeof(DCEvalue));
864 if(target == NULL) return NULL;
865 node = (DCEnode*)target;
866 target->discrim = CES_NIL;
867    } break;
868
869    case CES_VAR: {
870 DCEvartarget = (DCEvar*)calloc(1,sizeof(DCEvar));
871 if(target == NULL) return NULL;
872 node = (DCEnode*)target;
873    } break;
874
875    case CES_FCN: {
876 DCEfcntarget = (DCEfcn*)calloc(1,sizeof(DCEfcn));
877 if(target == NULL) return NULL;
878 node = (DCEnode*)target;
879    } break;
880
881    case CES_PROJECT: {
882 DCEprojectiontarget = (DCEprojection*)calloc(1,sizeof(DCEprojection));
883 if(target == NULL) return NULL;
884 node = (DCEnode*)target;
885    } break;
886
887    case CES_SELECT: {
888 DCEselectiontarget = (DCEselection*)calloc(1,sizeof(DCEselection));
889 if(target == NULL) return NULL;
890 node = (DCEnode*)target;
891 target->operator = CEO_NIL;
892    } break;
893
894    case CES_CONSTRAINT: {
895 DCEconstrainttarget = (DCEconstraint*)calloc(1,sizeof(DCEconstraint));
896 if(target == NULL) return NULL;
897 node = (DCEnode*)target;
898    } break;
899
900    default:
901 assert(0);
902    }
903
904    /* final action */
905    node->sort = sort;
906    return node;
907}
908
909int
910dceiswholeslice(DCEsliceslice)
911{
912    if(slice->first != 0
913       || slice->stride != 1
914       || slice->length != slice->declsize) return 0;
915    return 1;
916}
917
918int
919dceiswholesegment(DCEsegmentseg)
920{
921    int i,whole;
922
923    if(!seg->slicesdefined) return 0; /* actually, we don't know */
924    whole = 1; /* assume so */
925    for(i=0;i<seg->rank;i++) {
926 if(!dceiswholeslice(&seg->slices[i])) {whole = 0; break;}
927    }
928    return whole;
929}
930
931void
932dcemakewholeslice(DCEsliceslice, size_t declsize)
933{
934    slice->first = 0;
935    slice->stride = 1;
936    slice->length = declsize;
937    slice->declsize = declsize;
938    slice->count = declsize;
939    slice->last = slice->length - 1;
940}
941
942/* Remove slicing from terminal segment of p */
943void
944dcemakewholeprojection(DCEprojectionp)
945{
946    /* Remove the slicing (if any) from the last segment */
947    if(p->discrim == CES_VAR && p->var != NULL && p->var->segments != NULL) {
948        int lastindex = nclistlength(p->var->segments) - 1;
949        DCEsegmentlastseg = (DCEsegment*)nclistget(p->var->segments,lastindex);
950        lastseg->rank = 0;
951    }
952}
953
954int
955dcesamepath(NClistlist1NClistlist2)
956{
957    int i;
958    int len = nclistlength(list1);
959    if(len != nclistlength(list2)) return 0;
960    for(i=0;i<len;i++) {
961 DCEsegments1 = (DCEsegment*)nclistget(list1,i);
962 DCEsegments2 = (DCEsegment*)nclistget(list2,i);
963 if(strcmp(s1->name,s2->name) != 0) return 0;
964    }
965    return 1;
966}
967
968void
969dcesegment_transpose(DCEsegmentsegment,
970  size_t* start,
971  size_t* count,
972  size_t* stride,
973  size_t* sizes
974 )
975{
976    int i;
977    if(segment != NULL && sizes != NULL) {
978        for(i=0;i<segment->rank;i++) {
979     if(start != NULLstart[i] = segment->slices[i].first;
980     if(count != NULLcount[i] = segment->slices[i].count;
981     if(stride != NULLstride[i] = (size_t)segment->slices[i].stride;
982     if(sizes != NULLsizes[i] = segment->slices[i].declsize;
983 }
984    }
985}
986
987/* Compute segment size for subset of slices */
988size_t
989dcesegmentsize(DCEsegmentseg, size_t start, size_t stop)
990{
991    int icount;
992    if(!seg->slicesdefined) return 0; /* actually, we don't know */
993    for(count=1,i=start;i<stop;i++) {
994 count *= seg->slices[i].count;
995    }
996    return count;
997}
998
999/* Return the index of the leftmost slice
1000   starting at start and up to, but not including
1001   stop, such that it and all slices to the right
1002   are "safe". Safe means dceiswholeslice() is true.
1003   In effect, we can read the safe index set as a
1004   single chunk. Return stop if there is no safe index.
1005*/
1006
1007size_t
1008dcesafeindex(DCEsegmentseg, size_t start, size_t stop)
1009{
1010    size_t safe;
1011    if(!seg->slicesdefined) return stop; /* actually, we don't know */
1012    if(stop == 0) return stop;
1013    /* watch out because safe is unsigned */
1014    for(safe=stop-1;safe>start;safe--) {
1015 if(!dceiswholeslice(&seg->slices[safe])) return safe+1;
1016    }
1017    return dceiswholeslice(&seg->slices[start]) ? start /*every slice is safe*/
1018                                                 : start+1 ;
1019}
1020
1021
1022static const char*
1023dcesortname(CEsort sort)
1024{
1025    switch (sort) {
1026    case CES_SLICE: return "SLICE";
1027    case CES_SEGMENT: return "SEGMENT";
1028    case CES_VAR: return "VAR";
1029    case CES_FCN: return "FCN";
1030    case CES_CONST: return "CONST";
1031    case CES_VALUE: return "VALUE";
1032    case CES_PROJECT: return "PROJECT";
1033    case CES_SELECT: return "SELECT";
1034    case CES_CONSTRAINT: return "CONSTRAINT";
1035    case CES_STR: return "STR";
1036    case CES_INT: return "INT";
1037    case CES_FLOAT: return "FLOAT";
1038    default: break;
1039    }
1040    return "UNKNOWN";
1041}
1042
1043static void
1044dcedumpraw(DCEnodenodeNCbytesbuf)
1045{
1046    int i;
1047    char tmp[1024];
1048
1049    if(buf == NULL) return;
1050    if(node == NULL) {ncbytescat(buf,"<null>"); return;}
1051
1052    ncbytescat(buf,LBRACE);
1053    ncbytescat(buf,(char*)dcesortname(node->sort));
1054
1055    switch (node->sort) {
1056
1057    case CES_SLICE: {
1058     DCEsliceslice = (DCEslice*)node;
1059     snprintf(tmp,sizeof(tmp),
1060     " [first=%lu stride=%lu last=%lu len=%lu count=%lu size=%lu]",
1061     (unsigned long)slice->first,
1062     (unsigned long)slice->stride,
1063     (unsigned long)slice->last,
1064     (unsigned long)slice->length,
1065     (unsigned long)slice->count,
1066     (unsigned long)slice->declsize);
1067            ncbytescat(buf,tmp);
1068    } break;
1069
1070    case CES_SEGMENT: {
1071 DCEsegmentsegment = (DCEsegment*)node;
1072        int rank = segment->rank;
1073 char* name = (segment->name?segment->name:"<unknown>");
1074 ncbytescat(buf," name=");
1075 ncbytescat(buf,name);
1076        snprintf(tmp,sizeof(tmp)," rank=%lu",(unsigned long)rank);
1077 ncbytescat(buf,tmp);
1078        ncbytescat(buf," defined=");
1079        ncbytescat(buf,(segment->slicesdefined?"1":"0"));
1080        ncbytescat(buf," declized=");
1081        ncbytescat(buf,(segment->slicesdeclized?"1":"0"));
1082 if(rank > 0) {
1083            ncbytescat(buf," slices=");
1084            for(i=0;i<rank;i++) {
1085         DCEsliceslice = segment->slices+i;
1086                dcedumpraw((DCEnode*)slice,buf);
1087     }
1088 }
1089    } break;
1090
1091    case CES_VAR: {
1092 DCEvarvar = (DCEvar*)node;
1093        ncbytescat(buf," segments=");
1094 dcedumprawlist(var->segments,buf);
1095    } break;
1096
1097    case CES_FCN: {
1098 DCEfcnfcn = (DCEfcn*)node;
1099 ncbytescat(buf," name=");
1100        ncbytescat(buf,fcn->name);
1101        ncbytescat(buf,"args=");
1102 dcedumprawlist(fcn->args,buf);
1103    } break;
1104
1105    case CES_CONST: {
1106 DCEconstantvalue = (DCEconstant*)node;
1107 ncbytescat(buf," discrim=");
1108 ncbytescat(buf,dcesortname(value->discrim));
1109 ncbytescat(buf," value=");
1110        switch (value->discrim) {
1111        case CES_STR:
1112     ncbytescat(buf,"|");
1113     ncbytescat(buf,value->text);
1114     ncbytescat(buf,"|");
1115     break;
1116        case CES_INT:
1117            snprintf(tmp,sizeof(tmp),"%lld",value->intvalue);
1118            ncbytescat(buf,tmp);
1119     break;
1120        case CES_FLOAT:
1121            snprintf(tmp,sizeof(tmp),"%g",value->floatvalue);
1122            ncbytescat(buf,tmp);
1123     break;
1124        default: assert(0);
1125 }
1126    } break;
1127
1128    case CES_VALUE: {
1129 DCEvaluevalue = (DCEvalue*)node;
1130 ncbytescat(buf," discrim=");
1131 ncbytescat(buf,dcesortname(value->discrim));
1132        switch (value->discrim) {
1133        case CES_CONST:
1134         dcedumpraw((DCEnode*)value->constant,buf);
1135           break;
1136        case CES_VAR:
1137         dcedumpraw((DCEnode*)value->var,buf);
1138         break;
1139        case CES_FCN:
1140         dcedumpraw((DCEnode*)value->fcn,buf);
1141         break;
1142        default: assert(0);
1143        }
1144    } break;
1145
1146    case CES_PROJECT: {
1147 DCEprojectiontarget = (DCEprojection*)node;
1148 ncbytescat(buf," discrim=");
1149 ncbytescat(buf,dcesortname(target->discrim));
1150 switch (target->discrim) {
1151 case CES_VAR:
1152     dcedumpraw((DCEnode*)target->var,buf);
1153     break;
1154 case CES_FCN:
1155     dcedumpraw((DCEnode*)target->fcn,buf);
1156     break;
1157 default: assert(0);
1158 }
1159    } break;
1160
1161    case CES_SELECT: {
1162 DCEselectionsel = (DCEselection*)node;
1163 ncbytescat(buf," ");
1164 dcedumpraw((DCEnode*)sel->lhs,buf);
1165        if(sel->operator == CES_NIL) break;
1166        ncbytescat(buf,opstrings[(int)sel->operator]);
1167        if(nclistlength(sel->rhs) > 1)
1168            ncbytescat(buf,"{");
1169 dcedumprawlist(sel->rhs,buf);
1170        if(nclistlength(sel->rhs) > 1)
1171     ncbytescat(buf,"}");
1172    } break;
1173
1174    case CES_CONSTRAINT: {
1175 DCEconstraintcon = (DCEconstraint*)node;
1176        if(con->projections != NULL && nclistlength(con->projections) > 0) {
1177     ncbytescat(buf,"projections=");
1178            dcedumprawlist(con->projections,buf);
1179 }
1180        if(con->selections != NULL && nclistlength(con->selections) > 0) {
1181     ncbytescat(buf,"selections=");
1182            dcedumprawlist(con->selections,buf);
1183 }
1184    } break;
1185
1186    case CES_NIL: {
1187 ncbytescat(buf,"<nil>");
1188    } break;
1189
1190    default:
1191 assert(0);
1192    }
1193    ncbytescat(buf,RBRACE);
1194}
1195
1196static void
1197dcedumprawlist(NClistlistNCbytesbuf)
1198{
1199    int i;
1200    if(list == NULL || buf == NULL) return;
1201    ncbytescat(buf,"(");
1202    for(i=0;i<nclistlength(list);i++) {
1203 DCEnodenode = (DCEnode*)nclistget(list,i);
1204 if(node == NULL) continue;
1205 if(i>0) ncbytescat(buf,",");
1206 dcedumpraw((DCEnode*)node,buf);
1207    }
1208    ncbytescat(buf,")");
1209}
1210


HyperKWIC - Version 7.20DA executed at 11:37 on 27 Oct 2017 | Polyhedron Solutions - INTERNAL USE | COMMERCIAL (Any O/S) SN 4AKIed